How many permutations does a countable set have? [duplicate] Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Is symmetric group on natural numbers countable?Prove why this algorithm to compute all list permutations worksLooks like we picked the wrong theorem to popularize (Cantor diagonalization)Can someone please clarify combinations vs permutations?Mapping from reals to naturals if naturals can be used infinitely many timesWhy are positive rational numbers countable but real numbers are not?Is there a model of ZFC in which every real number is definable?Series that converge to every real number via permutationSeries and ConsistencyThe set of all digits in a real numberExplicit bijection between $Bbb R$ and permutations of $Bbb N$
Complexity of many constant time steps with occasional logarithmic steps
Was credit for the black hole image misattributed?
Why use gamma over alpha radiation?
Simulating Exploding Dice
Can't figure this one out.. What is the missing box?
Estimate capacitor parameters
Losing the Initialization Vector in Cipher Block Chaining
I'm having difficulty getting my players to do stuff in a sandbox campaign
Why don't the Weasley twins use magic outside of school if the Trace can only find the location of spells cast?
What LEGO pieces have "real-world" functionality?
What items from the Roman-age tech-level could be used to deter all creatures from entering a small area?
Strange behaviour of Check
Passing functions in C++
What was the last x86 CPU that did not have the x87 floating-point unit built in?
What's the point in a preamp?
Why is there no army of Iron-Mans in the MCU?
What to do with post with dry rot?
Is above average number of years spent on PhD considered a red flag in future academia or industry positions?
How to market an anarchic city as a tourism spot to people living in civilized areas?
How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time
Can a monk deflect thrown melee weapons?
A constraint that implies convexity
What's the difference between (size_t)-1 and ~0?
Would an alien lifeform be able to achieve space travel if lacking in vision?
How many permutations does a countable set have? [duplicate]
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Is symmetric group on natural numbers countable?Prove why this algorithm to compute all list permutations worksLooks like we picked the wrong theorem to popularize (Cantor diagonalization)Can someone please clarify combinations vs permutations?Mapping from reals to naturals if naturals can be used infinitely many timesWhy are positive rational numbers countable but real numbers are not?Is there a model of ZFC in which every real number is definable?Series that converge to every real number via permutationSeries and ConsistencyThe set of all digits in a real numberExplicit bijection between $Bbb R$ and permutations of $Bbb N$
$begingroup$
This question already has an answer here:
Is symmetric group on natural numbers countable?
8 answers
I have just come across the Riemann Rearrangement theorem and, from what I understand, it shows that any real can be written as a permutation of a conditionally convergent series. The problem I have is that permutations of an infinite series are countably infinite, so in theory one could list all possible permutations of the series which would be equivalent to listing all real numbers. But reals are uncountable.
This seems like a contradiction to me, where am I wrong?
permutations real-numbers
edited Apr 8 at 12:38
Asaf Karagila♦
308k33441775
asked Apr 8 at 10:53
Lorenzo Lorenzo
184
New contributor
Lorenzo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
marked as duplicate by Asaf Karagila♦ Apr 8 at 12:37
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:
Is symmetric group on natural numbers countable?
8 answers
I have just come across the Riemann Rearrangement theorem and, from what I understand, it shows that any real can be written as a permutation of a conditionally convergent series. The problem I have is that permutations of an infinite series are countably infinite, so in theory one could list all possible permutations of the series which would be equivalent to listing all real numbers. But reals are uncountable.
This seems like a contradiction to me, where am I wrong?
permutations real-numbers
edited Apr 8 at 12:38
Asaf Karagila♦
308k33441775
asked Apr 8 at 10:53
Lorenzo Lorenzo
184
New contributor
Lorenzo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
marked as duplicate by Asaf Karagila♦ Apr 8 at 12:37
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$
While the motivation for this question is the rearrangement theorem, the title should reflect the actual question instead.
$endgroup$
– Asaf Karagila♦
Apr 8 at 12:38
add a comment |
$begingroup$
This question already has an answer here:
Is symmetric group on natural numbers countable?
8 answers
I have just come across the Riemann Rearrangement theorem and, from what I understand, it shows that any real can be written as a permutation of a conditionally convergent series. The problem I have is that permutations of an infinite series are countably infinite, so in theory one could list all possible permutations of the series which would be equivalent to listing all real numbers. But reals are uncountable.
This seems like a contradiction to me, where am I wrong?
permutations real-numbers
edited Apr 8 at 12:38
Asaf Karagila♦
308k33441775
asked Apr 8 at 10:53
Lorenzo Lorenzo
184
New contributor
Lorenzo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
This question already has an answer here:
Is symmetric group on natural numbers countable?
8 answers
I have just come across the Riemann Rearrangement theorem and, from what I understand, it shows that any real can be written as a permutation of a conditionally convergent series. The problem I have is that permutations of an infinite series are countably infinite, so in theory one could list all possible permutations of the series which would be equivalent to listing all real numbers. But reals are uncountable.
This seems like a contradiction to me, where am I wrong?
This question already has an answer here:
Is symmetric group on natural numbers countable?
8 answers
permutations real-numbers
permutations real-numbers
edited Apr 8 at 12:38
Asaf Karagila♦
308k33441775
asked Apr 8 at 10:53
Lorenzo Lorenzo
184
New contributor
Lorenzo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Apr 8 at 12:38
Asaf Karagila♦
308k33441775
asked Apr 8 at 10:53
Lorenzo Lorenzo
184
New contributor
Lorenzo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Apr 8 at 12:38
Asaf Karagila♦
308k33441775
edited Apr 8 at 12:38
Asaf Karagila♦
308k33441775
edited Apr 8 at 12:38
Asaf Karagila♦
308k33441775
308k33441775
asked Apr 8 at 10:53
Lorenzo Lorenzo
184
New contributor
Lorenzo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Apr 8 at 10:53
Lorenzo Lorenzo
184
asked Apr 8 at 10:53
Lorenzo Lorenzo
184
184
New contributor
Lorenzo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Lorenzo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Lorenzo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
marked as duplicate by Asaf Karagila♦ Apr 8 at 12:37
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♦ Apr 8 at 12:37
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$
While the motivation for this question is the rearrangement theorem, the title should reflect the actual question instead.
$endgroup$
– Asaf Karagila♦
Apr 8 at 12:38
add a comment |
$begingroup$
While the motivation for this question is the rearrangement theorem, the title should reflect the actual question instead.
$endgroup$
– Asaf Karagila♦
Apr 8 at 12:38
$begingroup$
While the motivation for this question is the rearrangement theorem, the title should reflect the actual question instead.
$endgroup$
– Asaf Karagila♦
Apr 8 at 12:38
$begingroup$
While the motivation for this question is the rearrangement theorem, the title should reflect the actual question instead.
$endgroup$
– Asaf Karagila♦
Apr 8 at 12:38
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Permutations of an infinite series are not countably infinite, so there is no contradiction.
The set of permutations of an infinite series is the set of all bijections from $mathbb N$ to $mathbb N$, which is an uncountably infinite set. For one, the Riemann theorem you state can be used to prove that it is uncountable, or, more set-theoretically, a variant of the diagonal argument can be used, as in this post
answered Apr 8 at 10:57
5xum5xum
92.6k394162
$endgroup$
$begingroup$
Ok that makes sense, but I thought one could list all permutations by having permutations of different 'lengths' n (that permutate only the first n terms, where all permutations of length n are finite) and then listing each one after the other ie all permutations of length 1, all permutations of length 2 etc.
$endgroup$
– Lorenzo
Apr 8 at 11:07
1
$begingroup$
@Lorenzo There is no "length" to speak of here. Each permutation is a permutation of "infinite" length, if you will. It is a rearangement of the entire set $mathbb N$.
$endgroup$
– 5xum
Apr 8 at 11:08
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
Apr 8 at 11:12
$begingroup$
@Lorenzo For example, when, in your listing, to you list the permutation that maps $1$ to $2$, $2$ to $1$, $3$ to $4$, $4$ to $3$, $2k-1$ to $2k$ and $2k$ to $2k-1$?. There is no $n$ at which all terms beyond $n$ are unchanged! Every integer gets moved either one up or one down.
$endgroup$
– 5xum
Apr 8 at 11:13
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
Apr 8 at 11:20
|
show 1 more comment
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Permutations of an infinite series are not countably infinite, so there is no contradiction.
The set of permutations of an infinite series is the set of all bijections from $mathbb N$ to $mathbb N$, which is an uncountably infinite set. For one, the Riemann theorem you state can be used to prove that it is uncountable, or, more set-theoretically, a variant of the diagonal argument can be used, as in this post
answered Apr 8 at 10:57
5xum5xum
92.6k394162
$endgroup$
$begingroup$
Ok that makes sense, but I thought one could list all permutations by having permutations of different 'lengths' n (that permutate only the first n terms, where all permutations of length n are finite) and then listing each one after the other ie all permutations of length 1, all permutations of length 2 etc.
$endgroup$
– Lorenzo
Apr 8 at 11:07
1
$begingroup$
@Lorenzo There is no "length" to speak of here. Each permutation is a permutation of "infinite" length, if you will. It is a rearangement of the entire set $mathbb N$.
$endgroup$
– 5xum
Apr 8 at 11:08
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
Apr 8 at 11:12
$begingroup$
@Lorenzo For example, when, in your listing, to you list the permutation that maps $1$ to $2$, $2$ to $1$, $3$ to $4$, $4$ to $3$, $2k-1$ to $2k$ and $2k$ to $2k-1$?. There is no $n$ at which all terms beyond $n$ are unchanged! Every integer gets moved either one up or one down.
$endgroup$
– 5xum
Apr 8 at 11:13
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
Apr 8 at 11:20
|
show 1 more comment
$begingroup$
Permutations of an infinite series are not countably infinite, so there is no contradiction.
The set of permutations of an infinite series is the set of all bijections from $mathbb N$ to $mathbb N$, which is an uncountably infinite set. For one, the Riemann theorem you state can be used to prove that it is uncountable, or, more set-theoretically, a variant of the diagonal argument can be used, as in this post
answered Apr 8 at 10:57
5xum5xum
92.6k394162
$endgroup$
$begingroup$
Ok that makes sense, but I thought one could list all permutations by having permutations of different 'lengths' n (that permutate only the first n terms, where all permutations of length n are finite) and then listing each one after the other ie all permutations of length 1, all permutations of length 2 etc.
$endgroup$
– Lorenzo
Apr 8 at 11:07
1
$begingroup$
@Lorenzo There is no "length" to speak of here. Each permutation is a permutation of "infinite" length, if you will. It is a rearangement of the entire set $mathbb N$.
$endgroup$
– 5xum
Apr 8 at 11:08
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
Apr 8 at 11:12
$begingroup$
@Lorenzo For example, when, in your listing, to you list the permutation that maps $1$ to $2$, $2$ to $1$, $3$ to $4$, $4$ to $3$, $2k-1$ to $2k$ and $2k$ to $2k-1$?. There is no $n$ at which all terms beyond $n$ are unchanged! Every integer gets moved either one up or one down.
$endgroup$
– 5xum
Apr 8 at 11:13
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
Apr 8 at 11:20
|
show 1 more comment
$begingroup$
Permutations of an infinite series are not countably infinite, so there is no contradiction.
The set of permutations of an infinite series is the set of all bijections from $mathbb N$ to $mathbb N$, which is an uncountably infinite set. For one, the Riemann theorem you state can be used to prove that it is uncountable, or, more set-theoretically, a variant of the diagonal argument can be used, as in this post
answered Apr 8 at 10:57
5xum5xum
92.6k394162
$endgroup$
Permutations of an infinite series are not countably infinite, so there is no contradiction.
The set of permutations of an infinite series is the set of all bijections from $mathbb N$ to $mathbb N$, which is an uncountably infinite set. For one, the Riemann theorem you state can be used to prove that it is uncountable, or, more set-theoretically, a variant of the diagonal argument can be used, as in this post
answered Apr 8 at 10:57
5xum5xum
92.6k394162
answered Apr 8 at 10:57
5xum5xum
92.6k394162
answered Apr 8 at 10:57
5xum5xum
92.6k394162
answered Apr 8 at 10:57
5xum5xum
92.6k394162
92.6k394162
$begingroup$
Ok that makes sense, but I thought one could list all permutations by having permutations of different 'lengths' n (that permutate only the first n terms, where all permutations of length n are finite) and then listing each one after the other ie all permutations of length 1, all permutations of length 2 etc.
$endgroup$
– Lorenzo
Apr 8 at 11:07
1
$begingroup$
@Lorenzo There is no "length" to speak of here. Each permutation is a permutation of "infinite" length, if you will. It is a rearangement of the entire set $mathbb N$.
$endgroup$
– 5xum
Apr 8 at 11:08
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
Apr 8 at 11:12
$begingroup$
@Lorenzo For example, when, in your listing, to you list the permutation that maps $1$ to $2$, $2$ to $1$, $3$ to $4$, $4$ to $3$, $2k-1$ to $2k$ and $2k$ to $2k-1$?. There is no $n$ at which all terms beyond $n$ are unchanged! Every integer gets moved either one up or one down.
$endgroup$
– 5xum
Apr 8 at 11:13
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
Apr 8 at 11:20
|
show 1 more comment
$begingroup$
Ok that makes sense, but I thought one could list all permutations by having permutations of different 'lengths' n (that permutate only the first n terms, where all permutations of length n are finite) and then listing each one after the other ie all permutations of length 1, all permutations of length 2 etc.
$endgroup$
– Lorenzo
Apr 8 at 11:07
1
$begingroup$
@Lorenzo There is no "length" to speak of here. Each permutation is a permutation of "infinite" length, if you will. It is a rearangement of the entire set $mathbb N$.
$endgroup$
– 5xum
Apr 8 at 11:08
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
Apr 8 at 11:12
$begingroup$
@Lorenzo For example, when, in your listing, to you list the permutation that maps $1$ to $2$, $2$ to $1$, $3$ to $4$, $4$ to $3$, $2k-1$ to $2k$ and $2k$ to $2k-1$?. There is no $n$ at which all terms beyond $n$ are unchanged! Every integer gets moved either one up or one down.
$endgroup$
– 5xum
Apr 8 at 11:13
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
Apr 8 at 11:20
$begingroup$
Ok that makes sense, but I thought one could list all permutations by having permutations of different 'lengths' n (that permutate only the first n terms, where all permutations of length n are finite) and then listing each one after the other ie all permutations of length 1, all permutations of length 2 etc.
$endgroup$
– Lorenzo
Apr 8 at 11:07
$begingroup$
Ok that makes sense, but I thought one could list all permutations by having permutations of different 'lengths' n (that permutate only the first n terms, where all permutations of length n are finite) and then listing each one after the other ie all permutations of length 1, all permutations of length 2 etc.
$endgroup$
– Lorenzo
Apr 8 at 11:07
1
1
$begingroup$
@Lorenzo There is no "length" to speak of here. Each permutation is a permutation of "infinite" length, if you will. It is a rearangement of the entire set $mathbb N$.
$endgroup$
– 5xum
Apr 8 at 11:08
$begingroup$
@Lorenzo There is no "length" to speak of here. Each permutation is a permutation of "infinite" length, if you will. It is a rearangement of the entire set $mathbb N$.
$endgroup$
– 5xum
Apr 8 at 11:08
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
Apr 8 at 11:12
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
Apr 8 at 11:12
$begingroup$
@Lorenzo For example, when, in your listing, to you list the permutation that maps $1$ to $2$, $2$ to $1$, $3$ to $4$, $4$ to $3$, $2k-1$ to $2k$ and $2k$ to $2k-1$?. There is no $n$ at which all terms beyond $n$ are unchanged! Every integer gets moved either one up or one down.
$endgroup$
– 5xum
Apr 8 at 11:13
$begingroup$
@Lorenzo For example, when, in your listing, to you list the permutation that maps $1$ to $2$, $2$ to $1$, $3$ to $4$, $4$ to $3$, $2k-1$ to $2k$ and $2k$ to $2k-1$?. There is no $n$ at which all terms beyond $n$ are unchanged! Every integer gets moved either one up or one down.
$endgroup$
– 5xum
Apr 8 at 11:13
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
Apr 8 at 11:20
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
Apr 8 at 11:20
|
show 1 more comment
$begingroup$
While the motivation for this question is the rearrangement theorem, the title should reflect the actual question instead.
$endgroup$
– Asaf Karagila♦
Apr 8 at 12:38