LemmaStatement: AI-adaptedProof: AI-generatedprecheck 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 $A$ , 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 $A$ , with classes $[a]$ and quotient set $A / \sim$ (Equivalence relation, equivalence class, and the quotient set $A / \sim$ ). Then:

$a \in [a]$ for every $a \in A$ ; hence every class is nonempty and the classes cover $A$ , that is, the union of the members of $A / \sim$ is $A$ ;
$a \sim b$ if and only if $[a] = [b]$ ;
for all $a, b \in A$ , either $[a] = [b]$ or $[a] \cap [b] = \emptyset$ .

Conversely, call a set $P$ of subsets of $A$ a partition of $A$ when every member of $P$ is nonempty, distinct members of $P$ are disjoint, and the union of the members of $P$ is $A$ . For such a $P$ define $a \sim_{P} b$ to mean that some $B \in P$ contains both $a$ and $b$ . Then $\sim_{P}$ is an equivalence relation on $A$ whose quotient set is exactly $P$ , and it is the only equivalence relation on $A$ whose quotient set is $P$ .

Facts & Assumptions

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

[L1]

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

[L2]

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

[L3]

Transitivity: $a \sim b$ and $b \sim c$ imply $a \sim c$ (Equivalence relation, equivalence class, and the quotient set $A / \sim$ ).

Proof

technique · direct

1.1

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

L1given

1.2

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

L2L3given

1.3

Every member of $P$ is nonempty, distinct members of $P$ are disjoint, and the union of $P$ is $A$ ; consequently each $a \in A$ lies in at least one $B \in P$ , and in only one, since two members containing $a$ are not disjoint and therefore are not distinct. Write $B_{a}$ for that unique member.

given

2.1

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

step 1.1step 1.2

2.2

Suppose $[a] \cap [b] \neq \emptyset$ and pick $c$ in the intersection, so $a \sim c$ and $b \sim c$ . Symmetry gives $c \sim b$ , and transitivity then gives $a \sim b$ , so $[a] = [b]$ by step 1.2. Hence for any $a, b$ either the classes are disjoint or they are equal, which is claim 3.

step 1.2L2L3choose

2.3

$\sim_{P}$ is reflexive, since $a \in B_{a}$ gives $a \sim_{P} a$ ; it is symmetric, since the defining condition is symmetric in $a$ and $b$ ; and it is transitive, for if $a, b \in B$ and $b, c \in B^{'}$ with $B, B^{'} \in P$ , then $b \in B \cap B^{'}$ , so $B$ and $B^{'}$ are not disjoint and hence not distinct, giving $B = B^{'}$ and $a, c \in B$ . So $\sim_{P}$ is an equivalence relation on $A$ .

step 1.3given

3.1

Fix $a \in A$ and write $[a]_{P}$ for its class under $\sim_{P}$ . If $b \in [a]_{P}$ then some $B \in P$ contains $a$ and $b$ , and $B = B_{a}$ by the uniqueness in step 1.3, so $b \in B_{a}$ ; conversely if $b \in B_{a}$ then $B_{a}$ contains both $a$ and $b$ , so $b \in [a]_{P}$ . Hence $[a]_{P} = B_{a}$ .

step 1.3step 2.3

4.1

Every class of $\sim_{P}$ is a member of $P$ by step 3.1, and every $B \in P$ is nonempty, so choosing $a \in B$ gives $B = B_{a} = [a]_{P}$ , a class; therefore the quotient set of $\sim_{P}$ is exactly $P$ .

step 1.3step 3.1choose

4.2

Uniqueness. Let $\approx$ be any equivalence relation on $A$ whose quotient set is $P$ , and fix $a \in A$ . Its class $[a]_{\approx}$ lies in $P$ and contains $a$ by step 1.1 applied to $\approx$ , so $[a]_{\approx} = B_{a}$ by the uniqueness in step 1.3. Then $a \approx b$ holds exactly when $b \in [a]_{\approx} = B_{a}$ , which by step 3.1 holds exactly when $a \sim_{P} b$ ; so $\approx$ and $\sim_{P}$ relate the same pairs and are equal as subsets of $A \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 · two levels

18 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Equivalence class (Wikipedia) (standard reference, not scraped)
Partition of a set (Wikipedia) (standard reference, not scraped)

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