Require Import Undecidability.FOL.Util.Syntax_facts.
Require Export Undecidability.FOL.Util.FullTarski.
From Undecidability Require Import Shared.ListAutomation.
Import ListAutomationNotations.
Require Import Vector.
Local Set Implicit Arguments.
Local Unset Strict Implicit.
Local Notation vec := Vector.t.
Section fixb.
Context {Σ_funcs : funcs_signature}.
Context {Σ_preds : preds_signature}.
Context {ff : falsity_flag}.
Fixpoint impl (A : list form) phi :=
match A with
| [] => phi
| psi :: A => bin Impl psi (impl A phi)
end.
End fixb.
Notation "A ==> phi" := (impl A phi) (right associativity, at level 55).
Tarski Semantics
Section Tarski.
Context {Σ_funcs : funcs_signature}.
Context {Σ_preds : preds_signature}.
Section Substs.
Variable D : Type.
Variable I : interp D.
Lemma eval_ext rho xi t :
(forall x, rho x = xi x) -> eval rho t = eval xi t.
Proof.
intros H. induction t; cbn.
- now apply H.
- f_equal. apply map_ext_in. now apply IH.
Qed.
Lemma eval_comp rho xi t :
eval rho (subst_term xi t) = eval (xi >> eval rho) t.
Proof.
induction t; cbn.
- reflexivity.
- f_equal. rewrite map_map. apply map_ext_in, IH.
Qed.
Lemma sat_ext {ff : falsity_flag} rho xi phi :
(forall x, rho x = xi x) -> rho ⊨ phi <-> xi ⊨ phi.
Proof.
induction phi as [ | b P v | | ] in rho, xi |- *; cbn; intros H.
- reflexivity.
- erewrite map_ext; try reflexivity. intros t. now apply eval_ext.
- specialize (IHphi1 rho xi). specialize (IHphi2 rho xi). destruct b0; intuition.
- destruct q.
+ split; intros H' d; eapply IHphi; try apply (H' d). 1,2: intros []; cbn; intuition.
+ split; intros [d H']; exists d; eapply IHphi; try apply H'. 1,2: intros []; cbn; intuition.
Qed.
Lemma sat_ext' {ff : falsity_flag} rho xi phi :
(forall x, rho x = xi x) -> rho ⊨ phi -> xi ⊨ phi.
Proof.
intros Hext H. rewrite sat_ext. exact H.
intros x. now rewrite (Hext x).
Qed.
Lemma sat_comp {ff : falsity_flag} rho xi phi :
rho ⊨ (subst_form xi phi) <-> (xi >> eval rho) ⊨ phi.
Proof.
induction phi as [ | b P v | | ] in rho, xi |- *; cbn.
- reflexivity.
- erewrite map_map, map_ext; try reflexivity. intros t. apply eval_comp.
- specialize (IHphi1 rho xi). specialize (IHphi2 rho xi). destruct b0; intuition.
- destruct q.
+ setoid_rewrite IHphi. split; intros H d; eapply sat_ext. 2, 4: apply (H d).
all: intros []; cbn; trivial; now setoid_rewrite eval_comp.
+ setoid_rewrite IHphi. split; intros [d H]; exists d; eapply sat_ext. 2, 4: apply H.
all: intros []; cbn; trivial; now setoid_rewrite eval_comp.
Qed.
Lemma sat_subst {ff : falsity_flag} rho sigma phi :
(forall x, eval rho (sigma x) = rho x) -> rho ⊨ phi <-> rho ⊨ (subst_form sigma phi).
Proof.
intros H. rewrite sat_comp. apply sat_ext. intros x. now rewrite <- H.
Qed.
Lemma sat_single {ff : falsity_flag} (rho : nat -> D) (Phi : form) (t : term) :
(eval rho t .: rho) ⊨ Phi <-> rho ⊨ subst_form (t..) Phi.
Proof.
rewrite sat_comp. apply sat_ext. now intros [].
Qed.
Lemma impl_sat {ff : falsity_flag} A rho phi :
sat rho (A ==> phi) <-> ((forall psi, psi el A -> sat rho psi) -> sat rho phi).
Proof.
induction A; cbn; firstorder congruence.
Qed.
Lemma impl_sat' {ff : falsity_flag} A rho phi :
sat rho (A ==> phi) -> ((forall psi, psi el A -> sat rho psi) -> sat rho phi).
Proof.
eapply impl_sat.
Qed.
End Substs.
End Tarski.
Section TM.
Context {Σ_funcs : funcs_signature}.
Context {Σ_preds : preds_signature}.
Instance TM : interp unit :=
{| i_func := fun _ _ => tt; i_atom := fun _ _ => True; |}.
Fact TM_sat (rho : nat -> unit) (phi : form falsity_off) :
rho ⊨ phi.
Proof.
revert rho. remember falsity_off as ff. induction phi; cbn; trivial.
- discriminate.
- destruct b0; auto.
- destruct q; firstorder. exact tt.
Qed.
End TM.