3

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?

flag
2 
 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". – Nik Weaver Dec 8 at 18:45
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. – Colin McLarty Dec 8 at 22:32

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.