Composition of functions

Given two functions f : X → Y and g : Y → Z, the composition of both of them is a new function that is formed by applying one function to the output of the other function (kind of “chain reaction”) g ◦ f : X → Z is defined by (g ◦ f)(x) = g(f(x)) ∀ x ∈ X.

If Z = X, then we can define f ◦ g: Y → Y. However, in general f ◦ g ≠ f ◦ g. If X ≠ Y, that’s pretty obvious, these functions have different domains and codomains, but even in the case X = Y, f ◦ g and f ◦ g will generally not be the same function, e.g., f, g: ℝ → ℝ, f(x)=x², and g(x)=2x+1, f ◦ g = (2x+1)² = 4x² + 4x + 1 ≠ g ◦ f = 2x²+1.

Inverse functions

If a subset of X x Y is a bijection f, then each x ∈ X appears as the first member of exactly one ordered pair in f and also each y ∈ Y appears as the second member of exactly one ordered pair in f. Therefore, we can interchange the first and second members of all ordered pairs in f to obtain a set of ordered pairs (y, x), and get a new function, aka the inverse function f^-1. f^-1 is also a bijection function, that is, a one-to-one function mapping Y onto X.

We say that f is invertible if there exists a function f^-1: Y → X, called the inverse of f, such that f^-1∘f = id_X and f∘f_-1 = id_Y. When inverse functions exist, they are unique. A bijective function is always invertible.

Examples: f: ℝ → ℝ, defined by f(x) = x³ and g: ℝ → (0, ∞), defined by g(x) = e^x are both invertible, real-valued functions, and their inverse functions are f^-1: ℝ → ℝ, f^-1(x)=$\sqrt[3]{x}$ and g^-1: (0, ∞) → ℝ, g^-1(x) = ln(x) respectively. On the other hand, x² and cos(x) are not invertible.

f·f^-1(x)=$(\sqrt[3]{x})^3=x=id$

Properties of Composition of Functions

Given functions f: A → B, g: B → C, h: C → D. Then, the following statements hold true:

Associativity: (h·g)·f = h·(g·f)

Proof

Let a ∈ A, [(h·g)·f] (a) = (h·g)(f(a)) = h(g(f(a))) = h((g·f)(a)) = [h·(g·f)] (a)∎

If f and g are surjective or onto, then g·f is onto, too.

Proof.

Let c ∈ C ⇒ [g is onto] ∃b ∈ B: g(b) = c ⇒ [f is onto] ∃a ∈ A: f(a) = b. Therefore, ∃a ∈ A: (g·f)(a) = g(f(a)) = g(b) = c ∎

If f and g are both one-to-one, then g·f is one-to-one, too.

Proof.

Suppose (g.f)(a) = (g·f)(b) ⇒ g(f(a)) = g(f(b)) ⇒ [g is one-to-one] f(a) = f(b) ⇒ [f is one-to-one] a = b∎

If f and g are both bijective, then g·f is bijective.

Proof. If f and g are both bijective, then they are both one-to-one and onto ⇒ g.f is both one-to-one and onto ⇒ g is bijective.

Let f and g be invertible functions such that their composition f·g is well-defined. Then, f·g is invertible and (f·g)^-1=g^-1·f^-1

Proof. Let A, B and C be sets such that g: A → B and f: B → C.

(g^-1·f^-1)·(f·g) = [Associative] g^-1·((f^-1·f)·g) = [f is an invertible function, f: B → C, f^-1·f = id_B] g^-1·(id_B·g) = g^-1·g = id_A
(f·g)·(g^-1·f^-1) = [Associative] f·((g·g^-1)·f^-1) = [g is an invertible function, g: A → B, g·g^-1 = id_B] f·(id_B·f^-1) = f·f^-1 = id_C
Therefore, (g^-1·f^-1)·(f·g) = id_A and (f·g)·(g^-1·f^-1) = id_C ⇒ (f·g)^-1=g^-1·f^-1∎

If f·g expresses the process or idea of putting one’s socks (g), then putting on one’s shoes (f), (f·g)^-1=g^-1·f^-1 refers to the reverse process of undressing, which is taking off one’s shoes (f^-1), immediately followed by taking off one’s socks (g^-1).

This proposition can be easily generalized with a list of functions, say f₁, f₂, ···, f_n of invertible functions such that their composition f₁·f₂···f_n is well-defined. Then, f₁·f₂···f_n is invertible and (f₁·f₂···f_n)^-1 = f_n^-1···f₁^-1.

Cardinality of sets.

Definition. The empty set ∅ is finite and has cardinality |∅| = 0. A non-empty set S is called finite and have cardinality |S| = n ∈ N if and only if there exists a bijection from S to {1, 2, . . . n}. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements.

Proof. A function f: X → Y can only be injective if |Y| ≥ |X| since the number of elements in the image f(X) is equal to the number of elements in the domain and obviously f(X)⊆Y.

