Definition of Tarski Semantics


From Undecidability.FOLC Require Import GenTarski FullFOL.

(* *** Tarki Models **)

Section Tarski.
  Context { : Signature}.

  (* **** Semantic notions *)

  Section Semantics.

    Variable domain : Type.

    Context {I : interp domain }.

    Fixpoint sat ( : env domain) ( : form) : Prop :=
      match with
      | Pred P v i_P (Vector.map (eval ) v)
      | Fal False
      | Impl sat sat
      | Conj sat sat
      | Disj sat sat
      | Ex d : domain, sat (d .: )
      | All d : domain, sat (d .: )
      end.

  End Semantics.

  Arguments sat {_ _} _ _, _ _ _ _.

  Notation "rho ⊨ phi" := (sat ) (at level 20).

  Fixpoint list_or (A : list form) : form :=
    match A with
    | nil
    | ::A list_or A
    end.

  Lemma list_or_spec A D (I : interp D) :
     list_or A , A .
  Proof.
    induction A; cbn; split; auto.
    - firstorder.
    - intros [H|H].
      + exists a. tauto.
      + apply IHA in H as [[ ]]. exists . tauto.
    - intros [ [[|] H]]; auto.
      right. apply IHA. now exists .
  Qed.


  Definition constraint := D, interp D Prop.
  Definition con_subs (C C' : constraint) := ( D (I : interp D), C' D I C D I).
  Definition classical D (I : interp D) :=
     , ((( --> ) --> ) --> ).

  Definition has_model (C : constraint) (T : theory) :=
     D (I : interp D) , ( , T ) C D I.
  Definition valid_T (C : constraint) (T : theory) ( : form) :=
     D (I : interp D), C D I , ( , T ) .
  Definition valid_L (C : constraint) A :=
     D (I : interp D), C D I , ( , A ) .

  Notation "T '⊫<' C '>' phi" := (valid_T C T ) (at level 50).

  (*Lemma sat_and_iff D (I : interp D) rho phi psi :
    classical I -> sat rho phi /\ sat rho psi <-> sat rho (phi ∧ psi).
  Proof.
    cbn. repeat split. intuition. specialize (H rho phi ⊥). cbn in H. tauto. intuition. tauto. firstorder.
  Qed.*)


  (* **** Model relationships **)

  Lemma valid_T_subsumption (C C' : constraint) T :
    con_subs C C' valid_T C T valid_T C' T .
  Proof.
    firstorder.
  Qed.


  (* **** Substitution properties **)

  Section Substs.
    Variable D : Type.
    Variable I : interp D.

    Hint Unfold funcomp.

    Lemma eval_ext t :
      ( x, x = x) eval t = eval t.
    Proof.
      intros H; induction t using strong_term_ind; comp; try congruence.
      f_equal. now apply vec_map_ext.
    Qed.


    Lemma eval_comp t :
      eval (subst_term t) = eval ( >> eval ) t.
    Proof.
      induction t using strong_term_ind; comp; try congruence.
      f_equal. erewrite vec_comp. 2: reflexivity. now apply vec_map_ext.
    Qed.


    Lemma sat_ext :
      ( x, x = x) .
    Proof.
      induction in , |-*; intros Hext; comp.
      - tauto.
      - now rewrite (vec_ext ( x eval_ext x Hext)).
      - now erewrite , .
      - now erewrite , .
      - now erewrite , .
      - split; intros H' d; eapply (IHphi (d .: ) (d .: ) _), H'.
        Unshelve. all: (intros []; cbn; congruence).
      - split; intros [d H']; exists d; eapply (IHphi (d .: ) (d .: ) _), H'.
        Unshelve. all: (intros []; cbn; congruence).
    Qed.


    Lemma sat_comp :
       (subst_form ) ( >> eval ) .
    Proof.
      induction in , |-*; comp.
      - tauto.
      - erewrite vec_comp. 2: reflexivity. now rewrite (vec_ext ( x eval_comp x)).
      - now rewrite , .
      - now rewrite , .
      - now rewrite , .
      - setoid_rewrite IHphi. split; intros H d; eapply sat_ext. 2, 4: apply (H d).
        all: intros []; comp; rewrite? eval_comp; now comp.
      - setoid_rewrite IHphi. split; intros [d H]; exists d; eapply sat_ext. 2, 4: apply H.
        all: intros []; comp; rewrite? eval_comp; now comp.
    Qed.


    Lemma sat_subst :
      ( x, eval ( x) = x) (subst_form ).
    Proof.
      intros Hsigma. rewrite sat_comp. apply sat_ext. now comp.
    Qed.

  End Substs.

End Tarski.

Arguments sat {_ _ _} _ _, _ _ _ _ _.
Notation "rho ⊨ phi" := (sat ) (at level 20).

Arguments valid_T {_} _ _ _.
Notation "T '⊫<' C '>' phi" := (valid_T C T ) (at level 50).