Results 1 to 2 of 2

Thread: Prove every subset of N is either finite or countable

  1. #1
    Member Last_Singularity's Avatar
    Dec 2008

    Prove every subset of N is either finite or countable

    Please critique my attempt at this proof below: if there is an alternative approach that is better or if there are gaps in the logic of my method, please point them out - thanks!

    "Prove every subset of N is either finite or countable":
    Proof : Consider a nonempty set of nonnegative integers $\displaystyle S$ such that $\displaystyle S \subseteq N$. Then there exists an injective function $\displaystyle f: S \longrightarrow N$ by definition. More specifically, define $\displaystyle f$ as:
    $\displaystyle f(s_i) = i, i \in N$

    This allows us to use $\displaystyle f$ to enumerate the elements of $\displaystyle S$ by their size: letting $\displaystyle s_1$ be the smallest element of $\displaystyle S$, $\displaystyle s_2$ be the smallest element of $\displaystyle S \backslash \{ s_1 \}$ and so forth inductively until we exhaust all the elements of $\displaystyle S$. Using $\displaystyle f$, we would have paired up $\displaystyle s_1$ with $\displaystyle 1 \in N$, $\displaystyle s_2$ with $\displaystyle 2 \in N$ and so forth.

    If there exists an element $\displaystyle i_n$ of $\displaystyle N$ where $\displaystyle f^{-1}$ is undefined, as in, no element of $\displaystyle S$ maps to $\displaystyle i$, then $\displaystyle S \subset N$ and $\displaystyle card(S) < card(N)$, implying that $\displaystyle S$ is finite. More specifically, $\displaystyle S$ would have a finite cardinality of $\displaystyle i_n - 1$

    Otherwise, if such an element $\displaystyle i_n$ does not exist, $\displaystyle f$ will not only be an injection but also a surjection, since for all elements $\displaystyle i \in N$, there exists an $\displaystyle s_i \in S$ such that $\displaystyle f(s_i) = i$. Since $\displaystyle f$ is both injective and surjective, it is a bijection, implying that $\displaystyle card(S) = card(N)$. So by definition, if there exists a bijection between a set and the natural numbers, that set is countably infinite in cardinality.
    Last edited by Last_Singularity; Dec 31st 2008 at 07:35 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Nov 2008
    Yeah that's good.
    Furthermore, using that $\displaystyle \mathbb{N}$ is a well-ordered set, your proof doesn't need the axiom of choice.

    You could make it shorter considering "Prove that a non-finite subset of N is countable" instead of "Prove every subset of N is either finite or countable", but that changes almost nothing.
    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. Replies: 2
    Last Post: Nov 11th 2010, 04:56 AM
  3. Subset of A countable Set is countable
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: Nov 2nd 2008, 12:47 PM
  4. Replies: 1
    Last Post: Oct 15th 2008, 11:34 AM
  5. Replies: 4
    Last Post: Oct 11th 2008, 01:42 PM

Search tags for this page

Search Tags

/mathhelpforum @mathhelpforum