A questions about two definitions of the Principle of Mathematical Induction

[Dale10101]

My text says the following:

______________________________________________

"The Principle of Mathematical Induction"

· Let S be a set of positive integers which has the following properties.
o IF: S contains 1
o AND IF: S contains k +1 whatever it contains the positive integer k.
o THEN: S contains all positive integers.

Equivalently, for the purpose of defining a set of axioms for the system of integers, the Principal of Mathematical Induction can be restated as:

o "Every nonempty subset of the set of positive integers contains at least member."
_____________________________________________

I don't see how the 2nd definition is equivalent to the first.

Is it assumed that a "non empty set of the set of positive integers" is a subset of consecutive integers?

I would have assumed the set of say, even positive integers would be a proper subset of the the positive integers and if so what happens to k = 2, where k + 1 = 3 is not in the assumed subset?

This is a great forum, thanks, Dale

 

[DrPhil]

My text says the following:

______________________________________________

"The Principle of Mathematical Induction"

· Let S be a set of positive integers which has the following properties.
o IF: S contains 1
o AND IF: S contains k +1 whatever it contains the positive integer k.
o THEN: S contains all positive integers.

Equivalently, for the purpose of defining a set of axioms for the system of integers, the Principal of Mathematical Induction can be restated as:

o "Every nonempty subset of the set of positive integers contains at least member."
_____________________________________________

I don't see how the 2nd definition is equivalent to the first.

Is it assumed that a "non empty set of the set of positive integers" is a subset of consecutive integers?

I would have assumed the set of say, even positive integers would be a proper subset of the the positive integers and if so what happens to k = 2, where k + 1 = 3 is not in the assumed subset?

This is a great forum, thanks, Dale

I think the crucial phrase is "for the purpose of defining a set of axioms," that is, alternative set of axioms from Peano's axioms, which are what I learned. The first definition is based on Peano's axioms, and the second comes from set theory. I have a colleague who tries to confound me by using the set-theory axioms, but I haven't caught on yet. What we (Peano and I) call a "natural number" becomes a set with that number of members. If you want to follow up on that, here is a link:
https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers

 

[thepillow]

My text says the following:

I don't see how the 2nd definition is equivalent to the first.

This is a great forum, thanks, Dale

Hey Dale. They're equivalent in that if one is true then it can be shown that the other must also be true. But from their statements it's definitely not obvious that this is the case.


For example, suppose that the principal of mathematical induction is true. Then we can show that the well-ordering principal (non-empty subsets have a least element) must also be true.

Let's say we have a non-empty set \(\displaystyle S \subseteq \mathbb{N}\).

If \(\displaystyle 0 \in S \) then clearly \(\displaystyle S \) has a least element since there are no natural numbers less than 0. So let's suppose that \(\displaystyle 0 \notin S \). Suppose, also, that \(\displaystyle S \) does not have a least element (we'll arrive at a contradiction).

Now let's assume that for all \(\displaystyle 0 \leq i \leq k\) we have that \(\displaystyle i \notin S \).

If \(\displaystyle k+1 \) is an element of \(\displaystyle S\), then it must be the least element since all numbers between 0 and \(\displaystyle k \) are not in \(\displaystyle S \) by our assumption.

But we've assumed that \(\displaystyle S\) has no least element, so it must be that \(\displaystyle k+1 \notin S \). Then, by the principal of induction we have that \(\displaystyle k+2 \notin S \) and \(\displaystyle k+3 \notin S \), etc. So we arrive at the conclusion that \(\displaystyle S = \varnothing \). That is, there can't be any elements in \(\displaystyle S\) under these assumptions.

But we know that our set \(\displaystyle S \) is not empty. So we have a contradiction. And we can conclude that \(\displaystyle S \) must indeed have a least element.


So from the principal of induction we've arrived at the well-ordering principal. And you can go the other way as well.

Hope that helps a bit!

 

[Dale10101]

OK, and

Thank you Dr Phil and thank you M. Pillow.

A rudimentary question.

