Relations and Functions

Ordered pairs, Cartesian products, power set

Given two objects $x$ and $y$ , we can form the ordered pair $(x,y)$ . Unlike the pair set $\{x,y\}$ , the order in which the elements appear is important: given two ordered pairs $(x,y)$ and $(u,v)$ , we have

Similarly, we have ordered triples $(x,y,z)$ , ordered 4-tuples $(w,x,y,z)$ , and so on, where if $(x_1,x_2,\dots,x_n)$ and $(y_1,y_2,\dots,y_n)$ are ordered $n$ -tuples then

for $i=1,2,\dots,n.$

Given sets $A$ and $B$ , we form the Cartesian product of $A$ and $B$ , written $A\times B$ , defined by

If $A$ and $B$ are finite sets then $|A\times B|=|A|\cdot|B|$ .

If $A_1$ , $A_2$ , … , $A_n$ are sets, we define $A_1\times A_2\times\dots\times A_n$ to be the set of all $n$ -tuples $(a_1,a_2,\dots,a_n)$ where $a_i\in A_i$ for $i=1,2,\dots,n$ .

We sometimes write $A^n$ for $\underbrace{A\times A\times\dots\times A}_{\text{n times}}$ . In particular, we often write $A^2$ for $A\times A$ .

of a Cartesian product.

Example 4.2 _What is the Cartesian product $A\times B\times C$ where $A=\{ 0,1 \} , B= \{1,2 \}$ , and $C = \{ 0,1,2 \}$ ? What is $(A\times B)\times C)$ ?

Given a set $A$ we can form the power set of $A$ , power set denoted by $\mathcal P(A)$ , containing all the subsets of $A$ .

We will show later that if $A$ has $n$ elements then $\mathcal P(A)$ has $2^n$ elements.

Relations

Let $A$ and $B$ be sets. A binary relation from $A$ to $B$ is a subset of $A\times B$ . A binary relation on $A$ is a subset of $A\times A$ .

We use binary relations to represent relationships between the elements of $A$ and the elements of $B$ . If $R$ is a binary relation from $A$ to $B$ , and $(x,y)\in A\times B$ , then $(x,y)\in R$ if and only if the relationship holds between the element $x$ and the element $y$ .

$(x,y)\in R\qquad\Leftrightarrow\qquad x<y$ .

Then we have $R=\{(1,2),(1,3),(2,3)\}$ .

We often use infix notation for relations. In other words, we write $(x,y)\in R$ as $x R y$ . This is particularly common with relations like $<$ , $=$ , $\subseteq$ and so on that have standard names. If $(x,y)\notin R$ , we write $x\not R y$ .

There are various properties that a relation on a set might or might not have. We say that a relation $R$ on a set $A$ is

• reflexive if for all $x\in A$ , $x R x$ .
• symmetric if for all $x,y\in A$ , if $x R y$ then $y R x$ .
• antisymmetric if for all $x,y\in A$ , if $x R y$ and $y R x$ then $x=y$ .
• transitive if for all $x,y,z\in A$ , if $x R y$ and $y R z$ then $x R z$ .

$a\mid b \qquad \Leftrightarrow \qquad \text{for some}\ c\in \Z, b=ac$ .

Which of the above properties hold?

Equivalence relations

Let $A$ be a set. An equivalence relation on $A$ is a binary relation on $A$ that is reflexive, symmetric and transitive. We often use symbols like $\sim$ , $\equiv$ and $\cong$ for equivalence relations.

Does the answer change if we define $x\R y$ to mean that $x$ has the same mother or father as $y$ ?

is an equivalence relation.

is an equivalence relation. We call this relation the equivalence relation induced by $f$ .

Let $\sim$ be an equivalence relation on a set $A$ , and let $x\in A$ . The equivalence class of $x$ under $\sim$ , denoted by $[x]$ , is the set of all elements of $A$ that are related to $x$ under $\sim$ , i.e.

