# Relations, Equivalence class

Define the relation $R$ on the set $\Bbb Z^+$ of all positive integers by: for all $a, b \in \Bbb Z^+$, $aRb$ if and only if the largest digit of a is equal to the largest digit of $b$. For example, $\,271\,R\, 770\,$ because the largest digit of $271$ is 7 which is also the largest digit of $770$.

1. Prove that $R$ is an equivalence relation on $Z^+$.
2. Find the number of equivalence classes of $R$. Explain.
3. Find and simplify the number of positive integers between $100$ and $1000$ which are in the equivalence class $[271]$. Explain.

1. A relation $R$ is on a set $Z^+$ is equivalence if and only if, $R$ is reflexive, and $R$ is symmetric and $R$ is transitive.

Here, $R$ is reflexive because, for all $a \in \Bbb Z\ aRa$.
$R$ is symmetric as well. For all $a, b \in \Bbb Z$, if $aRb$ then $bRa$.
$R$ is transitive as well, because, for all $a, b, c \in \Bbb Z$, if $aRb$ and $bRc$, then $aRc$.
Therefore, $R$ is equivalence.

2. Number of equivalence classes of $R$, $\ [R]$ = $\left\{\,x \mid x \in\; \equiv \,\right\}$ so we have 9 equivalence classes.

• Maybe start by making a list of the equivalence classes.... for example, one equivalence class is the set of numbers that begin with the digit $1$. – angryavian Aug 17 '15 at 7:11
• @angryavian not start with 1, but have 1 as the largest digit. – user137794 Aug 17 '15 at 7:12
• @user137794 Oops, you're right thank you. – angryavian Aug 17 '15 at 7:18
• Note that you did not really prove anything in 1. you simply stated that $R$ has a property because it satisfies the definition of the property, but you have to argue why this is the case (of course, this is easy here, but you should still do it). – Matthias Klupsch Aug 17 '15 at 7:20
• Thanks - so, since this is on the set of all positive integers, there is unlimited number of equivalence classes? which makes no sense, so I don't know. – 2D3D4D Aug 17 '15 at 7:32

Hint:

If you investigate the questions like: "is $R$ and equivalence relation on set $A$?" then often (even stronger: almost always) it is very handsome to look for a function that has $A$ as domain and satisfies $$aRb\iff f(a)=f(b)\tag1$$

If you have found such a function then you are allowed to conclude:

• $R$ is an equivalence relation on $A$.
• The equivalence classes are the fibres of the function $f$, so take the form $[a]:=\{b\in A\mid f(a)=f(b)\}$

It is clear also that the number of equivalence classes is the cardinality of the range of function $f$.

You can do it with the function $f:\mathbb Z^+\rightarrow\{1,2,\cdots,9\}$ prescribed by: $$n\mapsto\text{largest digit of } n$$

Why is it so that you can conclude immediately that $R$ is an equivalence relation? Well:

• $f(a)=f(a)$ for each $a\in A$ (reflexive)
• $f(a)=f(b)\implies f(b)=f(a)$ for each $a,b\in A$ (symmetric)
• $f(a)=f(b)\wedge f(b)=f(c)\implies f(a)=f(c)$ for each $a,b,c\in A$ (transitive)

It is clear as crystal that these things are true for any function $f$ and $(1)$ makes it legal to replace expressions like $f(a)=f(b)$ by $aRb$.

Well, the equivalence class of $n$ (say the largest digit of $n$ is $k$) would be the positive integers whose largest digit is $k$. Now $k$ can be any number from 1 to 9 (you must omit 0 because a positive integer must have a positive digit). So for Question 3, you just need to find the number of integers between 100 and 1000 whose largest digit is 7.