Axioms of simple or linear order

If C is a collection of elements{x, y, z, …}, C is simply ordered relative to < if:

If x and y are distinct elements of C then x < y or* y < x,
If x < y then x and y are distinct, and
If x < y and y < z, then x < z.

* ‘Or’ is used in the inclusive sense.

Binary relations

A binary relation between two sets A and B is a subset of A x B. A binary relation on a set A is a subset of R = A x A. If (x, y) ϵ R we also write x R y. Generalization to ternary and quaternary relations is straightforward.

Relations are very general—since A x B is a subset of A x B, in that relation every element of A is related to every element of B.

A particular kind of relation might be a parent-child relation or an ‘is over’ relation.

Some mathematical binary relations of interest are functions, functions with inverses, 1-1 correspondences, simple order, greater than, and equivalence relations.

Functions

A function is a map from a domain (set) A to a range (set) B such that to every element of A there corresponds one element of B (that is, multivalued maps are not functions in this sense). We write f: A ® B, to denote that f is a function on A that maps to B or ‘f is a function from A to B. If y is the element of B that corresponds to the element x of A, we write f: x ® y or, traditionally, y = f(x). The element of B to which x in A maps is called the image of x. If a subset A' of A maps to a subset B' of B, then B' is called the image of A'; note that these uses of ‘image’ are different. The image of A is called the codomain of the function and is a subset of B (i.e. either B or a proper subset of B. Note that some writers (Bourbaki) interchange these meanings of range and codomain.

An injection or injective function or one-to-one function is a function that maps every point in A to a distinct point in B, i.e. if x ¹ x' then f(x) ¹ f(x'). The codomain of an injection is not necessarily the range, so injections are not necessarily invertible. However, if we define a new function as the same as f but with the codomain as the range then the new function is invertible.

A surjection or surjective function is one for which every point in the range is the image of at least one point in the domain, i.e. for which the range is the codomain. Since an element of the range may be mapped to by more than one element of the domain, a surjective function is not necessarily invertible. By restricting the range to the codomain, a general function will become surjective.

A bijection or bijective function is one that is injective and surjective; for a bijection, every element of the domain maps to a unique element of the range and to every element of the range there is a unique element in the domain. A bijection is a one-to-one-correspondence (but note that a one-to-one function is not necessarily a one-to-one-correspondence), i.e. the elements of the domain and the range can be ‘lined up’ so that for finite sets the domain and range have the same number of elements. Therefore there cannot be a 1:1 correspondence between a finite set and one of its proper subsets. This is not true for infinite sets. In fact one definition of an infinite set is that it is one for which there is a 1:1 correspondence between the set and one of its proper subsets.

Equivalence relations

An binary relation, » , on a collection S of elements {x, y, z, …} is one for which

If x ϵ S then x » x,
If x » y then y » x,
If x » y and y » z, then x » z.

Modular arithmetic

The modulo relation a º b (mod m), where a, b, and m are integers, means that a is the smallest integer such that and b differ by a multiple of m. Clearly, 0 £ a < m.

With the modulo relation may be used as defining an equivalence relation. For example, if m = 5, then {0, 5, 10, …}, {1, 6, 11, …} … form equivalence classes and can be treated as elements.

On this basis, a modular arithmetic can be developed.