Computably enumerable sets and total Turing oracles
Definitionfriedberg_muchnik_setsLet , where . A set is computably enumerable when there is a partial recursive procedure that halts exactly on its members. A set is computable when its membership predicate has a total computable Boolean decision function.
The total characteristic-function oracle for is
Define by partial recursiveness of relative to oracle . Both characteristic functions are defined on every natural input. Define Turing equivalence by reducibility in both directions, and define Turing incomparability by nonreducibility in both directions. The degree of a set is the equivalence class of its characteristic-function oracle in the quotient of partial functions by mutual Turing reducibility. A degree is computably enumerable when it is represented by a computably enumerable set.
These definitions provide the set and oracle interface for the existence theorem. They impose no computability assumption on an arbitrary oracle set.
Formalization Note This bundle preserves the eight supplied definitions in namespace Computability. PFun.lift embeds the total natural-number-valued characteristic function into the partial-function type used by Mathlib; the noncomputable marker allows its definition for arbitrary sets and does not imply that the oracle is computable.
import Mathlib.Computability.RE
import Mathlib.Computability.TuringDegree
open scoped Computability
namespace Computability
/-- A set of naturals is computably enumerable (c.e., r.e.). -/
def CEnumerable (A : Set ℕ) : Prop :=
REPred (fun n : ℕ => n ∈ A)
/-- A set of naturals is computable/recursive/decidable. -/
def ComputableSet (A : Set ℕ) : Prop :=
ComputablePred (fun n : ℕ => n ∈ A)
/-- The total characteristic function, represented as a partial-function oracle. -/
noncomputable def setOracle (A : Set ℕ) : ℕ →. ℕ := by
classical
exact PFun.lift (fun n : ℕ => if n ∈ A then 1 else 0)
/-- Turing reducibility between the total characteristic-function oracles. -/
def SetTuringReducible (A B : Set ℕ) : Prop :=
setOracle A ≤ᵀ setOracle B
/-- Two sets have the same Turing degree. -/
def SetTuringEquivalent (A B : Set ℕ) : Prop :=
SetTuringReducible A B ∧ SetTuringReducible B A
/-- Two sets have incomparable Turing degrees. -/
def TuringIncomparable (A B : Set ℕ) : Prop :=
¬ SetTuringReducible A B ∧
¬ SetTuringReducible B A
/-- The Turing degree of the total characteristic-function oracle. -/
noncomputable def degreeOfSet (A : Set ℕ) : TuringDegree :=
toAntisymmetrization TuringReducible (setOracle A)
/-- A Turing degree is c.e. if it contains a c.e. set. -/
def CEnumerableDegree (d : TuringDegree) : Prop :=
∃ A : Set ℕ,
CEnumerable A ∧ degreeOfSet A = d
end Computability
Read-back
What the Lean code literally says, in plain math · GPT-6 (independent Codex auditor)
CEnumerable. For any set , this proposition says that the partial function from to a one-element set which returns that sole element exactly when its input belongs to , and is undefined otherwise, is partial recursive. Thus its domain is exactly . Inputs include , and may be empty, in which case this is the nowhere-defined partial function, or all of , in which case it is the total constant function.
ComputableSet. For any set , this proposition says that there exists an assignment of a correct decision of to every natural number , such that the resulting total Boolean function, which returns true when and false when , is computable. The decision is required for every input, including ; the set is unrestricted and may be empty or all of .
setOracle. For any set , this defines a partial function whose domain is all of and whose value at each natural number , including , is if and if . It is the total characteristic function placed in the type of partial functions. The definition takes an arbitrary set , with no computability assumption; for the empty set it is constantly , and for it is constantly .
SetTuringReducible. For any two sets , this proposition says that the total function , defined by when and otherwise, is partial recursive relative to the single oracle , defined by when and otherwise. Relative partial recursiveness here is the class of partial functions generated by the constant-zero function, successor, the two natural-number pairing projections, and that oracle, under pairing of outputs, composition, primitive recursion, and unbounded minimization. Membership in this class is required for as a partial function, so the resulting computation is defined with the indicated value on every natural input, including . Both sets are arbitrary and may be empty or all of .
SetTuringEquivalent. For any two sets , this proposition is the conjunction of the following two assertions: the total function that returns on members of and on nonmembers is partial recursive relative to the sole oracle that returns on members of and on nonmembers; and the latter total function is partial recursive relative to the former as its sole oracle. In each direction, relative partial recursiveness allows the constant-zero function, successor, natural-number pairing projections, and the stated oracle, together with pairing, composition, primitive recursion, and unbounded minimization. Each resulting computation must have the prescribed value on every natural input, including . There are no restrictions on or , so empty sets and are included.
TuringIncomparable. For any two sets , let and be the total natural-number-valued functions that return on membership in their respective sets and on nonmembership. This proposition says both that is not partial recursive relative to the sole oracle and that is not partial recursive relative to the sole oracle . In each negated assertion, relative partial recursiveness means belonging to the class generated by constant zero, successor, natural-number pairing projections, and the stated oracle, under pairing, composition, primitive recursion, and unbounded minimization; membership would require the correct value at every natural input, including . The sets are unrestricted, including the possibility ; in that case the stated conjunction is false because an oracle itself is among the allowed functions.
degreeOfSet. For any set , this defines the equivalence class of the everywhere-defined partial function with value on members of and on nonmembers. The class is taken in the quotient of all partial functions from to by the equivalence relation that identifies and precisely when is partial recursive relative to the sole oracle and is partial recursive relative to the sole oracle . Relative partial recursiveness uses constant zero, successor, natural-number pairing projections, the stated oracle, and closure under pairing, composition, primitive recursion, and unbounded minimization. The quotient includes partial functions with arbitrary domains; the particular representative used here is defined at every natural number, including . The set may be empty or all of .
CEnumerableDegree. For any element of the quotient of all partial functions under mutual partial recursiveness relative to one another as sole oracles, this proposition says that there exists a set satisfying both of the following conditions: the partial function into a one-element set that returns its sole element exactly at the inputs in is partial recursive; and the equivalence class of the total function , which returns when its input belongs to and otherwise, equals . In the quotient relation, being partial recursive relative to an oracle means being generated from constant zero, successor, natural-number pairing projections, and that oracle, using pairing, composition, primitive recursion, and unbounded minimization. All natural inputs, including , are included; the witness set may be empty or all of , and its existence is required without a uniqueness condition.