Results 1 to 7 of 7

Math Help - Countable set

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    76

    Countable set

    Could someone give me a hand on this problem?
    Let X \subset R^n such that for every x \in X there exists a neighborhood N_r(x) such that  N_r(x) \bigcap X is at most countable. Prove that X is at most countable.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Countable set

    1. \mathbb{R}^n is second countable (open balls centered at rational coordinates and having rational radii form a countable base).

    2. Every subspace of a second countable space is second countable (the obvious proof works).

    3. Every open cover of a second countable space has a countable subcover.
    (Pf: Each set in an arbitrary open cover is some union of those basis sets, so the union of all the sets in the cover is the union of all of those associated basis sets. Now for each of those basis sets in that final union, pick one set of the original cover that it's a subset of. That picks out a countable subset of the original cover, since the basis is countable. The union of all those basis sets covers the space, and is also a subset of the union of that countable subset of the original cover. Thus that countable subset of the original cover is also a cover. This has shown how to produce a countable subcover for any open cover.)

    With those onbservations in hand, the problem is straighforward to prove.
    Last edited by johnsomeone; October 8th 2012 at 04:52 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2008
    Posts
    76

    Re: Countable set

    Thank you for your help, John. However, I have not learned a lot of the terms you mentioned such as: second countable, open cover, basis. Is there an elementary approach to this problem?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1

    Re: Countable set

    Quote Originally Posted by jackie View Post
    Thank you for your help, John. However, I have not learned a lot of the terms you mentioned such as: second countable, open cover, basis. Is there an elementary approach to this problem?
    Look at the OP.
    Quote Originally Posted by jackie View Post
    Could someone give me a hand on this problem?
    Let X \subset R^n such that for every x \in X there exists a neighborhood N_r(x) such that  N_r(x) \cap X is at most countable. Prove that X is at most countable.
    In reply#2 the third fact is important.
    You must know that the countable union of countable sets is countable.
    From the given, the collection N_r(x) is an open cover of X
    From #3 there is a countable subcover.
    You can get X as the countable union of countable sets that look like  N_r(x) \cap X
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Countable set

    Quote Originally Posted by jackie View Post
    Thank you for your help, John.
    Glad to help.

    Quote Originally Posted by jackie View Post
    However, I have not learned a lot of the terms you mentioned such as: second countable, open cover, basis.
    What I wrote is largely self contained, since I gave an outline of the proofs. If you arm yourself with the definitions (google - include the word "topology" in the search), which are *very* simple, what I wrote shouldn't won't be beyond your ability to follow. Plato has filled in more of the details of how the proof would proceed. So even if it strikes you as unfamiliar, it's not difficult - each step is very direct - and so is a good exercise to try to work through. It's a challenge, but not a daunting one, so is very useful to attempt.

    Quote Originally Posted by jackie View Post
    Is there an elementary approach to this problem?
    Here's a more geometric approach that will prove it. It will be a proof by contradiction. I'll set it up, but leave the concluding reasoning to you.

    Assume X is uncountable.

    \text{Let} \ f : X \rightarrow (0, \infty] \ \text{by} \ f(x) = \sup \{ r \in \mathbb{R}^+ | B(x, r) \cap X \text{is countable} \}.

    ( B(x, r) is the open ball in \mathbb{R}^n with center x and radius r).

    If \exists x_0 \in X such that f(x_0) = \infty, then every ball about x_0 intersects X in a countable set.

    That would mean that X \cap \mathbb{R}^n is countable, and so X is countable, which we've assumed is not the case.

    Therefore f : X \rightarrow (0, \infty). (This isn't necessary, but might help to avoid concern about the meaning of f(x_i) = \infty.)

    For r \in \mathbb{R}^+, define X_r = \{x \in X | f(x) \ge r \}.

    Then X = \cup_{m = 1}^{\infty} X_{1/m}.

    If X_{1/m} were countable \forall \ m \in \mathbb{Z}^+, then X would be countable - but we're assuming it's not.

    Therefore \exists m_0 \in \mathbb{Z}^+ such that X_{1/m_0} is uncountable. Let r_0 = 1/m_0 \ (>0).

    Now divide \mathbb{R}^n into a grid of solid n-dimensional cubes of side length s = \frac{r_0}{2 \sqrt{n}} \ (>0)

    Do it so that the coordinates of the verticies of the cubes are like (c_1s, c_2s, ... c_ns), where c_1, c_2, .. c_n \in \mathbb{Z}.

    The cubes are solid, and so will intersect in their common faces. This won't matter. What matters is this:

    The distance between any two points in a single cube is less than or equal to r_0/2 (a diagonal has length s\sqrt{n}),

    and therefore, for each of those cubes C, if y \in C, then C \subset B(y, r_0).

    The number of cubes is countable (its cardinality is less than or equal to the cardinality of all the verticies of all the cubes, which is countable).

    Here are some thoughts on finishing the proof:

    Consider how X_{r_0} is defined. If x \in X_{r_0}, what does that say about B(x, r_0)?

    If y \in C, for some cube C, what can you say?

    So, combining those two observations: what can you about X_{r_0}\cap C for those cubes C?

    Now recall that X_{r_0} is uncountable. Is it possible that X_{r_0}\cap C is countable for ALL of those cubes C?

    You should be able to produce a contradiction.
    Last edited by johnsomeone; October 9th 2012 at 09:36 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2008
    Posts
    76

    Re: Countable set

    Thank you Plato and John. Today my professor showed us the proof of Lindelof's lemma. So, now I know how to prove this problem by applying the lemma. Let B= \{B(x,r): x\in X, r \in R^{+}\}. Then B is an open cover for X. By the lemma, B has a countable subcover F=\{B(x_n,r_n): n\in N\} that also covers X. By hypothesis, B(x_n,r_n) \cap X is countable for every n. Hence, S= \bigcup (B(x_n,r_n) \cap X) is countable since it is a countable union of countable sets.

    I really want to understand your geometric proof, John. However, I can't figure out the answers to the questions you asked. I spent more than an hour going over your steps, but I don't really know how to proceed. I would really appreciate it if you can guide me more on your geometric proof.

    Consider how X_{r_0} is defined. If x \in X_{r_0}, what does that say about B(x, r_0)?
    Let A=\{ r \in \mathbb{R}^+ | B(x, r) \cap X \text{is countable} \}. Then if x \in X_{r_0} , then f(x)=supA \geq r_0=1/m_0. I asked myself. Is r_0 \in A? If it is, then B(x,r_0) \cap X is countable. I am not able to connect the dots here. Also, I don't really know how to use the fact that the function f(x) is defined as the the supremum of the set of radii of the balls.

    If y \in C, for some cube C, what can you say?
    Then C \subset B(y,r_0) since d(x,y)< r_0/2<r_0 for any  x\in C.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Countable set

    There are 4 established facts that, with a little bit of reasoning, will complete the proof.

    By the way each X_r was defined: if x \in X_{r_0}, then X \cap B(x, r) is countable for all r \le r_0.

    In particular, (Fact1) if x \in X_{r_0}, then X \cap B(x, r_0) is countable.

    By the way the size of those cubes were choosen, it's been established that:

    (Fact2) if x \in C, then C \subset B(x, r_{0})

    Also, by construction, (Fact3) those cubes, countable in number, cover all of \mathbb{R}^n.

    Finally, the specific r=r_0 was found so that (Fact4) X_{r_0} is uncountable.

    I envisioned the proof proceeding this way:

    Pick any one of those cubes C.

    If x \in X_{r_0} \cap C, then x \in X_{r_0}, and so X \cap B(x, r_0) is countable (Fact1).

    If x \in X_{r_0} \cap C, then x \in C, and so C \subset B(x, r_{0}) (Fact2).

    Thus, if x \in X_{r_0} \cap C, then C \subset B(x, r_{0}), so (X_{r_0} \cap C) \subset (X_{r_0} \cap B(x, r_{0})) \subset (X \cap B(x, r_{0})).

    Thus, if x \in X_{r_0} \cap C, then X_{r_0} \cap C is countable.

    (*) Incorporating that the empty set is countable proves: for every one of those cubes C, X_{r_0} \cap C is countable.

    (I use "countable" to mean finite or countably infinite, which means at most countably infinite. Sometimes people use "countable" only for exactly the cardinality of the integers, and "denumerable" for cardinality less than or equal to the cardinality of the integers. Since the premises and conclusion of the theorem are about "at most countable", the choice of terminology doesn't make any difference, because on one definition you're using "at most countable" everywhere, which is the same as "denumerable", and on the other definition - my definition - you're using "countable" everywhere. Note that the meaning of uncountable is the same for all of these definitions.)

    Now, since \mathbb{R}^n = \cup_{i = 1}^{\infty} C_i (Fact3), it follows that X_{r_0} = X_{r_0}\cap \mathbb{R}^n = \cup_{i = 1}^{\infty} (X_{r_0} \cap C_i).

    Because a countable union of countable sets is countable, and because X_{r_0} is uncountable (Fact4), it follows that there's at least one cube C such that (X_{r_0} \cap C) is uncountable.

    But that's a contradiction with (*). Therefore the assumption that X is uncountable is false.

    Therefore X is countable.

    $$$$$$$$$$$$$$$$$$$$$$$$$$$$$

    Sorry if attempting it was frustrating. Since I already knew where the proof was going, it was hard for me to gauge exactly how difficult it would be to complete from any given stopping point. I had hoped to leave it requiring some work and thought, but not so much that it was frustrating.

    Another thing. It was unforntunate for me to include that function f defined as a supremum. It's not necessary, and adds undue complication. It's a legacy from how I reasoned out the proof. I apologize for including it and not realizing that it was no longer needed.

    If you're curious about the origin & purpose of that f, I came to the above proof by reasoning:
    "What's the biggest r can be so that B(x,r) intersect X remains countable? It can't be infinite, or X would be countable. OK - what happens at its surpemum, f(r)? What happens is that any bigger ball than that will intersect X uncountably. That means that between the sphere of radius f(r), and any larger ball centered at x containing it, there are an uncountable number of X. So the closed n-dimensional annulus with inner radius f(r) and outer radius f(r)+epsilon has an uncountable number of X for all epsilon>0. That's a compact set. (Perfect, I thought, since this looks like a problem that wants to use compactness - it's about finiteness and gives something about the open sets around each point of the space in question - so surely it's about compactness.) That annulus is a compact set where each of those x's is bounded away from any uncountable portion of X. But that's impossible - you've an uncountable number, so they must be smushed up against one another closely *somewhere*. THEN it dawned on me that the compactness doesn't matter to that - ant uncountable set in \mathbb{R}^n must have some uncountable portion of itself smushed up against itself closely *somewhere*. Now matter how finely I slice up \mathbb{R}^n, if X is uncountable, then some arbitrarily tiny slice of \mathbb{R}^n will always contain an uncountable number of X elements." And that got me to this proof. So that's where the f(x) came from - as a legacy of my trying to prove this using a compact annulus centered at x for each x in X.
    Last edited by johnsomeone; October 12th 2012 at 08:03 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 07:14 AM
  2. Replies: 2
    Last Post: November 11th 2010, 05:56 AM
  3. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 02:59 PM
  4. Replies: 1
    Last Post: February 9th 2010, 02:51 PM
  5. Replies: 11
    Last Post: October 11th 2008, 07:49 PM

Search Tags


/mathhelpforum @mathhelpforum