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

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

  1. ray

    ray Guest

    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
    ray, Aug 9, 2004
    1. Advertisements

  2. ray

    Dave Seaman Guest

    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
    Dave Seaman, Aug 9, 2004
    1. Advertisements

  3. 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. ray

    Dave Seaman Guest

    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. ray

    Proginoskes Guest

    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. :cool:
    -- Christopher Heckman
    Proginoskes, Aug 10, 2004
  6. ray

    ray Guest

    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
    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.