Docs / Logic / Consequence / Basic

Consequence

import Linglib.Logic.Consequence.Basic · namespace Consequence

The semantics of a logic is a relation of satisfaction between models and formulas. A formula $\varphi$ is a consequence of a set $\Gamma$ of formulas when every model satisfying $\Gamma$ satisfies $\varphi$. Taking consequences is a closure operator on sets of formulas: a set entails its members, consequences survive added premises, and what follows from consequences of $\Gamma$ follows from $\Gamma$. Consequence transfers along a map of models that preserves and reflects satisfaction, so it survives restriction to a class of admissible models.

Implementation notes

  • A notion of satisfaction is a relation Model → Formula → Prop. A logic states its consequence relation as Γ ⊨[p] φ for its own satisfaction relation p, with everything its definition quantifies over bundled into the model type.
  • The models of a set of formulas and the theory of a class of models are the polars lowerPolar p Γ and upperPolar p K of Mathlib.Order.Concept, without names of their own.
  • Premises are sets, as theories are in Mathlib.ModelTheory, so the order and multiplicity of premises play no role and consequence is monotone in them. The order-sensitive consequence relations of update semantics take lists of updates and are in Semantics/Dynamic/Consequence.lean.

References

  • Tarski 1956, Logic, Semantics, Metamathematics: Papers from 1923 to 1938

Declarations

Γ ⊨[p] φ: the formula φ is a consequence of Γ when every model satisfying all of Γ satisfies φ.

def EntailsL46–49
{Model : Type u_1} {Formula : Type u_2} (p : Model → Formula → Prop) (Γ : Set Formula) (φ : Formula) :
  • Entails p Γ φ = ∀ (M : Model), (∀ γ ∈ Γ, p M γ) → p M φ

Used by entails_iff_mem_intentClosure, Entails.of_mem, Entails.weaken, Entails.trans, Entails.comap, Entails.restrict

Used in Logic/Consequence/Mixed, Logic/Orthologic/Epistemic/FrameSemantics, Logic/Orthologic/FrameSemantics, Logic/Team/BSML/Defs, Semantics/Modality/DomainSemantics

L51

The consequences of Γ are its closure under the closure operator of the satisfaction relation, so consequence is extensive, monotone and idempotent (Tarski 1956, Axioms 2 and 3 of On some fundamental concepts of metamathematics).

theorem entails_iff_mem_intentClosureL53–57
{Model : Type u_1} {Formula : Type u_2} {p : Model → Formula → Prop} {Γ : Set Formula} {φ : Formula} :
Entails p Γ φ ↔ φ ∈ (intentClosure p) Γ

Built from

theorem Entails.of_memL61
{Model : Type u_1} {Formula : Type u_2} {p : Model → Formula → Prop} {Γ : Set Formula} {φ : Formula} (h : φ ∈ Γ) :
Entails p Γ φ

Built from

Whatever follows from consequences of Γ follows from Γ.

theorem Entails.transL66–68
{Model : Type u_1} {Formula : Type u_2} {p : Model → Formula → Prop} {Γ Θ : Set Formula} {φ : Formula} (h₁ : ∀ θ ∈ Θ, Entails p Γ θ) (h₂ : Entails p Θ φ) :
Entails p Γ φ

Built from

Consequence transfers along a map of models that preserves and reflects satisfaction.

theorem Entails.comapL70–73
{Model : Type u_1} {Formula : Type u_2} {p : Model → Formula → Prop} {Γ : Set Formula} {φ : Formula} {Model' : Type u_3} {p' : Model' → Formula → Prop} (f : Model' → Model) (hf : ∀ (M : Model') (ψ : Formula), p' M ψ ↔ p (f M) ψ) (h : Entails p Γ φ) :
Entails p' Γ φ

Built from

Consequence over all models holds over any class of them.

theorem Entails.restrictL75–77
{Model : Type u_1} {Formula : Type u_2} {p : Model → Formula → Prop} {Γ : Set Formula} {φ : Formula} (K : Model → Prop) (h : Entails p Γ φ) :
Entails (fun (M : { M : Model // K M }) => p ↑M) Γ φ

Built from