2.2. Relations

Relations, and in particular, binary relations, are a very general class of objects. They generalize the notion of functions and can be used to encode a variety of things. Relations may encode transformations, mappings, or functions. They may also be used more generally to encode properties about a set of objects.

2.2.1. Binary Relations

Given two sets \(A\) and \(B\), their Cartesian product \(A \times B\) is the set of all pairs \((a,b)\) with \(a \in A\) and \(b \in B\). A binary relation is a subset of the Cartesian product, where membership in the relation set denotes that \(a\) relates to \(b\).

Definition (binary relation)

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

Notice that by definition, the empty set \(\varnothing\) is a relation. So is the entire Cartesian product \(A \times B\). However, these are both not very interesting. We are typically concerned with non-empty proper subsets of the Cartesian product.

Consider the set \(S\) of students in this class, and set \(M\) majors available in the faculty of science at UWO. Then a binary relation from \(S\) to \(M\) would “connect” or “relate” students in \(S\) and majors in \(M\). A critical piece of understanding relations is that they do not require that every element relates to another. Moreover, they do not require that every element relates to exactly one other. Relations are not necessarily functions.

A first relation

Let \(S\) be the set of students \(\{\text{Andrea}, \text{Bruce}, \text{Davood}, \text{Fiona}, \text{Jalal}, \text{Rahul}\}\).

Let \(M\) be the set of majors \(\{\text{Computer Science}, \text{Mathematics}, \text{Physics}, \text{Chemistry}, \text{Biology}\}\)

A relation \(\mathcal{R}\) from \(S\) to \(M\) is a subset of \(S \times M\). Let \(\mathcal{R}\) be as follows.

\[\begin{split} \begin{align} \mathcal{R} = \{ & \\ &(\text{Davood, Physics}), \\ &(\text{Andrea, Computer Science}),\\ &(\text{Rahul, Chemistry}), \\ &(\text{Bruce, Biology}), \\ &(\text{Fiona, Computer Science}), \\ & (\text{Andrea, Mathematics}), \\ &(\text{Bruce, Chemistry}), \\ &(\text{Rahul, Physics}), \\ &(\text{Rahul, Computer Science}) \\ \} \end{align} \end{split}\]

Membership in \(\mathcal{R}\) can be understood to encode that student \(s \in S\) is majoring in major \(m \in M\). Notice this relation is not “one-to-one” (something we will define formally later in Functions). This relation tells us that Davood is taking Physics, Andrea is taking Computer Science and Mathematics, Bruce is taking Biology and Chemistry, etc.

For some relation \(\mathcal{R}\) we write \(a\mathcal{R}b\) when \((a,b) \in \mathcal{R}\). If \((a,b) \not\in \mathcal{R}\) we may write \(a\not\mathcal{R}b\).

One possible view of binary relation \(\mathcal{R}\) is as a table; just like we did with the Cartesian product. However, in a binary relation, we are only interested in some of the cells of the table. One way of showing this is to leave cells of the table blank if they are not in the relation and somehow mark the cells for which \(a\mathcal{R}b\).

Relations as tables

Let \(A = \{1,2,3\}\) and \(B = \{a,b,c,d,e\}\). A binary relation from \(A\) to \(B\) could be:

\[ \{ (1,a), (1,c), (1,d), (2,a), (2,b), (3,c), (3,e) \}, \]

and its representation as a table:

\(\ \)	\(a\)	\(b\)	\(c\)	\(d\)	\(e\)
\(1\)	X	\(\ \)	X	X	\(\ \)
\(2\)	X	X	\(\ \)	\(\ \)	\(\ \)
\(3\)	\(\ \)	\(\ \)	X	\(\ \)	X

“X marks the spot”

---

Relations as Predicates

Relations are one possible encoding of predicates. In particular, of propositional functions with two or more variables. A pair being a member of a binary relation encodes that binding the variables of a propositional function to that pair results in true.

Recall from Predicate Logic that a predicate represents some property or relation. When the predicate uses a single variable, it represents a property. For example, \(P :=\) “is a dog.”. When the predicates uses two or more variables, it is now relating multiple objects together in some way. For example, \(Q :=\) “is the mother of”.

Let \(U\) be the set of all students as Western University. That is, \(U\) is the domain of discourse. Let \(F(x,y)\) be the propositional function “\(x\) and \(y\) are friends”. Let \(\mathcal{R}\) be a binary relation on \(U\). If:

\[ (x,y) \in \mathcal{R} \leftrightarrow P(x,y), \]

we can say \(\mathcal{R}\) represents \(F(x,y)\).

Mathematically, \(\mathcal{R}\) and \(F(x,y)\) may be considered indistinguishable. In the world of computer science, we could easily encode the relationship given by \(F(x,y)\) as a set of pairs. That is, we could directly encode \(\mathcal{R}\).

S = {"Andrea", "Bruce", "Davood", "Fiona", "Jalal", "Rahul"};
M = {"Computer Science", "Mathematics", "Physics", "Chemistry", "Biology"}
R = {
    ("Davood", "Physics"),
    ("Andrea", "Computer Science"),
    ("Rahul", "Chemistry"),
    ("Bruce", "Biology"),
    ("Fiona", "Computer Science"),
    ("Andrea", "Mathematics"),
    ("Bruce", "Chemistry"),
    ("Rahul", "Physics"),
    ("Rahul", "Computer Science")
}

for s in S :
    for m in M :
        if (s,m) in R: print("{} is majoring in {}".format(s,m));

Fiona is majoring in Computer Science
Rahul is majoring in Chemistry
Rahul is majoring in Physics
Rahul is majoring in Computer Science
Bruce is majoring in Chemistry
Bruce is majoring in Biology
Andrea is majoring in Computer Science
Andrea is majoring in Mathematics
Davood is majoring in Physics

Tip

Notice that ordering of strings when we constructed S and M in the previous code listing does not match the ordering of students printed by the for s in S loop.

Remember, sets do not care about ordering.

---

Constructing relations

We can construct relations just as we have done for sets. Indeed, relations are just sets (of tuples). In the previous section we saw the roster method applied to construct relations. Set builder notation is much more common and practical, since relations usually relate a large number of elements.

Set builder for relations

Consider the set of all fractions (rational numbers) which, when reduced fully, are actually integers. Such a property is actually a relation between the numerator and the denominator. It says that, for a fraction \(\frac{x}{y}\), \(x\) is a multiple of \(y\).

We can encode this relationship as a binary relation \(\mathcal{R}\) on \(\mathbb{Z}\):

\[\begin{split} \begin{align} \mathcal{R} &= \{ (x,y) \ |\ x, y \in \mathbb{Z},\ \frac{x}{y} \in \mathbb{Z}\}, \quad \textit{or} \\[1em] \mathcal{R} &= \{ (x,y) \ |\ x, y \in \mathbb{Z},\ \exists k \in \mathbb{Z}\ x = ky\} \end{align} \end{split}\]

Now, try it yourself.

Checkpoint

Relation builder

Describe the following relations using set builder notation.

