| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 768.1 | | CIMNET::KOLKER | Conan the Librarian | Mon Oct 12 1987 14:31 | 8 |
| re .0
You have successfully proven that every finite subset of the integers
has a greatest element.
What you have *not* proven [and you can't since it is false] is
that an arbitrary subset of the integers has a largest element
|
| 768.2 | does everyone know the proof? | VINO::JMUNZER | | Mon Oct 12 1987 17:12 | 3 |
| But the coins on the table are all heads or all tails.
John
|
| 768.3 | | CIMNET::KOLKER | Conan the Librarian | Mon Oct 12 1987 18:45 | 23 |
| re .2
I think this old saw is used as cautionary tale in applying
mathematical induction carelessly. Let me have a go at it.
Suppose a set of coins has only one member. Then the coins in the
set are all heads or all tails. That is case = 1
Assume it is true for case = n.
Add a new coin to the set. This new coin and an n-1 subset of the
original constitute an n set. Assume wlog they are all heads. The
original n set must have been all heads therefore the n+1 set is
all heads. There fore for all n, the coins are all heads.
Where did this "induction" break down?
Answer below
For n = 2 we cannot assert the new (second coin) has the same side
showing as a proper subset of the remaining coins, for that would
be an empty set.
|
| 768.4 | But this time, it's true! | ZFC::DERAMO | Daniel V. D'Eramo | Mon Oct 12 1987 19:10 | 2 |
| But induction can be used to prove that all positive integers are
interesting. Who remembers that one?
|
| 768.5 | Zorn's Lemma, Axiom of Choice, W O princ., Induct. | TLE::BRETT | | Tue Oct 13 1987 10:03 | 26 |
|
Since the use of induction depends on the well-ordering principle,
it can't be proved by it!
Summary of induction...
Given a proposition, P(x : POSITIVE) -> BOOLEAN, show that P is
true for all x.
The F be the nonempty set of positive integers for which P(x) -> FALSE.
F has some least member (well ordering principle!), say n.
If n = 1, then prove P(1) {first step of an inductive proof}.
If n > 1, then prove P(x-1) => P(x) and, since x-1 is not in F
conclude that x is not also {inductive step}.
Hence conclude that F must be empty.
However, notice that IF the well ordering principle is NOT true,
then there could be sets of positive integers without a least element
and hence it is impossible to select "n" above, and hence induction
doesn't work.
/Bevin
|
| 768.6 | | CIMNET::KOLKER | Conan the Librarian | Tue Oct 13 1987 11:19 | 9 |
| reply to all integers are interesting
proof after line feed:
Suppose there exist uninteresting integers. Then by well ordering
there must be a smallest uninteresting integer. But that is kind
of interesting, I mean really, the whole idea that all the
un-interesting integers have to be larger. Right? The contradiction
carries the day.
|
| 768.7 | Since you can well-order ANY set, | SQM::HALLYB | I sell too soon | Tue Oct 13 1987 12:04 | 2 |
| The same "proof" applies to real and complex numbers,
as well as function spaces and yet larger sets...
|
| 768.8 | | BEING::POSTPISCHIL | Always mount a scratch monkey. | Tue Oct 13 1987 17:02 | 7 |
| Re .7:
Not all sets have a smallest member, such as the set of all real
numbers greater than one.
-- edp
|
| 768.9 | | ZFC::DERAMO | Daniel V. D'Eramo | Tue Oct 13 1987 18:28 | 37 |
| .5>> However, notice that IF the well ordering principle is NOT true,
.5>> then there could be sets of positive integers without a least element
.5>> and hence it is impossible to select "n" above, and hence induction
.5>> doesn't work.
No -- Zorn's lemma, the axiom of choice, the well ordering
principle, apply to arbitrary sets. The well ordering
principle could be false -- for example, there may be no
well ordering of all real numbers -- but even so the set of
positive integers is still well ordered by its "natural"
ordering. The "highly structured" set of positive integers
can be well ordered without having to appeal to Zorn's lemma
or the axiom of choice.
Re .6: That's the proof!
.7>> Since you can well-order ANY set,
.7>> The same "proof" applies to real and complex numbers,
.7>> as well as function spaces and yet larger sets...
Not really. The standard or natural ordering of the
positive integers is a well ordering, and under this
ordering there is no "least" uninteresting positive integer.
But as stated in .7, the reals are not well-ordered under
their natural ordering, and it's not as interesting when
they are well ordered by some hypothetical ordering whose
existence is established by the axiom of choice.
.8>> Re .7:
.8>>
.8>> Not all sets have a smallest member, such as the set of all real
.8>> numbers greater than one.
Right. It is the standard ordering of the reals that
matters, and that is not a well ordering of the reals.
Dan
|
| 768.10 | | TLE::BRETT | | Wed Oct 14 1987 11:03 | 4 |
| I'm intrigued, can you prove that the set of positive integers is
well-ordered by the normal "<" operator without the use of induction?
/Bevin
|
| 768.11 | | CLT::GILBERT | Builder | Wed Oct 14 1987 14:10 | 7 |
| > I'm intrigued, can you prove that the set of positive integers is
> well-ordered by the normal "<" operator without the use of induction?
It's best to just assume the set of positive integers; it is a 'given'
in this problem, and so we shouldn't need to prove (inductively) that
it exists. What's the definition of the normal "<" operator? And do
you have a non-inductive definition of "well-ordered"?
|
| 768.12 | Do you believe in positive integers? | ZFC::DERAMO | Daniel V. D'Eramo | Wed Oct 14 1987 22:18 | 20 |
| .10>> I'm intrigued, can you prove that the set of positive integers is
.10>> well-ordered by the normal "<" operator without the use of induction?
If first order logic is what you prove things in, then the
usual axioms of number theory include an axiom scheme for
induction. So in that sense induction is assumed as a
property of the positive integers. The usual axioms of set
theory are strong enough to define a set [call it Fred] and
operations on that set that make Fred look exactly like what
everyone thinks positive integers are. One can prove
[without the axiom of choice] that the set Fred is well
ordered by the operation Fred-< that looks exactly like the
< of the positive integers. So in that sense, one can prove
that the positive integers are well-ordered by <, and the
proof does not use or assume induction over positive integers.
So in number theory, induction is an assumed property of the
positive integers; in set theory, it can be proven that
these things called positive integers have the property that
things can be proven about them using induction.
|
| 768.13 | some 'usual' definitions: | CHOVAX::YOUNG | Back from the Shadows Again, | Wed Oct 14 1987 22:47 | 44 |
| The 'usual' definition of the Natural Numbers (ie. the positive
integers) is that they are the set (or they are isomorphic to any
set that) conforms to Peanos Postulates:
For a set N: (informally stated)
P1: 1 is in N
P2: If (x) is in N then successor(x) is also in N
P3: If (x) and (y) are in N and ( succ.(x) = succ.(y) )
then ( x = y )
P4: There is no (x) in N such that ( succ.(x) = 1 )
P5: If 1 is in a set P and if the successor of every element
in P is also in P then P is equivilent to N.
( Induction )
The 'usual' definition for the '<' (less than) operator is that
it is a relation over the Natural numbers such that:
If ( a < b ) then
either
successor(a) = b
or
successor(a) < b
The 'usual' definition of the Well-Ordering principle is:
A Set T is Well-Ordered with respect to a relation L
IFF For any subset S of T
Either
S is the empty set
Or
there exists some (x) in S such that for any
other (y) in S ==> x.L.y
( which is to say that S has a least member )
I might also add that one of my number theory texts (Shockley) has
a proof that the Induction Postulate (P5) is equivalent to the
Well-Ordering Principle for < over Natural numbers.
I won't post the proof in case anyone wishes to work it out for
themselves.
-- Barry
|
| 768.14 | first & second order logics... | CHOVAX::YOUNG | Back from the Shadows Again, | Wed Oct 14 1987 22:59 | 16 |
| Re .12:
Actually the Induction Postulate is usualy stated in Second-Order
terms, ie.:
For any set T then T is equivilent to N IFF ...
When your phrasing things in terms of sets as variables, then you
are talking in at least second order logic.
( well actually with a lot of fancy footwork and extra postulates
you can state any second order postulate in first order terms,
but in practice no one ever bothers ).
-- Barry
|
| 768.15 | FOUL! You can't have it both ways, guys | SQM::HALLYB | I sell too soon | Thu Oct 15 1987 13:03 | 23 |
| .7> The same "proof" applies to real and complex numbers,
.7> as well as function spaces and yet larger sets...
.8> Re .7:
.8> Not all sets have a smallest member, such as the set of all real
.8> numbers greater than one.
Not true. Let E be "the set of all real numbers greater than one".
Use the Well Ordering Theorem to well order E. Under this
well-ordering, certainly not the normal "<" ordering, every
subset of E has a least member. That's an interesting number, etc.
DVD's response to this line of reasoning is:
.9> Right. It is the standard ordering of the reals that
.9> matters, and that is not a well ordering of the reals.
Which, while entirely correct, is a matter of his opinion. In fact,
the definition of "interesting" is a matter of opinion, and is the
downfall of this entire line of reasoning even for finite sets of
Mersenne Primes.
John
|
| 768.16 | | TLE::BRETT | | Thu Oct 15 1987 15:06 | 13 |
| Actually, given that the well-ordering theorem can provide SOME
"<" function that well-order's the positive reals, we can easily
construct MANY "<" functions that do (by composing the W-O "<" with
any 1-1, onto function from the positive reals to the positive reals)
and hence we can chose some "<" that makes ANY particular element
of the set of "uninteresting" reals the least member, and hence
(since this is NOT a 'privileged' position in the set) it is BORING
that for some artificially constructed "<", a particular number
is the least in the "uninteresting reals" set. I believe this
breaks the proof for reals. The point about the integer proof is
that the "<" is NOT an artificially created one.
/Bevin
|
| 768.17 | That's an interesting argument | SQM::HALLYB | I sell too soon | Thu Oct 15 1987 16:40 | 9 |
| > The point about the integer proof is that the "<" is NOT an
> artificially created one.
Of course it's artificial. You're just a lot more familiar with it.
Proof by massive harumph-ing is no more valid than any of the various
techniques used by the Spanish Inquisition to coerce the heathens.
John
|
| 768.18 | Were the integers discovered or invented? | ZFC::DERAMO | Daniel V. D'Eramo | Thu Oct 15 1987 20:05 | 20 |
| .17>> > The point about the integer proof is that the "<" is NOT an
.17>> > artificially created one.
.17>>
.17>> Of course it's artificial. You're just a lot more familiar with it.
Aha! A religious comment! "A famous person" (sorry, I
can't remember the source) said something like:
God created the integers, all the rest is man's invention.
A non-mathematician once told me that he "believed" in the
existence of the integers. Many more people feel the
integers exist, somewhere out there, than feel that
function spaces (for example) exist. So statements about
whether or not < is artificial are starting to get personal.
Dan
P.S. The development from .4 to here has been ...
interesting! :-)
|