PGDDSA Study · Semester 1

Core Titles

Key headlines and terms for quick recall

Relation — subset of $A \times B$
Properties: reflexive, symmetric, transitive, antisymmetric
Equivalence relation = reflex + sym + trans
Equivalence class $[a] = \{x : x \sim a\}$
Partition of a set
Correspondence: equivalence relations ↔ partitions

Basic Idea

What it is, why it matters, how it works

What is a relation?

A binary relation $R$ on a set $A$ is a subset of $A \times A$ . We write $a R b$ when $(a,b) \in R$ .

Three key properties

Reflexive: $a R a$ for every $a$
Symmetric: $a R b \implies b R a$
Transitive: $a R b \text{ and } b R c \implies a R c$
Antisymmetric (for partial orders): $a R b \text{ and } b R a \implies a = b$

Equivalence relation

A relation that is reflexive + symmetric + transitive. It groups elements that are "the same in some sense".

Examples: equality, congruence mod $n$ , having the same birthday.

Equivalence classes

For $a \in A$ , the class is $[a] = \{x \in A : x \sim a\}$ .

Key theorem. Equivalence classes either coincide or are disjoint, and together they cover $A$ — i.e., they form a partition.

Partition ↔ Equivalence relation

Every partition $\{A_1, A_2, \dots\}$ defines an equivalence: $a \sim b$ iff they lie in the same block. And every equivalence relation produces a partition via its classes. This is a bijective correspondence.

Why this matters in Data Science

Clustering = partitioning data. Equality of features, hash bucketing, deduplication, "group by" operations — all are equivalence relations under the hood.

Mind Map

Visual structure of the concept

RELATIONS
├── Definition: R ⊆ A × A
├── Properties
│   ├── Reflexive  aRa
│   ├── Symmetric  aRb ⇒ bRa
│   ├── Transitive aRb ∧ bRc ⇒ aRc
│   └── Antisymmetric (for posets)
├── EQUIVALENCE RELATION (R + S + T)
│   ├── Equivalence class [a]
│   ├── Classes are disjoint or equal
│   └── Quotient set A/~
└── PARTITION
    ├── Blocks cover A
    ├── Pairwise disjoint
    └── ↔ equivalence relation

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. Define an equivalence relation. A binary relation on $A$ that is reflexive, symmetric and transitive.

Q2. Give an example of a relation that is symmetric but not transitive. On $\{1,2,3\}$ : $R = \{(1,2),(2,1),(2,3),(3,2)\}$ . Symmetric, but $1R2$ and $2R3$ don't give $1R3$ .

Q3. What is an equivalence class? For $a \in A$ under equivalence $\sim$ , the class $[a] = \{x \in A : x \sim a\}$ .

Q4. Define a partition of a set $A$ . A collection of non-empty, pairwise-disjoint subsets of $A$ whose union is $A$ .

Part B (20 marks)

Q. Show that the equivalence classes of an equivalence relation form a partition. Verify with $\sim$ on $\mathbb{Z}$ defined by $a \sim b$ iff $a - b$ is divisible by 5.

Theorem. Let $\sim$ be an equivalence on $A$ . Then the classes $\{[a] : a \in A\}$ form a partition.

Proof.

Non-empty: By reflexivity, $a \in [a]$ , so every class is non-empty.
Cover: Every $a \in A$ lies in $[a]$ , so $\bigcup_{a \in A} [a] = A$ .
Disjoint or equal: Suppose $[a] \cap [b] \neq \emptyset$ , and pick $c$ in both. Then $c \sim a$ and $c \sim b$ . By symmetry $a \sim c$ , and by transitivity $a \sim b$ . Take any $x \in [a]$ : $x \sim a \sim b \Rightarrow x \in [b]$ . Symmetrically $[b] \subseteq [a]$ . Hence $[a] = [b]$ . ∎

Verification on $\mathbb{Z}$ , congruence mod 5.

Reflexive: $a - a = 0$ , divisible by 5. ✓
Symmetric: if $5 \mid (a-b)$ then $5 \mid (b-a)$ . ✓
Transitive: $5 \mid (a-b)$ and $5 \mid (b-c) \Rightarrow 5 \mid (a-c)$ . ✓

The five classes are $[0], [1], [2], [3], [4]$ — the residue classes mod 5 — and they partition $\mathbb{Z}$ .

Relations, Equivalence Relations and Partitions