# Show that $H = \bigcup_{n > 0} S_n$ is not equal to Sym$(X)$ for $X = \{1,2,3,4,…\}$.

Let $X = \{1,2,3...\}$ be the set of positive natural numbers, $S_n$ the permutation group, and Sym$(X)$ the set of all bijections from X to X with operation composition. I have the following questions.

1) How do I show that $H = \bigcup_{n > 0} S_n$ is a subgroup of Sym$(X)$, or how do I interpret this being a subgroup (in terms of compositions of bijections??).

2) How do I show that $H$ and Sym$(X)$ are not equal?

EDIT:

1) I have problems with the subgroup properties.

First property. The identity element of $S_2$ is not equal to the identity element of $S_4$ for example. I see that both are bijective functions such that $f(x) = x$. But $S_2$ sends $(12) \to (12)$, but does nothing with $(1234)$, it's not in its domain? So how do I prove that there exists a $id_f \in H$, such that $id_f$ in all $S_n$, and that this one equals the one in $Sym(X)$.

Second property. If $a,b \in \bigcup_{n > 0} S_n$, then $a,b \in S_i$ for some $i \leq n$, and thus $ab \in S_i$, and thus $ab \in \bigcup_{n > 0} S_n$. But what if $a$ and $b$ are not in the same $S_i$? I can only assume that the union of subgroups is a subgroup if $S_1 \subset S_2 \subset ... \subset S_n$.

Third property. This one is easy.

2) At first I was confused because I thought that you can always find enough bijective functions in $H$. But each $S_n \in H$ has finite order, and thus works on finitely many elements in $\mathbb{N}$. Thus a function $f \in Sym(X)$ that works on all $x \in \mathbb{N}$ cannot be in $H$, even though (I believe) all $f \in Sym(X)$ have finite order too... I think I understand this part now.

• Backing up a step, is it clear to you that $Sym(X)$ is a group with respect to function composition? After you grasp that, it should be clear that the $S_n$ are a nested family of subgroups. You can even come up with a very compact description of what portion of $Sym(X)$ is covered by the union of the $S_n$. – hardmath Feb 24 '16 at 3:00
• Yes, I have no problem at all understanding that Sym(X) is a group with respect to function composition. I just can't grasp how the union of infinite $S_n$ does not cover everything in $Sym(X)$... The infinite part is what makes it confusing. – user260710 Feb 24 '16 at 3:10
• The "infinite part" is exactly the key you need to spot that the $S_n$ don't cover everything. Pick out a bijection in $Sym(X)$ that moves infinitely many of the positive natural numbers in $X$. Ask yourself if it can be in any of the $S_n$ subgroups. – hardmath Feb 24 '16 at 3:19
• But there are infinitely many subgroups, why can't there be one in which there are infinitely many positive numbers moved? Where am I making a mistake in my thought process? – user260710 Feb 24 '16 at 3:26
• I've voted to re-open. The comments give sufficient context and thoughts on the problem from the OP. – Lee Mosher Feb 24 '16 at 13:11

Hint: Note that $H$ is the set of permutations of $X$ that have finite support in the sense that they move just a finite subset of $X$ and fix the rest.

The hint proves both points:

1. If $\sigma, \tau$ have finite support than so do $\sigma^{-1}$ and $\sigma\tau$. The identity clearly has finite support.

2. Not all permutations of $X$ have finite support. For instance, the one that swaps even and odd numbers does not.

• Do they also move a finite set of $\mathbb{N}$ if the union is infinite? – user260710 Feb 24 '16 at 0:54
• @user260710. yes because each element in $H$ belongs to some $S_n$. And $S_n \subset Sym(X)$ by fixing every number greater than $n$. – lhf Feb 24 '16 at 0:55
• I don't think I fully understand your hint. Because how do I know that there does not exist a $S_n$ for every element in Sym$(X)$? – user260710 Feb 24 '16 at 0:58
• @user260710, $x \mapsto x+1$ is not a bijection because $1$ is not in the image. – lhf Feb 24 '16 at 1:32
• Map the odds to the primes, and the evens to the rest, I doubt that has finite order. – Justin Young Feb 24 '16 at 15:36

Consider any bijection of $X$ without fixed points. It is clear it cannot be in any of the $S_n$, since all these permutations have infinite fixed points when viewed as bijections of $X$. This proves the second claim.

For the first one, if you want to put a group structure on $\cup S_n$, you have to consider the canonical injections $i^m_n : S_m \to S_n$ $(m<n)$ that sends a permutation in the same permutation fixing all the excess points. When you do the union, you're viewing any element of $\cup S_n$ as an equivalence class where $w = \sigma$ if there is some $n,m$ such that $w=i^m_n ( \sigma)$ or $\sigma=i^m_n (w)$.
This is a complicate way to say that you're essentially considering $S_{i-1} \subset S_i$.

Now for any two elements $w, \sigma$ in $\cup S_n$ you have that $w \in S_k$, $\sigma \in S_h$ for some $h,k$. Suppose wlog $h<k$ and define $\sigma \circ w$ as $i^h_k(\sigma) \circ w \in S_k$.
It follows that the identity element is $i^1_n(\operatorname{id})$ for any $n$.