Relations
Contents
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
Definition (binary relation)
Let
Notice that by definition, the empty set
Consider the set
A first relation
Let
Let
A relation
Membership in
For some relation
One possible view of binary relation
Relations as tables
Let
and its representation as a table:
X |
X |
X |
|||
X |
X |
||||
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,
Let
we can say
Mathematically,
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
We can encode this relationship as a binary relation
Now, try it yourself.
Relation builder
Describe the following relations using set builder notation.
(“Equal squares”)
is a binary relation on where when(“Odd neighbours”)
is a binary relation on relating all even integers to .(“Classmates”) Let
be all students at Western University. is a binary relation on relating all students who are enrolled in the same class. (Hint: define a “is enrolled in the same class” predicate.)
Relation builder
Let
“ is enrolled in the same class as ”.
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
reflexivity
symmetry
antisymmetry
transitivity
Reflexivity#
Definition (reflexive)
A binary relation
Reflexivity says that every element must relate to itself. Equality is an obvious reflexive relation. For any number
Reflexive relations
Let
It is clear that
Another way of thinking about a reflexive binary relation
That is, for any
Consider a counterexample. The following relation is not reflexive.
Why not? because
Symmetry#
Definition (symmetric)
A binary relation
Note that, unlike reflexive binary relations, symmetric relations do not require that every pair
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
Symmetric relations
The following are symmetric relations.
Let
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
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
Antisymmetric relation
Let
Let
Transitivity#
Definition (transitive)
A binary relation
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
Another typical mathematical example is inequality (
We have already inherently used transitivity throughout the previous sections. Most of our proof techniques rely on transitivity. Consider implication (
Direct proofs and equivalence proofs rely on forming a “chain” or implications or equivalences:
Consider a more abstract example.
Transitive relation
Let
This binary relation is transitive. The only pairs that fulfill the hypothesis of transitivity are
Properties of relations
Is the following relation reflexive, symmetric, antisymmetric, or transitive?
Properties of relations
Notice that
For any
we have , so is reflexive.Consider
and . but . Therefore, is not symmetric.We have
, so is antisymmetric.For any sets
such that and , it also holds that . Therefore, 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
Consider the relation of two people being (biological) siblings. Let
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
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
Reflexive:
,Symmetric:
, andTransitive:
.
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.
Reflexive. Every person shares the same postal code as themselves.
Symmetric. If two people
and share a postal code, then and share a postal code.Transitive. If
and share a postal code, and and share a postal code, then and 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
Reflexive: for any real number
, .Symmetric: for any two real numbers,
.Transitive: for any three real numbers,
.
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.#
Proving equivalence relations
Show that the following binary relation is an equivalence relation.
Hint:
Proving equivalence relations
Reflexivity.
For any
Symmetry.
For any
Transitivity.
For any
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
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
Consider the N6A 3K6 postal code. The equivalence class
Equivalence classes on the integers
Let
In general, the equivalence classes under
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
Partial Proof
We will prove that
Proceed by contrapositive. Assume
By definition, we have:
Since
Let
By contrapositive, it must be that
This theorem has an important consequence. It tells us that an equivalence relation on a set
Definition (partition)
A partition of a set
Written in mathematical notation, a partition of the set
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,
is even).The integers can also be partitioned into three groups: positive, negative, and
.The integers can also be partitioned into groups of pairs:
for any non-zero integer , and a lone group .
These last two examples show an important characteristic of partitions.
Given some set
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
Theorem
For an equivalence relation
What are the equivalence classes of the relation x % 10
= y % 10
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
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” (
Properties of
The ordering defined on the real numbers by
Reflexive: for any number
Antisymmetric: for any two numbers
Transitive: for any three numbers
More generally, a binary relation defines a partial order if it is reflexive, antisymmetric, and transitive.
Definition (partial order)
A binary relation
Recall that we can denote an equivalence relation with
Tip
Just as how
Let’s see our first example of a partial order.
Partial order on a power set
For a set
Reflexive: For any set
Antisymmetric: For any two sets
Transitive: For any three sets
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
Our first poset
Consider the set
How can we formally define
Out first poset
Let
; or for some and , and for all ; or and for all .
Where
Therefore,
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
Definition (total order)
A total order is a partial order
Definition (totally ordered set)
A totally ordered set is a set
Most “natural” partial orders are actually total orders.
Indeed, the ordering of
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:
Let
In the poset
Definition (comparable)
In a partially ordered set
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
For example, the natural numbers under the usual ordering have
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
This poset does not have a maximum element:
This poset also does not have a minimum element:
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
Proof: Let the maximum element of the poset be
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
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
In this set,
Why? Because the only comparable elements are:
Therefore,
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
Consider the set of integers under the normal ordering.
Now we can describe the Hasse diagram of a poset.
For a poset
Each element
is represented as a “dot”, “circle”, or “vertex”.The vertex representing
is drawn above any other element such that .A line segment is drawn between the vertex representing
and the vertex representing if covers .
A very simple Hasse diagram can be made the for the subset of natural numbers
Fig. 2.18 A Hasse diagram for
A more complex Hasse diagram can be made for the power set of
Fig. 2.19 A Hasse diagram for
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
Positions in Hasse diagrams
In a Hasse diagram, consider two vertices
Positions in Hasse diagrams
Maybe.
Consider Fig. 2.19.
2.2.5. Exercises#
Exercise 2.14
Consider the sets
Solution to Exercise 2.14
“student
enjoys the music of band ”,“student
has seen band live in concert”,“student
dislikes band ”,“student
is a member of band ” (probably a relation with very few elements).
Exercise 2.15
Consider the set
What is a possible binary relation from
Solution to Exercise 2.15
No such relation is immediately obvious. Generally speaking, binary relations from one set to a different set are symmetric. For example “
Exercise 2.16
Let
List the pairs contained in the following relations.
Solution to Exercise 2.16
Exercise 2.17
Let
List the pairs contained in the following relations.
Solution to Exercise 2.17
Exercise 2.18
Let
Draw a table representing the relation:
Solution to Exercise 2.18
X |
X |
X |
X |
X |
|
X |
X |
X |
|||
X |
|||||
Exercise 2.19
Consider binary relations on the set
Solution to Exercise 2.19
Transitive.
Reflexive, symmetric, and transitive.
Symmetric.
Antisymmetric (vacuously so).
Reflexive, symmetric, transitive, and antisymmetric.
Nothing.
Exercise 2.20
Consider binary relations on the set
Solution to Exercise 2.20
Transitive and Antisymmetric.
Antisymmetric (vacously so)
Nothing.
Symmetric.
Symmetric.
Exercise 2.21
A binary relation
Which relations in Exercise 2.19 are irreflexive?
Can a binary relation be neither reflexive nor irrefelexive?
Solution to Exercise 2.21
.Yes. Consider
on the set . It is not reflexive because . It is not irreflexive because .
Exercise 2.22
Let
Solution to Exercise 2.22
Symmetry says:
Transitivity says:
Reflexivity says:
Exercise 2.23
Show that the following relations are antisymmetric.
Solution to Exercise 2.23
By definition, we have antisymmetry as
Consider pairs which would be in
. This includes . Are there any pairs , such that is also in ? There are only two pairs of numbers which are equal to each other’s squares (i.e. and ): and . Since and , is antisymmetric.The relation
adds to many many pairs of the form . However, to have and , we need (notice that we square the second inequality and then join them together). However, only when or . We can see that and . This means is antisymmetric.
Exercise 2.24
Let the
What is wrong with the following statement?
“Since
Solution to Exercise 2.24
Recall that
Exercise 2.25
Consider a binary relation
Show that this relation is an equivalence relation.
What are the equivalence classes under this relation?
Solution to Exercise 2.25
Reflexive: For any non-zero integer
, .Symmetric: For any two non-zero integers
and , . Thus, if , .Transitive: Let
and . We show that . Since and must have the same sign. Since , and must have same sign. Therefore, and must have the same sign and thus .
The equivalences classes are
Exercise 2.26
Consider a binary relation
Show that this relation is an equivalence relations.
What are the equivalence classes of
and (i.e. the truth values true and false).
Solution to Exercise 2.26
Reflexive: For any propositional formula
, , therefore ; Symmetric: For any two propositional formulas , therefore is symmetric. Transitive: For any three propositional formulas such that and we have . Therefore, . is the set of tautologies, 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.
: For , if and only if . : For , if and only if . : For two sets and , if .
Solution to Exercise 2.27
This is a total order. Reflexive: for all real numbers
. Transitive: for all real numbers , . Antisymmetric: . It is a total order because every real number is comparable to another real number.This is not a partial order. It is not reflexive:
.Indeed this property is the same as saying
. 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?
Solution to Exercise 2.28
, , , , , , , . , are minimal. are maximal. There is not a maximum or minimum. , , , , , , , , , , , , , , are minimal. are maximal. There is no maximum or minimum.