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 S such that S \subseteq N. Then there exists an injective function f: S \longrightarrow N by definition. More specifically, define f as:
    f(s_i) = i, i \in N

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

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

    Otherwise, if such an element i_n does not exist, f will not only be an injection but also a surjection, since for all elements i \in N, there exists an s_i \in S such that f(s_i) = i. Since f is both injective and surjective, it is a bijection, implying that 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 \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