How many permutations does a countable set have? [duplicate]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$
Patience, young "Padovan"
Is ipsum/ipsa/ipse a third person pronoun, or can it serve other functions?
Does bootstrapped regression allow for inference?
A poker game description that does not feel gimmicky
Are white and non-white police officers equally likely to kill black suspects?
Where else does the Shulchan Aruch quote an authority by name?
Information to fellow intern about hiring?
What do you call something that goes against the spirit of the law, but is legal when interpreting the law to the letter?
Why do UK politicians seemingly ignore opinion polls on Brexit?
How is it possible for user's password to be changed after storage was encrypted? (on OS X, Android)
What does it exactly mean if a random variable follows a distribution
Why is my log file so massive? 22gb. I am running log backups
Why is the design of haulage companies so “special”?
Is there a familial term for apples and pears?
What does "enim et" mean?
COUNT(*) or MAX(id) - which is faster?
Where to refill my bottle in India?
Are objects structures and/or vice versa?
Does a dangling wire really electrocute me if I'm standing in water?
How to manage monthly salary
Shall I use personal or official e-mail account when registering to external websites for work purpose?
Is it wise to focus on putting odd beats on left when playing double bass drums?
Lied on resume at previous job
What is the meaning of "of trouble" in the following sentence?
How many permutations does a countable set have? [duplicate]
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 13 hours ago
Asaf Karagila♦
308k33441774
asked 15 hours ago
Lorenzo Lorenzo
132
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♦ 13 hours ago
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 13 hours ago
Asaf Karagila♦
308k33441774
asked 15 hours ago
Lorenzo Lorenzo
132
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♦ 13 hours ago
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♦
13 hours ago
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 13 hours ago
Asaf Karagila♦
308k33441774
asked 15 hours ago
Lorenzo Lorenzo
132
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 13 hours ago
Asaf Karagila♦
308k33441774
asked 15 hours ago
Lorenzo Lorenzo
132
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 13 hours ago
Asaf Karagila♦
308k33441774
asked 15 hours ago
Lorenzo Lorenzo
132
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 13 hours ago
Asaf Karagila♦
308k33441774
edited 13 hours ago
Asaf Karagila♦
308k33441774
edited 13 hours ago
Asaf Karagila♦
308k33441774
308k33441774
asked 15 hours ago
Lorenzo Lorenzo
132
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 15 hours ago
Lorenzo Lorenzo
132
asked 15 hours ago
Lorenzo Lorenzo
132
132
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♦ 13 hours ago
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♦ 13 hours ago
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♦
13 hours ago
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♦
13 hours ago
$begingroup$
While the motivation for this question is the rearrangement theorem, the title should reflect the actual question instead.
$endgroup$
– Asaf Karagila♦
13 hours ago
$begingroup$
While the motivation for this question is the rearrangement theorem, the title should reflect the actual question instead.
$endgroup$
– Asaf Karagila♦
13 hours ago
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 15 hours ago
5xum5xum
92.2k394162
$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
15 hours ago
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
15 hours ago
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
15 hours ago
$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
15 hours ago
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
15 hours ago
|
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 15 hours ago
5xum5xum
92.2k394162
$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
15 hours ago
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
15 hours ago
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
15 hours ago
$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
15 hours ago
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
15 hours ago
|
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 15 hours ago
5xum5xum
92.2k394162
$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
15 hours ago
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
15 hours ago
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
15 hours ago
$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
15 hours ago
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
15 hours ago
|
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 15 hours ago
5xum5xum
92.2k394162
$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 15 hours ago
5xum5xum
92.2k394162
answered 15 hours ago
5xum5xum
92.2k394162
answered 15 hours ago
5xum5xum
92.2k394162
answered 15 hours ago
5xum5xum
92.2k394162
92.2k394162
$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
15 hours ago
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
15 hours ago
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
15 hours ago
$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
15 hours ago
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
15 hours ago
|
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
15 hours ago
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
15 hours ago
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
15 hours ago
$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
15 hours ago
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
15 hours ago
$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
15 hours ago
$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
15 hours ago
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
15 hours ago
$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
15 hours ago
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
15 hours ago
$begingroup$
just saying length n as in all other terms beyond n are not changed eg. (13245678...) would be of length 3
$endgroup$
– Lorenzo
15 hours ago
$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
15 hours ago
$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
15 hours ago
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
15 hours ago
$begingroup$
Ok I get it now, thanks
$endgroup$
– Lorenzo
15 hours ago
|
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♦
13 hours ago