# Using the diagonal theorem in reverse to prove a theorem about cofinite sets.

Discussion in 'Recreational Math' started by ray, Aug 9, 2004.

1. ### rayGuest

Consider the collection T of cofinite (complements of finite sets)
sets of positive integers. These are countable, since the finite sets
F are countable and F and T are trivially 1 to 1. We enumerate T (and
there is an effective procedure for this based on some fairly natural
enumeration of F) and let D be the diagonal that is induced by the
enumeration. Form the complement of D (the usual step in the diagonal
argument), D*. Now, since we know that T is countable, it follows that
since D* differs from each member of T, then D* cannot be a cofinite
set, otherwise D* would be a witness to the fact that T is
uncountable. So D cannot be finite.

Thus any enumeration of cofinite sets will always induce an infinite
diagonal set.

Surely this is a theorem? It is not obvious (to my mind) that however
we enumerate the cofinite sets, then it must happen that for
infinitely many i, the number i will belong to the ith set in the
enumeration.

ray, Aug 9, 2004

2. ### Dave SeamanGuest

It's at least a witness to the fact that the enumeration of T is less
than complete, contrary to assumption.
Yes, it's a theorem. Why isn't it obvious? Your own argument is
correct.

Dave Seaman, Aug 9, 2004

3. ### The Last Danish PastryGuest

It is not clear to me how (since the elements of a set have no order) you
can talk about the diagonal of a set of sets.

The Last Danish Pastry, Aug 10, 2004
4. ### Dave SeamanGuest

An enumeration of T implies an order on T. Each member of T, being a
subset of the naturals, has the order that it inherits from N.

Dave Seaman, Aug 10, 2004
5. ### ProginoskesGuest

Yes. You can think of arguing by contradiction; if you theorem is not
true, then you can carry out the diagonalization process and get a VALID
element which is "not on the list", contradicting the fact (from
elsewhere) that a complete list is possible.
It's not obvious to me, either. -- Christopher Heckman

Proginoskes, Aug 10, 2004
6. ### rayGuest

I agree that this is an error on my part. I was thinking of binary
strings still, where the physical diagonal exists. D* is the set
defined so that x belongs to D* if and only if x does not belong to
T(x), where T(x) is the xth set in the enumeration. Thus D is the set
of numbers y such that y belongs to
T(y). Since D* cannot be cofinite, it follows that its complement - D
- must be infinite.

ray, Aug 10, 2004