Skip to main content
Replaced the newly created tag by an existing one
Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
added 18 characters in body; edited tags; edited title
Source Link
Asaf Karagila
  • 39.7k
  • 8
  • 134
  • 282

Definability of Goedel'sGödel's pairing function on ordinals

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

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

Is $p$ definable in a bigger 2nd order structure $<\kappa;\mathcal P(\kappa);\in>$$\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.

Definability of Goedel's pairing function on ordinals

Given an infinite cardinal $\kappa$, Goedel's function is a well-known bijection $p:\kappa^2$ onto $\kappa$.

Is $p$ definable in the structure $<\kappa;\in>$?

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

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

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.

Added top-level tag
Link
gmvh
  • 3.1k
  • 6
  • 27
  • 45
Source Link
Loading