karp_reducible_refl
Every language L over a finite alphabet Γ Karp-reduces to itself: the reduction is the identity function on words, which is computed by the identity Turing machine in a constant number of steps, and w ∈ L if and only if w ∈ L.
Statement
theorem karp_reducible_refl {Γ : Type} [Fintype Γ] (L : Language Γ) : KarpReducible Γ Γ L L
- Source
- Karp 1972 (reflexivity of ≤_p); Mathlib: Turing.idComputableInPolyTime
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- KarpReducibleA language L over an alphabet Γ Karp-reduces (polynomial-time many-one reduces) to a language L' over an alphabet Γ' if there is a…
Read back from the Lean
For every type Γ that is finite (the instance binder [Fintype Γ] says Γ carries a Fintype structure), and for every language L over Γ (L : Language Γ, i.e. a set of words/lists over Γ, so w ∈ L means w : List Γ lies in L), it is asserted that L Karp-reduces to itself, KarpReducible Γ Γ L L.
Unfolding the conclusion literally, the assertion is: there exists a function f : List Γ → List Γ such that
(a) Nonempty (Turing.TM2ComputableInPolyTime (id : List Γ → List Γ) (id : List Γ → List Γ) f) — i.e. f is computable by a two-tape Turing machine (the TM2 model) in polynomial time, where both the input encoding and the output encoding are the identity function on List Γ; and
(b) for every w : List Γ, w ∈ L ↔ f w ∈ L.
Quantifier order and binder structure, explicitly: ∀ Γ (Fintype Γ) (L : Language Γ), ∃ f : List Γ → List Γ, (Nonempty (poly-time-TM2-computable id id f)) ∧ (∀ w : List Γ, w ∈ L ↔ f w ∈ L). The type Γ is the same in both argument slots of KarpReducible, so this is only the self-reduction (reflexivity) instance.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that any language L over a finite alphabet Γ is Karp-reducible to itself, we exhibit the identity function on words as the reduction. The identity function is computable in polynomial time by a Turing machine via Turing.idComputableInPolyTime, and the condition w ∈ L ↔ id(w) ∈ L holds reflexively by Iff.rfl.
L Karp-reduces to itself via the identity function on words.
By definition, a Karp reduction from L to L requires a function f : List Γ → List Γ, a certificate that f is computable in polynomial time, and a proof that w ∈ L ↔ f w ∈ L for all words w. Choosing f to be the identity function id satisfies all three requirements: polynomial-time computability is provided by Turing.idComputableInPolyTime, and the membership equivalence w ∈ L ↔ id w ∈ L reduces to w ∈ L ↔ w ∈ L, which holds by reflexivity (Iff.rfl).
uses
Turing.idComputableInPolyTime,Iff.rflexact ⟨id, ⟨Turing.idComputableInPolyTime id⟩, fun _ => Iff.rfl⟩
Turing.idComputableInPolyTime- The identity function on words is computable in polynomial time by a multi-tape Turing machine.
Iff.rfl- Logical equivalence is reflexive: every proposition implies and is implied by itself (a ↔ a).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- Karp reducibility is reflexive: every language over a finite alphabet reduces to itself by the identity. -/theorem karp_reducible_refl {Γ : Type} [Fintype Γ] (L : Language Γ) : KarpReducible Γ Γ L L := by exact ⟨id, ⟨Turing.idComputableInPolyTime id⟩, fun _ => Iff.rfl⟩