# Determining if there are prime hyperintegers

I have $F$ a fixed nonprincipal ultrafilter on $\omega$ and let $N^*$ be the ultrapower with domain $\mathbb{N}/F$ (the extended natural numbers). The language contains $0,1,+,\cdot,<$ and =. A normal model for this language is the standard interpretation of integers $N$. Now I need to determine if there are infinitely large prime number.

In order to determine this I use Los's theorem that states that any sentence $B$ of $K$ is true in $\mathbb{N}/F$ if and only if $A = \{ n\in \mathbb{N} : B$ is true$\}\in F$.

I made the following sentence $B$: $(\forall x)(\forall y)( (xy = n) \Rightarrow ((x=1)\lor (y=1)))$

My conclusion is that we can't determine if $A$ is in $F$. For nonprincipal ultrafilters either $A$ or $\mathbb{N}\setminus A$ is in $F$, and there are no finite sets in $F$. But both $A$ and $\mathbb{N}\setminus A$ are infinite, so we can't determine if $A$ is in $F$, so we can't say if there are infinitely large prime numbers.

I have two questions:

1. Is my sentence $B$ closed. The tutor gave similar sentences in class, but there is no quantifier for my $n$..
2. Is my conclusion correct.
• The variable $n$ in $B$ appears free. So it's not a sentence. Now, $n$ is the thing you want to be a prime: should it come with an existential or a universal quantifier? Your conclusion is not correct. How do you get that both $A$ and its complement are infinite? It might be worth pointing out that Łoś also holds for formulas. So you can work with your $B(n)$, construct some element of the ultrapower and show it is prime and not a standard natural. Commented Mar 28, 2017 at 15:16
• I think it should come with an existential quantifier. Since $A$ is the set with all the standard prime numbers, and $N\A$ the set with all standard integers that are not prime, they both have infinite elements..
– Sven
Commented Mar 28, 2017 at 15:28
• You should write \setminus A instead of \A. Also, it's not easy as that: Łoś says something different: if $\phi(x)$ is a formula, then $N^*\models \phi([f])$ iff $\{n\in\mathbb N: N\models f(n)\}\in F$. So, if you take $B$ to be the sentence starting with $\exists n\dots$, then the set is just all of $\mathbb N\in F$ (no surprise, the ultrapower certainly thinks that there are primes). It would be better if you can come up with an $f$ so that the sentence $B([f])$ (the unquantified version) is true in the ultrapower (for this, use Łoś). Then, show that $[f]$ is not a standard prime. Commented Mar 28, 2017 at 15:37
• And if I use $B$ is $(\forall n)(\exists p) (p>n \land (\forall x)(\forall y)((xy=p)\Rightarrow ((x=1) \lor (y=1))))$, then $\{ n \in \mathbb{N}: \vDash _N B \}$ is the whole set $\mathbb{N}$ which is obviously in $F$, so then there exist hyperinteger prime numbers?
– Sven
Commented Mar 28, 2017 at 16:03
• Right, that's the other option and is a perfectly fine answer too. It still might be good to know how to "build" a nonstandard prime though (but obviously doesn't matter for this question). Commented Mar 28, 2017 at 16:12

One way to see that there are nonstandard primes is by considering the formula $$\phi(x)= x\text{ is prime''}$$ (the formalization of that is easy) and finding a nonstandard element satisfying it. Recall that Łoś's construction works for any formulas, not just sentences.

So if we construct an element $[f]\in N^*$ (where $f:\mathbb N\rightarrow \mathbb N$ and $[f]$ is its equivalence class), we have $$N^*\models\phi([f])\quad\text{iff}\quad \{n\in\mathbb N\mid N\models \phi(f(n))\}\in F\,.$$

But now it's easy to see what we have to do: We just have to choose a function $f$ which takes on prime values often enough. To ensure that $[f]$ is not a standard natural number (and thus not a standard prime), it better not be equal to any particular standard number too often (recall that if $m$ is a standard natural number and $c_m$ is the function with constant value $m$, then $[c_m]$ represents $m$ in the ultrapower; so if $f(n)=m$ for $F$-many $n$, $[f]=[c_m]$).

Good that there are infinitely many primes. Let $(p_n)_{n\in\mathbb N}$ be an enumeration of the primes (it can really be any sequence consisting of primes without any prime appearing infinitely often, so you can construct several nonstandard primes) and consider the function $$f\colon\mathbb N\rightarrow\mathbb N, n\mapsto p_n\,.$$ Then $[f]$ is prime and not a standard natural number, as desired.

• That's a great construction!
– Sven
Commented Mar 28, 2017 at 18:50

Transfer the sentence $\forall n\; \exists p\colon (p \text{ is prime })\wedge (p>n)$ (being a prime is of course an elementary statement as pointed out in the question itself).