Results 1 to 7 of 7

Thread: 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
    10
    Here is my thought.

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

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

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

  3. #3
    MHF Contributor

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

    There is a surjection $\displaystyle \Phi:N\to A$. Consider $\displaystyle \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
    10
    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; Dec 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
    21,742
    Thanks
    2814
    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
    19,729
    Thanks
    3010
    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 $\displaystyle \mathbb{N}$ is countable.

    Proof of the lemma:

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

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

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

    $\displaystyle f$ is one-to-one.

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

    $\displaystyle f$ is onto.

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

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

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

    Noe back to the original theorem:

    Subset of a countable set is countable.


    Proof:

    Let $\displaystyle A$ be countable set. If A is finite, every subset of $\displaystyle A$ is also finite, and therefor countable.
    If $\displaystyle A$ is infinite, $\displaystyle A\sim\mathbb{N}$. Let $\displaystyle B$ be a subset of $\displaystyle A$, and we will prove that $\displaystyle B$ is countable. Let $\displaystyle f:A\to \mathbb{N}$ be a bijection, so $\displaystyle f {[ B ]} \subseteq \mathbb{N} $, and therefor it countable.
    The function $\displaystyle g:B\to f{[B]}$, so that for all $\displaystyle x\in B$ $\displaystyle g(x)=f(x)$, is bijection, therefor $\displaystyle B\sim f{[B]} $, the conclusion is that $\displaystyle 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: Nov 29th 2010, 09:14 AM
  3. Inductive Proof of Countability of Algebraic Numbers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Aug 5th 2009, 09:04 AM
  4. Countability Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 21st 2009, 08:56 AM
  5. Proof of countability
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: Feb 15th 2007, 07:35 PM

Search Tags


/mathhelpforum @mathhelpforum