Mixing
Show that cardinality of a set is an equivalent relation - Equivalent according to Zermelo
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
This question is long but the basic idea is super simple: show that $|A| = |B|, |B| = |C| Rightarrow |A| = |C|$. So please don't be intimidated by the length of this post.
First some definition:
A set $W$ is a connection of two disjoint sets $A$ and $B$ (according to Zermelo) if the following hold:
- $Z in W Rightarrow (exists x in A, y in B)[Z = x, y]$
- For each $x in A$, there is exactly one $y in B$ such that $x, y in W$
- For each $y in B$, there is exactly one $x in A$ such that $x, y in W$
For the sake of clarity, we will refer to each element (which is itself a set) as a "pair set" whenever needed; this is done to emphasize that the connection $Sigma(A,B)$ is not the elements of the form $x,y$ satisfying condition 2 and 3 above, but the SET of all such elements.
In other words, $Sigma(A,B)$ refers to an entire set of "pair sets" $x,y$ satisfying conditions 2 and 3. For example, $Sigma(a,b,c, a,d) = emptyset$ while $Sigma(mathbb N, 1,2,3,...)$ could be either the set of all "pair sets" of the form $n, n+1$ or the set of all "pair sets" $0,4, 1, 3, 2, 2, 3,1, n, n+1$ with $n geq 4$ (as an aside, notice also that $1,3$ and $3,1$ are actually the same element). Of course, $Sigma(mathbb N, 1,2,3,...)$ could be neither of the two. Hence there can be multiple options for $Sigma(A, B)$ if $A$ and $B$ have same cardinality.
We may assume that for any two disjoint sets $A, B$, there always exists a connection of the two, denoted $Sigma(A,B)$.
Intuitively, $Sigma(A,B)$ is nonempty if and only if they have same cardinality.
Now I wish to prove the last part of $x3.3$:
Thanks for all the comments. I believe that the book has a typo and it should read "...and nonempty connections" exist (see also the last sentence of next paragraph).
It's also worth mentioning that $Sigma(A,B)$ is not a function of $A,B$ (example provided earlier with $mathbb N$ and $1,2,3,...$); in other words, we are not sure what exactly it is referring to, although we only know the property of its elements (as an analogy, we know what "a set of $5$ real numbers, each of which is greater than $2816$" is referring to, but there are several types of such a set - it could be $10001, 10002, 10003, 10004, 10005$ or $ pi^100, 19378, 10001, 48888, 2817$). Hence, the equivalence relation actually should be interpreted as "$...exists Sigma(A,C) neq emptyset, exists Sigma(B,C) neq emptyset$."
The only thing I am having difficulty is the last of the equivalent condition, transitivity. Here it is difficulty since, though the result is intuitively clear, I am not allowed to create bijection between sets and am only allowed to use the existence of class and first six of $ZF$ Axioms, namely axiom of extensionality, emptyset and pairset axioms, separation axiom, powerset axiom, unionset axiom, and axiom of infinity.
Say $D$ and $E$ are appropriate sets "connecting" the pairs $A,B$ and $B,C$, respectively. If $D=E$ then of course we are done, but I am lost on what to do if that is not the case.
set-theory cardinals equivalence-relations
asked Jul 25 at 3:36
BlueRoses
833314
 |Â
