CS2050 L13 Equivalence Relations

Overview

Abrahim Ladha develops equivalence relations as relations that are reflexive, symmetric, and transitive, then tests the definition against equality of sets, order on the reals, birthdays, rational-number representations, logical equivalence, parity, and bijections. He shows that equivalence classes partition their underlying set and applies the same framework to graph isomorphism, where a structure-preserving bijection defines equality up to relabeling.

Key takeaways

An equivalence relation must be reflexive, symmetric, and transitive; these properties formalize when objects can be treated as interchangeable under a chosen definition of equality.
Rational numbers can be equal despite different fraction forms: a/b and c/d represent the same value when ad = bc, for nonzero denominators.
The integer relation a + 3b even is an equivalence relation because it groups integers by parity, despite not initially looking like a definition of equality.
Every equivalence relation partitions its universe: its classes cover the universe, and any two classes that share an element must be identical.
Graph isomorphism defines structural equality through a bijection that preserves edges; identity, inverse, and composition establish reflexivity, symmetry, and transitivity.

Chapters

0:00 Relations and the Three Conditions for Equivalence

A relation from set A to set B is a subset of A × B; a relation over A is a subset of A × A.
Reflexivity requires x to relate to itself; symmetry requires xRy to imply yRx.
Transitivity requires xRy and yRz to imply xRz; an equivalence relation must satisfy all three properties.
These conditions generalize equality by ensuring related objects can substitute for one another consistently.

4:30 Equality Axioms and Set Equality by Extensionality

Equality of natural numbers satisfies reflexivity, symmetry, and transitivity through the equality axioms of Peano arithmetic.
Set extensionality defines A = B by requiring every z to belong to A if and only if it belongs to B.
The logical laws of biconditional establish the three equivalence properties for set equality.

9:05 Why Real-Number Less-Than-or-Equal Is Not an Equivalence

The relation x ≤ y can be defined by the existence of a nonnegative real u such that x + u = y.
It is reflexive by choosing u = 0 and transitive because the sum of two nonnegative reals is nonnegative.
It is not symmetric: for example, 3 ≤ 7 does not imply 7 ≤ 3.

15:50 Same Birthday as an Equivalence Relation on People

On the set of people, define A to relate to B exactly when they have the same birthday.
The relation is reflexive because each person has the same birthday as themselves.
Birthday equality is symmetric and transitive, so it is an equivalence relation.

18:20 Rational Equality Across Different Fraction Representations

Fractions such as 2/4 and 1/2 look different but represent the same rational number.
For integer numerators and nonzero denominators, define a/b to relate to c/d when ad = bc.
The cross-multiplication definition is reflexive, symmetric, and transitive, so it formalizes equality without requiring identical notation.

24:00 Logical Equivalence of Propositions

Two propositions are logically equivalent when they have the same truth table.
Equivalently, their biconditional is a tautology.
Reflexivity, symmetry, and transitivity follow from identical truth tables and the corresponding laws of the biconditional.

26:40 An Unexpected Integer Equivalence: a + 3b Is Even

For integers a and b, define a relation by requiring a + 3b to be even.
Reflexivity follows because a + 3a = 4a is even; symmetry and transitivity follow from parity algebra.
Since 3 has the same parity as 1, this relation groups integers according to whether they have the same parity.

32:55 Bijections Define an Equivalence Relation on Sets

For subsets of a universe, relate A and B when a bijection exists from A to B.
The identity function proves reflexivity, and the inverse of a bijection proves symmetry.
If bijections connect A to B and B to C, their composition is a bijection from A to C, proving transitivity.
For finite sets, having a bijection is equivalent to having the same cardinality; the relation also applies to infinite sets.

41:10 Finite Power-Set Example and Equivalence Classes

The power set of {1, 2, 3} contains eight subsets, including the empty set and subsets of sizes one, two, and three.
Under the bijection relation, subsets group by cardinality: the empty set, the three singletons, the three two-element sets, and the full set.
Each group is an equivalence class, illustrating how an equivalence relation divides a set into non-overlapping groups.

44:30 Equivalence Classes, Quotient Sets, and Partitions

For an element a, its equivalence class [a] is the set of all x in the universe such that x relates to a.
The quotient set is the set of all equivalence classes, treating each class as one representative object.
A partition covers the entire universe, and any two distinct parts are disjoint.

47:30 Proving Equivalence Classes Cover the Universe

The union of all equivalence classes is contained in the universe because each class is defined as a subset of it.
For any a in the universe, reflexivity gives a ~ a, so a belongs to its own class [a].
Therefore every element appears in at least one class, proving that the classes cover the universe.

51:50 Why Distinct Equivalence Classes Must Be Disjoint

To prove disjointness, show that if [a] and [b] overlap, then the classes are equal.
An element x in their intersection satisfies x ~ a and x ~ b.
Symmetry and transitivity show that every element related to a is related to b, and vice versa, so [a] = [b].

56:50 Graph Isomorphism as Equality Up to Relabeling

A graph is described by a vertex set V and an edge set E, with edges drawn from V × V.
Graph properties such as cycles and paths depend on structure rather than vertex names or drawing layout.
An isomorphism is a bijection between vertex sets that preserves whether each vertex pair forms an edge.
Graphs are isomorphic when a structure-preserving relabeling maps one graph to the other.

1:03:00 Proving Graph Isomorphism Is an Equivalence Relation

The identity bijection preserves every edge, proving that each graph is isomorphic to itself.
The inverse of a structure-preserving bijection is also a structure-preserving bijection, proving symmetry.
Composing isomorphisms from G1 to G2 and G2 to G3 gives an isomorphism from G1 to G3, proving transitivity.
Determining graph isomorphism algorithmically is difficult and has applications in fields such as chemistry.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.