Results 1 to 14 of 14

Thread: Show countable sets.

  1. #1
    Junior Member
    Joined
    Apr 2009
    Posts
    55
    Thanks
    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.
    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 $\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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2009
    Posts
    55
    Thanks
    1
    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
    21,782
    Thanks
    2824
    Awards
    1
    Quote Originally Posted by armeros View Post
    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 } ~?$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2009
    Posts
    55
    Thanks
    1
    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!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    Awards
    1
    Quote Originally Posted by armeros View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Apr 2009
    Posts
    55
    Thanks
    1
    Quote Originally Posted by Plato View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    Awards
    1
    $\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.
    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
    55
    Thanks
    1
    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
    $

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

  10. #10
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,781
    Thanks
    3030
    Quote Originally Posted by armeros View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    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 $\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.
    Follow Math Help Forum on Facebook and Google+

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

  13. #13
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    Awards
    1
    Quote Originally Posted by armeros View Post
    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 } $
    Follow Math Help Forum on Facebook and Google+

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

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum