Chapter 1 · Relations and Functions

Example 6: Same parity on {1, …, 7}

ExamplesEquivalence relations · Section 1.2

The question

Let $R$ be the relation defined in the set $A = \{1, 2, 3, 4, 5, 6, 7\}$ by $R = \{(a, b) :$ both $a$ and $b$ are either odd or even $\}$ ⁠. Show that $R$ is an equivalence relation. Further, show that all the elements of the subset $\{1, 3, 5, 7\}$ are related to each other and all the elements of the subset $\{2, 4, 6\}$ are related to each other, but no element of the subset $\{1, 3, 5, 7\}$ is related to any element of the subset $\{2, 4, 6\}$ ⁠.

Exam answer

Reflexive: For any $a \in A$ ⁠, $a$ and $a$ are both odd or both even, so $(a, a) \in R$ ⁠. Thus $R$ is reflexive.

Symmetric: Let $(a, b) \in R$ ⁠. Then $a, b$ are both odd or both even, so $b, a$ are both odd or both even and $(b, a) \in R$ ⁠. Thus $R$ is symmetric.

Transitive: Let $(a, b), (b, c) \in R$ ⁠. If $b$ is odd, then $a$ and $c$ are both odd. If $b$ is even, then $a$ and $c$ are both even. In both cases $(a, c) \in R$ ⁠. Thus $R$ is transitive.

Hence $R$ is an equivalence relation.

All elements of $\{1, 3, 5, 7\}$ are odd, so they are all related to each other. All elements of $\{2, 4, 6\}$ are even, so they are all related to each other.

An element of $\{1, 3, 5, 7\}$ is odd and an element of $\{2, 4, 6\}$ is even, so they are not related.

$\therefore$ No element of $\{1, 3, 5, 7\}$ is related to any element of $\{2, 4, 6\}$ ⁠. Hence proved.

Want the reason behind every step, the basics and the checks?

The one idea this problem is built on

"Both $a$ and $b$ are either odd or even" means $a$ and $b$ have the same parity: both odd, or both even. Every number has exactly one parity, so the relation is really "parity of $a$ = parity of $b$ ". A relation that says two things share a label is always an equivalence relation, because equality of labels is reflexive, symmetric and transitive. Its equivalence classes are the groups with the same label: the odd numbers $\{1,3,5,7\}$ and the even numbers $\{2,4,6\}$ ⁠.

Given, to show, and the plan

Given: $A = \{1,2,3,4,5,6,7\}$ and $(a,b)\in R$ exactly when $a, b$ are both odd or both even.
To show: (i) $R$ is reflexive, symmetric and transitive. (ii) Within $\{1,3,5,7\}$ every element is related to every other, and the same within $\{2,4,6\}$ ⁠. (iii) No element of $\{1,3,5,7\}$ is related to any element of $\{2,4,6\}$ ⁠.
Plan: Rewrite the rule as $p(a) = p(b)$ ⁠, where $p(x)$ is the parity of $x$ ⁠. Prove the three properties for arbitrary elements using properties of equality. Then read off the two subsets and check the "related" and "not related" claims.

Basics you need

1Odd and even

A whole number is even if it is $2k$ and odd if it is $2k+1$ for a whole number $k$ ⁠. Every integer is exactly one of the two. In $A$ ⁠: odd numbers are 1, 3, 5, 7 and even numbers are 2, 4, 6. Basics: integers, even and odd

2The three properties and equivalence

Reflexive: $(a,a)\in R$ for every $a$ ⁠. Symmetric: $(a,b)\in R \Rightarrow (b,a)\in R$ ⁠. Transitive: $(a,b),(b,c)\in R \Rightarrow (a,c)\in R$ ⁠. An equivalence relation has all three (Definition 4). Basics: reflexive, symmetric, transitive

3Equality is reflexive, symmetric and transitive

$x = x$ ⁠; $x = y \Rightarrow y = x$ ⁠; $x = y$ and $y = z \Rightarrow x = z$ ⁠. These hold for any kind of label, including the words "odd" and "even".

4Equivalence classes

The class of $a$ is the set of all elements related to $a$ ⁠. The classes of an equivalence relation do not overlap and together make up the whole set. Basics: equivalence classes

Part (i): $R$ is an equivalence relation

Rewrite the rule as an equation

For $x\in A$ let $p(x)$ be its parity: $p(x) = \text{odd}$ or $p(x) = \text{even}$ ⁠. The phrase "both $a$ and $b$ are either odd or even" means "both odd, or both even", that is
$(a,b)\in R \iff p(a) = p(b).$
For example $(3,7)\in R$ (both odd), $(2,6)\in R$ (both even), but $(3,4)\notin R$ (one odd, one even).

