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 AP is recognizable, then there exists a finite set FA such that every recognizable language B with FB also belongs to P.

Facts & Assumptions

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

[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.1

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

L2
1.2

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 F0F1 with sFs=A.

givenconstruct
2.1

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 xNx total and computable. If xATM then L(Nx)=AP; if xATM then L(Nx)=FsP for the finite stage s at which that simulation stops admitting new words.

L1L2L3step 1.2assume-contraconstruct
3.1

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 FA with FP.

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

Let B be recognizable with FB, and suppose for contradiction that BP. 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 xATM gives L(Kx)=FP, while xATM gives L(Kx)=FB=BP. As in step 3.1, the total computable map xKx 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.

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

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