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

Assume we have a countable, non-standard model of Peano Arithmetic (PA) in ZFC.

Let $N^*$ be the universe of this model and let $m \in N^*$ be a non-standard natural number larger than any standard natural number. $2^m \in N^*$ is the size of the $P(m)$, the powerset of numbers less than m, inside the model. We can even encode a bijection between $P(m)$ and $2^m$ inside the model. For example, we can encode a set as an m-bit string. x is a member of the set if the x'th bit of the string is true. Each such string is the binary representation of a natural number less than $2^m$.

Skolem's paradox considers a set that is uncountable inside the model yet countable outside the model. Here, we have a finite bijection inside the model which seems to be uncountable outside the model.

My question is how can the countably infinite set $X = \{x : x \in N^* \land x < m\}$ have a countable powerset? How can $Y = \{y : y \in N^* \land y < 2^m\}$ be a countable set inside ZFC? We can show there is a bijection between $P(X)$ and $Y$.

I know the answer must be something like the model doesn't "see" all of $P(m)$. If this is the answer, would someone give an example of a set of standard natural numbers the model can't "see"? For example, does there exist a binary representation of a standard real number such that this binary string is not a proper subset of the binary representation of some non-standard natural number inside the model.

share|cite|improve this question

First of all, models of $\sf PA$ don't see sets, they see integers. Perhaps what you wanted to say that you have $N$ which is a non-standard model of $\sf ZFC$ whose integers are a non-standard model of $\sf PA$.

Other than that, the reason that you give is correct. Yes, there are uncountably many subsets to that [proper] initial segment of $\omega^N$, but $N$ is countable and don't know them all, and moreover it thinks that collection is finite. An example of a standard set of integers not in the model is easy: $\omega$ itself. If it were there, it would have to be equal to $\omega^N$ in which case the integers were standard.

share|cite|improve this answer
If we represent sets of standard natural numbers as $\omega$ length binary strings then the set of all standard natural number would be a string of all 1's. ($2^m$ - 1) has a binary representation that has $m$ 1's. Since $m > \omega$, the first string is a proper subset of the second. – Russell Easterly Jul 2 '13 at 5:09
@Russell: You seem to confuse the objects of the model with the definable relations on the model, and with other possible things. The model only has integers in it. Not strings, not sets, not anything else. True, these objects are realized as sets in a universe of $\sf ZFC$, but that is hardly the point here. The point is what are the objects which reside inside the model, and what is definable over the model. – Asaf Karagila Jul 2 '13 at 6:38

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.