Function Composition and Inverses: The Algebra of Transformations

As we established previously, a function is a mathematical machine that transforms inputs from a domain $A$ into specific outputs in a codomain $B$.

Definition: A function $f$ from a set $A$ to a set $B$ (denoted $f: A \to B$) is a relation that assigns to every single element in the domain $A$ exactly one element in the codomain $B$.

But what happens if we connect these machines together? What if we want to run the machine backwards? This leads us to the algebraic concepts of function composition and invertibility.

Composition of Functions

Given two functions $f : X \to Y$ and $g : Y \to Z$, we can link them together like an assembly line. The output of $f$ becomes the direct input for $g$.

Definition: The composition of $g$ and $f$, denoted $g \circ f$ (read as “$g$ composed with $f$” or “$g$ of $f$”), is a new function mapping directly from $X$ to $Z$. It is defined mathematically as: $(g \circ f)(x) = g(f(x)) \quad \forall x \in X$.

Non-Commutativity of Composition

In standard multiplication, $a \times b = b \times a$. In function composition, order is absolute. Generally, $f \circ g \neq g \circ f$.

If the sets $X$ and $Y$ are completely different, you cannot even construct $f \circ g$ because the output of $g$ won’t fit into the domain of $f$. But even if the domain and codomains are identical (e.g., both are $\mathbb{R}$), the compositions will almost always yield different functions.

Example: Let $f, g: \mathbb{R} \to \mathbb{R}$ where $f(x) = x^2$ and $g(x) = 2x + 1$.

• $(f \circ g)(x) = f(g(x)) = f(2x + 1) = (2x + 1)^2 = 4x^2 + 4x + 1$
• $(g \circ f)(x) = g(f(x)) = g(x^2) = 2x^2 + 1$

Clearly, $4x^2 + 4x + 1 \neq 2x^2 + 1$. The order of operations matters drastically!

Inverse Functions

If a function transforms an input $x$ into an output $y$, can we build a machine that takes $y$ and perfectly reconstructs the original $x$?

If a function $f$ is a bijection (it is both perfectly one-to-one and hits every target in its codomain exactly once), then every $x \in X$ is paired with exactly one unique $y \in Y$. Because this pairing is completely unambiguous, we can simply reverse all the arrows.

Definition: We say that $f: X \to Y$ is invertible if there exists a function $f^{-1}: Y \to X$, called the inverse of $f$, such that running them sequentially cancels them out, returning the identity function ($\text{id}$): $f^{-1} \circ f = \text{id}_X \quad \text{and} \quad f \circ f^{-1} = \text{id}_Y$

When inverse functions exist, they are absolutely unique. A function is invertible if and only if it is bijective.

Examples of Invertible Functions:

• $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^3$. Its inverse is $f^{-1}(x) = \sqrt[3]{x}$. Check: $f^{-1}(f(x)) = \sqrt[3]{x^3} = x$.
• $g: \mathbb{R} \to (0, \infty)$ defined by $g(x) = e^x$. Its inverse is $g^{-1}(x) = \ln(x)$.

The Problem of Non-Invertible Functions (Domain Restriction)

Functions like $f(x) = x^2$ and $h(x) = \cos(x)$ mapping from $\mathbb{R} \to \mathbb{R}$ are not invertible.

Why? Because they are not injective. They fail the Horizontal Line Test. For example, $f(2) = 4$ and $f(-2) = 4$. If we try to run the machine backwards and input $4$, the machine doesn’t know whether to output $2$ or $-2$. A function can never have two outputs for one input.

To fix this, mathematicians “cheat.” We aggressively chop off half of the domain to force the function to be injective.

If we restrict $f(x) = x^2$ to the domain $[0, \infty)$, it is suddenly perfectly bijective. This is exactly how we are able to mathematically define the inverse function $f^{-1}(x) = \sqrt{x}$! Similarly, by restricting $\cos(x)$ to the domain $[0, \pi]$, we create the inverse function $\arccos(x)$.

Theorems: Properties of Composition

If we string multiple functions together, they obey a strict set of algebraic laws. Let $f: A \to B$, $g: B \to C$, and $h: C \to D$ be functions.

Theorem 1: Associativity. Function composition is strictly associative: $(h \circ g) \circ f = h \circ (g \circ f)$.

Proof:

Let $a \in A$. We evaluate both sides independently:

• $[(h \circ g) \circ f](a) = (h \circ g)(f(a)) = h(g(f(a)))$
• $[h \circ (g \circ f)](a) = h((g \circ f)(a)) = h(g(f(a)))$

