Functions: Mappings, Injections, and the Pigeonhole Principle

Brick walls are there for a reason. The brick walls are not there to keep us out. The brick walls are there to show how badly we want something. Because the brick walls are there to stop the people who don’t want something badly enough. They are there to keep out the other people, Randy Pausch.

💫 “The best way to predict the future is to create it.” — Peter Drucker

In mathematics, sets are isolated islands of objects. To build a thriving mathematical universe, we must build bridges between them. A function is the most important type of bridge we can build.

Defining a Function

Before we can define a function, we must quickly recall the Cartesian Product. If $A$ and $B$ are two sets, their Cartesian product $A \times B$ is the set of all possible ordered pairs $(a, b)$ where $a \in A$ and $b \in B$, e.g., $\{1, 2\} \times \{\text{red}, \text{yellow}, \text{blue}\} = \{(1, \text{red}), (1, \text{yellow}), (1, \text{blue}), (2, \text{red}), (2, \text{yellow}), (2, \text{blue})\}$.

A relation $R$ is simply any subset of this Cartesian product ($R \subseteq A \times B$).

A function is a highly restricted, specific type of relation.

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$. Functions are also called maps or mappings (Figure 1.a).

In the language of ordered pairs, a function is a subset of $A \times B$ in which every element $a$ in the domain $A$ must be paired with exactly one element $b$ in the codomain $B$. In other words, it satisfies two absolute rules:

1. Total Domain: Every element $a \in A$ must appear as the first element in an ordered pair.
2. Uniqueness: No element $a \in A$ can appear as the first element in more than one ordered pair.

If $(a, b)$ belongs to our function, we write $f(a) = b$. We call $a$ the argument (or input) and $b$ the value (or output). A way of representing the set of ordered pairs which define a function is to use one of these notations: $\{(x,y) \vert{} y = f(x), x \in X\}$ or $\{(x, f(x)) \vert{} x \in X\}$.

The Vending Machine Analogy

Think of a function as a vending machine.

• The Domain ($A$) is the set of valid buttons you can press. Rule number 1: Every button must do something.
• The Codomain ($B$) is the set of all yummy snacks stocked inside the machine.
• Uniqueness (Rule number 2): If you press “A1”, the machine drops exactly one specific bag of chips. If pressing “A1” randomly dropped either chips or a soda, the machine is broken. A function must be predictable!

A function is most often denoted by letters such as $f, g$, or $h$. A function takes an input element from a set $A$ (the domain, sometimes written $X$) and produces an output in the set $B$ (the codomain, sometimes writtesn $Y$). We can imagine it as some sort of black box, device, or machine that does some kind of computation or transformation (Figure 1.b). You put some object into its input funnel, then the function machine will process that object or argument and turn it into some other object or value, which comes out as output.

Domain, Codomain, Range (Image), and Graph

Understanding the anatomy of a function requires precise terminology:

• Domain ($A$): The set of all valid inputs.
• Codomain ($B$): The set of all potential outputs. This is the universe where the outputs live.
• Range (or Image): The set of actual outputs the function successfully hits. It is defined as $f(A) = \{f(x) \mid x \in A\}$.
• The graph of the function is the set of all ordered pairs $(x, y)$ in the plane that satisfy the equation $y = f(x)$, i.e., $\{(x, y) \mid y = f(x), x \in X\}$. It represents a curve in the $xy$-plane giving a pictorial representation of the function.

Crucial Distinction: The Range is a subset of the Codomain, $f(A) \subseteq B$. They are not always equal!

For example, let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x^2$.

The Domain is all real numbers. The Codomain is all real numbers. However, because squaring a real number never produces a negative, the Range is only the non-negative real numbers ($\mathbb{R}^+$). The function never “hits” the negative half of the codomain.

Well-Defined vs. Ill-Defined Functions

A function is well-defined if it perfectly obeys the two rules of functions. It is ill-defined if it breaks either rule.

