Docs / Logic / Orthologic / Compatibility

Compatibility frames

import Linglib.Logic.Orthologic.Compatibility · namespace Orthologic

This file defines compatibility frames, the possibility semantics for orthologic on which Holliday and Mandelkern build their account of epistemic modals. A frame is a set of partial possibilities with a reflexive, symmetric compatibility relation, and its propositions are the concepts of orthogonality, the complement of compatibility. They form an ortholattice $O(F)$ in which $\neg A$ holds where no $A$-possibility is compatible, the propositions are the paper's regular sets, and a possibility can settle a disjunction without settling either disjunct. The proposition that $x$ obtains is the least one containing $x$, whose members are the possibilities refining $x$, and $O(F)$ is Boolean exactly when compatible possibilities have a common refinement.

Main definitions

Implementation notes

A frame stores its orthogonality relation ortho, which defaults to ¬ compat, in the way Preorder stores <, so a frame built from an orthogonality relation, such as the canonical frame of an ortholattice, keeps that relation definitionally. Everything else is mathlib's concept API for ortho: negation is upperPolar, the regular sets are the extents, the paper's closure operator $c_◇$ is extentClosure, and the set $↓x$ of refinements of $x$ is the object concept Concept.ofObject, so that $y ⊑ x$ is $y ∈ ↓x$. The paper's formulas are characterizations of these objects. Decidability of compat is not bundled: use sites take [DecidableRel F.compat], as for SimpleGraph.Adj. The paper's frames are nonempty; no result here needs it, so the structure does not require it.

References

Declarations

A compatibility frame is a set of possibilities with a reflexive, symmetric compatibility relation; two possibilities are compatible when neither settles as true anything the other settles as false (Holliday & Mandelkern 2024 Definition 4.1).

structure CompatibilityL49–59
(S : Type u_2) :
Type u_2
  • compat : S → S → Prop

    Compatibility of possibilities.

  • compat_refl : Std.Refl self.compat
  • compat_symm : Std.Symm self.compat
  • ortho : S → S → Prop

    Orthogonality, the complement of compatibility.

  • ortho_iff (x y : S) : self.ortho x y ↔ ¬self.compat x y

Used by Compatibility.refl, Compatibility.compat.symm, Compatibility.instSymmOrtho, Compatibility.instIrreflOrtho, Compatibility.instDecidableRelOrthoOfCompat, Compatibility.Regular, Compatibility.mem_upperPolar_ortho, Compatibility.isExtent_ortho_iff, Compatibility.mem_extentClosure_ortho, Compatibility.mem_ofObject_ortho, Compatibility.upperPolar_ortho_eq_compl, Compatibility.inf_sup_le_iff

Used in Logic/Orthologic/Epistemic/Compatibility, Logic/Orthologic/Epistemic/Extension, Logic/Orthologic/Epistemic/FrameSemantics, Logic/Orthologic/FrameSemantics, HollidayMandelkern2024

L69–71

The closure operator c_◇ sends A to the possibilities all of whose compatible possibilities are compatible with an A-possibility, and its fixed points are the regular sets (Holliday & Mandelkern 2024 footnote 19). At A ∪ B it is the disjunction A ∨ B, so a possibility can settle A ∨ B without settling either (Holliday & Mandelkern 2024 eq. (2)).

theorem Compatibility.mem_extentClosure_orthoL102–109
{S : Type u_1} (F : Compatibility S) {A : Set S} {x : S} :
x ∈ (extentClosure F.ortho) A ↔ ∀ (y : S), F.compat x y → ∃ (z : S), F.compat y z ∧ z ∈ A

Built from

L119–124

The regular propositions form a Boolean algebra, by distributivity, exactly when compatibility implies compossibility: any two compatible possibilities have a common refinement (Holliday & Mandelkern 2024 Remark 4.9).

theorem Compatibility.inf_sup_le_iffL126–144
{S : Type u_1} (F : Compatibility S) :
(∀ (A B C : F.Regular), A ⊓ (B ⊔ C) ≤ A ⊓ B ⊔ A ⊓ C) ↔ ∀ (x y : S), F.compat x y → ∃ z ∈ Concept.ofObject F.ortho x, z ∈ Concept.ofObject F.ortho y

Built from ,