show 4 more comments
up vote
1
down vote
favorite
This question is long but the basic idea is super simple: show that $|A| = |B|, |B| = |C| Rightarrow |A| = |C|$. So please don't be intimidated by the length of this post.
First some definition:
A set $W$ is a connection of two disjoint sets $A$ and $B$ (according to Zermelo) if the following hold:
- $Z in W Rightarrow (exists x in A, y in B)[Z = x, y]$
- For each $x in A$, there is exactly one $y in B$ such that $x, y in W$
- For each $y in B$, there is exactly one $x in A$ such that $x, y in W$
For the sake of clarity, we will refer to each element (which is itself a set) as a "pair set" whenever needed; this is done to emphasize that the connection $Sigma(A,B)$ is not the elements of the form $x,y$ satisfying condition 2 and 3 above, but the SET of all such elements.
In other words, $Sigma(A,B)$ refers to an entire set of "pair sets" $x,y$ satisfying conditions 2 and 3. For example, $Sigma(a,b,c, a,d) = emptyset$ while $Sigma(mathbb N, 1,2,3,...)$ could be either the set of all "pair sets" of the form $n, n+1$ or the set of all "pair sets" $0,4, 1, 3, 2, 2, 3,1, n, n+1$ with $n geq 4$ (as an aside, notice also that $1,3$ and $3,1$ are actually the same element). Of course, $Sigma(mathbb N, 1,2,3,...)$ could be neither of the two. Hence there can be multiple options for $Sigma(A, B)$ if $A$ and $B$ have same cardinality.
We may assume that for any two disjoint sets $A, B$, there always exists a connection of the two, denoted $Sigma(A,B)$.
Intuitively, $Sigma(A,B)$ is nonempty if and only if they have same cardinality.
Now I wish to prove the last part of $x3.3$:
Thanks for all the comments. I believe that the book has a typo and it should read "...and nonempty connections" exist (see also the last sentence of next paragraph).
It's also worth mentioning that $Sigma(A,B)$ is not a function of $A,B$ (example provided earlier with $mathbb N$ and $1,2,3,...$); in other words, we are not sure what exactly it is referring to, although we only know the property of its elements (as an analogy, we know what "a set of $5$ real numbers, each of which is greater than $2816$" is referring to, but there are several types of such a set - it could be $10001, 10002, 10003, 10004, 10005$ or $ pi^100, 19378, 10001, 48888, 2817$). Hence, the equivalence relation actually should be interpreted as "$...exists Sigma(A,C) neq emptyset, exists Sigma(B,C) neq emptyset$."
The only thing I am having difficulty is the last of the equivalent condition, transitivity. Here it is difficulty since, though the result is intuitively clear, I am not allowed to create bijection between sets and am only allowed to use the existence of class and first six of $ZF$ Axioms, namely axiom of extensionality, emptyset and pairset axioms, separation axiom, powerset axiom, unionset axiom, and axiom of infinity.
Say $D$ and $E$ are appropriate sets "connecting" the pairs $A,B$ and $B,C$, respectively. If $D=E$ then of course we are done, but I am lost on what to do if that is not the case.
set-theory cardinals equivalence-relations
asked Jul 25 at 3:36
BlueRoses
833314
I think you should say $Sigma(A, B)$ exists iff they have the same cardinality. Because when they don't have the same cardinality, $Sigma(A, B)$ can't even exist, let alone being none-empty.
– Shervin Sorouri
Jul 25 at 16:07
@ShervinSorouri: Why would you say that? It's a set of "connections". If there are none, it's empty. How would it "not exist"?
– Asaf Karagila
Jul 25 at 16:12
This is really just composing functions, but here functions are represented in a different and peculiar way.
– Asaf Karagila
Jul 25 at 16:13
@AsafKaragila, Oh yeah, i misread that, i thought $Sigma(A, B)$ was just one of those connections.
– Shervin Sorouri
Jul 25 at 16:15
1
Have you proved $Xsim_rm Z X$? If you apply that to $X=Acup Bcup C$, then take the set that connects $X$ to itself, and consider only those elements of it that correspond to elements of $A$...
– Henning Makholm
Jul 26 at 0:12
 |Â
