3
$\begingroup$

The set of natural numbers $\mathbb{N}$ in set theory is defined with the axiom of infinity as the smallest inductive set and then it is usually proven that $\mathbb{N}$ satisfies the Peano axioms and well-ordering. However, I have yet to see a treatment where it is proven that $\mathbb{N}$ is equal to $\{0,1,2,...\}$, i.e. $\mathbb{N}$ contains the successors of 0 and nothing else.

I guess to answer my question, I would need to construct a model of set theory in which $\mathbb{N}$ contains 0, 1, 2, etc. plus some extra junk and show that this model indeed works. Maybe someone has done this already? Or maybe it can be proven directly?

Edit: There seems to be some confusion in the comments and answers below. After some thought, I believe that what I want to show is that $\mathbb{N}$ does not contain an element apart from 0 that is not the successor of anything else in $\mathbb{N}$. I think I can prove this by contradiction with the axiom of specification to get an inductive set smaller than $\mathbb{N}$.

$\endgroup$
  • 3
    $\begingroup$ I remember this being asked before. $\endgroup$ – Git Gud Dec 23 '14 at 21:56
  • $\begingroup$ Well, we would want to prove that it is countably infinite. $\endgroup$ – Julian Rachman Dec 23 '14 at 21:56
  • $\begingroup$ Is your question about defining $N$ in a model of $ZFC$ without the axiom of infinity? I would add the tag of model theory for this question too. $\endgroup$ – cmn1 Dec 23 '14 at 21:59
  • 1
    $\begingroup$ To prove that $\mathbb{N}$ is equal to $\{0,1,2,\ldots\}$, one would have to make the "$\ldots$" precise (which is in fact the intent of the usual definition of $\mathbb{N}$ as the smallest inductive set.) And when you talk about proving that "$\mathbb{N}$ contains the successors of 0 and nothing else," I don't think this is what you mean; there is only one successor of 0, namely 1, whereas $\mathbb{N}$ also contains 2. So I don't know precisely what you are asking. $\endgroup$ – Trevor Wilson Dec 23 '14 at 22:04
  • 1
    $\begingroup$ Before starting to edit my answer to address your edit, first I'd need you to clarify. How exactly do you define $\Bbb N$? And writing $\{0,1,2\ldots\}$ is not an answer. $\endgroup$ – Asaf Karagila Dec 27 '14 at 20:06
2
$\begingroup$

Question (quote) "I want to show that $\mathbb{N}$ does not contain an element apart from 0 that is not the successor of anything else in $\mathbb{N}$."

Short Answer This would contradict the minimality of $\mathbb{N}$. You mentioned a correct proof sketch by contradiction.

Long Answer You asked if it can be proved directly; we will show that every element of $\mathbb{N}$ is either $0$ or an iterated-successor of $0$ (i.e. $0$ is an element). This answers your overall question of why the alternative notation $\{0,1,2,\ldots\}$ is justified.

Remark "$\ldots$" is nothing but a symbol---it is meaningless and only used in notations. It's much like "$\infty$" in that regard. Another note is that the ZFC axioms do not restrict us on how to denote our sets. As long as we're clear about which unique set we refer to, we can use any notation for any set; i.e. $\omega$ and $\aleph_0$ are notations for the exact same set even though they're used in different contexts.

Recall

$\mathbb{N}$ is the minimal inductive set; i.e. it's an inductive set such that for each inductive set $B$, if $B\subseteq \mathbb{N}$, then $B=\mathbb{N}$.

Brief review

$A$ is an inductive set if $\varnothing\in A$ and for each $X\in A$, $X\cup\{X\}\in A$.

A natural number is an element of $\mathbb{N}$.

We will use "$+1$" to denote successor; i.e. $X+1=X\cup\{X\}$. From this we can derive the following (induction)

For each formula $\phi(x)$, if $\phi(0)$ holds and for each natural number $k$, if $\phi(k)$ holds, then $\phi(k+1)$, then for each natural number $n$, $\phi(n)$ holds.

At this point most would be satisfied that the notation $\{0,1,2,\ldots\}$ is justified, but we want to be pedantic and use the above theorem

Define the formula $\phi(x)$ by$$\phi(x)\overset{\mathrm{def}}{=} (x\ne 0)\Rightarrow (0\in x)$$

This is something that can be proved by induction for each natural number.

(sorry for not posting proofs, but you already have one)

$\endgroup$
5
$\begingroup$

Instead of working "backwards", work "forward". In that case, the need for the axiom of infinity is also mitigated.

Begin by defining ordinals, or cardinals whichever you like. Ordinals work better since they have an inherent successor operation. Now define the notion of "finiteness", it is true that many times this notion makes an appeal to the natural numbers but there are purely set theoretical definitions of finiteness. For example Dedekind-finiteness, Tarski-finiteness, and others.

Now define $\omega$ as the collection of all finite ordinals. This is exactly what you get when you begin with $\{0\}$ and close it under the successor operation. Next show, if you like, that this set is inductive and that it is in fact minimal.

In the course I'm TA'ing right now, the professor (who is a distinguished set theorist) is taking this sort of approach. The natural numbers are some atomic object at first, and after defining the ordinals we take the finite ordinals, $\omega$ as the set theoretic natural numbers. This circumvents the need to talk about inductive sets at all.

$\endgroup$
0
$\begingroup$

The Peano Axioms contain the Axiom of Induction, which says, basically, that the natural numbers contain only $0$ and its successors. At least, what I understand you to mean when you say "the successors of $0$", because, and Trevor pointed out, $0$ has only one successor. One formal way of stating this axiom is that if there is a set $S$ where $0\in S$, and for any natural number $n$, if $n$ is in $S$, then the successor of $n$ is in S, then the set $S$ contains every natural number. In other words, the statements "$0$ is a natural number" and "if $n$ is a natural number, then the successor of $n$ is a natural number," when combined with the other axioms about what the successor is and why $0$ is special, define all of the natural numbers.

So, if you show that $\Bbb{N}$ satisfies the Peano Axioms, then "$\Bbb{N}$ contains the successors of $0$ and nothing else." The Axiom of Induction is in the Peano Axioms to exlude that "extra junk".

See this question.

$\endgroup$
  • $\begingroup$ What do you mean by "successors of 0"? There is only one successor of zero, namely 1. $\endgroup$ – Trevor Wilson Dec 23 '14 at 22:06
  • $\begingroup$ @TrevorWilson would it be clearer if I said "iterated successors of zero"? What I mean is zero, and its successor, and its successor's successor, and so on. I assume that is what the OP means, as well. $\endgroup$ – KSmarts Dec 23 '14 at 22:08
  • $\begingroup$ That would be better, because it makes it clear that it is not a precise statement. What does the "and so on" mean? How many steps in the iteration? If we say there is one step for each natural number, then we are back where we started. So I'm not sure this answers the OP's question (although the question was imprecise, so I'm not sure it can be answered in its current form.) $\endgroup$ – Trevor Wilson Dec 23 '14 at 22:10
  • $\begingroup$ Of course, that isn't what the axiom of induction actually says, although that is the intuition for the axiom. The axiom of induction is about what can be proven, not about the elements of any set. $\endgroup$ – Thomas Andrews Dec 27 '14 at 20:08
  • $\begingroup$ @ThomasAndrews The set definition that I used is, as I said, one way of stating the axiom. The statement of proof, where if $P(0)$ and $P(n)\Rightarrow P(n++)$ then $P(x)$ for any natural number $x$, is more commonly used, but is equivalent. $\endgroup$ – KSmarts Dec 29 '14 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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