3
$\begingroup$

Simpson's book uses a pairing function $\langle i,j\rangle = (i+j)^2+j$. Is that choice of function simply unimportant, or does it have expository advantages over the Cantor pairing, or does it have real advantages over the Cantor pairing in terms of quantifier complexity of proofs using it?

$\endgroup$
2
  • 2
    $\begingroup$ Well, the Cantor pairing function involves the fraction $1/2$. It wouldn't be hard to implement it in SOA, but you can't just write down the formula like we can for Simpson's pairing. So I'm going to go with "expository advantages". $\endgroup$
    – Nik Weaver
    Dec 8, 2012 at 18:45
  • $\begingroup$ Ah, and if I am not missing something, a key point is that the proof $\frac{n^2+n}{2}$ exists uses only bounded quantification. So there cannot be an issue of quantifier complexity. $\endgroup$ Dec 8, 2012 at 22:32

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.