proposition: Theorem BPCP_satis R : ~ PCPb R <-> satis (¬ F R).
proof: Proof. rewrite PCPb_iff_dPCPb. split. - intros H. exists (list bool), (IB R), (fun _ => nil). intros H'. cbn. apply H, (IB_F H'). - rewrite <- PCPb_iff_dPCPb. intros H1 H2 % (BPCP_valid R (ff:=falsity_on)). apply (valid_satis H2), H1. Qed.
imports: Undecidability.PCP(PCP Util.PCP_facts) Undecidability.FOL(Deduction.FragmentNDFacts Semantics.Tarski.FragmentFacts Semantics.Tarski.FragmentSoundness Syntax.Core Syntax.Facts) Undecidability.FOL(FOL) Undecidability.Synthetic(Definitions DecidabilityFacts EnumerabilityFacts ReducibilityFacts MoreReducibilityFacts) Undecidability.PCP.Reductions.PCPb_iff_dPCPb Undecidability(Shared.ListAutomation)