1. ## [SOLVED] Show countable sets.

I have a problem on this question.

Suppose $\displaystyle A \subseteq \mathbb{R}^+, b \in \mathbb{R}^+,$ and for every list $\displaystyle a_1, a_2, ..., a_n$ of finitely many distinct elements of $\displaystyle A, a_1+a_2+...+a_n \leq b$. Prove that $\displaystyle A$ is countable.

(Hint: For each positive integer $\displaystyle n$, let $\displaystyle A_n = \{x \in A | x \geq 1/n \}$. What can you say about the number of elements in $\displaystyle A_n$?)

============================

I can only conclude from a hint that $\displaystyle |A_1| \leq |A_2| \leq ... \leq |A_n|$ (where $\displaystyle |A_i|$ = the number of elements in $\displaystyle A_i$). It seems there is no link from this hint to the question. I need to show either there is a function $\displaystyle f:A \longrightarrow \mathbb{Z}^+$ that is one-to-one, or a function $\displaystyle g: \mathbb{Z}^+ \longrightarrow A$ that is onto.

If A = (0, 1), clearly this is uncountable. But I may choose b to be very large so that for any $\displaystyle n \in \mathbb{Z}^+, a_1+...+a_n \leq b$. Then, how could that A needs to be countable??

Thank you very much in advance.

2. Originally Posted by armeros
If A = (0, 1), clearly this is uncountable. But I may choose b to be very large so that for any $\displaystyle n \in \mathbb{Z}^+, a_1+...+a_n \leq b$. Then, how could that A needs to be countable??
Hi armeros.

You cannot choose any $\displaystyle b$ this way. For any $\displaystyle a\in A=(0,\,1),$ let $\displaystyle a_n=a+\frac{1-a}{n+1}.$ Then clearly $\displaystyle a_n\in A$ and $\displaystyle \sum_na_n$ is not bounded above.

3. Thanks. But what about how I can relate this information to the question?

