A relation on a set is a subset of its Cartesian product. The important ones are equivalence relations (reflexive + symmetric + transitive), which partition a set into non-overlapping classes. Every partition defines an equivalence relation, and every equivalence relation defines a partition.
Properties of relations
Reflexive: a ~ a for all a. Symmetric: a ~ b implies b ~ a. Transitive: a ~ b and b ~ c implies a ~ c. An equivalence relation has all three.
Scheme
; Congruence mod 3 is an equivalence relation.; a ~ b iff 3 divides (a - b).
(define (related? a b) (= 0 (modulo (- a b) 3)))
; Reflexive: a ~ a
(display "7 ~ 7? ") (display (related? 77)) (newline)
; Symmetric: 7 ~ 4 and 4 ~ 7
(display "7 ~ 4? ") (display (related? 74)) (newline)
(display "4 ~ 7? ") (display (related? 47)) (newline)
; Transitive: 7 ~ 4 and 4 ~ 1 implies 7 ~ 1
(display "4 ~ 1? ") (display (related? 41)) (newline)
(display "7 ~ 1? ") (display (related? 71)) (newline)
; Not related: 7 and 5 differ by 2, not divisible by 3
(display "7 ~ 5? ") (display (related? 75))
Python
# Congruence mod 3def related(a, b):
return (a - b) % 3 == 0# Check all three propertiesprint(f"Reflexive: 7~7 = {related(7,7)}")
print(f"Symmetric: 7~4 = {related(7,4)}, 4~7 = {related(4,7)}")
print(f"Transitive: 7~4={related(7,4)}, 4~1={related(4,1)}, 7~1={related(7,1)}")
Equivalence classes
The equivalence class of a is the set of all elements related to a: [a] = all x in S such that x ~ a. Equivalence classes are either identical or disjoint. They partition the set into non-overlapping groups.
Scheme
; Equivalence classes of congruence mod 3 on {0,...,11}
(define (class-of a universe)
(define (related? x) (= 0 (modulo (- x a) 3)))
(define (go lst)
(cond ((null? lst) (list))
((related? (car lst)) (cons (car lst) (go (cdr lst))))
(else (go (cdr lst)))))
(go universe))
(define U (list 01234567891011))
(display "[0] = ") (display (class-of 0 U)) (newline)
(display "[1] = ") (display (class-of 1 U)) (newline)
(display "[2] = ") (display (class-of 2 U)) (newline)
; Three classes, covering all of {0,...,11} with no overlaps.
(display "[3] = ") (display (class-of 3 U))
; [3] = [0] — same class.
Partitions
A partition of set S is a collection of non-empty, pairwise disjoint subsets whose union is S. The fundamental theorem: equivalence relations and partitions are two views of the same thing. Given a partition, define a ~ b iff they are in the same block. Given an equivalence relation, the classes form a partition.
Scheme
; From partition to equivalence relation and back.; Partition of {1,...,6}: {{1,4}, {2,5}, {3,6}}
(define blocks (list (list 14) (list 25) (list 36)))
(define (member? x s)
(cond ((null? s) #f)
((= x (car s)) #t)
(else (member? x (cdr s)))))
(define (find-block x)
(define (go bs)
(cond ((null? bs) (list))
((member? x (car bs)) (car bs))
(else (go (cdr bs)))))
(go blocks))
(define (equiv? a b)
(equal? (find-block a) (find-block b)))
(display "1 ~ 4? ") (display (equiv? 14)) (newline)
(display "1 ~ 2? ") (display (equiv? 12)) (newline)
(display "2 ~ 5? ") (display (equiv? 25)) (newline)
(display "3 ~ 6? ") (display (equiv? 36))
A partial order is reflexive, antisymmetric (a ~ b and b ~ a implies a = b), and transitive. The divisibility relation on positive integers is a partial order. Unlike equivalence relations, partial orders have a direction: a divides b does not mean b divides a.
Scheme
; Divisibility as a partial order on {1,...,12}
(define (divides? a b) (= 0 (modulo b a)))
; Reflexive: a | a
(display "6|6? ") (display (divides? 66)) (newline)
; Antisymmetric: if a|b and b|a, then a=b
(display "3|6? ") (display (divides? 36)) (newline)
(display "6|3? ") (display (divides? 63)) (newline)
; 3|6 but not 6|3, so no antisymmetry violation.; Transitive: 2|6 and 6|12 implies 2|12
(display "2|6? ") (display (divides? 26)) (newline)
(display "6|12? ") (display (divides? 612)) (newline)
(display "2|12? ") (display (divides? 212))
Neighbors
🐱 Milewski Ch.3 — preorders (reflexive + transitive) are categories