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.
 A: 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$.
A: 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.
