Results 1 to 6 of 6

Math Help - Countability proof.

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    94

    Countability proof.

    I need help on proving

    (1) prove that if B A and A is countable, then B is countable

    (2) prove that if B A, A is infinite, and B is finite, then A\B is infinite

    I don't even know where to start... THx
    Last edited by mr fantastic; November 29th 2010 at 11:06 AM. Reason: Re-titled.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2010
    Posts
    94
    I have a theorem which says
    Suppose A is a set. The following statements are equivalent:
    1. A is countable
    2. Either A = empty or there is a function f:z+ -> A that is onto.
    3. There is a function f:A -> z+ that is one-to-one

    I am supposed to use those however I am stuck....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45
    If A is denumerable then A=\{a_1,a_2,\ldots\} . If B=\emptyset then, B is finite . If B\neq \emptyset let n_1 be the least positive integer such that a_{n_1}\in B, let n_2 be the least positive integer such that n_2>n_1 and a_{n_2}\in B ...

    Could you continue?

    Regards.

    Fernando Revilla
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    You can use the equivalent condition #3 to show (1). Namely, suppose B\subseteq A and there exists a one-to-one function f:A\to\mathbb{Z}^+. Consider the restriction of f on B, i.e., the function whose domain is B and that acts just like f on any x\in B. Is this restriction still one-to-one?

    For (2), note that A = B\cup(A\setminus B). What happens when A\setminus B is finite?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2010
    Posts
    94
    I get the (2) part , however could you explain more on (1) part please???
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    could you explain more on (1) part please???
    Whom are you asking? Fernando suggests using condition #2 to prove (1), i.e., that B is countable. Going with #2, let's assume that there is an onto function f:\mathbb{Z}^+\to A and that B is nonempty, i.e., there exists some fixed x_0\in B. I think it is easier to construct another function g:\mathbb{Z}^+\to B as follows:

    g(n)=<br />
\begin{cases}<br />
x_0 & f(n)\notin B\\<br />
f(n) & \text{otherwise}<br />
\end{cases}

    You have to check that indeed g:\mathbb{Z}^+\to B and that g is onto.

    If you are going ti use #3 to show (1), then assume that there exists an f:A\to\mathbb{Z}^+. Consider g(x) such that g(x)=f(x) for x\in B and g(x) is undefined otherwise. You need to show that g:B\to\mathbb{Z}^+ and that g is one-to-one.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Interval Countability proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 12th 2011, 04:29 PM
  2. Countability of Subsets proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: December 10th 2010, 07:19 AM
  3. Inductive Proof of Countability of Algebraic Numbers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 5th 2009, 09:04 AM
  4. Countability Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 21st 2009, 08:56 AM
  5. Proof of countability
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: February 15th 2007, 07:35 PM

Search Tags


/mathhelpforum @mathhelpforum