# Extract countable set from uncountable set

I have switched for a moment from calculating integrals and solving differential equations to learning how to prove statements about infinite sets.
I have made a list of exercises for training and found myself absolutely helpless even in the face of the simplest problems in that list. The thought process that is required, currently, is alien to my brain, so I want to start with a little help from the community.

The problem is:

Given an uncountable set A of positive numbers, prove that we can choose a countable subset B from set A, so that the sum of the elements of B is infinite.

I guess, we should somehow provide the construction of the set $B \subset A$ with the required property, but I don't event know how to start.

I'd like to see the thinking process with as much detail as possible, so that I could internalize this type of thinking.

No, my question is not duplicate. Why do you mark it a duplicate so fast?
1. I need to extract countable set B, not any set.
2. I am more concerned with the specific type of thinking that is needed to solve these kinds of problems, than particular one-line formula that does it. In order to make my question concrete, I have provided a specific problem. By explaning how we are coming up with the solution to that problem it is easy to show how one thinks in the process.

A lot of interesting and useful information has been generated in the comments :) Now I am going into analysing mode and start putting this information together inside of my brain (and mold it with additional thinking). It is interesting, what time will it take before I get a general feeling for what is happening :)

• The set of integers is countable. So there is no "uncountable set of positive integers". Do you perhaps mean real numbers? – Asaf Karagila Aug 19 '16 at 13:17
• @AsafKaragila Sorry, I will fix it in a moment. – Pixar Aug 19 '16 at 13:18
• You should try, if possible, to construct a strictly increasing sequence in $A$. Since all its elements are bounded from below by its first term $b>0$, the sum will be $\geq \sum_{n\in\Bbb N}b$ which is infinite. – paf Aug 19 '16 at 13:50

We want countable number of elements that is bigger than some fixed number. If $B \subseteq A$ such that $\inf B > 0$, that would be great.

Of course that fixed number can be very small, so we may use $\frac 1n$ maybe?

If we let

\begin{align*} A_1 &= (1, \infty) \\ \\ A_2 &= \left( \frac 12 , 1 \right] \\ \\ A_3 &= \left( \frac 13 , \frac 12 \right] \\ \\ A_4 &= \left( \frac 14 , \frac 13 \right] \\ \\ A_5 &= \left( \frac 15 , \frac 14 \right] \\ &\vdots \end{align*}

Observe that $\bigcup A_n = \mathbb R^+$.

We claim that $A$ should have uncountable number of elements in at least one of $A_n$. This is because, if $A$ has at most countable elements in each $A_n$, then $A$ would have at most countable elements. (countable union of countable sets is countable)

So, $A$ has uncountable number of elements in $A_{n_0}$ for some $n_0$. Now we choose $B$ any countable subset of $A_{n_0}$. (Thus $B$ is a countable subset of $A$).

Then, $A$ has countable number of elements that is bigger that $\frac 1{n_0}.$

• I think that is a better answer than the answers in the linked question :) – Pixar Aug 23 '16 at 11:40

I was thinking hard about the problem. During several days I was filling tens of pages with my thoughts and drawings. Finally, I understand the problem and the solution pretty deep. I have decided not to write the way I have arrived to the solution, because there are already several answers about the technical stuff. Instead I have decided to put here meta-solution, the description of how to think about that problem, which is what I really wanted when I've written this question.

Even after reading the answers I still didn't really understand what was the question. I have made the wrong emphasis, I didn't truly see what the question puts in doubt. I thought that the problem was to make an algorithm or some kind of procedure that will choose the right elements for us from the given set $A$. But the question doubts completely different thought. We should see the problem in uneven distribution of numbers in the set $A$. So the real issue is that the most of the numbers could be concentrated around $0$ (there is no problem if they are concentrated around number $100$ or number $42$) and, probably, we cannot make the sum of them that is big enough (infinite). For example, if we take as the elements of the set $A$ only the numbers in the interval $(0, 1)$, then, probably, these numbers are too small and we cannot make an infinite sum out of them. This is the thought that is based on intuitive understanding that these numbers constitute a line segment of a small length $1$. That turns out to be false, because we can choose rational numbers of the form $\frac{1}{n} (n \in \mathbb N)$ and they will sum up to infinity.

Now, the real problem is that we cannot choose these specific points, namely, $1, \frac{1}{2}, \frac{1}{3}, ..., \frac{1}{n},...$ and declare that the problem is solved. Imagine that we are playing a game against some agent with intellect and it wins a price when it can come up with a set $A$ that has uncountably many numbers, but it doesn't contain the specific points that we have chosen. The order of the game is following: 1. We choose countable amount of numbers that add up to infinity 2. After that, the agent looks at our choice and tries to come up with a set $A$ that is both uncountable and doesn't have the points that we have provided.

The catch is that we will always lose this game if we specify the procedure/algorithm to generate these numbers, because the agent will use the procedure to do exactly the opposite. It will use it to exclude the numbers from the set $A$. That is why algorithmic thinking doesn't help here at all.

