LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-05 (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.

Dependent choice along a sequence of relations: if $R_{n}$ is entire on $A$ for every $n$ , then from any $a$ there is a sequence with $a_{n} R_{n} a_{n + 1}$

Statement

Assume the Axiom of Dependent Choice (The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain).

Let $A$ be a nonempty set and let $(R_{n})_{n \in N}$ be a family of binary relations on $A$ , indexed by $N$ (The natural numbers $N$ (von Neumann)), such that

$for every n \in N and every u \in A there is v \in A with u R_{n} v .$

Then for every $a_{0} \in A$ there is a function $a : N \to A$ (Convergence and cluster points of a sequence in a topological space, sequential continuity, and the sequential closure) with

$a (0) = a_{0} and a (n) R_{n} a (n + 1) for every n \in N .$

Why this is not The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain read off. That axiom is stated for one relation $R$ , entire on one set, fixed before any step is taken. What is needed here is a relation that changes with the stage: at step $n$ the admissible successors are the $R_{n}$ -successors, and $R_{n}$ is a different relation for each $n$ . A family of relations on $A$ is not a relation on $A$ , so the axiom does not apply to it directly, and applying it as if it did would be a genuine gap. The proof below removes the gap by carrying the stage inside the set.

Facts & Assumptions

Given: A nonempty set $A$ , a family $(R_{n})_{n \in N}$ of binary relations on $A$ , a point $a_{0} \in A$ , and the Axiom of Dependent Choice.

[A1]

For every $n \in N$ and every $u \in A$ there is $v \in A$ with $u R_{n} v$ .

[L1]

Dependent choice: for every nonempty set $X$ , every relation $S$ on $X$ that is entire on $X$ — meaning every element of $X$ is related to some element of $X$ — and every $p \in X$ , there is a function $x : N \to X$ with $x_{0} = p$ and $x_{n} S x_{n + 1}$ for every $n \in N$ (The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain, Convergence and cluster points of a sequence in a topological space, sequential continuity, and the sequential closure).

[L2]

$N$ contains $0$ and every natural has the successor $n + 1$ (The natural numbers $N$ (von Neumann)).

[L3]

If $S \subseteq N$ contains $0$ and contains $n + 1$ whenever it contains $n$ , then $S = N$ (The principle of mathematical induction).

Proof

technique · direct

1.1

Put $X : = N \times A$ , a nonempty set since $A$ is nonempty and $0 \in N$ , and define a relation $S$ on $X$ by declaring $(n, u) S (m, v)$ to hold exactly when $m = n + 1$ and $u R_{n} v$ .

L2construct

2.1

$S$ is entire on $X$ : given $(n, u) \in X$ , [A1] supplies $v \in A$ with $u R_{n} v$ , and then $(n + 1, v)$ lies in $X$ and satisfies $(n, u) S (n + 1, v)$ .

A1L2step 1.1

3.1

By [L1] applied to $X$ , $S$ and the point $(0, a_{0})$ there is $x : N \to X$ with $x_{0} = (0, a_{0})$ and $x_{n} S x_{n + 1}$ for every $n$ ; write $x_{n} = (k_{n}, a_{n})$ with $k_{n} \in N$ and $a_{n} \in A$ , so that $k_{0} = 0$ , $a_{0}$ is the given point, and $k_{n + 1} = k_{n} + 1$ with $a_{n} R_{k_{n}} a_{n + 1}$ for every $n$ .

L1step 1.1step 2.1

4.1

$k_{n} = n$ for every $n \in N$ : the set ${n \in N : k_{n} = n}$ contains $0$ because $k_{0} = 0$ , and contains $n + 1$ whenever it contains $n$ because $k_{n + 1} = k_{n} + 1 = n + 1$ ; so [L3] makes it all of $N$ .

L3step 3.1

5.1

Therefore $a : n \mapsto a_{n}$ is a function $N \to A$ with $a (0) = a_{0}$ and $a (n) R_{n} a (n + 1)$ for every $n$ , the relation at stage $n$ being $R_{k_{n}} = R_{n}$ by step 4.1.

step 3.1step 4.1∎

Remarks

The device is the standard one and it is worth naming. Carrying the stage as a first coordinate turns a family of relations into a single relation on a larger set, at the cost of having to check afterwards that the first coordinate really counts $0, 1, 2, \dots$ ; that check is step 4.1 and it is an ordinary induction on $N$ , not a second appeal to choice.

Nothing beyond dependent choice is spent. The hypothesis [A1] is a pure existence statement, asserting for each stage and each element that some successor exists; it names none. All the selecting is done once, by [L1], and the lemma adds nothing to its cost.

Depends on

Used by

Dependency tree · two levels

21 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

Axiom of dependent choice (Wikipedia) (standard reference, not scraped)

Dependent choice along a sequence of relations: if RnRn​ is entire on AA for every nn, then from any aa there is a sequence with anRnan+1an​Rn​an+1​