1. (“Equal squares”) \(\mathcal{R}\) is a binary relation on \(\mathbb{R}\) where \(a\mathcal{R}b\) when \(a^2 = b^2\)

2. (“Odd neighbours”) \(\mathcal{R}\) is a binary relation on \(\mathbb{Z}\) relating all even integers \(i\) to \(i+1\).

3. (“Classmates”) Let \(U\) be all students at Western University. \(\mathcal{R}\) is a binary relation on \(U\) relating all students who are enrolled in the same class. (Hint: define a “is enrolled in the same class” predicate.)

Solution

Relation builder

1. \(\mathcal{R} = \{(a,b)\ |\ a,b \in \mathbb{R}, a^2 = b^2\}\)

2. \(\mathcal{R} = \{(a,b)\ |\ a,b \in \mathbb{Z}, a \text{ is even}, b = a+1\}\)

3. Let \(P(x,y) :=\) “\(x\) is enrolled in the same class as \(y\)”. \(\mathcal{R} = \{(a,b)\ |\ a,b \in {U}, P(a,b)\}\)

---

2.2.2. Properties of Relations

There are many possible properties that relations may have. In this section we look at some important properties for binary relations on some set \(A\). That is, binary relations \(\mathcal{R} \subseteq A \times A\). We will look at :

• reflexivity

• symmetry

• antisymmetry

• transitivity

Reflexivity

Definition (reflexive)

A binary relation \(\mathcal{R}\) on a set \(A\) is reflexive if and only if, for every \(a \in A\):

\[ (a,a) \in \mathcal{R}. \]

Reflexivity says that every element must relate to itself. Equality is an obvious reflexive relation. For any number \(x\), \(x = x\). Here’s another example.

Reflexive relations

Let \(P\) be the set all people. Let \(\mathcal{R}\) be the binary relation on \(P\) relating all people with the same first name.

It is clear that \(\mathcal{R}\) is reflexive because someone named “Foo Bar” shares their first name with themselves, namely, “Foo”.

Another way of thinking about a reflexive binary relation \(\mathcal{R}\) on \(A\) is that it is a superset of the set:

\[ \{ (a,a) \ |\ a \in A\} \]

That is, for any \(a \in A\), the pair \((a,a)\) is a member of \(\mathcal{R}\). But, often, \(\mathcal{R}\) is much more than that.

Consider a counterexample. The following relation is not reflexive.

\[ \mathcal{S} = \{(x,y) \ |\ x,y \in \mathbb{R}, x^2 + y^2 > 0\} \]

Why not? because \((0,0) \not\in \mathcal{S}\).

Symmetry

Definition (symmetric)

A binary relation \(\mathcal{R}\) on a set \(A\) is symmetric if and only if, for every \(a,b \in A\):

\[ (a,b) \in \mathcal{R} \rightarrow (b,a) \in \mathcal{R}. \]

Note that, unlike reflexive binary relations, symmetric relations do not require that every pair \((x,y)\) is in the relation. Rather, it only requires that if \((x,y)\) is in the relation, then so is \((y,x)\).

We can view symmetric relations as ones where the ordering of elements in a pair does not matter. Recall that in a tuple, order typically does matter; for two tuples \((a,b)\) and \((b,a)\), \((a,b) \neq (b,a)\). However, in a symmetric relation, if \((a,b)\) is in the relation, then so is \((b,a)\).

Symmetric relations

The following are symmetric relations.

\[ \mathcal{R}_1 = \{(x,y) \in \mathbb{R}^2 \ |\ x^2 + y^2 = 5\} \]

\[ \mathcal{R}_2 = \{(a,b) \in \mathbb{Z}^2 \ |\ 2x + 2y = 4\} \]

Let \(U\) be all students at Western and \(P(x,y) :=\) “\(x\) and \(y\) are in the same class.”

\[ \mathcal{R}_3 = \{ (x,y) \ |\ P(x,y)\} \]

When a relation is given by a formula and switching the variables in the formula give the same equation, then it is a symmetric relation.

Antisymmetry

Definition (antisymmetric)

A binary relation \(\mathcal{R}\) on a set \(A\) is antisymmetric if and only if, for every \(a,b \in A\):

\[ (a,b) \in \mathcal{R} \text{ and } (b,a) \in \mathcal{R} \rightarrow a=b. \]

Antisymmetry essentially says that any elements that relate symmetrically are actually equal. This is the probably the most difficulty relation property to understand.

A classic example is the relation induced by \(\leq\).

Antisymmetric relation

Let \(\mathcal{R} = \{(x,y) \in \mathbb{R}^2 \ |\ x \leq y\}\)

Let \(a, b\) be any two real numbers. Notice that if \(a \leq b\), then \((a,b) \in \mathcal{R}\). If it is also the case that \(b \leq a\), then \((b,a) \in \mathcal{R}\). However, notice that \((a \leq b) \land (b \leq a)\) can only occur when \(a = b\). Therefore, \(\mathcal{R}\) is antisymmetric.

Transitivity

Definition (transitive)

A binary relation \(\mathcal{R}\) on a set \(A\) is transitive if and only if, for every \(a,b,c \in A\):

\[ (a,b) \in \mathcal{R} \text{ and } (b,c) \in \mathcal{R} \rightarrow (a,c) \in \mathcal{R}. \]

Transitive relations are one which somehow form a “chain” of relations. Elements are related in a sequence or successive way. A typical example is “ancestry”. Let \(A(x,y) :=\) \(x\) is an ancestor of \(y\). The relation created by this predicate is surely transitive. The parents of your parents are your grandparents; your grandparents are surely your ancestors.

Another typical mathematical example is inequality (\(<\) or \(>\)). For any three numbers \(a,b,c\), \(a < b\) and \(b < c\) implies \(a < c\). This is natural.

We have already inherently used transitivity throughout the previous sections. Most of our proof techniques rely on transitivity. Consider implication (\(\rightarrow\)) or logical equivalence (\(\equiv\)).

Direct proofs and equivalence proofs rely on forming a “chain” or implications or equivalences:

\[ \begin{align}\begin{aligned}\begin{split} P \rightarrow P_1 \rightarrow P_2 \rightarrow P_3 \rightarrow \ldots \rightarrow Q \\[1em]\end{split}\\A \equiv A_1 \equiv A_2 \equiv A_3 \equiv \ldots \equiv B \end{aligned}\end{align} \]

Consider a more abstract example.

Transitive relation

Let \(\mathcal{R} = \{(a,d), (b,c), (b,d), (c,c), (c,d), (a,c)\}\).

This binary relation is transitive. The only pairs that fulfill the hypothesis of transitivity are \((a,c)\) and \((c,d)\). We also have \((a,b) \in \mathcal{R}\). Therefore, \(\mathcal{R}\) is transitive.

Checkpoint

Properties of relations

Is the following relation reflexive, symmetric, antisymmetric, or transitive?

\[ \mathcal{R} = \{(A,B) \in \mathcal{P}(\mathbb{Z}) \times \mathcal{P}(\mathbb{Z}) \ |\ A \subseteq B\} \]

