Mixing
Explanation of and alternative proof for Cantor's Theorem
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I'll state the Cantor's theorem proof as is it is in my study texts:
Theorem (Cantor): Let $X$ be any set. Then $|X|<|mathcalP(X)|$
Proof: Define map $varphi:XrightarrowmathcalP(X)$ by $varphi:xmapstox$. $varphi$ is injective, thus $|X|leq|mathcalP(X)|$. Now suppose there is a bijection (surjection) $psi:XrightarrowmathcalP(X)$. Denote the set $A=xin X, xnotin psi(x)$. By assumption, $psi$ is surjection so we find some $ain X$ such that $psi(a)=A$. Then we have two cases, either $ain A$, but the, by definition of $A$: $anotin psi(a)$ which is a contradiction. So $anotin A$ but then $ain psi(a)=A$ which is a contradiction aswell thus such surjection cannot exist.
So now, for my question. The definition of $A$ seems really weird to me. Because, in the first place. Assume $X=1,2$ then $mathcalP(X)=1,2,1,2,emptyset$. In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $psi$ but, the range of $psi$ are sets, aren't they? Thus $A=1,2$ and the case is $forall ain X:ainA$ thus the second case of the proof applies. Basically this leads me to the following idea: instead of constructing this set $A$, we can say that:
Estabilish injection and thus $|X|leq|mathcalP(X)|$ by $varphi:xmapstox$ thus $forallSinvarphi(x):|S|=1$, but for any set $X:$ $emptysetsubsetmathcalP(X)$ but $|emptyset|=0$ so $emptysetnotin ran(varphi)$ thus $varphi$ is not surjective.
elementary-set-theory proof-explanation
edited Jul 26 at 9:06
Asaf Karagila
291k31402732
asked Jul 26 at 8:02
Michal Dvořák
48912
add a comment |Â
up vote
1
down vote
favorite
I'll state the Cantor's theorem proof as is it is in my study texts:
Theorem (Cantor): Let $X$ be any set. Then $|X|<|mathcalP(X)|$
Proof: Define map $varphi:XrightarrowmathcalP(X)$ by $varphi:xmapstox$. $varphi$ is injective, thus $|X|leq|mathcalP(X)|$. Now suppose there is a bijection (surjection) $psi:XrightarrowmathcalP(X)$. Denote the set $A=xin X, xnotin psi(x)$. By assumption, $psi$ is surjection so we find some $ain X$ such that $psi(a)=A$. Then we have two cases, either $ain A$, but the, by definition of $A$: $anotin psi(a)$ which is a contradiction. So $anotin A$ but then $ain psi(a)=A$ which is a contradiction aswell thus such surjection cannot exist.
So now, for my question. The definition of $A$ seems really weird to me. Because, in the first place. Assume $X=1,2$ then $mathcalP(X)=1,2,1,2,emptyset$. In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $psi$ but, the range of $psi$ are sets, aren't they? Thus $A=1,2$ and the case is $forall ain X:ainA$ thus the second case of the proof applies. Basically this leads me to the following idea: instead of constructing this set $A$, we can say that:
Estabilish injection and thus $|X|leq|mathcalP(X)|$ by $varphi:xmapstox$ thus $forallSinvarphi(x):|S|=1$, but for any set $X:$ $emptysetsubsetmathcalP(X)$ but $|emptyset|=0$ so $emptysetnotin ran(varphi)$ thus $varphi$ is not surjective.
elementary-set-theory proof-explanation
edited Jul 26 at 9:06
Asaf Karagila
291k31402732
asked Jul 26 at 8:02
Michal Dvořák
48912
2
"In the proof $A$ is supposed to be the set of all members of $X$ that are not in the range of $psi$" No, that's not what $A$ is supposed to be. If $xin X$ then $psi(x)$ is a subset of $X$ and $A$ is a subset of $X$; and $Anepsi(x)$ because the two sets, $A$ and $psi(x),$ differ at $x$; namely, $$xin Aiff xnotinpsi(x).$$
– bof
Jul 26 at 8:19
1
The definition of $A$ is a kind of diagonalization.
– Hanul Jeon
Jul 26 at 8:21
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I'll state the Cantor's theorem proof as is it is in my study texts:
Theorem (Cantor): Let $X$ be any set. Then $|X|<|mathcalP(X)|$
Proof: Define map $varphi:XrightarrowmathcalP(X)$ by $varphi:xmapstox$. $varphi$ is injective, thus $|X|leq|mathcalP(X)|$. Now suppose there is a bijection (surjection) $psi:XrightarrowmathcalP(X)$. Denote the set $A=xin X, xnotin psi(x)$. By assumption, $psi$ is surjection so we find some $ain X$ such that $psi(a)=A$. Then we have two cases, either $ain A$, but the, by definition of $A$: $anotin psi(a)$ which is a contradiction. So $anotin A$ but then $ain psi(a)=A$ which is a contradiction aswell thus such surjection cannot exist.
So now, for my question. The definition of $A$ seems really weird to me. Because, in the first place. Assume $X=1,2$ then $mathcalP(X)=1,2,1,2,emptyset$. In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $psi$ but, the range of $psi$ are sets, aren't they? Thus $A=1,2$ and the case is $forall ain X:ainA$ thus the second case of the proof applies. Basically this leads me to the following idea: instead of constructing this set $A$, we can say that:
Estabilish injection and thus $|X|leq|mathcalP(X)|$ by $varphi:xmapstox$ thus $forallSinvarphi(x):|S|=1$, but for any set $X:$ $emptysetsubsetmathcalP(X)$ but $|emptyset|=0$ so $emptysetnotin ran(varphi)$ thus $varphi$ is not surjective.
elementary-set-theory proof-explanation
edited Jul 26 at 9:06
Asaf Karagila
291k31402732
asked Jul 26 at 8:02
Michal Dvořák
48912
I'll state the Cantor's theorem proof as is it is in my study texts:
Theorem (Cantor): Let $X$ be any set. Then $|X|<|mathcalP(X)|$
Proof: Define map $varphi:XrightarrowmathcalP(X)$ by $varphi:xmapstox$. $varphi$ is injective, thus $|X|leq|mathcalP(X)|$. Now suppose there is a bijection (surjection) $psi:XrightarrowmathcalP(X)$. Denote the set $A=xin X, xnotin psi(x)$. By assumption, $psi$ is surjection so we find some $ain X$ such that $psi(a)=A$. Then we have two cases, either $ain A$, but the, by definition of $A$: $anotin psi(a)$ which is a contradiction. So $anotin A$ but then $ain psi(a)=A$ which is a contradiction aswell thus such surjection cannot exist.
So now, for my question. The definition of $A$ seems really weird to me. Because, in the first place. Assume $X=1,2$ then $mathcalP(X)=1,2,1,2,emptyset$. In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $psi$ but, the range of $psi$ are sets, aren't they? Thus $A=1,2$ and the case is $forall ain X:ainA$ thus the second case of the proof applies. Basically this leads me to the following idea: instead of constructing this set $A$, we can say that:
Estabilish injection and thus $|X|leq|mathcalP(X)|$ by $varphi:xmapstox$ thus $forallSinvarphi(x):|S|=1$, but for any set $X:$ $emptysetsubsetmathcalP(X)$ but $|emptyset|=0$ so $emptysetnotin ran(varphi)$ thus $varphi$ is not surjective.
elementary-set-theory proof-explanation
edited Jul 26 at 9:06
Asaf Karagila
291k31402732
asked Jul 26 at 8:02
Michal Dvořák
48912
edited Jul 26 at 9:06
Asaf Karagila
291k31402732
edited Jul 26 at 9:06
Asaf Karagila
291k31402732
edited Jul 26 at 9:06
Asaf Karagila
291k31402732
291k31402732
asked Jul 26 at 8:02
Michal Dvořák
48912
asked Jul 26 at 8:02
Michal Dvořák
48912
asked Jul 26 at 8:02
Michal Dvořák
48912
48912
2
"In the proof $A$ is supposed to be the set of all members of $X$ that are not in the range of $psi$" No, that's not what $A$ is supposed to be. If $xin X$ then $psi(x)$ is a subset of $X$ and $A$ is a subset of $X$; and $Anepsi(x)$ because the two sets, $A$ and $psi(x),$ differ at $x$; namely, $$xin Aiff xnotinpsi(x).$$
– bof
Jul 26 at 8:19
1
The definition of $A$ is a kind of diagonalization.
– Hanul Jeon
Jul 26 at 8:21
add a comment |Â
2
"In the proof $A$ is supposed to be the set of all members of $X$ that are not in the range of $psi$" No, that's not what $A$ is supposed to be. If $xin X$ then $psi(x)$ is a subset of $X$ and $A$ is a subset of $X$; and $Anepsi(x)$ because the two sets, $A$ and $psi(x),$ differ at $x$; namely, $$xin Aiff xnotinpsi(x).$$
– bof
Jul 26 at 8:19
1
The definition of $A$ is a kind of diagonalization.
– Hanul Jeon
Jul 26 at 8:21
2
2
"In the proof $A$ is supposed to be the set of all members of $X$ that are not in the range of $psi$" No, that's not what $A$ is supposed to be. If $xin X$ then $psi(x)$ is a subset of $X$ and $A$ is a subset of $X$; and $Anepsi(x)$ because the two sets, $A$ and $psi(x),$ differ at $x$; namely, $$xin Aiff xnotinpsi(x).$$
– bof
Jul 26 at 8:19
"In the proof $A$ is supposed to be the set of all members of $X$ that are not in the range of $psi$" No, that's not what $A$ is supposed to be. If $xin X$ then $psi(x)$ is a subset of $X$ and $A$ is a subset of $X$; and $Anepsi(x)$ because the two sets, $A$ and $psi(x),$ differ at $x$; namely, $$xin Aiff xnotinpsi(x).$$
– bof
Jul 26 at 8:19
1
1
The definition of $A$ is a kind of diagonalization.
– Hanul Jeon
Jul 26 at 8:21
The definition of $A$ is a kind of diagonalization.
– Hanul Jeon
Jul 26 at 8:21
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
6
down vote
accepted
In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $psi$
No, this is not quite true. The construction is more subtle than that. For any $x in X$, the value $psi(x) in mathcal P(X)$ is some set -- a subset of $X$ to be precise. Note that this is not the range of $psi$, it is the value of $psi(x)$ for a single $x$.
Then we have either $x in psi(x)$ or $x notin psi(x)$, and we add $x$ to the set $A$ if and only if $x notin psi(x)$.
answered Jul 26 at 8:18
Mees de Vries
13.7k12345
So $A$ is the set for which the map $psi$ maps some $xin X$ to some say $Tin mathcalP(X)$ for which $xnotin T$?
– Michal Dvořák
Jul 26 at 8:20
2
$A$ is the set of such $x$, yes. The $x$ that are in $A$ are precisely the $x$ for which that is true.
– Mees de Vries
Jul 26 at 8:23
add a comment |Â
up vote
3
down vote
That the specific mapping $ varphi$ is not surjective, hence not bijective, is clear.
To prove that $|X|<|mathcalP(X)|$ , it is enough to show that each(!) mapping $psi:XrightarrowmathcalP(X)$ cannot be surjective.
In the proof above it is assumed that there is a surjective mapping $psi:XrightarrowmathcalP(X)$ . But this leads to a contradiction....
answered Jul 26 at 8:13
Fred
37.2k1237
So, my proof cannot be legit, because I've only constructed "one" non-surjective mapping, which doesn't prove there isn't "any"?
– Michal Dvořák
Jul 26 at 8:15
1
@Michal Dvořák Right, you have to prove no mapping from $X$ to $mathcalP(X)$ can be surjective.
– Hanul Jeon
Jul 26 at 8:19
Without the axiom of choice it is possible that two sets have no surjections between them, but no injection either. To establish $<$ one has to establish an injection and no bijection (which follows from no surjection).
– Asaf Karagila
Jul 26 at 8:57
add a comment |Â
up vote
1
down vote
Mees de Vries' answer gives an explanation of where your misunderstanding of the usual proof was.
To address your alternative proof attempt: you show that there is a particular injection from $X$ to $mathcalP(X)$, but that it's not surjective. This isn't enough to prove that $|X|<|mathcalP(X)|$. For example, we can define a function from $mathbb N$ to $mathbb Ntimes mathbb N$ by $varphi(n)=(n,1)$, which is injective but not surjective. However, $|mathbb N|=|mathbb Ntimes mathbb N|$ because other, more complicated, functions exist which are both injective and surjective (e.g. $psi(n)=(a,b)$ where $a,b$ are the unique positive integers such that $n=(2a-1)2^b-1$).
answered Jul 26 at 11:25
Especially Lime
19.1k22252
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $psi$
No, this is not quite true. The construction is more subtle than that. For any $x in X$, the value $psi(x) in mathcal P(X)$ is some set -- a subset of $X$ to be precise. Note that this is not the range of $psi$, it is the value of $psi(x)$ for a single $x$.
Then we have either $x in psi(x)$ or $x notin psi(x)$, and we add $x$ to the set $A$ if and only if $x notin psi(x)$.
answered Jul 26 at 8:18
Mees de Vries
13.7k12345
So $A$ is the set for which the map $psi$ maps some $xin X$ to some say $Tin mathcalP(X)$ for which $xnotin T$?
– Michal Dvořák
Jul 26 at 8:20
2
$A$ is the set of such $x$, yes. The $x$ that are in $A$ are precisely the $x$ for which that is true.
– Mees de Vries
Jul 26 at 8:23
add a comment |Â
up vote
6
down vote
accepted
In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $psi$
No, this is not quite true. The construction is more subtle than that. For any $x in X$, the value $psi(x) in mathcal P(X)$ is some set -- a subset of $X$ to be precise. Note that this is not the range of $psi$, it is the value of $psi(x)$ for a single $x$.
Then we have either $x in psi(x)$ or $x notin psi(x)$, and we add $x$ to the set $A$ if and only if $x notin psi(x)$.
answered Jul 26 at 8:18
Mees de Vries
13.7k12345
So $A$ is the set for which the map $psi$ maps some $xin X$ to some say $Tin mathcalP(X)$ for which $xnotin T$?
– Michal Dvořák
Jul 26 at 8:20
2
$A$ is the set of such $x$, yes. The $x$ that are in $A$ are precisely the $x$ for which that is true.
– Mees de Vries
Jul 26 at 8:23
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $psi$
No, this is not quite true. The construction is more subtle than that. For any $x in X$, the value $psi(x) in mathcal P(X)$ is some set -- a subset of $X$ to be precise. Note that this is not the range of $psi$, it is the value of $psi(x)$ for a single $x$.
Then we have either $x in psi(x)$ or $x notin psi(x)$, and we add $x$ to the set $A$ if and only if $x notin psi(x)$.
answered Jul 26 at 8:18
Mees de Vries
13.7k12345
In the proof $A$ is supposed to be the set of all members of $X$ (thus numbers) that are not in the range of $psi$
No, this is not quite true. The construction is more subtle than that. For any $x in X$, the value $psi(x) in mathcal P(X)$ is some set -- a subset of $X$ to be precise. Note that this is not the range of $psi$, it is the value of $psi(x)$ for a single $x$.
Then we have either $x in psi(x)$ or $x notin psi(x)$, and we add $x$ to the set $A$ if and only if $x notin psi(x)$.
answered Jul 26 at 8:18
Mees de Vries
13.7k12345
answered Jul 26 at 8:18
Mees de Vries
13.7k12345
answered Jul 26 at 8:18
Mees de Vries
13.7k12345
answered Jul 26 at 8:18
Mees de Vries
13.7k12345
13.7k12345
So $A$ is the set for which the map $psi$ maps some $xin X$ to some say $Tin mathcalP(X)$ for which $xnotin T$?
– Michal Dvořák
Jul 26 at 8:20
2
$A$ is the set of such $x$, yes. The $x$ that are in $A$ are precisely the $x$ for which that is true.
– Mees de Vries
Jul 26 at 8:23
add a comment |Â
So $A$ is the set for which the map $psi$ maps some $xin X$ to some say $Tin mathcalP(X)$ for which $xnotin T$?
– Michal Dvořák
Jul 26 at 8:20
2
$A$ is the set of such $x$, yes. The $x$ that are in $A$ are precisely the $x$ for which that is true.
– Mees de Vries
Jul 26 at 8:23
So $A$ is the set for which the map $psi$ maps some $xin X$ to some say $Tin mathcalP(X)$ for which $xnotin T$?
– Michal Dvořák
Jul 26 at 8:20
So $A$ is the set for which the map $psi$ maps some $xin X$ to some say $Tin mathcalP(X)$ for which $xnotin T$?
– Michal Dvořák
Jul 26 at 8:20
2
2
$A$ is the set of such $x$, yes. The $x$ that are in $A$ are precisely the $x$ for which that is true.
– Mees de Vries
Jul 26 at 8:23
$A$ is the set of such $x$, yes. The $x$ that are in $A$ are precisely the $x$ for which that is true.
– Mees de Vries
Jul 26 at 8:23
add a comment |Â
up vote
3
down vote
That the specific mapping $ varphi$ is not surjective, hence not bijective, is clear.
To prove that $|X|<|mathcalP(X)|$ , it is enough to show that each(!) mapping $psi:XrightarrowmathcalP(X)$ cannot be surjective.
In the proof above it is assumed that there is a surjective mapping $psi:XrightarrowmathcalP(X)$ . But this leads to a contradiction....
answered Jul 26 at 8:13
Fred
37.2k1237
So, my proof cannot be legit, because I've only constructed "one" non-surjective mapping, which doesn't prove there isn't "any"?
– Michal Dvořák
Jul 26 at 8:15
1
@Michal Dvořák Right, you have to prove no mapping from $X$ to $mathcalP(X)$ can be surjective.
– Hanul Jeon
Jul 26 at 8:19
Without the axiom of choice it is possible that two sets have no surjections between them, but no injection either. To establish $<$ one has to establish an injection and no bijection (which follows from no surjection).
– Asaf Karagila
Jul 26 at 8:57
add a comment |Â
up vote
3
down vote
That the specific mapping $ varphi$ is not surjective, hence not bijective, is clear.
To prove that $|X|<|mathcalP(X)|$ , it is enough to show that each(!) mapping $psi:XrightarrowmathcalP(X)$ cannot be surjective.
In the proof above it is assumed that there is a surjective mapping $psi:XrightarrowmathcalP(X)$ . But this leads to a contradiction....
answered Jul 26 at 8:13
Fred
37.2k1237
So, my proof cannot be legit, because I've only constructed "one" non-surjective mapping, which doesn't prove there isn't "any"?
– Michal Dvořák
Jul 26 at 8:15
1
@Michal Dvořák Right, you have to prove no mapping from $X$ to $mathcalP(X)$ can be surjective.
– Hanul Jeon
Jul 26 at 8:19
Without the axiom of choice it is possible that two sets have no surjections between them, but no injection either. To establish $<$ one has to establish an injection and no bijection (which follows from no surjection).
– Asaf Karagila
Jul 26 at 8:57
add a comment |Â
up vote
3
down vote
up vote
3
down vote
That the specific mapping $ varphi$ is not surjective, hence not bijective, is clear.
To prove that $|X|<|mathcalP(X)|$ , it is enough to show that each(!) mapping $psi:XrightarrowmathcalP(X)$ cannot be surjective.
In the proof above it is assumed that there is a surjective mapping $psi:XrightarrowmathcalP(X)$ . But this leads to a contradiction....
answered Jul 26 at 8:13
Fred
37.2k1237
That the specific mapping $ varphi$ is not surjective, hence not bijective, is clear.
To prove that $|X|<|mathcalP(X)|$ , it is enough to show that each(!) mapping $psi:XrightarrowmathcalP(X)$ cannot be surjective.
In the proof above it is assumed that there is a surjective mapping $psi:XrightarrowmathcalP(X)$ . But this leads to a contradiction....
answered Jul 26 at 8:13
Fred
37.2k1237
answered Jul 26 at 8:13
Fred
37.2k1237
answered Jul 26 at 8:13
Fred
37.2k1237
answered Jul 26 at 8:13
Fred
37.2k1237
37.2k1237
So, my proof cannot be legit, because I've only constructed "one" non-surjective mapping, which doesn't prove there isn't "any"?
– Michal Dvořák
Jul 26 at 8:15
1
@Michal Dvořák Right, you have to prove no mapping from $X$ to $mathcalP(X)$ can be surjective.
– Hanul Jeon
Jul 26 at 8:19
Without the axiom of choice it is possible that two sets have no surjections between them, but no injection either. To establish $<$ one has to establish an injection and no bijection (which follows from no surjection).
– Asaf Karagila
Jul 26 at 8:57
add a comment |Â
So, my proof cannot be legit, because I've only constructed "one" non-surjective mapping, which doesn't prove there isn't "any"?
– Michal Dvořák
Jul 26 at 8:15
1
@Michal Dvořák Right, you have to prove no mapping from $X$ to $mathcalP(X)$ can be surjective.
– Hanul Jeon
Jul 26 at 8:19
Without the axiom of choice it is possible that two sets have no surjections between them, but no injection either. To establish $<$ one has to establish an injection and no bijection (which follows from no surjection).
– Asaf Karagila
Jul 26 at 8:57
So, my proof cannot be legit, because I've only constructed "one" non-surjective mapping, which doesn't prove there isn't "any"?
– Michal Dvořák
Jul 26 at 8:15
So, my proof cannot be legit, because I've only constructed "one" non-surjective mapping, which doesn't prove there isn't "any"?
– Michal Dvořák
Jul 26 at 8:15
1
1
@Michal Dvořák Right, you have to prove no mapping from $X$ to $mathcalP(X)$ can be surjective.
– Hanul Jeon
Jul 26 at 8:19
@Michal Dvořák Right, you have to prove no mapping from $X$ to $mathcalP(X)$ can be surjective.
– Hanul Jeon
Jul 26 at 8:19
Without the axiom of choice it is possible that two sets have no surjections between them, but no injection either. To establish $<$ one has to establish an injection and no bijection (which follows from no surjection).
– Asaf Karagila
Jul 26 at 8:57
Without the axiom of choice it is possible that two sets have no surjections between them, but no injection either. To establish $<$ one has to establish an injection and no bijection (which follows from no surjection).
– Asaf Karagila
Jul 26 at 8:57
add a comment |Â
up vote
1
down vote
Mees de Vries' answer gives an explanation of where your misunderstanding of the usual proof was.
To address your alternative proof attempt: you show that there is a particular injection from $X$ to $mathcalP(X)$, but that it's not surjective. This isn't enough to prove that $|X|<|mathcalP(X)|$. For example, we can define a function from $mathbb N$ to $mathbb Ntimes mathbb N$ by $varphi(n)=(n,1)$, which is injective but not surjective. However, $|mathbb N|=|mathbb Ntimes mathbb N|$ because other, more complicated, functions exist which are both injective and surjective (e.g. $psi(n)=(a,b)$ where $a,b$ are the unique positive integers such that $n=(2a-1)2^b-1$).
answered Jul 26 at 11:25
Especially Lime
19.1k22252
add a comment |Â
up vote
1
down vote
Mees de Vries' answer gives an explanation of where your misunderstanding of the usual proof was.
To address your alternative proof attempt: you show that there is a particular injection from $X$ to $mathcalP(X)$, but that it's not surjective. This isn't enough to prove that $|X|<|mathcalP(X)|$. For example, we can define a function from $mathbb N$ to $mathbb Ntimes mathbb N$ by $varphi(n)=(n,1)$, which is injective but not surjective. However, $|mathbb N|=|mathbb Ntimes mathbb N|$ because other, more complicated, functions exist which are both injective and surjective (e.g. $psi(n)=(a,b)$ where $a,b$ are the unique positive integers such that $n=(2a-1)2^b-1$).
answered Jul 26 at 11:25
Especially Lime
19.1k22252
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Mees de Vries' answer gives an explanation of where your misunderstanding of the usual proof was.
To address your alternative proof attempt: you show that there is a particular injection from $X$ to $mathcalP(X)$, but that it's not surjective. This isn't enough to prove that $|X|<|mathcalP(X)|$. For example, we can define a function from $mathbb N$ to $mathbb Ntimes mathbb N$ by $varphi(n)=(n,1)$, which is injective but not surjective. However, $|mathbb N|=|mathbb Ntimes mathbb N|$ because other, more complicated, functions exist which are both injective and surjective (e.g. $psi(n)=(a,b)$ where $a,b$ are the unique positive integers such that $n=(2a-1)2^b-1$).
answered Jul 26 at 11:25
Especially Lime
19.1k22252
Mees de Vries' answer gives an explanation of where your misunderstanding of the usual proof was.
To address your alternative proof attempt: you show that there is a particular injection from $X$ to $mathcalP(X)$, but that it's not surjective. This isn't enough to prove that $|X|<|mathcalP(X)|$. For example, we can define a function from $mathbb N$ to $mathbb Ntimes mathbb N$ by $varphi(n)=(n,1)$, which is injective but not surjective. However, $|mathbb N|=|mathbb Ntimes mathbb N|$ because other, more complicated, functions exist which are both injective and surjective (e.g. $psi(n)=(a,b)$ where $a,b$ are the unique positive integers such that $n=(2a-1)2^b-1$).
answered Jul 26 at 11:25
Especially Lime
19.1k22252
answered Jul 26 at 11:25
Especially Lime
19.1k22252
answered Jul 26 at 11:25
Especially Lime
19.1k22252
answered Jul 26 at 11:25
Especially Lime
19.1k22252
19.1k22252
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%2f2863179%2fexplanation-of-and-alternative-proof-for-cantors-theorem%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
2
"In the proof $A$ is supposed to be the set of all members of $X$ that are not in the range of $psi$" No, that's not what $A$ is supposed to be. If $xin X$ then $psi(x)$ is a subset of $X$ and $A$ is a subset of $X$; and $Anepsi(x)$ because the two sets, $A$ and $psi(x),$ differ at $x$; namely, $$xin Aiff xnotinpsi(x).$$
– bof
Jul 26 at 8:19
1
The definition of $A$ is a kind of diagonalization.
– Hanul Jeon
Jul 26 at 8:21