From the free course Relations and Functions Course Wiki on Lykke

1.2 Types of Relations

Key concepts: Relation in a set A · Empty Relation · Universal Relation · Trivial Relations · Reflexive Relation · Symmetric Relation · Transitive Relation · Equivalence Relation · Equivalence Classes

This section systematically defines and illustrates various types of relations, starting with empty and universal relations. It then introduces the core properties of reflexive, symmetric, and transitive relations, which are essential for understanding equivalence relations. The concept of equivalence classes, which partition a set, is also explained with examples, followed by problems to classify relations.

1.2 Types of Relations

The study of relations forms a cornerstone of discrete mathematics, providing a formal framework to describe connections and associations between elements within sets. Building upon the foundational concepts of relations and functions introduced in Class XI, this section deeply explores the various classifications of relations defined within a single set. Understanding these types is crucial for advanced topics in algebra, logic, and computer science, particularly in areas like database design, graph theory, and the construction of abstract mathematical structures.

Relation in a Set A

What it is

A relation R in a set A is formally defined as any subset of the Cartesian product A × A. This means that R is a collection of ordered pairs (a, b) where both a and b are elements of A. When an ordered pair (a, b) belongs to R, we say that a is related to b by R, often denoted as a R b. This is a specific case of the more general definition of a relation from a set A to a set B, where R ⊆ A × B. Here, the domain and codomain are the same set A.

Why it matters

Defining relations within a single set A allows us to analyze intrinsic properties and structures within that set. It's the basis for classifying elements based on shared characteristics or connections, leading to powerful concepts like equivalence relations that partition a set, or order relations that structure it. This self-referential nature is fundamental to many mathematical and computational models.

How it works

To define a relation R in a set A, one specifies a rule or condition that elements a, b ∈ A must satisfy for the pair (a, b) to be included in R. For instance, if A is the set of integers, a relation could be "is less than or equal to" (≤), where R = {(a, b) ∈ A × A : a ≤ b}.

Concrete example

Let A = {1, 2, 3}. Consider the relation R defined as "is less than" on A. R = {(a, b) ∈ A × A : a < b}. The elements of R would be: {(1, 2), (1, 3), (2, 3)}. Here, 1 R 2 and 1 R 3, but 3 R 1 is false.

Common pitfalls

A common misconception is to confuse a relation in a set A with a function. While every function is a relation, not every relation is a function. In a relation, an element a can be related to multiple elements b, or to no elements at all, which is not permitted for functions. Also, ensure both elements of the ordered pair (a,b) truly belong to the specified set A.

Empty Relation

What it is

The Empty Relation (or Void Relation) on a set A is the relation R where no element of A is related to any element of A. Mathematically, it is defined as R = φ ⊂ A × A, where φ represents the empty set.

Why it matters

The empty relation serves as a boundary case in the spectrum of possible relations. While seemingly trivial, it is a valid relation by definition and is important for the completeness of mathematical theory. It represents a scenario where no connections exist between elements.

How it works

To construct an empty relation, one simply defines a condition that can never be met by any pair of elements from the set.

Concrete example

Let A = {1, 2, 3}. Consider the relation R = {(a, b) ∈ A × A : a + b = 7}. Since the maximum sum of any two elements from A is 3 + 3 = 6, there are no pairs (a, b) in A × A such that a + b = 7. Therefore, R = φ, which is the empty relation.

Universal Relation

What it is

The Universal Relation on a set A is the relation R where every element of A is related to every element of A. Mathematically, it is defined as R = A × A.

Why it matters

Like the empty relation, the universal relation is another boundary case, representing the maximum possible connectivity within a set. It signifies a scenario where all possible connections exist, which can be useful in certain theoretical contexts or as a baseline for comparison.

How it works

To construct a universal relation, one defines a condition that is always true for any pair of elements from the set.

Concrete example

Let A = {1, 2, 3}. Consider the relation R = {(a, b) ∈ A × A : a + b > 0}. Since all elements in A are positive, the sum of any two elements will always be greater than 0. Thus, R = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}, which is A × A, the universal relation.

Trivial Relations

The Empty Relation and the Universal Relation are collectively known as Trivial Relations because they represent the extreme, and often least interesting, cases of relatedness within a set. They serve as fundamental examples but typically lack the intricate structure found in other types of relations.

Reflexive Relation

What it is

A relation R in a set A is called reflexive if every element of A is related to itself. Formally, for every a ∈ A, the ordered pair (a, a) must belong to R. That is, (a, a) ∈ R for all a ∈ A.

Why it matters

Reflexivity signifies self-identity or self-connection. Many common relations, such as "is equal to" (=), "is a subset of" (⊆), or "is less than or equal to" (≤), are reflexive. This property is essential for defining equivalence relations and partial orderings, which are ubiquitous in mathematics and computer science.

How it works

To check if a relation R is reflexive, one must verify that for every element a in the set A, the pair (a, a) is present in R. If even one such pair is missing, the relation is not reflexive.

