MathIsimple
DM-11
Course 11

Relations

Study binary relations and their properties, from equivalence relations that partition sets to partial orders that organize elements hierarchically.

Learning Objectives
  • Define and represent binary relations
  • Identify relation properties
  • Understand equivalence relations and classes
  • Define partial and total orders
  • Draw Hasse diagrams
  • Compute closures of relations

1. Binary Relations

Definition 11.1: Binary Relation

A binary relation R from set A to set B is a subset of A×BA \times B.

If (a,b)∈R(a, b) \in R, we write aRbaRb.

Definition 11.2: Relation Properties
  • Reflexive: (a,a)∈R(a, a) \in R for all a∈Aa \in A
  • Symmetric: (a,b)∈R⇒(b,a)∈R(a, b) \in R \Rightarrow (b, a) \in R
  • Antisymmetric: (a,b)∈R∧(b,a)∈R⇒a=b(a, b) \in R \land (b, a) \in R \Rightarrow a = b
  • Transitive: (a,b)∈R∧(b,c)∈R⇒(a,c)∈R(a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R

2. Equivalence Relations

Definition 11.3: Equivalence Relation

A relation R on set A is an equivalence relation if it is reflexive, symmetric, and transitive.

Definition 11.4: Equivalence Class

The equivalence class of element a is:

[a]={b∈A∣aRb}[a] = \{b \in A \mid aRb\}
Theorem 11.1: Partition Theorem

The equivalence classes of an equivalence relation form a partition of the set.

Example: Equivalence Classes of Mod 3
  • [0]={…,−6,−3,0,3,6,…}[0] = \{\ldots, -6, -3, 0, 3, 6, \ldots\}
  • [1]={…,−5,−2,1,4,7,…}[1] = \{\ldots, -5, -2, 1, 4, 7, \ldots\}
  • [2]={…,−4,−1,2,5,8,…}[2] = \{\ldots, -4, -1, 2, 5, 8, \ldots\}

3. Partial Orders

Definition 11.5: Partial Order

A relation R on set A is a partial order if it is reflexive, antisymmetric, and transitive.

A set with a partial order is called a poset.

Example: Common Partial Orders
  • (Z,≤)(\mathbb{Z}, \leq) - integers with ≤
  • (P(S),⊆)(\mathcal{P}(S), \subseteq) - power set with subset relation
  • (Z+,∣)(\mathbb{Z}^+, \mid) - positive integers with "divides"
Definition 11.6: Total Order

A partial order is a total order if every two elements are comparable.

4. Closures

Definition 11.7: Closure

The closure of R with respect to property P is the smallest relation containing R that has property P.

Theorem 11.2: Computing Closures
  • Reflexive closure: Add all (a,a)(a,a)
  • Symmetric closure: Add (b,a)(b,a) for each (a,b)(a,b)
  • Transitive closure: Add pairs connected by paths

Practice Quiz

Relations Quiz
10
Questions
0
Correct
0%
Accuracy
1
A relation R on set A is reflexive if:
Easy
Not attempted
2
A relation R is symmetric if:
Easy
Not attempted
3
Which property does ≤\leq on integers NOT have?
Medium
Not attempted
4
An equivalence relation must be:
Easy
Not attempted
5
A partial order must be:
Medium
Not attempted
6
How many equivalence classes does 'congruence mod 3' partition Z\mathbb{Z} into?
Medium
Not attempted
7
The transitive closure of R adds all pairs (a,c)(a, c) where:
Hard
Not attempted
8
In a Hasse diagram, an edge from aa to bb (with bb above aa) means:
Medium
Not attempted
9
In a lattice, every pair of elements has:
Hard
Not attempted
10
If R is 'is a sibling of' (excluding self), R is:
Hard
Not attempted

Frequently Asked Questions

What's the difference between symmetric and antisymmetric?

Symmetric: If aRb then bRa.

Antisymmetric: If aRb AND bRa, then a = b.

How do equivalence relations differ from partial orders?

Both are reflexive and transitive. Equivalence relations are symmetric; partial orders are antisymmetric.

What are relations used for in CS?

Databases (tables are relations), graphs (edge sets), type systems (subtyping), dependency analysis.