Equivalence relations and cardinalities

68 Views Asked by At

Let $ X $ be a set and $ R $ an equivalence relation on $P(X)$ s.t for each $ A $, $ B $ subsets of $ X $ it satisfies that $ A ~R~ B \iff (A \setminus B) \cup (B \setminus A) $ is finite.

I was asked to specify a set $X$ for which the relation $R$ on $P(X)$ has countably equivalence classes s.t each of those is countable.

I struggle to follow the right intuition and if someone could shed some light (rather than an explicit example) I will be happy, thanks

Edit: I naively let $X = \mathbb{N}$ and tried to identify some attributes regarding $R$ which I failed

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose that $ X$ is infinite and let $j \colon \mathbb{N} \rightarrow X$ be an injection.

Let $ {R'}$ be the equivalence relation in $ P \left(\mathbb{N}\right)$ defined by

\begin{equation}A \ {R'} \ B \qquad \Longleftrightarrow \qquad j \left(A\right) \ R \ j \left(B\right)\end{equation}

As $j \left(A {\Delta} B\right) = j \left(A\right) \ {\Delta} \ j \left(B\right)$, we have that

$A \ {R'} \ B$ if and only if $A {\Delta} B$ is finite, where $ {\Delta}$ is the symmetric difference. Hence the equivalence class of $ A$ for the relation $ {R'}$ is

\begin{equation}\text{Cl} \left(A\right) = \bigcup_{n \geqslant 0} \left\{B \in P \left(\mathbb{N}\right) , A \cap \left[n , \infty \right[ = B \cap \left[n , \infty \right[\right\}\end{equation}

hence $\text{Cl} \left(A\right)$ is a countable union of finite sets, hence it is countable.

Since $ P \left(\mathbb{N}\right)$ is the union of all equivalence classes which are all countable, it follows that there are uncountably many equivalence classes for $R'$, hence uncountably many equivalence classes for $R$.