Mixing
How does my bijection between the natural numbers and the powerset of natural numbers break down? [duplicate]
$begingroup$
This question already has an answer here:
Why doesn't Cantor's diagonal argument also apply to natural numbers?
2 answers
Lets consider some natural number x in binary. Let the least significant digit represent the inclusion or exclusion of 0, the next least significant represent 1, and so on upwards. For some examples:
$0$ ; $0_2$ ; {}
$7$ ; $111_2$ ; {0, 1, 2}
$8$ ; $1000_2$ ; {3}
$14$ ; $1110_2$ ; {1, 2, 3}
By cantors diagonalization argument I know that this can't be a bijection between the natural numbers and their powerset, but I'm having trouble proving that it's not. Can I prove that this is not a bijection without just quoting the cardinality of the sets (and preferably with a counterexample)?
cardinals
asked Jan 14 at 19:42
matthew schallenkampmatthew schallenkamp
31
$endgroup$
marked as duplicate by Asaf Karagila♦ cardinals
Users with the cardinals badge can single-handedly close cardinals questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 14 at 19:55
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Why doesn't Cantor's diagonal argument also apply to natural numbers?
2 answers
Lets consider some natural number x in binary. Let the least significant digit represent the inclusion or exclusion of 0, the next least significant represent 1, and so on upwards. For some examples:
$0$ ; $0_2$ ; {}
$7$ ; $111_2$ ; {0, 1, 2}
$8$ ; $1000_2$ ; {3}
$14$ ; $1110_2$ ; {1, 2, 3}
By cantors diagonalization argument I know that this can't be a bijection between the natural numbers and their powerset, but I'm having trouble proving that it's not. Can I prove that this is not a bijection without just quoting the cardinality of the sets (and preferably with a counterexample)?
cardinals
asked Jan 14 at 19:42
matthew schallenkampmatthew schallenkamp
31
$endgroup$
marked as duplicate by Asaf Karagila♦ cardinals
Users with the cardinals badge can single-handedly close cardinals questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 14 at 19:55
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
The proof is simple enough that you can try and apply it for your function and see the result.
$endgroup$
– Asaf Karagila♦
Jan 14 at 19:56
add a comment |
$begingroup$
This question already has an answer here:
Why doesn't Cantor's diagonal argument also apply to natural numbers?
2 answers
Lets consider some natural number x in binary. Let the least significant digit represent the inclusion or exclusion of 0, the next least significant represent 1, and so on upwards. For some examples:
$0$ ; $0_2$ ; {}
$7$ ; $111_2$ ; {0, 1, 2}
$8$ ; $1000_2$ ; {3}
$14$ ; $1110_2$ ; {1, 2, 3}
By cantors diagonalization argument I know that this can't be a bijection between the natural numbers and their powerset, but I'm having trouble proving that it's not. Can I prove that this is not a bijection without just quoting the cardinality of the sets (and preferably with a counterexample)?
cardinals
asked Jan 14 at 19:42
matthew schallenkampmatthew schallenkamp
31
$endgroup$
This question already has an answer here:
Why doesn't Cantor's diagonal argument also apply to natural numbers?
2 answers
Lets consider some natural number x in binary. Let the least significant digit represent the inclusion or exclusion of 0, the next least significant represent 1, and so on upwards. For some examples:
$0$ ; $0_2$ ; {}
$7$ ; $111_2$ ; {0, 1, 2}
$8$ ; $1000_2$ ; {3}
$14$ ; $1110_2$ ; {1, 2, 3}
By cantors diagonalization argument I know that this can't be a bijection between the natural numbers and their powerset, but I'm having trouble proving that it's not. Can I prove that this is not a bijection without just quoting the cardinality of the sets (and preferably with a counterexample)?
This question already has an answer here:
Why doesn't Cantor's diagonal argument also apply to natural numbers?
2 answers
cardinals
cardinals
asked Jan 14 at 19:42
matthew schallenkampmatthew schallenkamp
31
asked Jan 14 at 19:42
matthew schallenkampmatthew schallenkamp
31
asked Jan 14 at 19:42
matthew schallenkampmatthew schallenkamp
31
asked Jan 14 at 19:42
matthew schallenkampmatthew schallenkamp
31
asked Jan 14 at 19:42
matthew schallenkampmatthew schallenkamp
31
31
marked as duplicate by Asaf Karagila♦ cardinals
Users with the cardinals badge can single-handedly close cardinals questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 14 at 19:55
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Asaf Karagila♦ cardinals
Users with the cardinals badge can single-handedly close cardinals questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 14 at 19:55
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
The proof is simple enough that you can try and apply it for your function and see the result.
$endgroup$
– Asaf Karagila♦
Jan 14 at 19:56
add a comment |
$begingroup$
The proof is simple enough that you can try and apply it for your function and see the result.
$endgroup$
– Asaf Karagila♦
Jan 14 at 19:56
$begingroup$
The proof is simple enough that you can try and apply it for your function and see the result.
$endgroup$
– Asaf Karagila♦
Jan 14 at 19:56
$begingroup$
The proof is simple enough that you can try and apply it for your function and see the result.
$endgroup$
– Asaf Karagila♦
Jan 14 at 19:56
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
That's a bijection between $mathbb N$ and the set of all finite subsets of $mathbb N$. But $mathbb N$ also has infinite subsets…
answered Jan 14 at 19:45
José Carlos SantosJosé Carlos Santos
162k22128232
$endgroup$
$begingroup$
Thank you, that's exactly what I was missing.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:03
add a comment |
$begingroup$
The proposed bijection only works for finite sets, as José Carlos Santos pointed out.
Even for finite sets, it doesn't work.
One issue is the multiplicity of assignments due to leading zeroes.
Consider the set ${1}$. This should be $01_2 = 1$, but $1_2=1$ has already been assigned to the set ${0}$.
Similarly, the set ${3}$ should also be $0001_2 = 1$.
answered Jan 14 at 19:52
Zubin MukerjeeZubin Mukerjee
15.2k32658
$endgroup$
$begingroup$
I'm considering the bits in reverse order from how you are, so instead of ${3}$ being $0001_2$ it is $1000_2$. That should alleviate the leading $0$'s issue.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:06
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
That's a bijection between $mathbb N$ and the set of all finite subsets of $mathbb N$. But $mathbb N$ also has infinite subsets…
answered Jan 14 at 19:45
José Carlos SantosJosé Carlos Santos
162k22128232
$endgroup$
$begingroup$
Thank you, that's exactly what I was missing.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:03
add a comment |
$begingroup$
That's a bijection between $mathbb N$ and the set of all finite subsets of $mathbb N$. But $mathbb N$ also has infinite subsets…
answered Jan 14 at 19:45
José Carlos SantosJosé Carlos Santos
162k22128232
$endgroup$
$begingroup$
Thank you, that's exactly what I was missing.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:03
add a comment |
$begingroup$
That's a bijection between $mathbb N$ and the set of all finite subsets of $mathbb N$. But $mathbb N$ also has infinite subsets…
answered Jan 14 at 19:45
José Carlos SantosJosé Carlos Santos
162k22128232
$endgroup$
That's a bijection between $mathbb N$ and the set of all finite subsets of $mathbb N$. But $mathbb N$ also has infinite subsets…
answered Jan 14 at 19:45
José Carlos SantosJosé Carlos Santos
162k22128232
answered Jan 14 at 19:45
José Carlos SantosJosé Carlos Santos
162k22128232
answered Jan 14 at 19:45
José Carlos SantosJosé Carlos Santos
162k22128232
answered Jan 14 at 19:45
José Carlos SantosJosé Carlos Santos
162k22128232
162k22128232
$begingroup$
Thank you, that's exactly what I was missing.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:03
add a comment |
$begingroup$
Thank you, that's exactly what I was missing.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:03
$begingroup$
Thank you, that's exactly what I was missing.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:03
$begingroup$
Thank you, that's exactly what I was missing.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:03
add a comment |
$begingroup$
The proposed bijection only works for finite sets, as José Carlos Santos pointed out.
Even for finite sets, it doesn't work.
One issue is the multiplicity of assignments due to leading zeroes.
Consider the set ${1}$. This should be $01_2 = 1$, but $1_2=1$ has already been assigned to the set ${0}$.
Similarly, the set ${3}$ should also be $0001_2 = 1$.
answered Jan 14 at 19:52
Zubin MukerjeeZubin Mukerjee
15.2k32658
$endgroup$
$begingroup$
I'm considering the bits in reverse order from how you are, so instead of ${3}$ being $0001_2$ it is $1000_2$. That should alleviate the leading $0$'s issue.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:06
add a comment |
$begingroup$
The proposed bijection only works for finite sets, as José Carlos Santos pointed out.
Even for finite sets, it doesn't work.
One issue is the multiplicity of assignments due to leading zeroes.
Consider the set ${1}$. This should be $01_2 = 1$, but $1_2=1$ has already been assigned to the set ${0}$.
Similarly, the set ${3}$ should also be $0001_2 = 1$.
answered Jan 14 at 19:52
Zubin MukerjeeZubin Mukerjee
15.2k32658
$endgroup$
$begingroup$
I'm considering the bits in reverse order from how you are, so instead of ${3}$ being $0001_2$ it is $1000_2$. That should alleviate the leading $0$'s issue.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:06
add a comment |
$begingroup$
The proposed bijection only works for finite sets, as José Carlos Santos pointed out.
Even for finite sets, it doesn't work.
One issue is the multiplicity of assignments due to leading zeroes.
Consider the set ${1}$. This should be $01_2 = 1$, but $1_2=1$ has already been assigned to the set ${0}$.
Similarly, the set ${3}$ should also be $0001_2 = 1$.
answered Jan 14 at 19:52
Zubin MukerjeeZubin Mukerjee
15.2k32658
$endgroup$
The proposed bijection only works for finite sets, as José Carlos Santos pointed out.
Even for finite sets, it doesn't work.
One issue is the multiplicity of assignments due to leading zeroes.
Consider the set ${1}$. This should be $01_2 = 1$, but $1_2=1$ has already been assigned to the set ${0}$.
Similarly, the set ${3}$ should also be $0001_2 = 1$.
answered Jan 14 at 19:52
Zubin MukerjeeZubin Mukerjee
15.2k32658
answered Jan 14 at 19:52
Zubin MukerjeeZubin Mukerjee
15.2k32658
answered Jan 14 at 19:52
Zubin MukerjeeZubin Mukerjee
15.2k32658
answered Jan 14 at 19:52
Zubin MukerjeeZubin Mukerjee
15.2k32658
15.2k32658
$begingroup$
I'm considering the bits in reverse order from how you are, so instead of ${3}$ being $0001_2$ it is $1000_2$. That should alleviate the leading $0$'s issue.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:06
add a comment |
$begingroup$
I'm considering the bits in reverse order from how you are, so instead of ${3}$ being $0001_2$ it is $1000_2$. That should alleviate the leading $0$'s issue.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:06
$begingroup$
I'm considering the bits in reverse order from how you are, so instead of ${3}$ being $0001_2$ it is $1000_2$. That should alleviate the leading $0$'s issue.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:06
$begingroup$
I'm considering the bits in reverse order from how you are, so instead of ${3}$ being $0001_2$ it is $1000_2$. That should alleviate the leading $0$'s issue.
$endgroup$
– matthew schallenkamp
Jan 15 at 20:06
add a comment |
$begingroup$
The proof is simple enough that you can try and apply it for your function and see the result.
$endgroup$
– Asaf Karagila♦
Jan 14 at 19:56