Equivalence relations..

Question

I'm just starting out with equivalence relations so please go easy on me! I can't quite understand how to even begin thinking about this question.

I understand I have to prove whether it is an equivalence relation or not. Therefore, I must show whether each of (a)..(d) are reflexive, symmetric, and transitive. But what is the function? For example, for (a), I have $Q = \{(a, b) : gcd(a, b) > 1\}$. So do I search for all integer pairs that have $gcd(a,b) > 1$?

Prove or disprove that it is an equivalence relation. For the equivalence relation(s), describe [26], either by writing out all its terms, or by noticing that it is a familiar set.

(a) $Q ⊆ \mathbb{Z} × \mathbb{Z}, Q = \{(a, b) : gcd(a, b) > 1\}$

(b) $R ⊆ \mathbb{Z} × \mathbb{Z}, R = \{(a, b) : |a − b| < 2\}$

(c) $S ⊆ \mathbb{Z} × \mathbb{Z}, S = \{(a, b) : a^2 = b^2\}$

(d) $T ⊆ \mathbb{Z} × \mathbb{Z}, T = \{(a, b) : a^2 ≡ b^2 mod 4\}$

Answer 1

Recall that an equivalence relation on a set $S$ may be expressed as a subset of $S\times S$, with the rules of reflexivity, symmetry and transitivity. Your examples are all subsets of $\mathbb{Z}\times\mathbb{Z}$, so which of these sets satisfy: $$ (a,a) \in S \quad\forall a \in \mathbb{Z} $$ $$ (a,b) \in S \implies (b,a) \in S $$ $$ (a,b) \in S, \quad (b,c) \in S \implies (a,c) \in S $$ I'll do the first one to get you going: $$ Q= \{ (a,b) : gcd(a,b)>1 \} $$ The question isn't very well stated. Let's assume that gcd's are always positive, e.g $gcd(-4,-2) = 2$.

Reflexivity: $gcd(a,a) = a$. So this is OK for any $|a|>1$, but $(-1,-1), (0,0), (1,1)$ are all missing from $Q$, so not an equivalence relation. It may be if we exclude these points, so let's continue.

Symmetry: $gcd(a,b) = gcd(b,a)$ so this is OK

Transitivity: No, this isn't going to work. Counterexample is $$ gcd(2,6) = 2,\quad gcd(6,3) = 3,\quad gcd(2,3) = 1 $$ Now do the same for the other examples!

Answer 2

As you said, an equivalence relation in a set $A$ is a subset $R \subset A \times A$ that satisfies: for any $a,b,c \in A$:

$(a,a) \in R$ (reflexivity), $(a,b) \in R \Leftrightarrow (b,a) \in R$ (symmetry) and $(a,b) \in R, (b,c) \in R \Rightarrow (a,c) \in R$ (transitivity).

Now you have to check this three conditions for your subsets. For example, in $(a)$, the subset of $\mathbb{Z} \times \mathbb{Z} $ is $$Q=\{(a,b): gcd(a,b)>1\}$$ This fails in the reflexivity, since $gcd(1,1)=1$ that's not strictly greater than $1$, so $(1,1) \notin Q$.

Now let's look at the item $(b)$: $$R=\{(a,b) \in \mathbb{Z} \times \mathbb{Z} : |a-b|<2\}$$ Now the reflexivity holds, since $|a-a|=0<2$ or in other words $(a,a) \in R, \ \ \forall a \in \mathbb{Z}$. Since $|a-b|=|b-a|$ the simetry condition also holds, but the transitivity condition fails, look for example at $(2,1) \in R $ and $(1,0) \in R$ if the transitivity holds we must have $(2,0) \in R$ but $|2-0|=2 \not<2$ so $(2,0) \notin R$.

Now let's look at item $(c)$: $$S=\{(a,b)\in \mathbb{Z} \times \mathbb{Z} :a^2=b^2\}$$ and this one is an equivalence relation, it's reflexive: $(a,a) \in S$ since $a^2=a^2$ for every integer. The relation is symmetric: if $a^2=b^2$ then $b^2=a^2$. Finally, it's transitive: if $(a,b) \in S$ and $(b,c) \in S$ then $a^2=b^2$ and $b^2=c^2$ so $a^2=c^2 \Rightarrow (a,c) \in S$.

The next item can be done analogously.