Friedberg–Muchnik theorem: two Turing incomparable c.e. sets
ProvedComputability.friedberg_muchnikThere exist two computably enumerable sets such that neither set is Turing reducible to the other:
Here computable enumerability means that membership is semidecidable. The relation means that a computation with access to the total membership oracle for decides membership in on every input. Thus both possible directions of oracle computation are excluded. This is the two-set Friedberg–Muchnik theorem, matching Miller's Theorem 26.2 on page 51.
Formalization Note The target has no hypotheses and retains the supplied statement in namespace Computability. It uses Mathlib's REPred and Turing reducibility through the imported set definitions. The degree-quotient helpers are included in the definition bundle but are not needed to state this goal.
import Definitions.Def_friedberg_muchnik_sets
namespace Computability
/-- There are two computably enumerable sets of incomparable Turing degree. -/
theorem friedberg_muchnik :
∃ A B : Set ℕ,
CEnumerable A ∧
CEnumerable B ∧
TuringIncomparable A B := by sorry
end Computability
Read-back
What the Lean code literally says, in plain math · GPT-6 (independent Codex auditor)
There exist sets , where , such that the partial function from to the singleton set that returns exactly on inputs belonging to and is undefined on all other inputs is partial recursive, and the corresponding partial function for is also partial recursive. For each of these sets , let be the total characteristic function given by when and when , viewed as a partial function that is defined on every input. These sets satisfy both that is not partial recursive with access to as its oracle and that is not partial recursive with access to as its oracle; thus no algorithm using the first of these oracles computes the other characteristic function correctly on every natural-number input, in either direction.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.