Is there any nonstandard model of $PA$ with the following properties?

  1. There exists a nonstandard number $n\in M$ such that $M\upharpoonright n$ is countable,

  2. Let $|x|=\lceil\log_2x\rceil$, then $|\{x\in M: M\models |x|=n\}|=|\mathbb{R}|=\aleph_1$, (with assumtion CH or any other axiom that implies $|\mathbb{R}|=\aleph_1$)

If the above question has a positive answer, what can be said about the measure of the numbers with length of $n$?

More precisely, let $f:\mathbb{N}\to M\upharpoonright n$ be a one to one function.

Q1. Is set $A_f=\{\sum_{i=0}^\infty 2^{-i-1}\cdot (v)_{f(i)}:v\in M,M\models|v|=n\}$ measurable? ($(x)_i$ is the i'th bit of $x$ in the binary representation)

Q2. Is there any one to one function $g:\mathbb{N}\to M\upharpoonright n$ such that $A_g$ becomes measure one?

  • 1
    $\begingroup$ Please define what $|x|$ and $M|_n$ mean. $\endgroup$ – Andrés E. Caicedo Feb 14 at 22:59
  • 2
    $\begingroup$ @AndrésE.Caicedo I understood $M\vert_n=M\upharpoonright n$ to be the initial segment of $M$ up to $n$. As to $\vert x\vert$, I think that's $log(x)$ (= the length of $x$'s representation in base $2$) $\endgroup$ – Noah Schweber Feb 15 at 1:16
  • 4
    $\begingroup$ If my interpretation is right, the first part just boils down to "Is there an $M\models PA$ and an $n\in M$ with $M\upharpoonright n$ countable but $M\upharpoonright 2^n$ uncountable?" If I recall correctly, the answer to that is yes. $\endgroup$ – Noah Schweber Feb 15 at 1:19
  • $\begingroup$ @AndrésE.Caicedo: The definition is added. $\endgroup$ – Erfan Khaniki Feb 15 at 7:27
  • 10
    $\begingroup$ The existence of such a model follows from Vaught's two cardinal theorem. The tricky part is showing that the relevant kind of Vaightian pair exists, i.e. a proper elementary pair $M \prec N$ and a nonstandard $n$ such that $M$ and $N$ agree up to $n$, but disagree before $2^n$. You can show that this happens with exercise 7 in section 12.1 of Hodges' big model theory textbook. In fact there is nothing special about $2^n$, you can do this with any function definable in $PA$ with superpolynomial growth. $\endgroup$ – James Hanson Feb 15 at 10:07

As requested this is a slightly more detailed answer to your first question. I really don't know how to approach your second question.

By a mild variation Vaught's two cardinal to get a model $N$ of $PA$ with a non-standard number $n$ such that $|\{x\in N:x \leq n \}|=\aleph_0$ but $|\{x\in N : x\leq 2^n\}|=\aleph_1$ it's enough to find an elementary pair of models $M \prec N$ and a non-standard number $n\in M$ such that $\{x\in M : x\leq n\}=\{x\in N : x\leq n\}$ but such that $\{x\in M: x \leq 2^n \}$ is a proper subset of $\{x \in N : x\leq 2^n \}$.

Choose a constant $n$ and add it to the language of $PA$. Now assume for the sake of contradiction that in every model $N$ of $PA$ for any $n\in N$ if $\{x\in N:x \leq n \}$ is infinite, then $|\{x\in N:x \leq n \}|=|\{x\in N : x\leq 2^n\}|$. Then by theorem 12.1.5 in Hodges' big model theory textbook there must be a layering of the definable set $\{x\in N : x\leq 2^n\}$ by the definable set $\{x\in N:x \leq n \}$ which by exercise 7 in section 12.1 implies that there is some polynomial $p(x)$ with integer coefficients such that for any model $M$ of $PA$ (with the constant $n$) if $|\{x\in N:x \leq n \}|=m<\omega$, then $|\{x\in N : x\leq 2^n\}| \leq p(m)$, but this is clearly absurd since $2^n$ grows faster than any polynomial.

Therefore no such layering can exist and there must be a model $N$ of $PA$ with the constant $n$ such that $|\{x\in N:x \leq n \}|$ and $|\{x\in N : x\leq 2^n\}|$ are both infinite and $|\{x\in N:x \leq n \}| < |\{x\in N : x\leq 2^n\}|$. So by the Löwenheim–Skolem theorem there is an elementary substructure $M$ of $N$ such that $\{x\in N:x \leq n \} \subseteq M$ and $|\{x\in N:x \leq n \}|=|M|$, so that in particular $\{x\in N : x\leq 2^n\}$ is not a subset of $M$.

  • $\begingroup$ Great answer. Thanks a lot. $\endgroup$ – Erfan Khaniki Feb 16 at 13:25
  • The point of this note is to point out that "Uncountable" can be strenghtened to "continuum-many" in Hanson's answer, but first a notation: Given a model $M$ of arithmetic and $a \in M$, I will use $[a]_M$ to denote the set $\{x\in M: x \leq a\}$.

Theorem (Mills and Paris) There is a model of arithmetic $M$ and some $n\in M$ such that $[n]_M$ is countable but $[2^n]_M$ is of the same cardinality as $\Bbb{R}$.

More detail: Mills and Paris showed---without the use of the continuum hypothesis---that given any countable model $M_0$ of PA, and any any nonstandard $n \in M_0$, there an elementary extension $M$ of $M_0$ such that $[n]_{M_{0}} = [n]_M$ but $[2^n]_M$ has cardinality $2^{\aleph_{0}}$. This result appears in their paper Closure properties of countable nonstandard integers, Fund. Math. 103 (3) (1979) 205–215. An exposition of this result can also be found in Section 3.5 of the book Structure of Models of Peano Arithmetic by Kossak and Schmerl.

  • $\begingroup$ Thank you very much for your answer. $\endgroup$ – Erfan Khaniki Feb 17 at 16:31

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.