This problem is from Dummit and Foote, 1.3.8:

Prove that if $\Omega=\{1,2,3,\cdots \}$ then $S_{\Omega}$ is an infinite group(do not say $\infty !=\infty$).

I was thinking arguing that since $\forall n\in \mathbb{N}$, $|S_{n}|=n!$, then as $n\rightarrow \infty, |S_{\Omega}|\rightarrow \infty$. I think this makes sense intuitively, but is it rigorous enough?

  • 4
    $\begingroup$ The problem with your argument is you are assuming that $S_\Omega$ is at least as big as each $S_n$, but at some point you need to directly analyze $S_\Omega$. So you might as well forget $S_n$ and directly think about $S_\Omega$. Then you just need to find infinitely many permutations of $\Omega$ and you're done. You can pick easy ones... $\endgroup$ – Cheerful Parsnip Oct 18 '11 at 5:19
  • 10
    $\begingroup$ You should first realize all the finite groups $S_n$ as subgroups of $S_\Omega$. This is easy: extend an element $\sigma$ of $S_n$ to an element of $S_\Omega$ by defining $\sigma(k)=k$ for all $k>n$. Then you can proceed according to your plan, and derive a contradiction from the contrapositive assumption that $|S_\Omega|$ would be finite. Too bad that you didn't choose $\Omega=\{0,1,2,\ldots\}$. Then you could follow Jim's suggestion e.g. by bitwise XORing with an arbitrary integer, and produce at least $|\Omega|$ distinct permutations :-) $\endgroup$ – Jyrki Lahtonen Oct 18 '11 at 5:34
  • 5
    $\begingroup$ Let $\sigma\in S_n$ (where $S_n$ is the permutation group on $n$ letters) and define $\overline{\sigma}\in S_{\Omega}$ by the rule $\overline{\sigma}(i)=\sigma(i)$ if $1\leq i\leq n$ and $\overline{\sigma}(i)=i$ if $i>n$. If $f_n:S_n\to S_{\Omega}$ is defined by $f_n(\sigma)=\overline{\sigma}$, then prove that $f_n:S_n\to S_{\Omega}$ is injective. In particular, $\left|S_{\Omega}\right|\geq n!$ for all positive integers $n$ and thus $S_{\Omega}$ is an infinite set. $\endgroup$ – Amitesh Datta Oct 18 '11 at 5:39
  • 1
    $\begingroup$ @Jyrki I think we began writing our comments at the same time because I have given a virtually identical argument in my comment! $\endgroup$ – Amitesh Datta Oct 18 '11 at 5:42
  • 2
    $\begingroup$ Note that there are two common interpretations for $S_{\Omega}$ when $\Omega$ is infinite: it can be the group of all bijections $\Omega\to\Omega$, or it can be the group of all permutations "of finite support" (that is, all bijections $\sigma\colon\Omega\to\Omega$ such that $\{x\in\Omega\mid \sigma(x)\neq x\}$ is finite). Doesn't affect the answer here, because the latter is already infinite, but is a good idea to specify which one you mean (just like one should always say if $D_{2k}$ means the dihedral group of order $2k$, or the dihedral group of degree $2k$). $\endgroup$ – Arturo Magidin Nov 1 '11 at 16:35

