Countable plus 1 equals uncountable (?)

Discussion in 'Recreational Math' started by ray, Sep 22, 2004.

  1. ray

    ray Guest

    What is wrong with this argument?

    A set is ‘maximal' if its cardinality can be increased by the addition
    of one extra element.

    Theorem.

    Any countable set is maximal.

    Trivially, every finite set is maximal. Suppose now that S is a
    countably infinite collection of subsets of N, and let S be enumerated
    by E, such that E(x) is the xth set in the enumeration. Let d be
    defined by ‘x belongs to d iff x belongs to E(x)', and let d* be the
    complement of d, so that d* is the usual diagonal construction. Now,
    suppose that d* is added to our collection S (Let S' = S union {d*}).
    Then since d* differs from E(x) for all x, d* cannot appear in our
    enumeration, thus it is impossible to completely enumerate S', and S'
    is uncountable. So S is maximally countable.

    Clearly, not any old extra subset A of N will do if we want S union
    {A} to be uncountable, it has to be d*. But how can this be? How can
    ‘adding one' sometimes make a set uncountable and sometimes not,
    depending on the ‘one' that is being added?
     
    ray, Sep 22, 2004
    #1
    1. Advertisements

  2. N being... the natural numbers?
    in N....
    No. What you have shown is that if you add an element, then the OLD
    enumeration need not ennumerate the set you get. However, one can
    still ennumerate S' as follows:

    Define E':N->S' by

    E'(0) = d*
    E'(n+1) = E(n) for every natural number n.

    E' ennumerates S', which shows that S' is countable. So, at least
    adding d* does not work. Since adding any element to S will yield
    either S or a set bijectable with S', this shows that your S is not,
    in fact, "maximal".
    Indeed: no set A will do, since S union {A} will have at most
    countably many elements.
    Who said that the same enumeration had to work for both S and S union
    {A}?


    --
    ======================================================================
    "It's not denial. I'm just very selective about
    what I accept as reality."
    --- Calvin ("Calvin and Hobbes")
    ======================================================================

    Arturo Magidin
     
    Arturo Magidin, Sep 22, 2004
    #2
    1. Advertisements

  3. ray

    Dave Seaman Guest

    Then a set is "maximal" iff it is finite (possibly Dedekind-finite in the
    absence of AC).
    Not so. Let f: N -> S' be given by

    f(0) = d*,
    f(n+1) = E(n).

    Then f enumerates S', contrary to your claim. It's true that f(0)
    differs from f(n) for n > 0, but there's nothing wrong with that.
    It doesn't make any difference what you add. Adding one member to a
    countable set always produces a countable set.

    What you are overlooking is the importance of the universal quantifier in
    the proof of Cantor's theorem. The proof depends on the fact that *for
    every* f: N -> P(N), there exists a d* (depending on f) such that d* is
    not in the range of f. Just one single d* for one mapping f is not
    sufficient.
     
    Dave Seaman, Sep 22, 2004
    #3
  4. Because one method of enumeration fails, enumeration is impossible?

    --Keith Lewis klewis {at} mitre.org
    The above may not (yet) represent the opinions of my employer.
     
    Keith A. Lewis, Sep 22, 2004
    #4
  5. ray

    ray Guest


    I put d* first in the enumeration, then d* builds as E builds! Of
    course. (I have posted to myself as it is not clear who to reply to
    but thanks for clearing that up.) I've changed the theorem
    accordingly.
     
    ray, Sep 22, 2004
    #5
  6. ray

    Dave Seaman Guest

    It can be sharpened to: a set is maximal iff it has no denumerable subset.
    Assuming AC: a set is maximal iff it is finite.
     
    Dave Seaman, Sep 22, 2004
    #6
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.