[Math] Reverse Skolem’s paradox

lo.logicset-theory

By using the Löwenheim–Skolem theorem & Mostowski collapse, in every model $V$ of $ZF+Con(ZF)$ there is a countable transitive set $M$ such that $(M,\in_M) \models ZF$. Is the following "converse" true?

In every model $V$ of $ZF$ and every transitive set $M \in V$ such that $(M,\in_M) \models ZF$, there exists a transitive set $N \in V$ such that:

$M \in N$

$(N,\in_N) \models ZF$

$M$ is countable inside $N$

Best Answer

The answer to your question is no. For example, suppose $\kappa$ is inaccessible and $M = V_{\kappa}$. Then $M$ is a model of $\sf ZF$ but $M$ cannot be countable in $N$ as it is not countable in $V$.

Of course there will always be a set generic extension of $V$ containing such an $N$ (just generically add a bijection from $M$ to omega)

Related Solutions

ZFC – Is There a Computable Model?

The Tennenbaum phenomenon is amazing, and that is totally correct, but let me give a direct proof using the idea of computable inseparability.

Theorem. There is no computable model of ZFC.

Proof: Suppose to the contrary that M is a computable model of ZFC. That is, we assume that the underlying set of M is ω and the membership relation E of M is computable.

First, we may overcome the issue you mention at the end of your question, and we can computably get access to what M thinks of as the n^th natural number, for any natural number n. To see this, observe first that there is a particular natural number z, which M believes is the natural number 0, another natural number N, which M believes to the set of all natural numbers, and another natural number s, which M believes is the successor function on the natural numbers. By decoding what it means to evaluate a function in set theory using ordered pairs, We may now successively compute the function i(0)=z and i(n+1) = the unique number that M believes is the successor function s of i(n). Thus, externally, we now have computable access to what M believes is the n^th natural number. Let me denote i(n) simply by n. (We could computably rearrange things, if desired, so that these were, say, the odd numbers).

Let A, B be any computably inseparable sets. That is, A and B are disjoint computably enumerable sets having no computable separation. (For example, A is the set of TM programs halting with output 0 on input 0, and B is the set of programs halting with output 1 on input 0.) Since A and B are each computably enumerable, there are programs p₀ and p₁ that enumerate them (in our universe). These programs are finite, and M agrees that p₀ and p₁ are TM programs that enumerate a set of what it thinks are natural numbers. There is some particular natural number c that M thinks is the set of natural numbers enumerated by p₀ before they are enumerated by p₁. Let A⁺ = { n | n E c }, which is the set of natural numbers n that M thinks are enumerated into M's version of A before they are enumerated into M's version of B. This is a computable set, since E is computable. Also, every member of A is in A⁺, since any number actually enumerated into A will be seen by M to have been so. Finally, for the same reason, no member of B is in A⁺, because M can see that they are enumerated into B by a (standard) stage, when they have not been enumerated into A. Thus, A⁺ is a computable separation of A and B, a contradiction. QED

Essentially this argument also establishes the version of Tennenbaum's theorem mentioned by Anonymous, that there is no computable nonstandard model of PA. But actually, Tennenbaum proved a stronger result, showing that neither plus nor times individually is computable in a nonstandard model of PA. And this takes a somewhat more subtle argument.

Edit (4/11/2017). The question was just bumped by another edit, and so I thought it made sense to update my answer here by mentioning a generalization of the result. Namely, in recent joint work,

M. T. Godziszewski and J. D. Hamkins, Computable quotient presentations of models of arithmetic and set theory, click through for pdf at the arxiv.

we prove that not only is there no computable model of ZFC, but also there is no computable quotient presentation of a model of ZFC, and indeed there is no c.e. quotient presentation of such a model, by an equivalence relation of any complexity. That is, there is no c.e. relation $\hat\in$ and equivalence relation $E$, of any complexity, which is a congruence with respect to $\hat\in$, such that the quotient $\langle\mathbb{N},\hat\in\rangle/E$ is a model of ZFC.

[Math] Uncountable nonstandard models of PA

Question 2 is an immediate consequence of the compactness theorem. Let $\kappa$ be fixed, and for each $\alpha < \kappa$ add a constant symbol $c_\alpha$ to the language. Add axioms of the form $c_\alpha < c_\beta$ for every $\alpha < \beta < \kappa$. The new theory $T$ is finitely satisfiable (every finite fragment is interpretable in the standard model of PA). So $T$ it is satisfiable, and the map $\alpha \mapsto c_\alpha$ is the desired embedding.

For question 1, it is known that $D$ cannot have the order type of the reals. There is a nice survey by Bovykin and Kaye [1] that includes this fact and has a lot more information about order types of models of PA. In the comments below, Andrey Bovykin suggests downloading his thesis from his homepage [2]; the paper is a summary of parts of the thesis.

1: Bovykin, Andrey; Kaye, Richard. Order-types of models of Peano arithmetic. (2002) Logic and algebra, 275--285, Contemp. Math., 302; MR1928396, DOI: 10.1090/conm/302/05055, http://www.maths.bris.ac.uk/~maaib/orders.ps

2: https://logic.pdmi.ras.ru/~andrey/research.html

Best Answer

Related Solutions

ZFC – Is There a Computable Model?

[Math] Uncountable nonstandard models of PA

Related Question