Well-ordering of Natural Numbers

[dmuthuk]

I am trying to prove that the set of natural numbers is well-ordered using induction. I am assuming of course that the natural numbers are defined as as the smallest inductive set (of the type specified by the Axiom of Infinity) and that the usual order is defined by n<m iff n\in m. I have an argument in mind, but since I am still getting used to induction, I am not sure sometimes if I am using it the right way. I mean I have used it a lot before, but have never thought about it seriously.

So, let S\subset\mathbb{N} be defined as follows: n\in S iff every subset of \mathbb{N} that contains n as an element has a smallest element. Then, since 0=\emptyset is an element of every number, it is the smallest element of every set that contains it. Next, we can assume that n\in S and prove that every set containing n^+ also has a smallest element. I will leave out the details here, but I was wondering if I can use induction in this manner.

The reason I am a little unsure about this is because I am used to using induction to prove statements like "the sum of the first n numbers is always \frac{n(n+1)}{2}".

 

[morphism]

I think that will be fine. (You might need to use strong induction -- at least the argument I have in mind does -- but strong induction is implied by regular induction.)

 

[dmuthuk]

Thanks. I have actually been reading Halmos' Naive Set Theory, and I just started learning about "transfinite induction". I wonder if strong induction is connected with this. I know that transfinite induction is equivalent to mathematical induction for \mathbb{N}.

 

[morphism]

It is related to transfinite induction, but this relation isn't relevant here. In a proof using regular induction for \mathbb{N}, you prove in the inductive step that if P(k) is true then P(k+1) is true; if you were using strong induction, on the other hand, you'd prove that if P(i), P(i+1), ..., P(k) are all true, then P(k+1) is true. It's really the same idea, except you're using the fact that your proposition is true for all previous cases instead of only the preceding one.

 

[matt grime]

Transfinite induction pertains to using ordinals strictly larger than N, so it is of no use here.

 

[dmuthuk]

In connection with the Well-ordering Theorem, I have come across this notion called "continuation", and it is a bit confusing. The definition in Halmos goes something like this:

A well-ordered set A is said to be a continuation of a well-ordered set B if B\subset A, B is an initial segement of A and B has the same ordering as A.

Now, I am assuming that "initial segment of A" means "initial segment of some element of A". Secondly, I would think that the subset criterion follows from the initial segment criterion, and hence it is redundant. However, does this definition assume that both A and B are included in some larger poset X? If that is the case, then, an initial segment of an element in A is not necessarily a subset of A, but I doubt that the definition assumes anything like that. Furthermore, I was under the impression that when we speak of one ordered set being a "subset" of another, it automatically inherits the ordering of the larger set since an ordered set is really a pair \{A,R\}, where R is the order relation on A. This could just be an issue with convention.

 

[matt grime]

This seems like it ought to be a remarkarbly obvious definition: what is a welol ordered set? it is just elements

x_1, x_2, x_3,..., x_n for a finite ordinal

x_1,... for the first infinite ordinal

x_1,x_2,...
y_1,y_2,...y_n for the ordinal w+n and so on. (Ok, you can't draw uncountable ordinals like this, but that is all that is going on.)
A is a continuation of B if you can get B by just removing all things after a certain point. Surely.

I don't know how it would be possible for an _element_ of a well ordered set to have 'an initial segment'

 

[dmuthuk]

Well, I haven't studied ordinal numbers just yet. I understand that well-ordered sets are just ordered sets for which every non-empty subset has a least element. By definition, if X is an ordered set, the initial segment determined by x\in X is the set s(x)=\{y\in X: y<x\}. I am not sure if this is a standard definition, but at least it is the one I have come across in Halmos' book.

In fact, my problem with the definition is independent of "well-ordering" since it could have been applied to any ordered set. I believe my confusion arises from the definition of ordered sets that I am currently using. As I mentioned earlier, the definition I am thinking about is that of a pair \{A,R\}, where A is the set considered, and R is a particular subset of A\times A that satisfies the order axioms. Given this model, what does it mean for one ordered set to be a "subset" of another? I suppose one way to define it is: \{A,R\} is a subset of \{B,T\} if A\subset B. This way, the ordering of A need not be the same as the ordering of A within B. So, it needs to be specified. I think this is the usual approach. However, we could also have required that R\subset T in the definition. Then, when we speak of subsets of ordered sets, we can automatically assume that they inherit the ordering from the larger set.

In any case, I am just trying to understand these ideas more precisely to avoid ambiguity.

 

[DrewBlay]

Thanks for this, very helpfull


___________________________________

http://www.free-training-tutorial.com/ordering-numbers-games.html"