Nope. Unfortunately, what you have written is not rigorous enough. Here is an argument. (In general, whenever you want to prove that some set is infinite, assume it is finite and using the elements construct another element which is not in the set. This is in the spirit of Euclid's argument for infinitude of primes.)

Let $S_{\Omega} = \{f: \Omega \rightarrow \Omega | f \text{ is bijective}\}$. We shall first prove that $S_{\Omega}$ is an infinite set. Assume that $S_{\Omega}$ has only finitely many elements, say $N$ of them. Let them be $f_1,f_2,\ldots,f_N$. We shall denote each $f_k$ as follows. $$f_k = \{a_{k1},a_{k2},\ldots,a_{kn},\ldots \}$$ where $a_{kl} = f_k(l)$. We then have the following.

$\begin{array}{ccc} f_1 & = & \{a_{11},a_{12},a_{13},\ldots,a_{1N},\ldots\}\\ f_2 & = & \{a_{21},a_{22},a_{23},\ldots,a_{2N},\ldots\}\\ f_3 & = & \{a_{31},a_{32},a_{33},\ldots,a_{3N},\ldots\}\\ \vdots & \vdots & \vdots \\ f_N & = & \{a_{N1},a_{N2},a_{N3},\ldots,a_{NN},\ldots\}\\ \end{array}$

Let $M = \max \{a_{11},a_{22},a_{33},\ldots,a_{NN}\}$. We shall now construct a $f$ which is a bijection from $\Omega$ to $\Omega$ but doesn't match with any of the $f_k$'s above. $$f(m) = \left \{ \begin{array}{lr} M+m & m \in \{1,2,\ldots,M\}\\ m-M & m \in \{M+1,M+2,\ldots,2M\}\\ m & m \geq 2M+1 \end{array} \right.$$ Clearly, $f$ is a bijection from $\Omega$ to $\Omega$. In-fact, the inverse of $f$ is itself. It is also easy to check that $f$ doesn't match with any of the $f_k$'s. If $f$ were to match with $f_k$ for some $k$, then we must have $f_k(k) = f(k)$. However, we have that $f_k(k) = a_{kk} \leq M < M+k = f(k)$. Hence, $f$ doesn't match with any of the listed $f_k$'s. This is true for any $N \in \mathbb{N}$. Hence, the set $S_{\Omega}$ is an infinite set.

Now we need to prove that $S_{\Omega}$ is a group.

Consider $f_1,f_2 \in S_{\Omega}$. Let $f = f_1 \circ f_2$. If we have $f_1( f_2 (a_1)) = f_1( f_2 (a_2))$, then since $f_1$ is a injective, we have $f_2(a_1) = f_2(a_2)$ and since $f_2$ is a injective, we get $a_1 = a_2$. Hence, $f_1 \circ f_2$ is injective. Given any $c \in \{1,2,3,\ldots\}$, since $f_1$ is surjective, $\exists b \in \{1,2,3,\ldots\}$ such that $f_1(b) = c$. Since $f_2$ is surjective, $\exists a \in \{1,2,3,\ldots\}$ such that $f_2(a) = b$. Hence, $\exists a \in \{1,2,3,\ldots\}$ such that $f_1(f_2(a)) = c$. Hence, $S_{\Omega}$ is closed under function compositions.

The associativity follows from the fact that composition of functions is associative.

The map $f(n) = n$, $\forall n \in \Omega$ acts as the identity map since for any $g \in S_{\Omega}$, we have $g(f(n)) = g(n)$ and $f(g(n)) = g(n)$.

For any $f \in S_{\Omega}$, since $f$ is a bijection, there exists an inverse map, $g$, which is also a bijection and hence $g \in S_{\Omega}$. Hence, any element in $S_{\Omega}$ has an inverse.

Hence, $S_{\Omega}$ is a group under function compositions.

| cite | improve this answer | |

Your argument as at stands is intuitive, but incorrect. What does it mean for a sequence of groups to converge (in this context)? Also, there is no proof that the size of 'the limit group' is the limit of the sizes of the groups which converge to that limit.

One way to fix your argument is as follows. For every $n$, $S_n$ is a (or is isomorphic to) as subgroup of $S_\Omega$). Hence $|S_n| \leq | S_\Omega |$ for every $n$. This implies that $S_\Omega$ is infinite (why?). The key idea here is to use the notion of subset/subgroup to compare size, not just plain old natural numbers.

Another proof can be found if you can pick distinct elements $g_i \in S_\Omega$, one for each $i \in \mathbb{N}$. But this is easy, just consider transpositions, there are plenty: $(1\; 2),(2\; 3),(3\; 4) \dots$ .

| cite | improve this answer | |

To give a simple answer you can just say that the cycle $(1,n)$ that permutes $1$ and $n$ is in $S_{\Omega}$ for every $n\in \Omega$. As $\Omega$ is infinite so is $S_{\Omega}$.

| cite | improve this answer | |
  • $\begingroup$ I particularly like this answer because it is succinct and goes hand-in-hand pretty well with discussed topics in Dummit and Foote. Particularly, they open up the section on permutation groups by saying that for any nonempty $\Omega$, $S_\Omega$ is a group under function composition (and write out the proof). Hence you may skip checking that $S_\Omega$ is a group by just citing the first paragraph. However, if you do not know that $S_\Omega$ is a group, you would need to prove that yourself, and you may look to the chosen answer for this question. $\endgroup$ – Decaf-Math Feb 7 '17 at 5:37

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.