|
|
| Author |
Message |
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
 Posted: Sun May 21, 2006 8:13 am Post subject:
Induction
|
|
|
Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
i) 0 has the property Q, Q(0).
ii) if x in T has the property Q then the successor of x, S(x), has the
property Q, Q(S(x)).
Then property Q holds for every element in T.
Now, if T is infinite, does this mean that all elements in the infinite
set T has the property Q or that for every finite subset T_m = {x | x <
m, x in T}, m in N+, all elements x in T_m has the property Q? |
|
| Back to top |
|
 |
William Elliot
science forum Guru
Joined: 24 Mar 2005
Posts: 1906
|
| Posted: Sun May 21, 2006 9:59 am Post subject:
Re: Induction
|
|
|
On Sun, 21 May 2006, un student wrote:
| Quote: | Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
Then T is order isomorphic to N, the integers or an initial segment |
thereof and all that you mumble below is correct.
| Quote: | i) 0 has the property Q, Q(0).
ii) if x in T has the property Q then the successor of x, S(x), has the
property Q, Q(S(x)).
Then property Q holds for every element in T.
Now, if T is infinite, does this mean that all elements in the infinite
set T has the property Q or that for every finite subset T_m = {x | x
m, x in T}, m in N+, all elements x in T_m has the property Q?
Yes, both. Exericse: show that the two alternatives are equivalent using |
only the fact that T is order isomorphic to N. |
|
| Back to top |
|
|
cody.roux@gmail.com
science forum beginner
Joined: 30 Apr 2006
Posts: 34
|
| Posted: Sun May 21, 2006 10:23 am Post subject:
Re: Induction
|
|
|
un student a écrit :
| Quote: | Now, if T is infinite, does this mean that all elements in the infinite
set T has the property Q or that for every finite subset T_m = {x | x
m, x in T}, m in N+, all elements x in T_m has the property Q?
|
I'm not sure what "m" means in this context. The (meta)theorem proves
that _all_ elements in T satisfy Q:
Let x be the smallest element not satisfying Q. x is non zero, so
there must be a smaller element. The immediate predecessor satisfies Q,
therefore x satisfies Q. Contradition:
There is no smallest element in the subset of elements that do not
satisfy Q, therefore Q is empty. |
|
| Back to top |
|
|
David C. Ullrich
science forum Guru
Joined: 28 Apr 2005
Posts: 2250
|
| Posted: Sun May 21, 2006 12:07 pm Post subject:
Re: Induction
|
|
|
On 21 May 2006 01:13:53 -0700, "un student" <un.student@gmail.com>
wrote:
| Quote: | Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
i) 0 has the property Q, Q(0).
ii) if x in T has the property Q then the successor of x, S(x), has the
property Q, Q(S(x)).
Then property Q holds for every element in T.
Now, if T is infinite, does this mean that all elements in the infinite
set T has the property Q
|
Uh, yes. If you've proved that every element of T has property
Q then it follows that every element of T has property Q.
| Quote: | or that for every finite subset T_m = {x | x
m, x in T}, m in N+, all elements x in T_m has the property Q?
|
************************
David C. Ullrich |
|
| Back to top |
|
|
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
| Posted: Sun May 21, 2006 1:37 pm Post subject:
Re: Induction
|
|
|
David C. Ullrich wrote:
| Quote: | On 21 May 2006 01:13:53 -0700, "un student" <un.student@gmail.com
wrote:
Now, if T is infinite, does this mean that all elements in the infinite
set T has the property Q
Uh, yes. If you've proved that every element of T has property
Q then it follows that every element of T has property Q.
|
But didn't I prove it for every finite subset T_m, not for T? I know
this might sound stupid but I'm having problems understanding the
difference between "finite but arbitrary large" and "infinite".
Take arbitrary finite subset A of N+. Now for every A, S_A sum x in A
is finite but sum x in N+ is infinite...?
Maybe I'm mixing the "value" of x in T and the cardinality of T?
| Quote: |
or that for every finite subset T_m = {x | x
m, x in T}, m in N+, all elements x in T_m has the property Q? |
|
|
| Back to top |
|
|
Brian M. Scott
science forum Guru
Joined: 10 May 2005
Posts: 332
|
| Posted: Sun May 21, 2006 4:53 pm Post subject:
Re: Induction
|
|
|
On 21 May 2006 01:13:53 -0700, un student
<un.student@gmail.com> wrote in
<news:1148199233.102187.119620@j33g2000cwa.googlegroups.com>
in alt.math.undergrad:
| Quote: | Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
i) 0 has the property Q, Q(0).
ii) if x in T has the property Q then the successor of x, S(x), has the
property Q, Q(S(x)).
Then property Q holds for every element in T.
|
Yes, and here's why. Let B = {t in T : ~Q(t)}, the set of
elements of T that don't have property Q. If B is
non-empty, then it has a smallest element, b, in the
well-ordering of T. Since 0 has the property Q, clearly b
is not 0, and therefore b = S(t) for some t in T. But t < b
(where I use '<' for the well-ordering on T), and b was the
<-minimal element of B, so t is not in B, and therefore
Q(t). But then (ii) implies Q(b), a contradiction. It
follows that B must be empty, i.e., that Q(t) for each t in
T.
| Quote: | Now, if T is infinite, does this mean that all elements in
the infinite set T has the property Q [...]
|
Yes: see above.
Brian |
|
| Back to top |
|
|
Jim Heckman
science forum Guru Wannabe
Joined: 28 Apr 2005
Posts: 121
|
| Posted: Mon May 22, 2006 8:23 am Post subject:
Re: Induction
|
|
|
On 21-May-2006, "un student" <un.student@gmail.com>
wrote in message <1148199233.102187.119620@j33g2000cwa.googlegroups.com>:
| Quote: | Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
i) 0 has the property Q, Q(0).
ii) if x in T has the property Q then the successor of x, S(x), has the
property Q, Q(S(x)).
Then property Q holds for every element in T.
Now, if T is infinite, does this mean that all elements in the infinite
set T has the property Q or that for every finite subset T_m = {x | x
m, x in T}, m in N+, all elements x in T_m has the property Q?
|
There is no such T. Any well-ordered set all of whose elements
except 0 have an immediate predecessor is finite.
--
Jim Heckman |
|
| Back to top |
|
|
Jim Heckman
science forum Guru Wannabe
Joined: 28 Apr 2005
Posts: 121
|
| Posted: Mon May 22, 2006 8:42 am Post subject:
Re: Induction
|
|
|
On 22-May-2006, "Jim Heckman" <wnzrfeurpxzna@lnubb.pbz.invalid>
wrote in message <1272t7npavnlbc1@corp.supernews.com>:
| Quote: | On 21-May-2006, "un student" <un.student@gmail.com
wrote in message <1148199233.102187.119620@j33g2000cwa.googlegroups.com>:
Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
i) 0 has the property Q, Q(0).
ii) if x in T has the property Q then the successor of x, S(x), has the
property Q, Q(S(x)).
Then property Q holds for every element in T.
Now, if T is infinite, does this mean that all elements in the infinite
set T has the property Q or that for every finite subset T_m = {x | x
m, x in T}, m in N+, all elements x in T_m has the property Q?
There is no such T. Any well-ordered set all of whose elements
except 0 have an immediate predecessor is finite.
|
D'oh. Except for sets order-isomorphic to omega, of course. But
then it's just a question of ordinary mathematical induction.
--
Jim Heckman |
|
| Back to top |
|
|
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
| Posted: Mon May 22, 2006 9:42 am Post subject:
Re: Induction
|
|
|
Jim Heckman wrote:
| Quote: | On 22-May-2006, "Jim Heckman" <wnzrfeurpxzna@lnubb.pbz.invalid
On 21-May-2006, "un student" <un.student@gmail.com
Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
..
Now, if T is infinite, does this mean that all elements in the infinite
set T has the property Q or that for every finite subset T_m = {x | x
m, x in T}, m in N+, all elements x in T_m has the property Q?
There is no such T. Any well-ordered set all of whose elements
except 0 have an immediate predecessor is finite.
|
I see, never thought about that. What if we drop "immediate
predecessor" and state that every element has exactly one successor?
Would it change the situation?
Does the induction principle need the "immediate predecessor" in order
to work? Induction principle seems like an easy way to proove things
for finite sets, but I don't understand how to extend it to infinite
sets. (or can it be extended?)
| Quote: | D'oh. Except for sets order-isomorphic to omega, of course. But
then it's just a question of ordinary mathematical induction.
|
Emh, ok, I take your word for it  (don't have a clue what
"order-isomorphic to omega" means...) |
|
| Back to top |
|
|
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
| Posted: Mon May 22, 2006 9:50 am Post subject:
Re: Induction
|
|
|
Brian M. Scott wrote:
| Quote: | On 21 May 2006 01:13:53 -0700, un student
Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
i) 0 has the property Q, Q(0).
ii) if x in T has the property Q then the successor of x, S(x), has the
property Q, Q(S(x)).
Then property Q holds for every element in T.
Yes, and here's why. Let B = {t in T : ~Q(t)}, the set of
|
Actually I made this proof before the original post but somehow felt
unsure about it. Don't it have an hidden assumption that induction
principle indeed works if T is infinite?
Or am I missing something very elementary here?
| Quote: | elements of T that don't have property Q. If B is
non-empty, then it has a smallest element, b, in the
well-ordering of T. Since 0 has the property Q, clearly b
is not 0, and therefore b = S(t) for some t in T. But t < b
|
Here "for some t in T" suggests that we are working with finite
sets...?
| Quote: | (where I use '<' for the well-ordering on T), and b was the
-minimal element of B, so t is not in B, and therefore
Q(t). But then (ii) implies Q(b), a contradiction. It
follows that B must be empty, i.e., that Q(t) for each t in
T.
Now, if T is infinite, does this mean that all elements in
the infinite set T has the property Q [...]
Yes: see above.
|
This gets pretty abstract and difficult... |
|
| Back to top |
|
|
William Elliot
science forum Guru
Joined: 24 Mar 2005
Posts: 1906
|
| Posted: Mon May 22, 2006 10:17 am Post subject:
Re: Induction
|
|
|
On Mon, 22 May 2006, un student wrote:
| Quote: | Jim Heckman wrote:
D'oh. Except for sets order-isomorphic to omega, of course. But
then it's just a question of ordinary mathematical induction.
Emh, ok, I take your word for it (don't have a clue what
"order-isomorphic to omega" means...)
f:X -> Y is an order isomorphism when |
f surjection, X,Y (partially) ordered sets and
for all x,y in X, (x <= y iff f(x) <= f(y)).
Exercise: order ismorphisms are bijections
(even when between partially ordered sets). |
|
| Back to top |
|
|
David C. Ullrich
science forum Guru
Joined: 28 Apr 2005
Posts: 2250
|
| Posted: Mon May 22, 2006 10:57 am Post subject:
Re: Induction
|
|
|
On 22 May 2006 02:50:37 -0700, "un student" <un.student@gmail.com>
wrote:
| Quote: | Brian M. Scott wrote:
On 21 May 2006 01:13:53 -0700, un student
Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
i) 0 has the property Q, Q(0).
ii) if x in T has the property Q then the successor of x, S(x), has the
property Q, Q(S(x)).
Then property Q holds for every element in T.
Yes, and here's why. Let B = {t in T : ~Q(t)}, the set of
Actually I made this proof before the original post but somehow felt
unsure about it. Don't it have an hidden assumption that induction
principle indeed works if T is infinite?
Or am I missing something very elementary here?
elements of T that don't have property Q. If B is
non-empty, then it has a smallest element, b, in the
well-ordering of T. Since 0 has the property Q, clearly b
is not 0, and therefore b = S(t) for some t in T. But t < b
Here "for some t in T" suggests that we are working with finite
sets...?
|
??? Why do you think that?
| Quote: | (where I use '<' for the well-ordering on T), and b was the
-minimal element of B, so t is not in B, and therefore
Q(t). But then (ii) implies Q(b), a contradiction. It
follows that B must be empty, i.e., that Q(t) for each t in
T.
Now, if T is infinite, does this mean that all elements in
the infinite set T has the property Q [...]
Yes: see above.
This gets pretty abstract and difficult...
|
Not difficult at all - there's just something basic you're
seriously misunderstanding. Hence the question above.
************************
David C. Ullrich |
|
| Back to top |
|
|
David C. Ullrich
science forum Guru
Joined: 28 Apr 2005
Posts: 2250
|
| Posted: Mon May 22, 2006 11:07 am Post subject:
Re: Induction
|
|
|
On 22 May 2006 02:42:08 -0700, "un student" <un.student@gmail.com>
wrote:
| Quote: | Jim Heckman wrote:
On 22-May-2006, "Jim Heckman" <wnzrfeurpxzna@lnubb.pbz.invalid
On 21-May-2006, "un student" <un.student@gmail.com
Take well-ordered set T which has smallest element 0. Let T have the
additional property that all elements in it, expect 0, have immediate
predecessor. If Q is a property that
..
Now, if T is infinite, does this mean that all elements in the infinite
set T has the property Q or that for every finite subset T_m = {x | x
m, x in T}, m in N+, all elements x in T_m has the property Q?
There is no such T. Any well-ordered set all of whose elements
except 0 have an immediate predecessor is finite.
I see, never thought about that.
|
It's not true. Also not relevant.
| Quote: | What if we drop "immediate
predecessor" and state that every element has exactly one successor?
Would it change the situation?
Does the induction principle need the "immediate predecessor" in order
to work?
|
For induction _in_ the form that it's being stated and used
here yes, we need that every element have an immediate predecessor.
There are other ways of formulating induction that do not require
this, but we should start by getting this version straight.
| Quote: | Induction principle seems like an easy way to proove things
for finite sets, but I don't understand how to extend it to infinite
sets. (or can it be extended?)
|
Nobody has any idea where you get the idea that something
here only works for finite sets.
Look. We're given that T is well-ordered, and that every
element of T other than the smallest element 0 has an
immediate predecessor. That says that for every x in T
except for x = 0 there exists y in T such that x = S(y),
where S(y) denotes the successor of y.
We're also given that 0 has property P, and that
P(y) implies P(S(y)) (that is, if y has property
P then S(y) has property P.) It follows that
every element of T has property P.
Proof: Let A be the set of elements of T which do
not have property P. We need to show that A is
empty. So we assume that A is not empty, and derive
a contradiction.
Now since A is nonempty and T is well-ordered
A has a smallest element. Say x is the smallest
element of A. There are two possibilities,
x = 0 or x > 0.
But x = 0 is impossible: x is in A, so x does
not have property P, but we're given that 0
_does_ have property P. So x is not equal to 0.
So x > 0. Then by assumption there exists y with
x = S(y). This implies that y < x. Since x is the
smallest element of A, y is not an element of A.
Since y is not an element of A, y has property P.
But now this implies that x also has property P,
since x = S(y). Which contradicts the fact that
x is an element of A.
QED.
There's the proof. Nothing there has anything at
all to do with any set being finite.
| Quote: | D'oh. Except for sets order-isomorphic to omega, of course. But
then it's just a question of ordinary mathematical induction.
Emh, ok, I take your word for it (don't have a clue what
"order-isomorphic to omega" means...)
|
************************
David C. Ullrich |
|
| Back to top |
|
|
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
| Posted: Mon May 22, 2006 12:58 pm Post subject:
Re: Induction
|
|
|
David C. Ullrich wrote:
| Quote: | Nobody has any idea where you get the idea that something
here only works for finite sets.
|
Gosh, it was a stupid stupid "misthought" (and no, I'm not telling
where idea came from ... I just completely mixed two separate things
in one proof I saw). I guess its time for vacation... |
|
| Back to top |
|
|
David C. Ullrich
science forum Guru
Joined: 28 Apr 2005
Posts: 2250
|
| Posted: Tue May 23, 2006 9:19 am Post subject:
Re: Induction
|
|
|
On 22 May 2006 05:58:29 -0700, "un student" <un.student@gmail.com>
wrote:
| Quote: | David C. Ullrich wrote:
Nobody has any idea where you get the idea that something
here only works for finite sets.
Gosh, it was a stupid stupid "misthought" (and no, I'm not telling
where idea came from ... I just completely mixed two separate things
in one proof I saw). I guess its time for vacation...
|
We all know the feeling. I guess this means it's all straight
now, fine.
************************
David C. Ullrich |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Fri Jan 09, 2009 12:09 am | All times are GMT
|
|
Bankruptcy | Mobile Phones | Bóle kręgosłupa | Loans | Mortgages
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Undergraduate
