Proving $A \sim B \iff (\exists k\in \mathbb{N}^+)(\forall n \in \mathbb{N}^+)nk\in A \iff nk\in B$ is equivalence relation.

Question

In an exercise I'm asked to prove that (not whether, the prompt assumes it is true) $$For \ A,B \subseteq \mathbb{N}\ \ A \sim B \iff (\exists k\in \mathbb{N}^+)(\forall n \in \mathbb{N}^+)nk\in A \iff nk\in B$$ is an equivalence relation. I have no problem proving reflexivity and symmetricity but my issue is the transitive property.

Isn't it true that: $\{2,4,8\} \sim \{2,3,4,8,9\} \land \{2,3,4,8,9\} \sim \{ 3,9\} $ but $\{2,4,8\} \nsim \{ 3,9\}$? This would suggest this isn't an equivalence relation since it fails transitivity.

What am I misunderstanding?

Answer 1

We must check that it is reflexive, symmetric, and transitive.

Reflexivity follows immediately since $nk \in A \iff nk \in A$.

Symmetry follows since $nk \in A \iff nk \in B$ is equivalent to $nk \in B \iff nk \in A$.

For transitivity, say $A \sim B$ and $B \sim C$. Then there exists $k_1 \in \mathbb{N}^+$ s.t. $\forall n \in \mathbb{N}^+$, $nk_1 \in A \iff nk_1 \in B$. Similarly $\exists k_2 \in \mathbb{N}^+$ s.t. $\forall n \in \mathbb{N}^+$, $nk_2 \in B \iff nk_2 \in C$.

Now consider $k_1k_2 \in \mathbb{N}^+$ and any $n \in \mathbb{N}^+$. $nk_1k_2=(nk_2)k_1 \in A \iff (nk_2)k_1=nk_1k_2 \in B$ since $A \sim B$. But also $nk_1k_2=(nk_1)k_2 \in B \iff (nk_1)k_2=nk_1k_2 \in C$ since $B \sim C$. Thus $\forall n \in \mathbb{N}^+$, $nk_1k_2 \in A \iff nk_1k_2 \in C$, and we are done.

Answer 2

As @SeanEberhard commented:

• any two finite sets are $∼$, since
• $A \sim B \iff (\exists k\in \mathbb{N}^+)(A \cap k \mathbb N^+= B \cap k \mathbb N^+).$

Let us now concentrate on transitivity, since (not surprisingly) you `have no problem proving reflexivity and symmetr[icit]y'.

My (now deleted) comment was:

note that if $A∩k\Bbb N^+=B∩k\Bbb N^+$ then $A∩k′\Bbb N^+=B∩k′\Bbb N^+$ for every multiple $k′$ of $k$.

Indeed, since $k'\Bbb N^+\subset k\Bbb N^+$: $A∩k'\Bbb N^+=A∩(k\Bbb N^+∩k'\Bbb N^+)=(A∩k\Bbb N^+)∩k'\Bbb N^+$, and similarly for $B$.

In your (now deleted) reply, you understood correctly how it led to the solution:

if $A∼B$ with $ k = k_1$ and $B∼C$ with $k = k_2$ then $A∼C$ for $k= k_1k_2$.

(instead of $k_1k_2$, you can even use any common multiple of $k_1$ and $k_2$, for instance the least one).

That's all.