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 universal Martin-Löf test exists
Statement
There is a Martin-Löf test such that every Martin-Löf test is contained in it after an index-dependent shift: for all .
Facts & Assumptions
Given: the acceptable numbering of partial computable functions and the uniform-enumeration convention for effectively open sequences.
Proof
Decode the outputs of the -th partial computable function as pairs , discarding malformed outputs. This enumerates a c.e. relation , and every c.e. relation occurs for some because Universal and acceptable numberings enumerates all partial computable functions. Hence the relations enumerate every uniformly effectively open candidate sequence.
For candidate , at component retain a newly enumerated cylinder only when the finite union retained so far would still have measure at most . The measure of a finite cylinder union is computable by reducing its strings to a finite prefix-free set. Thus the retained relation is uniformly c.e. and always obeys the component bound. If the candidate already is a Martin-Löf test, no cylinder is ever discarded, since every finite subunion has measure at most the final measure.
Let be the union of all retained -components at level . Dovetailing the enumerations makes uniformly effectively open, and subadditivity gives It is therefore a test by Martin-Löf tests and random sequences. If is a genuine test, step 2.1 does not trim it, so for all . Take to obtain the stated universality.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
2 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
- Simpson, Theorem 8.4.8 (standard reference, not scraped)