# 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, ${\displaystyle (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 ${\displaystyle (a,b)=\{\{a\},\{a,b\}\}}$. (This is simply a definition or a convention that can be useful for set theory.)

Theorem

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

Proof

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

If ${\displaystyle a=b}$, we have ${\displaystyle \{b\}=\{b,d\}}$ and thus ${\displaystyle d\in \{b\}}$ so ${\displaystyle b=d}$.
If ${\displaystyle a\neq b}$, note ${\displaystyle b\in \{a,d\}}$, so ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \ R\ }$ is a relation if ${\displaystyle z\in R\rightarrow z=(x,y)}$ for some x,y. We can simplify the notation and write ${\displaystyle (x,y)\in R}$ or simply ${\displaystyle 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 ${\displaystyle R\subset A\times B.}$
• The domain of a relation R is defined as ${\displaystyle {\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 ${\displaystyle {\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, ${\displaystyle {\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 ${\displaystyle {\mbox{field}}\ R\subseteq X}$.
• The converse or inverse of R is the set ${\displaystyle R^{T}=\{(y,x)\mid (x,y)\in R\}}$
• The image of a set E under a relation R is defined as ${\displaystyle 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 ${\displaystyle R^{T}[F]=\{x\in {\mbox{dom}}\ R\mid \exists y\in F,(x,y)\in R\}}$

The kinship relations uncle of and aunt of show that there are compositions of relations parent of and sibling of. Such compositions express relative multiplication:

We can compose two relations R and S to form one relation ${\displaystyle S\circ R=\{(x,z)\mid \exists y,(x,y)\in R\wedge (y,z)\in S\}}$. So ${\displaystyle xS\circ Rz}$ means that there is some y such that ${\displaystyle xRy\wedge ySz}$.

Benchmark binary relations:

1. The identity relation on A, ${\displaystyle 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:, ${\displaystyle A\times A}$ is written ${\displaystyle A^{2}.}$

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

• R is reflexive if ${\displaystyle xRx}$ holds for all x in X.
• R is symmetric if ${\displaystyle xRy}$ implies ${\displaystyle yRx}$ for all x and y in X.
• R is antisymmetric if ${\displaystyle xRy}$ and ${\displaystyle yRx}$ together imply that ${\displaystyle x=y}$ for all x and y in X.
• R is transitive if ${\displaystyle xRy}$ and ${\displaystyle yRz}$ together imply that ${\displaystyle 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 ${\displaystyle {\mathcal {P}}(U).}$

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

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

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

## Functions

### Definitions

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

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

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

### Properties of functions

A function ${\displaystyle f:X\rightarrow Y}$ is onto, or surjective, if for each ${\displaystyle y\in Y}$ exists ${\displaystyle x\in X}$ such that ${\displaystyle 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 ${\displaystyle X}$ are mapped to different elements of ${\displaystyle Y}$, that is ${\displaystyle 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 ${\displaystyle f:X\rightarrow Y}$ and ${\displaystyle g:Y\rightarrow Z}$, we may be interested in first evaluating f at some ${\displaystyle x\in X}$ and then evaluating g at ${\displaystyle f(x)}$. To this end, we define the composition of these functions, written ${\displaystyle g\circ f}$, as

${\displaystyle (g\circ f)(x)=g(f(x))}$

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

### Inverses of functions

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

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