Relations, equivalence relations and partitions

Se basa en

Requisitos previos obligatorios, hasta el fondo: 2

Aprenderás a

• Represent a relation on a finite set as a set of ordered pairs, a table and an arrow diagram.
• Test a relation for reflexivity, symmetry and transitivity, giving a counterexample whenever a property fails.
• Pass between an equivalence relation and the partition formed by its equivalence classes.

Definición

• A relation R on a set A is a subset of A × A; we write a R b when (a, b) ∈ R.
• R is an equivalence relation if it is reflexive (a R a), symmetric (a R b implies b R a) and transitive (a R b and b R c imply a R c).
• The equivalence class of a is [a] = {x ∈ A : x R a}.
• A partition of A is a set of non-empty, pairwise disjoint subsets of A whose union is A.

Teorema

• The equivalence classes of an equivalence relation on A form a partition of A, and every partition of A comes from exactly one equivalence relation.
• Any two equivalence classes are either equal or disjoint.
• For n ≥ 1, 'has the same remainder on division by n' is an equivalence relation on ℤ with exactly n classes.

Errores frecuentes

• Thinking symmetry and transitivity together imply reflexivity; the argument fails for an element related to nothing.
• Treating an equivalence class as a single element instead of a set of elements.
• Assuming every relation is symmetric, as 'is less than' shows it need not be.

Conduce a

Descubrimientos opcionales

• Quotient groups and quotient rings Collapsing each class to a single point gives a quotient set; when the relation respects an operation, the quotient inherits it, giving quotient groups and rings such as ℤ/nℤ.Sendero del Asombro →
• Universal properties The quotient map A → A/~ is universal: every function out of A that is constant on equivalence classes factors through it in exactly one way.Sendero del Asombro →
• Metric spaces and point-set topology Gluing points by an equivalence relation produces quotient spaces, such as a circle from an interval with its endpoints identified.
• ← Collections
• ← Integers

Itinerarios de aprendizaje

• Accelerated secondary progression

Lecturas complementarias

• Daniel J. Velleman, How to Prove It: A Structured Approach (1994)