1.3: Relations

\(\newcommand{\R}{\mathbb{R}}\) \(\newcommand{\N}{\mathbb{N}}\) \(\newcommand{\Z}{\mathbb{Z}}\)

Relations play a fundamental role in probability theory, as in most other areas of mathematics.

Definitions and Constructions

Suppose that \(S\) and \(T\) are sets. A relation from \(S\) to \(T\) is a subset of the product set \(S \times T\).

1. The domain of \(R\) is the set of first coordinates: \(\text{domain}(R) = \left\{x \in S: (x, y) \in R \text{ for some } y \in T\right\}\).
2. The range of \(R\) is the set of second coordinates: \(\text{range}(R) = \left\{y \in T: (x, y) \in R \text{ for some } x \in S\right\}\).

A relation from a set \(S\) to itself is a relation on \(S\).

As the name suggests, a relation \(R\) from \(S\) into \(T\) is supposed to define a relationship between the elements of \(S\) and the elements of \(T\), and so we usually use the more suggestive notation \(x\,R\,y\) when \((x, y) \in R\). Note that the domain of \(R\) is the projections of \( R \) onto \( S \) and the range of \( R \) is the projection of \( R \) onto \( T \).

Basic Examples

Suppose that \(S\) is a set and recall that \(\mathscr{P}(S)\) denotes the power set of \(S\), the collection of all subsets of \(S\). The membership relation \(\in\) from \(S\) to \(\mathscr{P}(S)\) is perhaps the most important and basic relationship in mathematics. Indeed, for us, it's a primitive (undefined) relationship—given \(x\) and \(A\), we assume that we understand the meaning of the statement \(x \in A\).

Another basic primitive relation is the equality relation \(=\) on a given set of objects \(S\). That is, given two objects \(x\) and \(y\), we assume that we understand the meaning of the statement \(x = y\).

Other basic relations that you have seen are

1. The subset relation \(\subseteq\) on \(\mathscr{P}(S)\).
2. The order relation \(\le\) on \(\R\)

These two belong to a special class of relations known as partial orders that we will study in the next section. Note that a function \(f\) from \(S\) into \(T\) is a special type of relation. To compare the two types of notation (relation and function), note that \(x\,f\,y\) means that \(y = f(x)\).

Constructions

Since a relation is just a set of ordered pairs, the set operations can be used to build new relations from existing ones.

if \(Q\) and \(R\) are relations from \(S\) to \(T\), then so are \(Q \cup R\), \(Q \cap R\), \(Q \setminus R\).

1. \(x(Q \cup R)y\) if and only if \(x\,Q\,y\) or \(x\,R\,y\).
2. \(x(Q \cap R)y\) if and only if \(x\,Q\,y\) and \(x\,R\,y\).
3. \(x(Q \setminus R)y\) if and only if \(x\,Q\,y\) but not \(x\,R\,y\).
4. If \(Q \subseteq R\) then \(x\,Q\,y\) implies \(x\,R\,y\).

If \(R\) is a relation from \(S\) to \(T\) and \(Q \subseteq R\), then \(Q\) is a relation from \(S\) to \(T\).

The restriction of a relation defines a new relation.

If \(R\) is a relation on \(S\) and \(A \subseteq S\) then \(R_A = R \cap (A \times A)\) is a relation on \(A\), called the restriction of \(R\) to \(A\).

The inverse of a relation also defines a new relation.

If \(R\) is a relation from \(S\) to \(T\), the inverse of \(R\) is the relation from \(T\) to \(S\) defined by \[ y\,R^{-1}\,x \text{ if and only if } x\,R\,y \]

Equivalently, \(R^{-1} = \{(y, x): (x, y) \in R\}\). Note that any function \(f\) from \(S\) into \(T\) has an inverse relation, but only when the \(f\) is one-to-one is the inverse relation also a function (the inverse function). Composition is another natural way to create new relations from existing ones.

Suppose that \(Q\) is a relation from \(S\) to \(T\) and that \(R\) is a relation from \(T\) to \(U\). The composition \(Q \circ R\) is the relation from \(S\) to \(U\) defined as follows: for \(x \in S\) and \(z \in U\), \(x(Q \circ R)z\) if and only if there exists \(y \in T\) such that \(x\,Q\,y\) and \(y\,R\,z\).

Note that the notation is inconsistent with the notation used for composition of functions, essentially because relations are read from left to right, while functions are read from right to left. Hopefully, the inconsistency will not cause confusion, since we will always use function notation for functions.

Basic Properties

The important classes of relations that we will study in the next couple of sections are characterized by certain basic properties. Here are the definitions:

Suppose that \(R\) is a relation on \(S\).

1. \(R\) is reflexive if \(x\,R\,x\) for all \(x \in S\).
2. \(R\) is irreflexive if no \(x \in S\) satisfies \(x\,R\,x\).
3. \(R\) is symmetric if \(x\,R\,y\) implies \(y\,R\,x\) for all \(x, \, y \in S\).
4. \(R\) is anti-symmetric if \(x\,R\,y\) and \(y\,R\,x\) implies \(x = y\) for all \(x, \, y \in S\).
5. \(R\) is transitive if \(x\,R\,y\) and \(y\,R\,z\) implies \(x\,R\,z\) for all \(x, \, y, \, z \in S\).

The proofs of the following results are straightforward, so be sure to try them yourself before reading the ones in the text.

A relation \(R\) on \(S\) is reflexive if and only if the equality relation \(=\) on \(S\) is a subset of \(R\).

Proof

