proposition: Theorem exdec : forall (P : nat -> Prop) (N : nat), (forall n : nat, P n \/ ~ P n) -> (exists x : nat, x < N /\ P x) \/ ~ (exists x : nat, x < N /\ P x).
proof: Proof. intro P. simple induction N. intro decP. right. intro. elim H. intros. elim H0. intros. elim (lt_n_O x). assumption. intros M IH decP. elim IH. left. elim H. intros. split with x. elim H0. intros. split. apply lt_S. assumption. assumption. intros. elim (decP M). left. split with M. split. apply lt_n_Sn. assumption. right. intro. elim H1. intros. elim H2. intros. unfold lt in H3. elim (le_lt_or_eq x M). intro. apply H. split with x. split. assumption. assumption. intro. apply H0. rewrite <- H5. assumption. apply le_S_n. assumption. assumption. Qed.
imports: Arith ZArith EqNat