Relations: Reflexive, Symmetric, Transitive, and Antisymmetric

Relations: Reflexive, Symmetric, Transitive, and Antisymmetric

A relation on a set $A$ is a subset of the Cartesian product $A \times A$, which means it is a set of ordered pairs of elements from $A$. For example, a relation $R$ on a set $A$ consists of pairs $(a, b)$, where both $a$ and $b$ belong to the set $A$.

There are specific properties that a relation can have. These properties are crucial in understanding the nature of relations in mathematics and computer science, especially in set theory and graph theory.

The four main properties that a relation can possess are reflexivity, symmetry, transitivity, and antisymmetry. Below is a detailed explanation of each property:

---

1. Reflexive Relation

A relation $R$ on a set $A$ is said to be reflexive if every element in $A$ is related to itself. In other words, for all $a \in A$, the pair $(a, a)$ must be in $R$.

Formal Definition:

$$\forall a \in A, (a, a) \in R$$

Example:

Let $A = \{1, 2, 3\}$ and let $R = \{(1, 1), (2, 2), (3, 3)\}$. This relation is reflexive because every element in $A$ is related to itself.

Non-Example:

If $A = \{1, 2, 3\}$ and $R = \{(1, 2), (2, 3)\}$, then the relation is not reflexive, because no element in $A$ is related to itself (e.g., $(1, 1) \notin R$).

---

2. Symmetric Relation

A relation $R$ on a set $A$ is symmetric if for all $a, b \in A$, whenever $(a, b) \in R$, it follows that $(b, a) \in R$. In other words, if $a$ is related to $b$, then $b$ must also be related to $a$.

Formal Definition:

$$\forall a, b \in A, \text{ if } (a, b) \in R \text{, then } (b, a) \in R$$

Example:

Let $A = \{1, 2, 3\}$ and $R = \{(1, 2), (2, 1), (2, 3), (3, 2)\}$. This relation is symmetric because if $(1, 2) \in R$, then $(2, 1) \in R$, and similarly for the other pairs.

Non-Example:

If $A = \{1, 2, 3\}$ and $R = \{(1, 2), (2, 3)\}$, the relation is not symmetric, because $(2, 1) \notin R$ and $(3, 2) \notin R$.

---

3. Transitive Relation

A relation $R$ on a set $A$ is transitive if for all $a, b, c \in A$, whenever $(a, b) \in R$ and $(b, c) \in R$, it follows that $(a, c) \in R$. In other words, if $a$ is related to $b$ and $b$ is related to $c$, then $a$ must also be related to $c$.

Formal Definition:

$$\forall a, b, c \in A, \text{ if } (a, b) \in R \text{ and } (b, c) \in R, \text{ then } (a, c) \in R$$

Example:

Let $A = \{1, 2, 3\}$ and $R = \{(1, 2), (2, 3), (1, 3)\}$. This relation is transitive because:

• $(1, 2) \in R$ and $(2, 3) \in R$, so $(1, 3) \in R$, which is true.

Non-Example:

If $A = \{1, 2, 3\}$ and $R = \{(1, 2), (2, 3)\}$, the relation is not transitive, because:

• $(1, 2) \in R$ and $(2, 3) \in R$, but $(1, 3) \notin R$, which violates the transitive property.

---

4. Antisymmetric Relation

A relation $R$ on a set $A$ is antisymmetric if for all $a, b \in A$, whenever $(a, b) \in R$ and $(b, a) \in R$, it follows that $a = b$. In other words, if both $a$ is related to $b$ and $b$ is related to $a$, then $a$ and $b$ must be the same element.

Formal Definition:

$$\forall a, b \in A, \text{ if } (a, b) \in R \text{ and } (b, a) \in R, \text{ then } a = b$$

Example:

Let $A = \{1, 2, 3\}$ and $R = \{(1, 2), (2, 1), (3, 3)\}$. This relation is antisymmetric because the only pair $(a, b)$ and $(b, a)$ that satisfies the condition is $(1, 2)$ and $(2, 1)$, but since these pairs are distinct, antisymmetry holds.

Non-Example:

If $A = \{1, 2, 3\}$ and $R = \{(1, 2), (2, 1), (2, 2)\}$, the relation is not antisymmetric because both $(1, 2)$ and $(2, 1)$ are in $R$, but $1 \neq 2$, which violates antisymmetry.

---

Summary of Properties

Property	Definition	Example	Non-Example
Reflexive	$\forall a \in A, (a, a) \in R$	$R = \{(1, 1), (2, 2), (3, 3)\}$ for $A = \{1, 2, 3\}$	$R = \{(1, 2), (2, 3)\}$ for $A = \{1, 2, 3\}$
Symmetric	$\forall a, b \in A, \text{ if } (a, b) \in R, \text{ then } (b, a) \in R$	$R = \{(1, 2), (2, 1), (2, 3), (3, 2)\}$ for $A = \{1, 2, 3\}$	$R = \{(1, 2), (2, 3)\}$ for $A = \{1, 2, 3\}$
Transitive	$\forall a, b, c \in A, \text{ if } (a, b) \in R \text{ and } (b, c) \in R, \text{ then } (a, c) \in R$	$R = \{(1, 2), (2, 3), (1, 3)\}$ for $A = \{1, 2, 3\}$	$R = \{(1, 2), (2, 3)\}$ for $A = \{1, 2, 3\}$
Antisymmetric	$\forall a, b \in A, \text{ if } (a, b) \in R \text{ and } (b, a) \in R, \text{ then } a = b$	$R = \{(1, 2), (2, 1), (3, 3)\}$ for $A = \{1, 2, 3\}$	$R = \{(1, 2), (2, 1), (2, 2)\}$ for $A = \{1, 2, 3\}$

---

Conclusion

These four properties—reflexive, symmetric, transitive, and antisymmetric—are used to classify and analyze relations on sets. They provide a foundation for understanding the structure of relations and are essential concepts in areas such as set theory, database theory, graph theory, and logic.