PropositionStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-07

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.

Descending sequences and the choice hypothesis

Statement

A well-founded relation $R$ on a definable class $X$ admits no sequence $f : ω \to X$ with $f (n + 1) R f (n)$ for every $n$ . Conversely, if $X$ is a set supplied with a choice function $c$ on all its nonempty subsets, absence of such a sequence implies well-foundedness. The converse is asserted with this extra hypothesis, not in bare ZF.

Facts & Assumptions

Given: Work in ZF unless the statement explicitly weakens or supplements it; fix the objects and hypotheses of the statement.

[F1]

Let $(W, <)$ be a well-order (def-well-order) and let $G$ be a class function: a rule, given by a formula in the language of set theory, that assigns a set $G (h)$ to every function $h$ whose domain is a proper initial segment of $W$ (def-initial-segment). Then there is exactly one function $F$ with domain $W$ such that $F (a) = G (F ↾ W_{< a}) for every a \in W .$ Here $F ↾ W_{< a}$ is the restriction of $F$ to the initial segment determined by $a$ , so the value of $F$ at $a$ is prescribed in terms of all its earlier values at once. Because $G$ is a class function rather than a set, this is a theorem schema of ZF: one theorem for each formula defining $G$ . It uses Replacement, and it uses no form of the Axiom of Choice. (Transfinite recursion)

Proof

1.1

The range of any descending sequence is a nonempty set. A minimal element of that range, say $f (n)$ , still has predecessor $f (n + 1)$ in the range, a contradiction. This uses exactly the minimal-element definition of well-foundedness.

given

1.2

For the converse, if a nonempty $A \subseteq X$ has no minimal member, every $A \cap {pred}_{R} (a)$ for $a \in A$ is nonempty. Begin with $f (0) = c (A)$ and recurse by $f (n + 1) = c (A \cap {pred}_{R} (f (n)))$ . The supplied choice function makes this a uniquely specified recursion on the set well-order $ω$ ; malformed histories can be assigned $c (A)$ .

F1given

2.1

Induction keeps every value in $A$ and ensures $f (n + 1) R f (n)$ at each step, contradicting the assumed absence. Thus every nonempty subset has a minimal element. For $X = \emptyset$ well-foundedness is vacuous and there is no sequence into $X$ .

step 1.2∎

Depends on

Transfinite recursion

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

4 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

Marks, Set Theory, Berkeley edition — Exercise 6.9 p.31 (choice made explicit). (standard reference, not scraped)