Bijections

A bijection, or one-to-one correspondence, between sets A and B is a function f: A → B that is both injective and surjective. Injective means that different elements of A map to different elements of B (f(a1) = f(a2) implies a1 = a2). Surjective means that every element of B is the image of some element of A (for every b in B, there exists a in A with f(a) = b). When these conditions hold, each element of A is paired with a unique element of B, and every element of B is paired with exactly one element of A.

A bijection has an inverse function f^{-1}: B → A, defined by f^{-1}(b) = a whenever f(a) = b. This inverse is a function and satisfies f^{-1}(f(a)) = a for all a in A and f(f^{-1}(b)) = b for all b in B. Bijections therefore establish a perfect pairing between the two sets and imply that A and B have the same cardinality.

Key properties include that the composition of bijections is a bijection, and a bijection preserves the size of subsets: the image of a subset under a bijection has the same cardinality as the subset itself.

Examples include the identity function on any set, which is trivially a bijection, and a permutation of a finite set, which is a bijection from the set to itself. A function like f(n) = 2n from the natural numbers to the natural numbers is not a bijection unless the codomain is restricted to the even numbers, in which case it is bijective. Not every function is a bijection; non-injective or non-surjective functions fail to be bijections.