show 4 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This question is long but the basic idea is super simple: show that $|A| = |B|, |B| = |C| Rightarrow |A| = |C|$. So please don't be intimidated by the length of this post.
First some definition:
A set $W$ is a connection of two disjoint sets $A$ and $B$ (according to Zermelo) if the following hold:
- $Z in W Rightarrow (exists x in A, y in B)[Z = x, y]$
- For each $x in A$, there is exactly one $y in B$ such that $x, y in W$
- For each $y in B$, there is exactly one $x in A$ such that $x, y in W$
For the sake of clarity, we will refer to each element (which is itself a set) as a "pair set" whenever needed; this is done to emphasize that the connection $Sigma(A,B)$ is not the elements of the form $x,y$ satisfying condition 2 and 3 above, but the SET of all such elements.
In other words, $Sigma(A,B)$ refers to an entire set of "pair sets" $x,y$ satisfying conditions 2 and 3. For example, $Sigma(a,b,c, a,d) = emptyset$ while $Sigma(mathbb N, 1,2,3,...)$ could be either the set of all "pair sets" of the form $n, n+1$ or the set of all "pair sets" $0,4, 1, 3, 2, 2, 3,1, n, n+1$ with $n geq 4$ (as an aside, notice also that $1,3$ and $3,1$ are actually the same element). Of course, $Sigma(mathbb N, 1,2,3,...)$ could be neither of the two. Hence there can be multiple options for $Sigma(A, B)$ if $A$ and $B$ have same cardinality.
We may assume that for any two disjoint sets $A, B$, there always exists a connection of the two, denoted $Sigma(A,B)$.
Intuitively, $Sigma(A,B)$ is nonempty if and only if they have same cardinality.
Now I wish to prove the last part of $x3.3$:
Thanks for all the comments. I believe that the book has a typo and it should read "...and nonempty connections" exist (see also the last sentence of next paragraph).
It's also worth mentioning that $Sigma(A,B)$ is not a function of $A,B$ (example provided earlier with $mathbb N$ and $1,2,3,...$); in other words, we are not sure what exactly it is referring to, although we only know the property of its elements (as an analogy, we know what "a set of $5$ real numbers, each of which is greater than $2816$" is referring to, but there are several types of such a set - it could be $10001, 10002, 10003, 10004, 10005$ or $ pi^100, 19378, 10001, 48888, 2817$). Hence, the equivalence relation actually should be interpreted as "$...exists Sigma(A,C) neq emptyset, exists Sigma(B,C) neq emptyset$."
The only thing I am having difficulty is the last of the equivalent condition, transitivity. Here it is difficulty since, though the result is intuitively clear, I am not allowed to create bijection between sets and am only allowed to use the existence of class and first six of $ZF$ Axioms, namely axiom of extensionality, emptyset and pairset axioms, separation axiom, powerset axiom, unionset axiom, and axiom of infinity.
Say $D$ and $E$ are appropriate sets "connecting" the pairs $A,B$ and $B,C$, respectively. If $D=E$ then of course we are done, but I am lost on what to do if that is not the case.
set-theory cardinals equivalence-relations
asked Jul 25 at 3:36
BlueRoses
833314
This question is long but the basic idea is super simple: show that $|A| = |B|, |B| = |C| Rightarrow |A| = |C|$. So please don't be intimidated by the length of this post.
First some definition:
A set $W$ is a connection of two disjoint sets $A$ and $B$ (according to Zermelo) if the following hold:
- $Z in W Rightarrow (exists x in A, y in B)[Z = x, y]$
- For each $x in A$, there is exactly one $y in B$ such that $x, y in W$
- For each $y in B$, there is exactly one $x in A$ such that $x, y in W$
For the sake of clarity, we will refer to each element (which is itself a set) as a "pair set" whenever needed; this is done to emphasize that the connection $Sigma(A,B)$ is not the elements of the form $x,y$ satisfying condition 2 and 3 above, but the SET of all such elements.
In other words, $Sigma(A,B)$ refers to an entire set of "pair sets" $x,y$ satisfying conditions 2 and 3. For example, $Sigma(a,b,c, a,d) = emptyset$ while $Sigma(mathbb N, 1,2,3,...)$ could be either the set of all "pair sets" of the form $n, n+1$ or the set of all "pair sets" $0,4, 1, 3, 2, 2, 3,1, n, n+1$ with $n geq 4$ (as an aside, notice also that $1,3$ and $3,1$ are actually the same element). Of course, $Sigma(mathbb N, 1,2,3,...)$ could be neither of the two. Hence there can be multiple options for $Sigma(A, B)$ if $A$ and $B$ have same cardinality.
We may assume that for any two disjoint sets $A, B$, there always exists a connection of the two, denoted $Sigma(A,B)$.
Intuitively, $Sigma(A,B)$ is nonempty if and only if they have same cardinality.
Now I wish to prove the last part of $x3.3$:
Thanks for all the comments. I believe that the book has a typo and it should read "...and nonempty connections" exist (see also the last sentence of next paragraph).
It's also worth mentioning that $Sigma(A,B)$ is not a function of $A,B$ (example provided earlier with $mathbb N$ and $1,2,3,...$); in other words, we are not sure what exactly it is referring to, although we only know the property of its elements (as an analogy, we know what "a set of $5$ real numbers, each of which is greater than $2816$" is referring to, but there are several types of such a set - it could be $10001, 10002, 10003, 10004, 10005$ or $ pi^100, 19378, 10001, 48888, 2817$). Hence, the equivalence relation actually should be interpreted as "$...exists Sigma(A,C) neq emptyset, exists Sigma(B,C) neq emptyset$."
The only thing I am having difficulty is the last of the equivalent condition, transitivity. Here it is difficulty since, though the result is intuitively clear, I am not allowed to create bijection between sets and am only allowed to use the existence of class and first six of $ZF$ Axioms, namely axiom of extensionality, emptyset and pairset axioms, separation axiom, powerset axiom, unionset axiom, and axiom of infinity.
Say $D$ and $E$ are appropriate sets "connecting" the pairs $A,B$ and $B,C$, respectively. If $D=E$ then of course we are done, but I am lost on what to do if that is not the case.
set-theory cardinals equivalence-relations
asked Jul 25 at 3:36
BlueRoses
833314
edited Jul 26 at 0:40
asked Jul 25 at 3:36
BlueRoses
833314
asked Jul 25 at 3:36
BlueRoses
833314
asked Jul 25 at 3:36
BlueRoses
833314
833314
I think you should say $Sigma(A, B)$ exists iff they have the same cardinality. Because when they don't have the same cardinality, $Sigma(A, B)$ can't even exist, let alone being none-empty.
– Shervin Sorouri
Jul 25 at 16:07
@ShervinSorouri: Why would you say that? It's a set of "connections". If there are none, it's empty. How would it "not exist"?
– Asaf Karagila
Jul 25 at 16:12
This is really just composing functions, but here functions are represented in a different and peculiar way.
– Asaf Karagila
Jul 25 at 16:13
@AsafKaragila, Oh yeah, i misread that, i thought $Sigma(A, B)$ was just one of those connections.
– Shervin Sorouri
Jul 25 at 16:15
1
Have you proved $Xsim_rm Z X$? If you apply that to $X=Acup Bcup C$, then take the set that connects $X$ to itself, and consider only those elements of it that correspond to elements of $A$...
– Henning Makholm
Jul 26 at 0:12
 |Â
