Measure of the numbers with length of $n$ for a nonstandard number $n$

Question

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?

Answer 1

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$.

Answer 2

• 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.