Functions as Sets: The Set-Theoretic Definition

A function is a set of ordered pairs with a rule: no two pairs share the same first element.

That's it. The function f(x) = x² on {1, 2, 3} is the set {(1, 1), (2, 4), (3, 9)}. Each input appears exactly once as a first element. Each maps to exactly one output.

A function is a special subset of a Cartesian product.

That's the unlock. In set theory, we don't say "f takes x and produces f(x)" as if the function does something. We say f is a collection of input-output pairs that happens to satisfy a uniqueness condition. The function is the pairs.

The Definition

A function f from set A to set B is a subset of A × B such that:

For every a ∈ A, there exists exactly one b ∈ B with (a, b) ∈ f.

We write f : A → B.

• A is the domain — the set of inputs
• B is the codomain — the set of possible outputs
• f(a) = b means (a, b) ∈ f

The Uniqueness Condition

The condition "exactly one b" is what makes a function a function.

If (a, b₁) ∈ f and (a, b₂) ∈ f, then b₁ = b₂.

No input maps to two different outputs. That would make f ambiguous, undefined.

Functions vs. Relations

A relation from A to B is any subset of A × B. No restrictions.

A function is a relation where every element of A appears exactly once as a first component.

All functions are relations. Not all relations are functions.

The relation {(1, 2), (1, 3), (2, 4)} is not a function: 1 maps to both 2 and 3. The relation {(1, 2), (3, 4)} from {1, 2, 3} to {2, 3, 4} is not a function: 2 has no image.

Domain, Codomain, Range

Domain: the set of all first components. Every element of the domain must appear in a pair.

Codomain: the target set B. Elements of B don't have to appear.

Range (or image): the set of all second components. The outputs that actually occur.

For f : {1, 2, 3} → ℤ defined by f = {(1, 2), (2, 4), (3, 6)}:

• Domain = {1, 2, 3}
• Codomain = ℤ
• Range = {2, 4, 6}

Range ⊆ codomain, but they may not be equal.

Notation: f(a) = b

If (a, b) ∈ f, we write f(a) = b.

"f of a equals b" means the pair (a, b) is in the function.

This notation hides the set structure, making functions feel like "machines." But underneath, f(a) = b is just membership: (a, b) ∈ f.

Example: Squaring Function

Let f : {-2, -1, 0, 1, 2} → ℕ be defined by f(x) = x².

As a set: f = {(-2, 4), (-1, 1), (0, 0), (1, 1), (2, 4)}

Notice: different inputs can map to the same output. That's allowed. What's forbidden is one input mapping to multiple outputs.

Injective (One-to-One)

A function f : A → B is injective (or one-to-one) if:

f(a₁) = f(a₂) implies a₁ = a₂

Different inputs give different outputs. No collisions.

As sets: no two pairs share the same second element.

The squaring function on {-2, -1, 0, 1, 2} is not injective: f(-1) = f(1) = 1.

Surjective (Onto)

A function f : A → B is surjective (or onto) if:

For every b ∈ B, there exists some a ∈ A with f(a) = b.

Every element of the codomain is hit. Range = codomain.

As sets: every element of B appears as a second component.

Bijective (One-to-One and Onto)

A function is bijective if it's both injective and surjective.

Every input maps to a unique output, and every output is hit exactly once.

Bijections pair A and B perfectly — this is how we defined "same cardinality."

Composition of Functions

If f : A → B and g : B → C, the composition g ∘ f : A → C is:

(g ∘ f)(a) = g(f(a))

As sets: g ∘ f = {(a, c) : there exists b with (a, b) ∈ f and (b, c) ∈ g}

Apply f first, then g.

Inverse Functions

If f : A → B is a bijection, its inverse f⁻¹ : B → A is:

f⁻¹ = {(b, a) : (a, b) ∈ f}

Swap the pairs. Since f is bijective, f⁻¹ is well-defined and also a bijection.

f⁻¹(f(a)) = a and f(f⁻¹(b)) = b.

Identity Function

The identity function on A is:

idₐ = {(a, a) : a ∈ A}

Every element maps to itself.

For any f : A → B: f ∘ idₐ = f id_B ∘ f = f

The Graph of a Function

In calculus, you "graph" f(x) by plotting points (x, f(x)).

In set theory, the function is the graph. There's no separate function "behind" the graph. The set of points IS the function.

Why Define Functions as Sets?

The set-theoretic definition:

• Makes functions precise objects
• Allows us to apply set operations (intersection, cardinality, etc.)
• Unifies functions with relations
• Clarifies what a function "is" rather than what it "does"

You can ask: how many functions are there from A to B? Answer: |B|^|A|. The power makes sense because you're counting subsets of A × B that satisfy the function condition.

Partial Functions

A partial function from A to B is a function from some subset of A to B.

Not every element of A needs an image. Division is a partial function on ℝ × ℝ — undefined when the second argument is 0.

Partial functions are subsets of A × B where each first element appears at most once.

The Core Insight

Functions are sets — specifically, sets of ordered pairs satisfying a uniqueness constraint.

This definition strips away the metaphor of "input-output machines" and reveals the underlying structure. A function from A to B is a certain kind of subset of A × B.

When you understand functions as sets, abstract concepts (composition, inverse, cardinality of function spaces) become operations on sets. The abstraction makes everything more precise and more general.

Part 11 of the Set Theory series.

Previous: Cardinality: Counting the Uncountable Next: Synthesis: Set Theory as the Foundation of Mathematics