Proving Induction Principle using Well Ordering Principle of Natural Nos

[solakis1]

In proving the induction principal using the well ordering principal of the Natural Nos the following proof was suggested:

Given :
1) Let S be a subset of N (=Natural Nos)

2) $1\in S$

3)$\forall y[y\in S\Longrightarrow (y+1)\in S$

Then prove : S=N

Proof:

Let , T= N-S and $T\neq\emptyset$

Then ,bu the well ordering principal T has a smallest element

Let x be the smallest element of T

Then $x-1\in S$

But $(x=1)+1\in S$

So $x\in S$

Thus T is empty and S=N

My problem is ,how can we prove that :

$x-1\in S$

I tried the following:

$\neg (x-1)\in T$ ,because x is the smallest element of T

But, $\neg (x-1)\ T\Longrightarrow[(x-1)\in N\Longrightarrow (x-1)\in S]$ ,because T=N-S

And since $\neg (x-1)\in T$ weare left with:

$x-1\in N\Longrightarrow x-1\in S$

And finally to prove :$x-1\in S $ ,x-1 must be a Natural No

How do we prove that??

 

[caffeinemachine]

In proving the induction principal using the well ordering principal of the Natural Nos the following proof was suggested:

Given :
1) Let S be a subset of N (=Natural Nos)

2) $1\in S$

