Skip to main content
3 of 4
added 18 characters in body; edited tags; edited title
Asaf Karagila
  • 39.7k
  • 8
  • 134
  • 282

Definability of Gödel's pairing function on ordinals

Given an infinite cardinal $\kappa$, Gödel's function is a well-known bijection $p:\kappa^2\to\kappa$.

Is $p$ definable in the structure $\langle\kappa;\in\rangle$?

Is $p$ definable in a bigger 2nd order structure $\langle\kappa;\mathcal P(\kappa);\in\rangle$?

It looks like any typical attempt to code something like this (even + on ordinals) somehow refers to a pairing function.