Each number has exactly one parity (Basic 1), so "both odd or both even" is the same as "same parity". Writing it as an equation lets us use the three properties of equality directly, which makes each step a one-line argument instead of a case split.

Every integer is either even or odd, and never both (Basic 1).
Reflexive

Take any $a\in A$ ⁠. Clearly $p(a) = p(a)$ ⁠: $a$ has the same parity as itself. So $(a,a)\in R$ for every $a\in A$ ⁠, and $R$ is reflexive.

This is the textbook's "both $a$ and $a$ must be either odd or even". If $a$ is odd then "both" are odd; if $a$ is even then "both" are even. Either way the pair $(a,a)$ satisfies the rule.

Equality is reflexive (Basic 3).
Symmetric

Suppose $(a,b)\in R$ ⁠, so $p(a) = p(b)$ ⁠. Then $p(b) = p(a)$ ⁠, which says $(b,a)\in R$ ⁠. Hence $R$ is symmetric.

The condition " $a$ and $b$ have the same parity" does not depend on the order in which we name them. Equality read backwards is still equality.

Equality is symmetric (Basic 3).
Transitive

Suppose $(a,b)\in R$ and $(b,c)\in R$ ⁠. Then $p(a) = p(b)$ and $p(b) = p(c)$ ⁠, so $p(a) = p(c)$ ⁠, that is $(a,c)\in R$ ⁠. Hence $R$ is transitive.

In words: if $b$ is odd then $a$ is odd (same as $b$ ⁠) and $c$ is odd (same as $b$ ⁠); if $b$ is even then both $a$ and $c$ are even. In either case $a$ and $c$ share a parity.

The middle element $b$ fixes one parity, and both $a$ and $c$ must agree with it. This is the textbook's "all elements $a, b, c$ must be either even or odd simultaneously". Two things that match the same thing match each other.

Equality is transitive (Basic 3).
Conclude part (i)

$R$ is reflexive, symmetric and transitive, so by Definition 4 $R$ is an equivalence relation on $A$ ⁠.

This is Example 5 restricted to a small set: two integers have the same parity exactly when their difference $a-b$ is even, so this $R$ is the relation "2 divides $a-b$ " on $\{1,\dots,7\}$ ⁠. Restricting an equivalence relation to a subset always gives an equivalence relation, since the three properties only talk about elements of the set.

Same parity $\iff$ $a - b$ even. See Example 5.

Part (ii) and (iii): the two subsets

Within $\{1,3,5,7\}$ ⁠, and within $\{2,4,6\}$ ⁠, everything is related

Take any $a, b\in\{1,3,5,7\}$ (they may be equal). Both are odd, so $p(a) = p(b) = \text{odd}$ and $(a,b)\in R$ ⁠. That gives $4\times4 = 16$ pairs. Similarly, any $a, b\in\{2,4,6\}$ are both even, so $(a,b)\in R$ ⁠, giving $3\times 3 = 9$ more pairs.

"All elements related to each other" is a claim about every pair from the subset. One reason covers all of them at once: every element of the subset has the same parity.

If a set has $n$ elements, it gives $n^2$ ordered pairs (Basic: $|S\times S| = n^2$ ⁠). Basics: sets and A × B
No element of $\{1,3,5,7\}$ is related to any element of $\{2,4,6\}$

Take any $a\in\{1,3,5,7\}$ and $b\in\{2,4,6\}$ ⁠. Then $a$ is odd and $b$ is even, so $p(a)\ne p(b)$ and $(a,b)\notin R$ ⁠. By symmetry (or the same argument) $(b,a)\notin R$ as well. That rules out $4\times 3 = 12$ pairs in each direction, 24 in all.

So $R$ contains exactly $16 + 9 = 25$ of the $7^2 = 49$ pairs in $A\times A$ ⁠, and the other $24$ are the mixed-parity pairs.

Left: the whole of $A\times A$ ⁠, with the 25 pairs of $R$ shaded. The checkerboard pattern appears because $(a,b)\in R$ exactly when $a+b$ is even. Right: the same information as two equivalence classes. Every number is related to every number in its own group and to nothing in the other group.

A pair with one odd and one even entry can never satisfy "same parity". This is part (iii) of the question. Together with part (ii) it says that $\{1,3,5,7\}$ and $\{2,4,6\}$ are exactly the equivalence classes of $R$ ⁠.

