0

Prove that the following relation is an equivalence relation and determine how many equivalence classes R partitions the set $Z^{+}$ into.

R = {$(a,b) | a∈Z^{+} ∧ b∈Z^{+} ∧ 10 | (a^{2}- b^{2})$}

Any help would be great. I would love an explanation, in layman's terms, of what I'm looking at. Thanks!

Terabyte
  • 101
  • 1
  • 1
  • 7
  • $aRb$ iff either of $a+b$ or $a-b$ is a multiple of $10$. –  Apr 12 '13 at 05:33
  • Hmm, ok. That makes sense. So how do I go about proving it? Do I have to show that it's reflexive, symmetric and transitive? – Terabyte Apr 12 '13 at 05:46
  • Yes - this should be quite straightforward hopefully. – Luke Mathieson Apr 12 '13 at 06:59
  • Yes, that would be the approach. –  Apr 12 '13 at 07:19
  • I understand how to do the proof now but I'm still a bit lost on how to determine the number equivalence classes R partitions the set Z+ into. Advice? – Terabyte Apr 12 '13 at 12:30
  • Start with $a=1$. Test $b=1,2,3,\dots$ to see which ones are in the equivalence class of $a$. When you see a pattern, stop computing, and prove the pattern works. Then take the smallest integer not in the class of $1$, and repeat the experiment. Eventually, you will get the idea and you will know how many equivalence classes there are. – Gerry Myerson Apr 12 '13 at 13:39
  • @Shahab While is true that $\rm:10\mid a^2!-b^2:\Rightarrow:10\mid a-b:$ or $\rm:10\mid a+b,:$ this requires proof; it is not true generally, e.g. $\rm:15\mid 4^2!-1^2:$ but $\rm:15\nmid 4!-!1,4!+!1.:$ It is true if the divisor is a prime $\rm:p:$ or $\rm:2p.\ $ – Math Gems Apr 12 '13 at 15:19

1 Answers1

0

First, we recall that equivalence relations are transitive, symmetric, and reflexive, i.e.

  • Reflexive: $(a,a) \in R$ for all $a$ in the set of concern (here, $\Bbb Z^+$)
  • Symmetry: $(a,b) \in R$ always implies $(b,a) \in R$
  • Transitivity: If $(a,b),(b,c) \in R$, then $(a,c) \in R$)

Consider proving each for this relation $R$ on $\Bbb Z^+$. Recall that $(a,b) \in R$ if $10\mid(a^2 - b^2)$.

  • Reflexive: Is $(a,a) \in R$? That is, does $10 \mid a^2 - a^2$? It does, because $10 \mid 0$.
  • Symmetry: Let $(a,b) \in R$; that is, let $10 \mid a^2 - b^2$. This means that there exists an integer $k$ such that $a^2 - b^2 = 10k$. But then, multiplying by $-1$ on each side, we see that $b^2 - a^2 = -10k = 10(-k)$. $k \in \Bbb Z \implies -k \in \Bbb Z$, and thus this means that $(b,a) \in R$ as well.
  • Transitivity: Let $(a,b),(b,c) \in R$. Thus, there exists integers $p,q$ such that $a^2 - b^2 = 10p$ and $b^2 - c^2 = 10q$. If we add these two equations together, we get that $a^2 - b^2 + b^2 - c^2 = 10p + 10q$; equivalently, $a^2 - c^2 = 10(p+q)$. Since $p,q \in \Bbb Z$, $p+q \in \Bbb Z$ too, and thus $(a,c) \in R$.

Thus, all three conditions are met: $R$ is an equivalence.

As for the equivalence classes, recall: the equivalence class $[a]$ of $a$ can be defined by

$$[a] = \{ b \mid aRb \}$$

or, in other words, the equivalence class contains all of the elements that are related to each other. So perhaps it's a good start to work with some examples. To which element might some integers be related? We'll need to fix $a$, and then find $b$ such that $b^2 = a^2 - 10k$ with integer $k$. Or rather, fix $a$, then subtract some $b^2$, and see if it's a multiple of ten (i.e. ends in a zero).

(You can have WolframAlpha output these easily. For example, here is $a=1$.)

Let $a=1$. Then we can have $b=1,11,19,21,29,31,39,41,49$ for $b \in [1,50]$. That's interesting on its own; it suggest $[1] = \{ k \in \Bbb Z^+ \mid k = 10m \pm 1, m \in \Bbb Z^+ \cup 0 \}$. That is, $[1]$ consists of everything one above or below a multiple of ten! (Or, equivalently, one or nine above a multiple of ten.)

Now let $a=2$ (Wolfram). Then $b=2,8,12,18,22,28,32,38,42,48$. Again, another pattern: anything that's two or eight above a multiple of of ten!

Now let $a=3$ (Wolfram), $a=4$ (Wolfram), and $a=5$ (Wolfram), and the pattern continues. In essence,

$$[k] = \{ p \in \Bbb Z^+ \mid p = 10q \pm k, q \in \Bbb Z^+ \}$$

i.e. $[k]$ consists of everything $k$ above or below a multiple of ten. (Equivalently, $k$ above or $10-k$ below.) We also see that by the time we hit $k=5$, we exhaust all of the integers.

Of course, this fact - that everything positive integer falls into one of $[1],\cdots,[5]$ - needs to be proven, but it's not difficult to see as each $[k]$ consists of the positive integers modulo $k$ and $10-k$ in union, and the positive integers modulo $10$ also partition the positive integers. You could also prove this more directly: each positive integer will have the form $10p+q$ for $p$ an integer and $q \in \{0,\cdots,9\}$, so just prove all of the integers which correspond to a given $q$ fall into the corresponding equivalence class.

This of course in turn means you have $5$ equivalence classes.

...though you did post this years ago so I imagine you don't really need this confirmation and help now, but if nothing else this might help others in the future and also gets this off the unanswered list.

PrincessEev
  • 43,815