Equivalence Relations fixed on A with specific properties

135 Views Asked by At

Fix a natural number $n$ and let $A=\{1,2,...,n\}$

a. Is there an equivalence relation $~$ on $A$ with the property that if $k\mid l$, then $k\sim l$? If so, how many such relations?

b. Is there an equivalence relation $~$ on $A$ with the property that $k\mid l$ if and only if $k\sim l$? If so, how many such equivalence relations?

1

There are 1 best solutions below

0
On

Assume that $k\mid l \Rightarrow k\sim l$. We have $1\sim x$ for all $x \in A$. By symmetry and transitivity, we have $x\sim y$ for all $x,y\in A$, and $\sim$ is the trivial relation with one equivalence class.

For part (b), the divisibility relation is not symmetric (unless $n=1$) and cannot be an equivalence.