Convention: $0\in\mathbb{N}$. Find the cardinality of
a) $A=\{f:\mathbb{N}\to \mathbb{N}\mid \forall n, f(n)=f(n+1)+f(n+2)\}$
b) $B=\{f:\mathbb{N}\to\mathbb{N}\mid\forall n, f(n)\ge f(n+1)\}$
My attempt:
a) We have $|A|\le |\mathbb{N}^{\mathbb{N}}|=2^{\omega}$. Now, I'm looking for some set $C\subseteq A$ with $C=2^{\omega}$, but seems to be tricky.
b) Again, $|B|\le 2^{\omega}$. All constant functions are contained in $B$ as well, so $\omega\le |B|$, but this does not help. I believe $C=\{f:\mathbb{N}\to \{0,1\}\mid f(0)=1\}\subseteq B$. Again, $|C|\le 2^{\omega}$. Define $\phi: \{0,1\}^{\mathbb{N}}\to C: f\mapsto \phi(f)$, where $\phi(f)(n)=f(n)$ if $f(0)=1$ and $\phi(f)(n)=1$ otherwise. This function is not injective if the latter assignment is defined. How can I change that?
Thanks.
It is true that $|A|\leq |\mathbb{N}^\mathbb{N}|=2^{\aleph_0}$, but it is possible to have smaller cardinality.
Notice that the condition given for a function $g$ in the set $B$ implies that the function is non-increasing. So, each of these functions is completely determined by the first value ($g(0)$) and the inputs where it changes value for something smaller (i.e., the values $n$ where $g(n)>g(n+1)$. Therefore, the functions $g$ is completely determined by a finite sequence of natural numbers, and again there are only $\aleph_0$ such sequences, thus $|B|\leq\aleph_0$. Also, the choice for $g(0)$ can be any natural number, so we have $|B|\geq \aleph_0$, and by Cantor-Bernstein, $|B|=\aleph_0$.
The set $A$ is a bit trickier. Note that the condition given for a function $f$ in the set $A$ implies that every value $f(n)$ is completely determined by $f(n-1)$ and $f(n-2)$, via the equation $$f(n+2)=f(n)-f(n+1).$$ Hence, $f$ is completely determined by the values $f(0)$ and $f(1)$, because we then have:
$$\begin{align*}f(2)&=f(0)-f(1)\\ f(3)&=f(1)-f(2)=f(1)-(f(0)-f(1)\\ &=-f(0)+2f(1)\\ f(4)&=2f(0)-3f(1)\\ f(5)&=-3f(0)+5f(1)\\ \vdots\ \ &=\vdots\ \ \end{align*}$$
Since there are at most $\aleph_0$ possible pairs of natural number that can be equal to $f(0),f(1)$, we then have $|A|\leq \aleph_0$.
There is still one more question. Notice that the equations given above may be negative depending on the choice of $f(0)$ and $f(1)$. Since a function $f\in A$ has domain $\mathbb{N}$ and codomain also $\mathbb{N}$, we have to make sure that $f(n+2)$ is always non-negative.
The value $f(n+2)$ can be calculated as:
$$f(n+2)=(-1)^{n+2}(F_n\cdot f(0)- F_{n+1}\cdot f(1))$$ where $F_n$ is the $n$-th term in the Fibonacci sequence. [It can be shown by induction, but I am not explaining this here]
So, if for any large even number $n$ we have $f(n+2),f(n+3)\geq 0$, this implies $$\begin{align*} f(n+2)&=F_n\cdot f(0)-F_{n+1}\cdot f(1)\geq 0\\ f(n+3)&=-F_{n+1}\cdot f(0)+F_{n+2}\cdot f(1)\geq 0\end{align*}$$ obtaining
$$\begin{align*} F_n\cdot f(0)\geq F_{n+1}\cdot f(1)\ , & &F_{n+2}\cdot f(1)\geq F_{n+1}\cdot f(0).\end{align*}$$ Dividing respectively by $f(0)$ and $f(1)$, we obtain that for every even number $n$, $$\begin{align*}\dfrac{F_n}{F_{n+1}}\geq \dfrac{f(1)}{f(0)}\geq \dfrac{F_{n+1}}{F_{n+2}} & &\text{and}& &\dfrac{F_{n+2}}{F_{n+1}}\geq \dfrac{f(0)}{f(1)} \geq \dfrac{F_n}{F_{n+1}}.\end{align*}$$ This is a contradicton since both sequences $\{F_n/F_{n+1}:n\in\mathbb{N}\}$ and $\{F_{n+1}/F_{n}:n\in\mathbb{N}\}$ are monotone and non-constant.
Hence, the only possibility for the condition $f(n)=f(n+1)+f(n+2)$ to hold for every $n\in\mathbb{N}$ is to have $f(0)=f(1)=0$, and so the set $A$ consists only of one element, the constant function $f(n)=0$. Therefore, $|A|=1$.