Alphabeta Math
Pipeline-generated
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.

✓ 3 results · all verified · 2 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Oracle Computability, the Jump, and Turing Degrees: Examples and Counterexamples

1 · Prerequisites

2 · Summary

These examples make quotienting by Turing equivalence, nonuniform oracle use, and the finite nature of a concrete oracle transcript explicit.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-07Open item page →

Changing representatives of a degree comparison

Example

Let A~=A⊕∅ and B~=B⊕∅. The tags can be ignored or supplied as constant 0 bits, so A≡TA~ and B≡TB~. Thus a comparison A≤TB gives the same degree comparison when these particular representatives are replaced by A~ and B~.

Facts & Assumptions

Given: sets A,B⊆N and their zero-padded tagged versions.

Verification

technique · direct
1.1

A A~-oracle decides A by even queries, while an A-oracle decides A~ by querying A on even inputs and returning 0 on odd inputs. Thus A≡TA~, and likewise B≡TB~.

givenconstruct
2.1

The degree order is representative-independent now yields A≤TB iff A~≤TB~.

step 1.1∎
ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-07Open item page →

A Turing reduction without a truth table

Example

Set X=0′. The non-domination argument guarantees at least one set Y≤TX which has no everywhere-total oracle functional computing it from X. This is an existence example: a Turing computation may need an oracle-dependent amount of information before it knows its answer.

Facts & Assumptions

Given: X=0′.

Verification

technique · direct
1.1

Some Turing reductions are not truth-table reductions supplies a set Y such that Y≤TX and Y̸≤ttX.

given
2.1

By Truth-table reduction, that failure says no functional computing Y from X is total on every possible oracle.

step 1.1∎
CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-07Open item page →

A finite oracle-query transcript

Statement refuted

A computation deciding whether 7 belongs to its oracle must read every bit of that oracle.

Counterexample

technique · direct

Given: an oracle X.

1.1

The machine that queries only 7 and returns the answer decides this predicate for every oracle X. Its transcript has the single query 7.

givenconstruct
2.1

Any two oracles agreeing at 7 give exactly the same run and output, even if they differ elsewhere. This finite witness refutes the claimed whole-oracle read.

step 1.1∎

Sources