CounterexampleConstruction: AI-adaptedVerification: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)

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 collapsing recursion has no solution on $(Z, <)$

Statement refuted

Refuted claim: the recursive equation $F (a) = {F (b) : b < a}$ has a solution for every total order, so the theorem schema Transfinite recursion and its corollary Every well-order has a unique order type need only a linear order in place of a well-order (Well-order and well-ordered set).

The witness is $(Z, <)$ with its usual order (Order on the integers). There is no function $F$ with $F (a) = {F (b) : b < a}$ for every $a \in Z$ : if there were, then $F (a) \in F (b)$ whenever $a < b$ , and the values along the descending sequence $- 1 > - 2 > - 3 > \dots$ would form a set $S$ (by Replacement) in which each element $x_{n + 1} = F (- (n + 2))$ is a member of the previous one $x_{n} = F (- (n + 1))$ , so $x_{n + 1} \in x_{n} \cap S$ for every $n$ ; Foundation applied to the nonempty set $S$ forbids exactly this. So the least-element hypothesis cannot be weakened to totality, and the failure is precisely the infinite descending sequence $- 1 > - 2 > - 3 > \dots$ that no well-order admits. The argument uses only Foundation, Replacement and the order of $Z$ ; no choice principle is used.

Facts & Assumptions

Given: The integers $Z$ with their order and ring operations, ZF with Foundation, and the supposition that a function $F$ satisfies $F (a) = {F (b) : b < a}$ for every $a \in Z$ . Write $x_{n} : = F (- (n + 1))$ for $n \in ω = N$ , where $n + 1 = σ (n)$ in $N$ and $- (n + 1)$ is the additive inverse of the image of $n + 1$ in $Z$ .

[F1]

Integers are ordered by the relation of Order on the integers: $x < y$ means $x \leq y$ and $x \neq y$ (Order on the integers).

[F2]

That relation is a total order on $Z$ compatible with addition: $x \leq y$ implies $x + z \leq y + z$ , and consequently $x < y$ implies $- y < - x$ (The integers form a totally ordered ring).

[F3]

$(Z, +, \cdot, 0, 1)$ is a commutative ring in which every element has an additive inverse, with the operations of Arithmetic on the integers (The integers form a commutative ring, Arithmetic on the integers).

[F4]

The canonical embedding of $N$ in $Z$ , written $n \mapsto [(n, 0)]$ , is injective and preserves addition and order, and its image is the set of nonnegative integers (The naturals embed in the integers).

[F5]

$ω = N$ with $0 = \emptyset$ and $σ (n) = n \cup {n}$ (The natural numbers $N$ (von Neumann)).

[F6]

For every natural $n$ one has $n < σ (n) = n + 1$ , hence $n + 1 < n + 2$ (On $N$ the order is membership: $m < n ⟺ m \in n$ ).

[F7]

If a formula determines one set $w$ for each $z$ in a set $A$ , then the collection of those $w$ is a set: this is the Axiom Schema of Replacement (The Axiom Schema of Replacement: for each formula $φ$ , if $φ$ defines a class function on $A$ then its image on $A$ is a set).

[F8]

Axiom of Foundation: every set $S$ with at least one member has a member $s$ with $s \cap S = \emptyset$ (The Axiom of Foundation: $\forall S (\exists t (t \in S) \to \exists s (s \in S \land \neg \exists u (u \in s \land u \in S)))$ ).

[F9]

Transfinite recursion: for a well-order $(W, <)$ and a class function $G$ there is exactly one $F$ on $W$ with $F (a) = G (F ↾ W_{< a})$ (Transfinite recursion).

[F10]

Every well-order is order isomorphic to exactly one ordinal, its order type, via the collapsing map $F (a) = {F (b) : b < a}$ (Every well-order has a unique order type).

[F11]

A function is a relation that never assigns two values to one argument; $F$ above is assumed to be such a relation with domain $Z$ (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).

Counterexample

technique · contradiction

1.1assume-contraF11

Suppose, for contradiction, that there is a function $F$ with $F (a) = {F (b) : b < a}$ for every $a \in Z$ .

1.2F2F3F4F5F6

For every $n \in ω$ the integers satisfy $- (n + 2) < - (n + 1)$ : the naturals satisfy $n + 1 < n + 2$ by [F6], so the corresponding integers $[(n + 1, 0)]$ and $[(n + 2, 0)]$ satisfy $[(n + 1, 0)] \leq [(n + 2, 0)]$ by order preservation of the embedding $n \mapsto [(n, 0)]$ , with the values distinct because that embedding is injective while $n + 1 \neq n + 2$ , hence $[(n + 1, 0)] < [(n + 2, 0)]$ ; applying negation reversal then gives $- [(n + 2, 0)] < - [(n + 1, 0)]$ , which is the displayed inequality.

2.1step 1.1

For all integers $a < b$ one has $F (a) \in F (b)$ : by the supposition $F (b) = {F (c) : c < b}$ , and $F (a)$ is one of the members of that set because $a < b$ .

2.2step 1.1F7F11

The set $S = {x_{n} : n \in ω}$ exists: $n \mapsto x_{n}$ is given by the formula $w = F (- (n + 1))$ , which determines one $w$ for each $n \in ω$ because $F$ is a function, so Replacement makes the image a set.

3.1step 2.1step 1.2

For every $n \in ω$ one has $x_{n + 1} \in x_{n}$ : step 1.2 puts $- (n + 2) < - (n + 1)$ , so step 2.1 applied to the pair $a = - (n + 2) < b = - (n + 1)$ gives $F (- (n + 2)) \in F (- (n + 1))$ , that is $x_{n + 1} \in x_{n}$ .

3.2step 2.2F8

The set $S$ is nonempty, since $x_{0} = F (- 1)$ is one of its members; so Foundation applies to $S$ and supplies $x \in S$ with $x \cap S = \emptyset$ .

4.1step 3.1step 3.2

Since $x \in S$ , there is $m \in ω$ with $x = x_{m}$ , and then step 3.1 gives $x_{m + 1} \in x_{m} \cap S$ , because $x_{m + 1} \in x_{m}$ and $x_{m + 1} \in S$ ; this contradicts $x_{m} \cap S = \emptyset$ from step 3.2.

5.1step 1.1step 3.1step 4.1F1F2F8F9F10discharge-contradiction∎

The supposition of step 1.1 is therefore refuted: there is no function $F$ with $F (a) = {F (b) : b < a}$ for every $a \in Z$ . So a solution of the collapsing recursion is not available on the total order $(Z, <)$ , and the least-element hypothesis of [F9] and [F10] cannot be weakened to totality; the failure is the infinite descending sequence $- 1 > - 2 > - 3 > \dots$ , whose values would form the set $S$ that Foundation forbids. The argument used only Foundation, Replacement and the order of $Z$ ; no choice principle was used.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

55 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

A. Marks, Set Theory (Berkeley lecture notes, 2026) (standard reference, not scraped)
J. T. Moore, MATH 6870: Set Theory (Cornell lecture notes) (standard reference, not scraped)

The collapsing recursion has no solution on (Z,<)(Z,<)