Relations

Foundations of mathematics

Introduction

In this article we build upon our previous article on sets to introduce relations, the way of expressing relationships between elements of sets. An understanding of relations is crucial to understand functions, widely used in many advanced topics in mathematics.

Prerequisites

To understand the relations, we recommend familiarity with the concepts in

Follow the above links to first get acquainted with the corresponding concepts.

Relations

A relation from a set \( \sA \) to a set \( \sB \) is a subset of \( \sA \times \sB \), where \( \times \) denotes the Cartesian product.

Example

Consider the sets \( \sA = \lbrace 1, 2, 3 \rbrace \) and \( \sB = \lbrace x, y, z \rbrace \).

$$ R_1 = \lbrace (1,x), (2, y), (1, z) \rbrace $$ $$ R_2 = \lbrace (x,1), (y,2), (z,3) \rbrace $$ $$ R_3 = \lbrace (1,1), (2, y), (3, z) \rbrace $$

Among these, \( R_1 \) is a relation from \( \sA \) to \( \sB \) and \( R_2 \) is a relation from \( \sB \) to \( \sA \). The set \( R_3 \) is not a relation between \( \sA \) and \( \sB \) because it contains the ordered pair \( (1,1) \).

Domain of a relation

The domain of a relation \( R \) from a set \( A \) to a set \( B \) is defined as $$ \text{dom}(R) = \{ a \in A: (a,b) \in R, \text{ for some } b \in B \} $$

Thus, the domain of a relation is the set of all elements of \( A \) that appear in the relation.

Example

Consider the relation \( R = \lbrace (1,x), (2,y), (2,z), (3,x) \rbrace \). Then \( \text{dom}(R) = \lbrace 1, 2, 3 \rbrace \).

Range of a relation

The range of a relation \( R \) from a set \( A \) to a set \( B \) is defined as $$ \text{range}(R) = \{ b \in B: (a,b) \in R, \text{ for some } a \in A \} $$

Thus, the range of a relation is the set of all elements of \( B \) that appear in the relation.

Example

Consider the relation \( R = \lbrace (1,x), (2,y), (2,z), (3,x) \rbrace \). Then \( \text{range}(R) = \lbrace x, y, z \rbrace \).

Inverse relation

If \( R \) is a relation from a set \( A \) to a set \( B \), then an inverse relation \( R^{-1} \) is defined as $$ R^{-1} = \{ (b,a) : (a,b) \in R \} $$

Example

Consider the relation \( R = \lbrace (x,1), (x,2), (y,1), (z,2) \rbrace \)

The inverse relation is \( \inv{R} = \lbrace (1,x), (1,y), (2,x), (2,z) \rbrace \).

Relation on a set

A relation on a set \( A \) is a relation such that both the domain and the range of the relation belong to \( A \). This means, relation on a set \( A \) is a subset of \( A \times A \).

Example

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).

The relation \( R = \lbrace (1,1), (1,2), (2,3) \rbrace \) is a relation on the set \( A \) since both coordinates of each ordered pair belong to \( A \).

Reflexive relation on a set

A relation \( R \) on a set \( A \) is said to be reflexive, if \( (x,x) \in R, \forall x \in A \).

Note that a reflexive relation on a set may also contain ordered pairs of the form \( (x,y) \) such that \( x \ne y \), as long as \( x \in A \) and \( y \in A \).

Examples

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).

  1. The relation \( R_1 = \lbrace (1,1), (2,2), (3,3) \rbrace \) is reflexive.
  2. The relation \( R_2 = \lbrace (1,1), (2,2), (3,3), (1,2), (3,1) \rbrace \) is also reflexive, although it contains \( (1,2) \) and \( (3,1) \).
  3. The relation \( R_3 = \lbrace (1,1), (1,2), (2,1), (1,3), (3,1) \rbrace \) is not reflexive because it is missing \( (2,2) \) and \( 3,3) \).

Irreflexive relation on a set

A relation \( R \) on a set \( A \) is said to be irreflexive, if for every \( x \in A \), \( (x,x) \not\in R \).

Examples

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).

  1. The relation \( R_1 = \lbrace (1,1), (2,2), (3,3) \rbrace \) is reflexive, but not irreflexive.
  2. The relation \( R_2 = \lbrace (1,2), (2,3), (3,1) \rbrace \) is irreflexive, but not reflexive.
  3. The relation \( R_3 = \set{ (1,1), (1,2), (2,3), (2,2), (3,1)} \) is not reflexive because it lacks \( (3,3) \). Also, it is not irreflexive because it contains \( (1,1) \) and \( (2,2) \).

Symmetric relation on a set

A relation \( R \) on a set \( A \) is said to be symmetric , if \( (x,y) \in R \) implies that \( (y,x) \in R \) for all \(x,y \in A \).

Note that if \( (x,y) \not\in R \), then we do not require \( (y,x) \) to be in \( R \).

Examples

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).

  1. The relation \( R_1 = \lbrace (1,1), (2,2), (3,3), (1,2), (3,1) \rbrace \) is not symmetric because it is missing \( (2,1) \) and \( (1,3) \).
  2. The relation \( R_2 = \lbrace (1,1), (1,2), (2,1), (1,3), (3,1) \rbrace \) is symmetric.

Antisymmetric relation on a set

A relation \( R \) on a set \( A \) is said to be antisymmetric , if \( (x,y) \in R \) and \( (y,x) \in R \) only if \( x = y \), for all \(x,y \in A \).