A function f: X → Y can only be surjective if (By definition, a function is a collection of ordered pairs of the form (a, b) that satisfies one condition: every element a in the domain A must be paired with exactly one element b in the codomain B. ) |Y| ≤ |X|. Therefore, if f is bijective then |Y| = |X|.

However, it will be important to know whether two infinite sets have the same cardinality. Two sets X and Y have the same cardinality if and only if there exist a bijection between them, e.g., ℤ (that is, whole numbers, positive, negative, and zeros), and ℤ⁺ (the set of positive elements of ℤ) have the same cardinality: 1 ↔ 0, 2 ↔ 1, 3 ↔ -1, 4 ↔ 2, 5 ↔ -2, 6 ↔ 3, 7 ↔ -3, etc. Therefore, |ℤ| = |ℤ⁺| = χ₀.

For any sets A, B, and B, the following statements are true: |A| = |A| (f: A → A, f(x) = x is bijective, that is, f = Id_A). If |A| = |B|, then |B| = |A| (if f: A → B is a bijection ⇒ f^-1: B → A is a bijection, too). If |A| = |B| and |B| = |C|, then |A| = |C| (if f: A → B and g: B → C are bijections, then g∘f: A → C is a bijection, too.)

X has cardinality less than or equal to the cardinality of Y, |X| ≤ |Y| if there exists an injective function from X into Y. X has cardinality strictly less than the cardinality of Y, |X| < |Y|, if there is an injective function, but no bijective function, from X to Y.

For any sets A, B, and C: |A| ≤ |A| (f: A → A, f(x) = x is bijective, that is, f = Id_A). If |A| ≤ |B| and |B| ≤ |C|, then |A| ≤ |C| (if f: A → B and g: B → C are injections, then g∘f: A → C is an injection, too.) Either |A| ≤ |B| or |B| ≤ |A| (it is not trivial). Cantor - Bernstein - Schroeder. If A and B are sets where |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.

Cantor’s Theorem. Let A be a set, and P(A) be its power set. Then. |A| < |$\mathbb{P(A)}$|. Recall that for any set A, the power set of A, written $\mathbb{P(A)}$, is the collection of all subsets of A.

Proof. If A is a finite set, it is enough to recall that |P(A)| = 2^|A|.

Let A be an arbitrary, possible infinite, set. We can define an injection f: A → P(A), f(a) = {a}, and therefore |A| ≤ |$\mathbb{P(A)}$|.

For the sake of contradiction, let f: A → P(A) be a bijection. Let D = {a ∈ A: a ∉ f(a)}. Of course, D ⊆ A ⇒ [f is a bijection (we only really need that f is a surjection)] ∃y ∈ A: f(y) = D. The big fat ugly question: is y ∈ D?

If y ∉ D ⇒ [By definition of D] y ∈ f(y) = D ⊥
If y ∈ D ⇒ [By definition of D] y ∉ f(y) = D ⊥

Therefore, no such bijection is possible ⇒ |A| < |$\mathbb{P(A)}$|∎

Observe that a proper subset of an infinite set could have the same number of elements as the whole set. Maybe it is hard to believe but, |ℚ| = χ₀. If you imagine the fractions to be glued or stuck to a cord or a string, and pulling it to the left, the string straightens out and all rational elements appear on it in as an infinite row as 0, 1/2, -1/2, 1, -1, 3/2, 2/3… (Figure 1.a.)

Theorem. There exists no bijection f: ℕ → ℝ, and therefore |ℕ| ≠ |ℝ|. This is a first indication of how there are different kinds of infinite.

Suppose that we’ve created a bijection, producing a list containing every single real number between 0 and 1 in some order. There is a “new” number between 0 and 1 that cannot possible be in the list.

Take the first decimal place of our first number on our list and adds 1 to it (if it was 9, you need to change it to a zero), and use the result as the first decimal place of the new number. Then, take the second decimal place of our second number on our list and adds 1 to it, using the result as the second decimal place of the new number. This process continues infinitely, and the new number, because of how we have constructed it (e.g., 0.25904···), won’t be on the list (Figure 1.b.)

Exercises:

|ℕ| = |ℤ|. Figure 1.d

$f(n) = \begin{cases} \frac{n}{2}, &n~ mod~ 2 = 0 \\ -\frac{n+1}{2}, &n~ mod~ 2 ≠ 0 \end{cases}$

∀a, b∈ ℝ, a < b, |[0, 1]| = |[a, b]|, f: [0, 1] → [a, b], f(x) = (b -a)x + a. Figure 1.e.
|($\frac{π}{2},-\frac{π}{2}$)| = |ℝ|, f: ($\frac{π}{2},-\frac{π}{2}$) → ℝ, f(x) = tan(x). Figure 1.f.
|(0, ∞)| = |(0, 1)|

We need to show that there is a bijective function f: (0, ∞) → (0, 1).

