Re: Using the diagonal theorem in reverse to prove a theorem about cofinite set
From: James Dolan (jdolan_at_math-cl-n03.math.ucr.edu)
Date: 08/10/04
- Next message: Herman Jurjus: "Re: Embedding Boolean Algebras"
- Previous message: The Last Danish Pastry: "Re: A geometry problem. Please help me!"
- In reply to: KRamsay: "Re: Using the diagonal theorem in reverse to prove a theorem about cofinite set"
- Next in thread: The Last Danish Pastry: "Re: Using the diagonal theorem in reverse to prove a theorem about cofinite sets."
- Messages sorted by: [ date ] [ thread ]
Date: Tue, 10 Aug 2004 08:31:51 +0000 (UTC)
in article <20040810024816.06972.00000230@mb-m03.aol.com>,
kramsay <kramsay@aol.com> wrote:
|In article <cf8qm9$iad$1@mozo.cc.purdue.edu>, Dave Seaman
|<dseaman@no.such.host> writes:
||> 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.
||
||Yes, it's a theorem. Why isn't it obvious? Your own argument is
||correct.
|
|A result's being obvious has a funny way of being different from the
|result having a simple, clear proof. Here's another proof that makes
|it seem more "obvious" to me, and I don't know why. If one tries to
|make such an enumeration, one keeps "getting further behind":
|
|For any n, there are 2^{n-1} sets of positive integers that contain n
|but no integers greater than n. For the complement of such a set S to
|be at a position k in the list such that k is not in the complement
|of S (i.e., k is in S), we must have 1<=k<=n. But there are only n
|such positions, which means that at least 2^{n-1}-n of the sets have
|to be put at an index k that's a member of the complement of S. This
|holds true for all n, so there are infinitely many such sets.
i think the following seems more "obvious" to me. first of all, i'd
rather enumerate the finite sets than the cofinite ones. we want to
marry off the "men" (= naturals) and the "women" (= finite sets of
naturals) in such a way that there's only a finite number of unhappy
marriages, where "happy" means that the husband belongs to the wife.
(hmm, i didn't know it was going to come out that way, folks.)
equivalently, we want only a finite number of unhappy women. but the
"one-man women" (= singleton sets of naturals) are hard to please; if
only a finite number of them are allowed to be unhappy, then they
monopolize all but a finite number of the men, who couldn't possibly
accommodate the infinite collection of all the rest of the women.
whereas keith ramsay's proof seems to say "there are 2^[n-1] women
such that the last man they'd want to marry is the nth, so for each
sufficiently big n you make at least one more woman permanently
unhappy when you dole out the nth man". i guess that's fairly obvious
too. the proof i gave relies on there being one particularly
hard-to-please group of women, but keith's shows that even if you got
rid of that group of trouble-makers, the rest of the women are still
choosy enough that you'd still have a hard time.
-- [e-mail address jdolan@math.ucr.edu]
- Next message: Herman Jurjus: "Re: Embedding Boolean Algebras"
- Previous message: The Last Danish Pastry: "Re: A geometry problem. Please help me!"
- In reply to: KRamsay: "Re: Using the diagonal theorem in reverse to prove a theorem about cofinite set"
- Next in thread: The Last Danish Pastry: "Re: Using the diagonal theorem in reverse to prove a theorem about cofinite sets."
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
