# Proof $[h]_r$ is infinite countable.

I have the following question :

Defintion : $R \subseteq \mathbb{N}^\mathbb{N} \times \mathbb{N}^\mathbb{N}$ two functions $f_1,f_2 \in \mathbb{N}^\mathbb{N}$ are almost identical if $A \subseteq \mathbb{N}$ (A is infinite). doesn't exist such that for all $i\in A$ applies $f_1(i)\neq f_2(i)$
if $f_1,f_2 \in$ are almost identical then $(f_1,f_2)\in R$

• Proof $h\in \mathbb{N}^\mathbb{N}$ proof $[h]_r$ is infinite countable.

What I did

I try to show an injective f:$\mathbb{N} \rightarrow [h]_r$ and also an injective $g:[h]_r \rightarrow \mathbb{N}$ and from cantor bernstein theorem there's a function that is injective and subjective so we know $[h]_r$ is infinite countable.

I thought of function $f$ as following since $(i\in \mathbb{N})$ $[h]_r=\{{j_i\in \mathbb{N}^\mathbb{N} |(h,j_i)\in R\}}$

$$f(i)=j_i (i\in \mathbb{N})$$

injective :

let $i,k \in \mathbb{N}$ such that $k\neq j$ then $f(i)=j_k\neq j_j=f(j)$ since there's $n\in \mathbb{N}$ that $j_k(n)\neq j_i(n)$.

$g:[h]_r\rightarrow \mathbb{N}$

for all $a,b \in [h]_r$ exists $i\in \mathbb{N}$ such that $a(i)\neq b(i)$ let $m=\max\{{i | a(i)\neq b(i) \}}$

for all $a\in [h]_r$ $$f(a)=p_1^a(1)*...*p_m^a(m)$$ while $p_1=2,p_2=3,..$ (prime numbers)

injective

from the prime number theorem each number has a unique way to be written.

$g,f$ are injective so from cantor bernstein theorem we know that $[h]_r$ is infinite countable.

I'm not sure about if i defined function $f$ correctly, I'd like to have an option about it.

• The definition of almost identical doesn't make sense. Taking $A$ to be the empty set shows that every pair of functions are almost identical. If we only consider nonempty $A$, then two functions are almost identical iff they are identical. I suspect you only want to consider infinite subsets $A$. – John Griffin Aug 30 '17 at 14:09
• @JohnGriffin Thank you, I didn't notice that part was missing, Edited. – JaVaPG Aug 30 '17 at 14:11


Your approach is correct though. We show $|\NN|\le|[h]|$ and $|[h]|\le|\NN|$.

The first inequality is simple enough. Define $f:\NN\to[h]$ as follows. For each $k\in\NN$, define $f(k):\NN\to\NN$ by $$f(k)(n) = \begin{cases} h(n)+1 & \text{if}\ n=k, \\ h(n) & \text{if}\ n\ne k. \end{cases}$$ This mapping is well-defined because for each $k\in\NN$ the function $f(k)$ is almost identical to $h$ (i.e., $f(k)\in[h]$ for every $k\in\NN$). The function $f$ is an injection because $k\ne j$ implies $$f(k)(j)=h(j)\ne h(j)+1=f(j)(j),$$ which shows that the functions $f(k)$ and $f(j)$ are distinct.

It remains to prove $|[h]|\le|\NN|$. It's not immediately clear to me how one would define an injection from $[h]$ into $\NN$. However, note that every function in $[h]$ must agree with $h$ at all but finitely many points. Thus to each element $a\in[h]$ we can find a finite subset $N_0$ of $\NN$ and a function $z:N_0\to\ZZ$ such that $$a(n) = \begin{cases} h(n)+z(n) & \text{if}\ n\in N_0, \\ h(n) & \text{if}\ n\not\in N_0. \end{cases}$$ There are only countably many finite subsets of $\NN$ and, for each finite subset $N_0$ of $\NN$, there are only countably many functions from $N_0$ into $\ZZ$. This shows that $[h]$ is countable.

To write this argument formally, we let $F(\NN)$ denote the set of finite subsets of $\NN$ and define a function $$g:[h]\to\bigcup_{N_0\in F(\NN)}\ZZ^{N_0}$$ as follows. Given $a\in [h]$, there exists a finite set $N_0$ of natural numbers such that $a(n)\ne h(n)$ iff $n\in N_0$. We define $g(a):N_0\to\ZZ$ by $g(a)(n)=a(n)-h(n)$. Then $g(a)\in\ZZ^{N_0}$ so that $g$ is well-defined.

To see that $g$ is one-to-one, suppose $a\ne b$ are in $[h]$. We have two cases. If there exists $n\in\NN$ such that $a(n)\ne h(n)$ and $b(n)=h(n)$ (or similarly $a(n)=h(n)$ and $b(n)\ne h(n)$), then the functions $g(a)$ and $g(b)$ are defined on different sets and thus $g(a)\ne g(b)$. Otherwise, suppose $a$ and $b$ differ from $h$ at the same points. Since $a\ne b$, there exists $n\in\NN$ such that $a(n)\ne b(n)$. Consequently $g(a)(n)=a(n)-h(n)\ne b(n)-h(n)=g(b)(n)$, which proves $g(a)\ne g(b)$. Therefore $g$ is an injection.

This shows that $$|[h]| \le \left|\bigcup_{N_0\in F(\NN)}\ZZ^{N_0}\right|.$$ Since $\cup_{N_0\in F(\NN)}\ZZ^{N_0}$ is a countable union of countable sets, we conclude that $|[h]| \le |\NN|$.

• Thank you very much for your answer, sorry for late respond. I'm a bit confused from the $f$ function you defined, as you said we need injection function such that $f: \mathbb{N}\rightarrow [h]_r$ but from your definition your I understand that you defined group of functions ($f(i)(k)=f(1)(k),f(2)(k),...$ each $i \in \mathbb{N}$ represent a different function, I don't understand why, the range of $f$ is the natural numbers meaning that we need to define one function $f$ such that for each $i\in \mathbb{N}, f(i)=a\in [h]_r$ can you explain? – JaVaPG Sep 4 '17 at 8:37
• @JaVaPG The function $f$ is a mapping from the natural numbers to the set of functions almost identical to $h$. Thus, for each $i\in\mathbb{N}$, the evaluation $f(i)$ of $f$ at $i$ needs to be a function almost identical to $h$. How do we define $f(i)$? Well we need to specify which natural number $f(i)(n)$ is for each $n\in\mathbb{N}$. Since we want $f(i)$ to be almost identical to $h$ (and all different for different $i$), we take $f(i)(n)=h(n)$ for all $n\ne i$ and $f(i)(i)=h(i)+1$. – John Griffin Sep 4 '17 at 12:47
• @JaVaPG If you don't like the double function evaluation notation, we could define $a_i:\mathbb{N}\to\mathbb{N}$ for each $i$ by $$a_i(n) = \begin{cases} h(i)+1 & \text{if}\ i=n,\\ h(n) & \text{otherwise}. \end{cases}$$ Then each $a_i$ is almost identical to $h$, so $a_i\in[h]$. Now define $f:\mathbb{N}\to[h]$ by $f(i)=a_i$, and note that $f$ is injective. Try convincing yourself that these two arguments are the same. – John Griffin Sep 4 '17 at 12:49