ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)

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.

Finite choice written out: a choice function for three sets

Example

Let

$F = {{0, 1}, {1, 2}, {2, 3}},$

a family of three nonempty sets of natural numbers. A choice function for $F$ (Choice function) can be written down outright, by listing its three values:

$g ({0, 1}) = 0, g ({1, 2}) = 1, g ({2, 3}) = 2.$

Nothing was assumed to produce it. Each value is one element taken from one set already known to be nonempty, and three such picks are made one after another. The induction of Every natural-number-indexed list of nonempty sets has a choice function on its family of values is exactly this process stated in general. That lemma indexes the family by a natural number rather than counting its members: writing the three sets as the values $F (0), F (1), F (2)$ of a function $F$ with domain $3 = {0, 1, 2}$ (The natural numbers $N$ (von Neumann)), the successor step restricts $F$ to the shorter index set, takes a choice function for those values, and overwrites it with one further pair.

Facts & Assumptions

Given: The family $F = {{0, 1}, {1, 2}, {2, 3}}$ , whose members are sets of natural numbers, together with the function $F$ with domain the von Neumann natural number $3 = {0, 1, 2}$ (The natural numbers $N$ (von Neumann)) given by $F (0) = {0, 1}$ , $F (1) = {1, 2}$ , $F (2) = {2, 3}$ , so that $F = F [3]$ .

[L1]

A choice function for a family $F$ is a function $g$ with domain $F$ such that $g (S) \in S$ for every $S \in F$ (Choice function).

[L2]

For every natural number $n$ and every function $F$ with domain $n$ all of whose values are nonempty, the family of values $F [n]$ has a choice function; the proof is an induction on $n$ whose successor step restricts $F$ to $n \subseteq σ (n)$ , takes a choice function for $F [n]$ , and overwrites it with the single pair $(F (n), a)$ for some $a \in F (n)$ (Every natural-number-indexed list of nonempty sets has a choice function on its family of values).

Verification

technique · direct

1.1

The three members are pairwise distinct: $0$ belongs to ${0, 1}$ and to neither of the others, $1$ belongs to ${1, 2}$ but not to ${2, 3}$ , and ${0, 1} \neq {2, 3}$ since $0 \notin {2, 3}$ ; so $F$ has exactly three members.

given

1.2

Every member is nonempty: $0 \in {0, 1}$ , $1 \in {1, 2}$ and $2 \in {2, 3}$ .

given

2.1

Let $g = {({0, 1}, 0), ({1, 2}, 1), ({2, 3}, 2)}$ , the set whose three elements are those ordered pairs; it is a relation with domain $F$ , and since the three members of $F$ are pairwise distinct its three first coordinates are pairwise distinct, so it is single valued: $g$ is a function on $F$ .

step 1.1construct

3.1

Its values lie where they must: $g ({0, 1}) = 0 \in {0, 1}$ , $g ({1, 2}) = 1 \in {1, 2}$ and $g ({2, 3}) = 2 \in {2, 3}$ , so $g (S) \in S$ for every $S \in F$ and $g$ is a choice function for $F$ .

step 2.1step 1.2L1

4.1

A function of this shape is what the induction of [L2] returns when run on the listing $F$ : since $F$ has domain $3$ and each value is nonempty by step 1.2, [L2] applies with $n = 3$ and yields a choice function for $F [3] = F$ , obtained in three stages, one pick at each index, so no choice principle is invoked and none is needed. Nothing here rests on counting the members of $F$ , only on the listing exhibited in the Given.

step 3.1step 1.2givenL2∎

Remarks

Where an axiom would have been needed, and why it was not. Each pick is a single existential instantiation from a single nonempty set, licensed by first-order logic alone. Three of them are made, one at a time, and three is a natural number, so the process stops. What ZF does not supply is a choice function for every arbitrary family of nonempty sets. An infinite family can still have a choice function given by a defining rule — such as the minimum rule below — so the gap filled by the Axiom of Choice is arbitrary families, not mere infinitude.
Choice functions are not unique. Taking the larger element of each pair gives another one, with values $1, 2, 3$ ; since each member has two elements there are $2 \cdot 2 \cdot 2 = 8$ choice functions for $F$ in all. Nothing in the definition prefers one of them.
The particular $g$ displayed above is the rule $S \mapsto \min S$ , which happens to work for every nonempty set of natural numbers at once ( $\min$ is a choice function on $N$ ). That is a feature of $N$ , not of finiteness. The two ingredients come apart in Russell's shoes and socks, where the family is infinite and carries no such rule.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

15 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

Choice function (Wikipedia) (standard reference, not scraped)
Axiom of choice (Wikipedia) (standard reference, not scraped)