Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12
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.

Infinite computably enumerable sets have computable injective enumerations

Statement

Every infinite computably enumerable subset of an effectively encoded set X is the range of a total computable injective function N→X.

Facts & Assumptions

Given: An infinite computably enumerable set A⊆X.

[L1]

By Computably enumerable sets and languages, since A is infinite it is in particular nonempty, so there exists a total computable function e:N→X whose range is exactly A.

[L2]

By Computable and partial computable functions, the total computable enumerator from [L1] is realized by a machine that halts with the code of e(n) on every input n.

Proof

technique · direct
1.1L1L2construct

By [L1], choose a total computable enumerator e:N→X with range exactly A, and let E be a machine as in [L2] that computes it. On input n, simulate the computations of E on 0,1,2,… one after another, keep the list of distinct output codewords already seen, and halt when the (n+1)st new codeword appears, outputting that codeword.

2.1step 1.1

The resulting function g:N→X is injective by construction, because each output is the next codeword not seen before. Every value of g lies in A because every output of E lies in the range of e. Conversely, if x∈A, then some stage of the sequential scan in step 1.1 encounters the codeword eX(x) among the outputs of E, so that codeword is eventually appended to the distinct-output list. Hence the range of g is exactly A.

3.1step 2.1given

Because A is infinite, for each n there are at least n+1 distinct elements of A. Step 2.1 shows that each of their codewords appears somewhere in the scan from step 1.1, so the (n+1)st new codeword is found after finitely many outputs of E. Therefore the machine of step 1.1 halts on every input n, and it computes a total injective function g:N→X with range A.

4.1step 2.1step 3.1∎

Thus every infinite c.e. set has a computable injective enumeration.

Depends on

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