TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Countable choice gives countable subsets of infinite sets

Statement

In ZF plus ${A C}_{ω}$ , every infinite set contains a countably infinite subset and is Dedekind-infinite.

Facts & Assumptions

[F1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable choice selects one object from each nonempty set in an omega family.

[F2]

$N \times N \approx N$ : Omega squared has an explicitly supplied enumeration.

[F3]

Dedekind infinitude is equivalent to a countable subset: An injected omega is equivalent to Dedekind infinitude.

Proof

Given: The objects and hypotheses in the statement.

1.1F1

For each positive integer $n$ , the set $T_{n}$ of injective maps $n \to X$ is nonempty: extend a finite tuple by a point outside its finite range, which exists because $X$ is infinite. This finite induction makes no countable choice. Now use countable choice once to select $t_{n} \in T_{n}$ .

2.1F2step 1.1

The set $U = ⋃_{n > 0} ran (t_{n})$ is covered by the coordinate values $t_{n} (i)$ with $i < n$ . Enumerate those pairs by the fixed enumeration of omega squared, discarding pairs outside the domain. This produces a sequence onto $U$ . Since $U$ contains $n$ distinct points for every $n$ , it is infinite. Retain the first occurrence of each new value; the retained indices form an infinite subset of omega and their increasing enumeration gives a bijection $ω \to U$ .

3.1F3step 2.1∎

Composing with the inclusion $U \subseteq X$ yields an injected omega and hence Dedekind infinitude.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

37 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

Jech, The Axiom of Choice, §2.4.1, p.20 (standard reference, not scraped)