# Quotient set and cardinality

Let $R_A= \{\langle x, y\rangle\mid y-x\in A\}$ for $A\subseteq \mathbb{Z}$

Given $A$ is a finite set and $R_A$ is an equivalence relation, what $A$ consists of?

For $k\in\mathbb{N}_+$ what is $A$ such that $R_A$ is an equivalence relation and, for it, $|\mathbb{Z}/R_A|=k$?

My thoughts are that for $A$ a finite set, $A=\{0\}$, because given $R_A$ equivalence, $\langle x,x\rangle\in R_A$, which means $A$ has to have $0$. I also understand that if $z\in \mathbb{Z}$, $z\in A$, $A$ is not a finite set because for $k\in\mathbb{Z}$, $\langle kz, 0\rangle \in R_A$.
Are my thought right? How do I describe them mathemathically?

My thoughts are that if $|\mathbb{Z}/R_A|=k$, then $A$ contains the $k$ first prime numbers. I understand that for each $z\in A$ $kz\in A$, but how do I describe the quotient set and equivalence classes? For example, let’s say that $5k\in A$, does this mean that all $5k$ is one quotient set, or each $5k$ is a quotient set of itself?

• I don't really think it matters that much.. – Yariv Levy Dec 2 '17 at 10:49
• Mathematics is case sensitive. The variables $x,X,\mathcal X,\mathscr X$ and even $\mathbb X$ are all entirely different variables. – Asaf Karagila Dec 2 '17 at 10:52
• can you show that if $a\in A$ then $a\mathbb Z\subset A$ ? what if $A$ contains $a$ and $b$, think about $\gcd(a,b)$. so $\mathbb Z/k\mathbb Z$ is not very far... – zwim Dec 2 '17 at 11:44

If $R_A$ is an equivalence relation on $\mathbb Z$ then it is reflexive so that e.g. $\langle 5,5\rangle\in R_A$.

That leads to $0=5-5\in A$.

If $R_A$ is an equivalence relation on $\mathbb Z$ then it is transitive.

Now if $n\in A$ and $n\neq0$ then $\langle k,k+n\rangle\in R_A$ for every $k\in\mathbb Z$. Then with transitivity we find that $\langle k,k+2n\rangle\in R_A$ which means that $2n\in A$. This can be repeated so shows that in situation $A$ is not finite. From this we conclude that $A=\{0\}$ is the only option under the condition that $A$ is finite.

Let it be that $R_A\subseteq\mathbb Z^2$ is an equivalence relation on $\mathbb Z$, and that the cardinality of $\mathbb Z/R_A$ is $k$ where $k$ is a positive integer.

If $A$ is finite then (as shown allready) $A=\{0\}$ so if $[n]$ is an equivalence class then $k\in[n]\iff n-k=0\iff n=k$ telling us that $[n]=\{n\}$. In that case the cardinality of $\mathbb Z/R_A$ is not a positive integer so we can exclude that $A=\{0\}$.

Let $[0]$ denote the equivalence class represented by $0$. Then by definition: $$n\in[0]\iff \langle 0,n\rangle\in R_A\iff n=n-0\in A$$ telling us that $[0]=A$.

Also by symmetry we have:$$n\in A\iff\langle0,n\rangle\in R_A\iff\langle n,0\rangle\in R_A\iff -n\in A$$

Now let $m$ be the smallest positive integer with $m\in[0]$.

Then the transitivity of $R_A$ allows us to prove by induction that $nm\in A$ for all $n\in\mathbb N_+$ and combining this with the former results we conclude that $m\mathbb Z:=\{mn\mid n\in\mathbb Z\}\subseteq A$.

If $r\in A$ then $r-m\lfloor\frac{r}{m}\rfloor\in A$ so it cannot happen that $r$ is not a multiple of $m$ (it would contradict the minimality of $m$).

Proved is now that $A=m\mathbb Z$.

If $r\in\mathbb Z$ with $0<r<m$ then $s\in[r]\iff s-r\in A=m\mathbb Z$ showing that $[r]=r+m\mathbb Z$.

Then in $[0],[1],\dots,[m-1]$ we have $m$ distinct equivalence classes that cover $\mathbb Z$ so $m=k$.

Our final conclusion is: $$A=k\mathbb Z$$