Docs / Logic / Consequence / Structural

Structural rules

import Linglib.Logic.Consequence.Structural · namespace Consequence

A relation $\Gamma \vdash \Delta$ between sets of formulas, read as "if every member of $\Gamma$ holds then some member of $\Delta$ does", may obey the three structural rules of Scott 1974: it is monotone when it survives added premises and conclusions, reflexive when each formula yields itself, and transitive when it is closed under cut. A monotone reflexive relation holds between overlapping sets. A transitive one admits cut on a single formula, and if also monotone it passes through sets of intermediate conclusions, so that its restriction to single formulas is transitive in the ordinary sense.

Implementation notes

For a relation r between sets of formulas, monotonicity is Monotone (Function.uncurry r) and reflexivity is Std.Refl fun φ ψ ↦ r {φ} {ψ}. Transitivity is the cut for sets of Shoesmith & Smiley 1978, which quantifies over the partitions of a set Z of cut formulas; a partition is given by its first block Z₁ ⊆ Z, the second being Z \ Z₁. Transitivity of r as a binary relation on sets would be a different rule, since a set is read conjunctively as premises and disjunctively as conclusions.

References

Declarations

A relation between sets of formulas is transitive when it is closed under cut for sets (Shoesmith & Smiley 1978, §2.1): Γ ⇒ Δ holds if Γ, Z₁ ⇒ Z₂, Δ holds for every partition Z₁, Z₂ of a set Z of cut formulas.

def IsTransitiveL45–49
{Formula : Type u_1} (r : Set Formula → Set Formula → Prop) :
  • IsTransitive r = ∀ ⦃Γ Δ : Set Formula⦄ (Z : Set Formula), (∀ (Z₁ : Set Formula), Z₁ ⊆ Z → r (Γ ∪ Z₁) (Z \ Z₁ ∪ Δ)) → r Γ Δ

Used by IsTransitive.cut, IsTransitive.trans, IsTransitive.isTrans

Used in Logic/Consequence/Mixed

A monotone relation that holds between each formula and itself holds between overlapping sets, rule (R) of Scott 1974.

theorem overlapL51–57
{Formula : Type u_1} {r : Set Formula → Set Formula → Prop} {Γ Δ : Set Formula} (hm : Monotone (Function.uncurry r)) (hr : Std.Refl fun (φ ψ : Formula) => r {φ} {ψ}) (h : (Γ ∩ Δ).Nonempty) :
r Γ Δ

Cut on one formula, rule (T) of Scott 1974.

theorem IsTransitive.cutL61–66
{Formula : Type u_1} {r : Set Formula → Set Formula → Prop} {Γ Δ : Set Formula} {φ : Formula} (ht : IsTransitive r) (h₁ : r (insert φ Γ) Δ) (h₂ : r Γ (insert φ Δ)) :
r Γ Δ

Built from

Whatever follows from single conclusions of Γ follows from Γ.

theorem IsTransitive.transL68–77
{Formula : Type u_1} {r : Set Formula → Set Formula → Prop} {Γ Δ Θ : Set Formula} (ht : IsTransitive r) (hm : Monotone (Function.uncurry r)) (h₁ : ∀ (θ : Formula), θ ∈ Θ → r Γ {θ}) (h₂ : r Θ Δ) :
r Γ Δ

Built from

The restriction of a monotone transitive relation to single formulas is transitive.

theorem IsTransitive.isTransL79–82
{Formula : Type u_1} {r : Set Formula → Set Formula → Prop} (ht : IsTransitive r) (hm : Monotone (Function.uncurry r)) :
IsTrans Formula fun (φ ψ : Formula) => r {φ} {ψ}

Built from