The link Not Skolem's Paradox - Part 3 includes the following words in a comment :
"By carefully tracing the details of the usual compactness argument and the proof of the completeness theorem, we can see that there must exist a nonstandard model of PA where the carrier set is $\mathbb{N}$ and the addition and multiplication are represented by particular $Σ^0_2$ arithmetical formulas."
My question is - is it possible to provide an outline of how this "careful tracing" is undertaken to show there must be non standard models with $Σ^0_2$ definitions of addition and multiplication ?
There looks to be a general method going on in the "careful tracing" that is neat since it doesn't look immediately obvious how such a method would work. A formula that maps N to a structure with (N ; Z chain) looks to be recursive in the usual +, * , e.g. by taking the even numbers map to N and map odd numbers to the Z chain. If it is the inverse relation that is not recursive but can be $Σ^0_2$ I couldn't show it nor the connection to compactness / completeness, so any hints greatly appreciated.
Build the tree of attempts to construct a complete consistent Henkin theory extending PA. That is, we start with PA, plus the assertions that $c$ is a constant for a nonstandard element, and then add the Henkin assertions, and then we proceed to complete the theory: at each level $n$, we include the next sentence $\sigma$ or its negation $\neg\sigma$, if no contradiction is revealed using proofs of length $n$. (If we make a mistake and add an inconsistent assertion, that whole part of the tree will eventually die out.)
This makes a computable infinite finitely branching tree. So it has a low branch. This branch provides exactly a complete consistent Henkin theory extending PA plus the assertions ensuring that $c$ is nonstandard. This theory can be used to construct the desired model. One needs to quotient by the equivalence relation, where two constants are equivalent if the branch contains the assertion that they are equal. Since the branch is low, we can decide this equivalence relation and the entire elementary diagram of the resulting model from an oracle for $0'$.
So the resulting model and its diagram have complexity $\Delta^0_2$.