Closed classes are fixed
NOT A NOVELTY CLAIM. This is a machine-checked formalisation, checked by the Lean 4 kernel and resting on no axiom beyond propext and Quot.sound. It is dated and citable. Prior art, where it exists, is cited below. No discovery is claimed.
A class whose every member's complement is again a member is fixed by σ — the property P and PSPACE have because a deterministic decider's answer can be flipped (Arora–Barak §2.6; Sipser §7). The model takes the closure as the hypothesis; it does not define P by machines.
Proposition
∀ C : Class, (∀ L, C L → C (compl L)) → σ C = CProof
By fun C h => (fixed_points_are_the_closed_classes C).mpr h in p-vs-np.lean. Checked by the Lean kernel.
- Debit
closed_classes_are_fixed— this theorem- Credit
Quot.sound:∀ {α : Sort u_1} {r : α → α → Prop} {a b : α}, r a b → Quot.mk r a = Quot.mk r b— a quotient makes equal what its relation relates — the axiom behind function extensionalitypropext:∀ {a b : Prop}, (a ↔ b) → a = b— two propositions that imply each other are the same proposition
Sources and identifiers
- Lean source · src/4/p-vs-np.lean
- Typeset paper · src/research/lean-theorems.tex
- Repository deposit · doi:10.5281/zenodo.21787144
- Author · ORCID 0009-0000-7312-9778
- Deposit record ·
p-vs-np--closed_classes_are_fixed