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 be a partial computable function on effectively encoded sets and , and assume that the chosen total decoder for the input encoding of is itself computable. Then its domain and its range are computably enumerable.
Facts & Assumptions
Given: A partial computable function on effectively encoded sets and , together with a computable total decoder for the chosen input encoding of .
By Computable and partial computable functions, some machine computes , halting exactly on the inputs in and outputting the correct value there.
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.
By A dovetailing schedule reaches every finite simulation stage, the stage-sum schedule eventually reaches every finite simulation stage of every candidate input.
Proof
Let . On an input word , run the computable decoder from the given data for the input encoding of . If is malformed, diverge forever. If is valid, simulate the machine from [L1] on the same word and accept exactly when that simulation halts. This recognizes exactly the binary language , so [L2] makes computably enumerable. Since consists exactly of the codes of elements of , the same enumeration viewed through the fixed encoding witnesses that is computably enumerable as a subset of .
Let . On an input word , dovetail the following branches over all binary words in shortlex order: first run the computable decoder for the input encoding of on , and discard the branch if is malformed; otherwise simulate the machine from [L1] on . Accept as soon as some valid input code halts with output . If for some , then [L3] ensures that the halting computation on the valid code is eventually reached, so the recognizer accepts. If , no valid branch can witness acceptance. Thus is recognizable, [L2] makes it computably enumerable as a binary language, and therefore is computably enumerable as a subset of .
Therefore both the domain and the range of a partial computable function are computably enumerable.
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
- Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)
- John Watrous, Introduction to the Theory of Computing, Lecture 18: Further discussion of computability (standard reference, not scraped)