Re: Zenkin's paper on Cantor (reply of Dr. Zenkin)

From: Dave Seaman (dseaman_at_no.such.host)
Date: 10/18/04

  • Next message: smangano_at_ureach.com: "Proof that this assertion about heaps is true" 
    Date: Mon, 18 Oct 2004 17:53:53 +0000 (UTC)

    On 18 Oct 2004 08:37:32 -0700, Craig Feinstein wrote:
    > Cantor's theorem that |S| < 2^{|S|} for any set S can be proven as
    > follows, without the whole diagonal presentation:

    > Suppose that S and 2^S can be put into one-to-one correspondence by
    > function f:S -> 2^S. Consider subset S'={x in S: x notin f(x)} of S.
    > Since f is one-to-one and onto, f(y)=S' for some y. If y in f(y) then
    > y notin f(y). And if y notin f(y), then y in f(y), so we have a
    > contradiction. Therefore, |S| < 2^{|S|} for any set S. QED

    To prove that |S| < |P(S)| you actually need to show two things, one of
    which is quite trivial:

            (1) There exists an injection f: S -> P(S).
            (2) There does not exist a surjection f: S -> P(S).

    Part (1) proves that |S| <= |P(S)|. Part (2) proves that the inequality
    is strict. We need part (1) because, in the absence of the axiom of
    choice, it is possible to have two sets that are incomparable in the
    sense that neither can be injected into the other.

    To demonstrate that part (1) holds, it is only necessary to consider the
    mapping s |-> {s}, which is an injection from S into P(S).

    That leaves part (2), which is where the diagonal argument comes in.
    Although the diagonal argument is often presented as an indirect proof
    (assume a surjection exists, and derive a contradiction), that approach
    is unnecessary and sometimes confuses the very people that are skeptical
    of Cantor's argument in the first place. Therefore, I propose to present
    a direct proof; in what follows, it is not assumed that f is a surjection
    and no contradiction is derived. Rather, the proof shows directly that f
    is not a surjection by exhibiting a member of P(S) that is not in the
    range of f.

    Proof of (2). Let the mapping f: S -> P(S) be given. Let D = { s in S :
    not(x in f(x)) }. (Note: D is the diagonal). Then D is a subset of S,
    which means it is a member of P(S). Moreover, D differs from f(s) for
    each s in S. There are two cases to consider:

            (a) if s in f(s), then not(s in D).
            (b) if not(s in f(s)), then s in D.

    For each s, it is clear from (a) and (b) that the symmetric difference of
    f(s) and D contains at least the element s, hence f(s) and D are not
    equal. This shows that D is not in the range of f, and therefore f is
    not a surjection, Q.E.D.

    > As a corollary, Aleph_0 < 2^Aleph_0.

    As another corollary, aleph_0 < |R|. Proof: consider the mapping f:
    P(N) -> [0,1] given by f(S) = 2 * sum_(s in S) 1/3^s. This is an
    injection from the power set of the naturals into [0,1], thus proving
    that 2^aleph_0 <= |[0,1]|. The image of f is the Cantor set. It's easy
    to show by the Cantor-Bernstein theorem that equality holds, and in fact
    c = 2^aleph_0 = |P(N)| = |[0,1]| = |R|.

    > There is nothing wrong with this logic -- except who said there was a
    > such thing as infinite sets? I've never seen an infinite set and could
    > argue that no such set can possibly exist in reality, only in theory
    > (or imagination).

    The existence of an infinite set is guaranteed by the axiom of infinity,
    which is one of the axioms of ZF. This axiom guarantees that there is a
    set large enough to contain all the natural numbers.

    > For instance, how do we know the set of natural numbers really exists?

    What does it mean for a mathematical object to "really exist"?

    > Has anyone ever counted to infinity? Who knows if when one counts to a
    > certain number, the great computer in the sky gives an overflow error?

    Has anyone ever counted to googolplex?

    > This argument has some sarcasm in it, but I think it is the heart of
    > the matter in why so many people are against Cantor's math, especially
    > when he first published it.

    > Craig 

    -- 
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
  • Next message: smangano_at_ureach.com: "Proof that this assertion about heaps is true"