Because both sides yield identical outputs for every input $a$, the composed functions are identical. $\blacksquare$

Theorem 2: Composition of Surjections. If $f$ and $g$ are both surjective (onto), then $g \circ f$ is also surjective.

Proof:

We must prove that for every element $c \in C$, there exists some $a \in A$ such that $(g \circ f)(a) = c$.

1. Because $g: B \to C$ is surjective, for our target $c \in C$, there exists at least one $b \in B$ such that $g(b) = c$
2. Because $f: A \to B$ is surjective, for that specific target $b \in B$, there exists at least one $a \in A$ such that $f(a) = b$.
3. Therefore, $(g \circ f)(a) = g(f(a)) = g(b) = c$. Since we found an $a$ for our arbitrary $c$, the composition is surjective. $\blacksquare$

Theorem 3: Composition of Injections. If $f$ and $g$ are both injective (one-to-one), then $g \circ f$ is also injective.

Proof:

Assume that two inputs produce the same output: $(g \circ f)(a_1) = (g \circ f)(a_2)$. We must prove that $a_1$ must equal $a_2$.$

1. $g(f(a_1)) = g(f(a_2))$. Because $g$ is injective, it can only output the same value if its inputs are identical. Therefore, $f(a_1) = f(a_2)$
2. Because $f$ is injective, too, it can only output the same value if its inputs are identical. Therefore: $a_1 = a_2$ Since identical outputs guarantee identical inputs, the composition is injective. $\blacksquare$

Corollary: If $f$ and $g$ are both bijective, then by Theorems 2 and 3, $g \circ f$ is also bijective!

Theorem 4: The Reversal Law of Inverses (The “Shoes and Socks” Theorem). Let $f: A \to B$ and $g: B \to C$ be invertible functions. Then, their composition $g \circ f$ is invertible, and its inverse is exactly $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

The “Shoes and Socks” Intuition: Why does the order reverse? Imagine $f$ is the process of putting on your socks, and $g$ is the process of putting on your shoes. The composition $g \circ f$ means you put your socks on first, then your shoes. If you want to invert this process (undress), you cannot take your socks off first! You must reverse the operations in reverse order: you must first take off your shoes ($g^{-1}$), immediately followed by taking off your socks ($f^{-1}$).

Proof: To prove that $f^{-1} \circ g^{-1}$ is the true inverse of $g \circ f$, we must compose them together and prove they collapse into the identity function. We rely heavily on the Associativity property (Theorem 1) to regroup the terms:

First, we test one direction: $\begin{aligned} (f^{-1} \circ g^{-1}) \circ (g \circ f) &= f^{-1} \circ (g^{-1} \circ g) \circ f \\ &= f^{-1} \circ (\text{id}_B) \circ f \\ &= f^{-1} \circ f \\ &= \text{id}_A \end{aligned}$

Next, we test the other direction: $\begin{aligned} (g \circ f) \circ (f^{-1} \circ g^{-1}) &= g \circ (f \circ f^{-1}) \circ g^{-1} \\ &= g \circ (\text{id}_B) \circ g^{-1} \\ &= g \circ g^{-1} \\ &= \text{id}_C \end{aligned}$

Because composing them in both directions yields the identity function, we have proven that $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$. $\blacksquare$

• This proposition can be easily generalized with a list of functions, say $f_1, f_2, \cdots, f_n$ of invertible functions such that their composition $f_1 \circ f_2 \circ \cdots f_n$ is well-defined. Then, $f_1 \circ f_2 \circ \cdots f_n$ is invertible and $(f_1 \circ f_2 \circ \cdots f_n)^{-1} = f_n^{-1}\circ \cdots f_1^{-1}$.

The Mathematics of Infinity: Cardinality and Bijections

How do we count things when there is no end to the counting?

In 1638, Galileo Galilei observed a paradox: there seem to be more whole numbers than perfect squares (since most numbers aren’t squares), yet for every whole number, there is exactly one perfect square ($1 \to 1$, $2 \to 4$, $3 \to 9$). How can one infinity be “larger” than another?

In the 19th century, Georg Cantor formalized the mathematics of infinity. He realized that to compare sizes, we shouldn’t “count” the elements. Instead, we should pair them up.

Cardinality of Sets

Definition: The empty set $\emptyset$ is finite and has cardinality $\vert{}\emptyset\vert{} = 0$. A non-empty set $S$ is called finite and has cardinality $\vert{}S\vert{} = n \in \mathbb{N}$ if and only if there exists a bijection from $S$ to the set $\{1, 2, \dots, n\}$.