We denote the set of equivalence classes of elements of $A$ under $\sim$ by $[A]$ or by $A/{\sim}$ .

Solution. $[1]=\{1,-1\}$ , $[14]=\{14,-14\}$ , and $[0]=\{0\}$ .

If $\sim$ is an equivalence relation on $A$ , and $x,y\in A$ , then the following are equivalent:

1. $x\sim y$ .
2. $[x]=[y]$ .
3. $[x]\cap[y]\ne\emptyset$ .

Proof: We show that (1) implies (2), (2) implies (3) and (3) implies (1).

$(1)\Rightarrow(2)$ Suppose $x\sim y$ . Let $z\in[y]$ . Then $y\sim z$ , so we have $x\sim y\sim z$ , and so by transitivity we have $x\sim z$ . Thus $z\in[x]$ . Hence $[y]\subseteq [x]$ . Conversely, let $w\in[x]$ . Then $x\sim w$ , so by symmetry we have $w\sim x.$ So $w\sim x\sim y$ , and so $w\sim y$ . Hence $y\sim w$ , so $w\in[y]$ . Thus $[x]\subseteq[y]$ , so $[x]=[y]$ .

$(2)\Rightarrow(3)$ Suppose $[x]=[y]$ . Then $[x]\cap[y]=[x]\cap[x]=[x]$ . By reflexivity, $x\sim x$ , so $x\in [x]$ , so $[x]\ne\emptyset$ . Thus $[x]\cap[y]\ne\emptyset.$

$(3)\Rightarrow(1)$ Suppose $[x]\cap[y]\ne\emptyset$ . Let $z\in[x]\cap[y]$ . Then $x\sim z$ and $y\sim z$ . By symmetry, we have $z\sim y$ , so $x\sim z\sim y$ , and therefore by transitivity we have $x\sim y$ .

Hence (1), (2) and (3) are equivalent.

In other words, if $[x]$ and $[y]$ are equivalence classes then either $[x]=[y]$ or $[x]$ and $[y]$ are disjoint. We say that the relation $\sim$ partitions the set $A$ .

Definition 4.1 A (finite) partition of a set $X$ is a set $\{ X_1, \dots, X_t \}$ where $X_i \subseteq X$ , $X_i \ne \emptyset$ and:

1. $X_i \cap X_j = \emptyset$ when $1 \le i < j \le t$ ;
2. $X_1 \cup X_2 \cup \cdots \cup X_t = X$ .

An example of a partition is cutting a cake into pieces: No slice of cake is empty, slices of cake have no crumbs in common, putting the slices together forms the whole cake.

Solution. $[1]=\{1,-1\}$ , $[14]=\{14,-14\}$ , and $[0]=\{0\}$ .

The graph representing an equivalence relation on a finite set is a union of complete graphs (with loops at every vertex).

Partial orderings

A commonly used type of relation is an ordering. For instance, words in a dictionary are ordered using a relation called “lexicographical ordering”. We also order real numbers and integers in familiar ways.

Consider the usual ordering on $\Z$ . Then the set of integers satisfying the relation is $\{ (x, y) \in \Z^2 \mid x \le y \}$ . One can verify that this relation is reflexive, antisymmetric, and transitive. Other relations that have these properties can be considered to be somehow “analogous” to familiar orderings.

A relation $R$ on a set $S$ is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set $S$ together with a partial ordering $R$ is called partially ordered set, or poset, and is denoted by (S,R).

In a poset the notation $a \preceq b$ denotes that $(a, b) \in R$ . This symbol is used to emphasise the similarity to the familiar “less than or equal to” relation. But be careful: Just because a relation is denoted by a symbol like $\preceq$ does not automatically imply it has exactly the same properties as $\le$ . We write $a \prec b$ to mean $a \preceq b$ , but $a \ne b$ . Also, we say ”$a$ is less than $b$ ” or ”$b$ is greater than $a$ ” if $a \prec b$ .

