Equivalence Relation - Generating Equivalence Relations

Generating Equivalence Relations

• Given any set X, there is an equivalence relation over the set of all possible functions X→X. Two such functions are deemed equivalent when their respective sets of fixpoints have the same cardinality, corresponding to cycles of length one in a permutation. Functions equivalent in this manner form an equivalence class on, and these equivalence classes partition .

• An equivalence relation ~ on X is the equivalence kernel of its surjective projection π : X → X/~. Conversely, any surjection between sets determines a partition on its domain, the set of preimages of singletons in the codomain. Thus an equivalence relation over X, a partition of X, and a projection whose domain is X, are three equivalent ways of specifying the same thing.

• The intersection of any collection of equivalence relations over X (viewed as a subset of X × X) is also an equivalence relation. This yields a convenient way of generating an equivalence relation: given any binary relation R on X, the equivalence relation generated by R is the smallest equivalence relation containing R. Concretely, R generates the equivalence relation a ~ b if and only if there exist elements x₁, x₂, ..., x_n in X such that a = x₁, b = x_n, and (x_i,x_{i+ 1})∈R or (x_i+1,x_i)∈R, i = 1, ..., n-1.

Note that the equivalence relation generated in this manner can be trivial. For instance, the equivalence relation ~ generated by:

• Any total order on X has exactly one equivalence class, X itself, because x ~ y for all x and y;
• Any subset of the identity relation on X has equivalence classes that are the singletons of X.

• Equivalence relations can construct new spaces by "gluing things together." Let X be the unit Cartesian square ×, and let ~ be the equivalence relation on X defined by ∀a, b ∈ ((a, 0) ~ (a, 1) ∧ (0, b) ~ (1, b)). Then the quotient space X/~ can be naturally identified with a torus: take a square piece of paper, bend and glue together the upper and lower edge to form a cylinder, then bend the resulting cylinder so as to glue together its two open ends, resulting in a torus.