Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Friedberg–Muchnik theorem: two Turing incomparable c.e. sets

Proved
Computability.friedberg_muchnik

by tomasz · Sep 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

computability-theoryfriedberg-muchnikrecursively-enumerableturing-degrees

There exist two computably enumerable sets A,B⊆NA,B\subseteq\mathbb NA,B⊆N such that neither set is Turing reducible to the other:

∃A,B⊆N,A is c.e.  ∧  B is c.e.  ∧  A̸≤TB  ∧  B̸≤TA.\exists A,B\subseteq\mathbb N,\qquad A\text{ is c.e.}\;\land\;B\text{ is c.e.}\;\land\;A\not\le_T B\;\land\;B\not\le_T A.∃A,B⊆N,A is c.e.∧B is c.e.∧A≤T​B∧B≤T​A.

Here computable enumerability means that membership is semidecidable. The relation A≤TBA\le_T BA≤T​B means that a computation with access to the total membership oracle for BBB decides membership in AAA 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.

Preamble
import Definitions.Def_friedberg_muchnik_sets
Formal statement
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
Source
Richard M. Friedberg (1957), Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944), PNAS 43(2), 236–238. DOI: https://doi.org/10.1073/pnas.43.2.236; free archive: https://pmc.ncbi.nlm.nih.gov/articles/PMC528418/. Exact two-set statement and working proof reference: Arnold W. Miller, Lecture notes in Recursion Theory, December 3, 2008, Section 26, Theorem 26.2, statement p. 51, proof pp. 51–54: https://people.math.wisc.edu/~awmille1/old/m773-07/recthy.pdf#page=51. Earlier independent contribution: A. A. Muchnik (1956), On the unsolvability of the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk SSSR 108(2), 194–197 (Russian); Math-Net bibliography: https://www.mathnet.ru/rus/person46479.
Read-back

What the Lean code literally says, in plain math · GPT-6 (independent Codex auditor)

There exist sets A,B⊆NA,B\subseteq\mathbb{N}A,B⊆N, where N={0,1,2,…}\mathbb{N}=\{0,1,2,\ldots\}N={0,1,2,…}, such that the partial function from N\mathbb{N}N to the singleton set {∗}\{\ast\}{∗} that returns ∗\ast∗ exactly on inputs belonging to AAA and is undefined on all other inputs is partial recursive, and the corresponding partial function for BBB is also partial recursive. For each of these sets XXX, let χX:N→N\chi_X:\mathbb{N}\to\mathbb{N}χX​:N→N be the total characteristic function given by χX(n)=1\chi_X(n)=1χX​(n)=1 when n∈Xn\in Xn∈X and χX(n)=0\chi_X(n)=0χX​(n)=0 when n∉Xn\notin Xn∈/X, viewed as a partial function that is defined on every input. These sets satisfy both that χA\chi_AχA​ is not partial recursive with access to χB\chi_BχB​ as its oracle and that χB\chi_BχB​ is not partial recursive with access to χA\chi_AχA​ 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.

Human review
  • Endorsed by Shuze Chen · Sep 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by tomasz · Sep 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me