CS285: Relations - Comprehensive Study Guide

1. Introduction to Binary Relations

Definition: Binary Relation

A binary relation R from a set A to a set B is a subset R ⊆ A × B.

In other words, a binary relation from A to B is a set of ordered pairs where the first element comes from A and the second element comes from B.

Key Point: Relations are MORE GENERAL than functions. A function is a special type of relation where exactly one element of B is related to each element of A.

Notation

• If (a,b) ∈ R, we write: a R b (read as "a is related to b")
• If (a,b) ∉ R, we write: a R̸ b (read as "a is not related to b")
• Alternative phrases: "a relates to b under relation R"

Example 1: Student-Course Relation

Let A = {1, 2, 3} represent students

Let B = {a, b} represent courses

R = {(1,a), (1,b), (2,a), (3,b)}

This means:

Student 1 is registered in courses a and b
Student 2 is registered in course a
Student 3 is registered in course b

Special Relation: Identity Relation

Identity Relation (I_A)

The identity relation on a set A is: I_A = {(a,a) | a ∈ A}

Every element is only related to itself.

Example: Identity Relation

If A = {1, 2, 3, 4}, then:

I_A = {(1,1), (2,2), (3,3), (4,4)}

Ways to Represent Relations

Roster Notation: List of ordered pairs {(1,2), (3,4), ...}
Set Builder Notation: {(a,b) | condition}
Graph/Digraph: Visual representation with dots and arrows
Table/Matrix: Zero-one matrix representation

2. Properties of Relations

Relations on a set A (where R: A → A) can have special properties:

Property 1: Reflexivity

Reflexive Relation

A relation R on A is reflexive if (a,a) ∈ R for every element a ∈ A

In other words: Every element is related to itself.

Irreflexive Relation

A relation R on A is irreflexive if (a,a) ∉ R for every element a ∈ A

In other words: No element is related to itself.

Important: "Irreflexive" ≠ "Not Reflexive"

A relation can be neither reflexive nor irreflexive
Example: R = {(1,2), (2,1), (1,1)} on A = {1,2} is NOT reflexive (missing (2,2)) and NOT irreflexive (has (1,1))

Examples on Integers

R₁ = {(a,b) | a ≤ b} - REFLEXIVE (every number ≤ itself)

R₂ = {(a,b) | a > b} - IRREFLEXIVE (no number > itself)

R₃ = {(a,b) | a = b or a = -b} - REFLEXIVE

R₄ = {(a,b) | a = b} - REFLEXIVE

Property 2: Symmetry

Symmetric Relation

A relation R on A is symmetric if:

(a,b) ∈ R → (b,a) ∈ R for all a, b ∈ A

When (a,b) is present, (b,a) MUST also be present.

Antisymmetric Relation

A relation R on A is antisymmetric if:

(a,b) ∈ R ∧ (b,a) ∈ R → a = b

Alternative: If (a,b) is there with a ≠ b, then (b,a) should NOT be there.

Important: Symmetric and Antisymmetric are NOT opposites!

A relation can have both properties (e.g., R = {(a,b) | a = b})
A relation can have neither property
A relation CANNOT be both symmetric AND antisymmetric if it contains some pair (a,b) where a ≠ b

Examples on Integers

R₁ = {(a,b) | a = b} - SYMMETRIC and ANTISYMMETRIC

R₂ = {(a,b) | a > b} - NOT SYMMETRIC, ANTISYMMETRIC

R₃ = {(a,b) | a = b+1} - NOT SYMMETRIC, ANTISYMMETRIC

Property 3: Transitivity

Transitive Relation

A relation R is transitive if:

(a,b) ∈ R ∧ (b,c) ∈ R → (a,c) ∈ R for all a, b, c

If there's a path from a to b and from b to c, there must be a direct connection from a to c.

Example: Checking Transitivity

A = {1, 2}

R₁ = {(1,1), (1,2), (2,1), (2,2)} - TRANSITIVE

