Docs / Logic / PIP / Semantics

Semantics of PIP

import Linglib.Logic.PIP.Semantics · namespace PIP

This file defines the value of a term and the truth of a formula of PIP in a model, relative to an assignment of pluralities to variables. Pluralities are sets of atoms. A variable denotes its assignment; set abstraction ⋃{x : φ} and summation Σxφ denote the union of the values of x over the assignments that agree with the current one outside the bound variables (for summation, also outside the local variables of φ) and satisfy φ. Presuppositions and label definitions do not affect truth, and an unexpanded label is false. A discourse φ₁, …, φₙ means Σw(φ₁ ∧ … ∧ φₙ) and is true iff that plurality of worlds is nonempty.

Both kinds of expression are realized by one recursion, Expr.Realize, as a relation to a point: an atom for a term, nothing for a formula.

Main definitions

Main statements

References

Declarations

A model: pluralities are sets of atoms α, and each n-ary relation symbol is interpreted over a world plurality and a tuple of n pluralities.

structure ModelL61–65
(P : ℕ → Type w) (α : Type u) :
Type (max u w)
  • I {n : ℕ} : P n → Set α → (Fin n → Set α) → Prop

    The interpretation of relation symbols.

Used by Expr.Realize, Term.realize, Formula.Realize, Term.mem_realize, Term.realize_var, Term.realize_bvar, Term.realize_inter, Term.realize_empty, Term.realize_presup, Term.mem_realize_abs, Term.mem_realize_sigma, Formula.realize_top, Formula.realize_atom, Formula.realize_rel, Formula.realize_eq, Formula.realize_subset, Formula.realize_mem, Formula.realize_sg, Formula.realize_pl, Formula.realize_neg, Formula.realize_conj, Formula.realize_ex, Formula.realize_presup, Formula.realize_labelDef, Formula.realize_label, Formula.realize_disj, Formula.realize_impl, Formula.realize_iff, Formula.realize_all, Formula.realize_some, Formula.realize_ex_iff_abs_nonempty, Term.realize_sigma_eq, Term.realize_sigma_eq_of_mem_locals, Term.realize_sigma_eq_image, Term.realize_sigma_eq_of_distributive, Expr.realize_congr, Formula.realize_congr, Model.Divisive, Term.exists_realize_eq_of_isVar, Expr.realize_of_isConjunctive, Term.realize_sigma_eq_of_isConjunctive, Formula.realize_closeList, Expr.realize_elim, Term.realize_elim, Formula.realize_elim

Used in Logic/PIP/Felicity, Logic/PIP/Intensional, AbneyKeshet2025, KeshetAbney2024

The meaning of the logical relations on pluralities. Membership s ∈ t holds when s is the singleton of an atom of t.

def LogicalRel.HoldsL73–80
{α : Type u_1} {n : ℕ} :
LogicalRel n → (Fin n → Set α) → Prop

Used by Expr.Realize, Formula.realize_rel

Realization: membership of an atom in the value of a term, and truth of a formula. A variable denotes its assignment, abstraction and summation the union of the values of the bound variable over assignments agreeing outside the bound variables; a formula is true classically, with presuppositions and label definitions transparent and an unexpanded label false.

def Expr.RealizeL86–108
{V : Type u} {L : Type v} {P : ℕ → Type w} {α : Type u_1} [DecidableEq V] (M : Model P α) (g : V → Set α) {k : Kind} :
Expr V L P k → Kind.Point α k → Prop
Equations

Built from , ,

Used by Term.realize, Formula.Realize, Term.mem_realize, Expr.realize_congr, Expr.realize_of_isConjunctive, Expr.realize_elim

The value of a term.

def Term.realizeL112–113
{V : Type u} {L : Type v} {P : ℕ → Type w} {α : Type u_1} [DecidableEq V] (M : Model P α) (g : V → Set α) (t : Term V L P) :
Set α

Built from ,

Used by Term.mem_realize, Term.realize_var, Term.realize_bvar, Term.realize_inter, Term.realize_empty, Term.realize_presup, Term.mem_realize_abs, Term.mem_realize_sigma, Formula.realize_atom, Formula.realize_rel, Formula.realize_eq, Formula.realize_subset, Formula.realize_mem, Formula.realize_sg, Formula.realize_pl, Formula.realize_some, Formula.realize_ex_iff_abs_nonempty, Term.realize_sigma_eq, Term.realize_sigma_eq_of_mem_locals, Term.realize_sigma_eq_image, Term.realize_sigma_eq_of_distributive, Term.exists_realize_eq_of_isVar, Term.realize_sigma_eq_of_isConjunctive, Term.realize_elim

Used in Logic/PIP/Felicity, Logic/PIP/Intensional, AbneyKeshet2025, KeshetAbney2024

Truth of a formula.

def Formula.RealizeL115–116
{V : Type u} {L : Type v} {P : ℕ → Type w} {α : Type u_1} [DecidableEq V] (M : Model P α) (g : V → Set α) (φ : Formula V L P) :

Built from ,

