Relations and Functions between Small Sets

A relation between two sets and is a subset of the Cartesian product ; is called the source set and is called the target set. If contains elements and contains elements, there are relations between and . If is a relation between and , the inverse of is the subset of consisting of all pairs where belongs to .

A function is a relation that contains no two pairs with the same first coordinate and distinct second coordinates. A function can be thought of as a rule that assigns to each element in a subset of the source (called the domain now) exactly one element in the target. The range is the subset of the target that consists of elements to which some element of the domain has been assigned. The function maps the domain to the range, and if a function called assigns an element to an element , it is written as . The relation that defines a function, that is, the collection of all pairs of the form for in the domain, is called the graph of the function.

There are different functions that map an -element domain into an -element target. (The sets in question must be finite for any formulas to do with and , but the definitions apply to infinite sets such as the real numbers.)

A function is one-to-one (also called an injection) if no two elements of the domain are assigned to the same element of the range. Visually, a function is one-to-one if no horizontal line intersects its graph more than once. The inverse of a function is itself a function if and only if the function is an injection. For any injections to exist, the target must be at least as large as the domain, that is, , in which case there are injections mapping an -element domain into an -element target.

A function is onto (also called a surjection) if the target and the range are the same set. For any surjections to exist, the domain must be at least as large as the target, that is, , in which case there are surjections mapping an -element domain onto an -element range.

A function that is both one-to-one and onto is called a bijection. For any bijections to exist, the domain and target must be the same size, that is, , in which case there are bijections mapping one -element set to another.