The set of integers (…-3,-2,-1,0,1,2,3…) are found to have several properties: closed under the operations of addition and multiplication, the properties of associativity and commutativity hold, etc … but before discovering these properties one needs something to start with something doesn't one?

So we posit a line marked off in equal units with each specific unit (or is it the mark following each unit) having a name that we have manufactured (one, two, three … and past 12 have a system for naming the increments.)

Is that the “given” before one even begins to define operations and look for properties?

If so, how does one say this as a beginning to the development of the theory of integers? Does one just say, we all know what integers are and what a number line is, and what it means to assign the set of integers to the number line now lets us define operations and discover properties.

If so, that would be fine, then I could go on to the next thing that confuses me. I ask because mathematics has a way of showing me that what seems obvious is often not.

I am following what each of you have written and have questions (whose answers will hopefully benefit more than myself), but I would like to be sure of my starting point.

Thanks.

 

[Dale10101]

If I may inquire.

Thank you M. thepillow

In part you were saying:

Let's say we have a non-empty set S⊆N.

If 0∈S then clearly S has a least element since there are no natural numbers less than 0. So let's suppose that 0∉S. Suppose, also, that S does not have a least element (we'll arrive at a contradiction).

Now let's assume that for all 0≤i≤k we have that i∉S.

OK, stopping there with a question

So for specificity let S = all even positive integers, a non empty set.

So 0∉S is true for +I.

We cannot assume that +I does not have a least element because we know the it has, 2. So we pretend we don’t know that and disagree with the argument, saying I will prove the opposite, that there is no least element.

"Now let's assume that for all 0≤i≤k we have that i∉S."

This confuses me a little. What is i? An address pointer, that is, a natural number counter allowed to click between each integer in its range, a convenience. But, the convenience does seem to take over a bit. Given +I, if k = 2, is k+1 =3 or k+1 = the contents of the next integer in the lineup, 4 ? It seems it needs to be the latter to support PMI … but that makes me confused about something else which I will try later to formulate because this is sort of interesting by itself.

 

[daon2]

Thank you Dr Phil and thank you M. Pillow.

A rudimentary question.

The set of integers (…-3,-2,-1,0,1,2,3…) are found to have several properties: closed under the operations of addition and multiplication, the properties of associativity and commutativity hold, etc … but before discovering these properties one needs something to start with something doesn't one?

When beginning the study of number systems, the natural numbers are introduced as a set N containing at least one member, call it 1 (or 0) and name it the "smallest". Accompanying this set is a special injective function S:N->N, called a successor function and say that x is "smaller" (different from) than S(x) for all x. As a one-side bounded, ordered set, that's really all there is.

There is nothing differentiating the set of natural numbers from the set of non-positive integers at this point. Imposing "enough" structure is what leads to what we know as the natural numbers. If you further insist that S also be a surjective function (every element of the set is the successor to another), you will be stepping in to the "integer" territory. For example, there should be a member -1 such that S(-1)=0. It is not until addition is defined that one can call this element 0 an additive identity.

How much structure you wish to include will change the type of structure completely and classifying them is a chore. The integers end up being what is abstractly called an Euclidean Domain. Essentially it is the "best" a commutative ring can be before becoming a field like the rationals.

So we posit a line marked off in equal units with each specific unit (or is it the mark following each unit) having a name that we have manufactured (one, two, three … and past 12 have a system for naming the increments.)

Is that the “given” before one even begins to define operations and look for properties?

Check out the axioms in a book, or on Wikipedia.

If so, how does one say this as a beginning to the development of the theory of integers? Does one just say, we all know what integers are and what a number line is, and what it means to assign the set of integers to the number line now lets us define operations and discover properties.

The abstract idea lives separate from any materialization of it, as on a number line or in any particular symbolic representation. The integers as you know them may not be how an alien race may know them and yet they are one in the same.

If so, that would be fine, then I could go on to the next thing that confuses me. I ask because mathematics has a way of showing me that what seems obvious is often not.

I am following what each of you have written and have questions (whose answers will hopefully benefit more than myself), but I would like to be sure of my starting point.

Thanks.

 

[Dale10101]

Think check please

