PM ✱1: literals of a valuation (for completeness)
DefinitionPM_core_valuation_literalsDRAFT — part of an in-progress public formalization of Principia Mathematica; it may still change, and every change is dated in the project's change log.
For a truth value and a formula , is if is true and otherwise. For a valuation and a variable , the literal is ; for a list of variables the literals are the list .
These are the hypotheses of Kalmár's lemma in the completeness proof of PM's ✱1 for truth tables (the card PM.meta_complete).
Source: PM.Complete.
Definition code
-- PM/Complete.lean at 2e43991fec42, without its theorems (skeleton subtraction);
-- generated by scripts/prove2me/export.py; every command kept is copied verbatim.
import Definitions.Def_PM_core_star1_system
import Definitions.Def_PM_core_statement_formulas
import Definitions.Def_PM_core_hypothetical_derivations
/-!
Kalmár-style completeness of PM's ✱1 system (stretch goal):
`theorem complete (p : F) (h : p.isTaut = true) : Thm p`
* `kalmar`: for a valuation `v` and a list `xs` containing the variables of `φ`, the literals
`x^v` (`x` if `v x`, else `∼x`) prove `φ^v` (`φ` if true under `v`, else `∼φ`).
* `elim`: if every assignment in `assignments xs` gives `Γ_v ⊢ φ`, then `⊢ φ`; one variable
at a time is discharged by the case split ✱2·11 (`Pf.cases`).
Only the rules of PM.Derived are used, so the result is an explicit `Thm` derivation, but it is
not one that follows PM's own proofs. PM.Replay2 does not use this theorem; it is an independent
check that the replayed system is complete for its truth-table semantics.
-/
namespace PM
open F Pf
/-! ## List lemmas, proved by hand so that nothing beyond the kernel is needed -/
section lists
variable {α : Type} {a : α}
end lists
/-! String-specific facts, proved from `String.decEq` (core's `LawfulBEq String` instance is not
axiom-free, so it is avoided). -/
/-! ## Kalmár's lemma -/
/-- `sgn b φ`: φ itself if `b`, else `∼φ`. -/
def sgn : Bool → F → F
| true, φ => φ
| false, φ => .neg φ
/-- The literal of variable `x` under `v`. -/
def lit (v : String → Bool) (x : String) : F := sgn (v x) (.var x)
/-- `lits v [x₁,…,xₙ] = [xₙ^v, …, x₁^v]` (the head variable is the last hypothesis). -/
def lits (v : String → Bool) : List String → List F
| [] => []
| x :: xs => lits v xs ++ [lit v x]
/-! ## Discharging the hypotheses -/
end PM
Source
Whitehead and Russell, Principia Mathematica, Vol. I (1910), ✱1–✱5; formalization: https://github.com/willmcginnis/principia-mathematica-lean/blob/2e43991fec4221198853c15ba637b6c8430cec4b/PM/Complete.lean