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?


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.

  • $\begingroup$ 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$. $\endgroup$ – hardmath Feb 24 '16 at 3:00
  • $\begingroup$ 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. $\endgroup$ – user260710 Feb 24 '16 at 3:10
  • $\begingroup$ 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. $\endgroup$ – hardmath Feb 24 '16 at 3:19
  • $\begingroup$ 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? $\endgroup$ – user260710 Feb 24 '16 at 3:26
  • 3
    $\begingroup$ I've voted to re-open. The comments give sufficient context and thoughts on the problem from the OP. $\endgroup$ – 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.

  • $\begingroup$ Do they also move a finite set of $\mathbb{N}$ if the union is infinite? $\endgroup$ – user260710 Feb 24 '16 at 0:54
  • $\begingroup$ @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$. $\endgroup$ – lhf Feb 24 '16 at 0:55
  • $\begingroup$ 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)$? $\endgroup$ – user260710 Feb 24 '16 at 0:58
  • 1
    $\begingroup$ @user260710, $x \mapsto x+1$ is not a bijection because $1$ is not in the image. $\endgroup$ – lhf Feb 24 '16 at 1:32
  • 1
    $\begingroup$ Map the odds to the primes, and the evens to the rest, I doubt that has finite order. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.