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.

Domains and ranges of partial computable functions are computably enumerable

Statement

Let f:DY be a partial computable function on effectively encoded sets X and Y, and assume that the chosen total decoder for the input encoding of X is itself computable. Then its domain DX and its range f[D]Y are computably enumerable.

Facts & Assumptions

Given: A partial computable function f:DY on effectively encoded sets X and Y, together with a computable total decoder for the chosen input encoding of X.

[L1]

By Computable and partial computable functions, some machine computes f, halting exactly on the inputs in D and outputting the correct value there.

[L2]

By A binary language is recognizable if and only if it is computably enumerable, it is enough to build recognizers for the binary code languages of the domain and range.

[L3]

By A dovetailing schedule reaches every finite simulation stage, the stage-sum schedule eventually reaches every finite simulation stage of every candidate input.

Proof

technique · direct
1.1

Let ED:={eX(x):xD}{0,1}. On an input word z{0,1}, run the computable decoder from the given data for the input encoding of X. If z is malformed, diverge forever. If z=eX(x) is valid, simulate the machine from [L1] on the same word z and accept exactly when that simulation halts. This recognizes exactly the binary language ED, so [L2] makes ED computably enumerable. Since ED consists exactly of the codes of elements of D, the same enumeration viewed through the fixed encoding eX witnesses that D is computably enumerable as a subset of X.

L1L2givenconstruct
1.2

Let ER:={eY(y):yf[D]}{0,1}. On an input word z{0,1}, dovetail the following branches over all binary words w in shortlex order: first run the computable decoder for the input encoding of X on w, and discard the branch if w is malformed; otherwise simulate the machine from [L1] on w. Accept as soon as some valid input code halts with output z. If z=eY(f(x)) for some xD, then [L3] ensures that the halting computation on the valid code eX(x) is eventually reached, so the recognizer accepts. If zER, no valid branch can witness acceptance. Thus ER is recognizable, [L2] makes it computably enumerable as a binary language, and therefore f[D] is computably enumerable as a subset of Y.

L1L2L3construct
2.1

Therefore both the domain and the range of a partial computable function are computably enumerable.

step 1.1step 1.2

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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