Canonical model for classical first-order logic

Main reference: Jeremy Avigad, Algebraic proofs of cut elimination [Avi01]

@[implicit_reducible]

instance LO.FirstOrder.Derivation.Canonical.instLESequent {L : Language} : LE (Sequent L)

Equations

• LO.FirstOrder.Derivation.Canonical.instLESequent = { le := fun (q p : LO.FirstOrder.Sequent L) => Nonempty (LO.FirstOrder.Derivation.Canonical.StrongerThan q p) }

@[implicit_reducible]

instance LO.FirstOrder.Derivation.Canonical.instPreorderSequent {L : Language} : Preorder (Sequent L)

Equations

• One or more equations did not get rendered due to their size.

def LO.FirstOrder.Derivation.Canonical.ConsistentSequent (L : Language) : Type u_1

Equations

• LO.FirstOrder.Derivation.Canonical.ConsistentSequent L = { Γ : LO.FirstOrder.Sequent L // IsEmpty (⊢ᴸᴷ¹ ∼Γ) }

@[implicit_reducible]

instance LO.FirstOrder.Derivation.Canonical.ConsistentSequent.instPreorder {L : Language} : Preorder (ConsistentSequent L)

Equations

• One or more equations did not get rendered due to their size.

def LO.FirstOrder.Derivation.Canonical.ConsistentSequent.nil {L : Language} : ConsistentSequent L

Equations

• LO.FirstOrder.Derivation.Canonical.ConsistentSequent.nil = ⟨[], ⋯⟩

@[implicit_reducible]

instance LO.FirstOrder.Derivation.Canonical.ConsistentSequent.instOrderTop {L : Language} : OrderTop (ConsistentSequent L)

Equations

• LO.FirstOrder.Derivation.Canonical.ConsistentSequent.instOrderTop = { top := LO.FirstOrder.Derivation.Canonical.ConsistentSequent.nil, le_top := ⋯ }

def LO.FirstOrder.Derivation.Canonical.ConsistentSequent.ofUnprovable {L : Language} (φ : Proposition L) (h : 𝐋𝐊¹ ⊬ ∼φ) : ConsistentSequent L

Equations

• LO.FirstOrder.Derivation.Canonical.ConsistentSequent.ofUnprovable φ h = ⟨[φ], ⋯⟩

@[reducible, inline]

abbrev LO.FirstOrder.Derivation.Canonical.IsForced {L : Language} (p : ConsistentSequent L) (φ : Propositionᵢ L) : Prop

Equations

• LO.FirstOrder.Derivation.Canonical.IsForced p φ = Nonempty (LO.FirstOrder.Derivation.Canonical.Forces (↑p) φ)

@[implicit_reducible]

instance LO.FirstOrder.Derivation.Canonical.instForcingRelationConsistentSequentPropositionᵢ {L : Language} : ForcingRelation (ConsistentSequent L) (Propositionᵢ L)

Equations

• LO.FirstOrder.Derivation.Canonical.instForcingRelationConsistentSequentPropositionᵢ = { Forces := LO.FirstOrder.Derivation.Canonical.IsForced }

@[implicit_reducible]

instance LO.FirstOrder.Derivation.Canonical.instWeakForcingRelationConsistentSequentProposition {L : Language} : WeakForcingRelation (ConsistentSequent L) (Proposition L)

Equations

• One or more equations did not get rendered due to their size.

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsForced.rel {L : Language} {p : ConsistentSequent L} {k : ℕ} {R : L.Rel k} {v : Fin k → Semiterm L ℕ 0} : p ⊩ Semiformulaᵢ.rel R v ↔ Nonempty (⊢ᴸᴷ¹ Semiformula.rel R v :: ∼↑p)

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsForced.fal {L : Language} {φ : Semipropositionᵢ L (0 + 1)} {p : ConsistentSequent L} : p ⊩ ∀¹ φ ↔ ∀ (t : Semiterm L ℕ 0), p ⊩ φ/[t]

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsForced.and {L : Language} {p : ConsistentSequent L} {φ ψ : Propositionᵢ L} : p ⊩ φ ⋏ ψ ↔ p ⊩ φ ∧ p ⊩ ψ

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsForced.or {L : Language} {p : ConsistentSequent L} {φ ψ : Propositionᵢ L} : p ⊩ φ ⋎ ψ ↔ p ⊩ φ ∨ p ⊩ ψ

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsForced.not_falsum {L : Language} (p : ConsistentSequent L) : ¬p ⊩ ⊥

theorem LO.FirstOrder.Derivation.Canonical.IsForced.imply {L : Language} {p : ConsistentSequent L} {φ ψ : Propositionᵢ L} : p ⊩ φ 🡒 ψ ↔ ∀ q ≤ p, q ⊩ φ → q ⊩ ψ

theorem LO.FirstOrder.Derivation.Canonical.IsForced.not {L : Language} {p : ConsistentSequent L} {φ : Propositionᵢ L} : p ⊩ ∼φ ↔ ∀ q ≤ p, ¬q ⊩ φ

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsForced.exs {L : Language} {φ : Semipropositionᵢ L (0 + 1)} {p : ConsistentSequent L} : p ⊩ ∃¹ φ ↔ ∃ (t : Semiterm L ℕ 0), p ⊩ φ/[t]

theorem LO.FirstOrder.Derivation.Canonical.IsForced.monotone {L : Language} {p q : ConsistentSequent L} (hqp : q ≤ p) {φ : Propositionᵢ L} (hφ : p ⊩ φ) : q ⊩ φ

instance LO.FirstOrder.Derivation.Canonical.IsForced.instIntKripkeConsistentSequentPropositionᵢGe {L : Language} : ForcingRelation.IntKripke (ConsistentSequent L) fun (x1 x2 : ConsistentSequent L) => x1 ≥ x2

theorem LO.FirstOrder.Derivation.Canonical.IsForced.sound_minimal {L : Language} {φ : Propositionᵢ L} : 𝗠𝗶𝗻¹ ⊢ φ → ConsistentSequent L ∀⊩ φ

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.iff_isForced {L : Language} {φ : Proposition L} {p : ConsistentSequent L} : p ⊩ᶜ φ ↔ p ⊩ Semiformula.doubleNegation φ

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.dn_neg_iff {L : Language} {φ : Proposition L} {p : ConsistentSequent L} : p ⊩ᶜ ∼φ ↔ p ⊩ ∼Semiformula.doubleNegation φ

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.verum {L : Language} (p : ConsistentSequent L) : p ⊩ᶜ ⊤

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.falsum {L : Language} (p : ConsistentSequent L) : ¬p ⊩ᶜ ⊥

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.not {L : Language} {φ : Proposition L} {p : ConsistentSequent L} : p ⊩ᶜ ∼φ ↔ ∀ q ≤ p, ¬q ⊩ᶜ φ

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.and {L : Language} {φ ψ : Proposition L} {p : ConsistentSequent L} : p ⊩ᶜ φ ⋏ ψ ↔ p ⊩ᶜ φ ∧ p ⊩ᶜ ψ

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.or {L : Language} {φ ψ : Proposition L} {p : ConsistentSequent L} : p ⊩ᶜ φ ⋎ ψ ↔ ∀ q ≤ p, ∃ r ≤ q, r ⊩ᶜ φ ∨ r ⊩ᶜ ψ

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.all {L : Language} {φ : Semiproposition L 1} {p : ConsistentSequent L} : p ⊩ᶜ ∀¹ φ ↔ ∀ (t : Semiterm L ℕ 0), p ⊩ᶜ φ/[t]

@[simp]

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.exs {L : Language} {φ : Semiproposition L 1} {p : ConsistentSequent L} : p ⊩ᶜ ∃¹ φ ↔ ∀ q ≤ p, ∃ r ≤ q, ∃ (t : Semiterm L ℕ 0), r ⊩ᶜ φ/[t]

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.monotone {L : Language} {φ : Proposition L} {p q : ConsistentSequent L} (h : q ≤ p) : p ⊩ᶜ φ → q ⊩ᶜ φ

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.gnericity {L : Language} {φ : Proposition L} {p : ConsistentSequent L} : p ⊩ᶜ φ ↔ ∀ q ≤ p, ∃ r ≤ q, r ⊩ᶜ φ

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.complete {L : Language} {φ : Proposition L} : ConsistentSequent L ∀⊩ᶜ φ ↔ 𝐋𝐊¹ ⊢ φ

theorem LO.FirstOrder.Derivation.Canonical.IsWeaklyForced.refl {L : Language} (φ : Proposition L) (h : 𝐋𝐊¹ ⊬ ∼φ) : ConsistentSequent.ofUnprovable φ h ⊩ᶜ φ