50
$\begingroup$

I guess it is too difficult a question to ask about the cardinality of $S_{\mathbb{N}}$ so I would like to ask whether it is countable or not.

I tried to prove it is uncountable somewhat mimicking the Cantor's diagonal argument but failed.

$\endgroup$
3

10 Answers 10

186
$\begingroup$

Here's a very silly argument to show $|S_\mathbb{N}| \geq 2^\mathbb{N}$.

A fact from calculus tells us that a non-absolutely convergent series whose terms converge to zero can be reordered to take the value of any real. So, for each real $\alpha$, there is a permutation such that $$ \sum\frac{(-1)^{n_i}}{n_i}= \alpha $$

So there must be at least as many permutations as reals!

$\endgroup$
3
  • 9
    $\begingroup$ Cute. You had the inequality backwards, but it was clear what you meant, so I went ahead and fixed it. $\endgroup$ Commented Jun 11, 2015 at 18:01
  • 32
    $\begingroup$ This is adorable. (+1) $\endgroup$
    – Micah
    Commented Jun 11, 2015 at 19:55
  • $\begingroup$ I guess the fact from calculus is the Riemann series theorem: en.wikipedia.org/wiki/Riemann_series_theorem $\endgroup$ Commented Apr 18, 2023 at 3:19
62
$\begingroup$

We can do a diagonal argument directly, too: Let $(\sigma_0,\sigma_1,\sigma_2,\ldots)$ be an infinite sequence of bijections $\mathbb N\to\mathbb N$. We wish to find a bijection $f$ that's not in the sequence:

Let $f$ be the bijection such that for each $k$, $f$ swaps $2k$ and $2k+1$ if $\sigma_k(2k)=2k$ and leaves them alone otherwise.

By construction $f$ is a bijection, and different from each of the $\sigma_i$s.

(Note that this argument shows less than the other answers: it only cloncludes that the cardinality of $S_{\mathbb N}$ is larger than $\aleph_0$, not that it equals $2^{\aleph_0}$.)


Note that unlike in the finite case, the group generated by all single transpositions is not the entire permutation group. Instead it is the group of all permutations "with finite support", which is countable.

$\endgroup$
0
36
$\begingroup$

$S_{\Bbb N}$ is simply the set of bijections from $\Bbb N$ to itself, which has cardinality $2^\omega=\mathfrak{c}$. (In particular, it’s uncountable.)

It’s clear that $|S_{\Bbb N}|\le\omega^\omega=2^\omega$. For the other direction, let $A$ be any infinite subset of $\Bbb N$, and enumerate $A=\{a_k:k\in\Bbb N\}$ in increasing order. Let

$$\sigma_A:\Bbb N\to\Bbb N:n\mapsto\begin{cases} a_{2k+1},&\text{if }n=a_{2k}\text{ for some }k\in\Bbb N\\ a_{2k},&\text{if }n=a_{2k+1}\text{ for some }k\in\Bbb N\\ n,&\text{if }n\in\Bbb N\setminus A\;. \end{cases}$$

$\Bbb N$ has $2^\omega$ infinite subsets, and $\sigma_A=\sigma_B$ iff $A=B$, so $|S_{\Bbb N}|\ge 2^\omega$. Thus, $|S_{\Bbb N}|=2^\omega$.

$\endgroup$
2
  • $\begingroup$ (Sorry for misreading your solution and breaking it in an attempt to "fix typos". I have rolled back). $\endgroup$ Commented Jun 11, 2015 at 17:57
  • $\begingroup$ @Henning: Not to worry: by the time I checked to see what the change was, you’d already rolled it back. $\endgroup$ Commented Jun 11, 2015 at 18:00
10
$\begingroup$

A similar argument to Brian's, but maybe slightly easier: given a set $S\subseteq\mathbb{N}$, let $\pi_S$ be the permutation which swaps $2n$ and $2n+1$ for each $n\in S$, and leaves all other numbers fixed. Then $\pi_S=\pi_{S'}\iff S=S'$, so $\vert S_\mathbb{N}\vert=2^\omega$.

What about generalizations to arbitrary infinite sets - that is, for which $A$ can we conclude that $S_A$ has cardinality $2^A$? (Assume choice fails badly, so this is nontrivial.)

  • My argument above works with any infinite set $A$ which can be put into bijection with its double $A\sqcup A$.

  • Brian's answer requires us to assume that each infinite subset of A can be written as a disjoint union of pairs. This need not be the case, e.g. if $A=X\times\omega$ for an amorphous set $X$ - one of the "rows" equal to $X$ need not be splittable into pairs (note that this $A$ can be put in bijection with $A\sqcup A$). (As written, it also requires $2^A$ to have the same cardinality as the set of infinite subsets of $A$, which is not always true, but this is easily fixable: for $X$ finite, have the associated permutation fix exactly the elements not in $X$.)

  • Moreover, Brian's argument merely produces a surjection from $S_A$ onto $2^A$, while the argument above yields an injection going the other way; in general, this is stronger. (The issue with Brian's argument is that one must choose a way of writing a given infinite $X\subseteq A$ as a disjoint union of pairs.)

  • On the other hand, the relationship between Brian's and my hypotheses is not clear. Certainly mine does not imply Brian's, but the converse may be true as well.

$\endgroup$
4
  • $\begingroup$ It is not clear to me that Brian's premise is strictly less strict -- he requires something about every infinite subset of $A$; you only need to know a property about $A$ itself. $\endgroup$ Commented Jun 11, 2015 at 18:32
  • $\begingroup$ Wow, of course you're right, and it's easy to come up with examples where Brian's premise fails and mine holds; in fact, an earlier draft of the answer contained such an example! Then I had a brain fart and decided I was wrong, and changed it. It's good now, hopefully. $\endgroup$ Commented Jun 11, 2015 at 18:37
  • $\begingroup$ Also "have the associated permutation fix exactly the elements not in $X$" implicitly assumes AC; otherwise you may not be able to choose a derangement for each finite subset uniformly. $\endgroup$ Commented Jun 11, 2015 at 18:46
  • $\begingroup$ Yes, that's basically the same issue as the splitting-into-pairs one. $\endgroup$ Commented Jun 11, 2015 at 18:47
9
$\begingroup$

The set of fixed points of any permutation $\pi\colon\mathbb{N}\to\mathbb{N}$ (i.e., the set $\{x\mid \pi(x)=x\}$) can be any subset of $\mathbb{N}$ except ones of the form $\mathbb{N}\setminus\{n\}$ for some $n$. So there are at least as many permutations as there are such subsets and there are uncountably many subsets.

Thanks to Henning Makholm for pointing out an error in the original version of this answer.

$\endgroup$
0
6
$\begingroup$

HINT:

If $\alpha$, $\beta$ are positive irrational numbers with $\frac{1}{\alpha} + \frac{1}{\beta} = 1$ then the sequence $$[\alpha], [ \beta], [ 2 \alpha], [2\beta], \ldots, [n \alpha ], [n \beta], \ldots$$ is a permutation of the numbers $1, 2, 3, \ldots$

$\bf{Added:}$ To prove (the classical result) that the sets $\{[\alpha], [2 \alpha], \ldots, \}$ and $\{[\beta], [2 \beta], \ldots, \}$ form a partition of $\{1, 2, \ldots\}$ , it is enough to show that for all $n\ge 1$ we have $$ \left |\,\{[\alpha], [2 \alpha], \ldots \} \cap \{1, 2, \ldots n\}\,\right| + \left |\,\{[\beta], [2 \beta], \ldots \} \cap \{1, 2, \ldots n\}\,\right|= n$$ that is: $$\left[ \frac{n+1}{\alpha}\right]+ \left[ \frac{n+1}{\beta}\right]=n$$ true because the non-integers $\frac{n+1}{\alpha}$, $\frac{n+1}{\beta}$ sum up to $n+1$.

$\endgroup$
4
  • 1
    $\begingroup$ This is harder to prove than the original claim (and still requires showing that these sequences are distinct), but it's still a cute approach to the problem. $\endgroup$ Commented Jun 12, 2015 at 21:02
  • $\begingroup$ Thanks. $\frac{u_{2n+1}}{u_{2n}} \to \frac{\alpha}{\beta}$ so the permutation produces back the pair $(\alpha, \beta)$. $\endgroup$
    – orangeskid
    Commented Jun 13, 2015 at 0:53
  • 1
    $\begingroup$ It is easy enough to see that the sequence uniquely determines $\alpha$ and $\beta$, but less obvious that it is a permutation of the naturals. Is $[x]$ round-to-nearest or the floor function? $\endgroup$ Commented Jun 13, 2015 at 13:34
  • $\begingroup$ @Henning Makholm: Yes, correct, the integer part. I forgot the author of this cute result, expected to find it in Polya & Szego. Just added a proof. $\endgroup$
    – orangeskid
    Commented Jun 14, 2015 at 6:07
