Docs / Logic / Consequence / Mixed

Mixed consequence

import Linglib.Logic.Consequence.Mixed · namespace Consequence

With two notions of satisfaction $p$ and $q$, a sequent $\Gamma \Rightarrow \Delta$ between sets of formulas is a mixed consequence when every model that $p$-satisfies all of $\Gamma$ $q$-satisfies some member of $\Delta$ (Cobreros et al. 2012), that is, when it has no countermodel. With $p = q$ and a single conclusion this is ordinary consequence.

Mixed consequence is monotone. It is reflexive exactly when $p \le q$ and transitive when $q \le p$. These rules characterize it: every monotone relation between sets of formulas is a mixed consequence, with $p \le q$ if it is reflexive and $q \le p$ if it is transitive (Chemla & Égré 2019), and one with all three rules is the consequence relation of a single notion of satisfaction (Scott 1974, Shoesmith & Smiley 1978). Negation dualizes mixed consequence, and a premise moves into the antecedent of a conditional read at $q$ with its antecedent at $p$.

Implementation notes

Notions of satisfaction are ordered pointwise: p ≤ q says that whatever a model p-satisfies it also q-satisfies. MixedConsequence.mono varies the two notions and MixedConsequence.weaken the two sets of formulas. A finite sequent is a set built with insert.

References

Declarations

L54–57

Mixed consequence (Cobreros et al. 2012, Definition 17): every model that p-satisfies all the premises q-satisfies some conclusion.

def MixedConsequenceL59–62
{Model : Type v} {Formula : Type u} (p q : Model → Formula → Prop) (Γ Δ : Set Formula) :

Built from

Used by mixedConsequence_iff_disjoint, mixedConsequence_iff_iInter_subset_iUnion, mixedConsequence_singleton_right, mixedConsequence_singleton_iff_mem_upperPolar, entails_iff_mixedConsequence, mixedConsequence_singleton_singleton, mixedConsequence_empty_singleton, mixedConsequence_singleton_empty, MixedConsequence.comap, MixedConsequence.mono, monotone_uncurry_mixedConsequence, stdRefl_mixedConsequence_iff, isTransitive_mixedConsequence, MixedConsequence.weaken, MixedConsequence.of_mem, MixedConsequence.cut, MixedConsequence.trans, isTrans_mixedConsequence, monotone_iff_exists_mixedConsequence, monotone_stdRefl_iff_exists_mixedConsequence, monotone_isTransitive_iff_exists_mixedConsequence, monotone_stdRefl_isTransitive_iff_exists_mixedConsequence, mixedConsequence_iff_dual, mixedConsequence_insert_insert_iff

Used in CobrerosEtAl2012

Countermodels

L69–73

A sequent is valid exactly when it has no countermodel: the models p-satisfying every premise are disjoint from those q-satisfying no conclusion.

theorem mixedConsequence_iff_disjointL75–80
{Model : Type v} {Formula : Type u} {p q : Model → Formula → Prop} {Γ Δ : Set Formula} :
MixedConsequence p q Γ Δ ↔ Disjoint (lowerPolar p Γ) (lowerPolar qᶜ Δ)

Built from

L82–86

Small sequents

L90–92
L94–98
L104–106
L108–110
L112–114

Changing the models and the notions of satisfaction

L120–125
L127–131

Structural rules

L159–161
L163–164
L171–174
L178–181
L183–189

Representation

A relation between sets of formulas is monotone and reflexive exactly when it is a mixed consequence whose premise standard is at least as strong as its conclusion standard (Chemla & Égré 2019, §3).

theorem monotone_stdRefl_iff_exists_mixedConsequenceL225–236
{Formula : Type u} {r : Set Formula → Set Formula → Prop} :
(Monotone (Function.uncurry r) ∧ Std.Refl fun (φ ψ : Formula) => r {φ} {ψ}) ↔ ∃ (Model : Type u) (p : Model → Formula → Prop) (q : Model → Formula → Prop), p ≤ q ∧ r = MixedConsequence p q

Built from

A relation between sets of formulas is monotone and transitive exactly when it is a mixed consequence whose conclusion standard is at least as strong as its premise standard (Chemla & Égré 2019, §3).

theorem monotone_isTransitive_iff_exists_mixedConsequenceL238–255
{Formula : Type u} {r : Set Formula → Set Formula → Prop} :
Monotone (Function.uncurry r) ∧ IsTransitive r ↔ ∃ (Model : Type u) (p : Model → Formula → Prop), ∃ q ≤ p, r = MixedConsequence p q

Built from

A relation between sets of formulas is monotone, reflexive and transitive exactly when it is the consequence relation of one notion of satisfaction (Scott 1974; Shoesmith & Smiley 1978, Theorem 2.1).

theorem monotone_stdRefl_isTransitive_iff_exists_mixedConsequenceL257–271
{Formula : Type u} {r : Set Formula → Set Formula → Prop} :
Monotone (Function.uncurry r) ∧ (Std.Refl fun (φ ψ : Formula) => r {φ} {ψ}) ∧ IsTransitive r ↔ ∃ (Model : Type u) (p : Model → Formula → Prop), r = MixedConsequence p p

Built from

Connectives

A premise moves into the antecedent of a conclusion when the conditional is q-satisfied iff p-satisfaction of its antecedent implies q-satisfaction of its consequent (Lemma 10 of Cobreros et al. 2012).

theorem mixedConsequence_insert_insert_iffL291–300
{Model : Type v} {Formula : Type u} {p q : Model → Formula → Prop} {Γ Δ : Set Formula} {φ ψ : Formula} {imp : Formula → Formula → Formula} (himp : ∀ (M : Model), q M (imp φ ψ) ↔ p M φ → q M ψ) :
MixedConsequence p q (insert φ Γ) (insert ψ Δ) ↔ MixedConsequence p q Γ (insert (imp φ ψ) Δ)

Built from