Is symmetric group on natural numbers countable? 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.
 A: 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.
A: 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.
A: 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, \}$ are a partition of $\{1, 2, \ldots\}$ it's enough to show ( think characteristic functions and integration) that 
$$ \left |\{[\alpha], [2 \alpha], \ldots, \} \cap \{1, 2, \ldots n\}\right| + \left |\{\beta, 2 \beta, \ldots, \} \cap \{1, 2, \ldots n\}\right|= n$$
for all $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$.
A: 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.
A: $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$.
A: 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}$. 
A: 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!
A: 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.
A: 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!)
A: 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.
