A Cute Problem


Jim told me this cute problem about two years ago. I was reminded of it while reading the recent posts over at Ars Mathematica. For your enjoyment:

Prove that in the poset of subsets of \mathbb{N}, there exists an uncountable chain(!)

6 Responses to “A Cute Problem”

  1. Harald Hanche-Olsen Says:

    Heh. Cute indeed. Here’s a partial spoiler: Replace the natural numbers by some other countable set. And a total spoiler (rot13 to spoil): Hfr gur engvbany ahzoref. Qrqrxvaq phgf.

  2. Terence Tao Says:

    It is a nice problem. One curious thing is that the first uncountable ordinal, which is the staple ingredient of most counterexamples in this spirit, is a total red herring here. Indeed, the chain involved cannot be well-ordered.

  3. fjfjfjf Says:

    Wow! This (1) seems impossible, yet (2) has a trivial proof. Very thought-provoking.

  4. Gadi Moran Says:

    Let the countble set be the set of rational numbers.
    with each real number x, let A(x) be the set of rationals smaller than x.
    The chain of sets {A(x): x in R} is as required (its cardinaliy is two to aleph 0, which is uncountable).
    No use of the axiom of choice is needed.

  5. legal tender Says:

    My family every time say that I am wasting my time here at web,
    but I know I am getting knowledge daily by reading
    thes fastidious articles or reviews.

  6. Reggie Says:

    A really good answer, full of raltnoatiiy!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: