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}.
R₁ = {(1,1), (2,2), (3,3), (1,2)}is reflexive because(1,1),(2,2), and(3,3)are all inR₁.R₂ = {(1,1), (2,2), (1,2)}is not reflexive because(3,3)is missing fromR₂.
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}.
R₁ = {(1,2), (2,1), (3,3)}is symmetric because(1,2)has(2,1)and(3,3)is self-symmetric.R₂ = {(1,2), (2,3)}is not symmetric because(1,2)is inR₂but(2,1)is not, and(2,3)is inR₂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}.
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.
R₂ = {(1,2), (2,3)}is not transitive because(1,2) ∈ R₂and(2,3) ∈ R₂, but(1,3)is missing fromR₂.
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:
- Reflexivity: Is every element related to itself? (
(a,a) ∈ Rfor alla ∈ A) - Symmetry: If
ais related tob, isbrelated toa? (If(a,b) ∈ R, then(b,a) ∈ R) - Transitivity: If
ais related tobandbis related toc, isarelated toc? (If(a,b) ∈ Rand(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:
- Reflexivity: For any
a ∈ Z,a - a = 0, which is an even integer. So,(a, a) ∈ R. Thus,Ris reflexive. - Symmetry: If
(a, b) ∈ R, thena - bis an even integer. This meansa - b = 2kfor some integerk. Thenb - a = -(a - b) = -2k = 2(-k). Since-kis also an integer,b - ais an even integer. So,(b, a) ∈ R. Thus,Ris symmetric. - Transitivity: If
(a, b) ∈ Rand(b, c) ∈ R, thena - bis even andb - cis even. So,a - b = 2kandb - c = 2mfor some integersk, m. Adding these equations:(a - b) + (b - c) = 2k + 2m. This simplifies toa - c = 2(k + m). Sincek + mis an integer,a - cis an even integer. So,(a, c) ∈ R. Thus,Ris transitive. SinceRis 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:
- Every element
a ∈ Abelongs to exactly one equivalence class (due to reflexivity and transitivity). - Any two equivalence classes are either identical or completely disjoint (due to symmetry and transitivity).
- 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 isZ. 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 partitionsZinto 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
- 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
Rhas no pairs(a, b)and(b, c)such thatbis shared, thenRis transitive by default. Similarly, ifRhas no(a, b)pairs wherea ≠ b, it's symmetric. This is a common source of confusion. - "For all" vs. "For some": For reflexivity, it is critical that
(a, a) ∈ Rfor every elementain the setA. If even one(a, a)is missing, the relation is not reflexive. - 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.
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 sectionAll sections of Relations and Functions Course Wiki · Browse more course pages