8
$\begingroup$

Theorem 1.53 (3) in page 227 of Hajek and Pudlak's book, Metamathematics of First-Order Arithmetic, says:

Theorem. If $M$ is a countable model of $I\Delta_{0}$ such that $M$ has a proper elementary end extension, then $M\models PA$.

Is the above theorem still true if we drop the countability assumption of $M$?

$\endgroup$

3 Answers 3

6
$\begingroup$

The countability assumption cannot matter. The reason is that any uncountable model $M$ is countable in a forcing extension of the set-theoretic universe. If $M$ has a proper elementary end-extension in the original universe, then this end-extension still exists in the forcing extension. So we may apply the theorem as you have stated it in the forcing extension in order to deduce that $M\models\text{PA}$. But the question whether $M$ is a model of PA or not is absolute between the set-theoretic universe $V$ and its forcing extensions $V[G]$, and so $M\models\text{PA}$ in $V$, as desired.

Although I like this kind of use of forcing, where one constructs the forcing extension in order solely to make a conclusion about what is true in the original universe, nevertheless one may omit it by taking a countable elementary substructure of a suitable $H_\theta$, in effect replacing $M$ with a countable proxy. Applying the theorem to the proxy, you get that the proxy satisfies $\text{PA}$, and so $M\models\text{PA}$ as well.

$\endgroup$
11
$\begingroup$

The theorem remains true without the countability assumption. The quickest way to see this is to deduce it from the following well-known facts about the regularity scheme (see here for a definition of the regularity scheme).

1. Suppose $\cal{M }$ is an ordered structure (of any cardinality) that has a proper elementary end extension, then $\cal{M}$ satisfies the regularity scheme. This is a routine exercise.

2. A model $\cal{M}$ of $I\Delta_{0}$ (of any cardinality) satisfies $PA$ iff $M$ satisfies the regularity scheme. See, e.g., Theorem 7.3 of Kaye's text on models of $PA$ for a proof.

Remark. The converse of Lemma 1 is true for countable $\cal{M}$, and is due to Keisler. The proof uses the omitting types theorem. It is known that the converse fails without the countability assumption.

$\endgroup$
1
  • $\begingroup$ Actually, the converse holds for models of PA of arbitrary cardinality. This is the MacDowell-Specker theorem. $\endgroup$ Commented Jan 18, 2014 at 12:13
11
$\begingroup$

Having seen the other answers, let me point out yet another quick argument using just Lowenheim-Skolem.

Let $M$ be an uncountable model and $N$ a proper elementary end extension of it. Expand $N$ by adding an extra unary predicate naming the subset $M$. Call the resulting structure $(N,M)$. Take a countable elementary substructure of it, say $(N',M')$. Then $N'$ is a proper elementary end extension of $M'$ and $M'$ is countable, so the theorem applies. Hence $M'$ is a model of PA and so is $M$ since they are elementarily equivalent.

$\endgroup$
0

You must log in to answer this question.

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