not_re_of_manyOneReducible_and_not_re
theoremverifiedformalization
If p is many-one reducible to q and p is not recursively enumerable, then q is not recursively enumerable.
Statement
theorem not_re_of_manyOneReducible_and_not_re {α β : Type*} [Primcodable α] [Primcodable β] {p : α → Prop} {q : β → Prop} (h : p ≤₀ q) (hp : ¬REPred p) : ¬REPred q
- Formalizes
- standard textbook result (computability theory: non-RE-ness transfers along many-one reductions)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- re_of_manyOneReducibleIf
pis many-one reducible toqandqis recursively enumerable, thenpis recursively enumerable.
- re_of_manyOneReducibleIf
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- If p reduces to q and p is not RE, then q is not RE. -/theorem not_re_of_manyOneReducible_and_not_re {α β : Type*} [Primcodable α] [Primcodable β] {p : α → Prop} {q : β → Prop} (h : p ≤₀ q) (hp : ¬REPred p) : ¬REPred q := by intro hq exact hp (re_of_manyOneReducible h hq)