Solution

Properties of relations

Notice that \(A\) and \(B\) are both elements of \(P(\mathbb{Z})\). Therefore, they are each some subset of the integers, of any size… For example, \(\{1,2,3,4,5\}\) and \(\{1,6,23,123,1299,1300\}\).

• For any \(A\) we have \(A \subseteq A\), so \(\mathcal{R}\) is reflexive.

• Consider \(A = \{1\}\) and \(B = \{1,2\}\). \(A \subseteq B\) but \(B \not\subseteq A\). Therefore, \(\mathcal{R}\) is not symmetric.

• We have \(A \subseteq B \land B \subseteq A \rightarrow A = B\), so \(\mathcal{R}\) is antisymmetric.

• For any sets \(A, B, C\) such that \(A \subseteq B\) and \(B \subseteq C\), it also holds that \(A \subseteq C\). Therefore, \(\mathcal{R}\) is transitive.

---

2.2.3. Equivalence Relations

Equivalence relations are special kinds of relations with several simultaneous properties. Equivalence classes are essential is discrete mathematics and computer science. We will see them in action and application in Section 4. Here, we define them and give some basic examples.

Definition (equivalence relation)

A binary relation \(\mathcal{R}\) on a set \(A\) is an equivalence relation if it is reflexive, symmetric, and transitive.

Consider the relation of two people being (biological) siblings. Let \(U\) be the set of all people in the world.

\[ \mathcal{R} = \{(x,y) \in U^2 \ |\ x \text{ and } y \text{ are siblings }\} \]

This relation is reflexive, transitive, and symmetric. Is everyone a sibling of themselves? Yes, if you consider that siblings are people “with the same parents”. Obviously a pair of people are siblings regardless of which order you look at them, and is therefore symmetric. Being siblings is also transitive. If Mary and Beth are siblings, and Beth and Fiona are siblings, then Mary and Fiona are also siblings.

Recall that for a binary relation \(\mathcal{R}\) we write \(a\mathcal{R}b\) when \((a,b) \in \mathcal{R}\). When \(\mathcal{R}\) is an equivalence relation, we can use the stronger notation \(a \sim b\) to denote that \(a\) “is equivalent to” \(b\) under the equivalence relation \(\mathcal{R}\).

As stated, we will study the applications of equivalence relations more in Section 4. Because of their usefulness, it is often the case that we must prove that a binary relation is an equivalence relation.

Such a proof comes in three parts: proving reflexivity, proving symmetry, and proving transitivity. To be explicit, for a binary relation \(\mathcal{R}\) on a set \(A\), we must prove:

1. Reflexive: \(\quad\ \ a \sim a \ \forall a \in A\),

2. Symmetric: \(\quad a \sim b \rightarrow b \sim a\), and

3. Transitive: \(\quad\ \, a \sim b \land b \sim c \rightarrow a \sim c\).

Postal codes, an equivalence relation

Consider the set of all people with a mailing address in Canada. Consider two people in this set to be related if they share a postal code. This relation is clearly an equivalence relation.

1. Reflexive. Every person shares the same postal code as themselves.

2. Symmetric. If two people \(x\) and \(y\) share a postal code, then \(y\) and \(x\) share a postal code.

3. Transitive. If \(a\) and \(b\) share a postal code, and \(b\) and \(c\) share a postal code, then \(a\) and \(c\) share a postal code.

Equivalence relations are a generalization or “weakening” of the usual notation of equality. Surely equality is the most fundamental equivalence relations.

Let \(\mathcal{R} = \{(x,y) \in \mathbb{R}^2 \ |\ x = y\}\). \(\mathcal{R}\) is an equivalence relation.

1. Reflexive: for any real number \(x\), \(x = x\).

2. Symmetric: for any two real numbers, \(x = y \rightarrow y = x\).

3. Transitive: for any three real numbers, \(x = y, y = z \rightarrow x = z\).

An example where equality is “weakened” is as follows. Consider the relation which relates any two circles of the same radius. Sure, two different circles, drawn in different places on the Cartesian plane are not “equal”. But, they are sufficiently similar that if you moved the origin, you may not be able to “tell them apart”.

Fig. 2.16 We can consider the green circles (of radius 1) equivalent. The purple circles (of radius 1.5) are similarly equivalent. Without an origin, the circles of the same radius are indistinguishable.

Checkpoint

Proving equivalence relations

Show that the following binary relation is an equivalence relation.

\[ \mathcal{R} = \{(x,y) \in \mathbb{Z}^+ \times \mathbb{Z}^+\ |\ \lceil\log_{10}(x)\rceil = \lceil\log_{10}(y)\rceil \} \]

Hint: \(\lceil\log_{10}{x}\rceil\) just counts the number of digits in \(x\).

Solution

Proving equivalence relations

1. Reflexivity.

For any \(x\), \(\log_{10}{x} = \log_{10}{x}\), therefore \((x,x) \in \mathcal{R}\) and \(\mathcal{R}\) is reflexive.

2. Symmetry.

For any \(x, y\) such that \(\lceil\log_{10}{x}\rceil = \lceil\log_{10}{y}\rceil\), surely \(\lceil\log_{10}{y}\rceil = \lceil\log_{10}{x}\rceil\). That is, if \(x\) has the same number of digits as \(y\), then \(y\) has the same number of digits as z. Therefore \(\mathcal{R}\) is symmetric.

3. Transitivity.

For any \(x,y,z\), if \(x\) and \(y\) have the same number of digits, and \(y\) and \(z\) have the same number of digits, then \(x\) and \(z\) have the same number of digits. Therefore \(\mathcal{R}\) is transitive. \(\blacksquare\)

---

Equivalence Classes

An important consequence of equivalence relations are equivalence classes. Equivalence classes group together all elements which are equivalent under a certain equivalence relation.

Definition (equivalence class)

Let \(\sim\) denote an equivalence relation on a set \(A\). Then, for an element \(a \in A\), the equivalence class of \(a\) is the set \(\{b \in A \ |\ b \sim a\}\).

Consider the previous equivalence relation where two people are equivalent if they share a postal code. This relation groups people together into sets where each set contains all of the people with the same postal code.

Fig. 2.17 The grouping of buildings with postal code N6A 3K6 includes King Richie’s.

We can represent the equivalence class of people with N6A 3K6 as their postal code using a representative of that group. Because of the symmetry and transitivity of equivalence relations, every element of an equivalence class is equivalent to every other element of that same equivalence class. Therefore, any element can be a representative of the class.

For an equivalence class of \(a \in A\) under some equivalence relation, equivalence classes are denoted in two possible ways, both using any representative of the class.

\[\begin{split} [a] = \{b \in A \ |\ b \sim a\}\\ \overline{a} = \{b \in A \ |\ b \sim a\} \end{split}\]

Consider the N6A 3K6 postal code. The equivalence class \([\text{King Richie}]\) includes \(\text{B & C variety}\). The same equivalence class can also be denoted as \([\text{B & C variety}]\), which includes \(\text{King Richie}\). The choice of representative for an equivalence class is arbitrary and any choice is equally correct.

