Group of Permutations

Permutation: Let S be a non-empty set. A permutation on S is defined as a map from S to S which is both one-to-one and onto.

Example: Let A(S) denotes the set of all permutations on a non-empty set S. Then A(S) forms a group under the operation of composition of maps.
Moreover if S contains n elements, then the group A(S) contains n! elements. This group A(s) is called Permutation Group.

Sol: Here, A(S) = The set of all the permutations on S.
          ∴      A(S) = {f : f: S → S is a one-one onto map}.
         Let f, g, h ∈ A(S).
         ∴ f, g, h are one-one onto maps from S to S.

Closure property: Since f, g are maps from S to S, so f o g is also a map from S to S.
                    f o g : S → S is defined by (f o g )(x) = f (g(x)), ∀ x ∈ S.
         We prove that f o g is one-one as well as onto.
         For one-one:
         Let x₁, x₂ ∈ S such that 
                ( f o g )(x₁) = ( f o g )(x₂) 
         ⇒        f (g(x₁)) = f (g(x₂))
         ⇒             g(x₁) = g(x₂), Since f is one-one
         ⇒                  x₁ = x₂, Since g is also one-one
         ∴            f o g is one one
         For onto
         Let z  ∈ S.
         Since f: S → S is onto and  z  ∈ S, so ∃ y  ∈ S such that f (y) = z.
         Since g: S → S is onto and  y  ∈ S, so ∃ x ∈ S such that g (y) = y.
        Consider (f o g)(x) = f (g (x)) = f (y) = z.
        ∴            f o g is onto.
        ∴            f o g is one-one map of S onto S.
        ∴            f o g is a permutation on S.
        ⇒  f o g ∈ A(S), ∀  f, g ∈ A(S).
        Thus, A(S) is closed under composition of maps.

Associativity: Let x ∈ S be an arbitrary element.
        For all f, g, h ∈ A(S),
         ∴ ((f o g) o h )(x) = (f o g)(h(x)) = f (g (h (x)))
             (f o (g o h ))(x) = f ((g o h)(x)) = f (g (h (x)))
         ∴ ((f o g) o h )(x) = (f o (g o h ))(x), ∀ x ∈ S.
         ⇒ f o g) o h  = f o (g o h )
       Thus, associativity property holds in A(S).

Existence of Identity: Define a map i : S → S by 
        i(x) = x, ∀ x ∈ S
        Let x₁ + x₂ ∈ S. Then i(x₁) = i(x₂)
        ⇒ x₁ = x₂
          ∴  i is one-one.
        If x ∈ S, then i (x) = x
        ∴  i is onto.
        ∴  i is one-one map of S onto itself.
        ∴  i is a permutation on S.
        So, i ∈ A(S).
        Also (f o i)(x) = f (i (x)) = f (x), ∀ x ∈ S.
       ∴ f o i = f.
       Similarly i o f = f, ∀ f ∈ A(S).
       i is identity element of A(S).

Existence of inverse:  For all f ∈ A(S), f is one-one and onto map of S to S.
      ∴ f is invertible map and f ^-1 is also one-one and onto.
      ∴ f ^-1 is a permutation on S.
      ∴ f ^-1 ∈ A(S).
      Also f ^-1 : S → S is defined by f ^-1 (y) = x    iff f (x) = y.
      Let x ∈ S.
      ∴ f (x) ∈ S.
      Let f (x) = y
      ∴ y ∈ S.
      Also, f (x) = y        ⇒ f ^-1 (y) = x .
      Now (f ^-1 o f)(x) = f ^-1 (f (x)) = f ^-1 (y) = x = i (x)
      So, (f ^-1 o f)(x) = i (x), ∀ x ∈ S.
      ⇒ f ^-1 o f = i, similarly, f  o f ^-1 = i.
      ∴  f ^-1 is inverse of f.
      ∴  A(S) forms a group under the operation of composition of maps.
      Further, if S contains n elements, then
      The number of elements in A(s)
              = The number of permutations of S.
              = The number of arrangements of n elements.
              = n!.