Results 1 to 2 of 2

Thread: 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
    10
    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 $\displaystyle A: \mathbb{N}\to S$ be a sequence such that $\displaystyle A_n$ is at most countable. And let $\displaystyle a: \mathbb{N}\to T$ be a sequence such that $\displaystyle a_n$ enumerates $\displaystyle A_n$ i.e. $\displaystyle a_n: \mathbb{N} \to A_n$ is a surjection. Then $\displaystyle \bigcup A[\mathbb{N}]$ is at most countable (i.e. $\displaystyle A_0\cup A_1\cup ... $ is at most countable).

    Proof: Define the function $\displaystyle f: \mathbb{N}\times \mathbb{N}\to \bigcup A[\mathbb{N}]$ as $\displaystyle f(x,y) = a_x(y)$. The function $\displaystyle f$ is onto and so $\displaystyle 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 $\displaystyle \mathbb{N}\times \mathbb{N}$ is countable).

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

    Theorem: $\displaystyle N$ is countable.

    Proof: Let $\displaystyle \mathbb{N}^n$ represent all functions $\displaystyle n\to \mathbb{N}$. Define $\displaystyle A: \mathbb{N} \to S$ by $\displaystyle A_n = \mathbb{N}^n$ where $\displaystyle S = \mathcal{P}(\mathbb{N}\times \mathbb{N})$. Then $\displaystyle \bigcup A[\mathbb{N}] = N$. Therefore by above if we can produce $\displaystyle a: \mathbb{N}\to T$ then $\displaystyle N$ would be countable. Let $\displaystyle g: \mathbb{N}\to \mathbb{N}\times \mathbb{N}$ be any bijection - we know one such exists. Define $\displaystyle a: \mathbb{N}\to N$ in following way. Define $\displaystyle a_1$ to be the set of all one-element sequences i.e. $\displaystyle a_1(k)$ is the function $\displaystyle a_1(k): 1 \to \mathbb{N}$ defined by $\displaystyle a_1(k)(0) = k$. Define $\displaystyle a_{n+1}$ recursively at a point $\displaystyle k$ by first letting $\displaystyle g(k)=(k_1,k_2)$ and then $\displaystyle a_{n+1}(k) $ to be the $\displaystyle n+1$ element sequence whose first $\displaystyle n$ elements are the terms of the sequence $\displaystyle a_n(k_1)$ and the $\displaystyle n+1$ element is $\displaystyle k_2$. It remains to show that $\displaystyle a_n$ is an enumeration of $\displaystyle A_n$ for $\displaystyle n\geq 1$. Of course we avoided $\displaystyle a_0$ since that is the empty sequence (empty sequence) and does not alter the cardinality in question. Therefore, $\displaystyle N$ is at most countable. There is just one last step and that is to find such a set $\displaystyle T$ which contains all these $\displaystyle 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: Apr 10th 2011, 12:14 AM
  2. mapping
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: Apr 5th 2011, 06:16 PM
  3. Mapping
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Mar 10th 2011, 01:52 AM
  4. Complex open mapping & conformal mapping problems.
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Feb 22nd 2011, 07:26 AM
  5. Mapping: one-to-one and onto
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Nov 6th 2008, 07:41 PM

Search Tags


/mathhelpforum @mathhelpforum