2 Relations

In mathematics a relation (sometimes binary relation) is something like \(\le\) or \(\subseteq\) or \(=\) that tells us that there is a relationship between two objects.

 

Formally, we define it as the set of ordered pairs \((a,b)\) for which the relation holds.

Definition 2.1 (Relation) 

A relation \(R\) on a set \(S\) is a subset of \(S \times S\).

 

If \((a,b) \in R\), we write \(a R b\).

 

It's a little bit awkward that we use the letter \(R\) for both the name of the relation and the symbol to indicate that \(a\) is related to \(b\), and indeed in many cases there is some other conventional notation that we use to indicate that \(a\) is related to \(b\).

 

It may seem odd to think of \(\le\) as a subset like this, but this definition turns out to be a convenient way to describe such a relation as a mathematical object.  We could alternatively think of a relation as a binary operation that takes two input elements and returns a "True" or "False", depending on whether the two elements are related according to that relation. But this is effectively the same thing as our definition above, since the subset \(R\) is simply those elements of \(S \times S\) that return "True" under that operation.

 

    (i) The "less than or equal to" relation on the set of real numbers is \(\{ (x,y) \in \mathbb{R}^2 : x\le y \}\).  We write \(x\le y\) if \((x,y)\) is in this set.

    (ii) The "divides" relation on \(\mathbb{N}\) is \(\{ (m,n) \in \mathbb{N}^2 :\ m \text{ divides } n \}\).  We write \(m | n\) if \((m,n)\) is in this set.

    (iii) For a set \(S\), the "subset" relation on \(\mathcal{P}(S)\) is \(\{ (A,B) \in \mathcal{P}(S)^{2} : A \subseteq B\}\).  We write \(A \subseteq B\) if \((A,B)\) is in this set.

 

I would also like you to be aware of some trivial examples, not because these are particularly interesting themselves, but because they can be helpful as we start to think about properties that relations do or do not have.

 

For any set \(S\), we can define the following relations.

    (i) Everything's related. There is a relation \(R\) defined by "for all \(x\) and for all \(y\), \(xRy\)".

    (ii) Nothing's related. There is a relation \(R\) defined by "for all \(x\), there does not exist \(y\) such that \(xRy\)".

    (iii) Everything's related only to itself. There is a relation \(R\) defined by "for all \(x\), \(xRy\) if and only if \(y=x\)."

 

Note that if \(S =\varnothing\), then these all describe the same relation, giving us perhaps the ultimate trivial relation.

 

Finally, let's have a real-world example.

 

Consider the set \(C\) of all chess players. Then "\(aRb\) if and only if \(a\) has ever beaten \(b\) at chess" is a relation on \(C\).

 

Note that for this relation, \(aRb\) and \(bRa\) mean different things, and those things are not mutually exclusive. Also, there are pairs of elements \(a\) and \(b\) such that neither \(aRb\) nor \(bRa\). For example, Magnus Carlsen has never beaten me at chess, and I haven't beaten him (yet).

 

 

Definition 2.5 (Reflexive, symmetric, anti-symmetric, transitive) 

Let \(S\) be a set, \(R\) a relation on \(S\) and \(x,y,z\in S\). We say that

    (i) \(R\) is reflexive if \(xRx\) for all \(x\) in \(S\),

    (ii) \(R\) is symmetric if whenever \(xRy\) then \(yRx\),

    (iii) \(R\) is anti-symmetric if whenever \(xRy\) and \(yRx\) then \(x=y\),

    (iv) \(R\) is transitive if whenever \(xRy\) and \(yRz\) then \(xRz\).

 

 

For the three trivial examples, decide whether they have the properties we just defined (does it matter what the set \(S\) is?)

 

Convince yourself that the relation in the chess example above satisfies none of these properties.

The relation \(\le\) on \(\mathbb{R}\) is reflexive, anti-symmetric, and transitive.

The relation \(<\) on \(\mathbb{R}\) is not reflexive or symmetric, but it is anti-symmetric and transitive.

The relation \(\neq\) on \(\mathbb{R}\) is not reflexive, anti-symmetric or transitive, but it is symmetric.

The relation \(=\) on \(\mathbb{R}\) is reflexive, symmetric, and transitive.

 

Here is another important example:

Let \(n\ge 2\) be an integer, and define \(R\) on \(\mathbb{Z}\) by saying \(a R b\) if and only if \(a-b\) is a multiple of \(n\).  Then \(R\) is reflexive, symmetric and transitive.

 

Proof. Reflexivity: For any \(a\in\mathbb{Z}\) we have \(aR a\) as \(0\) is a multiple of \(n\).

 

