equivalence relation on $\mathbb{N}$ which has $7$ Equivalence Classes where $2$ are finite and $5$ other equivalence classes are infinite.

Question

Define an equivalence relation on $\mathbb{N}$ which has $7$ Equivalence Classes where $2$ are finite and $5$ other equivalence classes are infinite.

I tried some function i.e-Identity etc but not getting anything correct

Answer 1

From my point of view, there are two related key facts about equivalence relations which can help us address this problem.

First: Let $X$ be an arbitrary set and let $\sim$ be an equivalence relation on $X$; then the equivalence classes of $\sim$ are either disjoint or identical.

For, denoting the equivalence class of $x \in X$ by $[x]$:

$[x] = \{ u \in X \mid u \sim x \}, \tag 1$

if

$[x] \cap [y] \ne \emptyset, \tag 2$

there is some $z \in X$ with

$z \in [x] \cap [y] \Longrightarrow z \in [x], \; z \in [y]; \tag 3$

then

$z \sim x, \; z \sim y; \tag4$

and since $\sim$ is an equivalence relation, it is transitive, so

$x \sim y, \tag 5$

i.e.,

$x \in [y]; \tag 6$

now if

$x_1 \in [x] \tag 7$

we have

$x_1 \sim x \Longrightarrow x_1 \sim y \Longrightarrow x_1 \in [y], \tag 8$

where we have used the transitivity of $\sim$ to affirm that $x_1 \sim y$; thus

$[x] \subset [y]; \tag 9$

the same argument with the roles of $x$ and $y$ interchanged shows that

$[y] \subset [x], \tag{10}$

from which we conclude

$[x] = [y]. \tag{11}$

We thus see that equivalence classes of $\sim$ form a partition of the set $X$; that is, the subsets $[x] \subset X$ form a disjoint family whose union is $X$.

Second: For any set $X$ let $X_\alpha$ be a collection of pairwise disjoint, nonempty subsets of $X$, indexed by some set $I$, such that

$\displaystyle \bigcup_{\alpha \in I}X_\alpha = X; \tag{12}$

define a relation $\sim$ on the set $X$ by

$x \sim y \Longleftrightarrow \exists \; \alpha \in I, \; x, y \in X_\alpha; \tag{13}$

that is, $x \sim y$ precisely when $x$ and $y$ are in the same $X_\alpha$ for some $\alpha \in I$; then $\sim$ is an equivalence relation on $X$ whose equivalence classes are the $X_\alpha$, $\alpha \in I$.

For given $x \in X_\alpha \subset X$, we clearly have $x \sim x$ since, logically,

$(x \in X_\alpha) \equiv (x \in X_\alpha \wedge x \in X_\alpha); \tag{14}$

also,

$(x, y \in X_\alpha) \equiv (x \in X_\alpha \wedge y \in X_\alpha) \equiv (y \in X_\alpha \wedge x \in X_\alpha) \equiv (y, x \in X_\alpha), \tag{15}$

which shows that

$(x \sim y) \equiv (y \sim x); \tag{16}$

(14)-(16) show that $\sim$ is both reflexive and symmetric; to see that $\sim$ is transitive, note that

$(x \sim y) \equiv (\exists \; \alpha \in I, \; x, y \in X_\alpha), \tag{17}$

and

$(y \sim z) \equiv (\exists \; \beta \in I, \; y, z \in X_\beta); \tag{18}$

now since

$y \in X_\alpha \cap X_\beta, \tag{19}$

and the $X_\alpha$ are pairwise disjoint, we must have $\alpha = \beta$, that is,

$X_\alpha = X_\beta, \tag{20}$

whence

$z \in X_\alpha, \tag{21}$

and therefore

$x \sim z, \tag{22}$

establishing the transitivity of $\sim$, which is thus seen to be an equivalence relation on $X$; it is then evident from (13) that the $X_\alpha$ are the equivalence classes of $\sim$.

We may apply these two principles, First and Second, to aid our uderstanding of the problem at hand; while First presents a general view of the workings of equivalence relations, it is Second which we exploit directly here: set

$Y_1 = \{ 1 \}, \; Y_2 = \{ 2 \}, \tag{21}$

and, for $1 \le k \le 5$,

$X_k = \{y \in \Bbb N \setminus (Y_1 \cup Y_2) \mid y = (k + 2) \mod 5 \}; \tag{22}$

then it is easy to see that

$X_1 = \{3, 8, 13, 18, \ldots, \} = \{ 5(k - 1) + 3, k \in \Bbb N \}, \tag{23}$

$X_2 = \{4, 9, 14, 19, \ldots \} = \{ 5 (k - 1) + 4, k \in \Bbb N \}, \tag{24}$

and so forth, for $1 \le j \le 5$:

$X_j = \{j + 2, j + 7, j + 12, j + 17, \ldots \} = \{ 5(k - 1) + (j + 2), k \in \Bbb N \}; \tag{25}$

the sets $X_j = X_1, X_2, \ldots, X_5$ each contain the elements of $\Bbb N \setminus (Y_1 \cup Y_2)$ with remainder $j + 2$ when divided by $5$ (where by a slight abuse of notation we identify $5$ and $0$ as remainders); as such, they are pairwise disjoint; furthermore, since every $y \in \Bbb N \setminus (Y_1 \cup Y_2)$ is of the form

$y = 5(k - 1) + (j + 2), \; k \in \Bbb N, 1 \le j \le 5, \tag{26}$

we see that the $X_j$, $1 \le j \le 5$, cover $\Bbb N - (Y_1 \cup Y_2)$:

$\Bbb N - (Y_1 \cup Y_2) = \displaystyle \bigcup_1^5 X_j; \tag{27}$

it then follows that

$\Bbb N = Y_1 \bigcup Y_2 \displaystyle \bigcup_1^5 X_j, \tag{28}$

giving a partition of $\Bbb N$ into seven subsets, two of which, $Y_1$ and $Y_2$, are finite and five of which, $X_j$, $1 \le j \le 5$, are infinite. We the may define $\sim$ with as above with respect to these subsets, and so the desired relation may be had.

Answer 2

Hint:

Find a partition $\{A_1,A_2,B_1,B_2,B_3,B_4,B_5\}$ of $\mathbb N$ such that $A_1,A_2$ are finite and $B_1,B_2,B_3,B_4,B_5$ are infinite.

Now define relation $\sim$ on $\mathbb N$ by stating that $n\sim m$ iff $n,m$ belong to the same element of the partition and you are done.