1.2 Relations
We often want to talk about whether two elements of a given set are related in a particular way, e.g. whether one real number is smaller or larger than the other, whether two integers have the same remainder on dividing by 7, and so on.
For example, \(<\) is a relation on the set of natural numbers: if a and b are natural numbers then \(a<b\) is either true or false. Equally, there is a relation \(\sim\) on the set of real numbers defined by \(a \sim b\) iff \(a-b\) is a whole number. Then \(1.5 \sim 2.5\) is true, but \(1.5 \sim \pi\) is false.
The formal set theoretical defintion of a relation on \(X\times X\) is a subset of \(X\times X\). (Can you see how to make a subset of \(X\times X\) out of a relation on X, and vice versa?).
Here are some properties a relation can have.
Definition 1.4 Let \(\sim\) be a relation on a set X.
- \(\sim\) is called symmetric if for any \(x,y \in X\) if \(x\sim y\) then \(y \sim x\)
- \(\sim\) is called reflexive if for any \(x\in X\) we have \(x\sim x\).
- \(\sim\) is called transitive if for any \(x,y,z \in X\) if \(x\sim y\) and \(y\sim z\) then \(x \sim z\).
- \(\sim\) is called an equivalence relation if it is reflexive, symmetric, and transitive.
Equivalence relations turn out to be very important. The simplest example is the \(=\) relation on any set, but you will see less familiar examples in lectures.
Definition 1.5
- Let \(\sim\) be an equivalence relation on a set X, and let \(x \in X\). The equivalence class of x, written \([x]\) or \([x]_\sim\), is \[ [x] = \{ y \in X: y \sim x\}. \]
- A partition of a set X is a collection of nonempty subsets of X, called the parts of the partition, with the property that every element of X belongs to exactly one part.
In other words, a partition is a collection of disjoint nonempty subsets of X whose union is X. For example, \(\{1, 2\}, \{3, 5\}, \{4\}\) is a partition of \(\{1,2,3,4,5\}\).
The next result says that the set of equivalence classes of an equivalence relation on a set X form a partition of X.
Proposition 1.1 Let \(\sim\) be an equivalence relation on a set X. Then
- Every \(x \in X\) belongs to some equivalence class, and
- if two equivalence classes are not disjoint, then they are equal.
Proof.
- \(x \in [x]\), because \(x \sim x\), because \(\sim\) is reflexive.
- Suppose \(z \in [x]\cap [y]\), we’ll show \([x]=[y]\).
- First of all, we have \(z \sim x\) and \(z \sim y\). By symmetry \(x \sim z\).
- \(x\sim z \sim y\), so by transitivity \(x \sim y\).
- Let \(u \in [x]\), so \(u \sim x\). Then \(u \sim x \sim y\), so \(u \in [y]\). We’ve shown \([x]\subseteq [y]\).
- The same argument shows \([y]\subseteq [x]\), so \([x]=[y]\).
Conversely, suppose X is a set and you are given a partition of X. Then you can define a relation \(\sim\) on X by \(x \sim y\) if and only if they lie in the same part of the partition. It’s not hard to check that this is an equivalence relation, and the equivalence classes are exactly the collection of nonempty subsets we started with. Thus equivalence relations on a set X are ‘the same thing’ as partitions of X.
1.2.1 Congruence modulo n
We finish the section on relations by discussing one of the most important kinds of equivalence relation, congruence modulo (mod for short) an integer n.
For each nonzero integer n we define a relation on the integers \(\mathbb{Z}\) called congruence mod n as follows: two integers a and b are congruent mod n if \(a-b\) is divisible by n.
This is equivalent to saying a and b have the same remainder when you divide by n. For example, 7 and 15 are congruent modulo 4 (as 7-15=-8 is a multiple of 4), but they are not congruent modulo 5 (as 7-15=-8 is not a multiple of 5.)
It is common to write \[ a \equiv b \mod n \] to mean that a is congruent to b mod n. You should check that congruence modulo n is an equivalence relation.
The set of equivalence classes under congruence modulo n is written \(\mathbb{Z}_n\). For example, if n=2 there are exactly two equivalence classes, \([0] = \{\ldots, -4, -2, 0, 2, 4, \ldots\}\) which is the set of all even numbers and \([1] = \{\ldots, -3, -1, 1, 3, \ldots \}\) which is the set of all odd numbers.