Used by Term.mem_realize_abs, Term.mem_realize_sigma, Formula.realize_top, Formula.realize_atom, Formula.realize_rel, Formula.realize_eq, Formula.realize_subset, Formula.realize_mem, Formula.realize_sg, Formula.realize_pl, Formula.realize_neg, Formula.realize_conj, Formula.realize_ex, Formula.realize_presup, Formula.realize_labelDef, Formula.realize_label, Formula.realize_disj, Formula.realize_impl, Formula.realize_iff, Formula.realize_all, Formula.realize_some, Formula.realize_ex_iff_abs_nonempty, Term.realize_sigma_eq, Term.realize_sigma_eq_of_mem_locals, Term.realize_sigma_eq_image, Term.realize_sigma_eq_of_distributive, Formula.realize_congr, Term.realize_sigma_eq_of_isConjunctive, Formula.realize_closeList, Formula.realize_elim

Used in Logic/PIP/Felicity, Logic/PIP/Intensional, AbneyKeshet2025, KeshetAbney2024

L118–119
L121
L123
L128
L133–135
L137–140
L176–178
L186–187

Derived clauses

L205–207

∃xφ is true iff ⋃{x : φ} is nonempty, provided φ is false when x is the null plurality, the standing assumption that predicates are false of the null individual.

theorem Formula.realize_ex_iff_abs_nonemptyL213–222
{V : Type u} {L : Type v} {P : ℕ → Type w} {α : Type u_1} [DecidableEq V] (M : Model P α) (g : V → Set α) (x : V) (φ : Formula V L P) (h : ¬Realize M (Function.update g x ∅) φ) :
Realize M g (Expr.ex x φ) ↔ (Term.realize M g (Expr.abs x φ)).Nonempty

Built from , ,

The value of a summation whose body, on the assignments agreeing outside the summation variable and its locals, depends on the summation variable's value alone: the sum of the pluralities satisfying that condition.

theorem Term.realize_sigma_eqL224–239
{V : Type u} {L : Type v} {P : ℕ → Type w} {α : Type u_1} [DecidableEq V] (M : Model P α) (g : V → Set α) {x : V} {φ : Formula V L P} {B : Set α → Prop} (hφ : ∀ (g' : V → Set α), Set.EqOn g' g {y : V | y ∉ Expr.locals φ ∧ y ≠ x} → (Formula.Realize M g' φ ↔ B (g' x))) :
realize M g (Expr.sigma x φ) = ⋃₀ {X : Set α | B X}

Built from , ,

The value of a summation whose body depends on the summation variable's value and on that of a local variable y: the sum of the pluralities related to some plurality, the local being summed away.

theorem Term.realize_sigma_eq_of_mem_localsL241–260
{V : Type u} {L : Type v} {P : ℕ → Type w} {α : Type u_1} [DecidableEq V] (M : Model P α) (g : V → Set α) {x y : V} (hxy : y ≠ x) {φ : Formula V L P} {C : Set α → Set α → Prop} (hφ : ∀ (g' : V → Set α), Set.EqOn g' g {z : V | z ∉ Expr.locals φ ∧ z ≠ x} → (Formula.Realize M g' φ ↔ C (g' x) (g' y))) (hy : y ∈ Expr.locals φ) :
realize M g (Expr.sigma x φ) = ⋃₀ {X : Set α | ∃ (Y : Set α), C X Y}

Built from , ,

A summation over a singular description, true of the singletons of the images of s: the plurality of those images.

theorem Term.realize_sigma_eq_imageL262–271
{V : Type u} {L : Type v} {P : ℕ → Type w} {α : Type u_1} [DecidableEq V] (M : Model P α) (g : V → Set α) {β : Type u_2} {x : V} {φ : Formula V L P} {f : β → α} {s : Set β} (hφ : ∀ (g' : V → Set α), Set.EqOn g' g {y : V | y ∉ Expr.locals φ ∧ y ≠ x} → (Formula.Realize M g' φ ↔ ∃ (b : β), g' x = {f b} ∧ b ∈ s)) :
realize M g (Expr.sigma x φ) = f '' s

Built from , ,

A summation over a distributive description, true of the nonempty pluralities within s: s itself.

theorem Term.realize_sigma_eq_of_distributiveL273–282
{V : Type u} {L : Type v} {P : ℕ → Type w} {α : Type u_1} [DecidableEq V] (M : Model P α) (g : V → Set α) {x : V} {φ : Formula V L P} {s : Set α} (hφ : ∀ (g' : V → Set α), Set.EqOn g' g {y : V | y ∉ Expr.locals φ ∧ y ≠ x} → (Formula.Realize M g' φ ↔ (g' x).Nonempty ∧ g' x ⊆ s)) :
realize M g (Expr.sigma x φ) = s

Built from , ,

Dependence on the variables

Summation over divisive predications

L343–391

The value of a summation over a conjunction of divisive predications: the atoms a for which the body holds where the summation variable is the singular {a} and each local is singular.

theorem Term.realize_sigma_eq_of_isConjunctiveL393–418
{V : Type u} {L : Type v} {P : ℕ → Type w} {α : Type u_1} [DecidableEq V] (M : Model P α) (g : V → Set α) {D : {n : ℕ} → P n → Bool} (hD : ∀ {n : ℕ} (r : P n), D r = true → M.Divisive r) {x : V} {φ : Formula V L P} (hφ : Expr.isConjunctive (fun {n : ℕ} => D) φ = true) :
realize M g (Expr.sigma x φ) = {a : α | ∃ (b : V → α), Formula.Realize M (fun (y : V) => if y = x then {a} else if y ∈ Expr.locals φ then {b y} else g y) φ}

Built from , , ,

Eliminability

L422–445