Library Deduxit.Linear.Refutations
Refutations: invariants that every derivation keeps
- The classical reading. Erase ! and ?; read ⊗ and & as "and", ⅋ and ⊕ as "or", 1 and ⊤ as true, ⊥ and 0 as false. Every derivable sequent is then a tautology, in every calculus ll R, Mix, weakening and cut included (ll_tautology).
- The balance of an atom. Without weakening, the literals of an atom meet in axioms, whichever additive alternatives a derivation takes. So the interval of the atom's excess of positive over negative literals contains zero, unless a ⊤ absorbs or a ! or ? copies the atom (balance).
- The count equation. Without weakening, a derivable sequent of multiplicative formulas with units has #⊗ − #⅋ − #1 + #⊥ + 2 formulas, or at least that many with Mix (count_equation).
From Stdlib Require Import Bool List Permutation ZArith Lia.
From Deduxit.Linear Require Export Calculus.
From Deduxit.Linear Require Export Intuitionistic.
Import ListNotations.
Section Refutations.
Context {atom : Type}.
Local Notation formula := (formula atom).
Local Notation iformula := (iformula atom).
Fixpoint eval (v : atom → bool) (A : formula) : bool :=
match A with
| var a ⇒ v a
| covar a ⇒ negb (v a)
| one | top ⇒ true
| bot | zero ⇒ false
| tens A B | awith A B ⇒ eval v A && eval v B
| parr A B | aplus A B ⇒ eval v A || eval v B
| oc A | wn A ⇒ eval v A
end.
match A with
| var a ⇒ v a
| covar a ⇒ negb (v a)
| one | top ⇒ true
| bot | zero ⇒ false
| tens A B | awith A B ⇒ eval v A && eval v B
| parr A B | aplus A B ⇒ eval v A || eval v B
| oc A | wn A ⇒ eval v A
end.
A formula's dual reads as its negation.
Lemma eval_dual : ∀ v A, eval v (dual A) = negb (eval v A).
Proof.
intros v A. induction A; cbn; rewrite ?IHA, ?IHA1, ?IHA2;
try destruct (eval v A1), (eval v A2); try destruct (v a); reflexivity.
Qed.
Proof.
intros v A. induction A; cbn; rewrite ?IHA, ?IHA1, ?IHA2;
try destruct (eval v A1), (eval v A2); try destruct (v a); reflexivity.
Qed.
A sequent reads as the disjunction of its formulas, and a
permutation keeps that reading.
Lemma existsb_perm : ∀ (f : formula → bool) l1 l2,
Permutation l1 l2 → existsb f l1 = existsb f l2.
Proof.
intros f l1 l2 H. induction H; cbn.
- reflexivity.
- now rewrite IHPermutation.
- destruct (f x), (f y); reflexivity.
- congruence.
Qed.
Permutation l1 l2 → existsb f l1 = existsb f l2.
Proof.
intros f l1 l2 H. induction H; cbn.
- reflexivity.
- now rewrite IHPermutation.
- destruct (f x), (f y); reflexivity.
- congruence.
Qed.
Every derivable sequent, in every calculus, reads as a tautology.
Theorem ll_tautology : ∀ R l, ll R l → ∀ v, existsb (eval v) l = true.
Proof.
intros R l H v. induction H; cbn in *; rewrite ?existsb_app in ×.
- destruct (v a); reflexivity.
- now rewrite <- (existsb_perm _ _ _ H0).
- reflexivity.
- exact IHll.
- reflexivity.
- destruct (eval v A), (eval v B), (existsb (eval v) l1), (existsb (eval v) l2);
cbn in *; congruence.
- destruct (eval v A), (eval v B); cbn in *; congruence.
- destruct (eval v A), (eval v B); cbn in *; congruence.
- destruct (eval v A), (eval v B); cbn in *; congruence.
- destruct (eval v A), (eval v B); cbn in *; congruence.
- exact IHll.
- exact IHll.
- rewrite IHll. apply orb_true_r.
- destruct (eval v A); cbn in *; congruence.
- now rewrite IHll1.
- rewrite IHll. apply orb_true_r.
- rewrite eval_dual in IHll2.
destruct (eval v A), (existsb (eval v) l1), (existsb (eval v) l2); cbn in *; congruence.
Qed.
Proof.
intros R l H v. induction H; cbn in *; rewrite ?existsb_app in ×.
- destruct (v a); reflexivity.
- now rewrite <- (existsb_perm _ _ _ H0).
- reflexivity.
- exact IHll.
- reflexivity.
- destruct (eval v A), (eval v B), (existsb (eval v) l1), (existsb (eval v) l2);
cbn in *; congruence.
- destruct (eval v A), (eval v B); cbn in *; congruence.
- destruct (eval v A), (eval v B); cbn in *; congruence.
- destruct (eval v A), (eval v B); cbn in *; congruence.
- destruct (eval v A), (eval v B); cbn in *; congruence.
- exact IHll.
- exact IHll.
- rewrite IHll. apply orb_true_r.
- destruct (eval v A); cbn in *; congruence.
- now rewrite IHll1.
- rewrite IHll. apply orb_true_r.
- rewrite eval_dual in IHll2.
destruct (eval v A), (existsb (eval v) l1), (existsb (eval v) l2); cbn in *; congruence.
Qed.
Whether an assignment makes a sequent's reading false.
An assignment that makes a sequent's reading false shows that the
sequent is not derivable, in every calculus.
Theorem classical_refutation : ∀ R v l, falsifies v l = true → ¬ ll R l.
Proof.
intros R v l F H. unfold falsifies in F.
rewrite (ll_tautology R l H v) in F. discriminate.
Qed.
Proof.
intros R v l F H. unfold falsifies in F.
rewrite (ll_tautology R l H v) in F. discriminate.
Qed.
The equality literals are compared with, and the atom counted.
The invariant holds for any function, since both literals of an
axiom compare alike; it means what it should when the function
decides equality, as String.eqb does.
An interval of the excess, None when it is unbounded.
The interval of a sum.
Definition add (x y : span) : span :=
match x, y with
| Some (l1, h1), Some (l2, h2) ⇒ Some ((l1 + l2)%Z, (h1 + h2)%Z)
| _, _ ⇒ None
end.
match x, y with
| Some (l1, h1), Some (l2, h2) ⇒ Some ((l1 + l2)%Z, (h1 + h2)%Z)
| _, _ ⇒ None
end.
The hull of two intervals: the excess of either alternative.
Definition hull (x y : span) : span :=
match x, y with
| Some (l1, h1), Some (l2, h2) ⇒ Some (Z.min l1 l2, Z.max h1 h2)
| _, _ ⇒ None
end.
match x, y with
| Some (l1, h1), Some (l2, h2) ⇒ Some (Z.min l1 l2, Z.max h1 h2)
| _, _ ⇒ None
end.
The interval below a ! or ?: zero when the interval inside is
exactly zero, unbounded otherwise, since copies add any number.
The interval of the atom's excess of positive over negative
literals in a formula, over its additive alternatives. None when
a ⊤ absorbs, or when the interval below an exponential is not
exactly zero.
Fixpoint excess (A : formula) : span :=
match A with
| var b ⇒ Some (if atom_eqb a b then (1%Z, 1%Z) else (0%Z, 0%Z))
| covar b ⇒ Some (if atom_eqb a b then ((-1)%Z, (-1)%Z) else (0%Z, 0%Z))
| one | bot | zero ⇒ Some (0%Z, 0%Z)
| top ⇒ None
| tens A B | parr A B ⇒ add (excess A) (excess B)
| awith A B | aplus A B ⇒ hull (excess A) (excess B)
| oc A | wn A ⇒ bang (excess A)
end.
match A with
| var b ⇒ Some (if atom_eqb a b then (1%Z, 1%Z) else (0%Z, 0%Z))
| covar b ⇒ Some (if atom_eqb a b then ((-1)%Z, (-1)%Z) else (0%Z, 0%Z))
| one | bot | zero ⇒ Some (0%Z, 0%Z)
| top ⇒ None
| tens A B | parr A B ⇒ add (excess A) (excess B)
| awith A B | aplus A B ⇒ hull (excess A) (excess B)
| oc A | wn A ⇒ bang (excess A)
end.
The interval of a sequent: the sum over its formulas.
Fixpoint excesses (l : list formula) : span :=
match l with
| [] ⇒ Some (0%Z, 0%Z)
| A :: l ⇒ add (excess A) (excesses l)
end.
match l with
| [] ⇒ Some (0%Z, 0%Z)
| A :: l ⇒ add (excess A) (excesses l)
end.
An interval contains zero, or is unbounded.
Definition holds (x : span) : Prop :=
match x with
| Some (lo, hi) ⇒ (lo ≤ 0 ≤ hi)%Z
| None ⇒ True
end.
Lemma add_none_r : ∀ x, add x None = None.
Proof. intros [[]|]; reflexivity. Qed.
Lemma add_zero_l : ∀ x, add (Some (0%Z, 0%Z)) x = x.
Proof. intros [[]|]; reflexivity. Qed.
Lemma add_comm : ∀ x y, add x y = add y x.
Proof. intros [[]|] [[]|]; cbn; try reflexivity. f_equal. f_equal; lia. Qed.
Lemma add_assoc : ∀ x y z, add x (add y z) = add (add x y) z.
Proof. intros [[]|] [[]|] [[]|]; cbn; try reflexivity. f_equal. f_equal; lia. Qed.
Lemma excesses_app : ∀ l1 l2,
excesses (l1 ++ l2) = add (excesses l1) (excesses l2).
Proof.
induction l1 as [|A l1 IH]; intro l2; cbn [app excesses].
- now rewrite add_zero_l.
- now rewrite IH, add_assoc.
Qed.
Lemma excesses_perm : ∀ l1 l2, Permutation l1 l2 → excesses l1 = excesses l2.
Proof.
intros l1 l2 H. induction H; cbn [excesses].
- reflexivity.
- now rewrite IHPermutation.
- now rewrite !add_assoc, (add_comm (excess y)).
- congruence.
Qed.
Lemma bang_cases : ∀ x,
bang x = None ∨ (bang x = Some (0%Z, 0%Z) ∧ x = Some (0%Z, 0%Z)).
Proof. intros [[[] []]|]; cbn; first [left; reflexivity | right; split; reflexivity]. Qed.
Lemma excesses_wn : ∀ l,
excesses (map wn l) = None ∨ excesses (map wn l) = Some (0%Z, 0%Z).
Proof.
induction l as [|A l IH]; cbn [map excesses excess]; [now right |].
destruct (bang_cases (excess A)) as [-> | [-> _]]; [now left |].
rewrite add_zero_l. exact IH.
Qed.
match x with
| Some (lo, hi) ⇒ (lo ≤ 0 ≤ hi)%Z
| None ⇒ True
end.
Lemma add_none_r : ∀ x, add x None = None.
Proof. intros [[]|]; reflexivity. Qed.
Lemma add_zero_l : ∀ x, add (Some (0%Z, 0%Z)) x = x.
Proof. intros [[]|]; reflexivity. Qed.
Lemma add_comm : ∀ x y, add x y = add y x.
Proof. intros [[]|] [[]|]; cbn; try reflexivity. f_equal. f_equal; lia. Qed.
Lemma add_assoc : ∀ x y z, add x (add y z) = add (add x y) z.
Proof. intros [[]|] [[]|] [[]|]; cbn; try reflexivity. f_equal. f_equal; lia. Qed.
Lemma excesses_app : ∀ l1 l2,
excesses (l1 ++ l2) = add (excesses l1) (excesses l2).
Proof.
induction l1 as [|A l1 IH]; intro l2; cbn [app excesses].
- now rewrite add_zero_l.
- now rewrite IH, add_assoc.
Qed.
Lemma excesses_perm : ∀ l1 l2, Permutation l1 l2 → excesses l1 = excesses l2.
Proof.
intros l1 l2 H. induction H; cbn [excesses].
- reflexivity.
- now rewrite IHPermutation.
- now rewrite !add_assoc, (add_comm (excess y)).
- congruence.
Qed.
Lemma bang_cases : ∀ x,
bang x = None ∨ (bang x = Some (0%Z, 0%Z) ∧ x = Some (0%Z, 0%Z)).
Proof. intros [[[] []]|]; cbn; first [left; reflexivity | right; split; reflexivity]. Qed.
Lemma excesses_wn : ∀ l,
excesses (map wn l) = None ∨ excesses (map wn l) = Some (0%Z, 0%Z).
Proof.
induction l as [|A l IH]; cbn [map excesses excess]; [now right |].
destruct (bang_cases (excess A)) as [-> | [-> _]]; [now left |].
rewrite add_zero_l. exact IH.
Qed.
Without weakening and without cut, every derivable sequent's
interval contains zero for every atom.
Theorem balance : ∀ R l,
ll R l → weakening R = false → cut R = false → holds (excesses l).
Proof.
intros R l H W K. induction H; cbn [excesses excess] in ×.
- destruct (atom_eqb a a0); cbn; lia.
- now rewrite <- (excesses_perm _ _ H0).
- cbn; lia.
- now rewrite add_zero_l.
- cbn; exact I.
- rewrite excesses_app in ×.
destruct (excess A) as [[]|], (excess B) as [[]|], (excesses l1) as [[]|],
(excesses l2) as [[]|]; cbn in *; auto; lia.
- rewrite <- add_assoc. exact IHll.
- destruct (excess A) as [[]|], (excess B) as [[]|], (excesses l) as [[]|];
cbn in *; auto; lia.
- destruct (excess A) as [[]|], (excess B) as [[]|], (excesses l) as [[]|];
cbn in *; auto; lia.
- destruct (excess A) as [[]|], (excess B) as [[]|], (excesses l) as [[]|];
cbn in *; auto; lia.
- destruct (bang_cases (excess A)) as [-> | [-> _]]; [cbn; exact I |].
rewrite add_zero_l.
destruct (excesses_wn l) as [-> | ->]; cbn; [exact I | lia].
- destruct (bang_cases (excess A)) as [-> | [-> E]]; [cbn; exact I |].
rewrite E in IHll. exact IHll.
- destruct (bang_cases (excess A)) as [-> | [-> _]]; [cbn; exact I |].
now rewrite add_zero_l.
- destruct (bang_cases (excess A)) as [B | [B _]]; rewrite B in *; [cbn; exact I |].
now rewrite !add_zero_l in ×.
- rewrite excesses_app.
destruct (excesses l1) as [[]|], (excesses l2) as [[]|]; cbn in *; auto; lia.
- congruence.
- congruence.
Qed.
ll R l → weakening R = false → cut R = false → holds (excesses l).
Proof.
intros R l H W K. induction H; cbn [excesses excess] in ×.
- destruct (atom_eqb a a0); cbn; lia.
- now rewrite <- (excesses_perm _ _ H0).
- cbn; lia.
- now rewrite add_zero_l.
- cbn; exact I.
- rewrite excesses_app in ×.
destruct (excess A) as [[]|], (excess B) as [[]|], (excesses l1) as [[]|],
(excesses l2) as [[]|]; cbn in *; auto; lia.
- rewrite <- add_assoc. exact IHll.
- destruct (excess A) as [[]|], (excess B) as [[]|], (excesses l) as [[]|];
cbn in *; auto; lia.
- destruct (excess A) as [[]|], (excess B) as [[]|], (excesses l) as [[]|];
cbn in *; auto; lia.
- destruct (excess A) as [[]|], (excess B) as [[]|], (excesses l) as [[]|];
cbn in *; auto; lia.
- destruct (bang_cases (excess A)) as [-> | [-> _]]; [cbn; exact I |].
rewrite add_zero_l.
destruct (excesses_wn l) as [-> | ->]; cbn; [exact I | lia].
- destruct (bang_cases (excess A)) as [-> | [-> E]]; [cbn; exact I |].
rewrite E in IHll. exact IHll.
- destruct (bang_cases (excess A)) as [-> | [-> _]]; [cbn; exact I |].
now rewrite add_zero_l.
- destruct (bang_cases (excess A)) as [B | [B _]]; rewrite B in *; [cbn; exact I |].
now rewrite !add_zero_l in ×.
- rewrite excesses_app.
destruct (excesses l1) as [[]|], (excesses l2) as [[]|]; cbn in *; auto; lia.
- congruence.
- congruence.
Qed.
Whether an interval excludes zero.
Definition excluded (x : span) : bool :=
match x with
| Some (lo, hi) ⇒ (0 <? lo)%Z || (hi <? 0)%Z
| None ⇒ false
end.
match x with
| Some (lo, hi) ⇒ (0 <? lo)%Z || (hi <? 0)%Z
| None ⇒ false
end.
Whether the balance of the atom refutes a sequent in a calculus:
the calculus has no weakening and no cut, and the interval excludes
zero.
Definition unbalanced (R : rules) (l : list formula) : bool :=
negb (weakening R) && negb (cut R) && excluded (excesses l).
negb (weakening R) && negb (cut R) && excluded (excesses l).
If unbalanced holds, the sequent is not derivable.
Theorem unbalanced_refutation : ∀ R l, unbalanced R l = true → ¬ ll R l.
Proof.
intros R l U H. unfold unbalanced in U.
apply andb_prop in U as [U E]. apply andb_prop in U as [W K].
apply negb_true_iff in W, K.
pose proof (balance R l H W K) as B.
destruct (excesses l) as [[lo hi]|]; cbn in *; [| discriminate].
apply orb_true_iff in E as [E | E]; apply Z.ltb_lt in E; lia.
Qed.
End Balance.
Proof.
intros R l U H. unfold unbalanced in U.
apply andb_prop in U as [U E]. apply andb_prop in U as [W K].
apply negb_true_iff in W, K.
pose proof (balance R l H W K) as B.
destruct (excesses l) as [[lo hi]|]; cbn in *; [| discriminate].
apply orb_true_iff in E as [E | E]; apply Z.ltb_lt in E; lia.
Qed.
End Balance.
Fixpoint mll (A : formula) : bool :=
match A with
| var _ | covar _ | one | bot ⇒ true
| tens A B | parr A B ⇒ mll A && mll B
| top | zero | awith _ _ | aplus _ _ | oc _ | wn _ ⇒ false
end.
match A with
| var _ | covar _ | one | bot ⇒ true
| tens A B | parr A B ⇒ mll A && mll B
| top | zero | awith _ _ | aplus _ _ | oc _ | wn _ ⇒ false
end.
#⊗ − #⅋ − #1 + #⊥ of a formula.
Fixpoint weight (A : formula) : Z :=
match A with
| one ⇒ (-1)%Z
| bot ⇒ 1%Z
| tens A B ⇒ (1 + weight A + weight B)%Z
| parr A B ⇒ (-1 + weight A + weight B)%Z
| _ ⇒ 0%Z
end.
match A with
| one ⇒ (-1)%Z
| bot ⇒ 1%Z
| tens A B ⇒ (1 + weight A + weight B)%Z
| parr A B ⇒ (-1 + weight A + weight B)%Z
| _ ⇒ 0%Z
end.
The weight of a sequent: the sum over its formulas.
Fixpoint weights (l : list formula) : Z :=
match l with
| [] ⇒ 0%Z
| A :: l ⇒ (weight A + weights l)%Z
end.
Lemma weights_app : ∀ l1 l2, weights (l1 ++ l2) = (weights l1 + weights l2)%Z.
Proof. induction l1 as [|A l1 IH]; intro l2; cbn; [| rewrite IH]; lia. Qed.
Lemma weights_perm : ∀ l1 l2, Permutation l1 l2 → weights l1 = weights l2.
Proof. intros l1 l2 H. induction H; cbn; lia. Qed.
Lemma forallb_perm : ∀ (f : formula → bool) l1 l2,
Permutation l1 l2 → forallb f l1 = forallb f l2.
Proof.
intros f l1 l2 H. induction H; cbn.
- reflexivity.
- now rewrite IHPermutation.
- destruct (f x), (f y); reflexivity.
- congruence.
Qed.
match l with
| [] ⇒ 0%Z
| A :: l ⇒ (weight A + weights l)%Z
end.
Lemma weights_app : ∀ l1 l2, weights (l1 ++ l2) = (weights l1 + weights l2)%Z.
Proof. induction l1 as [|A l1 IH]; intro l2; cbn; [| rewrite IH]; lia. Qed.
Lemma weights_perm : ∀ l1 l2, Permutation l1 l2 → weights l1 = weights l2.
Proof. intros l1 l2 H. induction H; cbn; lia. Qed.
Lemma forallb_perm : ∀ (f : formula → bool) l1 l2,
Permutation l1 l2 → forallb f l1 = forallb f l2.
Proof.
intros f l1 l2 H. induction H; cbn.
- reflexivity.
- now rewrite IHPermutation.
- destruct (f x), (f y); reflexivity.
- congruence.
Qed.
What the count equation says of a sequent in a calculus.
Definition counted (R : rules) (l : list formula) : Prop :=
if mix R then (weights l + 2 ≤ Z.of_nat (length l))%Z
else Z.of_nat (length l) = (weights l + 2)%Z.
if mix R then (weights l + 2 ≤ Z.of_nat (length l))%Z
else Z.of_nat (length l) = (weights l + 2)%Z.
Without weakening and without cut, every derivable sequent of
multiplicative formulas with units has as many formulas as the
equation says, or at least as many with Mix.
Theorem count_equation : ∀ R l,
ll R l → weakening R = false → cut R = false → forallb mll l = true → counted R l.
Proof.
intros R l H W K. unfold counted.
induction H; cbn [weights weight length forallb mll andb] in *; intro M.
- destruct (mix R); lia.
- rewrite <- (Permutation_length H0), <- (weights_perm _ _ H0).
apply IHll. now rewrite (forallb_perm _ _ _ H0).
- destruct (mix R); lia.
- specialize (IHll M). destruct (mix R); lia.
- discriminate.
- rewrite forallb_app in M.
apply andb_prop in M as [M M2]. apply andb_prop in M as [MA MB].
apply andb_prop in M2 as [M1 M2].
specialize (IHll1 (andb_true_intro (conj MA M1))).
specialize (IHll2 (andb_true_intro (conj MB M2))).
rewrite length_app, weights_app. destruct (mix R); lia.
- apply andb_prop in M as [M M1]. apply andb_prop in M as [MA MB].
specialize (IHll (andb_true_intro (conj MA (andb_true_intro (conj MB M1))))).
destruct (mix R); lia.
- discriminate.
- discriminate.
- discriminate.
- discriminate.
- discriminate.
- discriminate.
- discriminate.
- rewrite forallb_app in M. apply andb_prop in M as [M1 M2].
specialize (IHll1 M1). specialize (IHll2 M2).
match goal with E : mix R = true |- _ ⇒ rewrite E in × end.
rewrite length_app, weights_app. lia.
- congruence.
- congruence.
Qed.
ll R l → weakening R = false → cut R = false → forallb mll l = true → counted R l.
Proof.
intros R l H W K. unfold counted.
induction H; cbn [weights weight length forallb mll andb] in *; intro M.
- destruct (mix R); lia.
- rewrite <- (Permutation_length H0), <- (weights_perm _ _ H0).
apply IHll. now rewrite (forallb_perm _ _ _ H0).
- destruct (mix R); lia.
- specialize (IHll M). destruct (mix R); lia.
- discriminate.
- rewrite forallb_app in M.
apply andb_prop in M as [M M2]. apply andb_prop in M as [MA MB].
apply andb_prop in M2 as [M1 M2].
specialize (IHll1 (andb_true_intro (conj MA M1))).
specialize (IHll2 (andb_true_intro (conj MB M2))).
rewrite length_app, weights_app. destruct (mix R); lia.
- apply andb_prop in M as [M M1]. apply andb_prop in M as [MA MB].
specialize (IHll (andb_true_intro (conj MA (andb_true_intro (conj MB M1))))).
destruct (mix R); lia.
- discriminate.
- discriminate.
- discriminate.
- discriminate.
- discriminate.
- discriminate.
- discriminate.
- rewrite forallb_app in M. apply andb_prop in M as [M1 M2].
specialize (IHll1 M1). specialize (IHll2 M2).
match goal with E : mix R = true |- _ ⇒ rewrite E in × end.
rewrite length_app, weights_app. lia.
- congruence.
- congruence.
Qed.
Whether the count equation refutes a sequent in a calculus: the
calculus has no weakening and no cut, the formulas are
multiplicative with units, and their number is not what the
equation asks for (with Mix: fewer).
Definition fails_equation (R : rules) (l : list formula) : bool :=
negb (weakening R) && negb (cut R) && forallb mll l
&& (if mix R then (Z.of_nat (length l) <? weights l + 2)%Z
else negb (Z.of_nat (length l) =? weights l + 2)%Z).
negb (weakening R) && negb (cut R) && forallb mll l
&& (if mix R then (Z.of_nat (length l) <? weights l + 2)%Z
else negb (Z.of_nat (length l) =? weights l + 2)%Z).
If fails_equation holds, the sequent is not derivable.
Theorem equation_refutation : ∀ R l, fails_equation R l = true → ¬ ll R l.
Proof.
intros R l F H. unfold fails_equation in F.
apply andb_prop in F as [F E]. apply andb_prop in F as [F M].
apply andb_prop in F as [W K]. apply negb_true_iff in W, K.
pose proof (count_equation R l H W K M) as C. unfold counted in C.
destruct (mix R).
- apply Z.ltb_lt in E. lia.
- apply negb_true_iff, Z.eqb_neq in E. lia.
Qed.
Proof.
intros R l F H. unfold fails_equation in F.
apply andb_prop in F as [F E]. apply andb_prop in F as [F M].
apply andb_prop in F as [W K]. apply negb_true_iff in W, K.
pose proof (count_equation R l H W K M) as C. unfold counted in C.
destruct (mix R).
- apply Z.ltb_lt in E. lia.
- apply negb_true_iff, Z.eqb_neq in E. lia.
Qed.
The two-sided calculus in the one-sided one
Fixpoint itr (A : iformula) : formula :=
match A with
| ivar a ⇒ var a
| ione ⇒ one
| itens A B ⇒ tens (itr A) (itr B)
| ilmap A B ⇒ parr (dual (itr A)) (itr B)
| itop ⇒ top
| iwith A B ⇒ awith (itr A) (itr B)
| izero ⇒ zero
| iplus A B ⇒ aplus (itr A) (itr B)
| ioc A ⇒ oc (itr A)
end.
match A with
| ivar a ⇒ var a
| ione ⇒ one
| itens A B ⇒ tens (itr A) (itr B)
| ilmap A B ⇒ parr (dual (itr A)) (itr B)
| itop ⇒ top
| iwith A B ⇒ awith (itr A) (itr B)
| izero ⇒ zero
| iplus A B ⇒ aplus (itr A) (itr B)
| ioc A ⇒ oc (itr A)
end.
A two-sided sequent Γ ⊢ C as the one-sided sequent ⊢ C, Γ⊥.
Definition one_sided (G : list iformula) (C : iformula) : list formula :=
itr C :: map (fun A ⇒ dual (itr A)) G.
itr C :: map (fun A ⇒ dual (itr A)) G.
The one-sided calculus for a two-sided one: no Mix, and the same
weakening and cut.
Definition lrules (R : irules) : rules :=
{| mix := false; weakening := iweakening R; cut := icut R |}.
{| mix := false; weakening := iweakening R; cut := icut R |}.
The first two formulas exchanged.
Local Lemma swap : ∀ R (A B : formula) l, ll R (A :: B :: l) → ll R (B :: A :: l).
Proof. intros. eapply ex_r; [eassumption | apply perm_swap]. Qed.
Proof. intros. eapply ex_r; [eassumption | apply perm_swap]. Qed.
Every derivation in the two-sided calculus gives a derivation of
the sequent's one-sided translation, without Mix and with the same
weakening and cut.
Theorem ill_ll : ∀ R G C, ill R G C → ll (lrules R) (one_sided G C).
Proof.
intros R G C H. unfold one_sided. induction H; cbn in ×.
- apply swap, ax_r.
- eapply ex_r; [exact IHill |]. apply perm_skip, Permutation_map, H0.
- apply one_r.
- apply swap, bot_r, IHill.
- rewrite map_app. apply tens_r; assumption.
- apply swap, parr_r.
eapply ex_r; [exact IHill |].
apply perm_trans with (dual (itr A) :: itr C :: dual (itr B) :: map (fun A ⇒ dual (itr A)) l);
[apply perm_swap | apply perm_skip, perm_swap].
- apply parr_r. apply swap. exact IHill.
- rewrite dual_dual, map_app. apply swap.
eapply ex_r.
+ apply (tens_r _ (itr A) (dual (itr B)) (map (fun A ⇒ dual (itr A)) l1)
(itr C :: map (fun A ⇒ dual (itr A)) l2)); [exact IHill1 | apply swap, IHill2].
+ apply perm_skip. symmetry. apply Permutation_middle.
- apply top_r.
- apply with_r; assumption.
- apply swap, plus_r1, swap, IHill.
- apply swap, plus_r2, swap, IHill.
- apply swap, top_r.
- apply plus_r1. exact IHill.
- apply plus_r2. exact IHill.
- apply swap, with_r; apply swap; assumption.
- rewrite map_map in ×. cbn in ×.
replace (map (fun x ⇒ wn (dual (itr x))) l) with (map wn (map (fun x ⇒ dual (itr x)) l))
in × by now rewrite map_map.
apply oc_r, IHill.
- apply swap, de_r, swap, IHill.
- apply swap, wk_r, IHill.
- apply swap, co_r.
eapply ex_r; [exact IHill |].
apply perm_trans with (wn (dual (itr A)) :: itr C :: wn (dual (itr A)) :: map (fun A ⇒ dual (itr A)) l);
[apply perm_swap | apply perm_skip, perm_swap].
- apply swap, weakening_r; [exact H | exact IHill].
- rewrite map_app. eapply ex_r.
+ refine (cut_r (lrules R) _ (itr A) (map (fun A ⇒ dual (itr A)) l1)
(itr C :: map (fun A ⇒ dual (itr A)) l2) _ _); [assumption | exact IHill1 |].
apply swap, IHill2.
+ symmetry. apply Permutation_middle.
Qed.
Proof.
intros R G C H. unfold one_sided. induction H; cbn in ×.
- apply swap, ax_r.
- eapply ex_r; [exact IHill |]. apply perm_skip, Permutation_map, H0.
- apply one_r.
- apply swap, bot_r, IHill.
- rewrite map_app. apply tens_r; assumption.
- apply swap, parr_r.
eapply ex_r; [exact IHill |].
apply perm_trans with (dual (itr A) :: itr C :: dual (itr B) :: map (fun A ⇒ dual (itr A)) l);
[apply perm_swap | apply perm_skip, perm_swap].
- apply parr_r. apply swap. exact IHill.
- rewrite dual_dual, map_app. apply swap.
eapply ex_r.
+ apply (tens_r _ (itr A) (dual (itr B)) (map (fun A ⇒ dual (itr A)) l1)
(itr C :: map (fun A ⇒ dual (itr A)) l2)); [exact IHill1 | apply swap, IHill2].
+ apply perm_skip. symmetry. apply Permutation_middle.
- apply top_r.
- apply with_r; assumption.
- apply swap, plus_r1, swap, IHill.
- apply swap, plus_r2, swap, IHill.
- apply swap, top_r.
- apply plus_r1. exact IHill.
- apply plus_r2. exact IHill.
- apply swap, with_r; apply swap; assumption.
- rewrite map_map in ×. cbn in ×.
replace (map (fun x ⇒ wn (dual (itr x))) l) with (map wn (map (fun x ⇒ dual (itr x)) l))
in × by now rewrite map_map.
apply oc_r, IHill.
- apply swap, de_r, swap, IHill.
- apply swap, wk_r, IHill.
- apply swap, co_r.
eapply ex_r; [exact IHill |].
apply perm_trans with (wn (dual (itr A)) :: itr C :: wn (dual (itr A)) :: map (fun A ⇒ dual (itr A)) l);
[apply perm_swap | apply perm_skip, perm_swap].
- apply swap, weakening_r; [exact H | exact IHill].
- rewrite map_app. eapply ex_r.
+ refine (cut_r (lrules R) _ (itr A) (map (fun A ⇒ dual (itr A)) l1)
(itr C :: map (fun A ⇒ dual (itr A)) l2) _ _); [assumption | exact IHill1 |].
apply swap, IHill2.
+ symmetry. apply Permutation_middle.
Qed.
An intuitionistic formula's classical reading, with ⊸ read as
implication.
Fixpoint ieval (v : atom → bool) (A : iformula) : bool :=
match A with
| ivar a ⇒ v a
| ione | itop ⇒ true
| izero ⇒ false
| itens A B | iwith A B ⇒ ieval v A && ieval v B
| iplus A B ⇒ ieval v A || ieval v B
| ilmap A B ⇒ implb (ieval v A) (ieval v B)
| ioc A ⇒ ieval v A
end.
Lemma eval_itr : ∀ v A, eval v (itr A) = ieval v A.
Proof.
intros v A. induction A; cbn; rewrite ?eval_dual, ?IHA, ?IHA1, ?IHA2; try reflexivity.
destruct (ieval v A1), (ieval v A2); reflexivity.
Qed.
match A with
| ivar a ⇒ v a
| ione | itop ⇒ true
| izero ⇒ false
| itens A B | iwith A B ⇒ ieval v A && ieval v B
| iplus A B ⇒ ieval v A || ieval v B
| ilmap A B ⇒ implb (ieval v A) (ieval v B)
| ioc A ⇒ ieval v A
end.
Lemma eval_itr : ∀ v A, eval v (itr A) = ieval v A.
Proof.
intros v A. induction A; cbn; rewrite ?eval_dual, ?IHA, ?IHA1, ?IHA2; try reflexivity.
destruct (ieval v A1), (ieval v A2); reflexivity.
Qed.
True hypotheses read as false once negated in the one-sided
translation.
Lemma duals_false : ∀ v G,
forallb (ieval v) G = true → existsb (eval v) (map (fun A ⇒ dual (itr A)) G) = false.
Proof.
intros v G T. induction G as [|A G IH]; cbn in *; [reflexivity |].
apply andb_prop in T as [TA TG].
rewrite eval_dual, eval_itr, TA. exact (IH TG).
Qed.
forallb (ieval v) G = true → existsb (eval v) (map (fun A ⇒ dual (itr A)) G) = false.
Proof.
intros v G T. induction G as [|A G IH]; cbn in *; [reflexivity |].
apply andb_prop in T as [TA TG].
rewrite eval_dual, eval_itr, TA. exact (IH TG).
Qed.
Every derivable two-sided sequent, in either calculus, reads as a
tautology: when every hypothesis is true, so is the conclusion.
Theorem ill_tautology : ∀ R G C, ill R G C →
∀ v, forallb (ieval v) G = true → ieval v C = true.
Proof.
intros R G C H v T.
pose proof (ll_tautology _ _ (ill_ll R G C H) v) as E.
unfold one_sided in E. cbn in E. rewrite eval_itr, (duals_false v G T) in E.
now rewrite orb_false_r in E.
Qed.
∀ v, forallb (ieval v) G = true → ieval v C = true.
Proof.
intros R G C H v T.
pose proof (ll_tautology _ _ (ill_ll R G C H) v) as E.
unfold one_sided in E. cbn in E. rewrite eval_itr, (duals_false v G T) in E.
now rewrite orb_false_r in E.
Qed.
An assignment that makes the translation false shows that the
two-sided sequent is not derivable.
Theorem iclassical_refutation : ∀ R v G C,
falsifies v (one_sided G C) = true → ¬ ill R G C.
Proof.
intros R v G C F H. exact (classical_refutation _ v _ F (ill_ll R G C H)).
Qed.
falsifies v (one_sided G C) = true → ¬ ill R G C.
Proof.
intros R v G C F H. exact (classical_refutation _ v _ F (ill_ll R G C H)).
Qed.
An unbalanced atom in the translation shows that the two-sided
sequent is not derivable.
Theorem iunbalanced_refutation : ∀ atom_eqb a R G C,
unbalanced atom_eqb a (lrules R) (one_sided G C) = true → ¬ ill R G C.
Proof.
intros atom_eqb a R G C U H. exact (unbalanced_refutation atom_eqb a _ _ U (ill_ll R G C H)).
Qed.
unbalanced atom_eqb a (lrules R) (one_sided G C) = true → ¬ ill R G C.
Proof.
intros atom_eqb a R G C U H. exact (unbalanced_refutation atom_eqb a _ _ U (ill_ll R G C H)).
Qed.
A failed count equation of the translation shows that the
two-sided sequent is not derivable.