When $a$ and $b$ are elements of the poset $(S, \preceq)$ , it is not necessary that either $a \preceq b$ or $b \preceq a$ . For instance, in $(\mathcal P( \Z ), \subseteq)$ , $\{1, 2\}$ is not related to $\{1, 3\}$ , and vice versa, since neither set is contained within the other. Similarly, in $(\mathbb{P}, \mid )$ , $2$ is not related to $3$ and $3$ is not related to $2$ , since $2 \nmid 3$ and $3 \nmid 2$ . This leads to the following definition.

The adjective “partial” is used to describe partial orderings since pairs of elements may be incomparable. When every two elements in the set are comparable, the relation is called a total ordering.

Definition 4.2 If $(S, \preceq)$ is a poset and every two elements of $S$ are comparable, $S$ is called a totally ordered or linearly ordered set, and $\preceq$ is called a total order or a linear order. A totally ordered set is also called a chain.

We say that $(S, \preceq)$ is a well-ordered set if it is a poset such that $\preceq$ is a total ordering and such that every nonempty subset of S has a least element. ($a$ is a least element of $(S, \preceq)$ if $a \preceq b$ for all $b \in S$ .)

Example 4.31 The set $\Z$ , with the usual $\le$ ordering, is not well ordered since the set of negative integers, which is a subset of $\Z$ , has no least element.

