Proof by mathematical induction

[Korisnik]

I'm not sure if I'm posting in the right subforum because there is one about proofs, but it requires the question not to be homework-like, but I also need an explanation...

Homework Statement

Prove by mathematical induction:
Let m be the smallest element of A\subseteq\mathbb{N}. If A contains k+1 whenever it contains a natural number k, then A=\left\{n\in\mathbb{N}:n\geq m\right\}.

Now, what I don't understand here is how is this related to mathematical induction. I get some parts and my friend "slipped" me a clue so I'm afraid I couldn't understand it on my own... So if someone also knows where I could find more examples of mathematical induction of this kind, I'd be very grateful.

Homework Equations

Axiom of mathematical induction (which allows us to conclude, from some properties of subset M\subseteq\mathbb{N}, that M=\mathbb{N}):

Let M be a subset of a set of natural numbers \mathbb{N}.
Let's assume that M has these properties:
1) 1\in M,
2) if n\in M then so is n+1\in M.
Conclusion: M=\mathbb{N}.

The Attempt at a Solution

Now 10 questions before this one were just some 1+2+\dots+n=\frac{n}{2}(1+n) easy problems which I solved using the method: 1) check the base of the induction (first element in the sequence, in this case n=1), then (2) understand that (1+2+\dots+n)+(n+1)=\left[\frac{n}{2}(1+n)\right]+(n+1), and last - check if the result is the same for n+1, so:\left[\frac{n}{2}(1+n)\right]+(n+1)=\frac{n+1}{2}(1+(n+1)). (I know that the second step is just replacing the variable's name, but I skip that since this is a faster way.)

In the original problem, however, I cannot identify the pattern. My best *guess* is that the first step would be 1) k=m, because that's the first element of set A. So it's trivially true that k\in A since it's its first element. The second step would be 2) k\geq m, because if it's true for n, then it's true for k: A=\left\{k\in\mathbb{N}:k\geq m\right\}. Since it's true for any k, by the definition "it's true for k+1 whenever it's true for k", it's true for k+1: A=\left\{k+1\in\mathbb{N}:k+1\geq m\right\}.

So can someone explain what exactly is mathematical induction in this problem, and how to solve the original problem.

(I think mathematical induction is (by axiom) finding the conditions to support that *whatever* is true for \mathbb{N}, except if defined otherwise (for example, prove for n\geq4).)

 

[HallsofIvy]

I'm not sure if I'm posting in the right subforum because there is one about proofs, but it requires the question not to be homework-like, but I also need an explanation...

Homework Statement

Prove by mathematical induction:
Let m be the smallest element of A\subseteq\mathbb{N}. If A contains k+1 whenever it contains a natural number k, then A=\left\{n\in\mathbb{N}:n\geq m\right\}.

Now, what I don't understand here is how is this related to mathematical induction.

It says "A contains k+ 1 whenever it contains A". That's what induction is all about. However, the way you have stated it, the theorem is NOT true. For example, the set A= {1/2, 3/2, 5/2, ...} satisfies all the hypotheses but does NOT contain all natural numbers. The condition "whenever it contains a natural number k, it contains k+ 1" is vacuously true if A contains NO natural numbers. You must add the condition that A contains at least one natural number. (Or that A is a subset of the natural numbers which you don't say.)

There are several ways to do this but the most direct use of induction is this: First let B be the set of all natural numbers in A (in order to ignore all "non"natural numbers that might be in A). Call the smallest natural number in A, "m". (Since A has a smallest element, it must have a smallest natural number. Then m is also the smallest natural number in B. Construct a set C such that C contains natural number n if and only if B contains n+ m- 1. Since B contains m, C contains 1. If C contain natural number i, then B contains natural number i+ m- 1. By the condition that "if A contain k it also contains k+ 1", if B contains i+ m- 1, it also contains i+ m so that C contains i+ 1. By induction C is the set of all natural numbers. Now use the one-to-one and onto functions that have been defined between A and B and between B and C to arrive at the conclusion.

I get some parts and my friend "slipped" me a clue so I'm afraid I couldn't understand it on my own... So if someone also knows where I could find more examples of mathematical induction of this kind, I'd be very grateful.

Homework Equations

Axiom of mathematical induction (which allows us to conclude, from some properties of subset M\subseteq\mathbb{N}, that M=\mathbb{N}):

Let M be a subset of a set of natural numbers \mathbb{N}.
Let's assume that M has these properties:
1) 1\in M,
2) if n\in M then so is n+1\in M.
Conclusion: M=\mathbb{N}.

