proposition: Fact Σ2_has_tuples_spec l n ψ : ⟪Σ2_has_tuples l n⟫ ψ <-> mb_has_tuples mem (ψ l) n.
proof: Proof. unfold Σ2_has_tuples. rewrite fol_sem_mforall. fol equiv fa; intros v. rewrite fol_sem_bin_fix. fol equiv imp. + rewrite fol_sem_vec_fa. fol equiv; intros p. rew vec; simpl. now rewrite env_vlift_fix0, env_vlift_fix1. + rewrite fol_sem_quant_fix. fol equiv ex; intros x. rewrite Σ2_is_tuple_spec; simpl. fol equiv rel. apply vec_pos_ext; intros p. rew vec; simpl. rewrite env_vlift_fix0; auto. Qed.
imports: List Arith Nat Lia Max Wellfounded Coq.Setoids.Setoid Undecidability.Shared.Libs.DLW.Utils(utils_tac utils_list finite) Undecidability.Shared.Libs.DLW.Vec(pos vec) Undecidability.FOL.TRAKHTENBROT(notations fol_ops fo_sig fo_terms fo_logic)