Check: (1,2) and (2,1) are in R₁, and (1,1) is in R₁ ✓

R₂ = {(1,1), (1,2), (2,1)} - NOT TRANSITIVE

Why? (1,2) and (2,1) are in R₂, but (1,1) is missing... wait, it's there!

Actually, we need to check: (2,1) and (1,2) → need (2,2), which is missing ✗

Summary Table

Property	Definition	Visual Check
Reflexive	∀a: (a,a) ∈ R	All diagonal elements in matrix are 1
Irreflexive	∀a: (a,a) ∉ R	All diagonal elements in matrix are 0
Symmetric	(a,b) ∈ R → (b,a) ∈ R	Matrix is symmetric (M = M^T)
Antisymmetric	(a,b) ∈ R ∧ (b,a) ∈ R → a = b	All 1's across diagonal are from 0's
Transitive	(a,b) ∈ R ∧ (b,c) ∈ R → (a,c) ∈ R	Complete all triangles in digraph

3. Representing Relations

Method 1: Zero-One Matrices

Matrix Representation

To represent a relation R by a matrix M_R = [m_ij]:

m_ij = 1 if (a_i, b_j) ∈ R

m_ij = 0 if (a_i, b_j) ∉ R

Example: Matrix Representation

A = {1, 2, 3}, B = {1, 2}

R = {(2,1), (3,1), (3,2)}

Matrix M_R:

	1	2
1	0	0
2	1	0
3	1	1

Identifying Properties from Matrices

Reflexive:

All 1's on the main diagonal (top-left to bottom-right)

Irreflexive:

All 0's on the main diagonal

Symmetric:

Matrix equals its transpose: M = M^T

All 1's are mirrored across the diagonal

Antisymmetric:

If m_ij = 1 and i ≠ j, then m_ji = 0

All 1's across from each other (not on diagonal) must face 0's

Method 2: Directed Graphs (Digraphs)

Digraph Representation

A directed graph G = (V_G, E_G) where:

V_G is the set of vertices (nodes) - represents elements of set A
E_G is the set of edges (arcs) - represents ordered pairs in R
Draw an arrow from vertex a to vertex b if (a,b) ∈ R

Example: Digraph

R = {(1,1), (2,2), (3,3), (4,4), (1,3), (1,2), (1,4), (2,4)}

on set {1, 2, 3, 4}

Visual: Each number has a loop to itself (reflexive), plus arrows from 1 to 2, 3, 4 and from 2 to 4.

Identifying Properties from Digraphs

Reflexive:

Every vertex has a loop (self-edge)

Irreflexive:

No vertex has a loop

Symmetric:

Every edge has a corresponding edge in the opposite direction (bidirectional arrows)

Antisymmetric:

No two distinct vertices have edges in both directions

Transitive:

Whenever there's a path from x to y and y to z, there must be a direct edge from x to z

4. Combining Relations

Operation 1: Union and Intersection

Union (R₁ ∪ R₂):

M_R₁∪R₂ = M_R₁ ∨ M_R₂

Element-wise OR: m_ij = 1 if element is in R₁ OR R₂

Intersection (R₁ ∩ R₂):

M_R₁∩R₂ = M_R₁ ∧ M_R₂

Element-wise AND: m_ij = 1 if element is in R₁ AND R₂

Example: Union and Intersection

A = {1, 2, 3}

R₁ = {(1,1), (2,2), (1,2), (3,1), (2,3), (3,2)}

R₂ = {(1,1), (1,2), (1,3), (1,4)}

R₁ ∪ R₂ = {(1,1), (2,2), (1,2), (3,1), (2,3), (3,2), (1,3), (1,4)}

R₁ ∩ R₂ = {(1,1), (1,2)}

Operation 2: Composition

Composition (S ∘ R):

If R: A → B and S: B → C, then S ∘ R: A → C