If $X$ and $Y$ are finite sets, the existence of a bijection means they have the exact same number of elements.

• If a function $f: X \to Y$ is injective, it means $\vert{}X\vert{} \le \vert{}Y\vert{}$. There are enough unique targets in $Y$ for every element in $X$.
• If a function $f: X \to Y$ is surjective, it means $\vert{}X\vert{} \ge \vert{}Y\vert{}$. There are enough elements in $X$ to hit every target in $Y$.
• Therefore, if a function is bijective (both injective and surjective), $\vert{}X\vert{} = \vert{}Y\vert{}$.

We extend this logic to infinite sets: Two sets $X$ and $Y$ have the same cardinality if and only if there exists a perfect bijection between them.

Comparing Infinities

We denote the cardinality of the natural numbers $\mathbb{N} = \{1, 2, 3, \dots\}$ as $\aleph_0$ (Aleph-null). Any set that has this exact cardinality is called countably infinite.

Are the integers $\mathbb{Z}$ larger than the natural numbers $\mathbb{N}$? Intuitively, it seems like $\mathbb{Z}$ should be twice as large, since it includes negative numbers and zero. However, we can create a perfect bijection between them!

Let $f: \mathbb{N} \to \mathbb{Z}$ be defined as: $f(n) = \begin{cases} \frac{n}{2}, & \text{if } n \text{ is even} \\ -\frac{n-1}{2}, & \text{if } n \text{ is odd} \end{cases}$

This function perfectly pairs the elements: $1 \to 0$, $2 \to 1$, $3 \to -1$, $4 \to 2$, $5 \to -2$, and so on. No integer is missed, and no integer is hit twice. Therefore, $\vert{}\mathbb{N}\vert{} = \vert{}\mathbb{Z}\vert{} = \aleph_0$.

Conceptual Intuition (Hilbert’s Hotel): Imagine a hotel with an infinite number of rooms, and every room is occupied. A new guest arrives. The manager moves the guest in Room 1 to Room 2, Room 2 to Room 3, and so on. Room 1 is now empty for the new guest! Because the hotel is countably infinite, it can absorb infinite additions without running out of space.

Similarly, it is a profound truth that the rational numbers (fractions) are also countably infinite, $\vert{}\mathbb{N}\vert{} = \vert{}\mathbb{Q}\vert{}$.

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_1, a_2, 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_1, A_2, ···, A_n, the Cartesian product A_1 x A_2 x ··· x A_n is also countable infinite.

Proof.

1. Suppose A and B are both countable infinite, we can rewrite A and B in list form as follows, A = {a_1, a_2, a₃, ···} and B = {b_1, b_2, b₃, ···}. Figure 1.b shows how to form an infinite path passing through all elements of the Cartesian product A x B.  

2. We can mix or shuffle A and B into a single infinite list for A ∪ B as follows, A ∪ B = {a_1, b_1, a_2, b_2, a₃, b₃, ···} considering that we do not list an element twice if it belongs to both A and B.

3. The proof is provided by induction on n. For the basis step, n = 2, notice that it has already been demonstrated, A_1 x A_2 is countably infinite.

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

Let’s define the function f: A_1 x A_2 x ··· x A_n+1 → (A_1 x A_2 x ··· A_n) x A_n+1, as follows f(x_1, x_2, ···, x_n+1) = ((x_1, x_2, ···, x_n), x_n+1).

It is pretty obvious that f is bijective, and therefore |A_1 x A_2 x ··· x A_n+1| = |(A_1 x A_2 x ··· x A_n) x A_n+1|. By the induction hypothesis, A_1 x A_2 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_1 x A_2 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.

1. 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.
2. Is f_{-1} well defined? Since f is injective, this element a is indeed unique (in other words, f(a_1) = f(a_2) = b ⇒ a_1 = a_2), so f_{-1} is well-defined.
3. 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.

1. 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
2. is f injective? Let a_1, a_2 ∈ A: f(a_1)=f(a_2) = b. Let a be f_{-1}(b). a_2 = Id_A(a_2) = [By definition, f_{-1} ◦ f = Id_A] f_{-1} ◦ f(a_2) = f_{-1}(b) = a. Analogously, mutatis mutandis a_1 = a, and obviously [Sometimes, I wonder if I actually help or hinder the reader’s understanding] a_2 = a = a_1 ⇒ a_2 = a_1.