Mathematics · Ch 1 — Relations and Functions

Types of Relations

1.2

Types of Relations

1.2 Types of Relations

The Two Extreme Relations

A relation in a set $A$ is any subset of $A \times A$ . The smallest such subset is the empty set $\phi$ and the largest is the whole product $A \times A$ ; these two extremes give the simplest relations.

For $A = \{1, 2, 3, 4\}$ , the relation $R = \{(a, b): a - b = 10\}$ is empty ( $R = \phi$ ), since no pair satisfies $a - b = 10$ . The relation $R' = \{(a, b): |a - b| \geq 0\}$ is all of $A \times A$ , since $|a - b| \geq 0$ always holds.

Empty Relation

R

Universal Relation

R

Both are sometimes called trivial relations.

Note

Every other relation lies strictly between the extremes: $\phi \subset R \subset A \times A$ .

Notation Reminder

A relation can be given by the roster method (listing all ordered pairs) or the set-builder method (stating the condition), and $a\,R\,b$ means $(a, b) \in R$ . For instance, $R = \{(a, b): b = a + 1\}$ in $\{1, 2, 3, 4\}$ can be written as $a\,R\,b$ if and only if $b = a + 1$ .

Three Fundamental Properties of Relations

R

In words: a reflexive relation contains every self-pair $(a, a)$ ; a symmetric relation is "two-way" — whenever a pair appears, its reverse appears; a transitive relation "chains" — from $a$ to $b$ and $b$ to $c$ you may go straight from $a$ to $c$ .

Watch out

For transitivity, the condition applies only when both $(a, b)$ and $(b, c)$ are present; if either is missing, transitivity is not violated. Also $a$ , $b$ , and $c$ need not be distinct — they can be the same element.

Equivalence Relation

R

An equivalence relation is one of the most important concepts in mathematics — it captures the idea of "sameness" or equality in a generalized sense.

Equivalence Classes

Consider $R = \{(a, b): 2 \text{ divides } a - b\}$ on the set $\mathbb{Z}$ of integers; this relates two integers exactly when they have the same parity (both even or both odd). Observe:

All even integers are related to $0$ : $(0, \pm 2), (0, \pm 4), \dots$ all lie in $R$ ; no odd integer is related to $0$ .
All odd integers are related to $1$ : $(1, \pm 1), (1, \pm 3), \dots$ all lie in $R$ ; no even integer is related to $1$ .

Let $E$ be the even integers and $O$ the odd integers. Then all elements of $E$ are related to each other and all of $O$ to each other; no element of $E$ is related to one of $O$ ; and $E$ , $O$ are disjoint with $\mathbb{Z} = E \cup O$ . The subset $E$ is the equivalence class containing $0$ , denoted $[0]$ , and $O$ is the class $[1]$ . Note $[0] \neq [1]$ , $[0] = [2r]$ and $[1] = [2r + 1]$ for any $r \in \mathbb{Z}$ .

R

Going in Reverse: From Partition to Equivalence Relation

The correspondence works both ways — a partition also defines an equivalence relation. Subdivide $\mathbb{Z}$ into three mutually disjoint subsets:

A_1 = \{x \in \mathbb{Z}: x \text{ is a multiple of } 3\} = \{\dots, -6, -3, 0, 3, 6, \dots\}

$A_2 = \{x \in \mathbb{Z}: x - 1 \text{ is a multiple of } 3\} = \{\dots, -5, -2, 1, 4, 7, \dots\}$ …

Definition 1Empty Relation

Definition

A relation $R$ in a set $A$ is called an empty relation if no element of $A$ is related to any element of $A$ .

In set notation:

R = \phi \subset A \times A

Here, $\phi$ denotes the empty set. This means $R$ contains zero ordered pairs — it has no elements at all.

Intuition

Think of the empty relation as a "no-link" situation. Even if you check every possible pair of elements from $A$ , you will never find a pair that satisfies the condition for being in $R$ . The relation is simply a collection of nothing.

Concrete Example

Let $A = \{1, 2, 3, 4\}$ .

Define $R = \{(a, b) : a - b = 10\}$ . …

Definition 2Universal Relation

Definition

A relation $R$ in a set $A$ is called a universal relation if each element of $A$ is related to every element of $A$ .

In set notation, this means:

R = A \times A

That is, $R$ contains all possible ordered pairs $(a, b)$ where $a$ and $b$ are any elements of $A$ .

Intuition

Think of the universal relation as the "everything is connected to everything" relation. There are no restrictions — every pair of elements (including the same element with itself) is included. It is one of the two trivial relations (the other being the empty relation).

Concrete Example

Let $A = \{1, 2, 3\}$ .

The universal relation $R$ in $A$ is:

$R = \{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)\}$ …

Definition 3Types of Relations

Reflexive Relation

A relation $R$ in a set $A$ is called reflexive if every element of $A$ is related to itself.

Condition: For every $a \in A$ , the ordered pair $(a, a)$ must belong to $R$ .
In other words: $a\,R\,a$ must hold for all $a \in A$ .

Intuition: Think of a mirror — each element must "see itself" in the relation.

Example: Let $A = \{1, 2, 3\}$ and $R = \{(1,1), (2,2), (3,3), (1,2)\}$ .

Here, $(1,1)$ , $(2,2)$ , and $(3,3)$ are all present, so $R$ is reflexive.

Symmetric Relation

A relation $R$ in a set $A$ is called symmetric if whenever one element is related to another, the reverse is also true.

Condition: For all $a_1, a_2 \in A$ , if $(a_1, a_2) \in R$ , then $(a_2, a_1) \in R$ .
In other words: $a_1\,R\,a_2$ implies $a_2\,R\,a_1$ .

Intuition: It's a two-way street — if $a$ is connected to $b$ , then $b$ must be connected back to $a$ . …

Definition 4Equivalence Relation

Definition of Equivalence Relation

A relation $R$ in a set $A$ is called an equivalence relation if it satisfies all three of the following conditions:

Reflexive: Every element of $A$ is related to itself.

That is, $(a, a) \in R$ for every $a \in A$ .
Symmetric: If one element is related to another, then the second is related back to the first.

That is, if $(a, b) \in R$ , then $(b, a) \in R$ for all $a, b \in A$ .
Transitive: If one element is related to a second, and the second is related to a third, then the first is related to the third.

That is, if $(a, b) \in R$ and $(b, c) \in R$ , then $(a, c) \in R$ for all $a, b, c \in A$ .

Intuition

An equivalence relation groups elements of a set into "families" where every member of a family is connected to every other member (like being "equal" in some way), and no member of one family is connected to any member of another family.

Tiny Concrete Example

Let $A = \{1, 2, 3\}$ and define $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ .

Reflexive: $(1,1), (2,2), (3,3)$ are all present. ✓
Symmetric: $(1,2)$ is present and so is $(2,1)$ . ✓ …

Start your 14-day free trial to unlock the full solution →

← Previous · 1.1Introduction Next · 1.2 →Example 1 — Let A be the set of all students of a boys school. Show that the relat…