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?
$\begingroup$
$\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 WeaverCommented 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$– Colin McLartyCommented Dec 8, 2012 at 22:32
Add a comment
|