0
$\begingroup$

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\}$

$\endgroup$
  • $\begingroup$ There are two (equivant) was to think of relations. The intuitive way is two different numbers are related if ... they share so characteristic. Ex, 6 and 15 are related because gcd (6,15)=3 >1. Like wise 12 and 16 are related but 12 is not related to 7. More formally, a relation is a collection of pairs that are a subset of all possible pairs. So (6,15) and (12,16) are pairs in the relation but (12,7) isn't. Yes, you consider all integer pairs. But you don't "search" them. You show that whether gcd(a,a) is always > 1 for all a, whether gcd(a,b) > 1 always means gcd (b,a)> 1, etc. $\endgroup$ – fleablood Nov 21 '16 at 3:57
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Thanks! it's a lot clearer now. $\endgroup$ – SK23 Nov 21 '16 at 7:18
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Cheers Dieter. Appreciate the help. I have a better grasp of it now. $\endgroup$ – SK23 Nov 21 '16 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.