TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)

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.

Let $\sim$ be an equivalence relation on $A$ with quotient map $π : A \to A / \sim$ , and let $f : A \to B$ . There is a function $g : A / \sim \to B$ with $g \circ π = f$ if and only if $a \sim a^{'}$ implies $f (a) = f (a^{'})$ ; and such a $g$ is then unique

Statement

Let $\sim$ be an equivalence relation on a set $A$ , let $A / \sim$ be its quotient set and let $π : = {(a, C) \in A \times (A / \sim) : C = [a]}$ , the quotient map. Let $f : A \to B$ . Then $π$ is a surjective function $A \to A / \sim$ with $π (a) = [a]$ , and:

(i) there is a function $g : A / \sim \to B$ with $g \circ π = f$ if and only if $f (a) = f (a^{'})$ whenever $a \sim a^{'}$ ;
(ii) when such a $g$ exists it is unique, and it satisfies $g ([a]) = f (a)$ for every $a \in A$ .

Facts & Assumptions

Given: an equivalence relation $\sim$ on a set $A$ and a function $f : A \to B$ .

[L1]

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

[L2]

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

[L3]

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

[L4]

$[a] : = {b \in A : a \sim b} \subseteq A$ (Equivalence relation, equivalence class, and the quotient set $A / \sim$ ).

[L5]

$A / \sim : = {[a] : a \in A}$ (Equivalence relation, equivalence class, and the quotient set $A / \sim$ ).

[L6]

We write $f : A \to B$ , and say $f$ is a function from $A$ to $B$ , when $f$ is a function with $dom f = A$ and $ran f \subseteq B$ (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain).

[L7]

$f = g$ if and only if $dom f = dom g$ and $f (x) = g (x)$ for every $x \in dom f$ (Functions $f$ and $g$ are equal if and only if $dom f = dom g$ and $f (x) = g (x)$ for every $x$ in that common domain).

[L8]

$f$ is surjective (onto) if for every $b \in B$ there is some $x \in A$ with $f (x) = b$ (Injection, surjection, bijection).

[L9]

$z \in A \times B$ holds if and only if $z = (a, b)$ for some $a \in A$ and some $b \in B$ (The Cartesian product $A \times B : = {z \in P (P (A \cup B)) : \exists a \in A \exists b \in B z = (a, b)}$ ).

[L10]

For any parameters $\overset{ˉ}{p}$ and any set $x$ , there is a set $y$ whose elements are exactly the elements $z$ of $x$ for which $φ (z, \overset{ˉ}{p})$ holds (The Axiom Schema of Separation: for each formula $φ$ , $\forall \overset{ˉ}{p} \forall x \exists y \forall z (z \in y \leftrightarrow (z \in x \land φ (z, \overset{ˉ}{p})))$ ).

[L11]

$g \circ f$ is a function, $dom (g \circ f) = f^{- 1} [dom g]$ , and $(g \circ f) (x) = g (f (x))$ for every $x$ in that domain (If $f$ and $g$ are functions then $g \circ f$ is a function with domain $f^{- 1} [dom g]$ and $(g \circ f) (x) = g (f (x))$ there; $Δ_{A}$ is a function with $Δ_{A} (a) = a$ ; and $f \circ Δ_{A} = f = Δ_{B} \circ f$ for $f : A \to B$ ).

[L12]

$dom R : = {a : \exists b (a, b) \in R}, ran R : = {b : \exists a (a, b) \in R}$ (Relation, $dom R$ , $ran R$ , $fld R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[L13]

$z \in P (x)$ holds if and only if $z \subseteq x$ (The power set $P (x) = {z : z \subseteq x}$ ).

[L14]

$x \subseteq y$ means that every element of $x$ is an element of $y$ (Subset $x \subseteq y$ , proper subset $x ⊊ y$ , and the separation notation ${z \in x : φ (z)}$ ).

Proof

technique · direct

1.1L1L2L3L4L14

$[a] = [a^{'}]$ holds if and only if $a \sim a^{'}$ . If $a \sim a^{'}$ , then for $b \in A$ we get $b \in [a]$ exactly when $a \sim b$ , and symmetry with transitivity turns that into $a^{'} \sim b$ , so $[a] \subseteq [a^{'}]$ ; the same argument with $a$ and $a^{'}$ exchanged gives the reverse inclusion. Conversely $a \in [a]$ by reflexivity, so $[a] = [a^{'}]$ gives $a \in [a^{'}]$ , that is $a^{'} \sim a$ , and symmetry gives $a \sim a^{'}$ .

1.2L4L5L6L8L9L10L12

$π$ is a surjective function $A \to A / \sim$ with $π (a) = [a]$ : it is a set by separation inside $A \times (A / \sim)$ , it is single valued because $[a]$ is determined by $a$ , its domain is $A$ since $[a] \in A / \sim$ for every $a \in A$ , and every element of $A / \sim$ is $[a]$ for some $a \in A$ , so it is onto.

1.3L5L6L7L11

Uniqueness in (ii): if $g$ and $g^{'}$ are functions $A / \sim \to B$ with $g \circ π = f = g^{'} \circ π$ , then for $C \in A / \sim$ choose $a \in A$ with $C = [a]$ ; then $g (C) = g (π (a)) = f (a) = g^{'} (π (a)) = g^{'} (C)$ . Both have domain $A / \sim$ , so $g = g^{'}$ .

2.1L11step 1.1step 1.2

Claim (i), from left to right: suppose $g : A / \sim \to B$ satisfies $g \circ π = f$ , and let $a \sim a^{'}$ . Then $[a] = [a^{'}]$ , so $f (a) = g (π (a)) = g ([a]) = g ([a^{'}]) = g (π (a^{'})) = f (a^{'})$ .

2.2L5L6L7L9L10L11L12L13step 1.1step 1.2

Claim (i), from right to left: suppose $f (a) = f (a^{'})$ whenever $a \sim a^{'}$ , and separate inside $(A / \sim) \times B$ to obtain $g : = {(C, y) \in (A / \sim) \times B : \exists a (a \in A \land C = [a] \land y = f (a))}$ . It is single valued: if $C = [a] = [a^{'}]$ with values $f (a)$ and $f (a^{'})$ , then $a \sim a^{'}$ and the hypothesis gives $f (a) = f (a^{'})$ . Its domain is $A / \sim$ , since every class is some $[a]$ and then $(C, f (a)) \in g$ , and its range lies in $B$ ; so $g : A / \sim \to B$ with $g ([a]) = f (a)$ . Finally $g \circ π$ and $f$ are functions with domain $A$ and $(g \circ π) (a) = g ([a]) = f (a)$ , so $g \circ π = f$ .

3.1step 1.1step 1.2step 1.3step 2.1step 2.2∎

Both directions of (i) hold, and step 1.3 supplies the uniqueness in (ii) while step 2.2 supplies the formula $g ([a]) = f (a)$ , which is the statement.

Let $\sim$ be an equivalence relation on $A$ with quotient map $π : A \to A / \sim$ , and let $f : A \to B$ . There is a function $g : A / \sim \to B$ with $g \circ π = f$ if and only if $a \sim a^{'}$ implies $f (a) = f (a^{'})$ ; and such a $g$ is then unique

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources

Let ∼∼ be an equivalence relation on AA with quotient map π:A→A/∼π:A→A/∼, and let f:A→Bf:A→B. There is a function g:A/∼→Bg:A/∼→B with g∘π=fg∘π=f if and only if a∼a′a∼a′ implies f(a)=f(a′)f(a)=f(a′); and such a gg is then unique

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources

Let $\sim$ be an equivalence relation on $A$ with quotient map $π : A \to A / \sim$ , and let $f : A \to B$ . There is a function $g : A / \sim \to B$ with $g \circ π = f$ if and only if $a \sim a^{'}$ implies $f (a) = f (a^{'})$ ; and such a $g$ is then unique