Prove the set $A=\{ f | f:\mathbb{N}\to\mathbb{N} \mathrm{\;is\;a\;function}\}$ is infinite.

Question

I am trying to prove that the set $A=\{ f | f:\mathbb{N}\to\mathbb{N} \mathrm{\;is\;a\;function}\}$ is infinite. I believe that the way I am supposed to go about doing this is by proving $A$ has an infinite subset. I developed a proof, but I am unsure if I did it correctly:

Proof: Fix $A=\{ f | f:\mathbb{N}\to\mathbb{N} \mathrm{\;is\;a\;function}\}$. Note the function $f(n)=2n$ is in $A$. Next, consider the set $S=\{f(n)=2n | n \in \mathbb{N}\}$. Note $S$ consists of functions where $f:\mathbb{N}\to\mathbb{N}$, so $S$ is a subset of $A$. Also, note $S$ is the set of even naturals, and there is an infinite amount of even naturals, so $S=\{2, 4, 6, ...\}$, and $S$ is an infinite set. Thus, $A$ must be infinite, because $A$ has an infinite subset. (END)

I am not sure if my justification for the infinity of the set $S$ is enough for the argument, but I am not sure how to go about proving that the subset is going to be infinite if this is not a valid way. Any tips would be greatly appreciated. Thanks!

Answer 1

In this problem we are considering functions $f$ from $\Bbb N$ to $\Bbb N$. This is different than considering the output of such functions, which are natural numbers. To exhibit an infinite subset of $A$, why not try the following

I think it's safe to assume we know that $\Bbb N$ is infinite. For $n\in\Bbb N$, consider the function $f_n:\Bbb N\to\Bbb N$ with $f_n(x):=\begin{cases}1\qquad x=n\\0\qquad x\neq n\end{cases}$. Then each $f_n$ is in $A$ and $f_n\neq f_m$ whenever $n\neq m$. So we get an infinite subset $\{f_n\}_n$ of $A$, so $A$ must be infinite.

Answer 2

The set $S= \{f\}$ is a completely different thing then the set $T=\{f(x)|x\in A\}$.

$f$ is a single thing; the function $f$. $S$ is a finite set and $|S| = 1$.

$T=\{f(x)|x\in A\}$ is a set of output value of the function.

So $S = \{f|f(x) = 2x\}$ has one value; the function $f(x) = 2x$. $|S|=1$. It is not the set of even integers. $T=\{f(x)=2x|x \in \mathbb N\}$ is the set of even natural numbers. $|T|=|\mathbb N|$. $\{f|f(x)=2x\} = \{f(x)=2x|x \in \mathbb N\}$.

But you are correct that the easiest way is to show there is an infinite subset.

Consider $f_2(x) = 2x$ and $f_3(x) = 3x$ and $f_k(x) = kx$ and the set of functions $S=\{f_k|f_k(x) = kx; k\in \mathbb N\}$. Now $S$ is not $\mathbb N$ but is is easy to show $S$ is one-to-one with $\mathbb N$ ($\phi(k) = f_k$ is very clearly a bijection).

So $S\subset A$ and $|S| = |\mathbb N|$ so $S$ is infinite and $A$ is infinite.

Answer 3

Why not let $f_n(x)=nx$. It is easy to see $f_n\not =f_m$ for $n\not=m$. Then $f_n\in A\; \forall n\in \mathbb N$. (Technically, we have an injection $i:\mathbb N\to A$, with $i(n)=f_n$). Thus $\lvert A\rvert \ge\lvert \mathbb N\rvert $.

As to your proof, you got sidetracked, considering just the function $f_2$...