Mixing
equivalence relation on $mathbbN$ which has $7$ Equivalence Classes where $2$ are finite and $5$ other equivalence classes are infinite.
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Define an equivalence relation on $mathbbN$ 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
functions equivalence-relations
asked 7 hours ago
user581912
111
add a comment |Â
up vote
2
down vote
favorite
Define an equivalence relation on $mathbbN$ 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
functions equivalence-relations
asked 7 hours ago
user581912
111
1
Hint. You need not do this with a cleanly defined function. Can you find a decomposition into $5$ infinite classes and then jiggle a few elements arbitrarily?
– Ethan Bolker
6 hours ago
do a partition of $Bbb N$ into 7 pieces
– janmarqz
6 hours ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Define an equivalence relation on $mathbbN$ 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
functions equivalence-relations
asked 7 hours ago
user581912
111
Define an equivalence relation on $mathbbN$ 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
functions equivalence-relations
asked 7 hours ago
user581912
111
asked 7 hours ago
user581912
111
asked 7 hours ago
user581912
111
asked 7 hours ago
user581912
111
111
1
Hint. You need not do this with a cleanly defined function. Can you find a decomposition into $5$ infinite classes and then jiggle a few elements arbitrarily?
– Ethan Bolker
6 hours ago
do a partition of $Bbb N$ into 7 pieces
– janmarqz
6 hours ago
add a comment |Â
1
Hint. You need not do this with a cleanly defined function. Can you find a decomposition into $5$ infinite classes and then jiggle a few elements arbitrarily?
– Ethan Bolker
6 hours ago
do a partition of $Bbb N$ into 7 pieces
– janmarqz
6 hours ago
1
1
Hint. You need not do this with a cleanly defined function. Can you find a decomposition into $5$ infinite classes and then jiggle a few elements arbitrarily?
– Ethan Bolker
6 hours ago
Hint. You need not do this with a cleanly defined function. Can you find a decomposition into $5$ infinite classes and then jiggle a few elements arbitrarily?
– Ethan Bolker
6 hours ago
do a partition of $Bbb N$ into 7 pieces
– janmarqz
6 hours ago
do a partition of $Bbb N$ into 7 pieces
– janmarqz
6 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
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 $nsim m$ iff $n,m$ belong to the same element of the partition and you are done.
answered 6 hours ago
drhab
85.8k540118
add a comment |Â
up vote
0
down vote
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 z, ; 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], tag10$
from which we conclude
$[x] = [y]. tag11$
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 mutually disjoint, nonempty subsets of $X$, indexed by some set $I$, such that
$displaystyle bigcup_alpha in IX_alpha = X; tag12$
define a relation $sim$ on the set $X$ by
$x sim y Longleftrightarrow exists ; alpha in I, ; x, y in X_alpha; tag13$
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); tag14$
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), tag15$
which shows that
$(x sim y) equiv (y sim x); tag16$
(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), tag17$
and
$(y sim z) equiv (exists ; beta in I, ; y, z in X_beta); tag18$
now since
$y in X_alpha cap X_beta, tag19$
and the $X_alpha$ are mutually disjoint, we must have $alpha = beta$, that is,
$X_alpha = X_beta, tag20$
whence
$z in X_alpha, tag21$
and therefore
$x sim z, tag22$
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 , tag21$
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 ; tag22$
then it is easy to see that
$X_1 = 3, 8, 13, 18, ldots, = 5(k - 1) + 3, k in Bbb N , tag23$
$X_2 = 4, 9, 14, 19, ldots = 5 (k - 1) + 4, k in Bbb N , tag24$
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 ; tag25$
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$; as such, they are mutually 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, tag26$
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; tag27$
it then follows that
$Bbb N = Y_1 bigcup Y_2 displaystyle bigcup_1^5 X_j, tag28$
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.
answered 1 hour ago
Robert Lewis
36.7k22155
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
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 $nsim m$ iff $n,m$ belong to the same element of the partition and you are done.
answered 6 hours ago
drhab
85.8k540118
add a comment |Â
up vote
1
down vote
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 $nsim m$ iff $n,m$ belong to the same element of the partition and you are done.
answered 6 hours ago
drhab
85.8k540118
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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 $nsim m$ iff $n,m$ belong to the same element of the partition and you are done.
answered 6 hours ago
drhab
85.8k540118
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 $nsim m$ iff $n,m$ belong to the same element of the partition and you are done.
answered 6 hours ago
drhab
85.8k540118
edited 4 hours ago
answered 6 hours ago
drhab
85.8k540118
answered 6 hours ago
drhab
85.8k540118
answered 6 hours ago
drhab
85.8k540118
85.8k540118
add a comment |Â
add a comment |Â
up vote
0
down vote
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 z, ; 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], tag10$
from which we conclude
$[x] = [y]. tag11$
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 mutually disjoint, nonempty subsets of $X$, indexed by some set $I$, such that
$displaystyle bigcup_alpha in IX_alpha = X; tag12$
define a relation $sim$ on the set $X$ by
$x sim y Longleftrightarrow exists ; alpha in I, ; x, y in X_alpha; tag13$
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); tag14$
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), tag15$
which shows that
$(x sim y) equiv (y sim x); tag16$
(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), tag17$
and
$(y sim z) equiv (exists ; beta in I, ; y, z in X_beta); tag18$
now since
$y in X_alpha cap X_beta, tag19$
and the $X_alpha$ are mutually disjoint, we must have $alpha = beta$, that is,
$X_alpha = X_beta, tag20$
whence
$z in X_alpha, tag21$
and therefore
$x sim z, tag22$
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 , tag21$
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 ; tag22$
then it is easy to see that
$X_1 = 3, 8, 13, 18, ldots, = 5(k - 1) + 3, k in Bbb N , tag23$
$X_2 = 4, 9, 14, 19, ldots = 5 (k - 1) + 4, k in Bbb N , tag24$
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 ; tag25$
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$; as such, they are mutually 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, tag26$
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; tag27$
it then follows that
$Bbb N = Y_1 bigcup Y_2 displaystyle bigcup_1^5 X_j, tag28$
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.
answered 1 hour ago
Robert Lewis
36.7k22155
add a comment |Â
up vote
0
down vote
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 z, ; 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], tag10$
from which we conclude
$[x] = [y]. tag11$
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 mutually disjoint, nonempty subsets of $X$, indexed by some set $I$, such that
$displaystyle bigcup_alpha in IX_alpha = X; tag12$
define a relation $sim$ on the set $X$ by
$x sim y Longleftrightarrow exists ; alpha in I, ; x, y in X_alpha; tag13$
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); tag14$
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), tag15$
which shows that
$(x sim y) equiv (y sim x); tag16$
(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), tag17$
and
$(y sim z) equiv (exists ; beta in I, ; y, z in X_beta); tag18$
now since
$y in X_alpha cap X_beta, tag19$
and the $X_alpha$ are mutually disjoint, we must have $alpha = beta$, that is,
$X_alpha = X_beta, tag20$
whence
$z in X_alpha, tag21$
and therefore
$x sim z, tag22$
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 , tag21$
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 ; tag22$
then it is easy to see that
$X_1 = 3, 8, 13, 18, ldots, = 5(k - 1) + 3, k in Bbb N , tag23$
$X_2 = 4, 9, 14, 19, ldots = 5 (k - 1) + 4, k in Bbb N , tag24$
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 ; tag25$
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$; as such, they are mutually 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, tag26$
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; tag27$
it then follows that
$Bbb N = Y_1 bigcup Y_2 displaystyle bigcup_1^5 X_j, tag28$
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.
answered 1 hour ago
Robert Lewis
36.7k22155
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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 z, ; 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], tag10$
from which we conclude
$[x] = [y]. tag11$
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 mutually disjoint, nonempty subsets of $X$, indexed by some set $I$, such that
$displaystyle bigcup_alpha in IX_alpha = X; tag12$
define a relation $sim$ on the set $X$ by
$x sim y Longleftrightarrow exists ; alpha in I, ; x, y in X_alpha; tag13$
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); tag14$
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), tag15$
which shows that
$(x sim y) equiv (y sim x); tag16$
(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), tag17$
and
$(y sim z) equiv (exists ; beta in I, ; y, z in X_beta); tag18$
now since
$y in X_alpha cap X_beta, tag19$
and the $X_alpha$ are mutually disjoint, we must have $alpha = beta$, that is,
$X_alpha = X_beta, tag20$
whence
$z in X_alpha, tag21$
and therefore
$x sim z, tag22$
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 , tag21$
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 ; tag22$
then it is easy to see that
$X_1 = 3, 8, 13, 18, ldots, = 5(k - 1) + 3, k in Bbb N , tag23$
$X_2 = 4, 9, 14, 19, ldots = 5 (k - 1) + 4, k in Bbb N , tag24$
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 ; tag25$
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$; as such, they are mutually 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, tag26$
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; tag27$
it then follows that
$Bbb N = Y_1 bigcup Y_2 displaystyle bigcup_1^5 X_j, tag28$
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.
answered 1 hour ago
Robert Lewis
36.7k22155
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 z, ; 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], tag10$
from which we conclude
$[x] = [y]. tag11$
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 mutually disjoint, nonempty subsets of $X$, indexed by some set $I$, such that
$displaystyle bigcup_alpha in IX_alpha = X; tag12$
define a relation $sim$ on the set $X$ by
$x sim y Longleftrightarrow exists ; alpha in I, ; x, y in X_alpha; tag13$
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); tag14$
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), tag15$
which shows that
$(x sim y) equiv (y sim x); tag16$
(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), tag17$
and
$(y sim z) equiv (exists ; beta in I, ; y, z in X_beta); tag18$
now since
$y in X_alpha cap X_beta, tag19$
and the $X_alpha$ are mutually disjoint, we must have $alpha = beta$, that is,
$X_alpha = X_beta, tag20$
whence
$z in X_alpha, tag21$
and therefore
$x sim z, tag22$
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 , tag21$
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 ; tag22$
then it is easy to see that
$X_1 = 3, 8, 13, 18, ldots, = 5(k - 1) + 3, k in Bbb N , tag23$
$X_2 = 4, 9, 14, 19, ldots = 5 (k - 1) + 4, k in Bbb N , tag24$
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 ; tag25$
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$; as such, they are mutually 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, tag26$
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; tag27$
it then follows that
$Bbb N = Y_1 bigcup Y_2 displaystyle bigcup_1^5 X_j, tag28$
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.
answered 1 hour ago
Robert Lewis
36.7k22155
edited 1 hour ago
answered 1 hour ago
Robert Lewis
36.7k22155
answered 1 hour ago
Robert Lewis
36.7k22155
answered 1 hour ago
Robert Lewis
36.7k22155
36.7k22155
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873188%2fequivalence-relation-on-mathbbn-which-has-7-equivalence-classes-where-2%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Hint. You need not do this with a cleanly defined function. Can you find a decomposition into $5$ infinite classes and then jiggle a few elements arbitrarily?
– Ethan Bolker
6 hours ago
do a partition of $Bbb N$ into 7 pieces
– janmarqz
6 hours ago