What does help to win this game is in some sense linguistic thinking. We will provide the agent not with the concrete procedure that gives him ability to look at the specific choice that we make (so, he will not see the concrete examples of the points that we have chosen), but we will provide the agent with linguistic specification which hacks the game that we play and allows us to switch the orders of our choices. So, providing the agent with linguistic construct allows us to delay our choice and make it after the agent made a choice for distribution of the numbers in $A$.

For an uncountable set $A \subseteq (0, + \infty)$, consider the sets $F_1, F_2, \ldots$, where $F_n = \{ a \in A : a \geq 1/n \}$. Note that every element of $A$ is in at least one of these $F_n$, so $A = \cup_{n = 1}^{\infty} F_n$. We know that the countable union of countable sets is countable, but $A$ is uncountable, so at least one $F_n$ must be countable. Let's say it's $F_{n_0}$. Then $\sum_{a \in A} a \geq \sum_{a \in F_{n_0}} a \geq \sum_{a \in F_{n_{0}}} 1 / n_0$. But $F_{n_0}$ is infinite, so $\sum_{a \in F_{n_{0}}} 1 / n_0 = + \infty$.

• Why we have to consider $F_1, F_2, ...$ in the first place? How did you get to that? I do understand that this proves that we can extract the subset $B$, but why did you feel the urge to create that sequence? Why $1/n$ and not $ln(n)$? – Pixar Aug 19 '16 at 14:42
• We could've chosen any sequence $(s_n)_n$ of positive numbers that converges to $0$ and said $F_n = \{ a \in A : a \geq s_n \}$. The key is that each $F_n$ has a lower bound, that is, $s_n$, and moreover that $s_n \to 0$, which means every element of $A$ is in at least one of the $F_n$. – AJY Aug 19 '16 at 14:46
• So I could've used, say, $\ln (1 + 1/n)$, but $\ln (n)$ wouldn't do because $\ln (1) = 0$, which means $F_1$ has no useful lower bound, so if $A = (0, \ln 1.99)$, then we get nowhere because $F_n = \emptyset$ for $n \geq 2$. This is because $\ln (n) \not \to 0$. – AJY Aug 19 '16 at 14:49
• Could you, please, elaborate a bit more on why do we need a sequence of positive numbers that converges to $0$? – Pixar Aug 19 '16 at 14:49
• Are you familiar with the $\epsilon-\delta$ definition of limits? – AJY Aug 19 '16 at 14:50

Suppose for any integer $n\geq 1$ the set $A_n = \{ a\in A: a>1/n\}$ is finite. Then $A^*= \{ a\in A: a>0\} = \cup_{n\geq 1} A_n$ is countable. This is not possible so there must be $n\geq 1$ for which $A_n$ is infinite and the conclusion follows.

• Sorry, I don't understand. I will dissect your answer into sentences to show you what isn't reaching my brain :). For the start, is $n$ an integer or is it any number? – Pixar Aug 19 '16 at 14:26
• Why have you started thinking about elements of $A$ that are larger than $1/n$ and construct the sets $A_1, A_2, ...$? What motivated you to do so? Is it the first thing we should think about when we are dealing with problems concerning uncountable sets? Or is there something you first understood (intuitively felt) and only after that you are writing this rigorous structure of formulas? – Pixar Aug 19 '16 at 14:38
• Good question: I think it is a habit that I got from measure theory where you always want to look at countable unions of measurable sets (to ensure measurability and getting convergence theorems). Often you look at sets of the form $A_n=\{f>1/n\}$ for positive integers $n\geq 1$. For example, If $f$ is $L^1$ then each $A_n$ has finite measure and $\{f>0\}$ then is a countable union of finite measure sets (it's called $\sigma$-finite) something which otherwise may not be evident. – H. H. Rugh Aug 19 '16 at 14:46
• I've got a lot from your answer. I am trying to generalize from the question as much as possible, so that I don't have to write new questions here for each of the problems I will encounter. So, if I understood you correctly, you have developed that habit of thinking by solving problems in measure theory. Could you, please, provide some adjacent examples (where we need to look at countable unions of measurable sets (btw. what are they? =) )) or links to them in your answer that have stampted your brain with that intuition? – Pixar Aug 19 '16 at 15:05
• You will need to look for Lebesgue integration (e.g. wikipedia, but better is to try a book). I don't really have any digestible examples but when you come across a problem regarding countable sets what should come to mind is to describe the problem using integers (or any countable set of values). In my solution if $n\geq 1$ was any real number the first part would still hold but the (disjoint) union of the $A_n$'s would not be countable so that part would no longer work. – H. H. Rugh Aug 19 '16 at 15:14

$A$ \ $\{0\}$ is uncountable and equal to $\cup_{n\in N}A_n$ where $A_n=\{x\in A :|x|\geq 1/n\}.$ If every $A_n$ were finite then $A$ \ $\{0\}$ would only be countable . So there exists $n_0$ such that $A_{n_0}$ is infinite.

So at least one of the 2 sets $\{x\in A_{n_0}:x\geq 1/n\},$ $\{x\in A_{n_0}:x\leq -1/n\}$ is infinite. So there exists a subset $\{x_j:j\in N\}$ of one of them, with $i\ne j\implies x_i\ne x_j.$ Then $\sup_{m\in N}|\sum_{j=1}^mx_j|\geq \sup_{m\in N}m/n=\infty.$