Problem on successor/predecessor set

[StatOnTheSide]

Hi All. There is a problem in Halmos's Naive Set Theory on page 49. It states that

"if n$\neq$0 and if n is a natural number, prove that n=S(m) for some natural number m." Here, S(m) denotes the successor of the number m and is given by S(m)=m$\bigcup${m}.

My attempted solution to this was to use induction. Let P be a set which has "0" in it. Also, let P contain all the natural numbers such that if n$\in$P, then n=S(m) for some natural number m. Now 1=S(0). So 1$\in$P. 2=S(1). Hence 2$\in$P. Now let this be true for some n. Now as the successor of n, namely S(n) is, by definition, successor of n, we have that S(n) has a number (equal to n) such that S(n)=S(n). Therefore S(n)$\in$P. Hence by induction, it must be true for all n.

Since every natural number is in P, which posesses the property that all its elements have a predecessor, it must be true that all natural numbers have a predecessor.

I have two questions.

1. Is my proof right?

2. If it is wrong, kindly point out the mistake

3. If it is right, then I feel that "S(n)$\in$P whenever n$\in$P" is a funny statement. S(n)$\in$P even if n$\notin$P because it has a number n which is its predecessor. Why do we need n to be in P to prove it? In other words,
can this be proved without using induction? Please let me know.

 

[StatOnTheSide]

I also wanted to add that I read elsewhere that Induction can be used to prove it. It is in Terence Tao's book and is contained as an excercise where he has hinted that Induction has to be used. I just wish to know if I have used induction properly.

 

[dcpo]

Answering this question really depends on how the natural numbers are being defined. I don't have Halmos' book, but a standard construction is that 0 is defined to be the empty set, and every other number is defined to be the set containing all the previous 'numbers'. So $0=\emptyset, 1= \{\emptyset\}, 2=\{\{\emptyset\},\emptyset\}$ etc. From what you write it seems Halmos is using this definition, though I was slightly thrown initially by your use of $\bigcup$ rather than $\cup$.

This is a recursive definition, and an inductive proof of the proposition you're asking about is trivial when viewed this way. We easily establish that 1 has the required property, which is our base case, and the successor case is tautological. Of course, this requires that the natural numbers be defined in this way. Depending on how exactly Halmos has set things up it may be more complicated, and there's also the possibility that he has formally defined induction in such a way as to require more work here, but basically the result falls out of the recursive definition of natural numbers.

With regard your proof, I think you have an idea that leads to a correct answer, but it seems a little round about. I don't understand, for example, why you introduce P rather than just working with the set of all (non-zero) natural numbers directly. Possibly this is related to the way induction has been introduced. Also, your statement " let P contain all the natural numbers such that if $n\in P$, then $n= S(m)$ for some natural number $m$" is a little confusing , and is not formally correct as it references itself, and in any case P could be empty if we overlook the formal problem. I think you want to say that P contains every natural number that is a successor.

 

[StatOnTheSide]

Hi dcpo. Thanks very much for the reply.

Answering this question really depends on how the natural numbers are being defined. I don't have Halmos' book, but a standard construction is that 0 is defined to be the empty set, and every other number is defined to be the set containing all the previous 'numbers'. So $0=\emptyset, 1= \{\emptyset\}, 2=\{\{\emptyset\},\emptyset\}$ etc.

Halmos has defined 0=∅, 1 as being equal to {0}, 2 as being equal to {0,1} etc. In general, n+$\equiv$n$\cup${n}.

From what you write it seems Halmos is using this definition, though I was slightly thrown initially by your use of $\bigcup$ rather than $\cup$.

I am sorry about the confusion. I meant to use $\cup$ :).

This is a recursive definition, and an inductive proof of the proposition you're asking about is trivial when viewed this way. We easily establish that 1 has the required property, which is our base case, and the successor case is tautological. Of course, this requires that the natural numbers be defined in this way.

It is true that natural numbers have been defined that way.

Depending on how exactly Halmos has set things up it may be more complicated, and there's also the possibility that he has formally defined induction in such a way as to require more work here, but basically the result falls out of the recursive definition of natural numbers.

I wish to quote the induction definition here from the book. It states:

The minimality property of ω (set of natural numbers) can be expressed by saying that if a subset S of ω is a successor set, then S = ω. Alternatively, and in more primitive terms,

III. if S$\subset$ω, if 0$\in$S, and if n+ $\in$ S whenever n$\in$S, then S = ω.
Property (III) is known as the principle of mathematical induction.

Also, he states elsewhere that any property is identified with a set. In his own words,

It is ubiquitous mathematical practice to identify a property with a set, namely with the set of all objects that possesses the property.

With regard your proof, I think you have an idea that leads to a correct answer, but it seems a little round about. I don't understand, for example, why you introduce P rather than just working with the set of all (non-zero) natural numbers directly. Possibly this is related to the way induction has been introduced.

That is true. I introduced P because he has defined principle of induction to be the fact that a subset S of ω is equal to ω if it is a successor set. I started the proof on the same lines saying that let P (instead of S) be the set of all natural numbers having a predecessor and also the number 0. Then 1, 2, 3,.. all belong to it. Also, whenever n belongs to it, so does n+ in a trivial way. Hence P=ω.

Also, your statement " let P contain all the natural numbers such that if $n\in P$, then $n= S(m)$ for some natural number $m$" is a little confusing , and is not formally correct as it references itself, and in any case P could be empty if we overlook the formal problem. I think you want to say that P contains every natural number that is a successor.

That is correct. If I were to reword it, I would say "let P be the set containing 0, and all the numbers which have a predecessor. Then 1, 2, 3... all have predecessors and hence, are in P..."

With this correction, will the proof look OK? Please let me know.

 

[dcpo]

With the definition of induction you give the proof is straightforward. You take the set containing 0 along with all natural numbers which have predecessors. The inductive step is a tautology; by definition the successor of every number must be in this set. Therefore your set contains 0 and every successor number, and thus must be the set of all natural numbers, and thus all non-zero natural numbers must have a predecessor. This seems to be what you are getting at but you need to make explicit the induction.

 

[StatOnTheSide]

Thanks very much dcpo. It feels very comforting to get the right direction while solving problems in something as abstract as set theory :).