If $A$ is infinite, then $mathcalP(A)$ is uncountable
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Definition: A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable.
Theorem: if $A$ is an infinite set, then $mathcalP(A)$ is uncountable.
Cantor’s theorem: suppose that $f$ is a mapping from a set $A$ to its power set $mathcalP(A)$. Then $f$ is not surjective.
Lemma 1: assuming the Axiom of Dependent Choice, if $A$ is an
infinite set, then $A$ contains a countably infinite subset.
Lemma 2: $A$ is countable if and only if $A=emptyset$ or there exists a surjection from $mathbb N$ onto $A$.
The proof is quite short, but I'm not sure if I apply Lemmas correctly. Please help me check it out!
Proof: $A$ is an infinite set, then by Lemma 1 there exists a countably infinite subset $B$ of $A$. Thus there exists a bijection $g: mathbb N to B$. Assume the contrary that $mathcalP(A)$ is countable, then $mathcalP(B) subseteq mathcalP(A)$ is countable too. By Lemma 2, there exists a surjection $h: mathbb N to mathcalP(B)$. As a result, $h circ g^-1: B to mathcalP(B)$ is surjective. This contradicts Cantor's theorem. Hence $mathcalP(A)$ is uncountable.
elementary-set-theory proof-verification
asked Aug 30 at 3:04
Le Anh Dung
709419
 |Â
show 3 more comments
up vote
2
down vote
favorite
Definition: A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable.
Theorem: if $A$ is an infinite set, then $mathcalP(A)$ is uncountable.
Cantor’s theorem: suppose that $f$ is a mapping from a set $A$ to its power set $mathcalP(A)$. Then $f$ is not surjective.
Lemma 1: assuming the Axiom of Dependent Choice, if $A$ is an
infinite set, then $A$ contains a countably infinite subset.
Lemma 2: $A$ is countable if and only if $A=emptyset$ or there exists a surjection from $mathbb N$ onto $A$.
The proof is quite short, but I'm not sure if I apply Lemmas correctly. Please help me check it out!
Proof: $A$ is an infinite set, then by Lemma 1 there exists a countably infinite subset $B$ of $A$. Thus there exists a bijection $g: mathbb N to B$. Assume the contrary that $mathcalP(A)$ is countable, then $mathcalP(B) subseteq mathcalP(A)$ is countable too. By Lemma 2, there exists a surjection $h: mathbb N to mathcalP(B)$. As a result, $h circ g^-1: B to mathcalP(B)$ is surjective. This contradicts Cantor's theorem. Hence $mathcalP(A)$ is uncountable.
elementary-set-theory proof-verification
asked Aug 30 at 3:04
Le Anh Dung
709419
2
What is your definition of uncountable? Is it that it is strictly larger than $mathbb N$? If it simply means infinite and not countable (which is the standard usage), then it is easier to prove that if $mathcal P(A)$ is countable then in fact it is finite. This has the advantage of not using any form of the axiom of choice.
– Andrés E. Caicedo
Aug 30 at 3:14
1
You're already invoking Cantor's theorem, can't you just say $aleph_0 leq |A| < |mathcalP(A)|$?
– Guido A.
Aug 30 at 3:20
@AndrésE.Caicedo I'm quite interested in the proof of 'if $mathcalP(A)$ is countable then it is finite', would you mind giving a sketch of it?
– Guido A.
Aug 30 at 3:22
@AndrésE.Caicedo "A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable." I have edited my post to add this definition.
– Le Anh Dung
Aug 30 at 3:29
1
@LeAnhDung I think it looks fine :)
– Guido A.
Aug 30 at 3:47
 |Â