This follows from the definitions. \( R \) is reflexive if and only if \( (x, x) \in R \) for all \( x \in S \).

A relation \(R\) on \(S\) is symmetric if and only if \(R^{-1} = R\).

Proof

Suppose that \( R \) is symmetric. If \( (x, y) \in R \) then \( (y, x) \in R \) and hence \( (x, y) \in R^{-1} \). If \( (x, y) \in R^{-1} \) then \( (y, x) \in R \) and hence \( (x, y) \in R \). Thus \( R = R^{-1} \). Conversely, suppose \( R = R^{-1} \). If \( (x, y) \in R \) then \( (x, y) \in R^{-1} \) and hence \( (y, x) \in R \).

A relation \(R\) on \(S\) is transitive if and only if \(R \circ R \subseteq R\).

Proof

Suppose that \( R \) is transitive. If \( (x, z) \in R \circ R \) then there exists \( y \in S \) such that \( (x, y) \in R \) and \( (y, z) \in R \). But then \( (x, z) \in R \) by transitivity. Hence \( R \circ R \subseteq R \). Conversely, suppose that \( R \circ R \subseteq R \). If \( (x, y) \in R \) and \( (y, z) \in R \) then \( (x, z) \in R \circ R \) and hence \( (x, z) \in R \). Hence \( R \) is transitive.

A relation \(R\) on \(S\) is antisymmetric if and only if \(R \cap R^{-1}\) is a subset of the equality relation \(=\) on \(S\).

Proof

Restated, this result is that \( R \) is antisymmetric if and only if \( (x, y) \in R \cap R^{-1} \) implies \( x = y \). Thus suppose that \( R \) is antisymmetric. If \( (x, y) \in R \cap R^{-1} \) then \( (x, y) \in R \) and \( (x, y) \in R^{-1} \). But then \( (y, x) \in R \) so by antisymmetry, \( x = y \). Conversely suppose that \( (x, y) \in R \cap R^{-1} \) implies \( x = y \). If \( (x, y) \in R \) and \( (y, x) \in R \) then \( (x, y) \in R^{-1} \) and hence \( (x, y) \in R \cap R^{-1} \). Thus \( x = y \) so \( R \) is antisymmetric.

Suppose that \(Q\) and \(R\) are relations on \(S\). For each property below, if both \(Q\) and \(R\) have the property, then so does \(Q \cap R\).

1. reflexive
2. symmetric
3. transitive

Proof

1. Suppose that \( Q \) and \( R \) are reflexive. Then \( (x, x) \in Q \) and \( (x, x) \in R \) for each \( x \in S \) and hence \( (x, x) \in Q \cap R \) for each \( x \in S \). Thus \( Q \cap R \) is reflexive.
2. Suppose that \( Q \) and \( R \) are symmetric. If \( (x, y) \in Q \cap R \) then \( (x, y) \in Q \) and \( (x, y) \in R \). Hence \( (y, x) \in Q \) and \( (y, x) \in R \) so \( (y, x) \in Q \cap R \). Hence \( Q \cap R \) is symmetric.
3. Suppose that \( Q \) and \( R \) are transitive. If \( (x, y) \in Q \cap R \) and \( (y, z) \in Q \cap R \) then \( (x, y) \in Q \), \( (x, y) \in R \), \( (y, z) \in Q \), and \( (y, z) \in R \). Hence \( (x, z) \in Q \) and \( (x, z) \in R \) so \( (x, z) \in Q \cap R \). Hence \( Q \cap R \) is transitive.

Suppose that \(R\) is a relation on a set \(S\).

1. Give an explicit definition for the property \(R\) is not reflexive.
2. Give an explicit definition for the property \(R\) is not irreflexive.
3. Are any of the properties \(R\) is reflexive, \(R\) is not reflexive, \(R\) is irreflexive, \(R\) is not irreflexive equivalent?

Answer

1. \( R \) is not reflexive if and only if there exists \( x \in S \) such that \( (x, x) \notin R \).
2. \( R \) is not irreflexive if and only if there exists \( x \in S \) such that \( (x, x) \in R \).
3. Nope.

Suppose that \(R\) is a relation on a set \(S\).

1. Give an explicit definition for the property \(R\) is not symmetric.
2. Give an explicit definition for the property \(R\) is not antisymmetric.
3. Are any of the properties \(R\) is symmetric, \(R\) is not symmetric, \(R\) is antisymmetric, \(R\) is not antisymmetric equivalent?

Answer

1. \( R \) is not symmetric if and only if there exist \( x, \, y \in S \) such that \( (x, y) \in R \) and \( (y, x) \notin R \).
2. \( R \) is not antisymmetric if and only if there exist distinct \( x, \, y \in S \) such that \( (x, y) \in R \) and \( (y, x) \in R \).
3. Nope.

Computational Exercises

Let \(R\) be the relation defined on \(\R\) by \(x\,R\,y\) if and only if \(\sin(x) = \sin(y)\). Determine if \(R\) has each of the following properties:

1. reflexive
2. symmetric
3. transitive
4. irreflexive
5. antisymmetric

Answer

1. yes
2. yes
3. yes
4. no
5. no

The relation \(R\) in the previous exercise is a member of an important class of equivalence relations.

Let \(R\) be the relation defined on \(\R\) by \(x\,R\,y\) if and only if \(x^2 + y^2 \le 1\). Determine if \(R\) has each of the following properties:

1. reflexive
2. symmetric
3. transitive
4. irreflexive
5. antisymmetric

Answer

1. no
2. yes
3. no
4. no
5. no