Motivation and basic definitions

Consider the set of all bijections from a set $X$ to itself, Bij$(X)$. If $f$ and $g$ are two bijections, then so is their composition $f \circ g$. There is the indentity bijection that sends every element to itself, which we call $e$, and such that if $f$ is any bijection, $f \circ e = e \circ f = f$. Morever, every bijection $f$ has an inverse, $f^{-1}$, and the composition of a bijection and its inverse is equal to the identity.

Exercise 1.1 (05)   Show that the composition of bijections is associative, but not necessarily commutative. Find a general criterion for determining whether two bijections commute.

Exercise 1.2 (05)   When $X$ is the set $\{1,\dots,n\}$, Bij$(X)$ is the set of permutations on $n$ symbols and is denoted by $S_{n}$. How many elements does the $S_{n}$ have?

* Caesar's code and Borges' library. If we consider the set of bijections of the alphabet $\{a, b, \dots, z\}$, we enter the world of cryptography. Indeed, Julius Caesar used to encrypt his messages by substituting the letter $a$ by the letter $d$, the letter $b$ by the letter $e$, and so on (the letter $z$ is substituted by the letter $c$). The problem with this type of code is that ymjd fwj jcywjrjqd jfxd yt gwjfp. Hint: read The Gold-Bug by Edgar Allan Poe.

In a beautiful short story titled The Library of Babel, Jorge Luis Borges describes a library of books whose pages are filled with permutations of the letters of the alphabet, commas, points, and blank spaces. Of course, all the knowledge of the Universe could be found in such library since even the pages you're reading now are mostly of this form.

In the example of the bijections, we have a set together with an operation (the composition) that takes two elements of the set and gives you another. Moreover, this operation satisfies certain properties. Since this structure comes up very often in mathematics, it is useful to give it a name.

Definition 1.1   A group is composed of a set $G$ and a multiplication function

$$* : G \times G \longrightarrow G$$

that satisfies the following properties:

• Multiplication is associative: $(f*g)*h = f*(g*h)$.
• Existence of an identity: there is an element $e \in G$ such that for any $f \in G$, $f*e = e*f = f$.
• Existence of inverses: for any element $f \in G$, there is an element $f^{-1} \in G$ such that $f^{-1} * f = f * f^{-1} = e$.

Definition 1.2   Let $(G,*)$ be a group and let $H$ be a subset of $G$. We say that $H$ is a subgroup of $G$ if

• The identity belongs to $H$.
• Whenever an element is in $H$ so is its inverse.
• Whenever two elements are in $H$ so is their product.

Clearly, if $H$ is a subgroup of $(G,*)$, then $(H,*)$ is a group in its own right.

Exercise 1.3 (*10)   What is the probability that a subset of $S_{3}$ be a subgroup?