The Attempt at a Solution

Now 10 questions before this one were just some 1+2+\dots+n=\frac{n}{2}(1+n) easy problems which I solved using the method: 1) check the base of the induction (first element in the sequence, in this case n=1), then (2) understand that (1+2+\dots+n)+(n+1)=\left[\frac{n}{2}(1+n)\right]+(n+1), and last - check if the result is the same for n+1, so:\left[\frac{n}{2}(1+n)\right]+(n+1)=\frac{n+1}{2}(1+(n+1)). (I know that the second step is just replacing the variable's name, but I skip that since this is a faster way.)

In the original problem, however, I cannot identify the pattern. My best *guess* is that the first step would be 1) k=m, because that's the first element of set A. So it's trivially true that k\in A since it's its first element. The second step would be 2) k\geq m, because if it's true for n, then it's true for k: A=\left\{k\in\mathbb{N}:k\geq m\right\}. Since it's true for any k, by the definition "it's true for k+1 whenever it's true for k", it's true for k+1: A=\left\{k+1\in\mathbb{N}:k+1\geq m\right\}.

So can someone explain what exactly is mathematical induction in this problem, and how to solve the original problem.

(I think mathematical induction is (by axiom) finding the conditions to support that *whatever* is true for \mathbb{N}, except if defined otherwise (for example, prove for n\geq4).)

 

[Korisnik]

It says "A contains k+ 1 whenever it contains A". That's what induction is all about. However, the way you have stated it, the theorem is NOT true. For example, the set A= {1/2, 3/2, 5/2, ...} satisfies all the hypotheses but does NOT contain all natural numbers. The condition "whenever it contains a natural number k, it contains k+ 1" is vacuously true if A contains NO natural numbers. You must add the condition that A contains at least one natural number. (Or that A is a subset of the natural numbers which you don't say.)

I did say this (in bold), I denoted that m is the element of A\subseteq\mathbb{N}, where \mathbb{N} is the set of natural numbers (conventionally). Therefore if m\in A and A\subseteq \mathbb{N}\Rightarrow m\in \mathbb{N}. Therefore A must have a natural number m as the beginning.

 

[Curious3141]

(Or that A is a subset of the natural numbers which you don't say.)

The first line of the problem statement says *exactly* that.

Let m be the smallest element of A\subseteq\mathbb{N}.

 

[Korisnik]

There are several ways to do this but the most direct use of induction is this: First let B be the set of all natural numbers in A (in order to ignore all "non"natural numbers that might be in A). Call the smallest natural number in A, "m". (Since A has a smallest element, it must have a smallest natural number. Then m is also the smallest natural number in B. Construct a set C such that C contains natural number n if and only if B contains n+ m- 1. Since B contains m, C contains 1. If C contain natural number i, then B contains natural number i+ m- 1. By the condition that "if A contain k it also contains k+ 1", if B contains i+ m- 1, it also contains i+ m so that C contains i+ 1. By induction C is the set of all natural numbers. Now use the one-to-one and onto functions that have been defined between A and B and between B and C to arrive at the conclusion.

Ok I don't quite understand this. What you have shown is this:
A=\left\{n\in\mathbb{N}:n\geq m\right\}, then create another set \left(C=\left\{n\in\mathbb{N}\right\}\right)\Leftrightarrow (n+m-1\in A). Now since m is the smallest number, and can be 1 or bigger, m-1 will give a number \geq 0. That number +n, must be a number >0 (at least 1). But I don't understand why it MUST BE 1, because m can be 3. ... And why does m\in B means 1\in C? Is there an easier way, I really want to be able to do this alone, this is the first example after a series of easy questions like 1+2+\dots+n=\frac{n}{2}(1+n)... I'm sorry if I'm asking too much.