show 4 more comments
I think you should say $Sigma(A, B)$ exists iff they have the same cardinality. Because when they don't have the same cardinality, $Sigma(A, B)$ can't even exist, let alone being none-empty.
– Shervin Sorouri
Jul 25 at 16:07
@ShervinSorouri: Why would you say that? It's a set of "connections". If there are none, it's empty. How would it "not exist"?
– Asaf Karagila
Jul 25 at 16:12
This is really just composing functions, but here functions are represented in a different and peculiar way.
– Asaf Karagila
Jul 25 at 16:13
@AsafKaragila, Oh yeah, i misread that, i thought $Sigma(A, B)$ was just one of those connections.
– Shervin Sorouri
Jul 25 at 16:15
1
Have you proved $Xsim_rm Z X$? If you apply that to $X=Acup Bcup C$, then take the set that connects $X$ to itself, and consider only those elements of it that correspond to elements of $A$...
– Henning Makholm
Jul 26 at 0:12
I think you should say $Sigma(A, B)$ exists iff they have the same cardinality. Because when they don't have the same cardinality, $Sigma(A, B)$ can't even exist, let alone being none-empty.
– Shervin Sorouri
Jul 25 at 16:07
I think you should say $Sigma(A, B)$ exists iff they have the same cardinality. Because when they don't have the same cardinality, $Sigma(A, B)$ can't even exist, let alone being none-empty.
– Shervin Sorouri
Jul 25 at 16:07
@ShervinSorouri: Why would you say that? It's a set of "connections". If there are none, it's empty. How would it "not exist"?
– Asaf Karagila
Jul 25 at 16:12
@ShervinSorouri: Why would you say that? It's a set of "connections". If there are none, it's empty. How would it "not exist"?
– Asaf Karagila
Jul 25 at 16:12
This is really just composing functions, but here functions are represented in a different and peculiar way.
– Asaf Karagila
Jul 25 at 16:13
This is really just composing functions, but here functions are represented in a different and peculiar way.
– Asaf Karagila
Jul 25 at 16:13
@AsafKaragila, Oh yeah, i misread that, i thought $Sigma(A, B)$ was just one of those connections.
– Shervin Sorouri
Jul 25 at 16:15
@AsafKaragila, Oh yeah, i misread that, i thought $Sigma(A, B)$ was just one of those connections.
– Shervin Sorouri
Jul 25 at 16:15
1
1
Have you proved $Xsim_rm Z X$? If you apply that to $X=Acup Bcup C$, then take the set that connects $X$ to itself, and consider only those elements of it that correspond to elements of $A$...
– Henning Makholm
Jul 26 at 0:12
Have you proved $Xsim_rm Z X$? If you apply that to $X=Acup Bcup C$, then take the set that connects $X$ to itself, and consider only those elements of it that correspond to elements of $A$...
– Henning Makholm
Jul 26 at 0:12
 |Â