Note that if \( (x,y) \not\in R \), then we do not require \( (y,x) \) to be in \( R \).

Examples

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).

  1. The relation \( R_1 = \lbrace (1,1), (2,2), (3,3), (1,2), (3,1) \rbrace \) is antisymmetric
  2. The relation \( R_2 = \lbrace (1,1), (1,2), (2,1), (1,3), (3,1) \rbrace \) is not antisymmetric because \( (1,2) \) and \( (2,1) \) as well as \( (1,3) \) and \( (3,1) \) are present.

Asymmetric relation on a set

A relation \( R \) on a set \( A \) is said to be asymmetric , if \( (x,y) \in R \) implies that \( (y,x) \not\in R \) for all \(x,y \in A \).

Note that if \( (x,y) \not\in R \), then we do not require \( (y,x) \) to be absent from \( R \).

Examples

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).

  1. The relation \( R_1 = \lbrace (1,2), (2,1), (2,3), (3,1) \rbrace \) is not asymmetric because it contains \( (2,1) \).
  2. The relation \( R_2 = \lbrace (1,2), (2,3), (3,1) \rbrace \) is asymmetric.

Transitive reltaion on a set

A relation \( R \) on a set \( A \) is said to be transitive, if \( (x,y) \in R \) and \( (y,z) \in R \) implies that \( (x,z) \in R \), for all \( x,y,z \in A \).

Note that if \( (x,y) \not\in R \) or \( (y,z) \not\in R \), then \( (x,z) \) is not required to be in \( R \).

Examples

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \).

  1. The relation \( R_1 = \lbrace (1,1), (2,2), (3,3), (1,2), (3,1) \rbrace \) is not transitive because it is missing \( (3,2) \).
  2. The relation \( R_2 = \lbrace (1,2), (2,3), (1,3) \rbrace \) is transitive.

Equivalence relation

A relation on a set is known as an equivalence relation if it is reflexive, symmetric, and transitive.

Example

Let \( A = \lbrace 1, 2, 3 \rbrace \).

  1. The relation \( R_1 = \lbrace (1,1), (2,2), (3,3), (1,2), (3,1) \rbrace \) is reflexive, but not symmetric or transitive.
  2. The relation \( R_2 = \lbrace (1,1), (1,2), (2,1), (1,3), (3,1) \rbrace \) is symmetric but not reflexive or transitive.
  3. The relation \( R_3 = \lbrace (1,2), (2,3), (1,3) \rbrace \) is transitive but neither symmetric nor reflexive.
  4. The relation \( R_4 = \lbrace (1,1), (2,2), (3,3), (1,2), (2,1), (3,1), (1,3), (3,2), (2,3) \rbrace \) is reflexive, symmetric, and transitive.

Thus, the relation \( R_4 \) is an equivalence relation.

Equivalence classes

If \( R \) is an equivalence relation on a set \( A \), then for \( a \in A \), the set of all elements related to \( a \) is known as it's equivalence class. It is denoted as \( [a] \) and defined as

$$ [a] = \{x \in A: (x,a) \in R \} $$

Example

Let \( A = \lbrace 1, 2, 3 \rbrace \). Let \( R = \lbrace (1,1), (2,2), (3,3), (1,2), (2,1) \rbrace \) be an equivalence relation on \( A \).

Then, the following are the equivalence classes associated with elements of \( A \).

  1. \( [1] = \lbrace 1,2 \rbrace \)
  2. \( [2] = \lbrace 1,2 \rbrace \)
  3. \( [3] = \lbrace 3 \rbrace \)

Complementary relation

A relation \( \complement{R} \) is said to be a complementary relation to the relation \( R \) if for every \( (a,b) \in R \), it is the case that \( (a,b) \not\in \complement{R} \).

Example

Consider the relation \( R = \set{ (a,b) | a < b } \) on a set of integers. The complement of this relation is the relation \( \complement{R} = \set{ (a,b) | a \ge b } \).

Powers of a relation

Let \( R \) be a relation on a set \( A \). The powers \( R^n \), where \( n = 1, 2, 3, \ldots\), are defined inductively by

$$ R^1 = R \text{ and } R^{n+1} = R^n \circ R $$

where \( \circ \) denotes the composite relation.

Example

Let \( R = \set{(a,b), (b,c)} \). Then

$$ R^1 = \set{(a,b), (b,c)} $$ $$ R^2 = \set{(a,c)} $$

Closures of a relation

Consider a relation \( R \) on a set \( A \). Suppose \( R \) does not have a particular property \( P \), such as reflexivity, symmetry, or transitivity.

If there is another relation \( S \) on the set \( A \) with the property \( P \) containing \( R \) such that \( S \) is the subset of all relations on the set \( A \) with the property \( P \) that contain \( R \), then the set \( S \) is known as closure of \( R \) with respect to \( P \).

Example

Consider a relation \( R = \set{(x,x)} \) on the set \( A = \set{x, y} \). Clearly, \( R \) is not reflexive. However, the set \( S = \set{(x,x), (y,y)} \) is reflexive and \( R \subseteq S \). Moreover, \( S \) will be the subset of any reflexive relation on the set \( A \) that contains \( R \).

Thus, the relation \( S \) is the reflexive closure of \( R \).

Next-article

With a sound understanding of relations, we move on to specialized relations known as functions.

Please share

Let your friends, followers, and colleagues know about this resource you discovered.

Let's connect

Please share your comments, questions, encouragement, and feedback.