Library Deduxit.Intuitionistic.KripkeCheck
Finite Kripke models as data, and their checker
From Stdlib Require Import List Bool Arith.
From Deduxit.Intuitionistic Require Export Kripke.
Import ListNotations.
Section Check.
Context {atom : Type}.
Local Notation formula := (formula atom).
A finite Kripke model.
for each world, the worlds later than it
for each world, the atoms it forces
the worlds that force ⊥
v is in l.
The number of worlds.
The worlds.
The worlds later than w, w first.
The atoms w forces.
w forces the atom a.
w forces ⊥.
The model is one of the logic of R: the relation is transitive
and names worlds only, a later world forces every atom and every
⊥ an earlier one does, and in LJ no world forces ⊥.
Definition well_formed (R : rules) : bool :=
forallb (fun w ⇒
forallb (fun v ⇒
(v <? size)
&& forallb (fun u ⇒ mem u (ups w)) (ups v)
&& forallb (forces_atom v) (atoms_at w)
&& implb (absurd_at w) (absurd_at v))
(ups w))
worlds
&& implb (explosion R) (length (absurd M) =? 0).
forallb (fun w ⇒
forallb (fun v ⇒
(v <? size)
&& forallb (fun u ⇒ mem u (ups w)) (ups v)
&& forallb (forces_atom v) (atoms_at w)
&& implb (absurd_at w) (absurd_at v))
(ups w))
worlds
&& implb (explosion R) (length (absurd M) =? 0).
For each world in order, whether it forces A.
Fixpoint forced (A : formula) : list bool :=
match A with
| var a ⇒ map (fun w ⇒ forces_atom w a) worlds
| bot ⇒ map absurd_at worlds
| wedge A B ⇒
let fa := forced A in let fb := forced B in
map (fun w ⇒ nth w fa false && nth w fb false) worlds
| vee A B ⇒
let fa := forced A in let fb := forced B in
map (fun w ⇒ nth w fa false || nth w fb false) worlds
| imp A B ⇒
let fa := forced A in let fb := forced B in
map (fun w ⇒ forallb (fun v ⇒ implb (nth v fa false) (nth v fb false)) (ups w)) worlds
end.
match A with
| var a ⇒ map (fun w ⇒ forces_atom w a) worlds
| bot ⇒ map absurd_at worlds
| wedge A B ⇒
let fa := forced A in let fb := forced B in
map (fun w ⇒ nth w fa false && nth w fb false) worlds
| vee A B ⇒
let fa := forced A in let fb := forced B in
map (fun w ⇒ nth w fa false || nth w fb false) worlds
| imp A B ⇒
let fa := forced A in let fb := forced B in
map (fun w ⇒ forallb (fun v ⇒ implb (nth v fa false) (nth v fb false)) (ups w)) worlds
end.
Definition refutes (R : rules) (w : nat) (G : list formula) (C : formula) : bool :=
well_formed R && (w <? size)
&& forallb (fun A ⇒ nth w (forced A) false) G
&& negb (nth w (forced C) false).
well_formed R && (w <? size)
&& forallb (fun A ⇒ nth w (forced A) false) G
&& negb (nth w (forced C) false).
The model read as a Kripke model over the natural numbers: a number
past the worlds is later only than itself and forces no atom.
le w v: v is later than w.
w forces the atom a.
w forces ⊥.
mem tests membership.
Lemma mem_In : ∀ v l, mem v l = true ↔ In v l.
Proof.
intros v l. unfold mem. rewrite existsb_exists. split.
- intros [x [Hx E]]. apply Nat.eqb_eq in E. subst. exact Hx.
- intros H. ∃ v. split; [exact H | apply Nat.eqb_refl].
Qed.
Proof.
intros v l. unfold mem. rewrite existsb_exists. split.
- intros [x [Hx E]]. apply Nat.eqb_eq in E. subst. exact Hx.
- intros H. ∃ v. split; [exact H | apply Nat.eqb_refl].
Qed.
A number past the worlds has itself alone above it.
Lemma ups_past : ∀ w, size ≤ w → ups w = [w].
Proof.
intros w H. unfold ups. rewrite nth_overflow by exact H. reflexivity.
Qed.
Proof.
intros w H. unfold ups. rewrite nth_overflow by exact H. reflexivity.
Qed.
A vector over the worlds holds, at a world, its entry.
Lemma nth_worlds : ∀ (f : nat → bool) w,
w < size → nth w (map f worlds) false = f w.
Proof.
intros f w H. unfold worlds.
rewrite (nth_indep _ false (f 0)) by (rewrite length_map, length_seq; exact H).
rewrite map_nth, seq_nth by exact H. reflexivity.
Qed.
w < size → nth w (map f worlds) false = f w.
Proof.
intros f w H. unfold worlds.
rewrite (nth_indep _ false (f 0)) by (rewrite length_map, length_seq; exact H).
rewrite map_nth, seq_nth by exact H. reflexivity.
Qed.
What well_formed checks of each world and each later one.
Lemma well_formed_at : ∀ R, well_formed R = true →
∀ w v, w < size → In v (ups w) →
v < size
∧ (∀ u, In u (ups v) → In u (ups w))
∧ (∀ a, In a (atoms_at w) → forces_atom v a = true)
∧ (absurd_at w = true → absurd_at v = true).
Proof.
intros R H w v Hw Hv. apply andb_true_iff in H as [H _].
rewrite forallb_forall in H.
assert (Hw' : In w worlds) by (apply in_seq; split; [apply Nat.le_0_l | exact Hw]).
specialize (H w Hw'). rewrite forallb_forall in H. specialize (H v Hv).
repeat rewrite andb_true_iff in H. destruct H as [[[Hsize Htrans] Hatoms] Habs].
repeat split.
- apply Nat.ltb_lt. exact Hsize.
- intros u Hu. rewrite forallb_forall in Htrans. apply mem_In. exact (Htrans u Hu).
- intros a Ha. rewrite forallb_forall in Hatoms. exact (Hatoms a Ha).
- intros Hw''. rewrite Hw'' in Habs. exact Habs.
Qed.
∀ w v, w < size → In v (ups w) →
v < size
∧ (∀ u, In u (ups v) → In u (ups w))
∧ (∀ a, In a (atoms_at w) → forces_atom v a = true)
∧ (absurd_at w = true → absurd_at v = true).
Proof.
intros R H w v Hw Hv. apply andb_true_iff in H as [H _].
rewrite forallb_forall in H.
assert (Hw' : In w worlds) by (apply in_seq; split; [apply Nat.le_0_l | exact Hw]).
specialize (H w Hw'). rewrite forallb_forall in H. specialize (H v Hv).
repeat rewrite andb_true_iff in H. destruct H as [[[Hsize Htrans] Hatoms] Habs].
repeat split.
- apply Nat.ltb_lt. exact Hsize.
- intros u Hu. rewrite forallb_forall in Htrans. apply mem_In. exact (Htrans u Hu).
- intros a Ha. rewrite forallb_forall in Hatoms. exact (Hatoms a Ha).
- intros Hw''. rewrite Hw'' in Habs. exact Habs.
Qed.
A step from a world past the worlds stays there.
Lemma le_past : ∀ w v, size ≤ w → le w v → v = w.
Proof.
intros w v Hw H. unfold le in H. rewrite ups_past in H by exact Hw.
apply mem_In in H. destruct H as [E | []]. symmetry. exact E.
Qed.
Hypothesis atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b).
Proof.
intros w v Hw H. unfold le in H. rewrite ups_past in H by exact Hw.
apply mem_In in H. destruct H as [E | []]. symmetry. exact E.
Qed.
Hypothesis atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b).
A well-formed model is a Kripke model of its logic.
Lemma well_formed_model : ∀ R, well_formed R = true → model nat le val abs R.
Proof.
intros R H. split.
- intros w. unfold le, ups. apply mem_In. left. reflexivity.
- intros u v w Huv Hvw. destruct (Nat.lt_ge_cases u size) as [Hu | Hu].
+ unfold le in ×. apply mem_In in Huv, Hvw. apply mem_In.
exact (proj1 (proj2 (well_formed_at R H u v Hu Huv)) w Hvw).
+ apply le_past in Huv; [subst; exact Hvw | exact Hu].
- intros w v a Hle Ha. destruct (Nat.lt_ge_cases w size) as [Hw | Hw].
+ unfold le, val, forces_atom in ×. apply mem_In in Hle.
apply existsb_exists in Ha as [b [Hb E]].
destruct (atom_eqb_spec a b); [subst | discriminate].
exact (proj1 (proj2 (proj2 (well_formed_at R H w v Hw Hle))) b Hb).
+ apply le_past in Hle; [subst; exact Ha | exact Hw].
- intros w v Hle Ha. destruct (Nat.lt_ge_cases w size) as [Hw | Hw].
+ unfold le, abs in ×. apply mem_In in Hle.
exact (proj2 (proj2 (proj2 (well_formed_at R H w v Hw Hle))) Ha).
+ apply le_past in Hle; [subst; exact Ha | exact Hw].
- intros Hexp w Hw. unfold abs, absurd_at, mem in Hw.
apply andb_true_iff in H as [_ H]. rewrite Hexp in H. cbn in H.
apply Nat.eqb_eq, length_zero_iff_nil in H. rewrite H in Hw. discriminate.
Qed.
Proof.
intros R H. split.
- intros w. unfold le, ups. apply mem_In. left. reflexivity.
- intros u v w Huv Hvw. destruct (Nat.lt_ge_cases u size) as [Hu | Hu].
+ unfold le in ×. apply mem_In in Huv, Hvw. apply mem_In.
exact (proj1 (proj2 (well_formed_at R H u v Hu Huv)) w Hvw).
+ apply le_past in Huv; [subst; exact Hvw | exact Hu].
- intros w v a Hle Ha. destruct (Nat.lt_ge_cases w size) as [Hw | Hw].
+ unfold le, val, forces_atom in ×. apply mem_In in Hle.
apply existsb_exists in Ha as [b [Hb E]].
destruct (atom_eqb_spec a b); [subst | discriminate].
exact (proj1 (proj2 (proj2 (well_formed_at R H w v Hw Hle))) b Hb).
+ apply le_past in Hle; [subst; exact Ha | exact Hw].
- intros w v Hle Ha. destruct (Nat.lt_ge_cases w size) as [Hw | Hw].
+ unfold le, abs in ×. apply mem_In in Hle.
exact (proj2 (proj2 (proj2 (well_formed_at R H w v Hw Hle))) Ha).
+ apply le_past in Hle; [subst; exact Ha | exact Hw].
- intros Hexp w Hw. unfold abs, absurd_at, mem in Hw.
apply andb_true_iff in H as [_ H]. rewrite Hexp in H. cbn in H.
apply Nat.eqb_eq, length_zero_iff_nil in H. rewrite H in Hw. discriminate.
Qed.
At a world of a well-formed model, forced computes forcing.
Lemma forced_forces : ∀ R, well_formed R = true →
∀ A w, w < size → nth w (forced A) false = true ↔ forces le val abs w A.
Proof.
intros R H A. induction A as [a | | A IHA B IHB | A IHA B IHB | A IHA B IHB];
intros w Hw; cbn [forced forces]; rewrite nth_worlds by exact Hw.
- reflexivity.
- reflexivity.
- rewrite andb_true_iff, IHA, IHB by exact Hw. reflexivity.
- rewrite orb_true_iff, IHA, IHB by exact Hw. reflexivity.
- rewrite forallb_forall. split.
+ intros Himp v Hle HA. unfold le in Hle. apply mem_In in Hle.
pose proof (proj1 (well_formed_at R H w v Hw Hle)) as Hv.
specialize (Himp v Hle). apply IHB; [exact Hv |].
apply IHA in HA; [| exact Hv]. rewrite HA in Himp. exact Himp.
+ intros Himp v Hv. pose proof (proj1 (well_formed_at R H w v Hw Hv)) as Hs.
destruct (nth v (forced A) false) eqn:E; [| reflexivity]. cbn.
apply IHB; [exact Hs |]. apply Himp; [unfold le; apply mem_In; exact Hv |].
apply IHA; [exact Hs | exact E].
Qed.
End Check.
Arguments finite_model atom : clear implicits.
∀ A w, w < size → nth w (forced A) false = true ↔ forces le val abs w A.
Proof.
intros R H A. induction A as [a | | A IHA B IHB | A IHA B IHB | A IHA B IHB];
intros w Hw; cbn [forced forces]; rewrite nth_worlds by exact Hw.
- reflexivity.
- reflexivity.
- rewrite andb_true_iff, IHA, IHB by exact Hw. reflexivity.
- rewrite orb_true_iff, IHA, IHB by exact Hw. reflexivity.
- rewrite forallb_forall. split.
+ intros Himp v Hle HA. unfold le in Hle. apply mem_In in Hle.
pose proof (proj1 (well_formed_at R H w v Hw Hle)) as Hv.
specialize (Himp v Hle). apply IHB; [exact Hv |].
apply IHA in HA; [| exact Hv]. rewrite HA in Himp. exact Himp.
+ intros Himp v Hv. pose proof (proj1 (well_formed_at R H w v Hw Hv)) as Hs.
destruct (nth v (forced A) false) eqn:E; [| reflexivity]. cbn.
apply IHB; [exact Hs |]. apply Himp; [unfold le; apply mem_In; exact Hv |].
apply IHA; [exact Hs | exact E].
Qed.
End Check.
Arguments finite_model atom : clear implicits.
A finite model that refutes accepts shows the sequent underivable.
Theorem kripke_refutation : ∀ {atom} (atom_eqb : atom → atom → bool),
(∀ a b, reflect (a = b) (atom_eqb a b)) →
∀ R M w G C, refutes atom_eqb M R w G C = true → ¬ lj R G C.
Proof.
intros atom atom_eqb spec R M w G C H.
unfold refutes in H. repeat rewrite andb_true_iff in H.
destruct H as [[[Hwf Hw] HG] HC]. apply Nat.ltb_lt in Hw.
apply (kripke_countermodel nat (le M) (val atom_eqb M) (abs M) R
(well_formed_model atom_eqb M spec R Hwf) G C w).
- apply Forall_forall. intros A HA. rewrite forallb_forall in HG.
apply (forced_forces atom_eqb M R Hwf A w Hw). exact (HG A HA).
- rewrite <- (forced_forces atom_eqb M R Hwf C w Hw).
apply negb_true_iff in HC. rewrite HC. discriminate.
Qed.
(∀ a b, reflect (a = b) (atom_eqb a b)) →
∀ R M w G C, refutes atom_eqb M R w G C = true → ¬ lj R G C.
Proof.
intros atom atom_eqb spec R M w G C H.
unfold refutes in H. repeat rewrite andb_true_iff in H.
destruct H as [[[Hwf Hw] HG] HC]. apply Nat.ltb_lt in Hw.
apply (kripke_countermodel nat (le M) (val atom_eqb M) (abs M) R
(well_formed_model atom_eqb M spec R Hwf) G C w).
- apply Forall_forall. intros A HA. rewrite forallb_forall in HG.
apply (forced_forces atom_eqb M R Hwf A w Hw). exact (HG A HA).
- rewrite <- (forced_forces atom_eqb M R Hwf C w Hw).
apply negb_true_iff in HC. rewrite HC. discriminate.
Qed.