# Set Theory/Relations

## Ordered pairs

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, $(a,b)=(c,d)\iff a=c\ \wedge \ b=d$ .

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

Theorem

$(a,b)=(c,d)\iff a=c\ \wedge \ b=d$

Proof

If $a=c$  and $b=d$ , then $(a,b)=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=(c,d)$ .
Now, if $(a,b)=(c,d)$  then $\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$ . Then $\cap \{\{a\},\{a,b\}\}=\cap \{\{c\},\{c,d\}\}$ , so $\{a\}=\{c\}$  and $a=c$ .
So we have $(a,b)=(a,d)$ . Thus $\cup \{\{a\},\{a,b\}\}=\cup \{\{a\},\{a,d\}\}$  meaning $\{a,b\}=\{a,d\}$ .

If $a=b$ , we have $\{b\}=\{b,d\}$  and thus $d\in \{b\}$  so $b=d$ .
If $a\neq b$ , note $b\in \{a,d\}$ , so $b=d$

## Relations

Using the definition of ordered pairs, we now introduce the notion of a binary relation. The Cartesian Product of two sets is $A\times B=\{(a,b)\mid a\in A\wedge b\in B\}$ ,

The simplest definition of a binary relation is a set of ordered pairs. More formally, a set $\ R\$  is a relation if $z\in R\rightarrow z=(x,y)$  for some x,y. We can simplify the notation and write $(x,y)\in R$  or simply $xRy$ .

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 $R\subset A\times B.$
• The domain of a relation R is defined as ${\mbox{dom}}\ R=\{x\in A\mid \exists y,(x,y)\in R\}$ , or all sets that are the initial member of an ordered pair contained in R.
• The range of a relation R is defined as ${\mbox{ran}}\ R=\{y\in B\mid \exists x,(x,y)\in R\}$ , or all sets that are the final member of an ordered pair contained in R.
• The union of the domain and range, ${\mbox{field}}\ R={\mbox{dom}}\ R\cup {\mbox{ran}}\ R$ , is called the field of R.
• A relation R is a relation on a set X if ${\mbox{field}}\ R\subseteq X$ .
• The converse or inverse of R is the set $R^{T}=\{(y,x)\mid (x,y)\in R\}$
• The image of a set E under a relation R is defined as $R[E]=\{y\in {\mbox{ran}}\ R\mid \exists x\in E,(x,y)\in R\}$ .
• The preimage of a set F under a relation R is the image of F under RT or $R^{T}[F]=\{x\in {\mbox{dom}}\ R\mid \exists y\in F,(x,y)\in R\}$

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 $S\circ R=\{(x,z)\mid \exists y,(x,y)\in R\wedge (y,z)\in S\}$ . So $xS\circ Rz$  means that there is some y such that $xRy\wedge ySz$ .

Benchmark binary relations:

1. The identity relation on A, $I_{A}=\{(a,b)\mid a,b\in A,a=b\}$
2. The universal relation or the set where each element of A is related to every other element of A. Notation:, $A\times A$  is written $A^{2}.$

The following properties may or may not hold for a relation R on a set X:

• R is reflexive if $xRx$  holds for all x in X.
• R is symmetric if $xRy$  implies $yRx$  for all x and y in X.
• R is antisymmetric if $xRy$  and $yRx$  together imply that $x=y$  for all x and y in X.
• R is transitive if $xRy$  and $yRz$  together imply that $xRz$  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

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 ${\mathcal {P}}(U).$

The set membership relation $x\ \in \ A,\ \ A\subseteq U$  is a frequently used heterogeneous relation where the domain is U and the range is ${\mathcal {P}}(U).$

The converse of set membership is denoted by reflecting the membership glyph: $A\ \ni \ x.$

As an exercise, show that all relations from A to B are subsets of $A\times B$ .

## Functions

### Definitions

A function may be defined as a particular type of relation. We define a partial function $f:X\rightarrow Y$  as some mapping from a set $X$  to another set $Y$  that assigns to each $x\in X$  no more than one $y\in Y$ . Alternatively, f is a function if and only if $f\circ f^{-1}\subseteq I_{Y}$

If for each $x\in X$ , $f$  assigns exactly one $y\in Y$ , then $f$  is called a function. The following definitions are commonly used when discussing functions.

• If $f\subseteq X\times Y$  and $f$  is a function, then we can denote this by writing $f:X\to Y$ . The set $X$  is known as the domain and the set $Y$  is known as the codomain.
• For a function $f:X\to Y$ , the image of an element $x\in X$  is $y\in Y$  such that $f(x)=y$ . Alternatively, we can say that $y$  is the value of $f$  evaluated at $x$ .
• For a function $f:X\to Y$ , the image of a subset $A$  of $X$  is the set $\{y\in Y:f(x)=y{\mbox{ for some }}x\in A\}$ . This set is denoted by $f(A)$ . Be careful not to confuse this with $f(x)$  for $x\in X$ , which is an element of $Y$ .
• The range of a function $f:X\to Y$  is $f(X)$ , or all of the values $y\in Y$  where we can find an $x\in X$  such that $f(x)=y$ .
• For a function $f:X\to Y$ , the preimage of a subset $B$  of $Y$  is the set $\{x\in X:f(x)\in B\}$ . This is denoted by $f^{-1}(B)$ .

### Properties of functions

A function $f:X\rightarrow Y$  is onto, or surjective, if for each $y\in Y$  exists $x\in X$  such that $f(x)=y$ . 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 $X$  are mapped to different elements of $Y$ , that is $f(x)=f(y)\Rightarrow x=y$ . A function that is both injective and surjective is intuitively termed bijective.

### Composition of functions

Given two functions $f:X\rightarrow Y$  and $g:Y\rightarrow Z$ , we may be interested in first evaluating f at some $x\in X$  and then evaluating g at $f(x)$ . To this end, we define the composition of these functions, written $g\circ f$ , as

$(g\circ f)(x)=g(f(x))$

Note that the composition of these functions maps an element in $X$  to an element in $Z$ , so we would write $g\circ f:X\rightarrow Z$ .

### Inverses of functions

If there exists a function $g:Y\rightarrow X$  such that for $f:X\rightarrow Y$ , $g\circ f=I_{X}$ , we call $g$  a left inverse of $f$ . If a left inverse for $f$  exists, we say that $f$  is left invertible. Similarly, if there exists a function $h:Y\rightarrow X$  such that $f\circ h=I_{Y}$  then we call $h$  a right inverse of $f$ . If such an $h$  exists, we say that $f$  is right invertible. If there exists an element which is both a left and right inverse of $f$ , we say that such an element is the inverse of $f$  and denote it by $f^{-1}$ . 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 $g$  and a right inverse $h$ , then $g=h=f^{-1}$ .

Theorem: A function is invertible if and only if it is bijective.