3)$\forall y[y\in S\Longrightarrow (y+1)\in S$

Then prove : S=N

Proof:

Let , T= N-S and $T\neq\emptyset$

Then ,bu the well ordering principal T has a smallest element

Let x be the smallest element of T

Then $x-1\in S$

But $(x=1)+1\in S$

So $x\in S$

Thus T is empty and S=N

My problem is ,how can we prove that :

$x-1\in S$

I tried the following:

$\neg (x-1)\in T$ ,because x is the smallest element of T

But, $\neg (x-1)\ T\Longrightarrow[(x-1)\in N\Longrightarrow (x-1)\in S]$ ,because T=N-S

And since $\neg (x-1)\in T$ weare left with:

$x-1\in N\Longrightarrow x-1\in S$

And finally to prove :$x-1\in S $ ,x-1 must be a Natural No

How do we prove that??

Good job.

But first let's fix a notation issue.
I believe when you write $\neg (x-1)\in T$, it is same as $(x-1)\notin T$. Isn't it?

Now. $x$ is the smallest natural in $T$. Note that $x>1$ since if $x=1$ then we'd have $1\notin S$, contrary to the hypothesis.

Therefore $x-1$ is a natural number.

Does this solve your problem?

 

[solakis1]

Good job.

But first let's fix a notation issue.
I believe when you write $\neg (x-1)\in T$, it is same as $(x-1)\notin T$. Isn't it?

Now. $x$ is the smallest natural in $T$. Note that $x>1$ since if $x=1$ then we'd have $1\notin S$, contrary to the hypothesis.

Therefore $x-1$ is a natural number.

Does this solve your problem?

No .

YeS I AGREE x>1 ,because $x\geq 1$ and since 1 does not belong to T we have $x\neq1 $

But according to what theorem or definition or from any statement of the proof can you conclude x-1 is a natural No?

I need something to justify the claim that x-1 belongs to N.

Subtraction is not defined in Natural Nos

 

[Deveno]

The successor function is onto $\Bbb N - \{1\}$ (every natural number except 1 is the successor of some other natural number).

Therefore, given $x \in T = \Bbb N - S$, either:

1. $x = 1$, or
2. $x = s(y)$ for some $y \in \Bbb N$.

Since the first possibility leads to $x \not\in S$, we must have the second possibility.

Now $y < s(y) = x$, which means if $x$ is the smallest element of $\Bbb N - S$, that $y \not\in \Bbb N - S$, and since $y \in \Bbb N$, we must have:

$y \in \Bbb N \cap S = S$.

Since $y \in S \implies s(y) \in S$, we have $x = s(y) \in S$, contradicting that $x \not\in S$.

(Note carefully that I do not use subtraction OR addition).

Since our only assumption is that $T \neq \emptyset$, this must be false, as it leads in all cases to a contradiction.

A careful reading above shows that we use the following property of $\Bbb N$:

$n < s(n)$ for all $n \in \Bbb N$.

So a full proof depends on a careful definition of "<" that does not use anything except the successor function (for we need an order first, to assert that this order is "well-ordered").

Alternatively, it IS possible to define subtraction on $\Bbb N$, given addition, for CERTAIN pairs, $(x,y) \in \Bbb N^2$, that is, set, when $x > y$:

$x - y$ to be the unique element $k$ of $\Bbb N$ such that $y + k = x$.

 

[solakis1]

The successor function is onto $\Bbb N - \{1\}$ (every natural number except 1 is the successor of some other natural number).

Therefore, given $x \in T = \Bbb N - S$, either:

1. $x = 1$, or
2. $x = s(y)$ for some $y \in \Bbb N$.

Since the first possibility leads to $x \not\in S$, we must have the second possibility.

Now $y < s(y) = x$, which means if $x$ is the smallest element of $\Bbb N - S$, that $y \not\in \Bbb N - S$, and since $y \in \Bbb N$, we must have:

$y \in \Bbb N \cap S = S$.

Since $y \in S \implies s(y) \in S$, we have $x = s(y) \in S$, contradicting that $x \not\in S$.

(Note carefully that I do not use subtraction OR addition).

Since our only assumption is that $T \neq \emptyset$, this must be false, as it leads in all cases to a contradiction.

A careful reading above shows that we use the following property of $\Bbb N$:

$n < s(n)$ for all $n \in \Bbb N$.

So a full proof depends on a careful definition of "<" that does not use anything except the successor function (for we need an order first, to assert that this order is "well-ordered").

Alternatively, it IS possible to define subtraction on $\Bbb N$, given addition, for CERTAIN pairs, $(x,y) \in \Bbb N^2$, that is, set, when $x > y$:

$x - y$ to be the unique element $k$ of $\Bbb N$ such that $y + k = x$.

So the theorem you are suggesting is :

$\forall v[v\in N\Longrightarrow v=1\vee\exists y(y\in N\wedge y+1=v)]$

 

[Deveno]

Indeed, but "proving this" depends a LOT on what you are able to take "as given".

Typically, the principle of induction is often given as an AXIOM of the natural numbers. This is EQUIVALENT to the Well-orderedness of the natural numbers, in that given one, one can prove the other. It is not possible to prove BOTH given NEITHER.

One thing missing from this discussion is a "formal definition" (from whatever text/class you are using) of "what natural numbers ARE".

If one starts with a "first natural number" (by convention called "1"), and a successor function:

$s: \Bbb N \to \Bbb N - \{1\}$

one has to state which PROPERTIES $s$ is to satisfy. Note my statement of the co-domain of $s$ above already encodes one such property:

$\neg (\exists x \in \Bbb N: 1 = s(x))$

Another typical property is:

$s(x) = s(y) \implies x = y$ ($s$ is injective).

There is a vicious "circular reasoning trap" here, in that $s$ is only DEFINED given $\Bbb N$, and we'd like to use $s$ to DEFINE $\Bbb N$. One way around this, is to define:

$1 = x$

where $x$ is a one-element set (typically, the only one-element set that is GUARANTEED to exist is $\{\emptyset\}$), and then define the "successive sets" (set operator):

$s(x) = x \cup \{x\}$.

Then $\Bbb N$ is taken to be the closure of $x$ under $s$. This then guarantees that:

$s: \Bbb N \to \Bbb N -\{1\}$ is surjective (by closure).

The natural numbers obtained this way ARE NOT UNIQUE, we get isomorphic, but distinct, copies of the natural numbers if:

$x = $ "an elephant"
$x = $ "an apple" and so on.

Because of this, many find it preferable to start the natural numbers with 0, which can be unambiguously defined as:

$0 = \emptyset$.

One can (as I pointed out) that "addition" (taken as defined recursively by:

$a + 0 = a$
$a + s(b) = s(a + b)$)

can be used to define an order on $\Bbb N$, defining such an order without reference to addition is a little trickier: we first define:

$s^2 = s \circ s$
$s^{s(k)} = s \circ s^k$

and say: $a < b$ iff there is $k \in \Bbb N$ such that $b = s^k(a)$.

 

[solakis1]

Indeed, but "proving this" depends a LOT on what you are able to take "as given".

Typically, the principle of induction is often given as an AXIOM of the natural numbers. This is EQUIVALENT to the Well-orderedness of the natural numbers, in that given one, one can prove the other. It is not possible to prove BOTH given NEITHER.

One thing missing from this discussion is a "formal definition" (from whatever text/class you are using) of "what natural numbers ARE".
If one starts with a "first natural number" (by convention called "1"), and a successor function:

$s: \Bbb N \to \Bbb N - \{1\}$

one has to state which PROPERTIES $s$ is to satisfy. Note my statement of the co-domain of $s$ above already encodes one such property:

$\neg (\exists x \in \Bbb N: 1 = s(x))$

Another typical property is:

$s(x) = s(y) \implies x = y$ ($s$ is injective).

There is a vicious "circular reasoning trap" here, in that $s$ is only DEFINED given $\Bbb N$, and we'd like to use $s$ to DEFINE $\Bbb N$. One way around this, is to define:

$1 = x$

where $x$ is a one-element set (typically, the only one-element set that is GUARANTEED to exist is $\{\emptyset\}$), and then define the "successive sets" (set operator):

$s(x) = x \cup \{x\}$.

Then $\Bbb N$ is taken to be the closure of $x$ under $s$. This then guarantees that:

$s: \Bbb N \to \Bbb N -\{1\}$ is surjective (by closure).

The natural numbers obtained this way ARE NOT UNIQUE, we get isomorphic, but distinct, copies of the natural numbers if:

$x = $ "an elephant"
$x = $ "an apple" and so on.

Because of this, many find it preferable to start the natural numbers with 0, which can be unambiguously defined as:

$0 = \emptyset$.

One can (as I pointed out) that "addition" (taken as defined recursively by:

$a + 0 = a$
$a + s(b) = s(a + b)$)

can be used to define an order on $\Bbb N$, defining such an order without reference to addition is a little trickier: we first define:

$s^2 = s \circ s$
$s^{s(k)} = s \circ s^k$

and say: $a < b$ iff there is $k \in \Bbb N$ such that $b = s^k(a)$.

In proving that theorem do we have to use induction?

If yes ,is there any other proof ??

 

[Deveno]

In proving which theorem?

If the theorem you are referring to is the one in your last post, one *could* use induction to prove it...but, if the REASON you want to prove it is to bolster a proof about the induction principle, that's maybe not such a good idea.

Which is why I want to know: what facts about the natural numbers are you given that you do not HAVE to prove?

 

[solakis1]

In proving which theorem?

If the theorem you are referring to is the one in your last post, one *could* use induction to prove it...but, if the REASON you want to prove it is to bolster a proof about the induction principle, that's maybe not such a good idea.

Which is why I want to know: what facts about the natural numbers are you given that you do not HAVE to prove?

If you can remember :

In my OP in trying to prove rhe induction principal using the well ordering principal i had to use the fact that if :

If x is anatural No other than one ,then x-1 is a natural No as well.And in trying to justify that fact you suggested the theorem:$\forall v[v\in N\Longrightarrow v=1\vee\exists y(y\in N\wedge y+1=v)]$But in proving that theorem we have to use INDUCTION .Hence we are going into a circle.

 

[Deveno]

I did not say we HAVE to use induction...again, I ask you: what is your DEFINITION of natural number?

 

[solakis1]

I did not say we HAVE to use induction...again, I ask you: what is your DEFINITION of natural number?

Can you find then another way of proving the theorem without using induction??

Choose any axiomatic system you like ,as long as it has not the induction principal as an axiom,because that is the principal we want to prove.

 

[solakis1]

I did not say we HAVE to use induction...again, I ask you: what is your DEFINITION of natural number?

Natural No is a member of a set N OBEYING THE FOLLOWING AXIOMS:

1} $1\in N$