5
$\begingroup$

Let me add another proof just for fun:

Enumerate the rationals $\mathbb Q = \{ q_n \mid n \in \mathbb N \}$ and consider $$ f : S_{\mathbb N} \rightarrow \mathbb R, \ \sigma \mapsto \begin{cases} \lim_{n \rightarrow \infty} q_{\sigma(2n)}, \text{ if this limit exists} \\ 0, \text{ otherwise} \end{cases} $$

Then $f$ is surjective as every real can be written as the limit of pairwise distinct rationals and thus $S_\mathbb N$ has size at least continuum. On the other hand $|S_\mathbb N| \le | \mathbb N ^\mathbb N | = |2^\mathbb N|$ and therefore $S_\mathbb N$ has size of the continuum.

$\endgroup$
2
$\begingroup$

HINT: For a sequence in $q = (q_n) \in \{1,2\}^{\mathbb{Z}}$ consider the continuous piecewise linear function $\phi_q$, $0 \overset{\phi_q}{\mapsto} 0$, with slope $q_n$ on the interval $[n,n+1]$, giving a monotone permutation of $\mathbb{Q}$.

$\endgroup$
1
$\begingroup$

Here is a slightly analytic approach, that I think isn't too similar to what anyone else has written.

Since $\mathbb Q$ is countably infinite, it suffices to show that there are uncountably many bijections $\mathbb Q \to \mathbb Q$. We exhibit an injection $\mathbb R_{>0} \to S_{\mathbb Q}$.

Given a positive real $\alpha > 0$, define \begin{align*} f_\alpha: \mathbb Q &\to \mathbb Q \\ q &\mapsto \begin{cases} q & \text{if $\lvert q \rvert \le \alpha$} \\ -q & \text{if $\lvert q \rvert > \alpha$} \end{cases} \end{align*} Then $f_\alpha$ is an involution, so certainly a bijection.

Moreover, it is clear that $\sup \{q \in \mathbb Q \mid f_\alpha(q) = q\} = \alpha$. This shows that $\alpha \mapsto f_\alpha$ is an injection. So indeed $S_{\mathbb Q}$ is uncountable.

I personally like this proof a lot. I find it much more intuitive when things end up being uncountable "because of $\mathbb Q$", and particularly when it's because of a Dedekind-cut-like density-related construction like this, than when it's because of a diagonal argument.

(fun fact: the set of all bijections in $S_{\mathbb N}$ having no fixed points is also uncountable!)

$\endgroup$
1
$\begingroup$

You can prove this easily via diagonal argument. Let's start with supposing that $\mathrm{Aut}(\mathbb{N})$ is countable. Then we can list such automorphisms: $\forall j: \pi_{j} \in \mathrm{Aut}(\mathbb{N})$. In table: $$\begin{array}{ccc} \pi_{1}(1) & \pi_{1}(2)&\dots\\ \pi_{2}(1) & \pi_{2}(2)&\dots \\ \vdots &\vdots&\ddots& \end{array}$$ Now consider automorphism $\pi_{j}$ such that $\forall k\in\mathbb{N} \Rightarrow \pi_{j}(k)\neq k$ (i.e. without fixed points). It is pretty easy to construct though: divide numbers into groups of, say, four numbers (it must be an even number!) and reverse the order (you get $4,3,2,1,8,7,6,5,\dots$) Now consider permutation $\delta=\pi_{1}(1)\pi_{2}(2)\dots$ (consisting of diagonal elements). Now it is easy to see that permutations $\delta$ and $\delta\circ \pi_{j}$ are different ($\forall i \in\mathbb{N}\Rightarrow \pi_{j}(i)\neq (\delta\circ\pi_{j})(i)$). Indeed, permutations $a$ and $a\circ b$ are equal at some point iff $b$ has fixed point. Here is contradiction: permutation $\delta\circ \pi_{j}$ coincides with $\delta$ on a diagonal.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .