Bijection, injection and surjection

Lore & Background

A function is injective, or one-to-one, if each element of the codomain is mapped to by at most one element of the domain, or equivalently, if distinct elements of the domain map to distinct elements in the codomain. An injective function is also called an injection. Notationally: ∀x,x'∈X, f(x)=f(x') ⇒ x=x'. A function is surjective, or onto, if each element of the codomain is mapped to by at least one element of the domain; that is, if the image and the codomain of the function are equal. A surjective function is a surjection. Notationally: ∀y∈Y, ∃x∈X, y=f(x). The function is bijective (one-to-one and onto, one-to-one correspondence, or invertible) if each element of the codomain is mapped to by exactly one element of the domain; that is, if the function is both injective and surjective. A bijective function is also called a bijection.

Reader's Guide

Injections, surjections, and bijections provide a foundational classification for functions in mathematics. An injective function need not be surjective, and a surjective function need not be injective. The composition of two injections is again an injection, but if g∘f is injective, then it can only be concluded that f is injective. Every injection induces a bijection onto its image, and every surjection induces a bijection from a quotient set of its domain to its codomain. These concepts are essential for understanding invertibility, cardinality, and the structure of mathematical mappings. The formal definitions and properties given in the source article are the only facts used here.

Did You Know?

• A function is injective if and only if X is empty or f is left-invertible.
• A function is surjective if and only if it is right-invertible, a statement equivalent to the axiom of choice.
• The composition of two injections is again an injection.
• Every embedding is injective.

Bijection as the Engine of Enumeration

In the landscape of set theory, a bijection serves as the most precise tool for pairing elements between two collections. When we speak of enumerating a set S, the standard definition calls for a bijective function mapping either the full set of natural numbers or a finite initial segment {1, ..., n} onto S. This one-to-one correspondence guarantees that every element of S is hit exactly once, leaving no gaps and no duplicates. The natural numbers themselves are enumerated by the identity function f(x) = x, the simplest possible bijection from N to N. A more intricate example is the bijection from N₀ to the integers Z, defined by the formula f(x) = [1 − (−1)^x (2x + 1)] / 4, which interleaves positive and negative integers in a single sequence. For any non-empty finite set with n elements, one can construct a bijection from {1, 2, ..., n} to that set by sequentially assigning each element a distinct natural number. In this way, bijection is not merely a property of a function but the very mechanism that makes a complete, ordered listing possible.

Surjection and the Architecture of Ordered Lists

While bijection demands a perfect one-to-one pairing, surjection plays a distinct and equally important role in the theory of enumeration. In set theory, an ordered enumeration is formally defined as a surjection—meaning an onto mapping—whose domain carries a well-ordering. This characterization is considered natural because a well-ordering on the index set provides a unique, unambiguous rule for determining which element comes next once a partial listing has been established. The surjection requirement is deliberately broader than bijection: it permits the listing to be onto without insisting that every index maps to a distinct element, thereby accommodating greater generality. The well-ordering prerequisite, while the most natural and common choice, is not the only possible ordering structure one could impose. By relaxing the requirement from bijection to surjection, the framework remains flexible enough to handle sets where a strict one-to-one correspondence with the index set is either unnecessary or impossible, while still guaranteeing that every member of the target set appears in the listing at least once.

Injection as the Test for Countability

A set is called countable precisely when it can be enumerated, meaning a bijection exists from the natural numbers (or a finite initial segment thereof) to that set. However, an equivalent and often more convenient characterization sidesteps the need to distinguish between finite and countably infinite sets: a set S is countable if and only if there exists an injective function from S into the natural numbers. This injection-based definition is particularly useful because it unifies the treatment of finite sets and countably infinite sets under a single criterion. The term "enumerable" is sometimes applied to countable sets, but it also carries a second meaning in computability theory, referring to computably enumerable sets—those countable sets for which an explicit algorithm can produce the enumeration function. The injection perspective thus provides a clean, direction-reversed test: rather than building a list from N into S, one simply needs to show that S can be embedded without collisions into N, confirming that S is no larger than the natural numbers.

The Boundary of Countability and Cantor's Barrier

Not every set can be captured by a countable enumeration, and the boundary between those that can and those that cannot is one of the most consequential distinctions in mathematics. The set of real numbers stands as the canonical example of an uncountable set: Cantor's diagonal argument and his first uncountability proof both demonstrate that no bijection from the natural numbers (or any finite initial segment) onto the reals can exist. This means that no listing, no matter how cleverly ordered, can exhaust the real line. In contrast, the integers, the natural numbers, and every non-empty finite set all admit countable enumerations, and any finite set with n elements possesses exactly n! distinct enumerations when one requires the listing to be injective and to respect a limited form of partiality. The existence of uncountable sets thus reveals a fundamental limitation: the natural numbers, for all their infinite reach, are not large enough to index every conceivable collection, and the hierarchy of infinities extends well beyond what a single enumeration can reach.

Gallery