14
$\begingroup$

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.

$\endgroup$

2 Answers 2

15
$\begingroup$

For your first question, it's not hard to show with a back-and-forth argument that for any uncountable cardinal $\kappa$, the structure $\left<\kappa; \in\right>$ has $\left<\omega^\omega; \in\right>$ as an elementary substructure. This implies that $p$ cannot be first-order definable in $\left<\kappa; \in\right>$ (with $\kappa$ uncountable), since there exists $\alpha < \kappa$ such that for any $\beta,\gamma < \alpha$, $p(\beta,\gamma) < \alpha$, but by the argument given here, an ordinal has this property if and only if it is multiplicatively indecomposable, and $\omega^\omega$ is the first (infinite) multiplicatively indecomposable ordinal.

For your second question, I have a partial answer that probably can be leveraged into a full answer. Itay Neeman has a paper Monadic Definability of Ordinals which deals with some questions related to what is definable in monadic second order logic in $\left<\mathrm{On}; <\right>$. In it he shows that $\alpha + \beta$ and $\alpha \cdot \beta$ are not definable with $\alpha$ and $\beta$ with parameters (although oddly enough, the set of definable ordinals is closed under those operations). Assume that for arbitrarily large cardinals $\kappa$, there is a formula $\varphi(x,y,z)$ such that $\left<\kappa;\mathcal{P}(\kappa);\in\right> \models \varphi(\alpha,\beta,\gamma)$ if and only if $p(\alpha,\beta)=\gamma$. Then by the class pigeonhole principle, there is a single formula $\varphi(x,y,z)$ which works for arbitrarily large $\kappa$.

Now I claim that this would imply that $p$ is definable in $\left<\mathrm{On};<\right>$ in monadic second order logic. Specifically, we have that $p(\alpha,\beta)=\gamma$ if and only if there exists an ordinal $\delta > \max\{\alpha,\beta,\gamma\}$ such that in $\left< \delta; \mathcal{P}(\delta); \in\right>$ the formula $\varphi(x,y,z)$ defines a function $q: \delta^2 \to \delta$ such that

  • $q(x,y) < q(z,w)$ if and only if either $\max\{x,y\} < \max\{z,w\}$; $\max\{x,y\} = \max\{z,w\}$ and $x < z$; or $\max\{x,y\} = \max\{z,w\}$, $x=z$, and $y < w$ and
  • the function $q$ is a surjection onto $\delta$.

This is enough to ensure that $q$ is the restriction of $p$ to $\delta$. Since $\varphi(x,y,z)$ works for arbitrarily large $\kappa$, we have that this formula I have described does indeed define $p$.

Now that $p$ is definable, you have enough machinery to talk about maps between ordinals and you could define $\alpha +\beta$ as the smallest ordinal $\gamma > \alpha$ that has an order preserving map from $\beta$ whose range is disjoint from $\alpha$. Since $\alpha+\beta$ isn't definable (as a function), this is a contradiction, and we have that $p$ can't be definable in $\left<\kappa;\mathcal{P};\in\right>$ for arbitrarily large $\kappa$.

This argument can be extended to include definitions with parameters. This goes for the argument for the first question as well since Gödel's pairing function has an implicit definition that can be expressed in first-order logic.

By looking at Neeman's paper more closely, you could probably extract a more direct argument that gives that $p$ isn't definable for any $\kappa$.

$\endgroup$
11
  • $\begingroup$ Yes thank you it's very comprehensive. I supposed it should be in the negative. I am going to utilize $<\kappa,\mathcal P(\kappa),\in>$ as a proxy to study the definability in a bigger structure $H\kappa^+$ (all sets with transitive closure of size $\kappa$ or less). Thus the fix is to view the pairing function as a definability parameter along with $\in$. $\endgroup$ Feb 18, 2021 at 7:29
  • $\begingroup$ Gödel’s pairing function is quite specific. Could it be shown that $\langle\kappa,{\in}\rangle$ has no definable pairing function at all? (I wonder if there exist any ordered NIP structures with a pairing function.) $\endgroup$ Feb 18, 2021 at 10:45
  • $\begingroup$ (Without a linear order, a pairing function by itself is certainly not enough to guarantee IP: the structures $(H_k,{\in})$ in mathoverflow.net/a/302634 are stable.) $\endgroup$ Feb 18, 2021 at 12:04
  • $\begingroup$ @EmilJeřábek You probably know this, but Poizat showed that there is a (strictly) stable theory with a pairing function (although I have never actually been able to track down this construction). I've also asked a lot of people whether there's an NIP expansion of $(\omega,+,<)$ by a pairing function, but nobody's had any ideas. $\endgroup$ Feb 18, 2021 at 15:52
  • 1
    $\begingroup$ The above-mentioned construction of Poizat might refer to the theory of locally free (or: acyclic) pairing functions (i.e., bijections $f\colon M^2\to M$ such that $t(x_1,\dots,x_n)\ne x_i$ for all proper $f$-terms $t$), which goes back to Mal’cev (On the elementary theories of locally free universal algebras, Soviet Math. Doklady 2 (1961), 768–771). Its model-theoretic properties were studied by Bouscaren and Poizat (Des belles paires aux beaux uples, JSL 53 (1988), 434–442). $\endgroup$ Mar 10, 2021 at 18:10
11
$\begingroup$

For $\langle\kappa,{\in}\rangle$, James Hanson has already answered the question as stated. However, let me mention a generalization: it’s not just Gödel’s pairing function that’s not definable in $\langle\kappa,{\in}\rangle$—in fact, there is no injective pairing function definable in these structures.

The reason for this is the computational complexity (or rather, easiness) of $\mathrm{Th}(\kappa,{\in})$. The results on quantifier elimination in [1] easily imply that if $\phi$ is an $\exists_n$ sentence, then $$\langle\kappa,{\in}\rangle\models\phi\iff\langle\omega^n,{\in}\rangle\models\phi.$$ Moreover, $\langle\omega^n,{\in}\rangle$ has an obvious $n$-dimensional interpretation in $\langle\omega,{\in}\rangle$. This provides a polynomial-time reduction of the theory of $\langle\kappa,{\in}\rangle$ to the theory of $\langle\omega,{\in}\rangle$, which is known to be decidable in PSPACE; therefore,

Proposition: $\mathrm{Th}(\kappa,{\in})$ is decidable in PSPACE.

On the other hand, [2] proved that no consistent theory with a definable pairing function is in ELEMENTARY (which includes PSPACE, and much, much more).

Corollary: No pairing function is definable in $\langle\kappa,{\in}\rangle$.

References:

[1] John E. Doner, Andrzej Mostowski, Alfred Tarski: The elementary theory of well-ordering—a metamathematical study—, in: Logic Colloquium ’77 (A. Macintyre, L. Pacholski, J. Paris, eds.), Studies in Logic and the Foundations of Mathematics vol. 96, Elsevier, 1978, pp. 1–54, doi 10.1016/S0049-237X(08)71988-8.

[2] Jeanne Ferrante, Charles W. Rackoff: The computational complexity of logical theories, Lecture Notes in Mathematics vol. 718, Springer-Verlag, 1979, Chapter 8, doi 10.1007/BFb0062837.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.