Results 1 to 14 of 14

Math Help - Show countable sets.

  1. #1
    Junior Member
    Joined
    Apr 2009
    Posts
    50

    [SOLVED] Show countable sets.

    I have a problem on this question.

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

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

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

    I can only conclude from a hint that |A_1| \leq |A_2| \leq ... \leq |A_n| (where |A_i| = the number of elements in A_i). It seems there is no link from this hint to the question. I need to show either there is a function f:A \longrightarrow \mathbb{Z}^+ that is one-to-one, or a function 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 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.
    Last edited by armeros; May 18th 2009 at 09:11 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by armeros View Post
    If A = (0, 1), clearly this is uncountable. But I may choose b to be very large so that for any 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 b this way. For any a\in A=(0,\,1), let a_n=a+\frac{1-a}{n+1}. Then clearly a_n\in A and \sum_na_n is not bounded above.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2009
    Posts
    50
    Thanks. But what about how I can relate this information to the question?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,384
    Thanks
    1475
    Awards
    1
    Quote Originally Posted by armeros View Post
    Suppose A \subseteq \mathbb{R}^+, b \in \mathbb{R}^+, and for every list a_1, a_2, ..., a_n of finitely many distinct elements of A, a_1+a_2+...+a_n \leq b. Prove that A is countable. (Hint: For each positive integer n, let A_n = \{x \in A | x \geq 1/n \}.
    The b\in \mathbb{R}^+ is fixed as part of the given.
    You must know the Archimedean principle to do this problem: \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 A_n could have more that M_n terms?
    If not then \left( {\forall n \in \mathbb{Z}^ +  } \right)\left[ {A_n\text{ is finite} } \right].

    Is it clear to you that A = \bigcup\limits_n {A_n } ~?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2009
    Posts
    50
    I am trying to find some contradiction if |A_n| > M_n I looked into the Archimedean Property and there are two arguments.

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

    \forall x > 0, \exists n \in \mathbb{Z}^+ such that 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!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,384
    Thanks
    1475
    Awards
    1
    Quote Originally Posted by armeros View Post
    I am trying to find some contradiction if |A_n| > M_n
    If that were true then the sum of M_n elements from A_n would be >b.
    WHY?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Apr 2009
    Posts
    50
    Quote Originally Posted by Plato View Post
    If that were true then the sum of M_n elements from A_n would be >b.
    WHY?
    Hmm Let me see.

     <br />
a_1+a_2+...+a_n < b < M_n/n

    n(a_1+a_2+...+a_n) < M_n<br />

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

    One more thing, it seems to me that A_n should be equal to A, shouldn't it?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,384
    Thanks
    1475
    Awards
    1
    \left( {\forall a \in A_n } \right)\left[ {a \geqslant \frac{1}<br />
{n}} \right]\; \Rightarrow \;M_n a \geqslant \frac{{M_n }}<br />
{n} > b

    That says the each element in A_n is at least as large as \frac{1}{n}.
    If there were M_n distinct elements in A_n then their sum would be greater than b.
    That is contrary to the given.
    Last edited by Plato; May 18th 2009 at 08:57 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Apr 2009
    Posts
    50
    That's right. So, the final step, is A_n = A?

    The definition of A_i means that

     <br />
A_1 \subseteq A_2 \subseteq ... \subseteq A_n<br />

    Thanks for all your help.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121
    Quote Originally Posted by armeros View Post
    I have a problem on this question.

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

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

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

    I can only conclude from a hint that |A_1| \leq |A_2| \leq ... \leq |A_n| (where |A_i| = the number of elements in A_i). It seems there is no link from this hint to the question. I need to show either there is a function f:A \longrightarrow \mathbb{Z}^+ that is one-to-one, or a function 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 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 a_1, a_2, ..., a_n. Then [tex]a_1+ a_+ ...+ a_n> n(.9)> b.



    Thank you very much in advance.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,384
    Thanks
    1475
    Awards
    1
    Quote Originally Posted by HallsofIvy View Post
    There is no such b!. For any real b> 0, let n= b/0.9. Take n members of (0.9, 1) to be a_1, a_2, ..., a_n. Then [tex]a_1+ a_+ ...+ a_n> n(.9)> b.
    The number b is part of the given. It does exist.
    The mistake, as I pointed out, is that being part of the given b is fixed.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Apr 2009
    Posts
    50
    So, is A_n = A or A = \bigcup\limits_n {A_n } ~?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,384
    Thanks
    1475
    Awards
    1
    Quote Originally Posted by armeros View Post
    So, is A_n = A or A = \bigcup\limits_n {A_n } ~?
    I have told you that must be A = \bigcup\limits_n {A_n } .

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

    The other direction: x \in A\; \Rightarrow \;x > 0\; \Rightarrow \;\left( {\exists k \in \mathbb{Z}^ +  } \right)\left[ {\frac{1}<br />
{k} < x} \right]\; \Rightarrow \;x \in A_k \; \Rightarrow \;x \in \bigcup\limits_n {A_n }
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Apr 2009
    Posts
    50
    Thank you very much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. Show that the sets are countable:
    Posted in the Calculus Forum
    Replies: 13
    Last Post: October 30th 2010, 12:32 PM
  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, 01:59 PM
  4. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  5. Replies: 11
    Last Post: October 11th 2008, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum