Functions

What are the 3 things that a function consists of?

• A set A = dom(f) called the domain of f

• A set B = codom(f) called the codomain of f

• A rule that assigns to each element a in A a unique element f(a) in B

What is the definition of an identity function?

Let A be a set. The identity function on A is id_A : A → A defined id_A(a) = a

What is the definition of an inverse function?

Let A, B be sets. Let f: A → B be a bijection. The inverse f^-1 : B → A is defined by f^-1(b) is the unique a in A such that f(a) = b

Let f : A → B, g : B → C be functions. Suppose f and g are bijections. Then…

g ∘ f : A → C is a bijection

Let f : A → B, g : B → C, h : C → D be functions. Then…

• (h ∘ g) ∘ f = h ∘ (g ∘ f)

• f ∘ id_A = f = id_B ∘ f

Let f : A → B, g : B → C be functions. Suppose f is a bijection. Then…

f^-1 : B → A is a bijection and f ∘ f^-1 = id_A, f ∘ f^-1 = id_B

What is the definition of a permutation?

Let Ω be a set. A permutation of Ω is a bijection f : Ω → Ω. We define sym(Ω) to be the set of permutations of Ω. We mainly consider Ω = {1, 2, …, n} for a natural number n and write S_n for sym({1, 2, …, n})

What is two-row notation?

Let f ∈ S_n. The two-row notation of f is the symbol in the image

What is composition?

Let f, g ∈ Sym(Ω). Then g ∘ f ∈ Sym(Ω)

What is an inversion?

Let f ∈ Sym(Ω). Then f^-1 ∈ Sym(Ω)

What is the definition of a power of a permutation?

Let f ∈ Sym(Ω) and r be an integer. We define f^r as follows:

For r = 0, f⁰ = id_Ω

For r > 0, f^r = f ∘ f ∘ … ∘ f (r times)

For r < 0, let s = -r and set f^r = (f^-1)^s

Let f ∈ Sym(Ω) and r, s be integers. Then…

• f^r+s = f^r ∘ f^s

• f^rs = (f^r)^s

What is a cycle?

Let f ∈ Sym(Ω). We say f is a k-cycle if there exists a distinct a₁, …, a_k ∈ Ω such that f(a₁) = a₂, f(a₂) = a₃, …, f(a_k-1) = a_k, f(a_k) = a and f(b) = b for all other b ∈ Ω. We use the notation f= (a₁, a₂, …, a_k)

How to decompose a a function as a product of disjoint cycles?

• Find all the individual cycles in the function (e.g. c₁, c₂, …)

• Thus f = c₁ ∘ c₂ ∘ …

• The cycle shape of f is (r₁, r₂, …) where r₁, r₂, … are the length of each cycle in decreasing order

What are some key notes about notation in cycles?

• Omit ∘ for composition

• Omit 1-cycles

What is the order of a function g?

Let g ∈ Sym(Ω). The order of g is the smallest natural number m s.t. g^m = id_Ω. It is denoted o(g) = m (o stands for order)

Let g ∈ Sym(Ω) with cycle shape (r₁, r₂, …, r_m). What is o(g)?

o(g) = lcm(r₁, r₂, …, r_m)

Let g ∈ Sym(Ω), m = o(g) and r be an integer. What is g^r?

g^r = id_Ω iff m | r