To define relations on sets we must have a concept of an ordered pair, as opposed to the unordered pairs the axiom of pair gives. To have a rigorous definition of ordered pair, we aim to satisfy one important property, namely, for sets a,b,c and d, .
As it stands, there are many ways to define an ordered pair to satisfy this property. A simple definition, then is . (This is true simply by definition. It is a convention that we can usefully build upon, and has no deeper significance.)
If and , then .
Now, if then . Then , so and .
So we have . Thus meaning .
- If , we have and thus so .
- If , note , so
Using the definiton of ordered pairs, we now introduce the notion of a binary relation.
The Cartesian Product of two sets is ,
The simplest definition of a binary relation is a set of ordered pairs. More formally, a set is a relation if for some x,y. We can simplify the notation and write or simply .
We give a few useful definitions of sets used when speaking of relations.
- The domain of a relation R is defined as , or all sets that are the initial member of an ordered pair contained in R.
- The range of a relation R is defined as , or all sets that are the final member of an ordered pair contained in R.
- The union of the domain and range, , is called the field of R.
- A relation R is a relation on a set X if .
- The converse or inverse of R is the set
- The image of a set A under a relation R is defined as .
- The preimage of a set B under a relation R is the image of B over R-1 or
It is intuitive, when considering a relation, to seek to construct more relations from it, or to combine it with others.
We can compose two relations R and S to form one relation . So means that there is some y such that .
Benchmark binary relations:
- The identity relation on A,
- The universal relation or the set where each element of A is related to every other element of A. Notation:, is written
The following properties may or may not hold for a relation R on a set X:
- R is reflexive if holds for all x in X.
- R is symmetric if implies for all x and y in X.
- R is antisymmetric if and together imply that for all x and y in X.
- R is transitive if and together imply that holds for all x, y, and z in X.
- R is total if , , or both hold for all x and y in X.
When A and B are different sets, the relation is heterogeneous. Then relations on a single set A are called homogeneous relations.
Let U be a universe of discourse in a given context. By the power set axiom, there is a set of all the subsets of U called the power set of U written
The set membership relation is a frequently used heterogeneous relation where the domain is U and the range is
The converse of set membership is denoted by reflecting the membership glyph:
As an exercise, show that all relations from A to B are subsets of .
A function may be defined as a particular type of relation. We define a partial function as some mapping from a set to another set that assigns to each no more than one . Alternatively, f is a function if and only if
If for each , assigns exactly one , then is called a function. The following definitions are commonly used when discussing functions.
- If and is a function, then we can denote this by writing . The set is known as the domain and the set is known as the codomain.
- For a function , the image of an element is such that . Alternatively, we can say that is the value of evaluated at .
- For a function , the image of a subset of is the set . This set is denoted by . Be careful not to confuse this with for , which is an element of .
- The range of a function is , or all of the values where we can find an such that .
- For a function , the preimage of a subset of is the set . This is denoted by .
Properties of functions
A function is onto, or surjective, if for each exists such that . It is easy to show that a function is surjective if and only if its codomain is equal to its range. It is one-to-one, or injective, if different elements of are mapped to different elements of , that is . A function that is both injective and surjective is intuitively termed bijective.
Composition of functions
Given two functions and , we may be interested in first evaluating f at some and then evaluating g at . To this end, we define the composition of these functions, written , as
Note that the composition of these functions maps an element in to an element in , so we would write .
Inverses of functions
If there exists a function such that for , , we call a left inverse of . If a left inverse for exists, we say that is left invertible. Similarly, if there exists a function such that then we call a right inverse of . If such an exists, we say that is right invertible. If there exists an element which is both a left and right inverse of , we say that such an element is the inverse of and denote it by . Be careful not to confuse this with the preimage of f; the preimage of f always exists while the inverse may not. Proof of the following theorems is left as an exercise to the reader.
Theorem: If a function has both a left inverse and a right inverse , then .
Theorem: A function is invertible if and only if it is bijective.