show 3 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Definition: A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable.
Theorem: if $A$ is an infinite set, then $mathcalP(A)$ is uncountable.
Cantor’s theorem: suppose that $f$ is a mapping from a set $A$ to its power set $mathcalP(A)$. Then $f$ is not surjective.
Lemma 1: assuming the Axiom of Dependent Choice, if $A$ is an
infinite set, then $A$ contains a countably infinite subset.
Lemma 2: $A$ is countable if and only if $A=emptyset$ or there exists a surjection from $mathbb N$ onto $A$.
The proof is quite short, but I'm not sure if I apply Lemmas correctly. Please help me check it out!
Proof: $A$ is an infinite set, then by Lemma 1 there exists a countably infinite subset $B$ of $A$. Thus there exists a bijection $g: mathbb N to B$. Assume the contrary that $mathcalP(A)$ is countable, then $mathcalP(B) subseteq mathcalP(A)$ is countable too. By Lemma 2, there exists a surjection $h: mathbb N to mathcalP(B)$. As a result, $h circ g^-1: B to mathcalP(B)$ is surjective. This contradicts Cantor's theorem. Hence $mathcalP(A)$ is uncountable.
elementary-set-theory proof-verification
asked Aug 30 at 3:04
Le Anh Dung
709419
Definition: A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable.
Theorem: if $A$ is an infinite set, then $mathcalP(A)$ is uncountable.
Cantor’s theorem: suppose that $f$ is a mapping from a set $A$ to its power set $mathcalP(A)$. Then $f$ is not surjective.
Lemma 1: assuming the Axiom of Dependent Choice, if $A$ is an
infinite set, then $A$ contains a countably infinite subset.
Lemma 2: $A$ is countable if and only if $A=emptyset$ or there exists a surjection from $mathbb N$ onto $A$.
The proof is quite short, but I'm not sure if I apply Lemmas correctly. Please help me check it out!
Proof: $A$ is an infinite set, then by Lemma 1 there exists a countably infinite subset $B$ of $A$. Thus there exists a bijection $g: mathbb N to B$. Assume the contrary that $mathcalP(A)$ is countable, then $mathcalP(B) subseteq mathcalP(A)$ is countable too. By Lemma 2, there exists a surjection $h: mathbb N to mathcalP(B)$. As a result, $h circ g^-1: B to mathcalP(B)$ is surjective. This contradicts Cantor's theorem. Hence $mathcalP(A)$ is uncountable.
elementary-set-theory proof-verification
elementary-set-theory proof-verification
asked Aug 30 at 3:04
Le Anh Dung
709419
asked Aug 30 at 3:04
Le Anh Dung
709419
edited Aug 31 at 12:00
asked Aug 30 at 3:04
Le Anh Dung
709419
asked Aug 30 at 3:04
Le Anh Dung
709419
asked Aug 30 at 3:04
Le Anh Dung
709419
709419
2
What is your definition of uncountable? Is it that it is strictly larger than $mathbb N$? If it simply means infinite and not countable (which is the standard usage), then it is easier to prove that if $mathcal P(A)$ is countable then in fact it is finite. This has the advantage of not using any form of the axiom of choice.
– Andrés E. Caicedo
Aug 30 at 3:14
1
You're already invoking Cantor's theorem, can't you just say $aleph_0 leq |A| < |mathcalP(A)|$?
– Guido A.
Aug 30 at 3:20
@AndrésE.Caicedo I'm quite interested in the proof of 'if $mathcalP(A)$ is countable then it is finite', would you mind giving a sketch of it?
– Guido A.
Aug 30 at 3:22
@AndrésE.Caicedo "A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable." I have edited my post to add this definition.
– Le Anh Dung
Aug 30 at 3:29
1
@LeAnhDung I think it looks fine :)
– Guido A.
Aug 30 at 3:47
 |Â
