manyOneReducible_compl
theoremverifiedformalization
If a predicate p many-one reduces to q, then the complement of p many-one reduces to the complement of q.
Statement
theorem manyOneReducible_compl {α β : Type*} [Primcodable α] [Primcodable β] {p : α → Prop} {q : β → Prop} (h : p ≤₀ q) : (fun a => ¬p a) ≤₀ (fun b => ¬q b)
- Formalizes
- standard textbook result (computability theory: a many-one reduction also reduces the complements)
- Verified
- 06 Oct 2026
- Axioms
propext
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.
/-- Many-one reducibility is preserved under taking complements. -/theorem manyOneReducible_compl {α β : Type*} [Primcodable α] [Primcodable β] {p : α → Prop} {q : β → Prop} (h : p ≤₀ q) : (fun a => ¬p a) ≤₀ (fun b => ¬q b) := by rcases h with ⟨f, hf, hred⟩ exact ⟨f, hf, fun a => not_congr (hred a)⟩