Set Theory/Relations

Ordered pairs edit

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 elements in a set a,b,c and d,  .

As it stands, there are many ways to define an ordered pair to satisfy this property. A definition, then is  . (This is simply a definition or a convention that can be useful for set theory.)




If   and  , then  .
Now, if   then  . Then  , so   and  .
So we have  . Thus   meaning  .

If  , we have   and thus   so  .
If  , note  , so  

Relations edit

Using the definition 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 set A is the source and B is the target, with  
  • 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 E under a relation R is defined as  .
  • The preimage of a set F under a relation R is the image of F under RT 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:

  1. The identity relation on A,  
  2. 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 the domain of R is A, the source
  • R is univalent if xRy and xRz imply y = z.
  • A relation that is both total and univalent is called a function.

Heterogeneous relations edit

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  .

Functions edit

Definitions edit

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 edit

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 edit

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 edit

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.

Zermelo-Fraenkel (ZF) Axioms · Constructing Numbers