Sorry to be such a nudge about this but some of these concepts seem very slippery.

When beginning the study of number systems, the natural numbers are introduced as a set N containing at least one member, call it 1 (or 0) and name it the "smallest". Accompanying this set is a special injective function S:N->N, called a successor function.

So, the concept of a set as a “collection of objects/elements” is the beginning … no further explanation needed, we all know what we mean by a set and an object.

Next you say that the set has at least one member. OK.

Then you say “call it the smallest”. We are able to say that because, I think, along with the fundamental concepts of “set” and “element” is the concept of a ”relation” or “mapping” ...

(those terms are synonymous?, and again, the concept of mapping like that of a set and element is so fundamental that a verbal description and a mutual understanding is all that we can do?)

.... so that having a mutual arbitrary definition of a set, element, and relation/mapping so that we can talk about things, we can invent a means of symbolically defining “order” in a way that accords with what we also intuitively think of when we count, one, then two, then 3, etc. OK, done (Wikipedia http://en.wikipedia.org/wiki/Order_theory).

Knowing what order means on a symbolic level … does that allow us to “recognize” that the set of natural numbers is ordered (by virtue of our arbitrary map the 1 -> 2, 2-> 3, 3 ->4, etc), or does one need to “prove” the set of natural numbers is ordered?

Nuts … is the concept of “order” synonymous with the concept of a “sequence”. Are those concepts fundamental in the same sense as the concepts of a set/element and a relation? Could we have a discussion with an alien that did not understand those three concepts at the least?

But OK, let’s assume that the natural numbers are established with order and the we have a set with at least one element, the smallest, and that we call it “1”.

For specificity let us say we have the set of even natural numbers the smallest of which is 2 the second smallest is 4.
Now, BECAUSE we have a set which is ordered we can introduce the “successor function” which simply points to the next element of a sequence (i.e. an ordered list).

Now that is interesting because when we begin using the successor function it seems to me that we are no longer talking about the contents of a sequence but about the name of where each element of the list is located in the sequence … and that brings me around again to PMI.

"The Principle of Mathematical Induction"

· Let S be a set of positive integers which has the following properties.
o IF: S contains 1
o AND IF: S contains k +1 whatever it contains the positive integer k.
o THEN: S contains all positive integers.

When it is said “If S contains 1”. Are we saying “If S contains the integer 1” or are we saying “If there is first least element in a sequence.”?

In the specific case of even natural numbers that would mean the k = “1” = 2, the first element in the sequence. Similarly, is it true then that when we say talk about “k+1” we are not talking about the result of adding 1 to the contents of the k-th element (2 + 1 = 3,when k=”1”) but the (k+ 1)-th element in the list, i.e. "k+1" = 4 when k="1"=2.

Hmmm … so in that case what PMI is really saying is that if a set is ordered and has a first, smallest element, and if every element of the sequence points to a next element then … what? In the case of positive even natural numbers … that the sequence contains all positive even natural numbers?

(I feel like I am on the border line of understanding something or of watching the mathfish squirt out of the boat.)

Hmmm … PMI seems to be defining the fundamental properties of what makes a sequence a sequence and that by virtue of those properties, all sequences are … hmmm … nested inside of the simplest fundamental sequence … the sequence of natural counting numbers.

This is getting foggy and tenuous… am I lost or going somewhere? Little help please.

 

[daon2]

Sorry to be such a nudge about this but some of these concepts seem very slippery.



So, the concept of a set as a “collection of objects/elements” is the beginning … no further explanation needed, we all know what we mean by a set and an object.

Next you say that the set has at least one member. OK.

Then you say “call it the smallest”. We are able to say that because, I think, along with the fundamental concepts of “set” and “element” is the concept of a ”relation” or “mapping” ...

I am assigning a property to the single element I know belongs to the set. To be rigorous, one would define the smallest element to be the one which is not a successor to any other member of N.

(those terms are synonymous?, and again, the concept of mapping like that of a set and element is so fundamental that a verbal description and a mutual understanding is all that we can do?)

Mapping usually refers to a special relation, namely a function. Relations on a set N are subsets of NxN.

.... so that having a mutual arbitrary definition of a set, element, and relation/mapping so that we can talk about things, we can invent a means of symbolically defining “order” in a way that accords with what we also intuitively think of when we count, one, then two, then 3, etc. OK, done (Wikipedia http://en.wikipedia.org/wiki/Order_theory).

Knowing what order means on a symbolic level … does that allow us to “recognize” that the set of natural numbers is ordered (by virtue of our arbitrary map the 1 -> 2, 2-> 3, 3 ->4, etc), or does one need to “prove” the set of natural numbers is ordered?

The order must be defined. We define less-than to mean x<y if y = S(S(...(S(x))) = S^n(x) for some n>=1. Or without arguable circular reasoning, we might say y is an "eventual successor" of x.

Nuts … is the concept of “order” synonymous with the concept of a “sequence”. Are those concepts fundamental in the same sense as the concepts of a set/element and a relation? Could we have a discussion with an alien that did not understand those three concepts at the least?

Given a sequence, you can define an order in the obvious way. Given (a,b,c,...), a<'c, a<'b, b<'c and so on. The symbol "<" has a definite meaning though, so a different kind of ordering should be emphasized by a different symbol to avoid ambiguity if actual numbers are involved. Also, one should check that the sequence is injective, or else the standard notion of an equivalence relation will not hold, and we will always appreciate the "trichotomy" to be able to compare elements fruitfully.

But OK, let’s assume that the natural numbers are established with order and the we have a set with at least one element, the smallest, and that we call it “1”.

For specificity let us say we have the set of even natural numbers the smallest of which is 2 the second smallest is 4.
Now, BECAUSE we have a set which is ordered we can introduce the “successor function” which simply points to the next element of a sequence (i.e. an ordered list).

Now that is interesting because when we begin using the successor function it seems to me that we are no longer talking about the contents of a sequence but about the name of where each element of the list is located in the sequence … and that brings me around again to PMI.

Yes, as an ordered set which is bounded below, the natural numbers is the same as the even natural numbers.

"The Principle of Mathematical Induction"

· Let S be a set of positive integers which has the following properties.
o IF: S contains 1
o AND IF: S contains k +1 whatever it contains the positive integer k.
o THEN: S contains all positive integers.

When it is said “If S contains 1”. Are we saying “If S contains the integer 1” or are we saying “If there is first least element in a sequence.”?

You can apply induction to any set which is abstractly the same as the natural numbers. You can prove something, say P(n), is true for all even integers greater than or equal to -22 by showing P(-22) is true, and that if n is even at at least -22, P(n) implies P(n+2).

In the specific case of even natural numbers that would mean the k = “1” = 2, the first element in the sequence. Similarly, is it true then that when we say talk about “k+1” we are not talking about the result of adding 1 to the contents of the k-th element (2 + 1 = 3,when k=”1”) but the (k+ 1)-th element in the list, i.e. "k+1" = 4 when k="1"=2.

Hmmm … so in that case what PMI is really saying is that if a set is ordered and has a first, smallest element, and if every element of the sequence points to a next element then … what? In the case of positive even natural numbers … that the sequence contains all positive even natural numbers?

Correct. In my above example, S(2)=4. So for any such set N, you show P(smallest) is true and P(x) implies P(S(x)).

(I feel like I am on the border line of understanding something or of watching the mathfish squirt out of the boat.)

Hmmm … PMI seems to be defining the fundamental properties of what makes a sequence a sequence and that by virtue of those properties, all sequences are … hmmm … nested inside of the simplest fundamental sequence … the sequence of natural counting numbers.

That is the definition of a sequence! A sequence on X is a function f:N->X, and we define x_n to be f(n)!

This is getting foggy and tenuous… am I lost or going somewhere? Little help please.

You seem to understand!

 

[Dale10101]

Thanks

Thank you Daon2 for your explanations. I must digest this a bit. One thing I did not see is that a sequence is only amenable to PMI when you can encode it as a function of n, a set of integers with a least value which in toto must somehow be useful for proving identities ... well, will think about that. Thank you again. Dale