Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27
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 AA, and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation

Statement

Let \sim be an equivalence relation on a set AA, with classes [a][a] and quotient set A/A/{\sim} (Equivalence relation, equivalence class, and the quotient set A/A/{\sim}). Then:

  1. a[a]a \in [a] for every aAa \in A; hence every class is nonempty and the classes cover AA, that is, the union of the members of A/A/{\sim} is AA;
  2. aba \sim b if and only if [a]=[b][a] = [b];
  3. for all a,bAa, b \in A, either [a]=[b][a] = [b] or [a][b]=[a] \cap [b] = \varnothing.

Conversely, call a set PP of subsets of AA a partition of AA when every member of PP is nonempty, distinct members of PP are disjoint, and the union of the members of PP is AA. For such a PP define aPba \sim_P b to mean that some BPB \in P contains both aa and bb. Then P\sim_P is an equivalence relation on AA whose quotient set is exactly PP, and it is the only equivalence relation on AA whose quotient set is PP.

Facts & Assumptions

Given: An equivalence relation \sim on a set AA, with [a]={bA:ab}[a] = \{ b \in A : a \sim b \} and A/={[a]:aA}A/{\sim} = \{ [a] : a \in A \} (Equivalence relation, equivalence class, and the quotient set A/A/{\sim}); and, for the converse, a partition PP of AA in the sense stated above.

[L1]

Reflexivity: aaa \sim a for every aAa \in A (Equivalence relation, equivalence class, and the quotient set A/A/{\sim}).

[L2]

Symmetry: aba \sim b implies bab \sim a (Equivalence relation, equivalence class, and the quotient set A/A/{\sim}).

[L3]

Transitivity: aba \sim b and bcb \sim c imply aca \sim c (Equivalence relation, equivalence class, and the quotient set A/A/{\sim}).

Proof

technique · direct
1.1

For every aAa \in A reflexivity gives aaa \sim a, that is a[a]a \in [a]; so each class is nonempty, each class is a subset of AA by construction, and each aAa \in A lies in the class [a][a], whence the union of the members of A/A/{\sim} is exactly AA. This is claim 1.

L1given
1.2

Suppose aba \sim b. If c[b]c \in [b] then bcb \sim c, so aca \sim c by transitivity, so c[a]c \in [a]; thus [b][a][b] \subseteq [a]. Symmetry gives bab \sim a, and the same argument with aa and bb interchanged gives [a][b][a] \subseteq [b]; hence [a]=[b][a] = [b].

L2L3given
1.3

Every member of PP is nonempty, distinct members of PP are disjoint, and the union of PP is AA; consequently each aAa \in A lies in at least one BPB \in P, and in only one, since two members containing aa are not disjoint and therefore are not distinct. Write BaB_a for that unique member.

given
2.1

Suppose [a]=[b][a] = [b]. By step 1.1, b[b]=[a]b \in [b] = [a], which says aba \sim b. Together with step 1.2 this is claim 2.

step 1.1step 1.2
2.2

Suppose [a][b][a] \cap [b] \ne \varnothing and pick cc in the intersection, so aca \sim c and bcb \sim c. Symmetry gives cbc \sim b, and transitivity then gives aba \sim b, so [a]=[b][a] = [b] by step 1.2. Hence for any a,ba, b either the classes are disjoint or they are equal, which is claim 3.

step 1.2L2L3choose
2.3

P\sim_P is reflexive, since aBaa \in B_a gives aPaa \sim_P a; it is symmetric, since the defining condition is symmetric in aa and bb; and it is transitive, for if a,bBa, b \in B and b,cBb, c \in B' with B,BPB, B' \in P, then bBBb \in B \cap B', so BB and BB' are not disjoint and hence not distinct, giving B=BB = B' and a,cBa, c \in B. So P\sim_P is an equivalence relation on AA.

step 1.3given
3.1

Fix aAa \in A and write [a]P[a]_P for its class under P\sim_P. If b[a]Pb \in [a]_P then some BPB \in P contains aa and bb, and B=BaB = B_a by the uniqueness in step 1.3, so bBab \in B_a; conversely if bBab \in B_a then BaB_a contains both aa and bb, so b[a]Pb \in [a]_P. Hence [a]P=Ba[a]_P = B_a.

step 1.3step 2.3
4.1

Every class of P\sim_P is a member of PP by step 3.1, and every BPB \in P is nonempty, so choosing aBa \in B gives B=Ba=[a]PB = B_a = [a]_P, a class; therefore the quotient set of P\sim_P is exactly PP.

step 1.3step 3.1choose
4.2

Uniqueness. Let \approx be any equivalence relation on AA whose quotient set is PP, and fix aAa \in A. Its class [a][a]_\approx lies in PP and contains aa by step 1.1 applied to \approx, so [a]=Ba[a]_\approx = B_a by the uniqueness in step 1.3. Then aba \approx b holds exactly when b[a]=Bab \in [a]_\approx = B_a, which by step 3.1 holds exactly when aPba \sim_P b; so \approx and P\sim_P relate the same pairs and are equal as subsets of A×AA \times A.

step 1.1step 1.3step 3.1
5.1

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.

step 1.1step 2.1step 2.2step 2.3step 4.1step 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

Used by

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