proposition: Lemma bounded_dec {ff : falsity_flag} phi : forall n, dec (bounded n phi).
proof: Proof. Proof using sig_preds_dec sig_funcs_dec. induction phi; intros n. - left. constructor. - destruct (@vec_all_dec _ _ t (bounded_t n)) as [H|H]. + intros t' _. apply bounded_t_dec. + left. now constructor. + right. inversion 1. apply (inj_pair2_eq_dec _ sig_preds_dec) in H5 as ->. tauto. - destruct (IHphi1 n) as [H|H], (IHphi2 n) as [H'|H']. 2-4: right; invert_bounds; tauto. left. now constructor. - destruct (IHphi (S n)) as [H|H]. + left. now constructor. + right. invert_bounds. tauto. Qed.
imports: Undecidability.Synthetic(Definitions DecidabilityFacts EnumerabilityFacts ListEnumerabilityFacts ReducibilityFacts) Undecidability(Shared.ListAutomation Shared.Dec) Coq(Eqdep_dec PeanoNat) Coq.Vectors.Vector Undecidability.Shared.Libs.PSL.Vectors(Vectors) EqdepFacts