Equivalence classes on the integers

Let \(\mathcal{R}\) be the equivalence relation \(\{(a,b) \in \mathbb{Z}^2 \ \vert\ \ |a| = |b|\}\). We have the following equivalence classes:

\[\begin{split} [1] = [-1] = \{-1, 1\} \\[1em] [5] = [-5] = \{-5, 5\} \\[1em] [49] = [-49] = \{-49, 49\} \\[1em] \end{split}\]

In general, the equivalence classes under \(\mathcal{R}\) are the sets \(\{-i, i\}\), for all \(i \in \mathbb{Z}^+\), and \([0]\).

Equivalence classes have many useful properties. You may have conjectured one of them from the previous example. Namely, that no element is in two different equivalence classes. Consider that statement as a theorem. Can you prove it?

Theorem

Let \(X\) be a set with an equivalence relation \(\mathcal{R}\) and let \([x]\) and \([y]\) be two equivalence classes under \(\mathcal{R}\). Then, exactly one of the following is true:

\[\begin{split} \begin{align} &[x] = [y], \quad \text{or} \\[1em] &[x] \cap [y] = \varnothing \end{align} \end{split}\]

Partial Proof

We will prove that \([x] \neq [y] \rightarrow [x] \cap [y] = \varnothing\).

Proceed by contrapositive. Assume \(\varnothing \subset [x] \cap [y]\). Let \(a\) be such an element in the non-empty intersection. We will show that \([x] = [y]\).

By definition, we have:

\[\begin{split} [x] = \{a \in X \ |\ x \sim a\} \\[1em] [y] = \{a \in X \ |\ y \sim a\} \\[1em] \end{split}\]

Since \(a \in [x] \cap [y]\), we also have \(a \sim x\) and \(a \sim y\). Let us prove that \([x] = [y]\) by first showing \([x] \subseteq [y]\) and then \([y] \subseteq [x]\).

Let \(b \in [x]\). Therefore, \(b \sim x\). Since \(x \sim a\), \(b \sim a\) by transitivity. Again by transitivity, \(b \sim y\). Therefore, \(b \in [y]\). Now let \(b \in [y]\). Therefore, \(b \sim y\). Since \(y \sim a\), \(b \sim a\) by transitivity. Again by transitivity, \(b \sim x\). Therefore, \(b \in [x]\). Therefore, \([x] = [y]\).

By contrapositive, it must be that \([x] \neq [y] \rightarrow [x] \cap [y] = \varnothing\).

This theorem has an important consequence. It tells us that an equivalence relation on a set \(A\) creates a partition of \(X\).

Definition (partition)

A partition of a set \(A\) is a collection of disjoint subsets of \(A\) such that their union is all of \(A\).

Written in mathematical notation, a partition of the set \(A\) into a collection of sets \(A_1, \ldots, A_n\) is:

\[\begin{split} \begin{align} &\forall\ i,\ 1 \leq i \leq n,\ A_i \subset A \\[1em] &\forall\ i,j,\ 1 \leq i,j \leq n,\ i \neq j,\ A_i \cap A_j = \varnothing \\[1em] &\bigcup_{i=1}^n A_i = A \\[1em] \end{align} \end{split}\]

Example partitions

• The countries of the world are partitioned into continents.

• A deck of cards is partitioned into four suits: hearts, diamonds, clubs, spades.

• The integers are partitioned into odd integers and even integers (yes, \(0\) is even).

• The integers can also be partitioned into three groups: positive, negative, and \(0\).

• The integers can also be partitioned into groups of pairs: \(\{-i, i\}\) for any non-zero integer \(i\), and a lone group \(\{0\}\).

These last two examples show an important characteristic of partitions. Given some set \(A\), it can be partitioned in many different ways. The partitioning of a set is not unique.

Equivalence classes are one way to define a partition. (Although, not all partitions can be described by an equivalence relation.) Equivalence classes being disjoint is one step toward forming a partition. The other step is to show that every element of the set belongs to an equivalence class.

This final step is easy. Equivalence relations are reflexive! For any \(x \in X\), \(x \in [x]\). Therefore every element belongs to an equivalence class. Pair this with the previous theorem showing that equivalence classes are either equal or disjoint is enough to show that equivalence classes partition a set.

Theorem

For an equivalence relation \(\mathcal{R}\) on a set \(A\), its set of equivalences classes form a partition of \(A\).

What are the equivalence classes of the relation \(\mathcal{R} = \{ (x,y) \in \mathbb{Z}^2 \ |\ \)x % 10 = y % 10\(\}\)? Let’s construct a program to get some intuition.

d = {}
for i in range(0,100) :
    if i % 10 in d:
        d[i % 10].append(i)
    else :
        d[i % 10] = [i]

for (k,v) in d.items() :
    print(k, v);

