(math) Functions as exponentiation for Sets

20 Nov, 2025

Many arithmetic operations are "shadows" of set operations. For instance, a disjoint union of sets is just addition on numbers and Cartesian product is the analog of multiplication. We can translate from the world of sets to those of numbers using cardinality. Let $A$ and $B$ be finite sets with cardinalities $a$ and $b$ , respectively. Let $ℱ (A, B)$ be the set of functions from $A$ to $B$ . As each element of $x \in A$ has $b$ choices to map to under $f$ , the cardinality of $ℱ (A, B)$ is $b^{a}$ . That is why sometimes you will see the set of functions between $A$ and $B$ written as $B^{A}$ . This notation, although sickening, is quite suggestive. This is the analog of exponentiation for functions, and an invitation to play around.

An Example: power sets

The first non-trivial example of our framework is the set of subsets of $A$ which is called the power set of $A$ . The power set of $A$ is the set of functions from $A$ to ${0, 1}$ wherein we construct a subset $A_{f} \subseteq A$ corresponding to the function $f$ by setting $f (x) = 1$ if and only if $x \in A$ . The notation for the power set of $A$ is traditionally $℘ (A)$ , or alternatively ${0, 1}^{A}$ . There is nothing special about the 2-element set ${0, 1}$ , and as all sets of a given cardinality are isomorphic, we should feel no shame in using the notation $2^{A}$ for the power set.

Exponent laws for sets

For the following exposition, let $A, B, S$ be finite sets. To remember that $Y^{X}$ is the set of functions from $X$ to $Y$ and not the other way, think of how powers are brought down while performing derivatives or logarithms. Let us now see some exponent laws through the eyes of sets of functions. I will write $X \equiv Y$ if there exists a bijection between the sets $X$ and $Y$ , i.e., they have the same cardinality

Unions and Products

We first prove
Proposition: $S^{A} \times S^{B} \equiv S^{A \cup B}$ where $A$ and $B$ are disjoint sets.

Proof. Let us construct a bijection $ϕ : S^{A} \times S^{B} = S^{A \cup B}$ . Consider any function $(f, g) \in S^{A} \times S^{B}$ with $f : A \to S$ and $g : B \to S$ . As $A$ and $B$ are disjoint, we can unambiguously describe a function $h = ϕ (f, g)$ such that $h |_{A} = f$ and $h |_{B} = g$ , and thus $ϕ (f, g) \in S^{A \cup B}$ . On the other hand, if we start with any function $h$ on $S^{A \cup B}$ , we can define $ϕ^{- 1} (h) = (h |_{A}, h |_{B})$ , thus giving us a bijection. $◻$ .

One can check the consequences of this proposition on special examples such as $B = \emptyset$ while noting that $| S^{\emptyset} | = 1$ because $S^{\emptyset}$ consists only of the empty function. The case where $| S | = 2$ corresponds to the power sets, and so $℘ (A) \times ℘ (B) = ℘ (A \cup B)$ holds for disjoint sets. Having rested upon our laurels for a bit, we must face the eventual question -- if we have the addition law, then we must have the subtraction law. But what is a natural notion for division of sets?

Differences and Equivalence Relations

We use the notation $A - B$ to mean all elements of $A$ not contained in $B$ . From the previously proved proposition, we can show $S^{A - B} \times S^{B} \equiv S^{A}$ which is almost what we need but here is an explicit description of $S^{A - B}$ that feels more satiating.

Proposition: For any two functions $f$ and $g$ in $S^{A}$ , let $f ~ g$ if and only if $f |_{A - B} = g |_{A - B}$ . We have $S^{A - B} = S^{A} / ~$ .

Proof. Any representative function $\bar{f} \in S^{A} / ~$ is a unique function on $S^{A - B}$ which gives us our bijection. $◻$

We can understand the equivalence relation as not caring what the function values are on the set $B$ . By abuse of notation, we can write $S^{A - B} = S^{A} / S^{B}$ as we are removing the part of a function on $A$ that evaluates on $B$ .

Exponent of an exponent

This one is quite cool and I will sketch out a proof conversationally. The exponent-like law $(S^{A})^{B} \equiv S^{A \times B}$ holds. This law is capturing the idea that a two-variable function is a one-variable function when you fix one of the inputs. On the left hand side, we have a function $f : B \to (S^{A})$ which maps $b \in B$ to $f_{b}$ . Here $f_{b}$ is a function defined as $f_{b} (a) = f (a, b)$ . This is exactly a function on the set $A \times B$ . To see that this is indeed a bijection, we start with a function on the product and "fix" the second input, to obtain a function from $A$ to $S$ . This procedure is called currying.

Product with the same base

The base multiplication law $A^{S} \times B^{S} \equiv (A \times B)^{S}$ is straightforward to prove. Pick a function $f \in A^{S}$ and a function $g \in B^{S}$ . This gives us a function $(f, g)$ on $S$ that takes values in $A \times B$ . Conversely, any function $f : S \to A \times B$ , can be broken into two function $f |_{A} : S \to A$ and $f |_{B} : S \to B$ where $f |_{A} (s) = x$ and $f |_{B} (s) = y$ for $f (s) = (x, y)$ .

For completeness...

The set $S^{1}$ is in bijection with $S$ as for each $s \in S$ , there is a function $f_{s}$ such that $f_{s} (1) = s$ . Similarly, the set $S^{n}$ is in bijection with the set $S^{{1, 2, \dots, n}}$ where an element $(s_{1}, s_{2}, \dots, s_{n})$ is constructed using the function $f$ with $f (i) = s_{i}$ .

The final bijection

One of my favorite fact about the naturals is $2^{4} = 4^{2}$ . In the set-theoretic world this means that the number of functions from a set of size 4 to a set of size 2 ( $ℱ (4, 2)$ ) is the same as the number of functions from a set of size 2 to a set of size 4 ( $ℱ (2, 4)$ ).

One bijection that uses $2^{2} = 4$ proceeds as follows. For $f : {1, 2, 3, 4} \to {1, 2}$ , consider the following cases:

$f (1) = f (2) = 1$
$f (1) < f (2)$
$f (2) < f (1)$
$f (1) = f (2) = 2$ .

We define $ϕ : ℱ (4, 2) \to ℱ (2, 4)$ by setting $ϕ (f) (1)$ to be the case number satisfied above. Similarly, we can write the cases for $3$ and $4$ to define $ϕ (f) (2)$ . This completely dictates the map $ϕ (f)$ .

This is an unsatisfying bijection due to its foundation on casework. This bijection can be visualized if one imagines these functions as certain bipartite graphs between 2 and 4 vertices. In that case, we are picking pairs of edges to replace with a single edge. Even this picture is not quite natural, so we end on a sombre note, wishing for a canonical (or as close to it) bijective proof of $2^{4} = 4^{2}$ .

The idea that fascinates me here is that we can compress 4 edges into 2 edges, thus there is redundancy in the data. The above bijection picks up on this redundancy.