Concrete example

Let A = {1, 2, 3}.

  1. R₁ = {(1,1), (2,2), (3,3), (1,2)} is reflexive because (1,1), (2,2), and (3,3) are all in R₁.
  2. R₂ = {(1,1), (2,2), (1,2)} is not reflexive because (3,3) is missing from R₂.

Common pitfalls

The most common mistake is forgetting the "for all a ∈ A" clause. A relation might contain some (a,a) pairs but still not be reflexive if it doesn't contain all of them for every element in the set A.

Symmetric Relation

What it is

A relation R in a set A is called symmetric if whenever a is related to b, then b is also related to a. Formally, if (a, b) ∈ R, then (b, a) must also belong to R, for all a, b ∈ A.

Why it matters

Symmetry implies a bidirectional relationship or mutual connection. Relations like "is a sibling of," "is equal to," or "is connected to" (in an undirected graph) are symmetric. This property is crucial for understanding undirected graphs and defining equivalence relations.

How it works

To check for symmetry, for every pair (a, b) found in R where a ≠ b, you must ensure that its reverse pair (b, a) is also in R. If (a, b) ∈ R but (b, a) ∉ R, the relation is not symmetric. Note that (a, a) pairs do not affect symmetry, as (a, a) is its own reverse.

Concrete example

Let A = {1, 2, 3}.

  1. R₁ = {(1,2), (2,1), (3,3)} is symmetric because (1,2) has (2,1) and (3,3) is self-symmetric.
  2. R₂ = {(1,2), (2,3)} is not symmetric because (1,2) is in R₂ but (2,1) is not, and (2,3) is in R₂ but (3,2) is not.

Common pitfalls

Confusing symmetry with reflexivity. A relation can be symmetric without being reflexive (e.g., "is a sibling of" where no one is their own sibling), and vice-versa. Also, remember that if a pair (a,b) is not in R, then there's no requirement for (b,a) to be in R for symmetry to hold.

Transitive Relation

What it is

A relation R in a set A is called transitive if whenever a is related to b and b is related to c, then a is also related to c. Formally, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) must also belong to R, for all a, b, c ∈ A.

Why it matters

Transitivity represents a chain-like property or a "transfer" of the relation across elements. Relations like "is less than" (<), "is a subset of" (⊆), or "is an ancestor of" are transitive. This property is fundamental to order relations and equivalence relations, allowing us to infer indirect connections.

How it works

To check for transitivity, identify all pairs (a, b) and (b, c) in R where the second element of the first pair matches the first element of the second pair. For each such "chain," verify that the pair (a, c) is also in R. If even one such (a, c) is missing, the relation is not transitive.

Concrete example

Let A = {1, 2, 3}.

  1. R₁ = {(1,2), (2,3), (1,3), (1,1)} is transitive.
    • (1,2) ∈ R₁ and (2,3) ∈ R₁ implies (1,3) ∈ R₁ (which it is).
    • (1,1) doesn't form a chain that would violate transitivity.
  2. R₂ = {(1,2), (2,3)} is not transitive because (1,2) ∈ R₂ and (2,3) ∈ R₂, but (1,3) is missing from R₂.

Common pitfalls

The "if" condition for transitivity (and symmetry) is crucial. If there are no pairs (a, b) and (b, c) in R that form a chain, then the relation is vacuously transitive for those specific a, b, c. This means a relation with very few elements can often be transitive by default. Also, remember that a, b, c do not have to be distinct.

Table: Properties of Relations

Property Definition Example (on A={1,2,3}) Non-Example (on A={1,2,3})
Reflexive (a,a) ∈ R for all a ∈ A {(1,1), (2,2), (3,3), (1,2)} {(1,1), (1,2)} (missing (2,2), (3,3))
Symmetric If (a,b) ∈ R, then (b,a) ∈ R {(1,2), (2,1), (3,3)} {(1,2)} (missing (2,1))
Transitive If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R {(1,2), (2,3), (1,3), (1,1)} {(1,2), (2,3)} (missing (1,3))

Equivalence Relation

What it is

A relation R in a set A is called an Equivalence Relation if it is simultaneously reflexive, symmetric, and transitive.

Why it matters

Equivalence relations are profoundly important because they formalize the concept of "sameness" or "being equivalent." They partition a set into disjoint, non-overlapping subsets called equivalence classes, where all elements within a class are considered equivalent to each other under the relation. This concept is foundational in abstract algebra (e.g., quotient groups, rings), topology, and computer science (e.g., state equivalence in automata, data clustering).

How it works

To verify if a relation is an equivalence relation, one must systematically check all three properties:

  1. Reflexivity: Is every element related to itself? ((a,a) ∈ R for all a ∈ A)
  2. Symmetry: If a is related to b, is b related to a? (If (a,b) ∈ R, then (b,a) ∈ R)
  3. Transitivity: If a is related to b and b is related to c, is a related to c? (If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R) If all three conditions hold, the relation is an equivalence relation.

