# Cardinality...last one

• Jan 4th 2010, 09:38 PM
Drexel28
Cardinality...last one
This one is purely for fun. Tell me what you think of this.

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

Find the cardinality of $\displaystyle \mathfrak{M}$

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

Proof: Let $\displaystyle 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 $\displaystyle \tau:F_N(c)\mapsto\mathbb{N}^N\times\{c\}$ by $\displaystyle f\mapsto\left(f\left(1\right),\cdots,f\left(N\righ t),c\right)$. To see that this mapping is injective assume that

$\displaystyle \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 $\displaystyle f(n)=\bar{f}(n),\text{ }\forall n\in\mathbb{N}$ where it follows that $\displaystyle f=\bar{f}$. To see that it's surjective one merely needs to

know that for any $\displaystyle \left(n_1,\cdots,n_N,c\right)$ the function $\displaystyle 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 $\displaystyle F_N$ and $\displaystyle f\mapsto\left(n_1,\cdots,n_N,c\right)$. The conclusion follows, so $\displaystyle F_N(c)\cong \mathbb{N}^N\times\{c\}\cong\mathbb{N}^N$ where the last equipotence is

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

countable) that for a fixed $\displaystyle c$ that $\displaystyle \bigcup_{N\in\mathbb{N}}F_N(c)$ is countable. Lastly, noticing then that $\displaystyle \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. $\displaystyle \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.
• Jan 4th 2010, 10:34 PM
Shanks
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.
• Jan 5th 2010, 01:29 AM
Swlabr
Quote:

Originally Posted by Drexel28
This one is purely for fun. Tell me what you think of this.

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

Find the cardinality of $\displaystyle \mathfrak{M}$

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

Proof: Let $\displaystyle 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 $\displaystyle \tau:F_N(c)\mapsto\mathbb{N}^N\times\{c\}$ by $\displaystyle f\mapsto\left(f\left(1\right),\cdots,f\left(N\righ t),c\right)$. To see that this mapping is injective assume that

$\displaystyle \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 $\displaystyle f(n)=\bar{f}(n),\text{ }\forall n\in\mathbb{N}$ where it follows that $\displaystyle f=\bar{f}$. To see that it's surjective one merely needs to

know that for any $\displaystyle \left(n_1,\cdots,n_N,c\right)$ the function $\displaystyle 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 $\displaystyle F_N$ and $\displaystyle f\mapsto\left(n_1,\cdots,n_N,c\right)$. The conclusion follows, so $\displaystyle F_N(c)\cong \mathbb{N}^N\times\{c\}\cong\mathbb{N}^N$ where the last equipotence is

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

countable) that for a fixed $\displaystyle c$ that $\displaystyle \bigcup_{N\in\mathbb{N}}F_N(c)$ is countable. Lastly, noticing then that $\displaystyle \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. $\displaystyle \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 $\displaystyle F_N(c)$ I wasn't explicit with the $\displaystyle c$. When you are defining your bijection near the top of your proof you can just forget about the $\displaystyle 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.