Cardinality...last one

**Drexel28** · January 4th 2010, 09:38 PM

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.

**Shanks** · January 4th 2010, 10:34 PM

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.

**Swlabr** · January 5th 2010, 01:29 AM

Originally Posted by Drexel28

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.

Thread: Cardinality...last one

LinkBack

Thread Tools

Display

Cardinality...last one

Similar Math Help Forum Discussions

Cardinality

Cardinality of R, [0,1], R^2, [0,1] x [0,1]

Cardinality

Cardinality

Cardinality

Search Tags