Concrete example

Let A be the set of all integers, Z. Consider the relation R = {(a, b) ∈ Z × Z : a - b is an even integer}. Let's check the properties:

  1. Reflexivity: For any a ∈ Z, a - a = 0, which is an even integer. So, (a, a) ∈ R. Thus, R is reflexive.
  2. Symmetry: If (a, b) ∈ R, then a - b is an even integer. This means a - b = 2k for some integer k. Then b - a = -(a - b) = -2k = 2(-k). Since -k is also an integer, b - a is an even integer. So, (b, a) ∈ R. Thus, R is symmetric.
  3. Transitivity: If (a, b) ∈ R and (b, c) ∈ R, then a - b is even and b - c is even. So, a - b = 2k and b - c = 2m for some integers k, m. Adding these equations: (a - b) + (b - c) = 2k + 2m. This simplifies to a - c = 2(k + m). Since k + m is an integer, a - c is an even integer. So, (a, c) ∈ R. Thus, R is transitive. Since R is reflexive, symmetric, and transitive, it is an equivalence relation.

Equivalence Classes

What it is

For an equivalence relation R on a set A and any element a ∈ A, the equivalence class of a, denoted [a], is the set of all elements x ∈ A that are related to a by R. Formally, [a] = {x ∈ A : (x, a) ∈ R}.

Why it matters

Equivalence classes provide a concrete way to visualize how an equivalence relation partitions a set. They demonstrate that the set A can be broken down into a collection of disjoint, non-empty subsets, where each element of A belongs to exactly one such subset. This partitioning is fundamental to constructing quotient sets and understanding modular arithmetic.

How it works

The properties of an equivalence relation guarantee that:

  1. Every element a ∈ A belongs to exactly one equivalence class (due to reflexivity and transitivity).
  2. Any two equivalence classes are either identical or completely disjoint (due to symmetry and transitivity).
  3. The union of all distinct equivalence classes equals the original set A.

Concrete example

Continuing with the equivalence relation R = {(a, b) ∈ Z × Z : a - b is an even integer} on the set of integers Z. Let's find the equivalence classes:

  • Equivalence class of 0: [0] = {x ∈ Z : x - 0 is an even integer} = {x ∈ Z : x is an even integer} = {..., -4, -2, 0, 2, 4, ...}. This is the set of all even integers.
  • Equivalence class of 1: [1] = {x ∈ Z : x - 1 is an even integer} = {x ∈ Z : x is an odd integer} = {..., -3, -1, 1, 3, 5, ...}. This is the set of all odd integers. Notice that [0] and [1] are disjoint, and their union is Z. Any other integer will fall into either [0] or [1]. For example, [2] would be {x ∈ Z : x - 2 is an even integer}, which is the same as [0]. Thus, the equivalence relation partitions Z into two distinct equivalence classes: the set of even integers and the set of odd integers.

Table: Real-world Applications of Relation Types

Relation Type Real-world Application Description
Reflexive "is equal to" (=) Any number is equal to itself.
"is a subset of" (⊆) Any set is a subset of itself.
Symmetric "is a sibling of" If Person A is a sibling of Person B, then Person B is a sibling of Person A.
"is connected to" (in a social network) If User A is connected to User B, then User B is connected to User A (e.g., Facebook friends).
Transitive "is less than" (<) If a < b and b < c, then a < c.
"is an ancestor of" If A is an ancestor of B, and B is an ancestor of C, then A is an ancestor of C.
Equivalence "has the same birthday as" Partitions people into 365 (or 366) equivalence classes based on their birth date.
"is congruent to" (modulo n) If a ≡ b (mod n), b ≡ c (mod n), then a ≡ c (mod n). Partitions integers into n remainder classes.

Common Pitfalls and Misconceptions

  1. Vacuously True Properties: Transitivity and symmetry can be "vacuously true" if the premise of their conditional statement is never met. For example, if a relation R has no pairs (a, b) and (b, c) such that b is shared, then R is transitive by default. Similarly, if R has no (a, b) pairs where a ≠ b, it's symmetric. This is a common source of confusion.
  2. "For all" vs. "For some": For reflexivity, it is critical that (a, a) ∈ R for every element a in the set A. If even one (a, a) is missing, the relation is not reflexive.
  3. Distinguishing Relation Types: A single relation can possess multiple properties or none at all. For example, the "less than or equal to" (≤) relation on integers is reflexive and transitive but not symmetric. The "is a sibling of" relation is symmetric but neither reflexive nor transitive. Exercise 1.1 from the source material (Lemh1An) provides excellent examples of relations exhibiting different combinations of these properties, reinforcing the need for careful verification of each.
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 1
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 1
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 2
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 2
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 3
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 3

Source Materials

Study Relations and Functions Course Wiki on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Relations and Functions Course Wiki · Browse more course pages

1.2 Types of Relations — Relations and Functions Course Wiki | Lykke