# 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 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.)

**Theorem**

**Proof**

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
*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*or^{-1}

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*.

## 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.