|
|
| Author |
Message |
Jim Heckman
science forum Guru Wannabe
Joined: 28 Apr 2005
Posts: 121
|
 Posted: Thu May 25, 2006 1:25 am Post subject:
Re: Induction
|
|
|
On 22-May-2006, "un student" <un.student@gmail.com>
wrote in message <1148290928.047185.147090@u72g2000cwu.googlegroups.com>:
| 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.
|
[As has been pointed out, the preceding is of course wrong.]
| Quote: | 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?
|
As others have said, that's not really relevant to your situation,
but since you asked...
Yes. The usual formulation of mathematical induction depends on
each element of the relevant set having an immediate predecessor,
and dropping that condition does indeed change the situation. The
simplest counter-example is the ordinal number w+1 =
{0, 1, 2, ... ; w}, that is, the natural numbers plus one more
element tacked on, greater than all its predecessors. (Exercise:
Prove this is a well-ordered set.) Since the element w has no
immediate predecessor, there's no way to 'get' to it via ordinary
induction.
As for exactly one successor, it turns out that every element of a
well-ordered set, except the greatest element if there is one, has
an immediate successor. And of course that successor is unique.
I'm sure you'll eventually learn how to prove this if you're
studying set theory, and in particular well-ordered sets.
| Quote: | 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?)
|
Again as others have made clear, the induction principle works just
fine for infinite sets that happen to be order-isomorphic to the
natural numbers. There is also a generalization called transfinite
induction that can be applied to any well-ordered set. And again
I'm sure you'll eventually learn about this in your study of
well-ordered sets.
| 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...)
|
An order-isomorphism is a bijection that respects order. That is,
if f:A -> B is a bijection between two (partially) ordered sets,
then f is an order-isomorphism iff (a <= b) <-> (f(a) <= f(b)) for
all a in A and all b in B.
And "omega" (w) is just a common set-theoretic notation for the set
of natural numbers {0, 1, 2, ...} in their usual order.
--
Jim Heckman |
|
| Back to top |
|
 |
G.E. Ivey
science forum Guru
Joined: 29 Apr 2005
Posts: 308
|
| Posted: Thu May 25, 2006 11:11 pm Post subject:
Re: Induction
|
|
|
| Quote: | David C. Ullrich wrote:
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?
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?
Let X be a member of T. Then X is a member of some finite subset of T. It's even a member of some "chain" T0, T1,..., X which is what I think you really meant. |
|
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Fri Jan 09, 2009 12:28 am | All times are GMT
|
|
Notebook Deals | Free Advertising | Loans | Online Advertising | Credit Card Debt Consolidation Online
|
|
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
