proposition: Lemma FST_derivations_bound T B k n x : FSTeq <<= T -> T ⊢ opair k x ∈ enc_derivations B n -> T ⊢ k ∈ σ (tnumeral n).
proof: Proof. induction n in T |- *; cbn; intros HT H. - apply FST_sing_iff in H; trivial. eapply FST_eq_elem; trivial. apply FST_sym'; trivial. eapply opair_inj1; trivial. apply H. apply FST_refl'; trivial. eapply FST_adj; trivial. apply DI1. apply FST_refl'; trivial. - apply FST_adj in H; trivial. apply (DE H). + apply FST_adj; auto. apply DI1. eapply opair_inj1; auto. + apply FST_adj; auto. Qed.
imports: Undecidability.FOL.Syntax.Facts Undecidability.FOL.Semantics.Tarski.FullFacts Undecidability.FOL.Deduction.FullNDFacts Undecidability.FOL.Sets.FST Undecidability.FOL.FST Undecidability.FOL.Reductions.PCPb_to_FST Undecidability.PCP(PCP Util.PCP_facts Reductions.PCPb_iff_dPCPb) Undecidability(Shared.ListAutomation)