1
$\begingroup$

I don't think I quite get what the question is looking for. I wonder if anyone could point my attempt to the right track?

Prove that if $\Omega = \{1,2,3,\dots\}$ then $S_\Omega$ is an infinite group.

Assume for contradiction that the set of all permutations, $S_\Omega$ is finite, then it must be the permutations of a finite set $A \bf =\{1,2,\dots, n\}$ of permutations with finite members . But since $\Omega$ is infinite, $\exists p \in \Omega$ but $p \notin A$, such as, $\bf p = n+1$. So here's the contradiction, since we assumed $S_\Omega$ to contains all the permutations on $\bf \Omega$. If $p$ is not in $\bf A$, it does not participate the permutation, $S_\Omega$ can not contain all the permutation.

$\endgroup$
  • $\begingroup$ Oh it was made explicit that we can't prove by $\infty! = \infty$ @anon. $\endgroup$ – Tumbleweed Sep 7 '13 at 20:52
  • 1
    $\begingroup$ Is $A$ a set of permutations, or a subset of $\Omega$? You seem to conflate the two. What does it mean for $p$ to "participate" in the permutation, and what is "the" permutation? Why not just exhibit an infinite set of distinct permutations in $S_\Omega$? $\endgroup$ – anon Sep 7 '13 at 20:53
  • $\begingroup$ Hi @anon, yeah I realized my writing was pretty messy. Thank you for pointing that out and I have tried to improve it. Does it make sense now? $\endgroup$ – Tumbleweed Sep 7 '13 at 22:06
  • $\begingroup$ "If $S_\Omega$ is finite, then it must be the permutations of a finite set" - and how does that follow? (Also, you mean finite $A\subseteq\Omega$. You cannot assume $A=\{1,2,\cdots,n\}$.) $\endgroup$ – anon Sep 7 '13 at 22:08
  • $\begingroup$ okay, now it is them problem with the proof, not writing... I am content now, and I'll steer to the right direction... :) Thank you @anon. $\endgroup$ – Tumbleweed Sep 7 '13 at 22:09
3
$\begingroup$

As a more direct proof that it's infinite, note that (using cycle notation), $\Omega$ contains all permutations of the form $(1\,\,n)$ with $n \ge 1$.

(These are the permutations that switch $1$ with $n$, leaving all other numbers fixed).


In order to prove that it's a group, you need to show that the group law is associative, that there is an identity (the trivial permutation) and that there are inverses. These proofs are quite similar to the proofs that $S_n$ is a group for $n \in \Bbb{N}$.

$\endgroup$
  • $\begingroup$ Thank you T. Is my original approach wrong or just cumbersome..? Thank you . :-)( $\endgroup$ – Tumbleweed Sep 7 '13 at 21:51
  • $\begingroup$ @Tumbleweed As anon pointed out, you seem to have mixed a set of permutations and a subset of $\Omega$, so as written it's not correct. $\endgroup$ – user61527 Sep 7 '13 at 21:52
  • $\begingroup$ Perhaps I'm being pedantic, but one should also show (or at least remark) that $(1\ n) = (1\ m)$ implies $n = m$. $\endgroup$ – RghtHndSd Sep 7 '13 at 21:59
  • 1
    $\begingroup$ More dramatically, it contains a copy of $S_n$ for all $n$. $\endgroup$ – Alex Youcis Sep 8 '13 at 3:34

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.