Alphabeta Math
LemmaStatement: AI-adaptedProof: 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.

A nontrivial extensional property admits a uniform witness machine construction

Statement

Let P be a nontrivial extensional property of recognizable languages. Then there exists a recognizable language W such that W and lie on opposite sides of P, and there is a total computable map g:{0,1}{0,1} with the following property: for every coded pair x=M,w^, if g(x)=Nx, then

  • when xATM one has L(Nx)=W, and
  • when xATM one has L(Nx)=.

Facts & Assumptions

Given: A nontrivial extensional property P.

[L1]

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.

[L2]

A coded pair belongs to ATM exactly when the coded machine accepts the coded input word, by The Turing-machine acceptance problem ATM.

Proof

technique · direct
1.1

If P, choose a recognizable language WP. If instead P, choose a recognizable language WP. In either case, this choice fixes a recognizable language W that lies on the opposite side of P from .

L1givenconstruct
2.1

Fix a recognizer RW for W. For each coded pair x=M,w^, build a machine Nx that on input y simulates M on w; if that simulation ever accepts, Nx starts a simulation of RW on y, and if the simulation of M never accepts then Nx never accepts y. Because the code of RW is fixed and x is inserted as data, the map xNx is total and computable.

L2step 1.1construct
3.1

If xATM, then [L2] says that M accepts w, so step 2.1 eventually releases the simulation of RW on every input y; hence L(Nx)=W. If xATM, the simulation of M on w never accepts, so Nx accepts no input and L(Nx)=. This is exactly the required witness-machine construction.

L2step 2.1

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