2
$\begingroup$

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.

Thanks in advence!

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – John Griffin Aug 30 '17 at 14:09
  • $\begingroup$ @JohnGriffin Thank you, I didn't notice that part was missing, Edited. $\endgroup$ – JaVaPG Aug 30 '17 at 14:11
1
$\begingroup$

$\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$I'm having some trouble reading your arguments. Please don't use symbols that you are yet to define and clearly indicate quantifiers whenever you use variables.

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|$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – JaVaPG Sep 4 '17 at 8:37
  • $\begingroup$ @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$. $\endgroup$ – John Griffin Sep 4 '17 at 12:47
  • 1
    $\begingroup$ @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. $\endgroup$ – John Griffin Sep 4 '17 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.