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
    What definition of $\mathbb N$?2010-10-06
  • 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
    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.2010-10-07
  • 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
    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?2010-10-06
  • 0
    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.2010-10-06
  • 0
    @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.2010-10-06
  • 0
    @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.2010-10-06
  • 0
    @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.2010-10-06
  • 0
    @Mr. RM: I don't know what "ultimate set" means. But you can easily see how to extend my example of multiples of 1/2 to get lots and lots of examples. What I suspect is meant is that $N$ is the *smallest* set that both (i) contains 0; *and* (ii) whenever it contains $n$, it also contains $n+1$ (where $n+1$ needs to be defined in some way). But what you want is the *smallest* such set, not the largest.2010-10-06
  • 0
    @Arturo: Now I am very confused. If I had a definition of N and this definition of A, would it be possible to prove that N=A? And the proof would be divided in two (A⊇N and N⊇A) very similar arguments, just making use of the principle of induction. Is this right? I really appreciate the time your taking to answer me, and can't thank you enough for putting with these, for sure, newbie questions. Thanks again!2010-10-06
  • 0
    @Mr. RM: No, you *cannot prove that $A=N$* because I already gave you an example of a set $A$ that satisfies the conditions you give, but is *not* equal to $N$. So how could you possibly hope to prove something that is patently false? You can prove that any set $A$ that satisfies the conditions will necessarily CONTAIN $N$, but you cannot prove that it will be contained in $N$ because that assertion is, in general, FALSE.2010-10-06
  • 0
    @Arturo: One last question before i dig my nose again on my exercises: The principle of induction just says that if any set other than A has those two properties, A is a subset of it, right? Then, if i could prove that N is the smallest such set, i could conclude that N=A?2010-10-06
  • 0
    @Mr. RM: No. AGAIN: First, there is no unique set $A$ that satisfies the conditions you give, so you cannot talk about $A$ as if it were a *specific* set. It's not. The set of all integral multiples of $1/2$ is an example of a set $A$ satisfying your conditions, but it is *also* false that any set that satisfies the two conditions you give must contain $A$ (take the set of $B$ all integer mulitples of $1/3$, for example; it satisfies the two conditions, but $A$ is not contained in $B$ and $B$ is not contained in $A$; they are incomparable). (cont.)2010-10-06
  • 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
    But for that we need some definition of N, right?2010-10-06
  • 0
    Yes, of course. You might find it helpful to read the Wikipedia article on [Structural Induction](http://en.wikipedia.org/wiki/Structural_induction)2010-10-06