Proof that infinite lists cannot be shuffled uniformly

55 Views Asked by At

A list with countably infinitely many entries have $\beth_1$ permutations. As such, I thought uniform probability distribution over permutations of an infinite list exists, but eventually, I found that the answer is negative. Here goes the proof attempt.

A uniform probability distribution over the product space $2^\omega$ exists. This can be implemented as an RNG producing boolean values repeatedly and lazily. In fact, for computers, all probability spaces serve as quotients of this probability space.

So what about shuffling an infinite list? Permutations of an infinite list are basically bijections between $\mathbb{N}$ and $\mathbb{N}$. Let me denote this space by $X$. If the uniform probability distribution over $X$ exists, $X$ must be a quotient space of $2^\omega$ as well.

Now for each $n \in \mathbb{N}$, let $U_n$ be the collection of elements of $X$ that sends $1$ to $n$. Now because $\{1\}$ is compact in $\mathbb{N}$ and $\{n\}$ is open in $\mathbb{N}$, each $U_n$ is subbasic open in $X$, owing to the compact-open topology.

Since each $U_n$ is disjoint from another, yet they cover $X$, $X$ is not compact. This is a contradiction because $2^\omega$ is compact and compactness is preserved under continuous images.

Is this a valid proof that infinite lists cannot be shuffled uniformly?