show 3 more comments
2
What is your definition of uncountable? Is it that it is strictly larger than $mathbb N$? If it simply means infinite and not countable (which is the standard usage), then it is easier to prove that if $mathcal P(A)$ is countable then in fact it is finite. This has the advantage of not using any form of the axiom of choice.
– Andrés E. Caicedo
Aug 30 at 3:14
1
You're already invoking Cantor's theorem, can't you just say $aleph_0 leq |A| < |mathcalP(A)|$?
– Guido A.
Aug 30 at 3:20
@AndrésE.Caicedo I'm quite interested in the proof of 'if $mathcalP(A)$ is countable then it is finite', would you mind giving a sketch of it?
– Guido A.
Aug 30 at 3:22
@AndrésE.Caicedo "A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable." I have edited my post to add this definition.
– Le Anh Dung
Aug 30 at 3:29
1
@LeAnhDung I think it looks fine :)
– Guido A.
Aug 30 at 3:47
2
2
What is your definition of uncountable? Is it that it is strictly larger than $mathbb N$? If it simply means infinite and not countable (which is the standard usage), then it is easier to prove that if $mathcal P(A)$ is countable then in fact it is finite. This has the advantage of not using any form of the axiom of choice.
– Andrés E. Caicedo
Aug 30 at 3:14
What is your definition of uncountable? Is it that it is strictly larger than $mathbb N$? If it simply means infinite and not countable (which is the standard usage), then it is easier to prove that if $mathcal P(A)$ is countable then in fact it is finite. This has the advantage of not using any form of the axiom of choice.
– Andrés E. Caicedo
Aug 30 at 3:14
1
1
You're already invoking Cantor's theorem, can't you just say $aleph_0 leq |A| < |mathcalP(A)|$?
– Guido A.
Aug 30 at 3:20
You're already invoking Cantor's theorem, can't you just say $aleph_0 leq |A| < |mathcalP(A)|$?
– Guido A.
Aug 30 at 3:20
@AndrésE.Caicedo I'm quite interested in the proof of 'if $mathcalP(A)$ is countable then it is finite', would you mind giving a sketch of it?
– Guido A.
Aug 30 at 3:22
@AndrésE.Caicedo I'm quite interested in the proof of 'if $mathcalP(A)$ is countable then it is finite', would you mind giving a sketch of it?
– Guido A.
Aug 30 at 3:22
@AndrésE.Caicedo "A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable." I have edited my post to add this definition.
– Le Anh Dung
Aug 30 at 3:29
@AndrésE.Caicedo "A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable." I have edited my post to add this definition.
– Le Anh Dung
Aug 30 at 3:29
1
1
@LeAnhDung I think it looks fine :)
– Guido A.
Aug 30 at 3:47
@LeAnhDung I think it looks fine :)
– Guido A.
Aug 30 at 3:47
 |Â
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Let $A$ be an infinite set.
It is well known that we can find an injection $mathbbN to A$. Hence, $|mathbbN| leq |A|$ and it follows that $$|mathbbN| <|mathcalP(mathbbN)| leq |mathcalP(A)|$$
by Cantor's theorem.
answered Aug 31 at 12:27
Math_QED
6,57431345
I think we need countable choice for the injection $mathbbN to A$ though.
– Math_QED
Aug 31 at 12:29
Of course, we do ^^
– Le Anh Dung
Aug 31 at 12:31
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Let $A$ be an infinite set.
It is well known that we can find an injection $mathbbN to A$. Hence, $|mathbbN| leq |A|$ and it follows that $$|mathbbN| <|mathcalP(mathbbN)| leq |mathcalP(A)|$$
by Cantor's theorem.
answered Aug 31 at 12:27
Math_QED
6,57431345
I think we need countable choice for the injection $mathbbN to A$ though.
– Math_QED
Aug 31 at 12:29
Of course, we do ^^
– Le Anh Dung
Aug 31 at 12:31
add a comment |Â
up vote
1
down vote
accepted
Let $A$ be an infinite set.
It is well known that we can find an injection $mathbbN to A$. Hence, $|mathbbN| leq |A|$ and it follows that $$|mathbbN| <|mathcalP(mathbbN)| leq |mathcalP(A)|$$
by Cantor's theorem.
answered Aug 31 at 12:27
Math_QED
6,57431345
I think we need countable choice for the injection $mathbbN to A$ though.
– Math_QED
Aug 31 at 12:29
Of course, we do ^^
– Le Anh Dung
Aug 31 at 12:31
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Let $A$ be an infinite set.
It is well known that we can find an injection $mathbbN to A$. Hence, $|mathbbN| leq |A|$ and it follows that $$|mathbbN| <|mathcalP(mathbbN)| leq |mathcalP(A)|$$
by Cantor's theorem.
answered Aug 31 at 12:27
Math_QED
6,57431345
Let $A$ be an infinite set.
It is well known that we can find an injection $mathbbN to A$. Hence, $|mathbbN| leq |A|$ and it follows that $$|mathbbN| <|mathcalP(mathbbN)| leq |mathcalP(A)|$$
by Cantor's theorem.
answered Aug 31 at 12:27
Math_QED
6,57431345
answered Aug 31 at 12:27
Math_QED
6,57431345
answered Aug 31 at 12:27
Math_QED
6,57431345
answered Aug 31 at 12:27
Math_QED
6,57431345
6,57431345
I think we need countable choice for the injection $mathbbN to A$ though.
– Math_QED
Aug 31 at 12:29
Of course, we do ^^
– Le Anh Dung
Aug 31 at 12:31
add a comment |Â
I think we need countable choice for the injection $mathbbN to A$ though.
– Math_QED
Aug 31 at 12:29
Of course, we do ^^
– Le Anh Dung
Aug 31 at 12:31
I think we need countable choice for the injection $mathbbN to A$ though.
– Math_QED
Aug 31 at 12:29
I think we need countable choice for the injection $mathbbN to A$ though.
– Math_QED
Aug 31 at 12:29
Of course, we do ^^
– Le Anh Dung
Aug 31 at 12:31
Of course, we do ^^
– Le Anh Dung
Aug 31 at 12:31
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%2f2899063%2fif-a-is-infinite-then-mathcalpa-is-uncountable%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
What is your definition of uncountable? Is it that it is strictly larger than $mathbb N$? If it simply means infinite and not countable (which is the standard usage), then it is easier to prove that if $mathcal P(A)$ is countable then in fact it is finite. This has the advantage of not using any form of the axiom of choice.
– Andrés E. Caicedo
Aug 30 at 3:14
1
You're already invoking Cantor's theorem, can't you just say $aleph_0 leq |A| < |mathcalP(A)|$?
– Guido A.
Aug 30 at 3:20
@AndrésE.Caicedo I'm quite interested in the proof of 'if $mathcalP(A)$ is countable then it is finite', would you mind giving a sketch of it?
– Guido A.
Aug 30 at 3:22
@AndrésE.Caicedo "A set $A$ is countable if it is finite or if there is a bijection $c: mathbb N to A$; otherwise it is uncountable." I have edited my post to add this definition.
– Le Anh Dung
Aug 30 at 3:29
1
@LeAnhDung I think it looks fine :)
– Guido A.
Aug 30 at 3:47