Bijection

A bijection between two sets, \(X\) and \(Y\), is a "one-to-one pairing" of their elements. Formally, it is a function \(f: X \to Y\) (which can be encoded as a subset of \(X \times Y\)) so that:

• Different elements of \(X\) are sent to different elements of \(Y\).
• Every element of \(Y\) has some element of \(X\) which is sent to \(Y\).

The first property is known as injectivity, or being 1-1, and can be formally be written as \(f(x) = f(y)\) only if \(x = y\). The second property is known as surjectivity, or being onto, and can be formally written as, for all \(y \in Y\), there is \(x \in X\) so that \(f(x) = y\). Bijections are used to define cardinals and cardinality.