Showing that the hyperintegers are uncountable

Question

In class, we constructed the hyperintegers as follows:

Let $N$ be a normal model of the natural number with domain $\mathbb{N}$ in the language $\{0, 1, +, \cdot, <, =\} $. Also let $F$ be a fixed nonprincipal ultrafilter on $\omega$. Then we have $N^*$ as the ultrapower $N^\omega /F$ with domain $\mathbb{N}^{\omega} / F$ .

Now I need to show that $N^*$ is uncountable (this means that it's cardinality is $2^{\aleph_0}$ I guess).

The domain of $N^*$ are the equivalence classes of functions $\{f_F : f \mbox{ a function from }\mathbb{N} \to \mathbb{N}\}$ Further on, we have $N^{\sharp}$ which is the equivalence classes of all the constant functions.

This is my intuition: I know that $N$ and $N^{\sharp}$ are isomporphic (hence have the same cardinality, which is $\aleph_0$ since $N$ is a model for the natural numbers). Furthermore I know that $N^{\sharp}$ is elementary equivalent to $N^*$. But $N^*$ has an extra 'copy' of $N^\sharp$ on top of it, the hyperintegers. So then the cardinalty of $N^*$ should be $2^{\aleph_0}$ (does that even exist? And is that uncountable?). I hope someone can help me with a formal proof.

Answer 1

The structure of $N^*$ may vary depending on $F$, but its cardinal is indeed fixed, equal to $2^{\aleph_0}$.

To see this, you could define a family $\mathcal{C}$ of $2^{\aleph_0}$ maps $\omega \rightarrow N$ pairwise almost disjoint, that is such that $\forall f \neq g \in \mathcal{C}, (f-g)^{-1}(\{0\})$ is finite. (thus $f_F \neq g_F$) Then this family gives rise to $2^{\aleph_0}$ elements of $N^*$. I assume you know that $|N^*| \leq |\omega^{N}| = 2^{\aleph_0}$. edit: this is because the map $\omega^N \ni f \mapsto f_F \in N^*$ is surjective, and $2^{\aleph_0} \leq |\omega^N| \leq |(2^{\omega})^N| = |2^{\omega \times N}| = 2^{\aleph_0}$.

Now, for every subset $A$ of the set $\mathbb{N}_N$ of positive integers of $N$, let $f_A$ be the map that sends $m$ to the interpretation of $\underline{2^{a_0} + ... + 2^{a_{m-1}}}$ in $N$ where $a_0 < ... <a_{m-1}$ are the $m$ first elements of $A$, and let $\mathcal{F}$ denote $\{f_A \ | \ A \subset \mathbb{N}_N\}$. Can you prove that this works?

The result needed here is the following (actually, only the unicity): $\forall n \in \mathbb{N}, \exists ! a_0,...,a_n \in \{0;1\}, n = a_0 + a_12^1 + ... + a_n2^n$.

Answer 2

Here's a diagonalization argument. Let $\left(\mathbf{x}^{(m)} \right)_{m \in \mathbb{N}}$ denote a sequence of natural sequences $\left(x_{n}^{(m)} \right)_{n \in \mathbb{N}} \in \mathbb{N}^{\mathbb{N}}$. Define a sequence $\left(y_n \right)_{n \in \mathbb{N}}$ by $$y_{n} = 1 + \max_{1 \leq m \leq n} \left(x_{n}^{(m)} \right) .$$ Let $\sim$ denote the ultrafilter equality, i.e. $(a_{k}) \sim (b_{k}) \iff \{ k \in \mathbb{N} : a_k = b_k \} \in F$.

I claim that $(y_n) \not \sim \left( x_{n}^{(m)} \right)$ for all $m$. To see this, note that $y_n > x_{n}^{(m)}$ for all $n \geq m$, so $\left\{ n : y_n = x_{n}^{(m)} \right\} \subseteq \{ 1, \ldots , m - 1 \}$, which means the set is finite. But a nonprincipal ultrafilter contains no finite sets, so $\left\{ n : y_n = x_{n}^{(m)} \right\} \not \in F$. Thus $(y_n) \not \sim \left(x_{n}^{(m)} \right)$ for all $m$. Thus $^{*} \mathbb{N} \setminus S$ is non-empty for all countable $S$.

Note that in fact we can say that $(y_n) > \left(x_{n}^{(m)} \right)$ as a nonstandard natural, so we can elaborate that every countable subset of $^{*} \mathbb{N}$ is bounded.

Answer 3

In fact, there is an injection from the set of reals to the hypernaturals: for given real $r$ consider $$f(r) = \langle \lfloor rn\rfloor : n=1, 2,\cdots\rangle.$$ You can see that if $r\neq s$ then the sequence $f(r)$ and $f(s)$ are eventually componentwise different. Therefore the map $r \mapsto [f(r)]$ is injective.

Answer 4

A further variation on this theme is to choose a fixed infinite hyperinteger $H$ and note that the partial map $f\colon{}^\ast\mathbb{N}\to\mathbb{R}$ given by $f(n)=\text{st}(\frac{n}{H})$ whenever this is defined, is surjective.