2) For each $n\in N$ there exists a unique $n*\in N$ called the successor of n

3) For each $n\in N$ we have : $n*\neq 1$

4) If $n,m\in N$ and n*=m* then n=m

5) Any subset K of N having the properties:

......$1\in K$
......$k*\in K$ ,whenever $k\in K$

is equal to N

 

[Deveno]

Your axiom number 5 is equivalent to the induction principle.

But we can use it to prove this:

$\forall n \in \Bbb N: (n = 1)\vee(\exists k:n = s(k))$

as follows.

Let $A = \{n \in \Bbb N: \exists k: n = s(k)\}$.

Since $A \subseteq \Bbb N$, it is clear from the definiition of $A$ that if $n \in A$, so is $s(n)$.

Let $B = \{1\} \cup A$.

Then we have: $1 \in B$. We also have $s(1) \in A$ and thus $s(1) \in B$.

Now if $k \in B$, either:

1. $k = 1$
2. $k = s(m)$ for some $m \in \Bbb N$ (since then $k \in A = B - \{1\}$).

If $k = 1$ we have $s(k) = s(1) \in B$. If $k \neq 1$, we have $k \in B - \{1\} = A$ so that $s(k) \in A$ and thus $s(k) \in B$.

Thus we see $B$ has the following properties:

