Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $(N, +, \cdot, 0, 1, <, =)$ is a proper elementary substructure of $(N^*, +^*, \cdot^*, 0^*, 1^*, =^*, <^*)$. Show that there exists some (infinite) $b$, where $b ∈ N^*$, such that for each prime number $p ∈ N$, $N^* \models p | b$ iff $p ∈ S$, where $S$ is some set containing infinitely many primes.

share|cite|improve this question
Do you mean "for every $S$ and every prime $p\in\mathbb N$, the equivalence holds" or do you mean "there exists some $S$ such that for every prime $p\in\mathbb N$, the equivalence holds"? The former statement is not (always) true, but the latter is. – Lawrence Wong Oct 28 '13 at 12:43
I think it is for some S. – max_b Oct 28 '13 at 15:38
The quantifier on $S$ is still not very clear. Is $S$ is given in advance, or are you free to choose it so long as it is infinite? – Mikhail Katz Oct 28 '13 at 15:39
You're free to choose S so long as its infinite. – max_b Oct 28 '13 at 16:06
@Arthur: Do we need a new tags for non-standard models? – Asaf Karagila Oct 28 '13 at 17:09

If we choose $S$ to be the collection of all the standard primes, then it suffices to set $b=H!$ for some infinite integer $H$. Since the standard model satisfies the elementary formula expressing the factorial, the same formula evaluated at $H$ will give a non-standard integer divisible by all the primes up to $H$ by elementary equivalence, and in particular by all the finite primes in $S$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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