Model of PA in which every subset of $N$ extends to a definable set

Question

Let $M$ be a model of Peano Arithmetic.

Show that $M$ has an elementary extension $M^*$ such that for every $X \subset M$, there is a set $X^* \subset M^*$ such that $X^* \cap M = X$ and $X^*$ is definable in $M^*$.

Answer 1

To handle one set $X$, simply add a new constant symbol $c$ and then let $T$ be the theory consisting of the elementary diagram of $M$ together with the sentences stating that $k$ is in the set coded by $c$ (such as via binary digits or whatever coding you like), iff $k\in X$.

This theory is finitely consistent, and so it has a model $M^*$ by compactness. Let $X^*$ be the set coded by $c$ in $M^*$. The theory is precisely designed so that $X=X^*\cap M$, as desired.

Now, one can handle all sets $X\subset M$ simply by having lots of constants $c_X$, one for each set. The theory is still finitely consistent, and the argument works the same way.

A remark: you asked for $X^*$ to be definable, but I took you to mean definable with parameters. In my solution, for example, $X^*$ is definable from parameter $c$. In general, without parameters, it is not true even for the one-set case, since any definable subset of $M^*$ restricts to a definable subset of $M$, when $M^*$ is an elementary extension of $M$.

It would be an interesting question to give up on elementarity of the extension $M\subset M^*$, but ask in the one-set case for $X^*$ to be definable without parameters in the extension.