Did I do this problem from Spivak correctly?

[mathemasochist]

Homework Statement

Prove induction from the well-ordering principle.

Homework Equations

The Attempt at a Solution

So my attempt is similar to what Spivak uses to prove well-ordering from induction. Let A be the set equipped with the following properties:
1. 1 is in A
2. For every k in A, k+1 is also in A.

Now for the sake of contradiction, assume a nonempty set B of natural numbers such that none of the elements in B are in A. By well-ordering, there exists a smallest member of B, call it n, and by the conditions on A, n is greater than 1. This means n-1 is in A. However, if n-1 is in A, n is in A as well. Contradiction. So no such nonempty subset B exists. Therefore, all natural numbers are in A.

I feel like I messed up somewhere. In particular, is it valid to assume that, in set A, all members are natural numbers? Sorry, I'm not used to this level of rigor. When I was working through this problem, I had like 10 flashes of circular reasoning that assumed an informal version of induction somewhere.

 

[andrewkirk]

More information is needed.
What is the set that you are assuming to be well-ordered?
What is the precise statement of the induction principle that you wish to prove? Make sure that you indicate the identity of all sets that are referred to in this statement.
You refer to the natural numbers. What is the precise definition of 'natural numbers' that you are supposed to use here?

 

[mathemasochist]

I was trying to prove induction in general using the well-ordering principle.
Here is the precise statement I was trying to prove:
If A is a set such that 1 is an element of A and k+1 is in a whenever k is in A, then A is the set of natural numbers.

I don't know what the precise definition of natural numbers is, since Spivak just defines them the standard non-rigorous way (as the counting numbers 1, 2, 3...) I am assuming all sets of natural numbers are well-ordered.

 

[andrewkirk]

The statement is not provable because it is not true. The criterion is satisfied by the integers, the rational numbers, the real numbers and the complex numbers, none of which is equal to the set of natural numbers.

Nor does requiring A to be a well-ordered set fix the problem. The set
$$\{k/2\ :\ k\in\mathbb N\}$$ is well-ordered and obeys the above criterion, but it is not the set of natural numbers.

 

[mathemasochist]

Oops, you're right. I looked back at the text, and Spivak includes the additional condition that A is a set of natural numbers. Then the problem becomes proving that A contains all the natural numbers. Does specifying this condition fix my proof?

 

[andrewkirk]

I think Spivak's calculus is one of the best mathematics texts I have ever had the pleasure to read. But we are all human, even Michael Spivak, and I think he's got himself in a muddle here. I got out my 35-year old copy and looked up the part that deals with this and you're right, he doesn't define the natural numbers, which makes the whole problem meaningless. Here's why.

The usual construction of a set called 'the natural numbers' and denoted by $\mathbb N$ uses the axiom of infinity to assert the existence of a set that has the inductive property - the property you ascribe to $A$ above. From that we deduce that the set $C$ of all sets that satisfy the inductive property is nonempty. Hence we also know to be nonempty the unique set that is the intersection of all such sets, ie:
$$\bigcap_{S\in C}S$$
We call this set $\mathbb N$.

Given that definition, we do not need the well-ordering property to show that a subset of $\mathbb N$ that has the inductive property is equal to $\mathbb N$. Let $B$ be such a set. Then by assumption we have $B\subseteq\mathbb N$. Since $B$ has the inductive property we also know that $B\in C$. We then use the fact that the intersection of a collection of sets is a subset of every set in the collection (easily proven) to deduce that $\bigcap_{S\in C}S\triangleq\mathbb N\subseteq B$. So we have $\mathbb N\subseteq B\subseteq \mathbb N$, whence $B=\mathbb N$.

In order to set a problem with a less trivial solution, and in which we needed to use the well-ordering theorem, Spivak would first need to produce a different definition of the natural numbers.