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

[PcumP_Ravenclaw]

Hi all,

I Dont understand a principle from beardon, Algebra and Geometery chapter 2 real numbers...
Please answer

The Well-Ordering Principle Any non-empty subset of N has a smallest
member.
This apparently obvious result justifies the use of induction.
The Principle of Induction I Suppose that A ⊂ N, 1 ∈ A, and for every m,
m ∈ A implies that m + 1 ∈ A. Then A = N.

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..

 

[PcumP_Ravenclaw]

This is the set-theoretic version of the (presumably) familar result that if a
statement P(n) about n is true when n = 1, and if the truth of P(m) implies the
truth of P(m + 1), the P(n) is true for all n. Indeed, if we let A be the set of n for which P(n) is true, the two versions are easily seen to be equivalent to each
other.

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

 

[statdad]

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
<br /> n^2 \ge 2n-1 \text{ for } n \ge 1<br />

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
<br /> m^2 \ge 2m - 1<br />

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
<br /> \begin{align*}<br /> (m+1)^2 - \left(2(m+1)-1\right) &amp; = (m+1)^2 - \left(2m+1 \right) \\<br /> &amp; = \left(m^2 + 2m + 1\right) - (2m + 1) \\<br /> &amp; = m^2 &gt; 0<br /> \end{align*}<br />
since m \ge 1, so that we have

<br /> (m+1)^2 \ge 2(m+1) - 1 <br />

and P(m+1) is true.

 

[pasmith]

Hi all,

I Dont understand a principle from beardon, Algebra and Geometery chapter 2 real numbers...
Please answer


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..

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.

 

[PcumP_Ravenclaw]

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

 

[PcumP_Ravenclaw]

The Principle of Induction I Suppose that A ⊂ N, 1 ∈ A, and for every m,
m ∈ A implies that m + 1 ∈ A. Then A = N.

Proof Let B be the set of positive integers that are not in A; thus A ∩ B = ∅
and A ∪ B = N. We want to prove that B = ∅ for then, A = N. Suppose not,
then, by theWell-Ordering Principle, B has a smallest element, say b. As 1 ∈ A
we see that 1 (NOT an element) /∈ B; thus b ≥ 2 so that 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. This is a contradiction
(to A ∩ B = ∅), so that B = ∅, and A = N.

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...

 

[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.

 

[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?

 

[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!)

 

[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?

 

[statdad]

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.

 

[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 don't understand

Proof Let B be the set of positive integers that are not in A; thus A ∩ B = ∅
and A ∪ B = N. We want to prove that B = ∅ for then, A = N. Suppose not,
then, by theWell-Ordering Principle, B has a smallest element, say b. As 1 ∈ A
we see that 1 / ∈ B; thus b ≥ 2 so that 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. This is a contradiction
(to A ∩ B = ∅), so that B = ∅, and A = N.

 

[statdad]

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.