0 [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
1 [1, 11, 21, 31, 41, 51, 61, 71, 81, 91]
2 [2, 12, 22, 32, 42, 52, 62, 72, 82, 92]
3 [3, 13, 23, 33, 43, 53, 63, 73, 83, 93]
4 [4, 14, 24, 34, 44, 54, 64, 74, 84, 94]
5 [5, 15, 25, 35, 45, 55, 65, 75, 85, 95]
6 [6, 16, 26, 36, 46, 56, 66, 76, 86, 96]
7 [7, 17, 27, 37, 47, 57, 67, 77, 87, 97]
8 [8, 18, 28, 38, 48, 58, 68, 78, 88, 98]
9 [9, 19, 29, 39, 49, 59, 69, 79, 89, 99]

The equivalences classes under \(\mathcal{R}\) are \([0], [1], [2], [3], [4], [5], [6], [7], [8], [9]\).

---

2.2.4. Posets: Partially Ordered Sets

In the last section we saw that equivalence relations could be viewed as a weakened form of equality. The same can be said for inequality or ordering.

“Less than or equal to” (\(\leq\)) is the typical order relation. Its properties are reflexivity, antisymmetry, and transitivity. Let’s prove that.

Properties of \(\leq\)

The ordering defined on the real numbers by \(\leq\) is reflexive, antisymmetric, and transitive.

Reflexive: for any number \(x \in \mathbb{R}\), \(x \leq x\). Therefore, it is reflexive.

Antisymmetric: for any two numbers \(x,y \in \mathbb{R}\), if \(x \leq y\) and \(y \leq x\), then surely \(x=y\). Therefore it is antisymmetric.

Transitive: for any three numbers \(x,y,z \in \mathbb{R}\), if \(x \leq y\) and \(y \leq z\), then \(x \leq y \leq z\) and \(x \leq z\). Therefore, it is transitive.

More generally, a binary relation defines a partial order if it is reflexive, antisymmetric, and transitive.

Definition (partial order)

A binary relation \(\mathcal{R}\) on a set \(A\) is a partial order if it is reflexive, antisymmetric, and transitive.

Recall that we can denote an equivalence relation with \(\sim\). In particular, we used the notation \(a \sim b\) to denote \(a\mathcal{R}b\) for an equivalence relation \(\mathcal{R}\). We denote partial orders with \(\preceq\), and use \(a \preceq b\) to denote that the pair \((a,b)\) belongs to the partial order. In this case, we can also say that “\(a\) is less than \(b\)”.

Tip

Just as how \(a < b\) denotes \(a \leq b \land a \neq b\), we can use \(a \prec b\) to denote \(a \preceq b \land a \neq b\) for a partial order \(\preceq\). Moreover, we can use \(a \succeq b\) to denote \(b \preceq a\).

Let’s see our first example of a partial order.

Partial order on a power set

For a set \(A\), the binary relation defined by \(\subseteq\) on the power set \(\mathcal{P}(A)\) is a partial order.

Reflexive: For any set \(X \in \mathcal{P}(A)\), \(X \subseteq X\).

Antisymmetric: For any two sets \(X,Y \in \mathcal{P}(A)\), if \(X \subseteq Y\) and \(Y \subseteq X\), then \(X=Y\). Indeed, this is one definition of set equality.

Transitive: For any three sets \(X,Y,Z \in \mathcal{P}(A)\), if \(X \subseteq Y\) and \(Y \subseteq Z\), then \(X \subseteq Y \subseteq Z\) and \(X \subseteq Z\).

Now, for the titular object, a partially ordered set is a set combined with a partial order on that set.

Definition (partially ordered set)

A partially ordered set or poset is a set \(A\) along with a partial order on that set; a poset is a tuple \((A,\preceq)\).

Checkpoint

Our first poset

Consider the set \(W\), the set of all words in the English language, along with a partial order \(\preceq\) on \(W\) defined as \(a \preceq b\) if \(a\) comes before \(b\) in alphabetical order. Therefore, \((W,\preceq)\) is a poset.

How can we formally define \(\preceq\)? A good starting point is to consider that words in \(W\) are of the form \(w = c_1c_2\cdots c_n\), where each \(c_i\) is one letter a through z.

Solution

Out first poset

Let \(a = a_1a_2\cdots a_n, b = b_1b_2\cdots d_m\) be two elements of \(W\).

\(a \preceq b\) if:

1. \(a = b\); or

2. \(a_k < b_k\) for some \(k \leq m\) and \(k \leq n\), and \(a_i = b_i\) for all \(1 \leq i < k\); or

3. \(n < m\) and \(a_i = b_i\) for all \(1 \leq i \leq n\).

Where \(a_k < b_k\) means \(a_k\) is a letter the comes before \(b_k\) in the alphabet.

Therefore, \(\text{farm} \preceq \text{fun} \preceq \text{fungi}\).

---

Total order

The existence of a partial order suggests the existence of a total order. Notice that a partial order only requires that the relation is reflexive, antisymmetric, and transitive. A total order adds an additional property that for any two elements \(a,b\) in the set, \(a \preceq b\) or \(b \preceq a\).

Definition (total order)

A total order is a partial order \(\preceq\) on a set \(A\) where, for any two elements \(a,b \in A\), \(a \preceq b\) or \(b \preceq a\).

Definition (totally ordered set)

A totally ordered set is a set \(A\) along with a total order \(\preceq\) on that set; a totally ordered set is a tuple \((A,\preceq)\).

Most “natural” partial orders are actually total orders. Indeed, the ordering of \(\leq\) on the real numbers is a total order. For any two real numbers \(r_1, r_2\), either \(r_1 \leq r_2\) or \(r_2 \leq r_1\). The same goes for integers, rational numbers, and natural numbers.

The alphabetical ordering of the previous checkpoint is also a total order. Indeed, we can always compare any two words alphabetically.

More generally, we call this alphabetical ordering the lexicographical ordering in computer science. It generalizes alphabetical ordering to any set of strings that could contain letters, digits, or special characters. This is the ordering of strings in Python and most (if not all) programming languages.

w1 = "foobar"
w2 = "foobar!"
w3 = "123foobar"
w4 = "foobar123"
w5 = "FooBar"

print("{} < {}: {}".format(w1, w2, w1 < w2));
print("{} < {}: {}".format(w1, w3, w1 < w3));
print("{} < {}: {}".format(w1, w4, w1 < w4));
print("{} < {}: {}".format(w3, w4, w3 < w4));
print("{} < {}: {}".format(w1, w5, w1 < w5));

foobar < foobar!: True
foobar < 123foobar: False
foobar < foobar123: True
123foobar < foobar123: True
foobar < FooBar: False

So what is a partial order that is not a total order? We have already seen one: \(\subseteq\).

Let \(A = \{1,2,3\}\). The pair \((\mathcal{P}(A), \subseteq)\) is a partially ordered set that is not a totally ordered set. Why? Not every set in \(\mathcal{P}(A)\) is the subset or superset of another!

\[\begin{split} \begin{gather} \mathcal{P}(A) = \{ \varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{b,c\}, \{a,c\}, \{a,b,c\} \} \\[1em] \{a\} \subseteq \{a,b\}, \quad \{a\} \subseteq \{a,b,c\}, \quad \text{etc., but} \\[1em] \{a,b\} \not\subseteq \{b,c\} \quad \text{and}\quad \{b,c\} \not\subseteq \{a,b\} \end{gather} \end{split}\]

In the poset \((\mathcal{P}(A), \subseteq)\), there are many incomparable elements. If even one pair of elements in a set are incomparable, then it is not a total order.

Definition (comparable)

In a partially ordered set \((A, \preceq)\), two elements \(x, y\) are comparable if \(x \preceq y\) or \(y \preceq x\). If both \(x \not\preceq y\) and \(y \not\preceq x\), then \(x\) and \(y\) are said to be incomparable.

Some elements of a poset or totally ordered can be thought of as more special than the order elements. These elements have special names: minimum and maximum.

Definition (maximum and minimum)

An element \(m\) of a set \(A\) with a partial order \(\preceq\) is minimum if \(m \preceq a\) for all \(a \in A\) or maximum if \(a \preceq m\) for all \(a \in A\).

For example, the natural numbers under the usual ordering have \(0\) as their minimum. In the poset \((\mathcal{P}(A), \subseteq)\) for some set \(A\), \(\varnothing\) is the minimum. In the poset \((\mathcal{P}(A), \subseteq)\) for some set \(A\), \(A\) itself is the maximum.

Generally, a poset need not have a maximum or minimum. Indeed, since not all elements in a poset need to be comparable, there may not be a maximum or minimum.

A poset without a maximum

Let \(A = \{\{1,2\}, \{2,3\}, \{1\}, \{3\}\}\) along with \(\subseteq\) be a poset.

This poset does not have a maximum element:

\[ \{1\} \not\supseteq \{3\}, \quad \{3\} \not\supseteq \{1,2\}, \quad \{1,2\} \not\supseteq \{2,3\}, \quad \{2,3\} \not\supseteq \{1,2\} \]

This poset also does not have a minimum element:

\[ \{1\} \not\subseteq \{3\}, \quad \{3\} \not\subseteq \{1,2\}, \quad \{1,2\} \not\subseteq \{2,3\}, \quad \{2,3\} \not\subseteq \{1,2\} \]

An important characteristic of the maximum and minimum of a poset, if one exists, is that they are unique.

Proposition

The maximum of a poset \((A, \preceq)\), if there is one, is unique.

Proof: Let the maximum element of the poset be \(m\). Assume another maximum element exists \(x\). By definition, \(a \preceq m\) for all \(a \in A\). Similarly, \(a \preceq x\) for all \(a \in A\). Therefore, \(x \preceq m\) and \(m \preceq x\). By antisymmetry of a partial order, we have \(m = x\). Therefore \(m\) is unique. \(\blacksquare\)

A similar proof can be made to show that a minimum is unique, if it exists.

But what do we do in the cases where a minimum or a maximum does not exist? It is important, then, to differentiate between maximum and maximal, and minimum and minimal.

Definition (maximal and minimal)

An element \(m\) of a set \(A\) with a partial order \(\preceq\) is minimal if for any \(a \in A\) such that \(a \preceq m\), then \(m = a\). An element \(m\) is maximal if for any \(a \in A\) such that \(m \preceq a\), then \(m = a\).

The maximum element is one that is larger than any other element. The minimum element is one that is smaller than any other element. However, unlike maximum and minimum, we do not require that maximal and minimal elements are comparable to every other element. Therefore, we can understand them as follows. A maximal element is one which is “not less than” any other element. A minimal element is one which is “not greater than” any other element.

Let’s return to the example of a poset without a maximum.

A poset with multiple maximal element

Let \(A = \{\{1,2\}, \{2,3\}, \{1\}, \{3\}\}\) along with \(\subseteq\) be a poset.

In this set, \(\{1\}\) is minimal and \(\{3\}\) is minimal; \(\{1,2\}\) is maximal and \(\{2,3\}\) is maximal.

Why? Because the only comparable elements are:

\[\begin{split} \begin{align} & \{1\} \subseteq \{1,2\}, \text{ and} \\[1em] & \{3\} \subseteq \{2,3\} \end{align} \end{split}\]

Therefore, \(\{1\}\) is not greater than any other element (similarly \(\{3\}\)), and \(\{1,2\}\) is not less than any other element (similarly \(\{2,3\}\)).

---

Hasse Diagram

A very useful way to describe and visualize a poset is through something called a Hasse diagram. But before we see a Hasse diagram, we need one more definition.

Definition (cover)

Let \(a,b\) be elements of a set \(A\) and \((A, \preceq)\) be a poset. The element \(b\) covers \(a\) if \(a \preceq b\) and there does not exist another element \(c \in A\) such that both \(a \preceq c\) and \(c \preceq b\).

Consider the set of integers under the normal ordering. \(2\) covers \(1\) since there is no element between \(1\) and \(2\). However, \(3\) does not cover \(1\) because \(1 \leq 2 \leq 3\).

Now we can describe the Hasse diagram of a poset. For a poset \((A, \preceq)\):

1. Each element \(a \in A\) is represented as a “dot”, “circle”, or “vertex”.

2. The vertex representing \(a\) is drawn above any other element \(b \in A\) such that \(a \preceq b\).

3. A line segment is drawn between the vertex representing \(a\) and the vertex representing \(b\) if \(b\) covers \(a\).

A very simple Hasse diagram can be made the for the subset of natural numbers \(\{0,1,2,3\}\) with the usual ordering \(\leq\).

Fig. 2.18 A Hasse diagram for \((\{0,1,2,3\}, \leq)\)

A more complex Hasse diagram can be made for the power set of \(A =\{a,b,c\}\) with the partial ordering defined by \(\subseteq\).

Fig. 2.19 A Hasse diagram for \((\mathcal{P}(\{a,b,c\}), \subseteq)\)

Notice that a Hasse diagram immediately shows us which elements in a poset are comparable, which elements are maximal, and which elements are minimal.

In Fig. 2.19, we can see that \(\varnothing\) is a minimal element because it has no elements below it. \(A\) is a maximal element because it has no element above it. The figure also shows how \(\{b\}\) and \(\{a,c\}\) are incomparable since there is no line connecting them.

Checkpoint

Positions in Hasse diagrams

In a Hasse diagram, consider two vertices \(x\) and \(y\) such that \(y\) is placed above \(x\), but there is no line segment between \(x\) and \(y\). Does \(x \preceq y\) hold?

Solution

Positions in Hasse diagrams

Maybe. \(x \preceq y\) holds if there is some “upward” sequence of line segments connecting \(x\) to \(y\) through other vertices. For example, if \(a_1\) covers \(x\), and \(a_2\) covers \(a_1\), and \(y\) covers \(a_2\). On the other hand, without such a sequence, \(x\) and \(y\) are incomparable.

Consider Fig. 2.19. \(\{a,b\}\) is above \(\{c\}\) but \(\{c\} \not\subseteq \{a,b\}\). On the other hand, \(A\) is above \(\{c\}\) without a line directly connecting them, but \(\{c\} \subseteq \{a,b,c\}\). This latter relation holds through transitivity and the covers \(\{c\} \subseteq \{a,c\}\) and \(\{a,c\} \subseteq \{a,b,c\}\).

2.2.5. Exercises

Exercise 2.14

Consider the sets \(B\) of all Canadian bands (i.e. musical artists) and \(S\) of all students at Western. How can we interpret the Cartesian product \(S \times B\)? What is a possible binary relation that we could construct from \(S\) to \(B\)?

Solution to Exercise 2.14

\(S \times B\) is all possible pairs \((s,b)\) of a student \(s\) at Western and a Canadian artist \(b\). Possible relations from \(S\) to \(B\) could be:

• “student \(s\) enjoys the music of band \(b\)”,

• “student \(s\) has seen band \(b\) live in concert”,

• “student \(s\) dislikes band \(b\)”,

• “student \(s\) is a member of band \(b\)” (probably a relation with very few elements).

Exercise 2.15

Consider the set \(S\) of different sports. Consider the set \(P\) of people in London, Ontario.

What is a possible binary relation from \(S\) to \(P\)? What is a possible binary relation from \(P\) to \(S\)? Can you think of a binary relation between these sets such that the ordering of coordinates is important? That is, \(\mathcal{R} \subseteq S \times P\) has a different meaning if we constructed it as \(\mathcal{R} \subset P \times S\)?

Solution to Exercise 2.15

\(S\) to \(P\): relate \(s \in S\) to \(p \in P\) when \(s\) is a sport that \(p\) likes to participate in. \(P\) to \(S\) relate \(p \in P\) to \(s \in S\) when \(p\) is a on a team for sport \(s\).

No such relation is immediately obvious. Generally speaking, binary relations from one set to a different set are symmetric. For example “\(p\) participates in sport \(s\)” and “sport \(s\) has \(p\) as a participant” are the same; \((p,s)\) and \((s,p)\) can be interpretted as the same thing.

Exercise 2.16

Let \(A = \{0,2,5,6,7\}\) and let \(B = \{1,2,3,4,6\}\).

List the pairs contained in the following relations.

1. \(\mathcal{R}_1 = \{(a,b) \in A \times B \ |\ a = b\}\)

2. \(\mathcal{R}_2 = \{(a,b) \in A \times B \ |\ a < b\}\)

3. \(\mathcal{R}_3 = \{(a,b) \in A \times B \ |\ a \geq b\}\)

4. \(\mathcal{R}_4 = \{(a,b) \in A \times B \ |\ a - b = 2\}\)

Solution to Exercise 2.16

\[\begin{split} \begin{align} \mathcal{R}_1 &= \{ (2,2), (6,6) \}\\ \mathcal{R}_2 &= \{ (0,1),(0,2),(0,3),(0,4),(0,6), (2,3),(2,4),(2,6), (5,6)\} \\ \mathcal{R}_3 &= \{ (7,1),(7,2),(7,3),(7,4),(7,6), (6,1),(6,2),(6,3),(6,4),(6,6), (5,1),(5,2),(5,3),(5,4), (2,2), (2,1) \}\\ \mathcal{R}_4 &= \{ (5,3), (6,4) \} \end{align} \end{split}\]

Exercise 2.17

Let \(A = \{x \in \mathbb{Z}^- | x > -5\}\) and let \(B = \{x \in \mathbb{N} | x < 8\}\).

List the pairs contained in the following relations.

1. \(\mathcal{R}_1 = \{(a,b) \in A \times B \ |\ |a| = |b|\}\)

2. \(\mathcal{R}_2 = \{(a,b) \in A \times B \ |\ -a > b\}\)

3. \(\mathcal{R}_3 = \{(a,b) \in A \times B \ |\ 3a + 2b = 0\}\)

4. \(\mathcal{R}_4 = \{(a,b) \in A \times B \ |\ b < a\}\)

Solution to Exercise 2.17

\[\begin{split} \begin{align} \mathcal{R}_1 &= \{ (-1, 1), (-2, 2), (-3, 3), (-4, 4) \}\\ \mathcal{R}_2 &= \{ (-4, 0), (-4, 1), (-4, 2), (-4, 3), (-3, 0), (-3, 1), (-3, 2), (-2, 0), (-2, 1), (-1, 0)\} \\ \mathcal{R}_3 &= \{ (-2,3), (-4, 6) \}\\ \mathcal{R}_4 &= \varnothing \end{align} \end{split}\]

Exercise 2.18

Let \(A = \{0,2,5,6,7\}\) and let \(B = \{1,2,3,4,6\}\).

Draw a table representing the relation:

\[ \mathcal{R}_2 = \{(a,b) \in A \times B \ |\ a < b\} \]

Solution to Exercise 2.18

\(\ \)	\(1\)	\(2\)	\(3\)	\(4\)	\(6\)
\(0\)	X	X	X	X	X
\(2\)	\(\ \)	\(\ \)	X	X	X
\(5\)	\(\ \)	\(\ \)	\(\ \)	\(\ \)	X
\(6\)	\(\ \)	\(\ \)	\(\ \)	\(\ \)	\(\ \)
\(7\)	\(\ \)	\(\ \)	\(\ \)	\(\ \)	\(\ \)

Exercise 2.19

Consider binary relations on the set \(A = \{a,b,c,d\}\). Are the following relations reflexive? Symmetric? Antisymmetric? Transitive?

1. \(\mathcal{R}_1 = \{(b,b),(b,c), (b,d), (c,b), (c,c), (c,d)\}\)

2. \(\mathcal{R}_2 = \{(a,a),(a,b), (b,a), (b,b), (c,c), (d,d)\}\)

3. \(\mathcal{R}_3 = \{(d,b),(b,d)\}\)

4. \(\mathcal{R}_4 = \{(a,b),(b,c), (c,d)\}\)

5. \(\mathcal{R}_5 = \{(a,a),(b,b), (c,c), (d,d)\}\)

6. \(\mathcal{R}_6 = \{(a,c),(a,d), (b,c), (b,d), (c,a), (c,d)\}\)

Solution to Exercise 2.19

1. Transitive.

2. Reflexive, symmetric, and transitive.

3. Symmetric.

4. Antisymmetric (vacuously so).

5. Reflexive, symmetric, transitive, and antisymmetric.

6. Nothing.

Exercise 2.20

Consider binary relations on the set \(A = \{1,2,3,4,5\}\). Are the following relations reflexive? Symmetric? Antisymmetric? Transitive?

1. \(\mathcal{R}_1 = \{(1,2),(3,4), (4,5), (3,5), (2,2), (3,3), (4,4)\}\)

2. \(\mathcal{R}_2 = \{(1,2),(2,3), (4,5), (5,1)\}\)

3. \(\mathcal{R}_3 = \{(3,1), (1,3), (4,5)\}\)

4. \(\mathcal{R}_4 = \{(1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1)\}\)

5. \(\mathcal{R}_5 = \{(1,1), (5,1), (2,3), (3,2), (3,3), (4,4), (1,5)\}\)

Solution to Exercise 2.20

1. Transitive and Antisymmetric.

2. Antisymmetric (vacously so)

3. Nothing.

4. Symmetric.

5. Symmetric.

Exercise 2.21

A binary relation \(\mathcal{R}\) on a set \(A\) is irreflexive if and only if, for every \(a \in A\), \((a,a) \not\in \mathcal{R}\).

1. Which relations in Exercise 2.19 are irreflexive?

2. Can a binary relation be neither reflexive nor irrefelexive?

Solution to Exercise 2.21

1. \(\mathcal{R}_3, \mathcal{R}_4, \mathcal{R}_6\).

2. Yes. Consider \(\mathcal{R} = \{(a,a), (b,b)\}\) on the set \(\{a,b,c\}\). It is not reflexive because \((c,c) \not\in \mathcal{R}\). It is not irreflexive because \((a,a) \in \mathcal{R}\).

Exercise 2.22

Let \(\mathcal{R} = \varnothing\) be a binary relation on some non-empty set \(A\). Prove that \(\mathcal{R}\) is both symmetric and transitive. Further, prove that \(\mathcal{R}\) is not reflexive.

Solution to Exercise 2.22

Symmetry says: \(\forall\ a,b \in A (a,b) \in \mathcal{R} \rightarrow (b,a) \in \mathcal{R}\). Since \(\mathcal{R} = \varnothing\), this implication is vacuously true.

Transitivity says: \(\forall\ a,b,c\in A (a,b) \in \mathcal{R} \land (b,c) \in \mathcal{R} \rightarrow (a,c) \in \mathcal{R}\). Since \(\mathcal{R} = \varnothing\), this implication is vacuously true.

Reflexivity says: \(\forall\ a \in A (a,a) \in \mathcal{R}\). Since \(A\) is non-empty, and \(\mathcal{R}\) is empty, surely \(\mathcal{R}\) does not contain \((a,a)\) for even a single \(a\), so it cannot contain all such \((a,a)\).

Exercise 2.23

Show that the following relations are antisymmetric.

1. \(\mathcal{R}_1 = \{(x,y) \in \mathbb{Z}^2 \ |\ x = y^2\}\)

2. \(\mathcal{R}_2 = \{(x,y) \in \mathbb{Z}^2 \ |\ x \geq y^2\}\)

Solution to Exercise 2.23

By definition, we have antisymmetry as \(\forall x,y (x,y) \in \mathcal{R} \land (y,x) \in \mathcal{R} \rightarrow x = y\)

1. Consider pairs which would be in \(\mathcal{R}_1\). This includes \((4,2), (16,4), (9,-3)\). Are there any pairs \((x,y)\), such that \((y,x)\) is also in \(\mathcal{R}_1\)? There are only two pairs of numbers which are equal to each other’s squares (i.e. \(x = y^2\) and \(y = x^2\)): \((0,0)\) and \((1,1)\). Since \(0 =0\) and \(1 = 1\), \(\mathcal{R}_1\) is antisymmetric.

2. The relation \(\mathcal{R}_2\) adds to \(\mathcal{R}_1\) many many pairs of the form \((i^2, i), (i^2 + 1, i), (i^2 + 2, i), \ldots\). However, to have \(x \geq y^2\) and \(y \geq x^2\), we need \(x \geq y^2 \geq x^4\) (notice that we square the second inequality and then join them together). However, \(x \geq x^4\) only when \(x = 0\) or \(x = 1\). We can see that \((0,0) \in \mathcal{R}_2\) and \((1,1) \in \mathcal{R}_2\). This means \(\mathcal{R}_2\) is antisymmetric.

Exercise 2.24

Let the \(\mathcal{R}\) be an equivalence relation on \(\mathbb{R}^2\) so that \((a,b) \sim (c,d)\) if and only if \(a-b = c-d\).

What is wrong with the following statement?

“Since \(\mathcal{R}\) is an equivalence relation, it is symmetric and \((a,b) \in \mathcal{R}\) implies \((b,a) \in \mathcal{R}\).”

Solution to Exercise 2.24

Recall that \((a,b) \sim (c,d)\) implies that \(((a,b), (c,d)) \in \mathcal{R}\). That is, elements of \(\mathcal{R}\) are pairs of pairs. While it is true that symmetry means \((x,y) \in \mathcal{R} \rightarrow (y,x) \in \mathcal{R}\), we have already defined \(a\) and \(b\) to be elements of \(\mathbb{R}\), not each elements of \(\mathbb{R}^2\). The latter is needed because \(\mathcal{R}\) is a binary relation on \(\mathbb{R}^2\), and elements of \(\mathcal{R}\) belong to \(\mathbb{R}^4 = \mathbb{R}^2 \times \mathbb{R}^2\).

Exercise 2.25

Consider a binary relation \(\mathcal{R}\) defined on \(\mathbb{Z} \setminus \{0\}\) where \(a \sim b\) when \(ab > 0\).

1. Show that this relation is an equivalence relation.

2. What are the equivalence classes under this relation?

Solution to Exercise 2.25

1. Reflexive: For any non-zero integer \(a\), \(a^2 > 0\).

2. Symmetric: For any two non-zero integers \(a\) and \(b\), \(ab = ba\). Thus, if \(ab > 0\), \(ba > 0\).

3. Transitive: Let \(ab > 0\) and \(bc > 0\). We show that \(ac > 0\). Since \(ab > 0\) \(a\) and \(b\) must have the same sign. Since \(bc > 0\), \(b\) and \(c\) must have same sign. Therefore, \(a\) and \(c\) must have the same sign and thus \(ac > 0\).

The equivalences classes are \([-1]\) and \([1]\).

Exercise 2.26

Consider a binary relation \(\mathcal{R}\) defined on the set of all possible propositional formulas where, for two propositional formulas \(p\) and \(q\), we have \((p, q) \in \mathcal{R}\) when \(p \equiv q\).

1. Show that this relation is an equivalence relations.

2. What are the equivalence classes of \(\mathbf{T}\) and \(\mathbf{F}\) (i.e. the truth values true and false).

Solution to Exercise 2.26

1. Reflexive: For any propositional formula \(p\), \(p \equiv p\), therefore \((p,p) \in \mathcal{R}\); Symmetric: For any two propositional formulas \(p \equiv q \leftrightarrow q \equiv p\), therefore \(\mathcal{R}\) is symmetric. Transitive: For any three propositional formulas such that \(p \equiv q\) and \(q \equiv r\) we have \(p \equiv r\). Therefore, \((p,q), (q,r) \in \mathcal{R} \rightarrow (p,r) \in \mathcal{R}\).

2. \([\mathbf{T}]\) is the set of tautologies, \([\mathbf{F}]\) is the set of contradictions.

Exercise 2.27

Consider the following relations. Do they define partial orders? Total orders? If so, prove so. If not, give a counter-example showing that one of the properties does not hold.

1. \(\mathcal{R}_1\): For \(a,b \in \mathbb{R}\), \(a \preceq b\) if and only if \(a \geq b\).

2. \(\mathcal{R}_2\): For \(a,b \in \mathbb{R}\), \(a \preceq b\) if and only if \(a < b\).

3. \(\mathcal{R}_3\): For two sets \(A\) and \(B\), \(A \preceq B\) if \(A \setminus B = \varnothing\).

Solution to Exercise 2.27

1. This is a total order. Reflexive: for all real numbers \(a \geq a\). Transitive: for all real numbers \(a \geq b\), \(b \geq c\) \(\rightarrow a \geq c\). Antisymmetric: \(a \geq b \land b \geq a \rightarrow a=b\). It is a total order because every real number is comparable to another real number.

2. This is not a partial order. It is not reflexive: \(2 \nless 2\).

3. Indeed this property is the same as saying \(A \subseteq B\). Therefore it is a partial ordering.

Exercise 2.28

Consider the below Hasse diagrams. For each, list all pairs in the partial order. If there are any maximal or minimal elements, what are they? If there is a maximum or a minimum element, what is it?

1. 

2. 

Solution to Exercise 2.28

1. \(a \preceq c\), \(c \preceq f\), \(a \preceq f\), \(a \preceq e\), \(b \preceq d\), \(d \preceq e\), \(b \preceq e\), \(b \preceq g\). \(a\), \(b\) are minimal. \(f, e, g\) are maximal. There is not a maximum or minimum.

2. \(a \preceq e\), \(e \preceq h\), \(a \preceq h\), \(e \preceq i\), \(a \preceq i\), \(a \preceq g\), \(b \preceq d\), \(d \preceq g\), \(b \preceq g\), \(b \preceq f\), \(f \preceq g\), \(c \preceq e\), \(c \preceq h\), \(c \preceq i\), \(c \preceq g\) \(a,b,c\) are minimal. \(g,h,i\) are maximal. There is no maximum or minimum.