Results 1 to 2 of 2

Math Help - mapping

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    12

    mapping

    Hi can anybody help me here,
    i need help explaining the theory that

    The set of all finite subsets of the natural numbers is countable.
    i need to explain this by constructing an injective mapping. I looked on wikipedia but it was not too helpful.
    thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by math_lete View Post
    Hi can anybody help me here,
    i need help explaining the theory that

    The set of all finite subsets of the natural numbers is countable.
    i need to explain this by constructing an injective mapping. I looked on wikipedia but it was not too helpful.
    thanks
    This takes work if you are willing to avoid choice. There is a theorem which says that a countable union of at most countable sets is at most countable. The proof of this results depends on choice. Instead there is a weaker result.

    Theorem: Let A: \mathbb{N}\to S be a sequence such that A_n is at most countable. And let a: \mathbb{N}\to T be a sequence such that a_n enumerates A_n i.e. a_n: \mathbb{N} \to A_n is a surjection. Then \bigcup A[\mathbb{N}] is at most countable (i.e. A_0\cup A_1\cup ... is at most countable).

    Proof: Define the function f: \mathbb{N}\times \mathbb{N}\to \bigcup A[\mathbb{N}] as f(x,y) = a_x(y). The function f is onto and so f[ \mathbb{N}\times \mathbb{N} ] = \bigcup A[\mathbb{N}] is at most countable since the image of a countable set is at most countable (here we are using the result that \mathbb{N}\times \mathbb{N} is countable).

    Let N be the set of all finite subsequences of \mathbb{N}. We prove a stronger result.

    Theorem: N is countable.

    Proof: Let \mathbb{N}^n represent all functions n\to \mathbb{N}. Define A: \mathbb{N} \to S by A_n = \mathbb{N}^n where S = \mathcal{P}(\mathbb{N}\times \mathbb{N}). Then \bigcup A[\mathbb{N}] = N. Therefore by above if we can produce a: \mathbb{N}\to T then N would be countable. Let g: \mathbb{N}\to \mathbb{N}\times \mathbb{N} be any bijection - we know one such exists. Define a: \mathbb{N}\to N in following way. Define a_1 to be the set of all one-element sequences i.e. a_1(k) is the function a_1(k): 1 \to \mathbb{N} defined by a_1(k)(0) = k. Define a_{n+1} recursively at a point k by first letting g(k)=(k_1,k_2) and then a_{n+1}(k) to be the n+1 element sequence whose first n elements are the terms of the sequence a_n(k_1) and the n+1 element is k_2. It remains to show that a_n is an enumeration of A_n for n\geq 1. Of course we avoided a_0 since that is the empty sequence (empty sequence) and does not alter the cardinality in question. Therefore, N is at most countable. There is just one last step and that is to find such a set T which contains all these a_n to complete the proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. mapping
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: April 10th 2011, 12:14 AM
  2. mapping
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: April 5th 2011, 06:16 PM
  3. Mapping
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: March 10th 2011, 01:52 AM
  4. Complex open mapping & conformal mapping problems.
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 22nd 2011, 07:26 AM
  5. Mapping: one-to-one and onto
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 6th 2008, 07:41 PM

Search Tags


/mathhelpforum @mathhelpforum