FormalizedFormalLogic /Foundation

Formalization of Mathematical Logic

★ 299⑂ 32👁 9⑃ 818● 207▤ 1
LeanApache-2.0Created 2023-02-11formalizedformallogic.github.io/Foundation/
Download: Version 1Version-1 ↓12026-09-07
+0
Daily
299
stars
32
forks
9
watchers
818
prs
207
issues
1
releases

README

[Docs]: https://FormalizedFormalLogic.github.io/Foundation/docs
[Catalogue]: https://FormalizedFormalLogic.github.io/Catalogue

 Foundation




Formalizing mathematical logic in Lean 4.

 Structure & Summary

Main results of this repository. More detailed explanations are provided in [Docs].

- Logic: Fundamental notions shared by all logics (entailment, semantics, calculi, Lindenbaum algebras, …).
- Propositional: Propositional logic (classical and intuitionistic).
  - [Completeness of Tait calculus][prop:completeness]
- FirstOrder: [First-order logic][first_order]
  - [Completeness theorem][first_order:completeness]
  - [Cut-elimination of first-order sequent calculus _(Gentzen's Hauptsatz)_][first_order:hauptsatz]
  - [Gödel–Gentzen negative translation][first_order:goedel_translation]
  - [Downward Löwenheim–Skolem theorem][first_order:downward_loewenheim_skolem]
  - [Intuitionistic first-order logic and Kripke semantics][first_order:intuitionistic]
  - [Arithmetic][arith]: arithmetical theories ($\mathsf{PA^-}$, $\mathsf{I}\Sigma_n$, $\mathsf{I\Delta_0 + \Omega_1}$, $\mathsf{R_0}$, $\mathsf{Q}$, …), definability, exponentiation, hereditarily finite sets, and true arithmetic.
    - Arithmetic Theory Zoo
  - [Incompleteness][incompleteness]
    - Gödel's [First][arith:goedel_it1] and [Second][arith:goedel_it2] incompleteness theorems
    - [Gödel–Rosser's incompleteness theorem][arith:goedel_rosser]
    - [Löb's theorem][arith:loeb]
    - [Tarski's undefinability of truth][arith:tarski]
    - [Church's theorem and undecidability of first-order logic][arith:church]
  - [Set theory][set_theory]: $\mathsf{Z}$, $\mathsf{ZF}$, $\mathsf{ZFC}$ and their models.
    - [Consistency of ZFC][set_theory:zfc_consistent] (relative to Lean's type theory)
    - [Downward Löwenheim–Skolem theorem for models of set theory][set_theory:loewenheim_skolem]
- ProvabilityLogic: [Provability logic][provability_logic]
  - Arithmetical completeness theorems of [$\mathsf{GL}$][pl:gl_arith] and [$\mathsf{S}$][pl:s_arith], [$\mathsf{Grz}$][pl:grz_arith], and [$\mathsf{GL} + \Box^n \bot$][pl:glboxbot_arith]
  - [Classification of provability logics][pl:classification]
  - Provability Logic Zoo
- SecondOrder: Syntax, semantics, and derivations of second-order logic.
- Syntax: Syntax shared by first-order and second-order logic.
- Meta: Proof automation.
- Vorspiel: Supplemental definitions and theorems for Mathlib.

[prop:completeness]: ./Foundation/Propositional/Boolean/Tait.lean
[first_order]: ./Foundation/FirstOrder
[first_order:completeness]: ./Foundation/FirstOrder/LK/Completeness/CounterModel.lean
[first_order:hauptsatz]: ./Foundation/FirstOrder/LK/Hauptsatz.lean
[first_order:goedel_translation]: ./Foundation/FirstOrder/LJ/GoedelGentzen.lean
[first_order:downward_loewenheim_skolem]: ./Foundation/FirstOrder/Tarski/Skolemization.lean
[first_order:intuitionistic]: ./Foundation/FirstOrder/Kripke/Intuitionistic.lean
[arith]: ./Foundation/FirstOrder/Arithmetic
[incompletenes

Top issues

Discussions

Latest release

Version 1 v1 2026-09-07
Pinned version for S. Saitou and M. Noguchi, _"Mechanizing Gödel’s Incompleteness Theorems and Provability Logic"_ 2026

Snapshot: 2026-11-16T09:23:14Z · Data license Apache-2.0 · JSON