Trying to find a flaw in my proof that there are more rearrangements of an infinite series than real numbersQuestion on Riemann's rearrangement theoremProof that the real numbers are countable: Help with why this is wrongHow to divide aleph numbersHow to make Riemann rearrangement?All sets of rational numbers are bigger than the set containing infinite integers - or are they?Bijection between $mathbbZ longmapsto mathbbR$Verification of this proof that the set of real numbers is uncountable.Proof that the set of Natural numbers are equal to the Real numbersRearrangement of Alternating Harmonic Series to be InfinityUsing union of countably infinite sets, I tried to prove that set of all real numbers in [0,1) is countable
Source for "everyone has a specific area of Torah that they're naturally drawn to"
Would using carbon dioxide as fuel work to reduce the greenhouse effect?
Monday's Blocking Donimoes Problem
Is it OK to accept a job opportunity while planning on not taking it?
What does the following chess proverb mean: "Chess is a sea where a gnat may drink from and an elephant may bathe in."
How to pass array of values in lualatex?
Quickest way to move a line in a text file before another line in a text file?
What kind of curve (or model) should I fit to my percentage data?
What is a "staved" town, like in "Staverton"?
Storyboarding Approaches for the Non-Artistic
Found more old paper shares from broken up companies
Calculating Fibonacci sequence in several different ways
Create Circle with Inner Radius
Counterexample finite intersection property
Why did modems have speakers?
MITM on HTTPS traffic in Kazakhstan 2019
As the Ferris wheel turns
Why is a PhD thesis typically 150 pages?
Why is there an extra "t" in Lemmatization?
Pass USB 3.0 connection through D-SUB connector
Magic is the twist
How old is the Italian word "malandrino"?
Facebook video calling problem in Safari
How does mathematics work?
Trying to find a flaw in my proof that there are more rearrangements of an infinite series than real numbers
Question on Riemann's rearrangement theoremProof that the real numbers are countable: Help with why this is wrongHow to divide aleph numbersHow to make Riemann rearrangement?All sets of rational numbers are bigger than the set containing infinite integers - or are they?Bijection between $mathbbZ longmapsto mathbbR$Verification of this proof that the set of real numbers is uncountable.Proof that the set of Natural numbers are equal to the Real numbersRearrangement of Alternating Harmonic Series to be InfinityUsing union of countably infinite sets, I tried to prove that set of all real numbers in [0,1) is countable
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
So I had this thought that I was trying to prove as an exercise
Let $mathbbR$ be the set of real numbers and let $mathbbS$ be the set of all possible rearrangements of the alternating harmonic series. Prove that $|mathbbR| < |mathbbS|$
I thought I had a proof of this, but I then posted it to Reddit /r/math only to be downvoted and told the proof was wrong. The only comment I received was to "look at it from the other direction", but that confused me.
Here is my proof:
Two sets have the same cardinality iff there exists a bijection between them.
From the rearrangement theorem we can show that a the alternating harmonic series can converge to any real number via the following algorithm:
Start with $1$, if this is larger than the target number add the next negative term, otherwise add the next positive term. We create a mapping from the created rearrangement to the limit of this rearrangement. Notice that this maps to all real numbers.
Now take one of the series that we had, and switch the first two terms. This is a new rearrangement since it does not begin with $1$, so it should be mapped to a new real number. However all real numbers have already had a rearrangement mapped to them. As such we have two rearrangements pointing to a single real number, which means that our mapping is not a bijection.
As such there must be more rearrangements than real numbers.
Now I am not sure where my proof went wrong, so any help would be appreciated!
sequences-and-series general-topology elementary-set-theory real-numbers infinity
asked Jul 12 at 20:11
wjmccannwjmccann
7772 silver badges18 bronze badges
$endgroup$
|
show 6 more comments
$begingroup$
So I had this thought that I was trying to prove as an exercise
Let $mathbbR$ be the set of real numbers and let $mathbbS$ be the set of all possible rearrangements of the alternating harmonic series. Prove that $|mathbbR| < |mathbbS|$
I thought I had a proof of this, but I then posted it to Reddit /r/math only to be downvoted and told the proof was wrong. The only comment I received was to "look at it from the other direction", but that confused me.
Here is my proof:
Two sets have the same cardinality iff there exists a bijection between them.
From the rearrangement theorem we can show that a the alternating harmonic series can converge to any real number via the following algorithm:
Start with $1$, if this is larger than the target number add the next negative term, otherwise add the next positive term. We create a mapping from the created rearrangement to the limit of this rearrangement. Notice that this maps to all real numbers.
Now take one of the series that we had, and switch the first two terms. This is a new rearrangement since it does not begin with $1$, so it should be mapped to a new real number. However all real numbers have already had a rearrangement mapped to them. As such we have two rearrangements pointing to a single real number, which means that our mapping is not a bijection.
As such there must be more rearrangements than real numbers.
Now I am not sure where my proof went wrong, so any help would be appreciated!
sequences-and-series general-topology elementary-set-theory real-numbers infinity
asked Jul 12 at 20:11
wjmccannwjmccann
7772 silver badges18 bronze badges
$endgroup$
4
$begingroup$
That doesn't prove that there are more rearrangements. It proves that there are at least as many.
$endgroup$
– Matt Samuel
Jul 12 at 20:18
5
$begingroup$
I can map the integers into themselves injectively but not bijectively (say $F(n) = 2n$), but that doesn't mean the there are more integers than there are integers. Or if you prefer, I can map the even integers onto the integers, but the odds are left over in the domain ... but you can't conclude the domain is bigger than the range. One map is not all maps!
$endgroup$
– Ned
Jul 12 at 20:18
1
$begingroup$
The cardinality of the arrangements is at most that of $mathbb N^mathbb N $. I don't know if that's bigger than $c$, but I suspect it's not.
$endgroup$
– Matt Samuel
Jul 12 at 20:26
3
$begingroup$
@wjmccann The difference in the diagonal argument is it finds an additional element no matter what the map is. It gives you a method to construct a real number that an arbitrary map doesn't hit.
$endgroup$
– Matt Samuel
Jul 12 at 20:30
2
$begingroup$
@MattSamuel There are indeed the same number of each - you can code an arbitrary function into a binary expansion (think about building strings of zeros ...).
$endgroup$
– Noah Schweber
Jul 12 at 20:46
|
show 6 more comments
$begingroup$
So I had this thought that I was trying to prove as an exercise
Let $mathbbR$ be the set of real numbers and let $mathbbS$ be the set of all possible rearrangements of the alternating harmonic series. Prove that $|mathbbR| < |mathbbS|$
I thought I had a proof of this, but I then posted it to Reddit /r/math only to be downvoted and told the proof was wrong. The only comment I received was to "look at it from the other direction", but that confused me.
Here is my proof:
Two sets have the same cardinality iff there exists a bijection between them.
From the rearrangement theorem we can show that a the alternating harmonic series can converge to any real number via the following algorithm:
Start with $1$, if this is larger than the target number add the next negative term, otherwise add the next positive term. We create a mapping from the created rearrangement to the limit of this rearrangement. Notice that this maps to all real numbers.
Now take one of the series that we had, and switch the first two terms. This is a new rearrangement since it does not begin with $1$, so it should be mapped to a new real number. However all real numbers have already had a rearrangement mapped to them. As such we have two rearrangements pointing to a single real number, which means that our mapping is not a bijection.
As such there must be more rearrangements than real numbers.
Now I am not sure where my proof went wrong, so any help would be appreciated!
sequences-and-series general-topology elementary-set-theory real-numbers infinity
asked Jul 12 at 20:11
wjmccannwjmccann
7772 silver badges18 bronze badges
$endgroup$
So I had this thought that I was trying to prove as an exercise
Let $mathbbR$ be the set of real numbers and let $mathbbS$ be the set of all possible rearrangements of the alternating harmonic series. Prove that $|mathbbR| < |mathbbS|$
I thought I had a proof of this, but I then posted it to Reddit /r/math only to be downvoted and told the proof was wrong. The only comment I received was to "look at it from the other direction", but that confused me.
Here is my proof:
Two sets have the same cardinality iff there exists a bijection between them.
From the rearrangement theorem we can show that a the alternating harmonic series can converge to any real number via the following algorithm:
Start with $1$, if this is larger than the target number add the next negative term, otherwise add the next positive term. We create a mapping from the created rearrangement to the limit of this rearrangement. Notice that this maps to all real numbers.
Now take one of the series that we had, and switch the first two terms. This is a new rearrangement since it does not begin with $1$, so it should be mapped to a new real number. However all real numbers have already had a rearrangement mapped to them. As such we have two rearrangements pointing to a single real number, which means that our mapping is not a bijection.
As such there must be more rearrangements than real numbers.
Now I am not sure where my proof went wrong, so any help would be appreciated!
sequences-and-series general-topology elementary-set-theory real-numbers infinity
sequences-and-series general-topology elementary-set-theory real-numbers infinity
asked Jul 12 at 20:11
wjmccannwjmccann
7772 silver badges18 bronze badges
asked Jul 12 at 20:11
wjmccannwjmccann
7772 silver badges18 bronze badges
asked Jul 12 at 20:11
wjmccannwjmccann
7772 silver badges18 bronze badges
asked Jul 12 at 20:11
wjmccannwjmccann
7772 silver badges18 bronze badges
asked Jul 12 at 20:11
wjmccannwjmccann
7772 silver badges18 bronze badges
7772 silver badges18 bronze badges
4
$begingroup$
That doesn't prove that there are more rearrangements. It proves that there are at least as many.
$endgroup$
– Matt Samuel
Jul 12 at 20:18
5
$begingroup$
I can map the integers into themselves injectively but not bijectively (say $F(n) = 2n$), but that doesn't mean the there are more integers than there are integers. Or if you prefer, I can map the even integers onto the integers, but the odds are left over in the domain ... but you can't conclude the domain is bigger than the range. One map is not all maps!
$endgroup$
– Ned
Jul 12 at 20:18
1
$begingroup$
The cardinality of the arrangements is at most that of $mathbb N^mathbb N $. I don't know if that's bigger than $c$, but I suspect it's not.
$endgroup$
– Matt Samuel
Jul 12 at 20:26
3
$begingroup$
@wjmccann The difference in the diagonal argument is it finds an additional element no matter what the map is. It gives you a method to construct a real number that an arbitrary map doesn't hit.
$endgroup$
– Matt Samuel
Jul 12 at 20:30
2
$begingroup$
@MattSamuel There are indeed the same number of each - you can code an arbitrary function into a binary expansion (think about building strings of zeros ...).
$endgroup$
– Noah Schweber
Jul 12 at 20:46
|
show 6 more comments
4
$begingroup$
That doesn't prove that there are more rearrangements. It proves that there are at least as many.
$endgroup$
– Matt Samuel
Jul 12 at 20:18
5
$begingroup$
I can map the integers into themselves injectively but not bijectively (say $F(n) = 2n$), but that doesn't mean the there are more integers than there are integers. Or if you prefer, I can map the even integers onto the integers, but the odds are left over in the domain ... but you can't conclude the domain is bigger than the range. One map is not all maps!
$endgroup$
– Ned
Jul 12 at 20:18
1
$begingroup$
The cardinality of the arrangements is at most that of $mathbb N^mathbb N $. I don't know if that's bigger than $c$, but I suspect it's not.
$endgroup$
– Matt Samuel
Jul 12 at 20:26
3
$begingroup$
@wjmccann The difference in the diagonal argument is it finds an additional element no matter what the map is. It gives you a method to construct a real number that an arbitrary map doesn't hit.
$endgroup$
– Matt Samuel
Jul 12 at 20:30
2
$begingroup$
@MattSamuel There are indeed the same number of each - you can code an arbitrary function into a binary expansion (think about building strings of zeros ...).
$endgroup$
– Noah Schweber
Jul 12 at 20:46
4
4
$begingroup$
That doesn't prove that there are more rearrangements. It proves that there are at least as many.
$endgroup$
– Matt Samuel
Jul 12 at 20:18
$begingroup$
That doesn't prove that there are more rearrangements. It proves that there are at least as many.
$endgroup$
– Matt Samuel
Jul 12 at 20:18
5
5
$begingroup$
I can map the integers into themselves injectively but not bijectively (say $F(n) = 2n$), but that doesn't mean the there are more integers than there are integers. Or if you prefer, I can map the even integers onto the integers, but the odds are left over in the domain ... but you can't conclude the domain is bigger than the range. One map is not all maps!
$endgroup$
– Ned
Jul 12 at 20:18
$begingroup$
I can map the integers into themselves injectively but not bijectively (say $F(n) = 2n$), but that doesn't mean the there are more integers than there are integers. Or if you prefer, I can map the even integers onto the integers, but the odds are left over in the domain ... but you can't conclude the domain is bigger than the range. One map is not all maps!
$endgroup$
– Ned
Jul 12 at 20:18
1
1
$begingroup$
The cardinality of the arrangements is at most that of $mathbb N^mathbb N $. I don't know if that's bigger than $c$, but I suspect it's not.
$endgroup$
– Matt Samuel
Jul 12 at 20:26
$begingroup$
The cardinality of the arrangements is at most that of $mathbb N^mathbb N $. I don't know if that's bigger than $c$, but I suspect it's not.
$endgroup$
– Matt Samuel
Jul 12 at 20:26
3
3
$begingroup$
@wjmccann The difference in the diagonal argument is it finds an additional element no matter what the map is. It gives you a method to construct a real number that an arbitrary map doesn't hit.
$endgroup$
– Matt Samuel
Jul 12 at 20:30
$begingroup$
@wjmccann The difference in the diagonal argument is it finds an additional element no matter what the map is. It gives you a method to construct a real number that an arbitrary map doesn't hit.
$endgroup$
– Matt Samuel
Jul 12 at 20:30
2
2
$begingroup$
@MattSamuel There are indeed the same number of each - you can code an arbitrary function into a binary expansion (think about building strings of zeros ...).
$endgroup$
– Noah Schweber
Jul 12 at 20:46
$begingroup$
@MattSamuel There are indeed the same number of each - you can code an arbitrary function into a binary expansion (think about building strings of zeros ...).
$endgroup$
– Noah Schweber
Jul 12 at 20:46
|
show 6 more comments
5 Answers
5
active
oldest
votes
$begingroup$
Consider the function $FcolonBbbNto N$ defined by: $$F(n)=begincases 0 & n=0\ n-1 & n>0endcases$$
by your argument, since this function is not a bijection (clearly $F(0)=F(1)$ so it is not injective), $Bbb N$ is not the same size as $Bbb N$.
What just happened? You've proved, as I did above, there is a surjective function which is not injective. But that doesn't prevents a different function to be a bijection.
Cantor's diagonal works by showing that any function is not surjective, and therefore there are no bijections. But you've only showed that one function is not injective, and concluded that there are no bijections.
You have to remember: Infinite sets are very different from finite sets. Just because one function is a surjection which is not a bijection doesn't mean there a different one is not.
Here's an injective function from the rearrangements into the reals:
Let $fcolonBbbNto N$ be the permutation describing the rearrangement. Namely, $f(n)=k$ if and only if the $k$th summand is $frac1n$ (up to a sign, if you prefer). Map the rearrangement given by $f$ to the real number given by: $$sum_ninBbb Nfrac23^2^ncdot 3^f(n)$$
This sum converges, and you can quite easily show that if $fneq g$, then there is some $n$ such that $f(n)neq g(n)$ and therefore one of the digits in the trenary expansion of the two reals is different, and since those are only $0$ or $2$ this means that the real numbers are different. Therefore the map from rearrangements into the real numbers given above is injective.
On the other hand, you can easily show that there are at least $2^aleph_0$ rearrangements, but I will leave this to you as an exercise.
answered Jul 12 at 20:50
Asaf Karagila♦Asaf Karagila
314k34 gold badges452 silver badges785 bronze badges
$endgroup$
add a comment |
$begingroup$
As explained in the comments, what you've done is whip up a non-injective surjection from $mathbbS$ to $mathbbR$. This alone doesn't prove the statement in question, however - just because one surjection isn't injective doesn't mean that there isn't some other surjection which is injective.
This is a fundamental difference between the infinite and finite cases. If $A$ and $B$ are finite sets and $f:Arightarrow B$ is a non-injective surjection, then $A$ does in fact have greater cardinality than $B$. But this fails for infinite sets: consider for example the map from naturals to naturals given by $$xmapsto leftlfloorxover 2rightrfloor$$ (where "$lfloorcdotrfloor$" is the floor function). This is a non-injective surjection; should we conclude that $lvertmathbbNrvert>lvertmathbbNrvert$? You can easily whip up other examples to drive the point home.
Indeed, $mathbbR$ and $mathbbS$ have the same cardinality. Matt Samuel's comment has suggested an explanation: that the set $mathbbN^mathbbN$ of maps from naturals to naturals - or equivalently, infinite sequences of natural numbers - has cardinality at least that of $mathbbS$, and so we'll be done if we can find an injection from $mathbbN^mathbbN$ to $mathbbR$. We can do this by "coding into the binary expansion" - think about how the real number $$0.colorred001colorred00001colorred0001colorred01...$$ corresponds to the sequence $$2,4,3,1,....$$ Do you see how to turn this into an honest-to-goodness injection?
Incidentally, while it doesn't make a difference in the context of the axiom of choice (which tells us that given a surjection $Arightarrow B$ we can find an injection $Brightarrow A$), it will ultimately be better to think of cardinality in terms of injections rather than surjections: $lvert Arvertgelvert Brvert$ iff there is an injection $Brightarrow A$, not iff there is a surjection $Arightarrow B$. It's not immediately obvious that this is a better notion when choice fails, but it really does turn out to be the right one.
edited Jul 13 at 10:55
MBlanc
1,0107 silver badges13 bronze badges
answered Jul 12 at 20:52
Noah SchweberNoah Schweber
135k10 gold badges160 silver badges305 bronze badges
$endgroup$
$begingroup$
Funny how we both wrote similar answers. :P
$endgroup$
– Asaf Karagila♦
Jul 12 at 20:57
$begingroup$
@AsafKaragila As is our way. (Beat me by two minutes ...)
$endgroup$
– Noah Schweber
Jul 12 at 20:58
add a comment |
$begingroup$
While you showed $|mathbbR| leq |mathbbS|$ properly by constructing a surjection, the problem with your proof of $|mathbbR| neq |mathbbS|$ is that it merely shows that the particular kind of map you are trying to construct cannot be a bijection. For the proof to be valid, it would need to show that any map from $mathbbS$ to $mathbbR$ is not a bijection.
answered Jul 12 at 20:49
MagmaMagma
1,0301 silver badge9 bronze badges
$endgroup$
add a comment |
$begingroup$
You have shown the cardinality of the real numbers is a lower bound by constructing a surjective map. You can't conclude from the fact that it is not injective that there are more rearrangements, because in order to do that you'd need to be able to show that every map is not injective.
In fact, the cardinality of the set of functions from $mathbb N$ to $mathbb N$ is an upper bound, and that is the same as that of the real numbers. So in fact there are equally many arrangements as real numbers.
In Cantor's diagonal argument, we are given an arbitrary function from the naturals to the real numbers, and the argument provides an algorithm for finding a number that the function doesn't hit. This works because it's not just one function this works for, it is every function. Therefore no function from the naturals to the real numbers is surjective.
edited Jul 12 at 23:22
Noah Schweber
135k10 gold badges160 silver badges305 bronze badges
answered Jul 12 at 20:50
Matt SamuelMatt Samuel
40.8k6 gold badges38 silver badges71 bronze badges
$endgroup$
add a comment |
$begingroup$
If I understand the question, you want to count the rearrangements of an infinite series (they would be called permutations if the series were finite).
Each such rearrangement is characterized by a series of (integer) index numbers, right?
So you want to know the size of the set of all series of integers, right?
If nothing else, just "print out" each integer as a string of digits in base 2, and then concatenate all of the digits separated by 2s, and you get something that looks just like a real. No two series map onto the same real.
answered Jul 14 at 21:38
RodRod
1
$endgroup$
add a comment |
Your Answer
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%2f3291289%2ftrying-to-find-a-flaw-in-my-proof-that-there-are-more-rearrangements-of-an-infin%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Consider the function $FcolonBbbNto N$ defined by: $$F(n)=begincases 0 & n=0\ n-1 & n>0endcases$$
by your argument, since this function is not a bijection (clearly $F(0)=F(1)$ so it is not injective), $Bbb N$ is not the same size as $Bbb N$.
What just happened? You've proved, as I did above, there is a surjective function which is not injective. But that doesn't prevents a different function to be a bijection.
Cantor's diagonal works by showing that any function is not surjective, and therefore there are no bijections. But you've only showed that one function is not injective, and concluded that there are no bijections.
You have to remember: Infinite sets are very different from finite sets. Just because one function is a surjection which is not a bijection doesn't mean there a different one is not.
Here's an injective function from the rearrangements into the reals:
Let $fcolonBbbNto N$ be the permutation describing the rearrangement. Namely, $f(n)=k$ if and only if the $k$th summand is $frac1n$ (up to a sign, if you prefer). Map the rearrangement given by $f$ to the real number given by: $$sum_ninBbb Nfrac23^2^ncdot 3^f(n)$$
This sum converges, and you can quite easily show that if $fneq g$, then there is some $n$ such that $f(n)neq g(n)$ and therefore one of the digits in the trenary expansion of the two reals is different, and since those are only $0$ or $2$ this means that the real numbers are different. Therefore the map from rearrangements into the real numbers given above is injective.
On the other hand, you can easily show that there are at least $2^aleph_0$ rearrangements, but I will leave this to you as an exercise.
answered Jul 12 at 20:50
Asaf Karagila♦Asaf Karagila
314k34 gold badges452 silver badges785 bronze badges
$endgroup$
add a comment |
$begingroup$
Consider the function $FcolonBbbNto N$ defined by: $$F(n)=begincases 0 & n=0\ n-1 & n>0endcases$$
by your argument, since this function is not a bijection (clearly $F(0)=F(1)$ so it is not injective), $Bbb N$ is not the same size as $Bbb N$.
What just happened? You've proved, as I did above, there is a surjective function which is not injective. But that doesn't prevents a different function to be a bijection.
Cantor's diagonal works by showing that any function is not surjective, and therefore there are no bijections. But you've only showed that one function is not injective, and concluded that there are no bijections.
You have to remember: Infinite sets are very different from finite sets. Just because one function is a surjection which is not a bijection doesn't mean there a different one is not.
Here's an injective function from the rearrangements into the reals:
Let $fcolonBbbNto N$ be the permutation describing the rearrangement. Namely, $f(n)=k$ if and only if the $k$th summand is $frac1n$ (up to a sign, if you prefer). Map the rearrangement given by $f$ to the real number given by: $$sum_ninBbb Nfrac23^2^ncdot 3^f(n)$$
This sum converges, and you can quite easily show that if $fneq g$, then there is some $n$ such that $f(n)neq g(n)$ and therefore one of the digits in the trenary expansion of the two reals is different, and since those are only $0$ or $2$ this means that the real numbers are different. Therefore the map from rearrangements into the real numbers given above is injective.
On the other hand, you can easily show that there are at least $2^aleph_0$ rearrangements, but I will leave this to you as an exercise.
answered Jul 12 at 20:50
Asaf Karagila♦Asaf Karagila
314k34 gold badges452 silver badges785 bronze badges
$endgroup$
add a comment |
$begingroup$
Consider the function $FcolonBbbNto N$ defined by: $$F(n)=begincases 0 & n=0\ n-1 & n>0endcases$$
by your argument, since this function is not a bijection (clearly $F(0)=F(1)$ so it is not injective), $Bbb N$ is not the same size as $Bbb N$.
What just happened? You've proved, as I did above, there is a surjective function which is not injective. But that doesn't prevents a different function to be a bijection.
Cantor's diagonal works by showing that any function is not surjective, and therefore there are no bijections. But you've only showed that one function is not injective, and concluded that there are no bijections.
You have to remember: Infinite sets are very different from finite sets. Just because one function is a surjection which is not a bijection doesn't mean there a different one is not.
Here's an injective function from the rearrangements into the reals:
Let $fcolonBbbNto N$ be the permutation describing the rearrangement. Namely, $f(n)=k$ if and only if the $k$th summand is $frac1n$ (up to a sign, if you prefer). Map the rearrangement given by $f$ to the real number given by: $$sum_ninBbb Nfrac23^2^ncdot 3^f(n)$$
This sum converges, and you can quite easily show that if $fneq g$, then there is some $n$ such that $f(n)neq g(n)$ and therefore one of the digits in the trenary expansion of the two reals is different, and since those are only $0$ or $2$ this means that the real numbers are different. Therefore the map from rearrangements into the real numbers given above is injective.
On the other hand, you can easily show that there are at least $2^aleph_0$ rearrangements, but I will leave this to you as an exercise.
answered Jul 12 at 20:50
Asaf Karagila♦Asaf Karagila
314k34 gold badges452 silver badges785 bronze badges
$endgroup$
Consider the function $FcolonBbbNto N$ defined by: $$F(n)=begincases 0 & n=0\ n-1 & n>0endcases$$
by your argument, since this function is not a bijection (clearly $F(0)=F(1)$ so it is not injective), $Bbb N$ is not the same size as $Bbb N$.
What just happened? You've proved, as I did above, there is a surjective function which is not injective. But that doesn't prevents a different function to be a bijection.
Cantor's diagonal works by showing that any function is not surjective, and therefore there are no bijections. But you've only showed that one function is not injective, and concluded that there are no bijections.
You have to remember: Infinite sets are very different from finite sets. Just because one function is a surjection which is not a bijection doesn't mean there a different one is not.
Here's an injective function from the rearrangements into the reals:
Let $fcolonBbbNto N$ be the permutation describing the rearrangement. Namely, $f(n)=k$ if and only if the $k$th summand is $frac1n$ (up to a sign, if you prefer). Map the rearrangement given by $f$ to the real number given by: $$sum_ninBbb Nfrac23^2^ncdot 3^f(n)$$
This sum converges, and you can quite easily show that if $fneq g$, then there is some $n$ such that $f(n)neq g(n)$ and therefore one of the digits in the trenary expansion of the two reals is different, and since those are only $0$ or $2$ this means that the real numbers are different. Therefore the map from rearrangements into the real numbers given above is injective.
On the other hand, you can easily show that there are at least $2^aleph_0$ rearrangements, but I will leave this to you as an exercise.
answered Jul 12 at 20:50
Asaf Karagila♦Asaf Karagila
314k34 gold badges452 silver badges785 bronze badges
answered Jul 12 at 20:50
Asaf Karagila♦Asaf Karagila
314k34 gold badges452 silver badges785 bronze badges
answered Jul 12 at 20:50
Asaf Karagila♦Asaf Karagila
314k34 gold badges452 silver badges785 bronze badges
answered Jul 12 at 20:50
Asaf Karagila♦Asaf Karagila
314k34 gold badges452 silver badges785 bronze badges
314k34 gold badges452 silver badges785 bronze badges
add a comment |
add a comment |
$begingroup$
As explained in the comments, what you've done is whip up a non-injective surjection from $mathbbS$ to $mathbbR$. This alone doesn't prove the statement in question, however - just because one surjection isn't injective doesn't mean that there isn't some other surjection which is injective.
This is a fundamental difference between the infinite and finite cases. If $A$ and $B$ are finite sets and $f:Arightarrow B$ is a non-injective surjection, then $A$ does in fact have greater cardinality than $B$. But this fails for infinite sets: consider for example the map from naturals to naturals given by $$xmapsto leftlfloorxover 2rightrfloor$$ (where "$lfloorcdotrfloor$" is the floor function). This is a non-injective surjection; should we conclude that $lvertmathbbNrvert>lvertmathbbNrvert$? You can easily whip up other examples to drive the point home.
Indeed, $mathbbR$ and $mathbbS$ have the same cardinality. Matt Samuel's comment has suggested an explanation: that the set $mathbbN^mathbbN$ of maps from naturals to naturals - or equivalently, infinite sequences of natural numbers - has cardinality at least that of $mathbbS$, and so we'll be done if we can find an injection from $mathbbN^mathbbN$ to $mathbbR$. We can do this by "coding into the binary expansion" - think about how the real number $$0.colorred001colorred00001colorred0001colorred01...$$ corresponds to the sequence $$2,4,3,1,....$$ Do you see how to turn this into an honest-to-goodness injection?
Incidentally, while it doesn't make a difference in the context of the axiom of choice (which tells us that given a surjection $Arightarrow B$ we can find an injection $Brightarrow A$), it will ultimately be better to think of cardinality in terms of injections rather than surjections: $lvert Arvertgelvert Brvert$ iff there is an injection $Brightarrow A$, not iff there is a surjection $Arightarrow B$. It's not immediately obvious that this is a better notion when choice fails, but it really does turn out to be the right one.
edited Jul 13 at 10:55
MBlanc
1,0107 silver badges13 bronze badges
answered Jul 12 at 20:52
Noah SchweberNoah Schweber
135k10 gold badges160 silver badges305 bronze badges
$endgroup$
$begingroup$
Funny how we both wrote similar answers. :P
$endgroup$
– Asaf Karagila♦
Jul 12 at 20:57
$begingroup$
@AsafKaragila As is our way. (Beat me by two minutes ...)
$endgroup$
– Noah Schweber
Jul 12 at 20:58
add a comment |
$begingroup$
As explained in the comments, what you've done is whip up a non-injective surjection from $mathbbS$ to $mathbbR$. This alone doesn't prove the statement in question, however - just because one surjection isn't injective doesn't mean that there isn't some other surjection which is injective.
This is a fundamental difference between the infinite and finite cases. If $A$ and $B$ are finite sets and $f:Arightarrow B$ is a non-injective surjection, then $A$ does in fact have greater cardinality than $B$. But this fails for infinite sets: consider for example the map from naturals to naturals given by $$xmapsto leftlfloorxover 2rightrfloor$$ (where "$lfloorcdotrfloor$" is the floor function). This is a non-injective surjection; should we conclude that $lvertmathbbNrvert>lvertmathbbNrvert$? You can easily whip up other examples to drive the point home.
Indeed, $mathbbR$ and $mathbbS$ have the same cardinality. Matt Samuel's comment has suggested an explanation: that the set $mathbbN^mathbbN$ of maps from naturals to naturals - or equivalently, infinite sequences of natural numbers - has cardinality at least that of $mathbbS$, and so we'll be done if we can find an injection from $mathbbN^mathbbN$ to $mathbbR$. We can do this by "coding into the binary expansion" - think about how the real number $$0.colorred001colorred00001colorred0001colorred01...$$ corresponds to the sequence $$2,4,3,1,....$$ Do you see how to turn this into an honest-to-goodness injection?
Incidentally, while it doesn't make a difference in the context of the axiom of choice (which tells us that given a surjection $Arightarrow B$ we can find an injection $Brightarrow A$), it will ultimately be better to think of cardinality in terms of injections rather than surjections: $lvert Arvertgelvert Brvert$ iff there is an injection $Brightarrow A$, not iff there is a surjection $Arightarrow B$. It's not immediately obvious that this is a better notion when choice fails, but it really does turn out to be the right one.
edited Jul 13 at 10:55
MBlanc
1,0107 silver badges13 bronze badges
answered Jul 12 at 20:52
Noah SchweberNoah Schweber
135k10 gold badges160 silver badges305 bronze badges
$endgroup$
$begingroup$
Funny how we both wrote similar answers. :P
$endgroup$
– Asaf Karagila♦
Jul 12 at 20:57
$begingroup$
@AsafKaragila As is our way. (Beat me by two minutes ...)
$endgroup$
– Noah Schweber
Jul 12 at 20:58
add a comment |
$begingroup$
As explained in the comments, what you've done is whip up a non-injective surjection from $mathbbS$ to $mathbbR$. This alone doesn't prove the statement in question, however - just because one surjection isn't injective doesn't mean that there isn't some other surjection which is injective.
This is a fundamental difference between the infinite and finite cases. If $A$ and $B$ are finite sets and $f:Arightarrow B$ is a non-injective surjection, then $A$ does in fact have greater cardinality than $B$. But this fails for infinite sets: consider for example the map from naturals to naturals given by $$xmapsto leftlfloorxover 2rightrfloor$$ (where "$lfloorcdotrfloor$" is the floor function). This is a non-injective surjection; should we conclude that $lvertmathbbNrvert>lvertmathbbNrvert$? You can easily whip up other examples to drive the point home.
Indeed, $mathbbR$ and $mathbbS$ have the same cardinality. Matt Samuel's comment has suggested an explanation: that the set $mathbbN^mathbbN$ of maps from naturals to naturals - or equivalently, infinite sequences of natural numbers - has cardinality at least that of $mathbbS$, and so we'll be done if we can find an injection from $mathbbN^mathbbN$ to $mathbbR$. We can do this by "coding into the binary expansion" - think about how the real number $$0.colorred001colorred00001colorred0001colorred01...$$ corresponds to the sequence $$2,4,3,1,....$$ Do you see how to turn this into an honest-to-goodness injection?
Incidentally, while it doesn't make a difference in the context of the axiom of choice (which tells us that given a surjection $Arightarrow B$ we can find an injection $Brightarrow A$), it will ultimately be better to think of cardinality in terms of injections rather than surjections: $lvert Arvertgelvert Brvert$ iff there is an injection $Brightarrow A$, not iff there is a surjection $Arightarrow B$. It's not immediately obvious that this is a better notion when choice fails, but it really does turn out to be the right one.
edited Jul 13 at 10:55
MBlanc
1,0107 silver badges13 bronze badges
answered Jul 12 at 20:52
Noah SchweberNoah Schweber
135k10 gold badges160 silver badges305 bronze badges
$endgroup$
As explained in the comments, what you've done is whip up a non-injective surjection from $mathbbS$ to $mathbbR$. This alone doesn't prove the statement in question, however - just because one surjection isn't injective doesn't mean that there isn't some other surjection which is injective.
This is a fundamental difference between the infinite and finite cases. If $A$ and $B$ are finite sets and $f:Arightarrow B$ is a non-injective surjection, then $A$ does in fact have greater cardinality than $B$. But this fails for infinite sets: consider for example the map from naturals to naturals given by $$xmapsto leftlfloorxover 2rightrfloor$$ (where "$lfloorcdotrfloor$" is the floor function). This is a non-injective surjection; should we conclude that $lvertmathbbNrvert>lvertmathbbNrvert$? You can easily whip up other examples to drive the point home.
Indeed, $mathbbR$ and $mathbbS$ have the same cardinality. Matt Samuel's comment has suggested an explanation: that the set $mathbbN^mathbbN$ of maps from naturals to naturals - or equivalently, infinite sequences of natural numbers - has cardinality at least that of $mathbbS$, and so we'll be done if we can find an injection from $mathbbN^mathbbN$ to $mathbbR$. We can do this by "coding into the binary expansion" - think about how the real number $$0.colorred001colorred00001colorred0001colorred01...$$ corresponds to the sequence $$2,4,3,1,....$$ Do you see how to turn this into an honest-to-goodness injection?
Incidentally, while it doesn't make a difference in the context of the axiom of choice (which tells us that given a surjection $Arightarrow B$ we can find an injection $Brightarrow A$), it will ultimately be better to think of cardinality in terms of injections rather than surjections: $lvert Arvertgelvert Brvert$ iff there is an injection $Brightarrow A$, not iff there is a surjection $Arightarrow B$. It's not immediately obvious that this is a better notion when choice fails, but it really does turn out to be the right one.
edited Jul 13 at 10:55
MBlanc
1,0107 silver badges13 bronze badges
answered Jul 12 at 20:52
Noah SchweberNoah Schweber
135k10 gold badges160 silver badges305 bronze badges
edited Jul 13 at 10:55
MBlanc
1,0107 silver badges13 bronze badges
edited Jul 13 at 10:55
MBlanc
1,0107 silver badges13 bronze badges
edited Jul 13 at 10:55
MBlanc
1,0107 silver badges13 bronze badges
1,0107 silver badges13 bronze badges
answered Jul 12 at 20:52
Noah SchweberNoah Schweber
135k10 gold badges160 silver badges305 bronze badges
answered Jul 12 at 20:52
Noah SchweberNoah Schweber
135k10 gold badges160 silver badges305 bronze badges
answered Jul 12 at 20:52
Noah SchweberNoah Schweber
135k10 gold badges160 silver badges305 bronze badges
135k10 gold badges160 silver badges305 bronze badges
$begingroup$
Funny how we both wrote similar answers. :P
$endgroup$
– Asaf Karagila♦
Jul 12 at 20:57
$begingroup$
@AsafKaragila As is our way. (Beat me by two minutes ...)
$endgroup$
– Noah Schweber
Jul 12 at 20:58
add a comment |
$begingroup$
Funny how we both wrote similar answers. :P
$endgroup$
– Asaf Karagila♦
Jul 12 at 20:57
$begingroup$
@AsafKaragila As is our way. (Beat me by two minutes ...)
$endgroup$
– Noah Schweber
Jul 12 at 20:58
$begingroup$
Funny how we both wrote similar answers. :P
$endgroup$
– Asaf Karagila♦
Jul 12 at 20:57
$begingroup$
Funny how we both wrote similar answers. :P
$endgroup$
– Asaf Karagila♦
Jul 12 at 20:57
$begingroup$
@AsafKaragila As is our way. (Beat me by two minutes ...)
$endgroup$
– Noah Schweber
Jul 12 at 20:58
$begingroup$
@AsafKaragila As is our way. (Beat me by two minutes ...)
$endgroup$
– Noah Schweber
Jul 12 at 20:58
add a comment |
$begingroup$
While you showed $|mathbbR| leq |mathbbS|$ properly by constructing a surjection, the problem with your proof of $|mathbbR| neq |mathbbS|$ is that it merely shows that the particular kind of map you are trying to construct cannot be a bijection. For the proof to be valid, it would need to show that any map from $mathbbS$ to $mathbbR$ is not a bijection.
answered Jul 12 at 20:49
MagmaMagma
1,0301 silver badge9 bronze badges
$endgroup$
add a comment |
$begingroup$
While you showed $|mathbbR| leq |mathbbS|$ properly by constructing a surjection, the problem with your proof of $|mathbbR| neq |mathbbS|$ is that it merely shows that the particular kind of map you are trying to construct cannot be a bijection. For the proof to be valid, it would need to show that any map from $mathbbS$ to $mathbbR$ is not a bijection.
answered Jul 12 at 20:49
MagmaMagma
1,0301 silver badge9 bronze badges
$endgroup$
add a comment |
$begingroup$
While you showed $|mathbbR| leq |mathbbS|$ properly by constructing a surjection, the problem with your proof of $|mathbbR| neq |mathbbS|$ is that it merely shows that the particular kind of map you are trying to construct cannot be a bijection. For the proof to be valid, it would need to show that any map from $mathbbS$ to $mathbbR$ is not a bijection.
answered Jul 12 at 20:49
MagmaMagma
1,0301 silver badge9 bronze badges
$endgroup$
While you showed $|mathbbR| leq |mathbbS|$ properly by constructing a surjection, the problem with your proof of $|mathbbR| neq |mathbbS|$ is that it merely shows that the particular kind of map you are trying to construct cannot be a bijection. For the proof to be valid, it would need to show that any map from $mathbbS$ to $mathbbR$ is not a bijection.
answered Jul 12 at 20:49
MagmaMagma
1,0301 silver badge9 bronze badges
answered Jul 12 at 20:49
MagmaMagma
1,0301 silver badge9 bronze badges
answered Jul 12 at 20:49
MagmaMagma
1,0301 silver badge9 bronze badges
answered Jul 12 at 20:49
MagmaMagma
1,0301 silver badge9 bronze badges
1,0301 silver badge9 bronze badges
add a comment |
add a comment |
$begingroup$
You have shown the cardinality of the real numbers is a lower bound by constructing a surjective map. You can't conclude from the fact that it is not injective that there are more rearrangements, because in order to do that you'd need to be able to show that every map is not injective.
In fact, the cardinality of the set of functions from $mathbb N$ to $mathbb N$ is an upper bound, and that is the same as that of the real numbers. So in fact there are equally many arrangements as real numbers.
In Cantor's diagonal argument, we are given an arbitrary function from the naturals to the real numbers, and the argument provides an algorithm for finding a number that the function doesn't hit. This works because it's not just one function this works for, it is every function. Therefore no function from the naturals to the real numbers is surjective.
edited Jul 12 at 23:22
Noah Schweber
135k10 gold badges160 silver badges305 bronze badges
answered Jul 12 at 20:50
Matt SamuelMatt Samuel
40.8k6 gold badges38 silver badges71 bronze badges
$endgroup$
add a comment |
$begingroup$
You have shown the cardinality of the real numbers is a lower bound by constructing a surjective map. You can't conclude from the fact that it is not injective that there are more rearrangements, because in order to do that you'd need to be able to show that every map is not injective.
In fact, the cardinality of the set of functions from $mathbb N$ to $mathbb N$ is an upper bound, and that is the same as that of the real numbers. So in fact there are equally many arrangements as real numbers.
In Cantor's diagonal argument, we are given an arbitrary function from the naturals to the real numbers, and the argument provides an algorithm for finding a number that the function doesn't hit. This works because it's not just one function this works for, it is every function. Therefore no function from the naturals to the real numbers is surjective.
edited Jul 12 at 23:22
Noah Schweber
135k10 gold badges160 silver badges305 bronze badges
answered Jul 12 at 20:50
Matt SamuelMatt Samuel
40.8k6 gold badges38 silver badges71 bronze badges
$endgroup$
add a comment |
$begingroup$
You have shown the cardinality of the real numbers is a lower bound by constructing a surjective map. You can't conclude from the fact that it is not injective that there are more rearrangements, because in order to do that you'd need to be able to show that every map is not injective.
In fact, the cardinality of the set of functions from $mathbb N$ to $mathbb N$ is an upper bound, and that is the same as that of the real numbers. So in fact there are equally many arrangements as real numbers.
In Cantor's diagonal argument, we are given an arbitrary function from the naturals to the real numbers, and the argument provides an algorithm for finding a number that the function doesn't hit. This works because it's not just one function this works for, it is every function. Therefore no function from the naturals to the real numbers is surjective.
edited Jul 12 at 23:22
Noah Schweber
135k10 gold badges160 silver badges305 bronze badges
answered Jul 12 at 20:50
Matt SamuelMatt Samuel
40.8k6 gold badges38 silver badges71 bronze badges
$endgroup$
You have shown the cardinality of the real numbers is a lower bound by constructing a surjective map. You can't conclude from the fact that it is not injective that there are more rearrangements, because in order to do that you'd need to be able to show that every map is not injective.
In fact, the cardinality of the set of functions from $mathbb N$ to $mathbb N$ is an upper bound, and that is the same as that of the real numbers. So in fact there are equally many arrangements as real numbers.
In Cantor's diagonal argument, we are given an arbitrary function from the naturals to the real numbers, and the argument provides an algorithm for finding a number that the function doesn't hit. This works because it's not just one function this works for, it is every function. Therefore no function from the naturals to the real numbers is surjective.
edited Jul 12 at 23:22
Noah Schweber
135k10 gold badges160 silver badges305 bronze badges
answered Jul 12 at 20:50
Matt SamuelMatt Samuel
40.8k6 gold badges38 silver badges71 bronze badges
edited Jul 12 at 23:22
Noah Schweber
135k10 gold badges160 silver badges305 bronze badges
edited Jul 12 at 23:22
Noah Schweber
135k10 gold badges160 silver badges305 bronze badges
edited Jul 12 at 23:22
Noah Schweber
135k10 gold badges160 silver badges305 bronze badges
135k10 gold badges160 silver badges305 bronze badges
answered Jul 12 at 20:50
Matt SamuelMatt Samuel
40.8k6 gold badges38 silver badges71 bronze badges
answered Jul 12 at 20:50
Matt SamuelMatt Samuel
40.8k6 gold badges38 silver badges71 bronze badges
answered Jul 12 at 20:50
Matt SamuelMatt Samuel
40.8k6 gold badges38 silver badges71 bronze badges
40.8k6 gold badges38 silver badges71 bronze badges
add a comment |
add a comment |
$begingroup$
If I understand the question, you want to count the rearrangements of an infinite series (they would be called permutations if the series were finite).
Each such rearrangement is characterized by a series of (integer) index numbers, right?
So you want to know the size of the set of all series of integers, right?
If nothing else, just "print out" each integer as a string of digits in base 2, and then concatenate all of the digits separated by 2s, and you get something that looks just like a real. No two series map onto the same real.
answered Jul 14 at 21:38
RodRod
1
$endgroup$
add a comment |
$begingroup$
If I understand the question, you want to count the rearrangements of an infinite series (they would be called permutations if the series were finite).
Each such rearrangement is characterized by a series of (integer) index numbers, right?
So you want to know the size of the set of all series of integers, right?
If nothing else, just "print out" each integer as a string of digits in base 2, and then concatenate all of the digits separated by 2s, and you get something that looks just like a real. No two series map onto the same real.
answered Jul 14 at 21:38
RodRod
1
$endgroup$
add a comment |
$begingroup$
If I understand the question, you want to count the rearrangements of an infinite series (they would be called permutations if the series were finite).
Each such rearrangement is characterized by a series of (integer) index numbers, right?
So you want to know the size of the set of all series of integers, right?
If nothing else, just "print out" each integer as a string of digits in base 2, and then concatenate all of the digits separated by 2s, and you get something that looks just like a real. No two series map onto the same real.
answered Jul 14 at 21:38
RodRod
1
$endgroup$
If I understand the question, you want to count the rearrangements of an infinite series (they would be called permutations if the series were finite).
Each such rearrangement is characterized by a series of (integer) index numbers, right?
So you want to know the size of the set of all series of integers, right?
If nothing else, just "print out" each integer as a string of digits in base 2, and then concatenate all of the digits separated by 2s, and you get something that looks just like a real. No two series map onto the same real.
answered Jul 14 at 21:38
RodRod
1
answered Jul 14 at 21:38
RodRod
1
answered Jul 14 at 21:38
RodRod
1
answered Jul 14 at 21:38
RodRod
1
1
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%2f3291289%2ftrying-to-find-a-flaw-in-my-proof-that-there-are-more-rearrangements-of-an-infin%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
4
$begingroup$
That doesn't prove that there are more rearrangements. It proves that there are at least as many.
$endgroup$
– Matt Samuel
Jul 12 at 20:18
5
$begingroup$
I can map the integers into themselves injectively but not bijectively (say $F(n) = 2n$), but that doesn't mean the there are more integers than there are integers. Or if you prefer, I can map the even integers onto the integers, but the odds are left over in the domain ... but you can't conclude the domain is bigger than the range. One map is not all maps!
$endgroup$
– Ned
Jul 12 at 20:18
1
$begingroup$
The cardinality of the arrangements is at most that of $mathbb N^mathbb N $. I don't know if that's bigger than $c$, but I suspect it's not.
$endgroup$
– Matt Samuel
Jul 12 at 20:26
3
$begingroup$
@wjmccann The difference in the diagonal argument is it finds an additional element no matter what the map is. It gives you a method to construct a real number that an arbitrary map doesn't hit.
$endgroup$
– Matt Samuel
Jul 12 at 20:30
2
$begingroup$
@MattSamuel There are indeed the same number of each - you can code an arbitrary function into a binary expansion (think about building strings of zeros ...).
$endgroup$
– Noah Schweber
Jul 12 at 20:46