Problem understanding the Cantor Theorem's proof
$begingroup$
I can intuitevely picture the power set of A to be of a greater cardinality than A, as it permits multiple combinations of elements of A. However, I couldn't understand the usual proof that comes with the theorem. I tried looking for other proofs but couldn't find any. The proof assumes that in any bijective function f we choose, there's going to be elements of A that map into subsets they're not member of in P(A). And then we would use these as a contradiction.
My problem is the following: what if we choose a function f such that elements of A only map into subsets they're member of? Is this possible? Am I missing something? Wouldn't the proof fail with this kind of, but my understanding is that this f shouldn't exist, then why?
Thank you!
discrete-mathematics elementary-set-theory
asked Jan 21 at 0:51
bluemusebluemuse
976
$endgroup$
|
show 3 more comments
$begingroup$
I can intuitevely picture the power set of A to be of a greater cardinality than A, as it permits multiple combinations of elements of A. However, I couldn't understand the usual proof that comes with the theorem. I tried looking for other proofs but couldn't find any. The proof assumes that in any bijective function f we choose, there's going to be elements of A that map into subsets they're not member of in P(A). And then we would use these as a contradiction.
My problem is the following: what if we choose a function f such that elements of A only map into subsets they're member of? Is this possible? Am I missing something? Wouldn't the proof fail with this kind of, but my understanding is that this f shouldn't exist, then why?
Thank you!
discrete-mathematics elementary-set-theory
asked Jan 21 at 0:51
bluemusebluemuse
976
$endgroup$
$begingroup$
I've never seen a proof like the one you describe. (Where did you find it?) The usual proof shows that, given any function $f:Ato P(A)$, we can find an element of $P(A)$ which is not in the range of $f$.
$endgroup$
– bof
Jan 21 at 1:03
$begingroup$
To do that, don't we usually define $B = { x in A | x notin f(x) } $ ?
$endgroup$
– bluemuse
Jan 21 at 1:09
$begingroup$
Indeed, so $B$ is an element of $P(A)$ which is not in the range of $f$. In your question you alleged that we find some element of $A$ with some funny property.
$endgroup$
– bof
Jan 21 at 1:16
$begingroup$
Are you confusing elements with subsets? $B$ is a subset of $A$, which makes it an element of $P(A)$.
$endgroup$
– bof
Jan 21 at 1:21
$begingroup$
But what if we choose an f such that B is empty? I mean an f such that elements of A always map into subsets containing them so the property of B ( $ x notin f(x) $ ) is not possible? Yes I might be confusing a lot of stuff here because everyone seems to understand this besides me
$endgroup$
– bluemuse
Jan 21 at 1:24
|
show 3 more comments
$begingroup$
I can intuitevely picture the power set of A to be of a greater cardinality than A, as it permits multiple combinations of elements of A. However, I couldn't understand the usual proof that comes with the theorem. I tried looking for other proofs but couldn't find any. The proof assumes that in any bijective function f we choose, there's going to be elements of A that map into subsets they're not member of in P(A). And then we would use these as a contradiction.
My problem is the following: what if we choose a function f such that elements of A only map into subsets they're member of? Is this possible? Am I missing something? Wouldn't the proof fail with this kind of, but my understanding is that this f shouldn't exist, then why?
Thank you!
discrete-mathematics elementary-set-theory
asked Jan 21 at 0:51
bluemusebluemuse
976
$endgroup$
I can intuitevely picture the power set of A to be of a greater cardinality than A, as it permits multiple combinations of elements of A. However, I couldn't understand the usual proof that comes with the theorem. I tried looking for other proofs but couldn't find any. The proof assumes that in any bijective function f we choose, there's going to be elements of A that map into subsets they're not member of in P(A). And then we would use these as a contradiction.
My problem is the following: what if we choose a function f such that elements of A only map into subsets they're member of? Is this possible? Am I missing something? Wouldn't the proof fail with this kind of, but my understanding is that this f shouldn't exist, then why?
Thank you!
discrete-mathematics elementary-set-theory
discrete-mathematics elementary-set-theory
asked Jan 21 at 0:51
bluemusebluemuse
976
asked Jan 21 at 0:51
bluemusebluemuse
976
asked Jan 21 at 0:51
bluemusebluemuse
976
asked Jan 21 at 0:51
bluemusebluemuse
976
asked Jan 21 at 0:51
bluemusebluemuse
976
976
$begingroup$
I've never seen a proof like the one you describe. (Where did you find it?) The usual proof shows that, given any function $f:Ato P(A)$, we can find an element of $P(A)$ which is not in the range of $f$.
$endgroup$
– bof
Jan 21 at 1:03
$begingroup$
To do that, don't we usually define $B = { x in A | x notin f(x) } $ ?
$endgroup$
– bluemuse
Jan 21 at 1:09
$begingroup$
Indeed, so $B$ is an element of $P(A)$ which is not in the range of $f$. In your question you alleged that we find some element of $A$ with some funny property.
$endgroup$
– bof
Jan 21 at 1:16
$begingroup$
Are you confusing elements with subsets? $B$ is a subset of $A$, which makes it an element of $P(A)$.
$endgroup$
– bof
Jan 21 at 1:21
$begingroup$
But what if we choose an f such that B is empty? I mean an f such that elements of A always map into subsets containing them so the property of B ( $ x notin f(x) $ ) is not possible? Yes I might be confusing a lot of stuff here because everyone seems to understand this besides me
$endgroup$
– bluemuse
Jan 21 at 1:24
|
show 3 more comments
$begingroup$
I've never seen a proof like the one you describe. (Where did you find it?) The usual proof shows that, given any function $f:Ato P(A)$, we can find an element of $P(A)$ which is not in the range of $f$.
$endgroup$
– bof
Jan 21 at 1:03
$begingroup$
To do that, don't we usually define $B = { x in A | x notin f(x) } $ ?
$endgroup$
– bluemuse
Jan 21 at 1:09
$begingroup$
Indeed, so $B$ is an element of $P(A)$ which is not in the range of $f$. In your question you alleged that we find some element of $A$ with some funny property.
$endgroup$
– bof
Jan 21 at 1:16
$begingroup$
Are you confusing elements with subsets? $B$ is a subset of $A$, which makes it an element of $P(A)$.
$endgroup$
– bof
Jan 21 at 1:21
$begingroup$
But what if we choose an f such that B is empty? I mean an f such that elements of A always map into subsets containing them so the property of B ( $ x notin f(x) $ ) is not possible? Yes I might be confusing a lot of stuff here because everyone seems to understand this besides me
$endgroup$
– bluemuse
Jan 21 at 1:24
$begingroup$
I've never seen a proof like the one you describe. (Where did you find it?) The usual proof shows that, given any function $f:Ato P(A)$, we can find an element of $P(A)$ which is not in the range of $f$.
$endgroup$
– bof
Jan 21 at 1:03
$begingroup$
I've never seen a proof like the one you describe. (Where did you find it?) The usual proof shows that, given any function $f:Ato P(A)$, we can find an element of $P(A)$ which is not in the range of $f$.
$endgroup$
– bof
Jan 21 at 1:03
$begingroup$
To do that, don't we usually define $B = { x in A | x notin f(x) } $ ?
$endgroup$
– bluemuse
Jan 21 at 1:09
$begingroup$
To do that, don't we usually define $B = { x in A | x notin f(x) } $ ?
$endgroup$
– bluemuse
Jan 21 at 1:09
$begingroup$
Indeed, so $B$ is an element of $P(A)$ which is not in the range of $f$. In your question you alleged that we find some element of $A$ with some funny property.
$endgroup$
– bof
Jan 21 at 1:16
$begingroup$
Indeed, so $B$ is an element of $P(A)$ which is not in the range of $f$. In your question you alleged that we find some element of $A$ with some funny property.
$endgroup$
– bof
Jan 21 at 1:16
$begingroup$
Are you confusing elements with subsets? $B$ is a subset of $A$, which makes it an element of $P(A)$.
$endgroup$
– bof
Jan 21 at 1:21
$begingroup$
Are you confusing elements with subsets? $B$ is a subset of $A$, which makes it an element of $P(A)$.
$endgroup$
– bof
Jan 21 at 1:21
$begingroup$
But what if we choose an f such that B is empty? I mean an f such that elements of A always map into subsets containing them so the property of B ( $ x notin f(x) $ ) is not possible? Yes I might be confusing a lot of stuff here because everyone seems to understand this besides me
$endgroup$
– bluemuse
Jan 21 at 1:24
$begingroup$
But what if we choose an f such that B is empty? I mean an f such that elements of A always map into subsets containing them so the property of B ( $ x notin f(x) $ ) is not possible? Yes I might be confusing a lot of stuff here because everyone seems to understand this besides me
$endgroup$
– bluemuse
Jan 21 at 1:24
|
show 3 more comments
3 Answers
3
active
oldest
votes
$begingroup$
That's not what Cantor's diagonal argument says. What it says? We take a function from $A$ to $P(A)$. Then, for each element $x$ of $A$, we ask a question - is $x$ an element of $f(x)$? Construct a new set $Bsubset A$ as follows; its elements are precisely those $x$ for which we answered no. In other words, $xin B$ if $xnotin f(x)$ and $xnotin B$ if $xin f(x)$. This $B$ is a subset of $A$, so it's in $P(A)$. We then argue that it can't be in the image of $f$. If $yin B$, $ynotin f(y)$ by the definition of $B$, and $Bneq f(y)$. If $ynotin B$, $yin f(y)$ by the definition of $B$, and $Bneq f(y)$. Repeat over all $y$, and $B$ isn't in the image of $f$.
So, what if we choose $f$ such that $xin f(x)$ for all $xin A$? Then $B$ is empty, and it's not in the image of $f$ - because everything in the image of $f$ has at least one element.
answered Jan 21 at 1:10
jmerryjmerry
9,8481225
$endgroup$
$begingroup$
This makes things a lot clearer! thank you!
$endgroup$
– bluemuse
Jan 21 at 1:26
add a comment |
$begingroup$
The proof I know goes as follows; Assume we have a Set A and a bijection f from A onto P(A). Now given this (fixed) bijection we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves. Now there must be some element of A which is projected onto that subset since f is bijective. It can now be shown that this element is both a member and not a member of said subset, which is a contradiction.
answered Jan 21 at 1:12
Jagol95Jagol95
1637
$endgroup$
$begingroup$
Right, but $f$ doesn't have to be a bijection, just a surjection. The proof shows that there is no surjection from $A$ to $P(A)$.
$endgroup$
– bof
Jan 21 at 1:19
$begingroup$
" we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves " this is exactly my question, how do we know such subset exists?
$endgroup$
– bluemuse
Jan 21 at 1:21
1
$begingroup$
@bluemuse Take for example the set of all integers which contain a seven. The set exists since for any integer we can clearly decide if it's a member of the set or not. The same principle is applied here.
$endgroup$
– Jagol95
Jan 21 at 1:29
1
$begingroup$
@bluemuse we are not assuming that this set is nonempty
$endgroup$
– Jagol95
Jan 21 at 1:35
add a comment |
$begingroup$
No, nothing goes wrong if we use such a map as our listing.
For example, one such map - arguably the simplest - is $$f:Arightarrow P(A):amapsto{a}.$$ The "antidiagonal set" associated to $f$ is $$Cantor(f)={a:anotin f(a)}={a:anotin{a}}=emptyset.$$ But this is fine: $Cantor(f)$ is indeed a subset of $A$, and it is indeed not in the range of $f$. So nothing's gone wrong.
answered Jan 21 at 1:16
Noah SchweberNoah Schweber
125k10150287
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3081354%2fproblem-understanding-the-cantor-theorems-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
That's not what Cantor's diagonal argument says. What it says? We take a function from $A$ to $P(A)$. Then, for each element $x$ of $A$, we ask a question - is $x$ an element of $f(x)$? Construct a new set $Bsubset A$ as follows; its elements are precisely those $x$ for which we answered no. In other words, $xin B$ if $xnotin f(x)$ and $xnotin B$ if $xin f(x)$. This $B$ is a subset of $A$, so it's in $P(A)$. We then argue that it can't be in the image of $f$. If $yin B$, $ynotin f(y)$ by the definition of $B$, and $Bneq f(y)$. If $ynotin B$, $yin f(y)$ by the definition of $B$, and $Bneq f(y)$. Repeat over all $y$, and $B$ isn't in the image of $f$.
So, what if we choose $f$ such that $xin f(x)$ for all $xin A$? Then $B$ is empty, and it's not in the image of $f$ - because everything in the image of $f$ has at least one element.
answered Jan 21 at 1:10
jmerryjmerry
9,8481225
$endgroup$
$begingroup$
This makes things a lot clearer! thank you!
$endgroup$
– bluemuse
Jan 21 at 1:26
add a comment |
$begingroup$
That's not what Cantor's diagonal argument says. What it says? We take a function from $A$ to $P(A)$. Then, for each element $x$ of $A$, we ask a question - is $x$ an element of $f(x)$? Construct a new set $Bsubset A$ as follows; its elements are precisely those $x$ for which we answered no. In other words, $xin B$ if $xnotin f(x)$ and $xnotin B$ if $xin f(x)$. This $B$ is a subset of $A$, so it's in $P(A)$. We then argue that it can't be in the image of $f$. If $yin B$, $ynotin f(y)$ by the definition of $B$, and $Bneq f(y)$. If $ynotin B$, $yin f(y)$ by the definition of $B$, and $Bneq f(y)$. Repeat over all $y$, and $B$ isn't in the image of $f$.
So, what if we choose $f$ such that $xin f(x)$ for all $xin A$? Then $B$ is empty, and it's not in the image of $f$ - because everything in the image of $f$ has at least one element.
answered Jan 21 at 1:10
jmerryjmerry
9,8481225
$endgroup$
$begingroup$
This makes things a lot clearer! thank you!
$endgroup$
– bluemuse
Jan 21 at 1:26
add a comment |
$begingroup$
That's not what Cantor's diagonal argument says. What it says? We take a function from $A$ to $P(A)$. Then, for each element $x$ of $A$, we ask a question - is $x$ an element of $f(x)$? Construct a new set $Bsubset A$ as follows; its elements are precisely those $x$ for which we answered no. In other words, $xin B$ if $xnotin f(x)$ and $xnotin B$ if $xin f(x)$. This $B$ is a subset of $A$, so it's in $P(A)$. We then argue that it can't be in the image of $f$. If $yin B$, $ynotin f(y)$ by the definition of $B$, and $Bneq f(y)$. If $ynotin B$, $yin f(y)$ by the definition of $B$, and $Bneq f(y)$. Repeat over all $y$, and $B$ isn't in the image of $f$.
So, what if we choose $f$ such that $xin f(x)$ for all $xin A$? Then $B$ is empty, and it's not in the image of $f$ - because everything in the image of $f$ has at least one element.
answered Jan 21 at 1:10
jmerryjmerry
9,8481225
$endgroup$
That's not what Cantor's diagonal argument says. What it says? We take a function from $A$ to $P(A)$. Then, for each element $x$ of $A$, we ask a question - is $x$ an element of $f(x)$? Construct a new set $Bsubset A$ as follows; its elements are precisely those $x$ for which we answered no. In other words, $xin B$ if $xnotin f(x)$ and $xnotin B$ if $xin f(x)$. This $B$ is a subset of $A$, so it's in $P(A)$. We then argue that it can't be in the image of $f$. If $yin B$, $ynotin f(y)$ by the definition of $B$, and $Bneq f(y)$. If $ynotin B$, $yin f(y)$ by the definition of $B$, and $Bneq f(y)$. Repeat over all $y$, and $B$ isn't in the image of $f$.
So, what if we choose $f$ such that $xin f(x)$ for all $xin A$? Then $B$ is empty, and it's not in the image of $f$ - because everything in the image of $f$ has at least one element.
answered Jan 21 at 1:10
jmerryjmerry
9,8481225
answered Jan 21 at 1:10
jmerryjmerry
9,8481225
answered Jan 21 at 1:10
jmerryjmerry
9,8481225
answered Jan 21 at 1:10
jmerryjmerry
9,8481225
9,8481225
$begingroup$
This makes things a lot clearer! thank you!
$endgroup$
– bluemuse
Jan 21 at 1:26
add a comment |
$begingroup$
This makes things a lot clearer! thank you!
$endgroup$
– bluemuse
Jan 21 at 1:26
$begingroup$
This makes things a lot clearer! thank you!
$endgroup$
– bluemuse
Jan 21 at 1:26
$begingroup$
This makes things a lot clearer! thank you!
$endgroup$
– bluemuse
Jan 21 at 1:26
add a comment |
$begingroup$
The proof I know goes as follows; Assume we have a Set A and a bijection f from A onto P(A). Now given this (fixed) bijection we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves. Now there must be some element of A which is projected onto that subset since f is bijective. It can now be shown that this element is both a member and not a member of said subset, which is a contradiction.
answered Jan 21 at 1:12
Jagol95Jagol95
1637
$endgroup$
$begingroup$
Right, but $f$ doesn't have to be a bijection, just a surjection. The proof shows that there is no surjection from $A$ to $P(A)$.
$endgroup$
– bof
Jan 21 at 1:19
$begingroup$
" we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves " this is exactly my question, how do we know such subset exists?
$endgroup$
– bluemuse
Jan 21 at 1:21
1
$begingroup$
@bluemuse Take for example the set of all integers which contain a seven. The set exists since for any integer we can clearly decide if it's a member of the set or not. The same principle is applied here.
$endgroup$
– Jagol95
Jan 21 at 1:29
1
$begingroup$
@bluemuse we are not assuming that this set is nonempty
$endgroup$
– Jagol95
Jan 21 at 1:35
add a comment |
$begingroup$
The proof I know goes as follows; Assume we have a Set A and a bijection f from A onto P(A). Now given this (fixed) bijection we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves. Now there must be some element of A which is projected onto that subset since f is bijective. It can now be shown that this element is both a member and not a member of said subset, which is a contradiction.
answered Jan 21 at 1:12
Jagol95Jagol95
1637
$endgroup$
$begingroup$
Right, but $f$ doesn't have to be a bijection, just a surjection. The proof shows that there is no surjection from $A$ to $P(A)$.
$endgroup$
– bof
Jan 21 at 1:19
$begingroup$
" we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves " this is exactly my question, how do we know such subset exists?
$endgroup$
– bluemuse
Jan 21 at 1:21
1
$begingroup$
@bluemuse Take for example the set of all integers which contain a seven. The set exists since for any integer we can clearly decide if it's a member of the set or not. The same principle is applied here.
$endgroup$
– Jagol95
Jan 21 at 1:29
1
$begingroup$
@bluemuse we are not assuming that this set is nonempty
$endgroup$
– Jagol95
Jan 21 at 1:35
add a comment |
$begingroup$
The proof I know goes as follows; Assume we have a Set A and a bijection f from A onto P(A). Now given this (fixed) bijection we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves. Now there must be some element of A which is projected onto that subset since f is bijective. It can now be shown that this element is both a member and not a member of said subset, which is a contradiction.
answered Jan 21 at 1:12
Jagol95Jagol95
1637
$endgroup$
The proof I know goes as follows; Assume we have a Set A and a bijection f from A onto P(A). Now given this (fixed) bijection we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves. Now there must be some element of A which is projected onto that subset since f is bijective. It can now be shown that this element is both a member and not a member of said subset, which is a contradiction.
answered Jan 21 at 1:12
Jagol95Jagol95
1637
answered Jan 21 at 1:12
Jagol95Jagol95
1637
answered Jan 21 at 1:12
Jagol95Jagol95
1637
answered Jan 21 at 1:12
Jagol95Jagol95
1637
1637
$begingroup$
Right, but $f$ doesn't have to be a bijection, just a surjection. The proof shows that there is no surjection from $A$ to $P(A)$.
$endgroup$
– bof
Jan 21 at 1:19
$begingroup$
" we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves " this is exactly my question, how do we know such subset exists?
$endgroup$
– bluemuse
Jan 21 at 1:21
1
$begingroup$
@bluemuse Take for example the set of all integers which contain a seven. The set exists since for any integer we can clearly decide if it's a member of the set or not. The same principle is applied here.
$endgroup$
– Jagol95
Jan 21 at 1:29
1
$begingroup$
@bluemuse we are not assuming that this set is nonempty
$endgroup$
– Jagol95
Jan 21 at 1:35
add a comment |
$begingroup$
Right, but $f$ doesn't have to be a bijection, just a surjection. The proof shows that there is no surjection from $A$ to $P(A)$.
$endgroup$
– bof
Jan 21 at 1:19
$begingroup$
" we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves " this is exactly my question, how do we know such subset exists?
$endgroup$
– bluemuse
Jan 21 at 1:21
1
$begingroup$
@bluemuse Take for example the set of all integers which contain a seven. The set exists since for any integer we can clearly decide if it's a member of the set or not. The same principle is applied here.
$endgroup$
– Jagol95
Jan 21 at 1:29
1
$begingroup$
@bluemuse we are not assuming that this set is nonempty
$endgroup$
– Jagol95
Jan 21 at 1:35
$begingroup$
Right, but $f$ doesn't have to be a bijection, just a surjection. The proof shows that there is no surjection from $A$ to $P(A)$.
$endgroup$
– bof
Jan 21 at 1:19
$begingroup$
Right, but $f$ doesn't have to be a bijection, just a surjection. The proof shows that there is no surjection from $A$ to $P(A)$.
$endgroup$
– bof
Jan 21 at 1:19
$begingroup$
" we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves " this is exactly my question, how do we know such subset exists?
$endgroup$
– bluemuse
Jan 21 at 1:21
$begingroup$
" we may determine the subset of Elements of A whose projection( some subset of A) does not include themselves " this is exactly my question, how do we know such subset exists?
$endgroup$
– bluemuse
Jan 21 at 1:21
1
1
$begingroup$
@bluemuse Take for example the set of all integers which contain a seven. The set exists since for any integer we can clearly decide if it's a member of the set or not. The same principle is applied here.
$endgroup$
– Jagol95
Jan 21 at 1:29
$begingroup$
@bluemuse Take for example the set of all integers which contain a seven. The set exists since for any integer we can clearly decide if it's a member of the set or not. The same principle is applied here.
$endgroup$
– Jagol95
Jan 21 at 1:29
1
1
$begingroup$
@bluemuse we are not assuming that this set is nonempty
$endgroup$
– Jagol95
Jan 21 at 1:35
$begingroup$
@bluemuse we are not assuming that this set is nonempty
$endgroup$
– Jagol95
Jan 21 at 1:35
add a comment |
$begingroup$
No, nothing goes wrong if we use such a map as our listing.
For example, one such map - arguably the simplest - is $$f:Arightarrow P(A):amapsto{a}.$$ The "antidiagonal set" associated to $f$ is $$Cantor(f)={a:anotin f(a)}={a:anotin{a}}=emptyset.$$ But this is fine: $Cantor(f)$ is indeed a subset of $A$, and it is indeed not in the range of $f$. So nothing's gone wrong.
answered Jan 21 at 1:16
Noah SchweberNoah Schweber
125k10150287
$endgroup$
add a comment |
$begingroup$
No, nothing goes wrong if we use such a map as our listing.
For example, one such map - arguably the simplest - is $$f:Arightarrow P(A):amapsto{a}.$$ The "antidiagonal set" associated to $f$ is $$Cantor(f)={a:anotin f(a)}={a:anotin{a}}=emptyset.$$ But this is fine: $Cantor(f)$ is indeed a subset of $A$, and it is indeed not in the range of $f$. So nothing's gone wrong.
answered Jan 21 at 1:16
Noah SchweberNoah Schweber
125k10150287
$endgroup$
add a comment |
$begingroup$
No, nothing goes wrong if we use such a map as our listing.
For example, one such map - arguably the simplest - is $$f:Arightarrow P(A):amapsto{a}.$$ The "antidiagonal set" associated to $f$ is $$Cantor(f)={a:anotin f(a)}={a:anotin{a}}=emptyset.$$ But this is fine: $Cantor(f)$ is indeed a subset of $A$, and it is indeed not in the range of $f$. So nothing's gone wrong.
answered Jan 21 at 1:16
Noah SchweberNoah Schweber
125k10150287
$endgroup$
No, nothing goes wrong if we use such a map as our listing.
For example, one such map - arguably the simplest - is $$f:Arightarrow P(A):amapsto{a}.$$ The "antidiagonal set" associated to $f$ is $$Cantor(f)={a:anotin f(a)}={a:anotin{a}}=emptyset.$$ But this is fine: $Cantor(f)$ is indeed a subset of $A$, and it is indeed not in the range of $f$. So nothing's gone wrong.
answered Jan 21 at 1:16
Noah SchweberNoah Schweber
125k10150287
answered Jan 21 at 1:16
Noah SchweberNoah Schweber
125k10150287
answered Jan 21 at 1:16
Noah SchweberNoah Schweber
125k10150287
answered Jan 21 at 1:16
Noah SchweberNoah Schweber
125k10150287
125k10150287
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3081354%2fproblem-understanding-the-cantor-theorems-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I've never seen a proof like the one you describe. (Where did you find it?) The usual proof shows that, given any function $f:Ato P(A)$, we can find an element of $P(A)$ which is not in the range of $f$.
$endgroup$
– bof
Jan 21 at 1:03
$begingroup$
To do that, don't we usually define $B = { x in A | x notin f(x) } $ ?
$endgroup$
– bluemuse
Jan 21 at 1:09
$begingroup$
Indeed, so $B$ is an element of $P(A)$ which is not in the range of $f$. In your question you alleged that we find some element of $A$ with some funny property.
$endgroup$
– bof
Jan 21 at 1:16
$begingroup$
Are you confusing elements with subsets? $B$ is a subset of $A$, which makes it an element of $P(A)$.
$endgroup$
– bof
Jan 21 at 1:21
$begingroup$
But what if we choose an f such that B is empty? I mean an f such that elements of A always map into subsets containing them so the property of B ( $ x notin f(x) $ ) is not possible? Yes I might be confusing a lot of stuff here because everyone seems to understand this besides me
$endgroup$
– bluemuse
Jan 21 at 1:24