(a,c) ∈ S ∘ R if there exists b such that (a,b) ∈ R and (b,c) ∈ S

Matrix: M_S∘R = M_R ⊙ M_S (Boolean product)

Important: M_S∘R = M_R ⊙ M_S ≠ M_S ⊙ M_R

Order matters in composition!

Boolean Product:
Like matrix multiplication, but:
• Use ∨ (OR) instead of + (addition)
• Use ∧ (AND) instead of × (multiplication)

Example: Composition

R = {(1,1), (1,2), (2,5), (3,4)}

S = {(1,6), (2,1), (4,0)}

S ∘ R:

(1,1) in R and (1,6) in S → (1,6) in S∘R
(1,2) in R and (2,1) in S → (1,1) in S∘R
(3,4) in R and (4,0) in S → (3,0) in S∘R

S ∘ R = {(1,6), (1,1), (3,0)}

Operation 3: Powers of Relations

Powers:

R¹ = R

Rⁿ⁺¹ = Rⁿ ∘ R

Matrix: M_Rⁿ = M_R^[n] (Boolean power)

Example: Powers

R = {(1,1), (2,1), (3,2), (4,3)}

R² = R ∘ R = {(1,1), (2,1), (3,1), (4,2)}

R³ = R² ∘ R = {(1,1), (2,1), (3,1), (4,1)}

5. Closure of Relations

Closure Concept:

For any property X, the "X closure" of a set A is the smallest superset of A that has property X.

We add the minimum number of elements to R to make it satisfy the property.

1. Reflexive Closure

Reflexive Closure of R:

Add (a,a) to R for each a ∈ A not already in R

Formula: R ∪ I_A

where I_A = {(a,a) | a ∈ A} is the identity relation

Example: Reflexive Closure

R = {(1,1), (1,2), (2,1), (3,2)} on A = {1, 2, 3}

Missing: (2,2) and (3,3)

Reflexive Closure = {(1,1), (1,2), (2,1), (3,2), (2,2), (3,3)}

2. Symmetric Closure

Symmetric Closure of R:

Add (b,a) to R for each (a,b) in R where (b,a) is not already in R

Formula: R ∪ R^-1

where R^-1 = {(b,a) | (a,b) ∈ R} is the inverse relation

Example: Symmetric Closure

R = {(1,1), (2,2), (1,2), (3,1), (2,3), (3,2)}

Missing reverse pairs: (2,1) and (1,3)

Symmetric Closure = {(1,1), (2,2), (1,2), (3,1), (2,3), (3,2), (2,1), (1,3)}

3. Transitive Closure

Transitive Closure of R:

Repeatedly add (a,c) to R for each (a,b) and (b,c) in R where (a,c) is not already present

Formula: R* = R ∪ R² ∪ R³ ∪ ... ∪ Rⁿ

where n = |A| (size of set A)

Matrix: M_R* = M_R ∨ M_R^[2] ∨ ... ∨ M_R^[n]

Example: Transitive Closure

R = {(1,1), (1,2), (2,1), (3,2)} on A = {1, 2, 3}

R² = R ∘ R = {(1,1), (1,2), (2,1), (2,2), (3,1)}

R³ = R² ∘ R = {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)}

Transitive Closure R* = R ∪ R² ∪ R³

= {(1,1), (1,2), (2,1), (3,2), (2,2), (3,1)}

Summary: Computing Closures

Closure Type	Formula	What to Add
Reflexive	R ∪ I_A	All (a,a) pairs
Symmetric	R ∪ R^-1	Reverse of each pair
Transitive	R ∪ R² ∪ ... ∪ Rⁿ	All paths of length ≥ 2

6. Equivalence Relations

Equivalence Relation:

An equivalence relation on a set A is any binary relation on A that is:

Reflexive
Symmetric
Transitive

Key Concept: Equivalence relations partition a set into groups where elements in each group are "equivalent" to each other.

Example 1: Equivalence on Real Numbers

