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.
A nontrivial extensional property admits a uniform witness machine construction
Statement
Let be a nontrivial extensional property of recognizable languages. Then there exists a recognizable language such that and lie on opposite sides of , and there is a total computable map with the following property: for every coded pair , if , then
- when one has , and
- when one has .
Facts & Assumptions
Given: A nontrivial extensional property .
A nontrivial extensional property has at least one recognizable witness language inside the property and at least one recognizable witness language outside it, by Index sets and extensional properties of Turing-machine languages.
A coded pair belongs to exactly when the coded machine accepts the coded input word, by The Turing-machine acceptance problem .
Proof
If , choose a recognizable language . If instead , choose a recognizable language . In either case, this choice fixes a recognizable language that lies on the opposite side of from .
Fix a recognizer for . For each coded pair , build a machine that on input simulates on ; if that simulation ever accepts, starts a simulation of on , and if the simulation of never accepts then never accepts . Because the code of is fixed and is inserted as data, the map is total and computable.
If , then [L2] says that accepts , so step 2.1 eventually releases the simulation of on every input ; hence . If , the simulation of on never accepts, so accepts no input and . This is exactly the required witness-machine construction.
Depends on
Used by
Dependency tree · two levels
8 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
- EECS 376 Course Notes, Part 6: Computability (standard reference, not scraped)
- H. G. Rice, Classes of Recursively Enumerable Sets and Their Decision Problems (standard reference, not scraped)