Re: where is that pdf file about how to write mathematical proofs for dummies?

On Thu, 11 Jun 2009 11:44:57 -0700 (PDT), MoeBlee
<jazzmobe@xxxxxxxxxxx> wrote:

On Jun 10, 8:17 pm, Aatu Koskensilta <aatu.koskensi...@xxxxxx> wrote:
MoeBlee <jazzm...@xxxxxxxxxxx> writes:
Lamport, the author of that paper, claims there is an error in the
proof of Schroder-Bernstein in Kelley's 'General Topology'. That is
basically the same proof as in Halmos's 'Naive Set Theory'. I've
worked through those proofs. I had to fill in missing details, but
I've not seen any error. What error is Lamport referring to?

I have no idea, and have unfortunately lost my copy of _General
Topology_. Perhaps you could produce the proof here for our inspection?

Go to Google Books. Search 'Kelley Schroder Bernstein'. The first
result will be the book. Click on the book cover. You'll be at page 28
of the book, where the proof appears.

By the way, Kelley mentions that proof is credited to Birkhoff &
MacLane. Yet Wikipedia asserts that the proof goes back to Julius
Konig.

Oh, _that_ proof. Been thinking about what to do about some
set theory in "reals" next semester - that's the proof I came up
with one day, then I saw it on Wikipedia.

It seems to me that the proof is correct, although I can also
imagiue someone thinking it's wrong if he misunderstands
a certain assertion at the end. Not that the possible
misunderstanding I have in mind is the same as what
Lamport says is an error, but it's possible:

Say f: A -> B and g: B -> A are injections. Assume wlog
that A and B are disjoint.

Now for a given b in B, f^(-1)(b) may or may not exist;
since f is 1-1 there's at most one f^(-1)(b). Similarly
for a in A.

For a in A define the set

E_a = {..., f^(-1)(g^(-1)(a)), g^(-1)(a), a, f(a), g(f(a)),
f(g(f(a))), ...},

where the sequence extends infinitely far to the right
and as far as possible to the left. Note that the word
"sequence" in the previous sentence really refers only
to the notation - by definition E_a is a _set_, not
a sequence (for example E_a may well be a finite
set even though that sequence always extends infinitely
far to the right). Similarly define E_b for b in B.

Say X = A union B. It's easy to see that the sets
E_x give a partition of X. So we need only show
that for every x in X there is a bijection between
A_x = A intersect E_x and B_x = B intersect E_x.

And it's easy to see that for every x, either f or g
furnishes such a bijection. If E_x is "infinite to the
left" then either one works, while if the "leftmost"
element of E_x is an element of A then f restricted
to A_x is a bijection onto B_x: Since f is 1-1 its
restriction is 1-1, and the representation of E_x
as that sequence shows that every element of
B_s is f of some element of A_x.

Seems possible that a person could think that
the notation implies that each E_x is infinite,
which is not so. Also seems possible that someone
could think that the definition of the bijection
from A_x to B_x is "move one step to the right
in that sequence" - if so then one might be
concerned about whether that was actually
well-defined as a mapping on _elements_
as opposed to mapping sequence indices
to seqience indices.

Ok, I looked it up on Google Books as you suggest.
For a second I said aha, that's just a simpler and
cleaner way to say what I just said.

But it seems to me that what's in Kelly is _wrong_,
although it's easily fixed - what the author probably
meant, or should have meant, is ok. The problem
is indeed related to the fact that E_x can be finite
although the definition includes infinitely many
expressions:

Suppose that there exist a in A and b in B with
f(a) = b and g(b) = a. Then f has exactly one
ancestor, namely b. In particular a has an
odd number of ancestors. Kelley states that
this implies that f(a) has an even number of
ancestors, which is false; f(a) also has exactly
one ancestor. Error.

But the problem is just that "even/odd/infinite
number of ancestors is not exactly what we
meant or should have meant. Instead of
"infinitely many ancestors" consider the class
of a in A such that you can take the inverse
image, then the inverse image again, infinitely
many times. That would be the set of elements
with infinitely many ancestors and _also_
the elements that are part of closed loops
as above. Subdivide the _other_ elements
by the parity of the number of ancestors.
Now things are fine.



MoeBlee

David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
.

Relevant Pages

  • Re: Cantor Confusion
    ... The entries surpass every finite entry. ... S is a denumerable sequence of finite sequences. ... we trivially PROVE the diagonal sequence is infinite. ... set theory such that you believe you have proofs in set theory of P and ...
    (sci.math)
  • Re: Ultimate debunking of Cantors Theory
    ... in the list is a finite sequence. ... The other claim is that the infinite diagonal ... the diagonal argument in Z set theory proves that there are ... first order logic with identity, an axiom of Z set theory, or derived, ...
    (sci.math)
  • Re: Dial 999 for the real number line
    ... that infinite sets are not numerous, ... Does set theory hold the keys to the kingdom of heaven? ... proofs of uncountablility of the reals, but that is not going to happen. ... sequence is the truncated decimal with n digits. ...
    (sci.math)
  • Re: Review of Mueckenheims book.
    ... there is a projection of all finite lines. ... projection of all finite lines is infinite. ... The projection of a sequence has a Waft Maximum abbreviated by WM. ... know, an infinite finite number is not possible, even in set theory ...
    (sci.math)
  • Re: Review of Mueckenheims book.
    ... ....2222, they are actually infinitely distant elements of a sequence, ... smallest positive number, on the infinite scale. ... That's the ordering used by Cantor to prove their countability. ... If a set S is countable, then there is a total order < of S such that ...
    (sci.math)
Quantcast