5
$\begingroup$

I've seen a construction of a sentence of first order logic that is consistent, but has no models with underlying set $\mathbb{N}$ and recursive functions and relations. Do there also exist consistent sentences with no model on $\mathbb{N}$ with arithmetically definable functions and relations? If no, at which levels of the arithmetical hierarchy are there consistent sentences with no model at that level? If yes, what about the same question for analytically definable models?

$\endgroup$
6
$\begingroup$

Tarski proved that there is no arithmetically definable truth predicate. But one can express what it means to be a truth predicate in a single assertion expressing the Tarskian recursion, in the language with a symbol for that predicate. So there is no arithmetic model of the sentence asserting that $T$ is a truth predicate, if the rest of the model is the standard arithmetic, even though this theory is consistent.

But the requirement that the rest of the model is standard is required for this argument. Ultimately, the answer to your question is negative, because if $\sigma$ is a consistent sentence, then one can build the Henkin model of $\sigma$, and this model will be arithmetically definable, and indeed computable from $0'$. Every consistent sentence has an arithmetically definable model on $\mathbb{N}$ of low complexity. Indeed, the Henkin construction shows that every arithmetically definable consistent theory has a model whose elementary diagram has complexity at most one level higher in the arithmetic hierarchy. For some introductory background, see Reed Solomon's Effective Classical Completeness Theorem.

$\endgroup$
6
$\begingroup$

In this edit Propositions A and B are fine-tuned (thanks to input from Alex Mennen and David Marker).

This note complements the answer by Joel Hamkins. The question was posed for consistent sentences and asked for the arithmetical definability of the open diagram of some model of the given sentence, but as pointed out by Joel, a much stronger result is true, namely: every consistent arithmetically definable theory has a model whose elementary diagram is arithmetically definable.

In contrast, there are extensions $T$ of PA (Peano arithmetic) with the property that the open diagram of no model of $T$ is arithmetically definable; indeed something much stronger is true:

Proposition A. For every $X \subseteq \omega$ there is a consistent theory $T$ in the language of arithmetic extending PA such that $X$ is Turing reducible to the open diagram of every model of $T$ whose universe is $\omega$.

Proposition A can be readily established as an immediate corollary of the following classical result:

Theorem B (Scott). Every countable Scott set can be realized as the standard system of some pointwise definable model of PA.

Proof sketch of the proposition. It is easy to see that any $X\subseteq\omega$ is included in a countable Scott set (for example the Scott set can be chosen as all subsets of $\omega$ that are arithmetical in $X$), so by Theorem B there is a pointwise definable model $\mathcal{M}_0$ of PA whose standard system $\mathrm{SSy}(\mathcal{M}_0)$ includes $X$. Let $T$ be the first order theory of $\mathcal{M}_0$, and note that $X$ is in the standard system of every model of $T$.

On the other hand, it is well-known that if $\mathcal{M}$ is a model of PA whose universe is $\omega$, then every member of $\mathrm{SSy} (\mathcal{M}$) is Turing reducible to the graph of both the addition and the multiplication operation of $\mathcal{M}$ [this fact plays a key role in the proof of Tennenbaum's theorem that states that there is no nonstandard model of Peano arithmetic whose open diagram is computable]. This implies that if $\mathcal{M}$ is additionally a model of $T$, then every member of $\mathrm{SSy}(\mathcal{M}$), and in particular $X$, is Turing reducible to the graph of the addition operation of $\mathcal{M}$.

$\endgroup$
  • 1
    $\begingroup$ Easier proof of that proposition: consider the language with a constant $0$, a unary successor function, and a unary predicate $P$. Let $X$ be a set that is not arithmetically definable. Let $T:=\{P(n)|n\in X\}\cup\{\neg P(n)|n\notin X\}$, where $n$ is shorthand for the $n$th iterate of the successor function starting from $0$. $T$ is consistent, but the open diagram of any model of $T$ can compute $X$. $\endgroup$ – Alex Mennen Jul 8 '16 at 20:23
  • $\begingroup$ @AlexMennen: Thanks for your nice observation, in light of which I have modified the proposition so as to make it nontrivial. $\endgroup$ – Ali Enayat Jul 9 '16 at 0:09
  • $\begingroup$ My construction can also be modified to extend PA, just by expanding the language to include $+$ and $\times$, and then adjoining PA to the theory. $\endgroup$ – Alex Mennen Jul 9 '16 at 1:35
  • $\begingroup$ Using a sufficiently independent sequence of sentences one could get $T\supset $PA in the language of arithmetic such that $T$ has no model but the $\Sigma_n$-theory is arithmetic for all $n$. Indeed for any $X$ we could choose $T$ such that $X$ is computable in $T$. $\endgroup$ – Dave Marker Jul 9 '16 at 17:25
  • $\begingroup$ @Alex Mennen: agreed, but in Proposition A, $T$ was implicitly meant (as indicated by the proof) to be in the language of PA, I have now made that explicit. $\endgroup$ – Ali Enayat Jul 9 '16 at 23:07

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.