7
$\begingroup$

Can an uncountable model of Peano Arithmetic be recursive?

What does it mean for an uncountable model to be recursive? Well, we represent the elements of the model using real numbers instead of natural numbers, and assume $+, \times, ^{-1}$ are computable functions and $\ge$ is a computable relation on the real numbers. (In particular, we could assume we are using lambda calculus, and add symbols for $+, \times, \ge, ^{-1}$, as well as a symbol for each computable real number. Or you could use some other model of Real computation.)

So an uncountable model $M$ of Peano Arithmetic is recursive if $\mathbb N_M \subseteq \mathbb R$ is a computable set, and $+_M, \times_M$ are computable.

Improve this question
$\endgroup$
15
  • 7
    $\begingroup$ There are various competing inequivalent notions of computability on the real numbers, such as the concepts of computable analysis (which find their origins in Turing's concept of a computable real number), to Blum-Shub-Smale computability via flowchart machines, and you mention the lambda-calculus in your language. $\endgroup$
    – Joel David Hamkins
    Commented Jun 1, 2018 at 14:00
  • 3
    $\begingroup$ In $\alpha$-recursion theory, the answer is yes. Just take a completion of PA as a parameter, and then run the Henkin construction. $\endgroup$
    – Dan Turetsky
    Commented Jun 1, 2018 at 14:44
  • 1
    $\begingroup$ @JoelDavidHamkins As long as $\alpha$ is uncountable, that can be fixed by adding enough constants. In $\omega_1$-recursion we can construct a size-$\aleph_1$ model of an arbitrary countable first-order theory in $L_{\omega_1}$ by iteratively building proper elementary extensions via the Henkin argument + adding new constants. I think that's what Dan meant? $\endgroup$
    – Noah Schweber
    Commented Jun 1, 2018 at 17:26
  • 1
    $\begingroup$ @NoahSchweber that's a reciprocal operation for the real numbers, not natural numbers. $\endgroup$
    – Christopher King
    Commented Jun 1, 2018 at 17:27
  • 2
    $\begingroup$ @PyRulez Oh, I see - you're saying that those are requirements you expect any reasonable notion of computability on the reals to satisfy. Sorry, that wasn't clear to me. $\endgroup$
    – Noah Schweber
    Commented Jun 1, 2018 at 17:27

1 Answer 1

Reset to default
2
$\begingroup$

I will not be able to give a full answer, but rather attempt to make the question precise and give some partial answers.

First, I shall side with Andrej Bauer's point in the comments that there ought to be a consensus what computability ought to mean here. Bringing in e.g. the BSS-model would essentially amount to a model-theoretic investigation (is there an interpretation of this theory in that theory) rather than a question of computability.

We are thus asking about represented spaces (in the sense of computable analysis) and computable functions. More precisely, we ask:

Question: What represented spaces $\mathbf{N}$ with computable operations $\times, + : \mathbf{N} \times \mathbf{N} \to \mathbf{N}$ and computable constants $0, 1 \in \mathbf{N}$ are there such that $(\mathbf{N},0,1,+,\times)$ is a model of Peano arithmetic? We shall call these "Type-2 computable models".

First Observation: Each countable ultrapower of $\mathbb{N}$ yields a Type-2 computable model (which is uncountable).

This is just because ultrapowers trivially preserve computability of functions, they only mess with relation symbols. Of course the equality of an ultrapower is about as complicated as the ultrafilter we are using. So this does not even give us Borel equality.

Second Observation: There are Type-2 computable non-standard models with decidable equality (which are countable).

Pick your favourite countable PA-model $M$, and let $p \in 2^\omega$ denote its atomatic diagram. Now define a representation $\rho_M$ of $M$ as follows:

$01^n0^\omega$ is a name for the standard $n \in M$. $11^n0p$ is a name for the $n$-th non-standard number in $M$ according to the injective enumeration we picked for defining $p$.

Equality is trivially decidable. For $+$ and $\times$, either both inputs are standard numbers, and thus the output is standard again; or we can figure out what the output is with the help of $p$ which a non-standard input provides. QED

As a side remark: This shows that Tennenbaum's theorem is relying on the tacit assumption that all numbers are computable.

Now having decidable equality implies being countable, so if we want uncountable models, we do have to relax our demands a bit. The natural requirement would seem to be being Hausdorff, i.e. having equality being co-ce. So the actual (and still open) question would seem to be:

Question: Are there uncountable Hausdorff Type-2 computable models of PA?

Improve this answer
$\endgroup$
4
  • $\begingroup$ How do you compute $\ge$ for an ultrapower? $\endgroup$
    – Christopher King
    Commented Jun 11, 2018 at 22:50
  • $\begingroup$ @PyRulez Essentially, everything that I wrote about equality applies to $\geq$ just as well. Its complexity is horrible for the ultrapowers, it cannot be decidable at all for uncountable models, and the best to hope for is co-c.e., but I don't know whether we can get it (which is why I don't claim to fully answer your question). $\endgroup$
    – Arno
    Commented Jun 11, 2018 at 23:08
  • 1
    $\begingroup$ Am I understanding correctly that a represented space is allowed to use an arbitrary set of names and still be 'computable'? Because if so I believe every countable first-order theory with infinite models has an uncountable Hausdorff Type-2 computable model. $\endgroup$
    – James E Hanson
    Commented Jun 20, 2018 at 19:24
  • 1
    $\begingroup$ Basically the idea is that an Ehrenfeucht-Mostowski functor for the theory is only a countable amount of information, so you can encode it in every name of an element of your model, then you take the EM model whose spine is $\mathbb{R}$ and this will have a computable representation. There's some fiddly details but I think it works. $\endgroup$
    – James E Hanson
    Commented Jun 20, 2018 at 20:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .