4
$\begingroup$

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?

  • 0
    @user1729: Simpler to map to $\cup\{n\}\times S_n$ the way you describe. Since this is a countable union of finite sets, it's countable, so you know $S_{\omega}$ is at most countable.2011-11-01

3 Answers 3

6

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.

6

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$ .

2

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}$.

  • 0
    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.2017-02-07