Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I give you the following definition of the set $A$, how could you prove it is equal the set of the natural numbers without an explicit definiton for the latter?

The set $A$ is inductively defined as follows:

i) $0 \in A$; and
ii) $\forall n$, a natural number, if $n \in A$, then $n+1 \in A$.

I can easily prove that $A$ is contained in the natural numbers, but I'm failing to see how to prove the converse without a similar definition for the natural numbers.

Thanks for taking the time to read me.

share|improve this question
What definition of $\mathbb N$? –  anon Oct 6 '10 at 16:05
You cannot prove something is equal to $\mathbb{N}$ unless you know what $\mathbb{N}$ is. So I do not see how you can hope to prove that $A$ is equal to $\mathbb{N}$ "without an explicit definition of" the latter. If you don't know what $\mathbb{N}$ is, then how can you prove anything about it? –  Arturo Magidin Oct 6 '10 at 16:06
add comment

3 Answers

up vote 0 down vote accepted

An inductive set $A$ is any set with the following properties:

  • $\left\{\right\}\in A$
  • $\forall x\left(x\in A\rightarrow S\left(x\right)\in A\right)$, where $S\left(x\right)$ is the successor of $x$

You can prove that $\mathbb{N}$ is an inductive set, and that if $A$ is any inductive set, then $\mathbb{N}\subseteq A$, but the other way around is false, that is, you can't prove that $A\subseteq\mathbb{N}$. Take for example $A=\mathbb{N}\cup\left\{a\right\}$, where $a$ is anything except a natural number. $A$ is inductive, but it is obvious that $A\subseteq\mathbb{N}$ is false.

Anyway, as far as I know, the best definition of the set of natural numbers is the following one: $\forall x\left(x\in\mathbb{N}\leftrightarrow\forall A\left(x\in A\right)\right)$, where $A$ is any inductive set.

share|improve this answer
Under your definition, $A=\mathbb{N}\cup${$a$} is not inductive, because although it contains $a$, it does not contain $S(a)$. You need to "throw in" $S(a)$, $S(S(a))$, $S(S(S(a)))$, etc. –  Arturo Magidin Oct 7 '10 at 18:47
@Arturo: Yes, of course. Sorry for my oversight. –  Francesco Turco Oct 7 '10 at 21:31
add comment

It seems to me that your 'proof' that the set $A \subseteq \mathbb{N}$ must have a mistake because basically you're just defining what Tom Apostol calls an inductive set in his Calculus book. I mean, $A$ can just be a set of real numbers and could perfectly well satisfy your two propierties.

For instance you can take $A = [0, \infty[$ and then $A$ satisfies both properties, but nonetheless $A$ is not contained in $\mathbb{N}$.

In fact Apostol's book defines $\mathbb{N}$ as the set of all numbers that belong to every inductive set.

share|improve this answer
Even when we explicitly say, in ii), for every 'n' natural number? Isn't that the so called 'environment set', which is the "biggest" set capable of satisfying those two properties? –  Mr. RM Oct 6 '10 at 16:03
But how can you make sense of "for every $n$ natural number" without knowing what "natural numbers" means? If you do not have a definition of the set of natural numbers, it does not seem to me to make sense. –  Arturo Magidin Oct 6 '10 at 16:10
@Mr. RM: the definition you give of $A$ merely asserts that $0$ is in $A$, and that for every natural number $n$ (whatever that may mean in the absence of a definition of natural numbers), if $n$ is in $A$ then $n+1$ is in $A$. It does not, however, assert that these are the only things in $A$. For example, the set $A$ of all integer multiples of $\frac{1}{2}$ satisfies the two conditions you give, but is not contained in the set of natural numbers. There is no "biggest set" that satisfies the two properties: every cardinal and every ordinal satisfies them. –  Arturo Magidin Oct 6 '10 at 16:14
@Arturo: The context in which this homework was given was to come up with an inductive definition of N. In class we came up with various. Then, for homework we were to prove that those definitions were indeed the same as the definition of the natural numbers. But all this time we never really defined N. Since I usually struggle with math concepts, I was thinking to be missing some 'key' to this. –  Mr. RM Oct 6 '10 at 16:16
@Arturo: That cardinal and ordinal stuff I haven't reached it yet. Our teacher said, like you, that there is an infinity of sets satisfying those two properties, for you can come up with another set satisfying those two properties and then some more that the set A actually cannot. In the end, he concluded that N was the ultimate set satisfying those two properties for A is included in N. That was I said the "biggest". I apologise for the confusion. –  Mr. RM Oct 6 '10 at 16:23
show 6 more comments

That's not an inductive definition of $A\:$. Rather, it's an inductive proof that $\ A \supseteq\mathbb N\:$. If you know additionally that $\: A \subseteq \mathbb N\:$ then you can conclude that $\:A = \mathbb N\:$. That's standard mathematical induction.

share|improve this answer
But for that we need some definition of N, right? –  Mr. RM Oct 6 '10 at 16:27
Yes, of course. You might find it helpful to read the Wikipedia article on Structural Induction –  Bill Dubuque Oct 6 '10 at 16:33
add comment

Your Answer


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