Calculus

Set Theory

Set Theory Logo

Injection, Surjection, Bijection

Injection

Let f : A → B be a function from the domain A to the codomain B.

The function f is called injective (or one-to-one) if it maps distinct elements of A to distinct elements of B. In other words, for every element y in the codomain B there exists at most one preimage in the domain A:

\[\forall {x_1},{x_2} \in A:\;{x_1} \ne {x_2}\; \Rightarrow f\left( {{x_1}} \right) \ne f\left( {{x_2}} \right).\]
Injective and not injective functions
Figure 1.

A horizontal line intersects the graph of an injective function at most once (that is, once or not at all). In this case, we say that the function passes the horizontal line test.

If a horizontal line intersects the graph of a function in more than one point, the function fails the horizontal line test and is not injective.

Surjection

A function \(f\) from \(A\) to \(B\) is called surjective (or onto) if for every \(y\) in the codomain \(B\) there exists at least one \(x\) in the domain \(A:\)

\[\forall y \in B:\;\exists x \in A\; \text{such that}\;y = f\left( x \right).\]
Surjective and not surjective functions
Figure 2.

Any horizontal line should intersect the graph of a surjective function at least once (once or more).

If there is an element of the range of a function such that the horizontal line through this element does not intersect the graph of the function, we say the function fails the horizontal line test and is not surjective.

The range and the codomain for a surjective function are identical.

Bijection

A function \(f\) from set \(A\) to set \(B\) is called bijective (one-to-one and onto) if for every \(y\) in the codomain \(B\) there is exactly one element \(x\) in the domain \(A:\)

\[\forall y \in B:\;\exists! x \in A\; \text{such that}\;y = f\left( x \right).\]

The notation \(\exists! x\) means that there exists exactly one element \(x.\)

Bijective function
Figure 3.

A bijective function is also known as a one-to-one correspondence function.

Any horizontal line passing through any element of the range should intersect the graph of a bijective function exactly once.

An example of a bijective function is the identity function. The identity function \({I_A}\) on the set \(A\) is defined by

\[{I_A} : A \to A,\; {I_A}\left( x \right) = x.\]

If \(f : A \to B\) is a bijective function, then \(\left| A \right| = \left| B \right|,\) that is, the sets \(A\) and \(B\) have the same cardinality.

See solved problems on Page 2.

Page 1 Page 2