Library Deduxit.Intuitionistic.Kripke
Kripke models and their soundness
From Stdlib Require Import List Permutation Bool.
From Deduxit.Intuitionistic Require Export Calculus.
Import ListNotations.
Section Kripke.
Context {atom : Type}.
Local Notation formula := (formula atom).
Variable world : Type.
Variable le : world → world → Prop.
Variable val : world → atom → Prop.
Variable absurd : world → Prop.
Record model (R : rules) : Prop := {
model_refl : ∀ w, le w w;
model_trans : ∀ u v w, le u v → le v w → le u w;
model_val : ∀ w v a, le w v → val w a → val v a;
model_absurd : ∀ w v, le w v → absurd w → absurd v;
model_explosion : explosion R = true → ∀ w, ¬ absurd w;
}.
model_refl : ∀ w, le w w;
model_trans : ∀ u v w, le u v → le v w → le u w;
model_val : ∀ w v a, le w v → val w a → val v a;
model_absurd : ∀ w v, le w v → absurd w → absurd v;
model_explosion : explosion R = true → ∀ w, ¬ absurd w;
}.
The world w forces the formula A.
Fixpoint forces (w : world) (A : formula) : Prop :=
match A with
| var a ⇒ val w a
| bot ⇒ absurd w
| wedge A B ⇒ forces w A ∧ forces w B
| vee A B ⇒ forces w A ∨ forces w B
| imp A B ⇒ ∀ v, le w v → forces v A → forces v B
end.
Variable R : rules.
Hypothesis M : model R.
match A with
| var a ⇒ val w a
| bot ⇒ absurd w
| wedge A B ⇒ forces w A ∧ forces w B
| vee A B ⇒ forces w A ∨ forces w B
| imp A B ⇒ ∀ v, le w v → forces v A → forces v B
end.
Variable R : rules.
Hypothesis M : model R.
What a world forces, every later world forces.
Lemma persistence : ∀ A w v, le w v → forces w A → forces v A.
Proof.
induction A as [a | | A IHA B IHB | A IHA B IHB | A IHA B IHB];
intros w v Hle H; cbn in ×.
- exact (model_val _ M _ _ _ Hle H).
- exact (model_absurd _ M _ _ Hle H).
- destruct H as [HA HB]. split; [exact (IHA _ _ Hle HA) | exact (IHB _ _ Hle HB)].
- destruct H as [HA | HB]; [left; exact (IHA _ _ Hle HA) | right; exact (IHB _ _ Hle HB)].
- intros u Hvu HA. exact (H u (model_trans _ M _ _ _ Hle Hvu) HA).
Qed.
Proof.
induction A as [a | | A IHA B IHB | A IHA B IHB | A IHA B IHB];
intros w v Hle H; cbn in ×.
- exact (model_val _ M _ _ _ Hle H).
- exact (model_absurd _ M _ _ Hle H).
- destruct H as [HA HB]. split; [exact (IHA _ _ Hle HA) | exact (IHB _ _ Hle HB)].
- destruct H as [HA | HB]; [left; exact (IHA _ _ Hle HA) | right; exact (IHB _ _ Hle HB)].
- intros u Hvu HA. exact (H u (model_trans _ M _ _ _ Hle Hvu) HA).
Qed.
Every derivable sequent holds at every world of the model.
Theorem kripke_soundness : ∀ G C, lj R G C →
∀ w, Forall (forces w) G → forces w C.
Proof.
intros G C D. induction D as [A | l1 l2 C D IHD Hp | A l C D IHD | A l C D IHD
| Hexp C | A B l D1 IHD1 D2 IHD2 | A B l C D IHD | A B l D IHD | A B l D IHD
| A B l C D1 IHD1 D2 IHD2 | A B l D IHD | A B l C D1 IHD1 D2 IHD2
| Hcut A l C D1 IHD1 D2 IHD2]; intros w HG.
- apply Forall_cons_iff in HG as [HA _]. exact HA.
- apply IHD. apply Forall_forall. intros x Hx.
eapply Forall_forall; [exact HG |]. apply Permutation_in with l1; assumption.
- apply Forall_cons_iff in HG as [_ Hl]. exact (IHD w Hl).
- apply Forall_cons_iff in HG as [HA Hl]. apply IHD. repeat constructor; assumption.
- apply Forall_cons_iff in HG as [Hbot _]. cbn in Hbot.
exfalso. exact (model_explosion _ M Hexp w Hbot).
- split; [exact (IHD1 w HG) | exact (IHD2 w HG)].
- apply Forall_cons_iff in HG as [[HA HB] Hl]. apply IHD. repeat constructor; assumption.
- left. exact (IHD w HG).
- right. exact (IHD w HG).
- apply Forall_cons_iff in HG as [[HA | HB] Hl].
+ apply IHD1. constructor; assumption.
+ apply IHD2. constructor; assumption.
- intros v Hle HA. apply IHD. constructor; [exact HA |].
eapply Forall_impl; [| exact HG]. intros x. apply persistence. exact Hle.
- apply Forall_cons_iff in HG as [Himp Hl]. apply IHD2. constructor; [| exact Hl].
exact (Himp w (model_refl _ M w) (IHD1 w Hl)).
- apply IHD2. constructor; [exact (IHD1 w HG) | exact HG].
Qed.
∀ w, Forall (forces w) G → forces w C.
Proof.
intros G C D. induction D as [A | l1 l2 C D IHD Hp | A l C D IHD | A l C D IHD
| Hexp C | A B l D1 IHD1 D2 IHD2 | A B l C D IHD | A B l D IHD | A B l D IHD
| A B l C D1 IHD1 D2 IHD2 | A B l D IHD | A B l C D1 IHD1 D2 IHD2
| Hcut A l C D1 IHD1 D2 IHD2]; intros w HG.
- apply Forall_cons_iff in HG as [HA _]. exact HA.
- apply IHD. apply Forall_forall. intros x Hx.
eapply Forall_forall; [exact HG |]. apply Permutation_in with l1; assumption.
- apply Forall_cons_iff in HG as [_ Hl]. exact (IHD w Hl).
- apply Forall_cons_iff in HG as [HA Hl]. apply IHD. repeat constructor; assumption.
- apply Forall_cons_iff in HG as [Hbot _]. cbn in Hbot.
exfalso. exact (model_explosion _ M Hexp w Hbot).
- split; [exact (IHD1 w HG) | exact (IHD2 w HG)].
- apply Forall_cons_iff in HG as [[HA HB] Hl]. apply IHD. repeat constructor; assumption.
- left. exact (IHD w HG).
- right. exact (IHD w HG).
- apply Forall_cons_iff in HG as [[HA | HB] Hl].
+ apply IHD1. constructor; assumption.
+ apply IHD2. constructor; assumption.
- intros v Hle HA. apply IHD. constructor; [exact HA |].
eapply Forall_impl; [| exact HG]. intros x. apply persistence. exact Hle.
- apply Forall_cons_iff in HG as [Himp Hl]. apply IHD2. constructor; [| exact Hl].
exact (Himp w (model_refl _ M w) (IHD1 w Hl)).
- apply IHD2. constructor; [exact (IHD1 w HG) | exact HG].
Qed.
A world that forces the hypotheses and not the conclusion shows the
sequent underivable.
Theorem kripke_countermodel : ∀ G C w,
Forall (forces w) G → ¬ forces w C → ¬ lj R G C.
Proof.
intros G C w HG HC D. exact (HC (kripke_soundness G C D w HG)).
Qed.
End Kripke.
Arguments model {atom} world le val absurd R.
Arguments forces {atom world} le val absurd w A.
Section Classical.
Context {atom : Type}.
Local Notation formula := (formula atom).
Forall (forces w) G → ¬ forces w C → ¬ lj R G C.
Proof.
intros G C w HG HC D. exact (HC (kripke_soundness G C D w HG)).
Qed.
End Kripke.
Arguments model {atom} world le val absurd R.
Arguments forces {atom world} le val absurd w A.
Section Classical.
Context {atom : Type}.
Local Notation formula := (formula atom).
The truth value of a formula under an assignment v of the atoms,
⊥ false.
Fixpoint eval (v : atom → bool) (A : formula) : bool :=
match A with
| var a ⇒ v a
| bot ⇒ false
| wedge A B ⇒ eval v A && eval v B
| vee A B ⇒ eval v A || eval v B
| imp A B ⇒ implb (eval v A) (eval v B)
end.
match A with
| var a ⇒ v a
| bot ⇒ false
| wedge A B ⇒ eval v A && eval v B
| vee A B ⇒ eval v A || eval v B
| imp A B ⇒ implb (eval v A) (eval v B)
end.
The model with one world, forcing exactly the true atoms.
Lemma forces_eval : ∀ v A,
forces (world := unit) (fun _ _ ⇒ True) (fun _ a ⇒ v a = true) (fun _ ⇒ False) tt A
↔ eval v A = true.
Proof.
intros v A. induction A as [a | | A IHA B IHB | A IHA B IHB | A IHA B IHB]; cbn.
- reflexivity.
- split; [intros [] | discriminate].
- rewrite andb_true_iff, IHA, IHB. reflexivity.
- rewrite orb_true_iff, IHA, IHB. reflexivity.
- rewrite implb_true_iff, <- IHA, <- IHB. split.
+ intros H HA. exact (H tt I HA).
+ intros H [] _ HA. exact (H HA).
Qed.
forces (world := unit) (fun _ _ ⇒ True) (fun _ a ⇒ v a = true) (fun _ ⇒ False) tt A
↔ eval v A = true.
Proof.
intros v A. induction A as [a | | A IHA B IHB | A IHA B IHB | A IHA B IHB]; cbn.
- reflexivity.
- split; [intros [] | discriminate].
- rewrite andb_true_iff, IHA, IHB. reflexivity.
- rewrite orb_true_iff, IHA, IHB. reflexivity.
- rewrite implb_true_iff, <- IHA, <- IHB. split.
+ intros H HA. exact (H tt I HA).
+ intros H [] _ HA. exact (H HA).
Qed.
A sequent whose hypotheses an assignment makes true and whose
conclusion it makes false is underivable, in LJ and LM, with cut or
without.
Theorem classical_refutation : ∀ R v G C,
forallb (eval v) G && negb (eval v C) = true → ¬ lj R G C.
Proof.
intros R v G C H. apply andb_true_iff in H as [HG HC].
apply (kripke_countermodel unit (fun _ _ ⇒ True) (fun _ a ⇒ v a = true)
(fun _ ⇒ False) R) with tt.
- split; auto.
- apply Forall_forall. intros A HA. apply forces_eval.
apply forallb_forall with (x := A) in HG; assumption.
- rewrite forces_eval. apply negb_true_iff in HC. rewrite HC. discriminate.
Qed.
End Classical.
forallb (eval v) G && negb (eval v C) = true → ¬ lj R G C.
Proof.
intros R v G C H. apply andb_true_iff in H as [HG HC].
apply (kripke_countermodel unit (fun _ _ ⇒ True) (fun _ a ⇒ v a = true)
(fun _ ⇒ False) R) with tt.
- split; auto.
- apply Forall_forall. intros A HA. apply forces_eval.
apply forallb_forall with (x := A) in HG; assumption.
- rewrite forces_eval. apply negb_true_iff in HC. rewrite HC. discriminate.
Qed.
End Classical.