R = {(a,b) | a - b is an integer} on the set of real numbers

Check Reflexive: a - a = 0, which is an integer ✓

Check Symmetric: If a - b is an integer, then b - a = -(a-b) is also an integer ✓

Check Transitive: If a - b and b - c are integers, then a - c = (a-b) + (b-c) is also an integer ✓

Conclusion: R is an equivalence relation!

Example 2: Congruence Modulo n

R = {(a,b) | a ≡ b (mod n)} - "a congruent to b modulo n"

This means n divides (a - b)

This is an equivalence relation and partitions integers into n equivalence classes:

[0] = {..., -6, -3, 0, 3, 6, ...} (for mod 3)
[1] = {..., -5, -2, 1, 4, 7, ...}
[2] = {..., -4, -1, 2, 5, 8, ...}

Applications of Equivalence Relations

Common Examples:

Equality (=): The most basic equivalence relation
Same age: People with the same age are equivalent
Same birthday: People born on the same day
Congruence modulo n: Numbers with same remainder when divided by n
Similar triangles: Triangles with same angles

Quick Check for Equivalence Relations

Checklist:
☑ Reflexive: (a,a) for all a?
☑ Symmetric: If (a,b) then (b,a)?
☑ Transitive: If (a,b) and (b,c) then (a,c)?

If ALL THREE are YES → Equivalence Relation!

📝 Quick Reference Guide

Property Quick Check

To Check If...	Matrix Check	Graph Check
Reflexive	All 1's on diagonal	Loop at every vertex
Symmetric	M = M^T	All edges bidirectional
Transitive	Check M^[2] ⊆ M	Complete all triangles
Equivalence	Reflexive + Symmetric + Check R² ⊆ R	All three properties

Common Mistakes to Avoid

⚠️ Warning:

Don't confuse "not reflexive" with "irreflexive"
Don't confuse "not symmetric" with "antisymmetric"
Remember: Composition order matters! S ∘ R ≠ R ∘ S
For transitive closure, you may need multiple powers (up to Rⁿ)
Boolean operations: ∨ is OR, ∧ is AND (not regular +, ×)

Formulas to Remember

Key Formulas:
• Reflexive Closure: R ∪ I_A
• Symmetric Closure: R ∪ R^-1
• Transitive Closure: R* = R ∪ R² ∪ R³ ∪ ... ∪ Rⁿ
• Composition: M_S∘R = M_R ⊙ M_S
• Union: M_R₁∪R₂ = M_R₁ ∨ M_R₂
• Intersection: M_R₁∩R₂ = M_R₁ ∧ M_R₂

📋 Table of Contents

1. Introduction to Binary Relations

Notation

Special Relation: Identity Relation

Ways to Represent Relations

2. Properties of Relations

Property 1: Reflexivity

Reflexive Relation

Irreflexive Relation

Property 2: Symmetry

Symmetric Relation

Antisymmetric Relation

Property 3: Transitivity

Transitive Relation

Summary Table

3. Representing Relations

Method 1: Zero-One Matrices

Identifying Properties from Matrices

Reflexive:

Irreflexive:

Symmetric:

Antisymmetric:

Method 2: Directed Graphs (Digraphs)

Identifying Properties from Digraphs

Reflexive:

Irreflexive:

Symmetric:

Antisymmetric:

Transitive:

4. Combining Relations

Operation 1: Union and Intersection

Operation 2: Composition

Operation 3: Powers of Relations

5. Closure of Relations

1. Reflexive Closure

Reflexive Closure of R:

2. Symmetric Closure

Symmetric Closure of R:

3. Transitive Closure

Transitive Closure of R:

Summary: Computing Closures

6. Equivalence Relations

Applications of Equivalence Relations

Common Examples:

Quick Check for Equivalence Relations

📝 Quick Reference Guide

Property Quick Check

Common Mistakes to Avoid

Formulas to Remember