Author 
Message 
un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Sat Jul 01, 2006 7:59 am Post subject:
Nature of proofs by induction



(Excuse my ignorance if this is a stupid question. I'm still going
through old material in order to get back to the track after a few
years pause.)
I have noticed some uses of proof by induction which I don't feel
comfortable with. Could someone clarify the situation for me?
Proofs are done by first prooving property holds at step 0, next we
prove that if it holds for n then it does hold for n+1 and we conclude
that it holds for all n in N (to provide the skeleton of the
technique).
Now, take a proof, say:
Let [n] = {1,2,...,n} and A a proper subset of [n]. Now for some k < n
there exists bijection f:A>[k]
Proof.
step 0: Clearly this hold for n=0 because [0] does not have proper
subsets
step n> n+: Assume claim holds for n and prove it for n+. Let A be a
proper subset of [n+] (n+ is the successor of n). Let B be the
intersection of A and [n]. If B=[n], then A=B and the claim holds for A
and n+ if we choose k=n.
Assume B is a proper subset of [n]. By the induction hypothesis there
exists k < n and bijection f:b>[k]. If A=B then we have a proof for A.
Assume B =/= A. Now A=B union {n+}. Now mapping g:A>[k+], where
g(i)=f(i) for every i =/= n+ and g(n+) = k+ is a bijection. Because k <
n, then k+ < n+ and hence we have prooved the claim for n+.
Now what I have done is
i) proved step 0 by noticing [0] does not have proper subsets
ii) assumed that if hypothesis holds for n then it holds for n+1
Doesn't the step "hypothesis hold for n" assume that [n] does not have
proper subsets? At least this was the way to prove step 0.
Can we use "property is not defined at 0" on step n even if property is
defined for n? Doesn't the situation change if the property is defined
at, say, 1? 

Back to top 


Brian M. Scott science forum Guru
Joined: 10 May 2005
Posts: 332

Posted: Sat Jul 01, 2006 8:58 am Post subject:
Re: Nature of proofs by induction



On 1 Jul 2006 00:59:54 0700, un student
<un.student@gmail.com> wrote in
<news:1151740794.295303.321760@b68g2000cwa.googlegroups.com>
in alt.math.undergrad:
[...]
Quote:  I have noticed some uses of proof by induction which I don't feel
comfortable with. Could someone clarify the situation for me?
Proofs are done by first prooving property holds at step 0, next we
prove that if it holds for n then it does hold for n+1 and we conclude
that it holds for all n in N (to provide the skeleton of the
technique).

This is one kind of proof by induction; there are others.
Quote:  Now, take a proof, say:
Let [n] = {1,2,...,n} and A a proper subset of [n]. Now for some k < n
there exists bijection f:A>[k]
Proof.
step 0: Clearly this hold for n=0 because [0] does not have proper
subsets
step n> n+: Assume claim holds for n and prove it for n+. Let A be a
proper subset of [n+] (n+ is the successor of n). Let B be the
intersection of A and [n]. If B=[n], then A=B and the claim holds for A
and n+ if we choose k=n.

And the specific bijection from A to [n] is the identity
map.
Quote:  Assume B is a proper subset of [n]. By the induction hypothesis there
exists k < n and bijection f:b>[k]. If A=B then we have a proof for A.
Assume B =/= A. Now A=B union {n+}. Now mapping g:A>[k+], where
g(i)=f(i) for every i =/= n+ and g(n+) = k+ is a bijection. Because k
n, then k+ < n+ and hence we have prooved the claim for n+.

By showing how to construct the desired bijection for any
given proper subset of [n+].
Quote:  Now what I have done is
i) proved step 0 by noticing [0] does not have proper subsets
ii) assumed that if hypothesis holds for n then it holds for n+1

No, absolutely not. You have *proved* that if it holds for
n, then it holds for n+1, which is a completely different
thing.
Quote:  Doesn't the step "hypothesis hold for n" assume that [n] does not have
proper subsets?

No, not in the least. The assumption that the hypothesis
holds for [n] is this, if written out in full:
If A is a proper subset of [n], then for some natural
number k < n there is a bijection f : A > [k].
There is nothing there about whether or not [n] has proper
subsets. Of course when n > 0 it always does.
Quote:  At least this was the way to prove step 0.

