Types of Relation

Definition

A relation from set $A$ to set $B$ is any subset of the Cartesian product $A \times B$.
If $R$ is a relation from $A$ to $B$, then:

$$R \subseteq A \times B$$

If $(a,b) \in R$, then we say that $a$ is related to $b$ by $R$, written as $aRb$.

When the relation is defined on a single set $A$, it is called a relation on $A$, and then:

$$R \subseteq A \times A$$

Relations are classified into different types based on the way elements are connected and on whether certain properties hold.

Main Content

1. Basic Types of Relations

Empty relation and universal relation

The empty relation contains no ordered pairs at all. If $A \neq \emptyset$, then the empty relation on $A$ is: $$R = \emptyset$$ The universal relation contains every possible ordered pair in $A \times A$. If $A = \{1,2\}$, then the universal relation is: $$R = \{(1,1),(1,2),(2,1),(2,2)\}$$

Identity relation and inverse relation

The identity relation on a set $A$ relates every element only to itself: $$I_A = \{(a,a) : a \in A\}$$ The inverse relation $R^{-1}$ reverses every ordered pair in $R$. If $(a,b) \in R$, then $(b,a) \in R^{-1}$.
Example: If $R = \{(1,2),(3,4)\}$, then $$R^{-1} = \{(2,1),(4,3)\}$$

These basic types help in understanding how relations are formed and manipulated. They are the building blocks of more advanced relation properties.

2. Special Properties of Relations

Reflexive, symmetric, and transitive relations

These are the most important properties used to classify relations.

• A relation $R$ on $A$ is reflexive if every element is related to itself: $$(a,a) \in R \text{ for all } a \in A$$

• It is symmetric if whenever $(a,b) \in R$, then $(b,a) \in R$.

• It is transitive if whenever $(a,b) \in R$ and $(b,c) \in R$, then $(a,c) \in R$.

Example: On the set of integers, the relation “is equal to” is reflexive, symmetric, and transitive.

Antisymmetric and irreflexive relations

• A relation is antisymmetric if: $$(a,b) \in R \text{ and } (b,a) \in R \Rightarrow a=b$$ Example: “$\leq$” on numbers is antisymmetric.

• A relation is irreflexive if no element is related to itself: $$(a,a) \notin R \text{ for all } a \in A$$ Example: “$<$” on integers is irreflexive.

These properties are fundamental because they determine whether a relation can be used to build equivalence classes, partial orders, or other mathematical structures.

3. Major Classifications of Relations

Equivalence relation

A relation is an equivalence relation if it is reflexive, symmetric, and transitive all at once.
Example: “has the same remainder when divided by 3” on integers is an equivalence relation.
If $a \equiv b \pmod{3}$, then:

• $a$ is equivalent to itself,
• if $a$ is related to $b$, then $b$ is related to $a$,
• if $a$ is related to $b$ and $b$ to $c$, then $a$ is related to $c$.

Equivalence relations divide a set into equivalence classes. For example, integers can be partitioned into classes based on remainder modulo 3:

• $\{\dots,-3,0,3,6,\dots\}$
• $\{\dots,-2,1,4,7,\dots\}$
• $\{\dots,-1,2,5,8,\dots\}$

Partial order relation

A relation is a partial order if it is reflexive, antisymmetric, and transitive.
Example: “$\subseteq$” on the power set of a set is a partial order.
Another common example is “$\leq$” on real numbers.

In a partial order, not every pair must be comparable. For example, if $A = \{1,2,3\}$, then under the subset relation, $\{1\}$ and $\{2\}$ are not comparable because neither is a subset of the other.

Partial orders are often shown using Hasse diagrams, which remove unnecessary arrows and self-loops to display the structure clearly.

Total order relation

A total order (or linear order) is a partial order in which every pair of elements is comparable.
Example: The relation “$\leq$” on integers is a total order because for any $a$ and $b$, either $a \leq b$ or $b \leq a$.

Total orders are important in arranging items in a complete sequence, such as sorting numbers, ranking students, or ordering events in time.

Working / Process

1. Identify the set and the relation

• First, determine the set $A$ or the sets $A$ and $B$.
• Write the relation as a collection of ordered pairs or as a rule.
• Example: On $A=\{1,2,3\}$, let $R=\{(1,1),(1,2),(2,2),(3,3)\}$.

2. Check the required properties

• Test whether the relation is reflexive, symmetric, transitive, antisymmetric, or irreflexive.
• Use definitions carefully:
  • Reflexive: all $(a,a)$ must be present.
  • Symmetric: every pair must have its reverse.
  • Transitive: chains must imply the shortcut pair.
• For example, if $(1,2)$ and $(2,3)$ are in $R$, then $(1,3)$ must also be in $R$ for transitivity.

3. Classify the relation

• If the relation satisfies reflexive, symmetric, and transitive, classify it as an equivalence relation.
• If it satisfies reflexive, antisymmetric, and transitive, classify it as a partial order.
• If every pair is comparable under a partial order, classify it as a total order.
• If none of these conditions fit, describe it as a general relation or note the exact properties it satisfies.

Advantages / Applications

Organizing mathematical structures

Types of relations help classify sets into meaningful structures like equivalence classes and ordered sets, which are foundational in higher mathematics.

Computer science and data modeling

Relations are used in databases, graph theory, programming, and algorithms. For example, relational databases store data using relations, and graph edges represent relations between vertices.

Problem solving and theorem proving

In proofs, identifying whether a relation is reflexive, symmetric, transitive, or antisymmetric helps establish the correct type of structure and supports rigorous reasoning.

Summary

• Relations describe how elements of sets are connected using ordered pairs.
• Different types of relations are classified by properties such as reflexive, symmetric, transitive, antisymmetric, and irreflexive.
• Special types like equivalence relations, partial orders, and total orders are extremely important in mathematics and computer science.
• Equivalence relations group elements into classes, while order relations arrange elements systematically.