Properties of Relations

Introduction

• Topic: Properties of Relations
• Subject Code: 18CS36
• Presented by: Dr. Madhura, Assistant Professor, Department of Mathematics, Sai Vidya Institute of Technology, Bengaluru.

Properties of Relations

1. Reflexive Relation

• Definition: A relation R on a set A is reflexive if (a, a) ∈ R for every a ∈ A.
• Non-Reflexive: R is non-reflexive if there exists an element a ∈ A such that (a, a) ∉ R.
• Example:
  • Reflexive: "≤", "=", "≥"
  • Non-reflexive: "<", ">"
• Example Set: If A = {1, 2, 3, 4}, the relation R = {(1, 1), (2, 2), (3, 3)} is non-reflexive since (4, 4) does not belong to R.

2. Irreflexive Relation

• Definition: A relation R is irreflexive if (a, a) ∉ R for every a ∈ A.
• Note: Non-reflexive does not imply irreflexive. A relation can be non-reflexive but not irreflexive.

3. Symmetric Relation

• Definition: A relation R on set A is symmetric if for all a, b ∈ A, if (a, b) ∈ R, then (b, a) ∈ R.

4. Asymmetric Relation

• Definition: A relation R is asymmetric if for every a, b ∈ A, if (a, b) ∈ R, then (b, a) ∉ R.

5. Anti-Symmetric Relation

• Definition: A relation R is anti-symmetric if whenever (a, b) ∈ R and (b, a) ∈ R, then a = b.
• Note: Asymmetric and anti-symmetric relations are not the same.

6. Transitive Relation

• Definition: A relation R is transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
• Example: Relations such as "≤" and "≥" are transitive.

7. Equivalence Relation

• Definition: A relation R is an equivalence relation if it is reflexive, symmetric, and transitive.
• Example: The equality relation.

8. Equivalence Classes

• Definition: Given an equivalence relation R on a set A, the equivalence class of an element a ∈ A is the set of all elements that are related to a by R.
• Notation: Usually denoted as [a] or R(a).

9. Partition of a Set

• Definition: A set A can be partitioned into non-empty subsets A1, A2, ..., Ak such that:
  1. A = A1 ∪ A2 ∪ ... ∪ Ak
  2. Ai ∩ Aj = ∅ for i ≠ j.
  • This means that any two subsets are disjoint.

Problem Examples

Example Problem 1

• Given A = {1, 2, 3, 4} and R = {(1, 3), (1, 1), (3, 1), (2, 2), (3, 4), (4, 4)}
• Task: Determine if R is reflexive, irreflexive, symmetric, anti-symmetric, or transitive.

Example Problem 2

• Given A = {1, 2, 3, 4} and R defined by R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 3), (3, 3), (4, 4)}
• Task: Verify if R is an equivalence relation.

Example Problem 3

• Given a fixed integer n > 1, prove the relation "congruent modulo n" is an equivalence relation on the set of all integers.

Example Problem 4

• Given a relation on A = {1, 2, 3, 4} to determine the partition induced by a relation R.

Summary

The lecture covered various properties of relations including reflexive, irreflexive, symmetric, asymmetric, anti-symmetric, transitive relations, equivalence relations, equivalence classes, and the concept of partitioning a set. Examples and definitions were provided to clarify each concept.