# Countable plus 1 equals uncountable (?)

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

1. ### rayGuest

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

2. ### Arturo MagidinGuest

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

3. ### Dave SeamanGuest

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
4. ### Keith A. LewisGuest

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
5. ### rayGuest

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
6. ### Dave SeamanGuest

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