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?

  • $\begingroup$ I don't really think it matters that much.. $\endgroup$ – Yariv Levy Dec 2 '17 at 10:49
  • 1
    $\begingroup$ Mathematics is case sensitive. The variables $x,X,\mathcal X,\mathscr X$ and even $\mathbb X$ are all entirely different variables. $\endgroup$ – Asaf Karagila Dec 2 '17 at 10:52
  • $\begingroup$ 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... $\endgroup$ – 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$$


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.