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 sets 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 simple definition, then is $(a,b)=\{\{a\},\{a,b\}\}$. (This is true simply by definition. It is a convention that we can usefully build upon, and has no deeper significance.)

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 \ne b$, note $b \in \{a,d\}$, so $b=d$

Relations

Using the definiton of ordered pairs, we now introduce the notion of a binary relation.

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 $x R y$.

We give a few useful definitions of sets used when speaking of relations.

• The domain of a relation R is defined as $\mbox{dom}\ R = \{x \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 \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 inverse of R is the set $R^{-1}=\{(y,x) \mid (x,y) \in R\}$

• The image of a set A under a relation R is defined as $R[A] = \{y\in \mbox{ran}\ R \mid \exists x \in A, (x,y)\in R\}$.

• The preimage of a set B under a relation R is the image of B over R^-1 or $R^{-1}[B] = \{x\in \mbox{dom}\ R \mid \exists y \in B, (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 $x S \circ R z$ means that there is some y such that $xRy \wedge ySz$.

We can define a few useful binary relations as examples:

1. The Cartesian Product of two sets is $A \times B = \{(a,b) \in \mathcal{P}(\mathcal{P}(A\cup B)) \mid a \in A \wedge b \in B\}$, or the set where all elements of A are related to all elements of B. As an exercise, show that all relations from A to B are subsets of $A \times B$. Notationally $A \times A$ is written $A^2$
2. The membership relation on a set A, $\in_A = \{(a,b) \mid a, b \in A, a \in b\}$
3. The identity relation on A, $I_A = \{(a,b) \mid a,b \in A, a=b\}$

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

• R is reflexive if $x R x$ holds for all x in X.
• R is symmetric if $x R y$ implies $y R x$ for all x and y in X.
• R is antisymmetric if $x R y$ and $y R x$ together imply that $x = y$ for all x and y in X.
• R is transitive if $x R y$ and $y R z$ together imply that $x R z$ holds for all x, y, and z in X.
• R is total if $x R y$, $y R x$, or both hold for all x and y in X.

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 on each $x \in X$, $f$ assigns exactly one $y \in Y$, then $f$ is called total function or just 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.