1. $1 \in B$.
2. for all $k \in B$, we have $s(k) \in B$.

Therefore, by your axiom (5), $B = \Bbb N$, so $A = \Bbb N - \{1\}$.

Hence either for all $n \in \Bbb N$, we have either $n =1$, or $n \in A$, which is what we set out to prove.

There is a slight difference between $\Bbb N$ being INDUCTIVELY DEFINED, and "the principle of induction" being TRUE for $\Bbb N$. However, the latter is a consequence of the former.

What this all boils down to, in the end, is that axiom (5), or some OTHER axiom (like the well-ordered principle) is NEEDED to give the natural numbers the property we feel they "ought to have". A different way of saying this is:

The natural numbers is a minimal inductively-defined (or SUCCESSIVE) set that includes one.

The axiom of infinity in Zermelo Fraenkel set theory says there exists at least one such set. One can use the axiom (schema) of specification to then show the existence of a unique set that lies in EVERY successive set (informally, we take the intersection of all sets for which the axiom of infinity holds).

This then makes the principle of induction a consequence of the 'background" set theory.

Note that, in essence, this entire argument rests on the idea:

An infinite set exists.

One CANNOT prove this from the OTHER axioms of set theory, and I mention in passing that not ALL mathematicians BELIEVE this to be true (such mathematicians are known as ultrafinitists, a rather extreme form of mathematical reductionism). So essentially, this entire matter comes down to an article of faith:

Do you BELIEVE that induction is "intuitively true"?

 

[solakis1]

Your axiom number 5 is equivalent to the induction principle.

But we can use it to prove this:

$\forall n \in \Bbb N: (n = 1)\vee(\exists k:n = s(k))$

as follows.

If in proving the above Theorem we use the induction principal and then in proving the induction principal apart from the well ordering principal we use that theorem ,aren't we going in a circle?

WE are using the induction principal (thru the said theorem) to prove the induction principal

 

[Deveno]

Suppose we assume the well-ordering theorem is true. I'm not saying it IS, I'm saying suppose we ASSUME it is.

Let $S \subseteq \Bbb N$ be a set such that:

$1 \in S$
$k \in S \implies s(k) \in S$, where $s$ denotes the successor function (you can use $k^{\ast}$ or $k+1$ if you prefer).

We wish to show that $S = \Bbb N$.

To this end, we suppose that the opposite is true, that $\Bbb N - S \neq \emptyset$.

By the well-ordering principle, letting $T = \Bbb N - S$, since $T$ is non-empty, it has a minimal element, say $m$.

Also by the well-ordering principle, $\Bbb N$ itself has a minimal element: this is the natural number 1 (this follows from your axiom (3)).

First, let's examine whether or not we can have $m = 1$. Clearly, we cannot, for $1 \in S$, and therefore $1 \not\in T$. Since 1 is the minimal element of $\Bbb N$, it follows that $m > 1$.