Examples of Well-Defined Functions:

1. $f: \mathbb{R} \to \mathbb{R}$ where $f(x) = 2x + 1$. Every real number has a unique output. Similarly, $2x + 7, 3x -1, x^2 +2x +1, x^3, x^2 +4x +3$, etc. are all well-defined functions
2. The Identity Function: For any set $X$, the identity function $\text{id}_X: X \to X$ simply returns the input: $\text{id}_X(x) = x$.
3. $f: \mathbb{R} \setminus \{0\} \to \mathbb{R}$ where $f(x) = \frac{1}{x}$. By explicitly removing $0$ from our domain, the function is perfectly well-defined.
4. Let $A = \{a, b, c\}$, and let $P(A)$ be the power set of $A$ (the set of all subsets of the set $A$), $P(A) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$, and let $f$ be the function “cardinality” that counts the number of elements of any given set $X$ (a subset of $A$): $P(A) \to \mathbb{N}, f(X) = \vert{} X \vert{}. \emptyset \to 0; \{a\}, \{b\}, \{c\} \to 1; \{a, b\}, \{a, c\}, \{b, c\} \to 2; \{a, b, c\} \to 3$.

Examples of Ill-Defined Functions:

1. Rule 1 Violation (Missing Output): Let $f: \mathbb{R} \to \mathbb{R}$ be $f(x) = \sqrt{x}$. Because we declared the domain to be all real numbers, we are asking the function to process negative numbers. Since the square root of a negative is not a real number (it doesn’t live in the codomain), the function fails. The tangent function is undefined for $\frac{\pi}{2}+2k\pi, k \in \mathbb{Z}$; the logarithmic function $\log_b(x)$ (for any positive real number $b \ne 1$) is defined only for $x \gt 0$.
2. Rule 2 Violation (Multiple Outputs): Let $f: \mathbb{R}^+ \to \mathbb{R}$ defined by the relation $y^2 = x$. If we input $x=4$, what is the output? It could be $y=2$ or $y=-2$. Because a single input maps to two different outputs, it is not a function.
3. The Fraction Trap: Let $f: \mathbb{Q} \to \mathbb{Z}$ defined by $f\left(\frac{p}{q}\right) = p$. In words, the function outputs the numerator. This is disastrously ill-defined! The rational number one-half can be written as $\frac{1}{2}$ or $\frac{2}{4}$. Our function would say $f(\frac{1}{2}) = 1$, but $f(\frac{2}{4}) = 2$. A single rational number produces different outputs depending on how it is written!
4. 1.c’s diagram represents the set of pairs $\{(1, \text{A}), (2, \text{B}), (3, \text{C}), (3, \text{D})\}$. It does not define a function because: (i) $3$ is in more than one ordered pair, namely $(3, \text{C})$ and $(3, \text{D})$; (ii) $4$ is not a first element (input) of any ordered pair.
5. $f = \{(x, y) \in \mathbb{Z} \times \mathbb{Z} \mid 2x -3y = 1\}$ is not a function either because $(1, y) \notin f$ ($1$ is not a first element of any ordered pair). Suppose for the sake of contradiction, $\exists y$: $2(1)-3(y) = 1 \implies -3y = -1 \implies y = \frac{1}{3} \notin \mathbb{Z}$ $\bot$

Types of functions

We classify functions based on how the Domain maps into the Codomain.

1. Injective (One-to-One). An injective function guarantees that distinct inputs produce distinct outputs. It never maps two different elements of the domain to the same element in the codomain. Formally: If $f(a_1) = f(a_2)$, then $a_1 = a_2$. In other words, if we pick any element from the codomain, it is either connected to exactly one or no elements from the domain.
   Examples: $f(x) = 2x$, $g(x) = 2x + 1$ are both injective, but $f(x) = x^2$ is not, because $f(-2) = 4$ and $f(2) = 4$. Two inputs hit the same target.
   Any strictly monotonic function — one that is always strictly increasing or strictly decreasing — is guaranteed to be injective (e.g., $e^x$).  

2. Surjective (Onto). A surjective function hits everything. It guarantees that the Range is exactly equal to the Codomain. Formally: For every $y \in B$, there exists at least one $x \in A$ such that $f(x) = y$.
   $f: \mathbb{R} \to \mathbb{R}$ where $f(x) = 2x$ is surjective. For any target $y$, you can hit it by inputting $x = \frac{y}{2}$. $f: \mathbb{R} \to \mathbb{R}$ where $f(x) = x^2$ is not surjective (it never hits negatives). However, if we shrink the codomain, $g: \mathbb{R} \to \mathbb{R}^+$ where $g(x) = x^2$ is surjective!
   $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = \frac{1}{x^2+1}$ is neither injective ($f(1) = f(-1) = \frac{1}{2}$) nor surjective (there is no $x \in \mathbb{R}$ with $\frac{1}{x^2+1} = 2$, since this implies $1 = 2x^2 + 2 \implies x^2=\frac{-1}{2} \implies x=\sqrt{\frac{-1}{2}}, x ∈\mathbb{R}$ — a contradiction $\bot$).

3. Bijective. A bijective function is a perfect one-to-one pairing between two sets. It is both injective and surjective. Every element in the domain maps to exactly one unique element in the codomain, and every element in the codomain is hit exactly once.
   Examples: $f: \mathbb{R} \to \mathbb{R}$ where $f(x) = x^3$ is bijective. Any lineal function over the real numbers, $f: \mathbb{R} \to \mathbb{R},f(x) = ax + b$ with $a \ne 0$ is a bijection. $g: \mathbb{R} \to (\frac{-\pi}{2}, \frac{\pi}{2})$, given by $g(x) = \arctg(x)$ is bijective, too.

The Pigeonhole Principle

The Pigeonhole Principle is a profound observation in combinatorics that relies entirely on the definitions of injective and surjective functions.

The Pigeonhole principle states that if you put $n$ items into $m$ containers, and $n > m$, then at least one container must hold more than one item.

In the formal language of functions, let $A$ (the items) and $B$ (the containers) be finite sets, and let $f: A \to B$ be a function.

1. If $\vert{}A\vert{} > \vert{}B\vert{}$, then $f$ cannot be injective. There are not enough unique targets, so at least two inputs must hit the same target.
2. If $\vert{}A\vert{} < \vert{}B\vert{}$, then $f$ cannot be surjective. There are not enough inputs to hit every target.

Application: The Hair on Your Head

Theorem: In any city containing more than 200,000 people, there are absolutely guaranteed to be at least two people with the exact same number of hairs on their head.

Proof:

Biologists estimate that the absolute maximum number of hairs on a human head is roughly $150,000$.

Let $A$ be the set of citizens in our city. We are given $\vert{}A\vert{} > 200,000$. Let $B$ be the set of all possible hair counts on a human head. $B = \{0, 1, 2, \dots, 150,000\}$. Thus, $\vert{}B\vert{} = 150,001$.

Let $f: A \to B$ be the function that maps a citizen to their exact hair count.

Because $\vert{}A\vert{} > \vert{}B\vert{}$, the Pigeonhole Principle dictates that $f$ cannot be injective. Therefore, there must exist at least two distinct citizens, $x$ and $y$, such that $f(x) = f(y)$.

We have mathematically proven that at least two people share the exact same number of hairs, without having to count a single head! $\blacksquare$

Computer Science Connection: The Pigeonhole Principle is the mathematical reason why hash collisions are unavoidable in cryptography and software engineering. A hash function takes an infinite amount of possible inputs (like any file on a computer) and maps it to a finite, fixed-length code. Because the domain of files ($\vert{}A\vert{} = \infty$) is vastly larger than the codomain of fixed-length codes ($\vert{}B\vert{}$ is finite), the function cannot be injective. There will always be two different files that produce the exact same hash code.