The letters of the alphabet have a standard ordering $'a'<'b'<\cdots <`z'$ . The “dictionary” or “lexicographic” ordering turns this ordering on letters into an ordering on words. This is a special case of a general principle: given an alphabet set $A$ that is a poset one can impose an ordering on strings over the alphabet $A$ . We now explain this construction.

First, we will show how to construct a partial ordering on the Cartesian product of two posets, $(A_{1}, \preceq_{1})$ and $(A_{2}, \preceq_{2})$ . The lexicographic ordering $\preceq$ on $A_{1} \times A_{2}$ is defined by specifying that one pair is less than a second pair if the first entry of the first pair is less than (in $A_{1}$ ) the first entry of the second pair, or if the first entries are equal, but the second entry of this pair is less than (in $A_{2}$ ) the second entry of the second pair. In other words, $(a_{1}, a_{2})$ is less than $(b_{1}, b_{2})$ , that is

either if $a_{1} \prec_{1} b_{1}$ or if both $a_{1} = b_{1}$ and $a_{2} \prec_{2} b_{2}$ .

We obtain a partial ordering $\preceq$ by adding equality to the ordering $\prec$ on $A \times B$ . The verification of this is left as an exercise.

A lexicographic ordering can be defined on the Cartesian product of $n$ posets $(A_{1}, {\preceq_{1}}), (A_{2}, {\preceq_2}),\ldots, (A_{n}, {\preceq_{n}})$ . Define the partial ordering $\preceq$ on $A_{1} \times A_{2} \times \cdots \times A_{n}$ by

if $a_{1} \prec_{1} b_{1}$ , or if there is an integer $i > 0$ such that $a_{1} = b_{1}, \ldots, a_{i} = b_{i}$ , and $a_{i+1} \prec_{i+1} b_{i+1}$ . In other words, one $n$ -tuple is less than a second $n$ -tuple if the entry of the first $n$ -tuple in the first position where the two $n$ -tuples disagree is less than the entry in that position in the second $n$ -tuple.

Consider the strings $a_{l}a_{2} \cdots a_{m}$ and $b_{1}b_{2} \cdots b_{n}$ on a partially ordered set $S$ . Suppose these strings are not equal in length. Let $t$ be the minimum of $m$ and $n$ . The definition of lexicographic ordering is that the string $a_{1}a_{2} \cdots a_{m}$ is less than $b_{1}b_{2} \cdots b_{n}$ if and only if

where $\prec$ in this inequality represents the lexicographic ordering of $S^{t}$ . In other words, to determine the ordering of two different strings, the longer string is truncated to the length of the shorter string, namely, to $t = \min(m, n)$ terms. Then the $t$ -tuples made up of the first $t$ terms of each string are compared using the lexicographic ordering on $S^{t}$ . One string is less than another string if the $t$ -tuple corresponding to the first string is less than the $t$ -tuple of the second string, or if these two $t$ -tuples are the same, but the second string is longer. The verification that this is a partial ordering is left as an exercise.

We can draw a directed graph of a poset (called a Hasse diagram or lattice diagram) as follows. Each element of the poset is represented by a dot, called a vertex. An arrow, called a directed edge, is drawn from element $a$ to element $b$ if $a\preceq b$ . The diagram (a) below is a digraph of the poset $(\{1, 2, 3, 4\}, \le)$ .

Many edges in the directed graph for a finite poset do not have to be shown since they must be present. For instance, consider the directed graph for the partial ordering $\{(a, b) \mid a \le b\}$ on the set $\{l, 2, 3, 4\},$ shown in diagram (a) below. Since this relation is a partial ordering, it is reflexive, and its directed graph has loops at all vertices.

Consequently, we do not have to show these loops since they must be present; in diagram (b) loops and arrows are not shown.

Because a partial ordering is transitive, we do not have to show those edges that must be present because of transitivity. For example, in diagram (c) the edges $(1, 3), (1, 4)$ , and $(2, 4)$ are not shown since they must be present. If we assume that all edges are pointed “upward” (as they are drawn in the figure), we do not have to show the directions of the edges; diagram (c) does not show directions.

To draw the diagram, execute the following procedure. Start with the directed graph for this relation. Draw it so that arrows are always pointing upwards. Because a partial ordering is reflexive, a loop is present at every vertex. Remove these loops. Remove all edges whose presence is imposed by transitivity. For instance, if $(a, b)$ and $(b, c)$ are in the partial ordering, remove the edge $(a, c)$ , since it must be present also. Furthermore, if $(c, d)$ is also in the partial ordering, remove the edge $(a, d)$ , since is must be present also. Finally, arrange each edge so that its initial vertex is below its terminal vertex (as it is drawn on paper). Remove all the arrows on the directed edges, since the direction on the edges is now indicated by which vertices are “higher” on the page. Note that Hasse diagrams never have horizontal edges!

These steps are well-defined, and only a finite number of steps need to be carried out for a finite poset. When all the steps have been taken, the resulting diagram contains sufficient information to find the partial ordering. This diagram is called a Hasse diagram, named after the 20th century German mathematician Helmut Hasse.

For many applications it is useful to be able to identify certain extremal elements of partially ordered students. For example, a prize might be given to the student in a course with the highest grade.

An element of a poset is called maximal if it is not less than any element of the poset. That is, $a$ is maximal in the poset $(S, \preceq)$ if there is no $b \in S$ such that $a \prec b$ . Similarly, an element of a poset is called minimal if it is not greater than any element of the poset. That is, $a$ is minimal if there is no element $b \in S$ such that $b \prec a$ . Maximal and minimal elements are easy to spot using a Hasse diagram. They are the elements with nothing above them or with nothing below them.

are maximal, and which are minimal?

Sometimes there is an element in a poset that is greater than every other element. Such an element is called the greatest element. That is, $a$ is the greatest element of the poset $(S, \preceq)$ if $b \preceq a$ for all $b \in S$ . The greatest element is unique when it exists. Likewise, an element is called the least element if it is less than all the other elements in the poset. That is, $a$ is the least element of $(S, \preceq)$ if $a \preceq b$ for all $b \in S$ . The least element is unique when it exists.

Solution. The least element is the empty set, since $\emptyset \subseteq T$ for any subset $T<L$ of $S$ . The set $S$ is the greatest element in this poset, since $T \subseteq S$ whenever $T$ is a subset of $S$ .

Solution. The integer 1 is the least element since $1 \mid n$ whenever $n$ is a positive integer. Since there is no integer that is divisible by all positive integers, there is no greatest element.

Let $(S, \preceq)$ be a poset and $A \subseteq S$ a subset of it. Then $(A , \preceq)$ is also a poset. Sometimes it is possible to find an element in $S$ that is greater than all the elements in the subset $A$ . An element $u \in S$ such that $a \preceq u$ for all elements $a \in A$ is called an upper bound of $A$ . Likewise, an element $l \in S$ such that $l \preceq a$ for all elements $a \in A$ is called a lower bound of $A$ .

An element $x$ is called the least upper bound of the subset $A$ if $x$ is an upper bound that is less than every other upper bound of $A$ . Since there is only one such element, if it exists, it makes sense to call this element the least upper bound. That is, $x$ is the least upper bound of $A$ if $a \preceq x$ whenever $a \in A$ , and $x \preceq z$ whenever $z$ is an upper bound of $A$ . Similarly, the element $y$ is called the greatest lower bound of $A$ if $y$ is a lower bound of $A$ and $z \preceq y$ whenever $z$ is a lower bound of $A$ . The greatest lower bound of $A$ is unique if it exists. The greatest lower bound and least upper bound of a subset $A$ are denoted by $glb(A)$ and $lub(A)$ , respectively.

Solution. An integer is a lower bound of $\{3, 9, 12\}$ if 3, 9, and 12 are divisible by this integer. The only such integers are 1 and 3. Since $1 \mid 3$ , 3 is the greatest lower bound of $\{3, 9, 12\}$ . The only lower bound for the set $\{1, 2, 4, 5, 10\}$ with respect to $\mid$ is the element 1. Hence, 1 is the greatest lower bound for $\{1, 2, 4, 5, 10\}$ .

Relational calculus

There are various operations that can be performed on relations to obtain a new relation.

Let $R$ be a binary relation from $A$ to $B$ , so that $R \subseteq A \times B$ . The complement relation is $R' = (A \times B) \setminus R$ . In otherwords, $a~R~b$ if and only if $a~\cancel{R}'~b$ .

The complement of the binary relation $=$ on $\mathbb{R}$ is $\neq$ .

Let $R$ be a binary relation from $A$ to $B$ , so that $R \subseteq A \times B$ . The converse relation is $R' \subseteq B \times A$ defined by

The converse of the binary relation $=$ on $\mathbb{R}$ is $=$ .

If $R$ is a relation from $A$ to $B$ and we have $C \subseteq A$ , $D \subseteq B$ , then we define the relational image of $C$ under $R,$ $R(C)$ , by

and we define the relational preimage of $D$ under $R$ by

In the special case where the relation is a function $f,$ we can rewrite these definitions as

a $R(\{1,2\})$

b $R(\{3\})$

c $R^←(\{2,3\})$

d $R^←(\{4\})$

Find:

a $R(\{12\})$

b $R^←(\{12\})$

Solution. $R(\{12\}) = \{\dots, -36, -24, -12, 0, 12, 24, 36, ~\dots \}$

Let $R_1$ and $R_2$ be two binary relations on $A \times B$ . We define the union

Let $R_1$ and $R_2$ be two binary relations on $A \times B$ . We define the intersection

Functions

Let $A$ and $B$ be sets. Informally, a function $f$ from $A$ to $B$ is a rule that assigns, to each element $x$ of $A$ a unique element $f(x)$ of $B$ , called the image of $x$ under $f$ .

Formally, a function is a special type of relation. A function from $A$ to $B$ is a binary relation $f$ from $A$ to $B$ such that for every $x\in A$ there is exactly one $y\in B$ such that $(x,y)\in f$ . We never use infix notation for functions: instead, we use the notation we are already familiar with, by abbreviating $(x,y)\in f$ as $y=f(x)$ .