Symmetry: If \(aR b\) then \(a-b=kn\) for some integer \(k\). So \(b-a=-kn\), and hence \(bR a\).

 

Transitivity: If \(aR b\) and \(bR c\) then \(a-b=kn\) and \(b-c=ln\) for integers \(k,l\). So then \(a-c=(a-b)+(b-c)=(k+l)n\), and hence \(aRc\).

 

 

Example 2.7 provides an example of a particularly important type of relation, an equivalence relation.  An equivalence relation provides a way of saying two objects are, in some particular sense, `the same':

 

Definition 2.8 (Equivalence relation) 

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

 

If \(R\) is an equivalence relation, we denote it by \(\sim\) (various other symbols, including \(\equiv\), are sometimes used).  

 

The following are all examples of equivalence relations:

    (i) \(S=\mathbb{C}\), with \(z\sim w\) if and only if \(\left\vert z\right\vert =\left\vert w\right\vert \);

    (ii) \(S\) is the set of polygons in \(\mathbb{R}^{2}\), and \(\sim\) is congruence;

    (iii) \(S\) is the set of differentiable functions on \(\mathbb{R}\), and \(f \sim g\) if and only if \(f'(x) = g'(x)\)

    (iv) The relation on \(\mathbb{Z}\) defined in Example 2.7; in this case \(\sim\) represents congruence modulo \(n\).  It is the basis for modular arithmetic, and you will often see \(a \sim b\) expressed as \(a \equiv b \pmod{n}\) in this case.

 

An equivalence relation provides a way of grouping together elements that can be viewed as being the same.

Definition 2.10 (Equivalence class) 

Given an equivalence relation \(\sim\) on a set \(S\), and given \(x \in S\), the equivalence class of \(x\), denoted \(\overline{x}\) (or sometimes \([x]\)), is the subset 

 

 

For example, with the equivalence relation defined in Example 2.7 (congruence modulo \(n\)) the equivalence class of \(1\) is the set \(\overline{1} = \{ \ldots, -n+1, 1, n+1, 2n+1, \ldots \}\); that is, all the integers that are congruent to \(1\) modulo \(n\). Note that \(1\) and \(\overline{1}\) are different.

 

Definition 2.11 (Quotient set) 

Given an equivalence relation \(\sim\) on a set \(S\), the set of equivalence classes is called the quotient set and is denoted \(S/\!\sim\). We have

or more explicitly

 

 

Note that \(S/\!\sim\) is a set of sets.

 

Grouping the elements of a set into equivalence classes like this provides a partition of the set, which we define as follows.

 

Definition 2.12 (Partition) 

A partition of a set \(S\) is a collection of subsets \(\left\{ A_i \subseteq S : i \in I \right\}\), where \(I\) is an indexing set, with the property that 

    (i) \(A_i \neq \varnothing\) for all \( i \in I\) (that is, all the subsets are non-empty),

    (ii) \(\bigcup_{i \in I} A_i = S\) (that is, every member of \(S\) lies in one of the subsets),

    (iii) \(A_i \cap A_j = \varnothing\) for every \(i \neq j\) (that is, the subsets are disjoint).

 

The subsets are called the parts of the partition.

 

For example, \(\{ \{n\in \mathbb{N} : n \text{ is divisible by } 2 \}, \{n\in \mathbb{N} : n+1 \text{ is divisible by } 2 \}\}\) forms a partition of the natural numbers, into evens and odds.

 

The fact that the equivalence classes for any equivalence relation form a partition is something that will be proved in the Groups and Group Action course later in the year (though it is not particularly difficult and you may like to have a go at doing so).

 

Conversely, we can use any given partition to define an equivalence relation, by saying that \(x \sim y\) if and only if \(x\) and \(y\) are elements of the same part of the partition (you may like to check that indeed this definition satisfies the conditions to be an equivalence relation: reflexivity, symmetry and transitivity). Thus, there is a natural correspondence between equivalence relations and partitions of a set.

 

Suppose \(S\) is the set of students at Oxford.  This set can be partitioned according to colleges; that is, the partitioning subsets are the sets of students at each college, which form a partition since (i) there are no colleges with no students (I'm ignoring All Souls College for the purpose of this example), (ii) every student is a member of a college, and (iii) you can't be at more than one college (I'm ignoring some exceptions). Then the equivalence relation \(\sim\) induced by this partition says that \(x \sim y\) if and only if \(x\) and \(y\) are at the same college.  

 

This is a good example of the fact that being "equivalent" does not mean the elements are actually the same! Every one of you is wonderfully unique... but there might be some purpose for which it is convenient to view all the students in a college as essentially the same, and the equivalence class provides a way of representing that mathematically.