Question

Let R be the relation on ℤ+×ℤ+ defined by (a,b)R(c,d) if and only if a−2d=c−2b.

(a) prove that R is an equivalence relation
(b) list all elements of the equivalence class [(3,3)]

(c) find an equivalence class that has exactly 271 elements.

(d) is it true that for every positive integer n, there is an equivalence class that contains exactly n elements? explain

Answer 1

(a)
An equivalence relation must satisfy the following three requirements:
1. reflexivity
(a,b)R(c,d) is reflexive if
(a,b)R(a,b)is defined.
Since a-2d=c-2b ≡ a+2b=c+2d
so (a,b)R(a,b) is defined since a+2b=a+2b
Therefore R is reflexive.
2. symmetry
R is symmetric if
(a,b)R(c,d) <=> (c,d)R(a,b)
Since by definition,
a-2d=c-2b <=> c-2b=a-2d
R is symmetric
3. Transistivity
R is transitive if
(a,b)R(c,d) and (c,d)R(e,f) <=>(a,b)R(e,f)
We know that
a-2d=c-2b, and
c-2f=e-2d
Add preceding equations,
a-2d+c-2f=c-2b+e-2d
Simplify
a-2f=e=2b
<=>
(a,b)R(e,f)
Therefore R is transitive.

Since R satisfies all three requirements, R is an equivalence relation.

(b)
Elements of the equivalence class [(3,3)] consists of all elements (c,d) that satisfy (3,3)R(c,d), from which we can name the following set:
{(1,4),(3,3),(5,2),(7,1)}

(c) hints:
show that the number of elements of an equivalent class (a,b) has exactly
floor((a+2b-1)/2) elements. Floor(x) function return the greatest integer not exceeding x. Use mathematical induction if necessary.
Hence find the equivalent class that has 271 elements.

(d) hints:
Deduce from (c).