But 0 is a very special case.
Quote:  Can we use "property is not defined at 0"

???
The property *is* defined at 0, and what's more, 0 has it:
'if A is a proper subset of [0], then for some natural
number k < 0 there is a bijection f : A > [k]' is a true
statement. Admittedly, it's true for the trivial reason
that [0] has no proper subsets, but it's still true. (It's
a statement of the form 'if P then Q', and such a statement
is automatically true when P is false.)
Quote:  on step n even if property is defined for n? Doesn't the
situation change if the property is defined at, say, 1?

I don't see where you're getting this: nothing in the proof
of (ii) is based on an assumption that [n] has no proper
subsets.
Brian 

Back to top 


un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Sat Jul 01, 2006 9:41 am Post subject:
Re: Nature of proofs by induction



Brian M. Scott wrote:
Quote:  On 1 Jul 2006 00:59:54 0700, un student
un.student@gmail.com> wrote in
Now what I have done is
i) proved step 0 by noticing [0] does not have proper subsets
ii) assumed that if hypothesis holds for n then it holds for n+1
No, absolutely not. You have *proved* that if it holds for
n, then it holds for n+1, which is a completely different
thing.

Yes, this is what I ment. A massive typo.
<...>
Quote:  At least this was the way to prove step 0.
But 0 is a very special case.

Yes, I see that :)
<..>
Quote:  The property *is* defined at 0, and what's more, 0 has it:
'if A is a proper subset of [0], then for some natural
number k < 0 there is a bijection f : A > [k]' is a true
statement. Admittedly, it's true for the trivial reason
that [0] has no proper subsets, but it's still true. (It's
a statement of the form 'if P then Q', and such a statement
is automatically true when P is false.)

Ok, I think I'm getting it. What I "saw" in the proof was something
like:
Let f be function f(n) = n+1 for all n > 0, n in N, and f is not
defined at 0.
Lemma: f is not defined anywhere
Proof. (which is incorrect)
step 0: clearly f is not defined at 0
step n>n+1: by induction hypothesis f is not defined at n. But now
f(n) = f(n1)+1 > f(n+)=f(n)+1 but since f is not defined at n it
can't be defined on n+ neither and hence f is not defined anywhere.
Here I explicitly used the "not defined" when in the previous proof it
was used "implicitly".
I mean, that step 0 was proved by showing A is false (no proper
subsets) and showing that now property B follows N=A>B because
anything follows from false. Now if written out explicitly.
A=[0] has a proper subset
B=Bijection f exists
Because A is false then A>B is true. Let N=A>B, which is true. Now
step n>n+ uses (actually no, but this is how I thought) N to prove the
case for n+. Here
C=[n] has a proper subset
D=Bijection exists
M=C>D
Now we have to proof N>M is true, ie L=(A>B) > (C>D) is true,
correct? Now if n=0, then A>B is same as C>D and hence L is true. If
n>0, then A>B is (still) true and C is true. Now it remains to be
shown that from C one gets D.
If the above reasoning is correct I got it. Looks like I thought A=C,
but actually that is true only when n=0. And if n=0 then C=D and L is
naturally true. One could say that A and B are constants, but C and D
are functions of n and C(0)=A, D(0)=B
Ok, maybe now...
Thank you! 

Back to top 


David C. Ullrich science forum Guru
Joined: 28 Apr 2005
Posts: 2250

Posted: Sat Jul 01, 2006 10:48 am Post subject:
Re: Nature of proofs by induction