4. Originally Posted by armeros
Suppose $\displaystyle A \subseteq \mathbb{R}^+, b \in \mathbb{R}^+,$ and for every list $\displaystyle a_1, a_2, ..., a_n$ of finitely many distinct elements of $\displaystyle A, a_1+a_2+...+a_n \leq b$. Prove that $\displaystyle A$ is countable. (Hint: For each positive integer $\displaystyle n$, let $\displaystyle A_n = \{x \in A | x \geq 1/n \}$.
The $\displaystyle b\in \mathbb{R}^+$ is fixed as part of the given.
You must know the Archimedean principle to do this problem: $\displaystyle \left( {\forall n \in \mathbb{Z}^ + } \right)\left( {\exists M_n \in \mathbb{Z}^ +} \right)\left[ {\frac{{M_n }}{n} > b} \right]$.
Is it possible that $\displaystyle A_n$ could have more that $\displaystyle M_n$ terms?
If not then $\displaystyle \left( {\forall n \in \mathbb{Z}^ + } \right)\left[ {A_n\text{ is finite} } \right].$

Is it clear to you that $\displaystyle A = \bigcup\limits_n {A_n } ~?$

5. I am trying to find some contradiction if $\displaystyle |A_n| > M_n$ I looked into the Archimedean Property and there are two arguments.

$\displaystyle \forall x \in \mathbb{R} \exists n \in \mathbb{Z}^+$ such that $\displaystyle x<n$.

$\displaystyle \forall x > 0, \exists n \in \mathbb{Z}^+$such that $\displaystyle 1/n < x$.

Which one did you apply? And moreover, the book I am reading did not mention Archimedean property at all, so I thought there might be some other way to do it.

The rest are clear to me. Thanks!

6. Originally Posted by armeros
I am trying to find some contradiction if $\displaystyle |A_n| > M_n$
If that were true then the sum of $\displaystyle M_n$ elements from $\displaystyle A_n$ would be $\displaystyle >b$.
WHY?

7. Originally Posted by Plato
If that were true then the sum of $\displaystyle M_n$ elements from $\displaystyle A_n$ would be $\displaystyle >b$.
WHY?
Hmm Let me see.

$\displaystyle a_1+a_2+...+a_n < b < M_n/n$

$\displaystyle n(a_1+a_2+...+a_n) < M_n$

...no good. I don't get it, at least for this moment.

One more thing, it seems to me that $\displaystyle A_n$ should be equal to A, shouldn't it?

8. $\displaystyle \left( {\forall a \in A_n } \right)\left[ {a \geqslant \frac{1} {n}} \right]\; \Rightarrow \;M_n a \geqslant \frac{{M_n }} {n} > b$

That says the each element in $\displaystyle A_n$ is at least as large as $\displaystyle \frac{1}{n}$.
If there were $\displaystyle M_n$ distinct elements in $\displaystyle A_n$ then their sum would be greater than $\displaystyle b$.
That is contrary to the given.

9. That's right. So, the final step, is $\displaystyle A_n = A$?

The definition of $\displaystyle A_i$means that

$\displaystyle A_1 \subseteq A_2 \subseteq ... \subseteq A_n$

10. Originally Posted by armeros
I have a problem on this question.

Suppose $\displaystyle A \subseteq \mathbb{R}^+, b \in \mathbb{R}^+,$ and for every list $\displaystyle a_1, a_2, ..., a_n$ of finitely many distinct elements of $\displaystyle A, a_1+a_2+...+a_n \leq b$. Prove that $\displaystyle A$ is countable.

(Hint: For each positive integer $\displaystyle n$, let $\displaystyle A_n = \{x \in A | x \geq 1/n \}$. What can you say about the number of elements in $\displaystyle A_n$?)

============================

I can only conclude from a hint that $\displaystyle |A_1| \leq |A_2| \leq ... \leq |A_n|$ (where $\displaystyle |A_i|$ = the number of elements in $\displaystyle A_i$). It seems there is no link from this hint to the question. I need to show either there is a function $\displaystyle f:A \longrightarrow \mathbb{Z}^+$ that is one-to-one, or a function $\displaystyle g: \mathbb{Z}^+ \longrightarrow A$ that is onto.

If A = (0, 1), clearly this is uncountable. But I may choose b to be very large so that for any $\displaystyle n \in \mathbb{Z}^+, a_1+...+a_n \leq b$. Then, how could that A needs to be countable??
There is no such b!. For any real b> 0, let n= b/0.9. Take n members of (0.9, 1) to be $\displaystyle a_1, a_2, ..., a_n$. Then [tex]a_1+ a_+ ...+ a_n> n(.9)> b.

Thank you very much in advance.

11. Originally Posted by HallsofIvy
There is no such b!. For any real b> 0, let n= b/0.9. Take n members of (0.9, 1) to be $\displaystyle a_1, a_2, ..., a_n$. Then [tex]a_1+ a_+ ...+ a_n> n(.9)> b.
The number $\displaystyle b$ is part of the given. It does exist.
The mistake, as I pointed out, is that being part of the given $\displaystyle b$ is fixed.

12. So, is $\displaystyle A_n$ = A or $\displaystyle A = \bigcup\limits_n {A_n } ~?$

13. Originally Posted by armeros
So, is $\displaystyle A_n$ = A or $\displaystyle A = \bigcup\limits_n {A_n } ~?$
I have told you that must be $\displaystyle A = \bigcup\limits_n {A_n }$.

It is clear that $\displaystyle \left( {\forall n \in \mathbb{Z}^ + } \right)\left[ {A_n \subseteq A} \right]$

The other direction: $\displaystyle x \in A\; \Rightarrow \;x > 0\; \Rightarrow \;\left( {\exists k \in \mathbb{Z}^ + } \right)\left[ {\frac{1} {k} < x} \right]\; \Rightarrow \;x \in A_k \; \Rightarrow \;x \in \bigcup\limits_n {A_n }$

14. Thank you very much!