re_complete_of_le
theoremverifiedformalization
If p is RE-complete, q is recursively enumerable, and p many-one reduces to q, then q is RE-complete.
Statement
universe u in theorem re_complete_of_le {α β : Type*} [Primcodable α] [Primcodable β] {p : α → Prop} {q : β → Prop} (hp : REComplete.{_, u} p) (hq : REPred q) (h : p ≤₀ q) : REComplete.{_, u} q
- Formalizes
- standard textbook result (computability theory: an RE set that an RE-complete set reduces to is RE-complete)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- RECompleteA predicate
pis RE-complete if it is recursively enumerable and every recursively enumerable predicate many-one reduces top.
- RECompleteA predicate
Lean source view module on GitHub
universe u in /-- If p is RE-complete, q is RE, and p ≤₀ q, then q is RE-complete (for predicates in the same universe). -/ theorem re_complete_of_le {α β : Type*} [Primcodable α] [Primcodable β] {p : α → Prop} {q : β → Prop} (hp : REComplete.{_, u} p) (hq : REPred q) (h : p ≤₀ q) : REComplete.{_, u} q := ⟨hq, fun _ hr => (hp.2 _ hr).trans h⟩