Equivalence classes of an equivalence relation are disjoint and their union is the whole set (Section 1.2, after Example 5). Here $\{1,3,5,7\}\cap\{2,4,6\} = \varnothing$ and $\{1,3,5,7\}\cup\{2,4,6\} = A$ ⁠. Basics: equivalence classes

Result

$R$ relates two numbers exactly when they have the same parity, so it is reflexive, symmetric and transitive: an equivalence relation. All elements of $\{1,3,5,7\}$ are related to each other (all odd), all elements of $\{2,4,6\}$ are related to each other (all even), and no odd element is related to an even one. These two subsets are the equivalence classes $[1] = \{1,3,5,7\}$ and $[2] = \{2,4,6\}$ ⁠.

Play this problem

Class Catcher, in the chapter’s Games tab. Level 1 is this example: sort 1 to 7 into the two baskets {1, 3, 5, 7} and {2, 4, 6}. Play Class Catcher ↗

Check it with numbers

Count the pairs: $16$ odd-odd plus $9$ even-even gives $25$ pairs in $R$ ⁠, and $49 - 25 = 24 = 2\times(4\times 3)$ mixed pairs outside $R$ ⁠. Transitivity sample: $(3,7)\in R$ and $(7,1)\in R$ ⁠, and indeed $(3,1)\in R$ (both odd). Cross check: $5 - 2 = 3$ is odd, so $(5,2)\notin R$ ⁠, matching "no odd element is related to an even one". The verification script checks reflexivity, symmetry and transitivity by brute force over all $25\times 25 = 625$ ways of choosing two pairs of $R$ ⁠.

Common mistakes

Misreading the rule. "Both $a$ and $b$ are either odd or even" does not mean " $a$ is odd or $b$ is even". It means both odd, or both even.
Forgetting pairs like $(3,3)$ and $(5,1)$ ⁠. "Related to each other" includes each element with itself and both orders.
Proving transitivity with one triple. $(1,3),(3,5)\Rightarrow(1,5)$ is an example, not a proof. Argue with arbitrary $a, b, c$ ⁠, as in Part (i) Step 4.
Calling $\{1,3,5,7\}$ and $\{2,4,6\}$ "relations". They are subsets of A (the equivalence classes); the relation is the set of 25 pairs.

What to take away

"Same label" relations (same parity, same remainder, same length) are always equivalence relations, by the properties of equality.
The equivalence classes are the groups of elements sharing a label. They never overlap and they fill the set.
This example is Example 5 ("2 divides $a-b$ ") on the finite set $\{1,\dots,7\}$ ⁠, where every claim can also be checked by listing pairs.

Every fact used, and where it comes from

Fact	Used in	Source
Every integer is exactly one of odd, even	Part (i) Step 1	Definition of odd and even (Basics: even and odd)
Equality is reflexive, symmetric, transitive	Part (i) Steps 2–4	Basic properties of equality
Reflexive, symmetric, transitive; equivalence relation	Part (i) Steps 2–5	Definitions 3 and 4, Section 1.2 (Lesson: types of relations)
Same parity $\iff$ $a-b$ even	Part (i) Step 5	Example 5
Equivalence classes are disjoint and cover the set	Part (ii) and (iii) Steps 1, 2	Section 1.2, after Example 5 (Lesson: equivalence relations)
Pair counts 16, 9, 25, 24	Part (ii) and (iii) Steps 1, 2; Check	Counted by brute force in the site's verification script

Found an error, or want more?

Tell us if something on this page is wrong or unclear, or if you would like a fuller explanation, another method or a new feature. Send feedback on this problem →

Example 6: Same parity on {1, …, 7}

Basics you need

Part (i): RRR is an equivalence relation

Rewrite the rule as an equation

Reflexive

Symmetric

Transitive

Conclude part (i)

Part (ii) and (iii): the two subsets

Within {1,3,5,7}\{1,3,5,7\}{1,3,5,7}⁠, and within {2,4,6}\{2,4,6\}{2,4,6}⁠, everything is related

No element of {1,3,5,7}\{1,3,5,7\}{1,3,5,7} is related to any element of {2,4,6}\{2,4,6\}{2,4,6}

Every fact used, and where it comes from

Part (i): $R$ is an equivalence relation

Within $\{1,3,5,7\}$ ⁠, and within $\{2,4,6\}$ ⁠, everything is related

No element of $\{1,3,5,7\}$ is related to any element of $\{2,4,6\}$