3
$\begingroup$

If $(E,<)$ is a linear order, let $s(E,<)$ denote the least ordinal which doesn't embed in $(E,<)$.

I am trying to prove the following:

  • If $(M,+,.,0,1)$ is a model of open induction, (or equivalently, the set of positive elements of an integer part of a real closed field) then $s(M,<)$ where $x < y$ is defined by $\exists z(z \neq 0 \wedge x + z = y)$ is regular.

I can prove this when no element of $M$ has a cofinal sequence of powers using a real closed field having $M \cup (-M)$ as an integer part. However, I wonder if my proof misses the point.

I am trying to find some literature about $s(E,<)$ where it could have been studied and where its regularity may have been questioned. Does anyone know where to find such study?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Your claim isn't true.

For a counterexample, let's construct a $\kappa$-like model. A model of arithmetic (or indeed any ordered structure) is $\kappa$-like, if it has size $\kappa$, but every proper initial segment of it has size less than $\kappa$.

One can construct a $\kappa$-like model $M\models\text{PA}$ for any uncountable $\kappa$, including singular $\kappa$, by iteratively using the MacDowell-Specker theorem, which asserts that every model of arithmetic has a proper elementary end-extension (and so it has one of the same cardinality). Specifically, let $M_0\models\text{PA}$ be any countable model of arithmetic, and construct a tower of end-extensions $$M_0\prec_e M_1\prec_e\dots\prec_e M_\alpha\prec_e M_{\alpha+1}\prec_e\dots\prec_e M$$ where at successor stages we apply the MacDowell-Specker theorem, choosing $M_{\alpha+1}$ to have the same size as $M_\alpha$, and at limit stages take unions. Let $M=\bigcup_{\alpha<\kappa}M_\alpha$ be the model at stage $\kappa$, which will be $\kappa$-like, since the initial segments are contained in the various $M_\alpha$, which have size $|\alpha\cdot\omega|$, which is less than $\kappa$.

It follows that $\kappa$ order-embeds into $\langle M,<\rangle$, since we added new points on top at each stage, but $\kappa+1$ does not embed, since no bounded segment of $M$ has size $\kappa$. So your characteristic $s(M,<)$ will be $\kappa+1$, which is not a regular cardinal. So this is a counterexample.

You asked for literature, and there seems to be a lot of work on $\kappa$-like models, such as:

Improve this answer
$\endgroup$
6
  • $\begingroup$ This is very helpful. I realise that what I claimed I proved was wrong too because I proved it for $s(E,<)$ being defined as the supremum of the ordinals which embed in $(E,<)$, which is different. $\endgroup$
    – nombre
    Feb 7, 2016 at 13:47
  • $\begingroup$ Yes, those are different, since in the case of my $\kappa$-like model, the supremum will be $\kappa$. But the construction shows that this, too, can be singular. $\endgroup$
    – Joel David Hamkins
    Feb 7, 2016 at 13:48
  • $\begingroup$ Yes, and your counter example made me find the error in my proof. Thanks a lot! $\endgroup$
    – nombre
    Feb 7, 2016 at 14:17
  • $\begingroup$ Just a precision: I understand that at limit $\alpha$, $M_{\alpha}$ is a model of open induction because open induction has $\forall \exists$-axiomatisations, but why would it be a model of full PA? $\endgroup$
    – nombre
    Feb 7, 2016 at 16:08
  • $\begingroup$ The union of a chain of elementary extensions is an elementary extension, and so all the models have the same theory. $\endgroup$
    – Joel David Hamkins
    Feb 7, 2016 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.