show 4 more comments
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
The difficulty here is to find some way to construct a set that is "obviously" in bijective correspondence with $A$ and yet disjoint from both $A$ and $C$.
The same difficulty arises if you want to show that $Asim_rm Z A$.
Without "cheating" and defining Kuratowski pairs so we can just proceed in a more modern way, and also without Regularity, the best I can think of is to diagonalize our way to some new elements. The core of that would be the following lemma -- I'll leave it to you to apply it in your particular situation...
Lemma. Let $X$ be a set. There exists a $Y$ disjoint from $X$ such that $Sigma(X,Y)$ is nonempty.
Proof. Choose and fix two sets $0$ and $1$ that are not elements of $X$. (That has to be possible, or Separation would create a contradiction through Russell's paradox). Then define
$$ overline X = 0,x mid xin Xland 0,xnotin x $$
and then set
$$ Y = overline X cup 1,x mid xin X $$
Even though it looks like we need Replacement, these in fact both exist due to Separation because they are both are subsets of $mathcal P(Xcup0,1)$.
But no $yin Y$ can equal any $xin X$, because $0,xin y$ iff $0,xin overline X$ which is exactly if $0,xnotin x$.
answered Jul 26 at 0:24
Henning Makholm
225k16290516
1
@BlueRoses: Russells paradox shows that there is no set of all sets. In particular $X$ cannot be a set of all sets, so there is some $0notin X$. But $Xcup0$ is not a set of all sets either, so we can pick a $1$ not in that.
– Henning Makholm
Jul 26 at 0:32
1
Or, by unfolding the argument of Russell's paradox, you can concretely set $0=xin Xmid xnotin x$ and set $1=0cup0$, (since $0$ cannot contain itself because $0subseteq X$ and $0notin X$).
– Henning Makholm
Jul 26 at 0:34
@BlueRoses: Why would they have a different number of elements? By definition $Y$ has one element arising from each $xin X$, namely the set $overline Xcup1,x$. (And these are all different because each of them has only that one element containing $1$).
– Henning Makholm
Jul 26 at 0:48
@BlueRoses: Mostly by having plenty of experience and knowing a lot of tricks already. In this case, diagonalization is a standard trick for constructing something of a given kind that differs from a lot of other things at the same time -- or in other words, to find something outside a given set. So that was the "bigger gun" I pulled out when about 10 minutes of trying to make something simpler work didn't yield results. The rest was just a matter of puzzling out how the details would fit together.
– Henning Makholm
Jul 26 at 1:17
Henning, Russell's Paradox shows that there is no set of all sets which are not members of themselves, which in turn implies that not every class is a set. In presence of full Separation this implies there is no set of all sets as well. But New Foundations avoids Russell's Paradox while retaining a universal set just fine.
– Asaf Karagila
Jul 26 at 6:52
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
The difficulty here is to find some way to construct a set that is "obviously" in bijective correspondence with $A$ and yet disjoint from both $A$ and $C$.
The same difficulty arises if you want to show that $Asim_rm Z A$.
Without "cheating" and defining Kuratowski pairs so we can just proceed in a more modern way, and also without Regularity, the best I can think of is to diagonalize our way to some new elements. The core of that would be the following lemma -- I'll leave it to you to apply it in your particular situation...
Lemma. Let $X$ be a set. There exists a $Y$ disjoint from $X$ such that $Sigma(X,Y)$ is nonempty.
Proof. Choose and fix two sets $0$ and $1$ that are not elements of $X$. (That has to be possible, or Separation would create a contradiction through Russell's paradox). Then define
$$ overline X = 0,x mid xin Xland 0,xnotin x $$
and then set
$$ Y = overline X cup 1,x mid xin X $$
Even though it looks like we need Replacement, these in fact both exist due to Separation because they are both are subsets of $mathcal P(Xcup0,1)$.
But no $yin Y$ can equal any $xin X$, because $0,xin y$ iff $0,xin overline X$ which is exactly if $0,xnotin x$.
answered Jul 26 at 0:24
Henning Makholm
225k16290516
1
@BlueRoses: Russells paradox shows that there is no set of all sets. In particular $X$ cannot be a set of all sets, so there is some $0notin X$. But $Xcup0$ is not a set of all sets either, so we can pick a $1$ not in that.
– Henning Makholm
Jul 26 at 0:32
1
Or, by unfolding the argument of Russell's paradox, you can concretely set $0=xin Xmid xnotin x$ and set $1=0cup0$, (since $0$ cannot contain itself because $0subseteq X$ and $0notin X$).
– Henning Makholm
Jul 26 at 0:34
@BlueRoses: Why would they have a different number of elements? By definition $Y$ has one element arising from each $xin X$, namely the set $overline Xcup1,x$. (And these are all different because each of them has only that one element containing $1$).
– Henning Makholm
Jul 26 at 0:48
@BlueRoses: Mostly by having plenty of experience and knowing a lot of tricks already. In this case, diagonalization is a standard trick for constructing something of a given kind that differs from a lot of other things at the same time -- or in other words, to find something outside a given set. So that was the "bigger gun" I pulled out when about 10 minutes of trying to make something simpler work didn't yield results. The rest was just a matter of puzzling out how the details would fit together.
– Henning Makholm
Jul 26 at 1:17
Henning, Russell's Paradox shows that there is no set of all sets which are not members of themselves, which in turn implies that not every class is a set. In presence of full Separation this implies there is no set of all sets as well. But New Foundations avoids Russell's Paradox while retaining a universal set just fine.
– Asaf Karagila
Jul 26 at 6:52
 |Â
show 1 more comment
up vote
2
down vote
accepted
The difficulty here is to find some way to construct a set that is "obviously" in bijective correspondence with $A$ and yet disjoint from both $A$ and $C$.
The same difficulty arises if you want to show that $Asim_rm Z A$.
Without "cheating" and defining Kuratowski pairs so we can just proceed in a more modern way, and also without Regularity, the best I can think of is to diagonalize our way to some new elements. The core of that would be the following lemma -- I'll leave it to you to apply it in your particular situation...
Lemma. Let $X$ be a set. There exists a $Y$ disjoint from $X$ such that $Sigma(X,Y)$ is nonempty.
Proof. Choose and fix two sets $0$ and $1$ that are not elements of $X$. (That has to be possible, or Separation would create a contradiction through Russell's paradox). Then define
$$ overline X = 0,x mid xin Xland 0,xnotin x $$
and then set
$$ Y = overline X cup 1,x mid xin X $$
Even though it looks like we need Replacement, these in fact both exist due to Separation because they are both are subsets of $mathcal P(Xcup0,1)$.
But no $yin Y$ can equal any $xin X$, because $0,xin y$ iff $0,xin overline X$ which is exactly if $0,xnotin x$.
answered Jul 26 at 0:24
Henning Makholm
225k16290516
1
@BlueRoses: Russells paradox shows that there is no set of all sets. In particular $X$ cannot be a set of all sets, so there is some $0notin X$. But $Xcup0$ is not a set of all sets either, so we can pick a $1$ not in that.
– Henning Makholm
Jul 26 at 0:32
1
Or, by unfolding the argument of Russell's paradox, you can concretely set $0=xin Xmid xnotin x$ and set $1=0cup0$, (since $0$ cannot contain itself because $0subseteq X$ and $0notin X$).
– Henning Makholm
Jul 26 at 0:34
@BlueRoses: Why would they have a different number of elements? By definition $Y$ has one element arising from each $xin X$, namely the set $overline Xcup1,x$. (And these are all different because each of them has only that one element containing $1$).
– Henning Makholm
Jul 26 at 0:48
@BlueRoses: Mostly by having plenty of experience and knowing a lot of tricks already. In this case, diagonalization is a standard trick for constructing something of a given kind that differs from a lot of other things at the same time -- or in other words, to find something outside a given set. So that was the "bigger gun" I pulled out when about 10 minutes of trying to make something simpler work didn't yield results. The rest was just a matter of puzzling out how the details would fit together.
– Henning Makholm
Jul 26 at 1:17
Henning, Russell's Paradox shows that there is no set of all sets which are not members of themselves, which in turn implies that not every class is a set. In presence of full Separation this implies there is no set of all sets as well. But New Foundations avoids Russell's Paradox while retaining a universal set just fine.
– Asaf Karagila
Jul 26 at 6:52
 |Â
show 1 more comment
up vote
2
down vote
accepted
up vote
2
down vote
accepted
The difficulty here is to find some way to construct a set that is "obviously" in bijective correspondence with $A$ and yet disjoint from both $A$ and $C$.
The same difficulty arises if you want to show that $Asim_rm Z A$.
Without "cheating" and defining Kuratowski pairs so we can just proceed in a more modern way, and also without Regularity, the best I can think of is to diagonalize our way to some new elements. The core of that would be the following lemma -- I'll leave it to you to apply it in your particular situation...
Lemma. Let $X$ be a set. There exists a $Y$ disjoint from $X$ such that $Sigma(X,Y)$ is nonempty.
Proof. Choose and fix two sets $0$ and $1$ that are not elements of $X$. (That has to be possible, or Separation would create a contradiction through Russell's paradox). Then define
$$ overline X = 0,x mid xin Xland 0,xnotin x $$
and then set
$$ Y = overline X cup 1,x mid xin X $$
Even though it looks like we need Replacement, these in fact both exist due to Separation because they are both are subsets of $mathcal P(Xcup0,1)$.
But no $yin Y$ can equal any $xin X$, because $0,xin y$ iff $0,xin overline X$ which is exactly if $0,xnotin x$.
answered Jul 26 at 0:24
Henning Makholm
225k16290516
The difficulty here is to find some way to construct a set that is "obviously" in bijective correspondence with $A$ and yet disjoint from both $A$ and $C$.
The same difficulty arises if you want to show that $Asim_rm Z A$.
Without "cheating" and defining Kuratowski pairs so we can just proceed in a more modern way, and also without Regularity, the best I can think of is to diagonalize our way to some new elements. The core of that would be the following lemma -- I'll leave it to you to apply it in your particular situation...
Lemma. Let $X$ be a set. There exists a $Y$ disjoint from $X$ such that $Sigma(X,Y)$ is nonempty.
Proof. Choose and fix two sets $0$ and $1$ that are not elements of $X$. (That has to be possible, or Separation would create a contradiction through Russell's paradox). Then define
$$ overline X = 0,x mid xin Xland 0,xnotin x $$
and then set
$$ Y = overline X cup 1,x mid xin X $$
Even though it looks like we need Replacement, these in fact both exist due to Separation because they are both are subsets of $mathcal P(Xcup0,1)$.
But no $yin Y$ can equal any $xin X$, because $0,xin y$ iff $0,xin overline X$ which is exactly if $0,xnotin x$.
answered Jul 26 at 0:24
Henning Makholm
225k16290516
edited Jul 26 at 0:40
answered Jul 26 at 0:24
Henning Makholm
225k16290516
answered Jul 26 at 0:24
Henning Makholm
225k16290516
answered Jul 26 at 0:24
Henning Makholm
225k16290516
225k16290516
1
@BlueRoses: Russells paradox shows that there is no set of all sets. In particular $X$ cannot be a set of all sets, so there is some $0notin X$. But $Xcup0$ is not a set of all sets either, so we can pick a $1$ not in that.
– Henning Makholm
Jul 26 at 0:32
1
Or, by unfolding the argument of Russell's paradox, you can concretely set $0=xin Xmid xnotin x$ and set $1=0cup0$, (since $0$ cannot contain itself because $0subseteq X$ and $0notin X$).
– Henning Makholm
Jul 26 at 0:34
@BlueRoses: Why would they have a different number of elements? By definition $Y$ has one element arising from each $xin X$, namely the set $overline Xcup1,x$. (And these are all different because each of them has only that one element containing $1$).
– Henning Makholm
Jul 26 at 0:48
@BlueRoses: Mostly by having plenty of experience and knowing a lot of tricks already. In this case, diagonalization is a standard trick for constructing something of a given kind that differs from a lot of other things at the same time -- or in other words, to find something outside a given set. So that was the "bigger gun" I pulled out when about 10 minutes of trying to make something simpler work didn't yield results. The rest was just a matter of puzzling out how the details would fit together.
– Henning Makholm
Jul 26 at 1:17
Henning, Russell's Paradox shows that there is no set of all sets which are not members of themselves, which in turn implies that not every class is a set. In presence of full Separation this implies there is no set of all sets as well. But New Foundations avoids Russell's Paradox while retaining a universal set just fine.
– Asaf Karagila
Jul 26 at 6:52
 |Â
show 1 more comment
1
@BlueRoses: Russells paradox shows that there is no set of all sets. In particular $X$ cannot be a set of all sets, so there is some $0notin X$. But $Xcup0$ is not a set of all sets either, so we can pick a $1$ not in that.
– Henning Makholm
Jul 26 at 0:32
1
Or, by unfolding the argument of Russell's paradox, you can concretely set $0=xin Xmid xnotin x$ and set $1=0cup0$, (since $0$ cannot contain itself because $0subseteq X$ and $0notin X$).
– Henning Makholm
Jul 26 at 0:34
@BlueRoses: Why would they have a different number of elements? By definition $Y$ has one element arising from each $xin X$, namely the set $overline Xcup1,x$. (And these are all different because each of them has only that one element containing $1$).
– Henning Makholm
Jul 26 at 0:48
@BlueRoses: Mostly by having plenty of experience and knowing a lot of tricks already. In this case, diagonalization is a standard trick for constructing something of a given kind that differs from a lot of other things at the same time -- or in other words, to find something outside a given set. So that was the "bigger gun" I pulled out when about 10 minutes of trying to make something simpler work didn't yield results. The rest was just a matter of puzzling out how the details would fit together.
– Henning Makholm
Jul 26 at 1:17
Henning, Russell's Paradox shows that there is no set of all sets which are not members of themselves, which in turn implies that not every class is a set. In presence of full Separation this implies there is no set of all sets as well. But New Foundations avoids Russell's Paradox while retaining a universal set just fine.
– Asaf Karagila
Jul 26 at 6:52
1
1
@BlueRoses: Russells paradox shows that there is no set of all sets. In particular $X$ cannot be a set of all sets, so there is some $0notin X$. But $Xcup0$ is not a set of all sets either, so we can pick a $1$ not in that.
– Henning Makholm
Jul 26 at 0:32
@BlueRoses: Russells paradox shows that there is no set of all sets. In particular $X$ cannot be a set of all sets, so there is some $0notin X$. But $Xcup0$ is not a set of all sets either, so we can pick a $1$ not in that.
– Henning Makholm
Jul 26 at 0:32
1
1
Or, by unfolding the argument of Russell's paradox, you can concretely set $0=xin Xmid xnotin x$ and set $1=0cup0$, (since $0$ cannot contain itself because $0subseteq X$ and $0notin X$).
– Henning Makholm
Jul 26 at 0:34
Or, by unfolding the argument of Russell's paradox, you can concretely set $0=xin Xmid xnotin x$ and set $1=0cup0$, (since $0$ cannot contain itself because $0subseteq X$ and $0notin X$).
– Henning Makholm
Jul 26 at 0:34
@BlueRoses: Why would they have a different number of elements? By definition $Y$ has one element arising from each $xin X$, namely the set $overline Xcup1,x$. (And these are all different because each of them has only that one element containing $1$).
– Henning Makholm
Jul 26 at 0:48
@BlueRoses: Why would they have a different number of elements? By definition $Y$ has one element arising from each $xin X$, namely the set $overline Xcup1,x$. (And these are all different because each of them has only that one element containing $1$).
– Henning Makholm
Jul 26 at 0:48
@BlueRoses: Mostly by having plenty of experience and knowing a lot of tricks already. In this case, diagonalization is a standard trick for constructing something of a given kind that differs from a lot of other things at the same time -- or in other words, to find something outside a given set. So that was the "bigger gun" I pulled out when about 10 minutes of trying to make something simpler work didn't yield results. The rest was just a matter of puzzling out how the details would fit together.
– Henning Makholm
Jul 26 at 1:17
@BlueRoses: Mostly by having plenty of experience and knowing a lot of tricks already. In this case, diagonalization is a standard trick for constructing something of a given kind that differs from a lot of other things at the same time -- or in other words, to find something outside a given set. So that was the "bigger gun" I pulled out when about 10 minutes of trying to make something simpler work didn't yield results. The rest was just a matter of puzzling out how the details would fit together.
– Henning Makholm
Jul 26 at 1:17
Henning, Russell's Paradox shows that there is no set of all sets which are not members of themselves, which in turn implies that not every class is a set. In presence of full Separation this implies there is no set of all sets as well. But New Foundations avoids Russell's Paradox while retaining a universal set just fine.
– Asaf Karagila
Jul 26 at 6:52
Henning, Russell's Paradox shows that there is no set of all sets which are not members of themselves, which in turn implies that not every class is a set. In presence of full Separation this implies there is no set of all sets as well. But New Foundations avoids Russell's Paradox while retaining a universal set just fine.
– Asaf Karagila
Jul 26 at 6:52
 |Â
show 1 more 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%2f2861988%2fshow-that-cardinality-of-a-set-is-an-equivalent-relation-equivalent-according%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
I think you should say $Sigma(A, B)$ exists iff they have the same cardinality. Because when they don't have the same cardinality, $Sigma(A, B)$ can't even exist, let alone being none-empty.
– Shervin Sorouri
Jul 25 at 16:07
@ShervinSorouri: Why would you say that? It's a set of "connections". If there are none, it's empty. How would it "not exist"?
– Asaf Karagila
Jul 25 at 16:12
This is really just composing functions, but here functions are represented in a different and peculiar way.
– Asaf Karagila
Jul 25 at 16:13
@AsafKaragila, Oh yeah, i misread that, i thought $Sigma(A, B)$ was just one of those connections.
– Shervin Sorouri
Jul 25 at 16:15
1
Have you proved $Xsim_rm Z X$? If you apply that to $X=Acup Bcup C$, then take the set that connects $X$ to itself, and consider only those elements of it that correspond to elements of $A$...
– Henning Makholm
Jul 26 at 0:12