On 1 Jul 2006 00:59:54 0700, "un student" <un.student@gmail.com>
wrote:
Quote:  (Excuse my ignorance if this is a stupid question. I'm still going
through old material in order to get back to the track after a few
years pause.)
I have noticed some uses of proof by induction which I don't feel
comfortable with. Could someone clarify the situation for me?
Proofs are done by first prooving property holds at step 0, next we
prove that if it holds for n then it does hold for n+1 and we conclude
that it holds for all n in N (to provide the skeleton of the
technique).
Now, take a proof, say:
Let [n] = {1,2,...,n} and A a proper subset of [n]. Now for some k < n
there exists bijection f:A>[k]
Proof.
step 0: Clearly this hold for n=0 because [0] does not have proper
subsets
step n> n+: Assume claim holds for n and prove it for n+. Let A be a
proper subset of [n+] (n+ is the successor of n). Let B be the
intersection of A and [n]. If B=[n], then A=B and the claim holds for A
and n+ if we choose k=n.
Assume B is a proper subset of [n]. By the induction hypothesis there
exists k < n and bijection f:b>[k]. If A=B then we have a proof for A.
Assume B =/= A. Now A=B union {n+}. Now mapping g:A>[k+], where
g(i)=f(i) for every i =/= n+ and g(n+) = k+ is a bijection. Because k
n, then k+ < n+ and hence we have prooved the claim for n+.
Now what I have done is
i) proved step 0 by noticing [0] does not have proper subsets
ii) assumed that if hypothesis holds for n then it holds for n+1
Doesn't the step "hypothesis hold for n" assume that [n] does not have
proper subsets? At least this was the way to prove step 0.

No. You proved that every proper subset of the empty set has the
required property. The fact that the empty set has no proper
subsets doesn't change that  the details of _how_ you proved
it doesn't change that.
Quote:  Can we use "property is not defined at 0" on step n even if property is
defined for n? Doesn't the situation change if the property is defined
at, say, 1?

Don't know what you mean. The property _is_ defined when n = 0.
************************
David C. Ullrich 

Back to top 


un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Sat Jul 01, 2006 11:03 am Post subject:
Re: Nature of proofs by induction



David C. Ullrich wrote:
Quote:  "un student" <un.student@gmail.com> wrote:
Now what I have done is
i) proved step 0 by noticing [0] does not have proper subsets
ii) assumed that if hypothesis holds for n then it holds for n+1
Doesn't the step "hypothesis hold for n" assume that [n] does not have
proper subsets? At least this was the way to prove step 0.
No. You proved that every proper subset of the empty set has the
required property. The fact that the empty set has no proper
subsets doesn't change that  the details of _how_ you proved
it doesn't change that.

Ah, yes, the techique still works. I didn't see that.
Quote: 
Can we use "property is not defined at 0" on step n even if property is
defined for n? Doesn't the situation change if the property is defined
at, say, 1?
Don't know what you mean. The property _is_ defined when n = 0.

I was not precise enough. Actually I ment that on proof by induction
one first proves that property holds at some point i and then uses this
information to prove that if the property holds at n >= i, then it
holds in n+1. Now, if we prove that the property in question holds in i
using a fact P which only holds in i but no for any m > i, don't we
later, when assuming property holds in n, assume that P holds as well?
Uhh. This is hard to explain (as misunderstandings, which I seem to
have quite a bunch, usually are). Is my text understable? 

Back to top 


G.E. Ivey science forum Guru
Joined: 29 Apr 2005
Posts: 308

Posted: Sat Jul 01, 2006 4:26 pm Post subject:
Re: Nature of proofs by induction



Quote:  (Excuse my ignorance if this is a stupid question.
I'm still going
through old material in order to get back to the
track after a few
years pause.)
I have noticed some uses of proof by induction which
I don't feel
comfortable with. Could someone clarify the situation
for me?
Proofs are done by first prooving property holds at
step 0, next we
prove that if it holds for n then it does hold for
n+1 and we conclude
that it holds for all n in N (to provide the skeleton
of the
technique).
Now, take a proof, say:
Let [n] = {1,2,...,n} and A a proper subset of [n].
Now for some k < n
there exists bijection f:A>[k]
Proof.
step 0: Clearly this hold for n=0 because [0] does
not have proper
subsets
step n> n+: Assume claim holds for n and prove it
for n+. Let A be a
proper subset of [n+] (n+ is the successor of n). Let
B be the
intersection of A and [n]. If B=[n], then A=B and the
claim holds for A
and n+ if we choose k=n.
Assume B is a proper subset of [n]. By the induction
hypothesis there
exists k < n and bijection f:b>[k]. If A=B then we
have a proof for A.
Assume B =/= A. Now A=B union {n+}. Now mapping
g:A>[k+], where
g(i)=f(i) for every i =/= n+ and g(n+) = k+ is a
bijection. Because k
n, then k+ < n+ and hence we have prooved the claim
for n+.
Now what I have done is
i) proved step 0 by noticing [0] does not have
e proper subsets
ii) assumed that if hypothesis holds for n then it
t holds for n+1
Doesn't the step "hypothesis hold for n" assume that
[n] does not have
proper subsets? At least this was the way to prove
step 0.
Can we use "property is not defined at 0" on step n
even if property is
defined for n? Doesn't the situation change if the
property is defined
at, say, 1?

