Results 1 to 7 of 7

Math Help - Countability of Subsets proof

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    86

    Countability of Subsets proof

    Prove: A subset of a countable set is countable.

    I began the proof saying we will assume a set B which is a subset of A where A is countable. By the following proposition, which says,

    " the nonempty set A is countable if and only if there exists a surjection N --> A ",

    there exists a surjection N --> A

    Then I think there exists a surjection from N --> B, which would mean B is countable as well, but I am not sure how to justify this statement. Any help with this proof would be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Here is my thought.

    Let A be the set. Then since A is countable, |A|=n.

    Let B\subseteq A. |B| can, at most, be equal to set A.

    Therefore, |B|\leq n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,712
    Thanks
    1641
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    Let A be the set. Then since A is countable, |A|=n.
    That statement is false. The set A could be infinite.
    Perhaps you are confused as to what countable means.

    There is a surjection \Phi:N\to A. Consider \Phi\left(\Phi^{-1}(B)\right).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    In my books, when we discuss countable infinite, we say countable infinite not countable. So I was under the impression we were dealing with a finite set A.
    Last edited by dwsmith; December 9th 2010 at 03:41 PM. Reason: changed word from he to we
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,712
    Thanks
    1641
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    In my books, when we discuss countable infinite, we say countable infinite not countable. So I was under the impression we were dealing with a finite set A.
    It appears that you have the misfortune of having a non-standard textbook.
    COUNTABLE.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,792
    Thanks
    1532
    A "surjection" From N to X is a function such that, for all x in X, there exist n such that f(n)= x.

    Let x be a member of B. Since B is a subset of A, x is a member of A. Since A is countable, there exist a surjection, f, from N to A, so there exist some n such that f(n)= x. Since this is true for all x in B, there exist a surjection from N to B.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by jstarks44444 View Post
    Prove: A subset of a countable set is countable.

    I began the proof saying we will assume a set B which is a subset of A where A is countable. By the following proposition, which says,

    " the nonempty set A is countable if and only if there exists a surjection N --> A ",

    there exists a surjection N --> A

    Then I think there exists a surjection from N --> B, which would mean B is countable as well, but I am not sure how to justify this statement. Any help with this proof would be appreciated!


    Lemma:

    Every subset of \mathbb{N} is countable.

    Proof of the lemma:

    Let B\subset\mathbb{N}. If B is finite, it is obvious that B is countable.
    If B is infinite, we will find bijection f:B\to\mathbb{N} , with that we will show that B is countable.

    For every x\inB, set of elements of B that are smaller than x is finite.
    Let us now define the function f:B\to\mathbb{N}:

    For every x\inB, f(x) will be the number of elements that are smaller than x.

    f is one-to-one.

    (Proof) If a and b are elements of B and a<b, each element of B that smaller than a is smaller also than b, and a himself isn't smaller that a, but smaller that b. Hence f(b)\geq f(a)+1, so that f(a) \neq f(b).

    f is onto.

    (Proof) We will prove that for every n\in\mathbb{N} have an origin.
    Proving by induction on n.

    B is infinite, hence B isn't empty, therefor B has first element- a_0, it's obvious that f(a_0)=0.
    Suppose that there is origin for n, and we prove that there is origin to n+1, let a be origin for n. B is infinite, set of elements of B that less than a is finite, hence set of elements of B that greater from a is not empty. Let b the first such element. Elements of B that are smaller than b they are elements of B that are smaller than a adding a, so we get that f(b)=n+1, hence n+1 has an origin. We proved that f is onto.

    f is bijective, therefor B\sim\mathbb{N}, hence B countable.

    Noe back to the original theorem:

    Subset of a countable set is countable.


    Proof:

    Let A be countable set. If A is finite, every subset of A is also finite, and therefor countable.
    If A is infinite, A\sim\mathbb{N}. Let B be a subset of A, and we will prove that B is countable. Let f:A\to \mathbb{N} be a bijection, so f {[ B ]} \subseteq \mathbb{N} , and therefor it countable.
    The function g:B\to f{[B]}, so that for all x\in B g(x)=f(x), is bijection, therefor B\sim f{[B]} , the conclusion is that B countable.
    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 proof.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 29th 2010, 09:14 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