Property for the natural numbers.

This question is inspired by another question I had, where I wanted to prove something about the natural numbers.

Often in analysis books I see some proofs, where they use the natural numbers, but it is not really proved why they can argue like they do with the natural numbers, and I never even thought it was a problem, because it seemed so reasonable. Here are two different cases I have seen, it is the first one I am wondering about:

1. We make a procedure where we look for something in a function that has the natural numbers as it domain. We start with 1, and if f(1) does not have the desired property we create an alement $a_1$, if f(2) does not have the property we want, we create an element $a_2$, and move on. Then we conclude that either we will have a finite number of elements $a_1,a_2,..,a_n$, or we will get an infinite sequence $a_1,a_2,...$, where every natural number k, will occur as $a_k$.

2. We have a set S with the natural numbers, and we know that there is an n in the natural numbers that has this property. We want to show that there is a smallest element in here that has this property, we start by 1, and if one does not have this property we go to 2, if 2 not, we go to 3 etc., then we know that we will stop before n, or at n.

I have seen some books that have made arguments similar to these. Property 2 is the well ordering property, and is proved using induction. But can property 1 also be proved with induction?

Here is the example of the proof that uses property 1. It is from measure theory, and all the details are not important for this question, the only thing that is important for this question is why he can say what he says where I have marked in red:

• Is it accurate to call this induction in the way you have described, since the n case does not imply the n + 1 case? It is valid but it not induction unless one case implies the next. – theREALyumdub Aug 27 '15 at 1:21
• @theREALyumdub: It is induction in the form of an inductive construction. – user21820 Aug 27 '15 at 1:53
• Property (1) looks like it's essentially omega-consistency in disguise; effectively it's saying that either there is some specific $i$ for which $f(i)$ is true, or we have $\forall k\neg f(k)$. – Steven Stadnicki Aug 27 '15 at 2:58
• I'm confused as to what you're asking. Any set is either finite or infinite, right? – Akiva Weinberger Aug 27 '15 at 3:09
• My understanding of the question is: "We start by writing down $a_1$. At each step we either write down $a_k$ (where $k$ is the smallest number not yet written) or we stop. Then prove that we either end up with a finite sequence $a_1,\dots,a_n$ or the infinite sequence $a_1,a_2,\dots$." Is that the right understanding? – Akiva Weinberger Aug 27 '15 at 3:13

• You are incorrect. Note the use of the word "deterministically." By this, I mean that there is a function $f$ such that, given some $a_n$ that does not meet the conditions for termination, we define $a_{n+1}:=f(a_n).$ This uses the Recursion Theorem, and no choice is required. – Cameron Buie Aug 27 '15 at 3:00