MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 '12 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 '12 at 22:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.