Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 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.

Recognizable extensional properties are positively witnessed by finite information

Statement

Let P be an extensional property of recognizable languages, and assume that its index set IP is recognizable. If A∈P is recognizable, then there exists a finite set F⊆A such that every recognizable language B with F⊆B also belongs to P.

Facts & Assumptions

Given: An extensional property P with recognizable index set, and a recognizable language A∈P.

[L1]

By Index sets and extensional properties of Turing-machine languages, membership in P depends only on the recognized language, so the property can be viewed through any recognizable presentation of the same language.

[L2]

The language ATM is recognizable but undecidable, by The Turing-machine acceptance problem is recognizable and The Turing-machine acceptance problem is undecidable. A language is decidable if and only if it and its complement are both recognizable, by A language is decidable if and only if it and its complement are recognizable.

[L3]

Machine descriptions have a fixed effective coding, and ATM contains exactly the codes of accepting machine-input pairs, by A fixed effective binary encoding of deterministic one-tape Turing machines and The Turing-machine acceptance problem ATM.

Proof

technique · direct
1.1L2

By [L2], ATM‾ is not recognizable: otherwise both ATM and its complement would be recognizable and hence ATM would be decidable.

1.2givenconstruct

Choose a recognizer for A, and let Σ be its finite input alphabet. Dovetail the recognizer on the words of Σ∗ in a fixed length-lexicographic order, outputting each newly accepted word once. This gives an effective enumeration of A by finite stages F0⊆F1⊆⋯ with ⋃sFs=A.

2.1L1L2L3step 1.2assume-contraconstruct

Suppose for contradiction that no finite subset of A belongs to P. For each binary word x, effectively construct a recognizer Nx that, on its own input y, simulates the stage enumeration from step 1.2 and the recognizer for ATM on x in lockstep. It accepts if y appears in the stage enumeration before the latter recognizer accepts, and otherwise continues forever. The coding in [L3] makes x↦⌜Nx⌝ total and computable. If x∉ATM then L(Nx)=A∈P; if x∈ATM then L(Nx)=Fs∉P for the finite stage s at which that simulation stops admitting new words.

3.1step 1.1step 2.1contradictiondischarge-contradiction: the assumed absence of a finite witness would recognize the complement of A_TM

A recognizer for IP could therefore recognize ATM‾: on input x, compute ⌜Nx⌝ and run the index-set recognizer on it. This contradicts step 1.1. Hence there is a finite set F⊆A with F∈P.

4.1L1L2L3step 1.1step 3.1assume-contraconstructdischarge-contradiction: an extension outside the property would recognize the complement of A_TM∎

Let B be recognizable with F⊆B, and suppose for contradiction that B∉P. For each binary word x, effectively build a recognizer Kx that accepts every word of F and, if the recognizer for ATM accepts x, also simulates a fixed recognizer for B. Then x∉ATM gives L(Kx)=F∈P, while x∈ATM gives L(Kx)=F∪B=B∉P. As in step 3.1, the total computable map x↦⌜Kx⌝ and the recognizer for IP would recognize ATM‾, contradicting step 1.1. Therefore every such B belongs to P, and F is the required finite positive witness.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

17 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