1
$\begingroup$

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.

  • 0
    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?2010-10-06

3 Answers 3

0

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.

  • 0
    @Arturo: Yes, of course. Sorry for my oversight.2010-10-07
2

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.

  • 0
    @Mr. RM: (cont) The principle of induction says that any **subset of $N$** that satisfies the two conditions must be equal to $N$. But notice that you start with a SUBSET of $N$. Second: You cannot prove *anything* about $N$ until you have a *definition* of $N$. (And what you give above is not a definition of a set, it is a set of conditions that a set may or may not satisfy; that's why there is no single set $A$). The conditions you have *do not define $N$*. You cannot prove they do, because it is *false* that they do. So you may as well stop trying proving that they define $N$.2010-10-06
1

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.

  • 0
    Yes, of course. You mi$g$ht find it helpful to read the Wikipedia article on [Structural $I$nduction](http://en.wikipedia.or$g$/wiki/Structural_induction)2010-10-06