Consider the interval (0, ∞) as the positive x-axis and the interval (0, 1) on the y-axis of ℝ², so they are both perpendicular to each other as illustrated in Figure 1.a.

Let’s define geometrically f(x) to be the point on the interval (0, 1) where the line from the point P(-1, 1) to x ∈ (0, ∞) intersects the y -axis. By similar triangles formulas (Recall: two triangles are similar if their corresponding angles are equal and their corresponding sides are in the same ratio), we have $\frac{1}{x+1}=\frac{f(x)}{x}↭f(x)=\frac{x}{x+1}$. It is left to the reader to demonstrate that f is bijective.

Definition. Let A be an arbitrary set. Then, A is said to be countable infinite if |ℕ| = |A|, that is, if there exists a bijection f: ℕ → A. A is said to be uncountable if A is infinite and |ℕ| ≠ |A|, that is, if there exists no bijection f: ℕ → A.

If A is countable infinite, there exists a bijection f: ℕ → A, it allows us to list out the set A as an infinite list f(1), f(2), f(3), ···, i.e., the set A’s elements can be arranged in an infinite list a₁, a₂, a₃, ···

Theorem. If A and B are both countable infinite, then so is A x B and A ∪ B. More generally, given n countable infinite A₁, A₂, ···, A_n, the Cartesian product A₁ x A₂ x ··· x A_n is also countable infinite.

Proof.

Suppose A and B are both countable infinite, we can rewrite A and B in list form as follows, A = {a₁, a₂, a₃, ···} and B = {b₁, b₂, b₃, ···}. Figure 1.b shows how to form an infinite path passing through all elements of the Cartesian product A x B.
We can mix or shuffle A and B into a single infinite list for A ∪ B as follows, A ∪ B = {a₁, b₁, a₂, b₂, a₃, b₃, ···} considering that we do not list an element twice if it belongs to both A and B.
The proof is provided by induction on n. For the basis step, n = 2, notice that it has already been demonstrated, A₁ x A₂ is countably infinite.

Let’s assume that the statement holds for k = n, i.e., A₁ x A₂ x ··· x A_n is countably infinite, and consider k = n+1, i.e., the Cartesian product A₁ x A₂ x ··· x A_n+1.

Let’s define the function f: A₁ x A₂ x ··· x A_n+1 → (A₁ x A₂ x ··· A_n) x A_n+1, as follows f(x₁, x₂, ···, x_n+1) = ((x₁, x₂, ···, x_n), x_n+1).

It is pretty obvious that f is bijective, and therefore |A₁ x A₂ x ··· x A_n+1| = |(A₁ x A₂ x ··· x A_n) x A_n+1|. By the induction hypothesis, A₁ x A₂ x ··· x A_n is countable infinite, and by assumption A_n+1 is countable infinite. Futhermore, the Cartesian product of two countable infinite sets (n = 2, Case base) is countable infinite, too, and we have shown that A₁ x A₂ x ··· x A_n+1 has the same cardinality of this Cartesian product, and therefore it is countable infinite∎

Theorem. A function is bijective if and only if has an inverse.

Proof.

⇒) Suppose f: A → B be bijective.

Definition. We will define a function f⁻¹: B → A as follows. Let b ∈ B. Since f is surjective, ∃a ∈ A such that f(a) = b. Let f⁻¹(b) = a.
Is f^-1 well defined? Since f is injective, this element a is indeed unique (in other words, f(a₁) = f(a₂) = b ⇒ a₁ = a₂), so f^-1 is well-defined.
Is f^-1 the inverse of f? Let a ∈ A, b = f(a). Then, by definition, f^-1(b) = a. Then f^-1 ◦ f(a) = f^-1(f(a)) = f^-1(b) = a ⇒ f^-1 ◦ f = Id_A. Similarly, let b ∈ B, a = f^-1(b). Then, by definition, f(a) = b ⇒ f ◦ f^-1(b) = f(f^-1(b)) = f(a) = b ⇒ f ∘ f^-1 = id_B. Therefore, f^-1 ◦ f = Id_A and f ∘ f^-1 = id_B ⇒ f^-1 is the inverse of f.

⇐) Suppose f has an inverse.

is f surjective? Suppose b ∈ B. Let a be f^-1(b). Then, f(a) = f(f^-1(b))=f ◦ f^-1(b) = [By definition, f ∘ f^-1 = id_B] b
is f injective? Let a₁, a₂ ∈ A: f(a₁)=f(a₂) = b. Let a be f^-1(b). a₂ = Id_A(a₂) = [By definition, f^-1 ◦ f = Id_A] f^-1 ◦ f(a₂) = f^-1(b) = a. Analogously, mutatis mutandis a₁ = a, and obviously [Sometimes, I wonder if I actually help or hinder the reader’s understanding] a₂ = a = a₁ ⇒ a₂ = a₁.