AFTD Auto-Formalizing Theoretical Domains

karp_reducible_refl

theoremverified

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.

  1. 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).

    line 3

    uses Turing.idComputableInPolyTime, Iff.rfl

      exact ⟨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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it