The step you seem to have trouble with is this one:

$m = s(m')$ for some $m' \in \Bbb N$.

And that's why I keep asking you: WHAT ARE NATURAL NUMBERS?

I claim the natural numbers are THIS set:

$\{1,s(1),s(s(1)),s(s(s(1))),\dots,s^k(1),\dots\}$.

Except for 1, every element of this set is $s(\text{something})$, namely the previous natural number in the list.

This is logically equivalent to the claim:

$s:\Bbb N \to \Bbb N -\{1\}$ is SURJECTIVE, which (in my opinion) should be PART OF THE DEFINITION.

Let me ask you a different, but related question:

What is the set:

$\{k \in \Bbb N: k \neq s(m)$ for any $m \in \Bbb N\}$?

Returning to the proof:

If $m = s(m')$ we have $m' \in S$, but $s(m') = m \not\in S$, violating the construction of $S$ itself.

Since our only assumption was that $T$ is non-empty, this must be FALSE, so $S = \Bbb N$.

*********************

I want to remark here that we can view:

$s^k(1) = s(k)$ two different ways:

in the first way, $k$ is an ORDINAL, we are talking about the $k$-th successor of 1. On the right-hand side, $k$ is a NUMERAL, that is an element of $\Bbb N$. So, implicitly, we are referring to a bijection between numerals and ordinals. For example:

"Three" $\iff$ "Third".

As far as your remarks go about the "circularity" of these arguments: I AGREE. It matters not whether you pick the well-ordering principle, or the principle of induction as an "axiom", you have to choose ONE of them (or some OTHER equivalent logical statement) to fully DEFINE the natural numbers.

 

[solakis1]

Also by the well-ordering principle, $\Bbb N$ itself has a minimal element: this is the natural number 1 (this follows from your axiom (3)).

If you can prove:

for all,nεΝ $n\geq 1$, without induction ,then my problem is solved.

Axiom (3) and the well ordering principal do not prove that

I claim the natural numbers are THIS set:

$\{1,s(1),s(s(1)),s(s(s(1))),\dots,s^k(1),\dots\}$.

.

How do you know that the next element in the set is going to be:

$s^{k+1}(1)$??

 

[Deveno]

If you can prove:

for all,nεΝ $n\geq 1$, without induction ,then my problem is solved.

Axiom (3) and the well ordering principal do not prove that
How do you know that the next element in the set is going to be:

$s^{k+1}(1)$??

One question: what does $a \geq b$ mean for $a,b \in \Bbb N$?

 

[solakis1]

One question: what does $a \geq b$ mean for $a,b \in \Bbb N$?

By definition we have:

$\forall a\forall b[a\geq b\Longleftrightarrow a>b\vee a=b]$

Where $\forall a\forall b[a>b\Longleftrightarrow b<a]$

where :$\forall a\forall b\forall c [a<b\Longleftrightarrow\exists c(c\in N\wedge a+c=b)]$

 

[Deveno]

Well, OK, but if that is the case, then you must already have a definition of "+", in which case you CAN define subtraction, as long as $a > b$, and your original objection doesn't hold water.

(Explicitly: if $a > b$, then $a - b = k$, where $k$ is the natural number we know exists such that $b+k = a$, from the definition of ">", so as long as $a > b$, it follows that $a - b$ is a natural number).

Let's see if we can prove that for all $n \in \Bbb N$, we have $n \geq 1$. Clearly this holds if $n = 1$, so without loss of generality assume $n \neq 1$.

Suppose that $n < 1$. This means there is a natural number $k$ such that $k+n = 1$. Can $n = 1$? No, because that violates your axiom (3). In fact, if $n = s(m)$, we have from the definition of addition:

$k + n = k+s(m) = s(k+m)$, which again violates axiom (3).

Thus, $n \neq 2,3,4,\dots$, so which natural number can $n$ be?

I firmly believe that for a definition of "natural number" to be WORKABLE, you must INSIST that it be closed under successorship. Otherwise, for example, something like $\Bbb N[x]$ (polynomials with natural number coefficients) fits the bill, under lexicographical ordering, which can be made into a total order.