proposition: Fact decode_encode x y : decode (enc_npair x y) = (x, y).
proof: Proof. revert x y. enough (forall n x y, enc_npair x y = n -> decode n = (x, y)) by eauto. induction n as [|n IH]; intros x y; cbn. - destruct x, y; cbn. 1: reflexivity. all: intros [=]. - destruct y; cbn. + destruct x; cbn. * intros [=]. * intros [= <-]. rewrite (IH 0 x). 1: reflexivity. unfold enc_npair. replace (x + 0) with x by lia. reflexivity. + intros [= <-]. rewrite (IH (S x) y). 1: reflexivity. unfold enc_npair. replace (y + S x) with (S y + x) by lia. reflexivity. Qed.
imports: Undecidability.FOL(Semantics.FiniteTarski.Full) Undecidability.FOL(Syntax.Facts Semantics.Tarski.FullFacts Syntax.BinSig) Undecidability.SeparationLogic(MSL) Undecidability.Shared(Dec) Undecidability.Synthetic.DecidabilityFacts List