How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced — the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted — a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated — a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The equivalence classes of an equivalence relation are nonempty, cover , and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation
Statement
Let be an equivalence relation on a set , with classes and quotient set (Equivalence relation, equivalence class, and the quotient set ). Then:
- for every ; hence every class is nonempty and the classes cover , that is, the union of the members of is ;
- if and only if ;
- for all , either or .
Conversely, call a set of subsets of a partition of when every member of is nonempty, distinct members of are disjoint, and the union of the members of is . For such a define to mean that some contains both and . Then is an equivalence relation on whose quotient set is exactly , and it is the only equivalence relation on whose quotient set is .
Facts & Assumptions
Given: An equivalence relation on a set , with and (Equivalence relation, equivalence class, and the quotient set ); and, for the converse, a partition of in the sense stated above.
Reflexivity: for every (Equivalence relation, equivalence class, and the quotient set ).
Symmetry: implies (Equivalence relation, equivalence class, and the quotient set ).
Transitivity: and imply (Equivalence relation, equivalence class, and the quotient set ).
Proof
For every reflexivity gives , that is ; so each class is nonempty, each class is a subset of by construction, and each lies in the class , whence the union of the members of is exactly . This is claim 1.
Suppose . If then , so by transitivity, so ; thus . Symmetry gives , and the same argument with and interchanged gives ; hence .
Every member of is nonempty, distinct members of are disjoint, and the union of is ; consequently each lies in at least one , and in only one, since two members containing are not disjoint and therefore are not distinct. Write for that unique member.
Suppose . By step 1.1, , which says . Together with step 1.2 this is claim 2.
Suppose and pick in the intersection, so and . Symmetry gives , and transitivity then gives , so by step 1.2. Hence for any either the classes are disjoint or they are equal, which is claim 3.
is reflexive, since gives ; it is symmetric, since the defining condition is symmetric in and ; and it is transitive, for if and with , then , so and are not disjoint and hence not distinct, giving and . So is an equivalence relation on .
Fix and write for its class under . If then some contains and , and by the uniqueness in step 1.3, so ; conversely if then contains both and , so . Hence .
Every class of is a member of by step 3.1, and every is nonempty, so choosing gives , a class; therefore the quotient set of is exactly .
Uniqueness. Let be any equivalence relation on whose quotient set is , and fix . Its class lies in and contains by step 1.1 applied to , so by the uniqueness in step 1.3. Then holds exactly when , which by step 3.1 holds exactly when ; so and relate the same pairs and are equal as subsets of .
Claims 1, 2 and 3 are steps 1.1, 2.1 and 2.2; the converse is steps 2.3, 4.1 and 4.2.
Remarks
-
Claim 2 is the fact used constantly in practice: an equation between classes may always be replaced by a relation between representatives, and conversely. Claim 3 is what makes a quotient set behave like a set of disjoint boxes.
-
The converse half is what licenses building an equivalence relation by describing its classes rather than its pairs. The uniqueness clause matters: it says that no information is lost either way, so a partition and an equivalence relation are interchangeable descriptions of the same structure.
Depends on
- Equivalence relation, equivalence class, and the quotient set $A/{\sim}$
- The union $\bigcup x$ of a set, and the binary union $a \cup b := \bigcup \{a,b\}$
- The intersection $\bigcap x$ of a nonempty set, the binary intersection $a \cap b := \bigcap\{a,b\}$, and disjointness
- The power set $\mathcal{P}(x) = \{\, z : z \subseteq x \,\}$
- Subset $x \subseteq y$, proper subset $x \subsetneq y$, and the separation notation $\{\, z \in x : \varphi(z) \,\}$
- There is exactly one set with no elements, written $\varnothing$
Used by
- The congruence class [a]ₙ and the quotient set ℤ/n Definition
- A two-cell partition of a three-element set, the equivalence relation it induces listed pair by pair, and the quotient set recovered from it Example
- For n ≥ 1 the congruence classes modulo n form an abelian group (ℤ/n, +) of order n, generated by the class of 1 Example
- For integers a and b the following are equivalent: a ∣ b and b ∣ a; b = ua for a unit u; |a| = |b|. Being associates is an equivalence relation whose class of a is {a, -a} Lemma
- The left cosets of a subgroup partition the group Lemma
- The Axiom of Choice is stated on this page and assumed by no proof on it; the two statements that would need it are identified and left unsettled Remark
- Every function f : A → B factors as f = ι ∘ bar f ∘ π with π : A → A/ker f the surjective quotient map, bar f : A/ker f → f[A] the bijection [a] ↦ f(a), and ι : f[A] → B the inclusion injection; bar f is the only function making the factorisation hold Theorem
- The orbits of a group action are the equivalence classes of x∼ y iff y=g· x for some g, and hence partition the acted-on set Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 26 results over 11 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Equivalence class (Wikipedia) (standard reference, not scraped)
- Partition of a set (Wikipedia) (standard reference, not scraped)