Results 1 to 3 of 3

Math Help - Cardinality...last one

  1. #1
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Cardinality...last one

    This one is purely for fun. Tell me what you think of this.

    Problem: Call a mapping f:\mathbb{N}\mapsto\mathbb{N} eventually constant if there exists some N\in\mathbb{N} such that if n>N then f(n)=c for some fixed c\in\mathbb{N}. Let \mathfrak{M} be the set of all eventually constant function.

    Find the cardinality of \mathfrak{M}

    Claim: \mathfrak{M}\cong\mathbb{N} ( \cong is used here to denote equipotence)

    Proof: Let F_N\left(c\right)=\left\{f|f:\mathbb{N}\mapsto\mat  hbb{N}\text{ and }f\left(n\right)=c,\text{ }n>N\right\}, and construct a mapping \tau:F_N(c)\mapsto\mathbb{N}^N\times\{c\} by f\mapsto\left(f\left(1\right),\cdots,f\left(N\righ  t),c\right). To see that this mapping is injective assume that

    \tau\left(f\right)=\tau\left(\bar{f}\right)\implie  s\left(f(1),\cdots,f\left(N\right),c\right)=\left(  \bar{f}\left(1\right),\cdots,\bar{f}\left(N\right)  ,c\right) where it clearly follows that f(n)=\bar{f}(n),\text{ }\forall n\in\mathbb{N} where it follows that f=\bar{f}. To see that it's surjective one merely needs to

    know that for any \left(n_1,\cdots,n_N,c\right) the function f\left(k\right)=\begin{cases} n_k & \mbox{if}\quad 1\leqslant k\leqslant N \\ c & \mbox{if}\quad k>N\end{cases} is in F_N and f\mapsto\left(n_1,\cdots,n_N,c\right). The conclusion follows, so F_N(c)\cong \mathbb{N}^N\times\{c\}\cong\mathbb{N}^N where the last equipotence is

    obvious. Thus, for a fixed c all the possible functions that are eventually c is \bigcup_{c\in\mathbb{N}}F_N(c). Now, since each F_N(c) is countable it follows (since the union of countably many countable sets is

    countable) that for a fixed c that \bigcup_{N\in\mathbb{N}}F_N(c) is countable. Lastly, noticing then that \mathfrak{M}=\bigcup_{c\in\mathbb{N}}\bigcup_{N\in  \mathbb{N}}F_N(c) and reapplying the theorem that the union of countably many countably sets is countable

    finishes the argument. \blacksquare


    What do you think? It's late, and maybe I'm paranoid but I feel I am overlooking something.

    Thank you very much for taking the time to read it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    I think you are quite right.
    If I am supposed to prove this, I will bigin with proving that the collection of all finite subset of N is countable, and then the collection of eventually constant mapping is embeded in the cartesian product of the collection of all finite subset of N, and N.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Drexel28 View Post
    This one is purely for fun. Tell me what you think of this.

    Problem: Call a mapping f:\mathbb{N}\mapsto\mathbb{N} eventually constant if there exists some N\in\mathbb{N} such that if n>N then f(n)=c for some fixed c\in\mathbb{N}. Let \mathfrak{M} be the set of all eventually constant function.

    Find the cardinality of \mathfrak{M}

    Claim: \mathfrak{M}\cong\mathbb{N} ( \cong is used here to denote equipotence)

    Proof: Let F_N\left(c\right)=\left\{f|f:\mathbb{N}\mapsto\mat  hbb{N}\text{ and }f\left(n\right)=c,\text{ }n>N\right\}, and construct a mapping \tau:F_N(c)\mapsto\mathbb{N}^N\times\{c\} by f\mapsto\left(f\left(1\right),\cdots,f\left(N\righ  t),c\right). To see that this mapping is injective assume that

    \tau\left(f\right)=\tau\left(\bar{f}\right)\implie  s\left(f(1),\cdots,f\left(N\right),c\right)=\left(  \bar{f}\left(1\right),\cdots,\bar{f}\left(N\right)  ,c\right) where it clearly follows that f(n)=\bar{f}(n),\text{ }\forall n\in\mathbb{N} where it follows that f=\bar{f}. To see that it's surjective one merely needs to

    know that for any \left(n_1,\cdots,n_N,c\right) the function f\left(k\right)=\begin{cases} n_k & \mbox{if}\quad 1\leqslant k\leqslant N \\ c & \mbox{if}\quad k>N\end{cases} is in F_N and f\mapsto\left(n_1,\cdots,n_N,c\right). The conclusion follows, so F_N(c)\cong \mathbb{N}^N\times\{c\}\cong\mathbb{N}^N where the last equipotence is

    obvious. Thus, for a fixed c all the possible functions that are eventually c is \bigcup_{c\in\mathbb{N}}F_N(c). Now, since each F_N(c) is countable it follows (since the union of countably many countable sets is

    countable) that for a fixed c that \bigcup_{N\in\mathbb{N}}F_N(c) is countable. Lastly, noticing then that \mathfrak{M}=\bigcup_{c\in\mathbb{N}}\bigcup_{N\in  \mathbb{N}}F_N(c) and reapplying the theorem that the union of countably many countably sets is countable

    finishes the argument. \blacksquare


    What do you think? It's late, and maybe I'm paranoid but I feel I am overlooking something.

    Thank you very much for taking the time to read it.
    Your proof looks fine. It is, essentially, what I would do. In fact, I spend a wee while writing up here what I would do, posted it, then re-read your post to discover what I had written was, essentially, the same as what you had written. Essentially.

    That said, what I did was instead of defining the function F_N(c) I wasn't explicit with the c. When you are defining your bijection near the top of your proof you can just forget about the c's as taking a cross product with the natural numbers will preserve your countability. This just makes defining everything neater and should, I think, remove a few lines afterwards.
    Last edited by Swlabr; January 5th 2010 at 01:39 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 07:08 AM
  2. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: March 18th 2010, 02:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 05:36 PM
  5. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 02:23 PM

Search Tags


/mathhelpforum @mathhelpforum