Looks to me like a variation on the "horse of a different color" paradox:
Theorem: In any set of n horses, they must all be of the same color (there is NO "horse of a different color!).
Proof by induction on n: Let A be a set containing exactly one horse. Clearly all horses in the set are of the same color!
Now, assume the statement is true for some n. For a set of n+1 horses. Take one of the horses, call it "a", and remove it from the set. The remaining set has n horses and so they are all of the same color. Now, from the original set of horses, choose a different horse, call it "b", and remove it from the set. Again, since this is a set of n horses, they must be all of the same color. But this set now contains "a", so "a" must be of the same color as all the others. Since "b" was in the orginal set of n when "a" was removed, it is of the same color as all the other horses. Therefore, all horses in the set of n+1 horses must be of the same color. By induction, any set of n horses must have all horses of the same color!
Do you see the error? If n+1= 2, when we remove "a", we have a set containing only 1 horse. Yes, that consists of a single color. When we remove "b" we again have just one horse, of one color. But there are no "other horses". It does not follow that "a" and "b" are of the same color. The argument for going from n to n+1 only works if n is at least 2. We can't go from 1 to 2.
Does your argument for going from n to n+1 work if n= 0? 

Back to top 


un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Sat Jul 01, 2006 5:19 pm Post subject:
Re: Nature of proofs by induction



G.E. Ivey wrote:
Quote: 
Looks to me like a variation on the "horse of a different color" paradox:

A variation...maybe, but not exactly the same.
Quote: 
Theorem: In any set of n horses, they must all be of the same color
(there is NO "horse of a different color!).
...
Do you see the error?

Yes.
Quote:  Does your argument for going from n to n+1 work if n= 0?

I tried to express that if we have a fact P on which we base our proof
on step 0 then, in my opinion, that fact P has to hold for all n or the
proof fails.
If from the fact P we reduce that f(0) holds and P is false at other
f(n), n > 0, is it safe to assume f(n) holds?
Apparently it is but I don't see why... Anyway, I'm off for vacation
now :)
Thanks to all! 

Back to top 


Brian M. Scott science forum Guru
Joined: 10 May 2005
Posts: 332

Posted: Sat Jul 01, 2006 5:54 pm Post subject:
Re: Nature of proofs by induction



On 1 Jul 2006 04:03:50 0700, un student
<un.student@gmail.com> wrote in
<news:1151751830.497636.6880@j8g2000cwa.googlegroups.com> in
alt.math.undergrad:
[...]
Quote:  I was not precise enough. Actually I ment that on proof by induction
one first proves that property holds at some point i and then uses this
information to prove that if the property holds at n >= i, then it
holds in n+1.

No: the two parts of a proof by induction are completely
independent. It is entirely possible to prove *first* that
if the property holds at some n >= i, then it also holds at
n + 1. In fact, it's easy to find examples in which it's
possible to prove this even though the property *doesn't*
hold at i. As an example, consider the following property
P(n).
P(n): 0 + 1 + 2 + 3 + ... + n = (n^2 + n + 1)/2
Suppose that P(k) is true for some particular k >= 0. Then
0 + 1 + ... + k + (k+1) =
[0 + 1 + ... + k] + (k+1) =
(k^2 + k + 1)/2 + k + 1 (because P(k) is true),
and by elementary algebra
(k^2 + k + 1)/2 + k + 1 =
(k^2 + 3k + 3)/2 =
[(k+1)^2 + (k+1) + 1]/2,
i.e., P(k+1) is true. In other words, P(k) implies P(k+1),
which is exactly what one needs to show in the induction
step.
But P(0) is easily seen to be false, since 0 != 0^2 + 0 + 1.
In fact, P(n) is easily seen to be false for *all* n. Note
first that n^2 + n + 1 = n(n + 1) + 1. Now n and n + 1 are
consecutive integers, so one of them is even, and therefore
the product n(n + 1) is even, n(n + 1) + 1 is odd, and
(n^2 + n + 1)/2 = [n(n + 1) + 1]/2 isn't an integer. But
the sum 0 + 1 + ... + n obviously is an integer.
Quote:  Now, if we prove that the property in question holds in i
using a fact P which only holds in i but no for any m
i, don't we later, when assuming property holds in n,
assume that P holds as well?

No. Once again, the two parts of the proof are completely
independent of each other.
[...]
Brian 

Back to top 


Brian M. Scott science forum Guru
Joined: 10 May 2005
Posts: 332

Posted: Sat Jul 01, 2006 5:58 pm Post subject:
Re: Nature of proofs by induction



On 1 Jul 2006 10:19:24 0700, un student
<un.student@gmail.com> wrote in
<news:1151774364.101065.197710@b68g2000cwa.googlegroups.com>
in alt.math.undergrad:
[...]
Quote:  If from the fact P we [d]educe that f(0) holds and P is false at other
f(n), n > 0, is it safe to assume f(n) holds?

Sure, because it's a conditional assumption. You're not in
fact asserting that f(n) holds. You're temporarily assuming
this to see what consequences it would have. In particular,
you want to know that f(n+1) is one of those consequences.
To put it a bit differently, you're proving f(n) > f(n+1);
the most straightforward way to do this is to assume for the
sake of argument that f(n) is true, and try to deduce
f(n+1). If you succeed, you've proved f(n) > f(n+1), but
you still have no idea whether f(n) is actually true or not.
[...]
Brian 

Back to top 


David C. Ullrich science forum Guru
Joined: 28 Apr 2005
Posts: 2250

Posted: Sun Jul 02, 2006 11:45 am Post subject:
Re: Nature of proofs by induction



On 1 Jul 2006 04:03:50 0700, "un student" <un.student@gmail.com>
wrote:
Quote:  David C. Ullrich wrote:
"un student" <un.student@gmail.com> wrote:
Now what I have done is
i) proved step 0 by noticing [0] does not have proper subsets
ii) assumed that if hypothesis holds for n then it holds for n+1
Doesn't the step "hypothesis hold for n" assume that [n] does not have
proper subsets? At least this was the way to prove step 0.
No. You proved that every proper subset of the empty set has the
required property. The fact that the empty set has no proper
subsets doesn't change that  the details of _how_ you proved
it doesn't change that.
Ah, yes, the techique still works. I didn't see that.
Can we use "property is not defined at 0" on step n even if property is
defined for n? Doesn't the situation change if the property is defined
at, say, 1?
Don't know what you mean. The property _is_ defined when n = 0.
I was not precise enough. Actually I ment that on proof by induction
one first proves that property holds at some point i and then uses this
information to prove that if the property holds at n >= i, then it
holds in n+1. Now, if we prove that the property in question holds in i
using a fact P which only holds in i but no for any m > i, don't we
later, when assuming property holds in n, assume that P holds as well?
Uhh. This is hard to explain (as misunderstandings, which I seem to
have quite a bunch, usually are). Is my text understable?

Yes, your question is understandable. It's already been answered
several times, including once by me! You should try understanding
the replies instead of repeating the question:
If you prove that the property holds when n = 0 and then
show that it holds at n + 1 assuming it holds at n then
you're done. Details about _how_ you proved it holds at
n = 0 are irrelevant.
************************
David C. Ullrich 

Back to top 


un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Tue Jul 11, 2006 9:33 am Post subject:
Re: Nature of proofs by induction



Brian M. Scott wrote:
Quote:  On 1 Jul 2006 04:03:50 0700, un student
No: the two parts of a proof by induction are completely
independent. It is entirely possible to prove *first* that
if the property holds at some n >= i, then it also holds at
n + 1. In fact, it's easy to find examples in which it's

Ok, after thinking for a while I figured that out. It looks that I have
made mistakes on my proofs. I have used the assumptions on step 0 at
step n>n+1 which I shouldn't have. Luckily I started to doubt my work,
this kind of misunderstanding is quite fatal one and hard to spot...
Thanks to all again! 

Back to top 


Google


Back to top 



The time now is Sun Oct 23, 2011 6:21 am  All times are GMT

