Countable set

Printable View

October 7th 2012, 01:20 PM
jackie

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.
October 7th 2012, 04:52 PM
johnsomeone

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.
October 8th 2012, 02:27 PM
jackie

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?
October 8th 2012, 03:05 PM
Plato

Re: Countable set

Quote:

Originally Posted by jackie

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

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$
October 9th 2012, 06:26 AM
johnsomeone

Re: Countable set

Quote:

Originally Posted by jackie

Thank you for your help, John.

Glad to help.

Quote:

Originally Posted by jackie

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

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.
October 9th 2012, 07:23 PM
jackie

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. (Headbang) I would really appreciate it if you can guide me more on your geometric proof.

Quote:

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.

Quote:

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$ .
October 12th 2012, 05:54 AM
johnsomeone

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.