Functions and Relations


The cross product of two sets A and B is the set of ordered pairs where the first element is from A and the second is from B. This definition may be written symbolically as:

AxB = {(a,b) : a is in A and b is in B}.


A relation on two sets A and B is an arbitrary subset of the cross product. That is, a relation is an arbitrary set of ordered pairs with the first element from the set A and the second from B.


A function f mapping set A to set B is a relation over A and B such that:

  1. for each a in A there exists an element b in B such that (a,b) is in f
  2. if (a,b) is in f and (a,c) is in f then b = c.

Alternatively, for each element a in A there exists a unique b in B such that b = f(a).

Notes on Functions and Notation

For a function mapping the set A to the set B, the set A is referred to as the domain of the function; whereas, the set B is referred to as the codomain of the function.

An example of the most common and slackest functional notation is f(x) = 2x or y = 2x. The first derives from Newton and the second from Leibnitz. These forms of functional notation do not explicitly specify the domain or codomain of the function. It could be a function on integers, rationals, reals or over the complex field or any other group defining a multiplicative operation. A more complete system of functional notation specifies:

The linear function discussed above would be specified as:

f : R -> R
x |-> 2x

Note that for this function, every element in the domain maps to one and only one element in the codomain. It may be the case that not every element of the codomain has an element of the domain mapping to it. For example, the absolute value function:

f : R -> R
x |-> |x|

maps negative numbers to their positive counterparts; thus, only non-negative numbers are mapped to from the domain.

The set of elements within the codomain that are mapped to from some element in the domain is called the range; that is,

Range = {y : there exists an x such that y = f(x)}

For the absolute value function above, the codomain is R whereas the range is the non-negative reals.

A function is onto (surjective) if the range equals the codomain.

A function is 1 to 1 (injective) if no two elements in the domain map to the same element in the codomain. The absolute value function above is not injective since both 2 and -2 map to 2.

A function is bijective when it is both injective and surjective.