# Don't understand a principle from Beardon, Algebra and Geometery

1. Aug 11, 2014

### PcumP_Ravenclaw

Hi all,

I Dont understand a principle from beardon, Algebra and Geometery chapter 2 real numbers...
In the principle of Induction what is 'm'? and what is 'm+1'? are m elements of A how can m+1 also be an element of A?? if A is a subset of natural numbers how it be all natural numbers in the end??

Thx..

2. Aug 11, 2014

### PcumP_Ravenclaw

Please also explain what the above means?? How are n and m related?? thx..

3. Aug 11, 2014

P(n) means you have a sequence of statements indexed on n: P(1), P(2), P(3), ...
The statement means this:
If you know that P(1) (the first statement) is true, and that
if it is always true that whenever one of the statements P(m) is true, for any arbitrary integer, it follows that P(m+1) (the next statement after P(m)) is also true, then P(n) is true for all integers n.

As a very trivial example, suppose that we want to show P(n) is true, where
P(n) is the statement
$$n^2 \ge 2n-1 \text{ for } n \ge 1$$

First we check that P(1) happens to be true: to do this you need to show that $1^2 \ge 2 \cdot 1 - 1$: since $1 \ge 1$ is true, P(1) is true.

Now assume that for some $m \ge 1$ the statement P(m) is true, so we know that
$$m^2 \ge 2m - 1$$

The next step is to verify that this means $(m+1)^2 \ge 2(m+1) - 1$

There are several ways to do the work for this example - what follows is only one. Note that
$2(m+1) - 1 = 2m + 1$, so
\begin{align*} (m+1)^2 - \left(2(m+1)-1\right) & = (m+1)^2 - \left(2m+1 \right) \\ & = \left(m^2 + 2m + 1\right) - (2m + 1) \\ & = m^2 > 0 \end{align*}
since $m \ge 1$, so that we have

$$(m+1)^2 \ge 2(m+1) - 1$$

and P(m+1) is true.

4. Aug 11, 2014

### pasmith

We don't know what A is. All we know is that it is a subset of the natural numbers which satisfies certain properties (namely that $1 \in A$ and that for every natural number $m$, if $m \in A$ then the natural number $m + 1 \in A$ also).

It happens that $\mathbb{N}$ is a subset of the natural numbers which satisfies those properties, and the point of the proposition is that $\mathbb{N}$ is the only subset of $\mathbb{N}$ which satisfies those properties.

5. Aug 11, 2014

### PcumP_Ravenclaw

m is a value between 1 and n? and isn't m+1 same as n?

6. Aug 11, 2014

### PcumP_Ravenclaw

Sorry guys i still have some confusion!! In the above proof, why is the author bringing in B? what does " b − 1 ≥ 1 (that is, b − 1 ∈ N). As b is the
smallest element in B, it follows that b − 1 / ∈ B, and hence that b − 1 ∈ A. But
then, by our hypothesis, (b − 1) + 1 ∈ A, so that b ∈ A." mean?
how does " b − 1 ≥ 1 (that is, b − 1 ∈ N)." ???
thx...

7. Aug 11, 2014

### HallsofIvy

That's the whole point! That is a contradiction which shows that set B cannot be non-empty. Since B is empty, there is NO upper bound to A.

8. Aug 11, 2014

### PcumP_Ravenclaw

what do you mean by upper bound of A?? A is assumed to be all of Natural numbers right? if B is a subset of A then is B a finite set?

9. Aug 12, 2014

### HallsofIvy

No, you are completely misreading this. The conclusion of the theorem is that A is the set of all natural numbers, that is NOT an assumption.

(And it is certainly NOT true that any subset of N must be finite!)

10. Aug 13, 2014

### PcumP_Ravenclaw

why is it that when m+1 is an element of A then all of elements in A become Natural numbers? what is the reason behind m+1? and why must 1 be an element of A always as the initial condition?

11. Aug 13, 2014

Think this way: you start by establishing that there is a single integer in the set A - as set forth here it is the integer 1.
The next part says (paraphrasing here) "anytime some integer m whatever it may be, is in the set, we can conclude that the next integer, m+1, is also in the set"

So, when you know that 1 is in A, the second portion tells you that 2 has to be in A. But then 3 has to be in A, and 4, and ..., so you have that A contains all positive integers.

Why does 1 have to be the initial condition?
Actually it doesn't. That is typically the setup for the first exposition of this topic, but there are situations where other integers are in the "initial condition" part (as you call it). The common idea with that: whatever the setting, there has to be a first case that is known to be true - sometimes that first case corresponds to n = 1, sometimes to other integers.

12. Aug 13, 2014

### PcumP_Ravenclaw

Hey statdad, can you prove to me if possible, how we can just say " conclude that the next integer, m+1, is also in the set"?

The proof from the book is given below for your reference but I dont understand

13. Aug 13, 2014

As in the example I worked through, you have to follow this pattern:
a) Verify that the first statement (P(1) in the presentation above) is true - this shows that $1 \in A$ and you know A is not the empty set.
b) You have to PROVE (verify) the statements have this condition: for any integer m with P(m) true, so $m \in A$, it follows (from your proof) that P(m+1) is true, so that $m+1 \in A$. We don't automatically conclude it, we have to demonstrate that it is true.

In the proof outline you provide:
a) A and B are, by the nature of the definition of B, disjoint - no elements in common.
b) The proof is by contradiction, so since the goal is to show $B = \emptyset$ we assume B is not empty; if it isn't empty it must have a least element, which we'll call $b$
c) We know $1 \in A$, and since A, B, are disjoint, this means $b \ge 2$.
(I think this next part could have been worded better in the proof.) The stated language is "... so that $b - 1 \ge 1$ (that is, $b - 1 \notin B$)" : The idea here is simple: b is the smallest element of B, so anything smaller is not in B, therefore $b - 1 \in A$.

So, to this point, we have the following ideas
- A, B are disjoint, and $A \cup B = N$
- A has this property: if some integer $m \in A$ then we know $m+1 \in A$
- The integer $b - 1 \in A$ (from the final line in the previous paragraph)

Now use the final two bullets together: $b - 1$ is an integer element of A (final bullet point) so we know that $(b-1) + 1 = b \in A$ (using the next to last bullet point)

This is where the contradiction apears.
First, A, B are disjoint, because of how B was defined.
Second, $b \in B$ (it was defined as the smallest element of B)
Third, Properties of A led us to conclude that it is also the case that $b \in A$

If A, B are disjoint, they cannot have an element in common, yet we just found an integer b that is in both of them.

What caused the contradiction to occur? The assumption that $B \ne \emptyset$. The only way to avoid the contradiction is to realize that $B = \emptyset$ has to be true, and if that is the case then since $A \cup B = n$ it has to be true that $A = N$.