Post's Theorem and Markov's Principle


Require Export Reductions.
Require Import ConstructiveEpsilon.

Definition stable P := ~~ P P.

Definition MP := f : bool, stable ( n, f n = true).

Definition (p : Prop) :
  ( x, dec (p x)) ex p sig p.
Proof.
  apply constructive_indefinite_ground_description_nat_Acc.
Defined.


Local Notation R p :=
  ( x y : x = S y p y).

Lemma Acc_ind_dep (A : Type) (R : A A Prop) (P : a, Acc R a Prop) :
  ( x (F : ( y, R y x Acc R y)), ( y (Hy : R y x), P y (F y Hy)) P x (Acc_intro x F))
   x (h : Acc R x), P x h.
Proof.
  refine (fix f H x h := match h with Acc_intro _ F _ end).
  apply H. intros y Hy. apply f, H.
Qed.


Notation mu' d H := (proj1_sig ( d H)).

Lemma mu_least (p : Prop) (d : x, dec (p x)) (H : ex p) :
   n, p n mu' d H n.
Proof.
  intros n H'. unfold , constructive_indefinite_ground_description_nat_Acc.
  unfold acc_implies_P_eventually. assert (Hn : 0 n) by omega. revert n H' Hn.
  generalize 0, (P_eventually_implies_acc_ex p H). clear H.
  intros k H. pattern k, H. apply (@Acc_ind_dep (R p)). clear k H.
  intros k F IH n . cbn. destruct (d k) as [H|H]; trivial.
  destruct Fix_F eqn : E. rewrite E. apply IH; trivial. clear E.
  apply le_lt_eq_dec in as [|]; subst; tauto.
Qed.


Definition ldecidable X (p : X Prop) :=
   x, p x p x.

Lemma weakPost X (p : X Prop) : discrete X
  ldecidable p enumerable p enumerable (compl p) decidable p.
Proof.
  intros [E] % discrete_iff Hl [f Hf] [g Hg].
  eapply decidable_iff. econstructor. intros x.
  assert ( n, f n = Some x g n = Some x) by (destruct (Hl x); firstorder).
  destruct ( (p := n f n = Some x g n = Some x)) as [n HN]; trivial.
  - intros n. exact _.
  - decide (f n = Some x); decide (g n = Some x); firstorder.
Qed.


Fact stable_red X Y (p : X Prop) (q : Y Prop) :
  p q ( y, stable (q y)) ( x, stable (p x)).
Proof.
  intros [f H] H' x. unfold stable.
  repeat rewrite H. apply H'.
Qed.


Lemma MP_to_decMP :
  MP ( p : Prop, decidable p stable ( n, p n)).
Proof.
  intros H p [d Hd] ?.
  specialize (H ( x if d x then true else false)).
  destruct H.
  - intros ?. eapply . intros [n]. eapply H. exists n. now eapply Hd in as .
  - specialize (Hd x). destruct (d x); try congruence. exists x. now eapply Hd.
Qed.


Lemma decMP_to_eMP :
  ( p : Prop, decidable p stable ( n, p n)) ( X (p : X Prop), enumerable p stable ( n, p n)).
Proof.
  intros dMP X p [e He] ?. destruct (dMP ( n e n None)).
  - exists ( n match e n with Some _ true | _ false end). intros; destruct (e x); firstorder congruence.
  - intros ?. eapply H. intros [x]. eapply . eapply He in as [n].
    exists n. congruence.
  - destruct (e x) eqn:E; try congruence. exists . eapply He. now exists x.
Qed.


Lemma eMP_to_MP :
  ( X (p : X Prop), enumerable p stable ( n, p n)) MP.
Proof.
  intros eMP f ?. destruct (eMP ( n f n = true)).
  - eapply dec_count_enum. now exists f. exists Some. eauto.
  - firstorder.
  - eauto.
Qed.


Lemma MP_enum_stable X (p : X Prop) :
  MP enumerable p discrete X x, stable (p x).
Proof.
  intros MP [f Hf] [d Hd] x. eapply MP_to_decMP with (p := n f n = Some x) in MP.
  - intros H. rewrite Hf in *. now eapply MP.
  - exists ( n match f n with Some x' d (x, x') | _ false end).
    intros . destruct (f ). rewrite (Hd (x,)). split. inversion 1. eauto. intros . eauto.
    split; inversion 1.
Qed.


Definition POST' :=
   X (p : X Prop), discrete X enumerable p enumerable ( x p x) ldecidable p.

Theorem MP_Post :
  MP POST'.
Proof.
  intros mp X p HX [f Hf] [g Hg].
  cut ( x, n, f n = Some x g n = Some x).
  - intros H x. destruct (H x); firstorder.
  - intros x. apply (MP_to_decMP mp).
    + apply discrete_iff in HX as [H]. apply decidable_iff.
      constructor. intros n. exact _.
    + intros H. assert ( : (p x p x)) by tauto. firstorder.
Qed.


Lemma Post_to' :
   POST' MP.
Proof.
  intros HP. apply eMP_to_MP. apply decMP_to_eMP.
  intros p [Hp] % decidable_iff H. destruct (HP ( _ n, p n)) with (x:=0); trivial.
  - eapply discrete_iff. econstructor. exact _.
  - change (enumerable ( m n, ( (x : * ) p (snd x)) (m,n))).
    apply projection. eapply dec_count_enum; try apply enumerable_nat_nat.
    apply decidable_iff. constructor. intros [n m]. exact _.
  - exists ( _ None). intros x. firstorder congruence.
  - contradiction.
Qed.


Definition POST :=
   X (p : X Prop), discrete X enumerable p enumerable ( x p x) decidable p.

Lemma Post_MP :
  POST MP.
Proof.
  split; intros.
  - intros ?. eapply Post_to'.
    intros ? ? ? ? ? ?. destruct (H X p ) as [g].
    specialize ( x). destruct (g x); firstorder congruence.
  - intros ? ? ? ? ?. eapply weakPost; eauto.
    eapply MP_Post; eauto.
Qed.