Types of Relations

Introduction

Relations on a set can be classified based on their properties. Understanding these properties is crucial for recognizing equivalence relations, which are fundamental in mathematics.

---

Reflexive Relation

Definition

A relation $R$ on set $A$ is reflexive if every element is related to itself:

$$\boxed{(a, a) \in R \text{ for all } a \in A}$$

How to Check

The diagonal elements $(a, a)$ must ALL be present in $R$.

Examples

Reflexive:

• On $A = \{1, 2, 3\}$: $R = \{(1,1), (2,2), (3,3), (1,2)\}$ (reflexive)
• “=” on real numbers: $x = x$ for all $x$ (reflexive)
• “≤” on real numbers: $x \leq x$ for all $x$ (reflexive)

Not Reflexive:

• On $A = \{1, 2, 3\}$: $R = \{(1,1), (2,2), (1,2)\}$ ✗ (missing $(3,3)$)
• “<” on real numbers: $x < x$ is false ✗

---

Symmetric Relation

Definition

A relation $R$ on set $A$ is symmetric if:

$$\boxed{(a, b) \in R \Rightarrow (b, a) \in R}$$

Whenever $a$ is related to $b$, then $b$ is also related to $a$.

How to Check

For every ordered pair $(a, b)$ in $R$, check if $(b, a)$ is also in $R$.

Examples

Symmetric:

• On $A = \{1, 2, 3\}$: $R = \{(1,1), (1,2), (2,1)\}$ (symmetric)
• “=” on real numbers: if $x = y$, then $y = x$ (symmetric)
• “is sibling of” on people (symmetric)

Not Symmetric:

• On $A = \{1, 2\}$: $R = \{(1,2)\}$ ✗ (has $(1,2)$ but not $(2,1)$)
• “≤” on real numbers: $2 \leq 3$ but not $3 \leq 2$ ✗
• “is father of” ✗

---

Anti-Symmetric Relation

Definition

A relation $R$ on set $A$ is anti-symmetric if:

$$\boxed{(a, b) \in R \text{ and } (b, a) \in R \Rightarrow a = b}$$

Different elements cannot be related in both directions.

Examples

Anti-symmetric:

• “≤” on real numbers: if $x \leq y$ and $y \leq x$, then $x = y$ (antisymmetric)
• “divides” on positive integers (antisymmetric)

Not Anti-symmetric:

• On $A = \{1, 2\}$: $R = \{(1,2), (2,1)\}$ ✗ (1 ≠ 2 but both pairs exist)

---

Transitive Relation

Definition

A relation $R$ on set $A$ is transitive if:

$$\boxed{(a, b) \in R \text{ and } (b, c) \in R \Rightarrow (a, c) \in R}$$

If $a$ is related to $b$, and $b$ is related to $c$, then $a$ must be related to $c$.

How to Check

For every chain $a \to b \to c$ in the relation, verify $a \to c$ exists.

Examples

Transitive:

• On $A = \{1, 2, 3\}$: $R = \{(1,2), (2,3), (1,3)\}$ (transitive)
• “≤” on real numbers: if $x \leq y$ and $y \leq z$, then $x \leq z$ (transitive)
• “is ancestor of” (transitive)

Not Transitive:

• On $A = \{1, 2, 3\}$: $R = \{(1,2), (2,3)\}$ ✗ (missing $(1,3)$)
• “is friend of” (friend’s friend may not be your friend) ✗

Interactive Demo: Visualize Relation Properties

Explore different types of relations and their properties graphically.

---

Summary of Properties

Property	Condition	Check
Reflexive	$(a, a) \in R$ for all $a$	All diagonal pairs present
Symmetric	$(a,b) \in R \Rightarrow (b,a) \in R$	Pairs come in symmetric pairs
Anti-symmetric	$(a,b), (b,a) \in R \Rightarrow a = b$	No symmetric pairs for different elements
Transitive	$(a,b), (b,c) \in R \Rightarrow (a,c) \in R$	All chains close

---

Equivalence Relation

Definition

A relation $R$ on set $A$ is an equivalence relation if it is:

$$\boxed{\text{Reflexive + Symmetric + Transitive}}$$

Examples of Equivalence Relations

1. Equality on any set: $x = y$

2. Congruence modulo n on integers: $a \equiv b \pmod{n}$ (same remainder when divided by $n$)

3. Same birthday on people

4. Parallel lines on the set of lines

Example Verification

Claim: “Has same remainder when divided by 3” is an equivalence relation on $\mathbb{Z}$.

Proof:

Let $aRb$ mean “$a - b$ is divisible by 3”.

1. Reflexive: $a - a = 0$ is divisible by 3. (Yes)

2. Symmetric: If $a - b$ is divisible by 3, then $b - a = -(a-b)$ is also divisible by 3. (Yes)

3. Transitive: If $a - b = 3k$ and $b - c = 3m$, then: $a - c = (a - b) + (b - c) = 3k + 3m = 3(k+m)$ is divisible by 3. (Yes)

---

Equivalence Classes

Definition

For an equivalence relation $R$ on $A$, the equivalence class of element $a$ is:

$$[a] = \{x \in A : xRa\}$$

All elements equivalent to $a$.

Example

For “same remainder mod 3” on $\mathbb{Z}$:

• $[0] = \{..., -6, -3, 0, 3, 6, 9, ...\}$ (divisible by 3)
• $[1] = \{..., -5, -2, 1, 4, 7, 10, ...\}$ (remainder 1)
• $[2] = \{..., -4, -1, 2, 5, 8, 11, ...\}$ (remainder 2)

Properties of Equivalence Classes

1. Every element belongs to exactly one equivalence class
2. Two equivalence classes are either identical or disjoint
3. The equivalence classes partition the set $A$

---

Counting Problems

Number of Reflexive Relations

Each of the $n^2 - n$ non-diagonal entries can be 0 or 1:

$$\text{Reflexive relations on } A = 2^{n^2 - n} = 2^{n(n-1)}$$

Number of Symmetric Relations

Choose the upper triangle (including diagonal) freely; lower triangle is determined:

$$\text{Symmetric relations on } A = 2^{\frac{n(n+1)}{2}}$$

Number of Reflexive and Symmetric Relations

$$= 2^{\frac{n(n-1)}{2}}$$

---

Quick Comparison Table

Relation	Reflexive	Symmetric	Transitive	Equivalence
=	Yes	Yes	Yes	Yes
≤	Yes	No	Yes	No
<	No	No	Yes	No
⊥ (perpendicular)	No	Yes	No	No
∥ (parallel)	Yes	Yes	Yes	Yes

---

Practice Problems

1. Check if $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ on $\{1,2,3\}$ is an equivalence relation.

2. On $\mathbb{Z}$, define $aRb$ if $|a - b| \leq 1$. Is $R$ transitive?

3. Find all equivalence classes for “divisible by 4” on $\{1, 2, 3, ..., 12\}$.

---