Notations:
- $\mathbb{F}(\left\{0;1\right \})$ is the set of all finit word on $\left\{0;1\right \}$
- let $m \in\left\{0;1\right \}^{\mathbb{N}} $ then $m|_n$ is the finit word of size n which coincide with the first n character of m
- let $m \in \mathbb{F}(\left\{0;1\right \})$ and $m' \in \mathbb{F}(\left\{0;1\right \})$ or $\in \left\{0;1\right \}^{\mathbb{N}}$ then $m+m'$ is the concatenation of m and m'
- let $m \in \mathbb{F}(\left\{0;1\right \})$ and $m' \in \mathbb{F}(\left\{0;1\right \})$ or $\in \left\{0;1\right \}^{\mathbb{N}}$ then $m<m'$ mean the begin of $m'$ is $m$ and $m \neq m'$
- let $m_1 < m_2 < m_3 ....$, then $\lim\limits_{x \rightarrow +\infty} m_n$ is the word which have for nth character the nth character of $m_n$
Theorem : let $f: \left\{0;1\right \}^{\mathbb{N}} \times \mathbb{N} \rightarrow \left\{0;1\right \} $: such that
$\forall m \in \left\{0;1\right \}^{\mathbb{N}}, \exists n \in\mathbb{N}$ such that $\forall p> n: f(m,p) = f(m,n)$
$\forall m \in \left\{0;1\right \}^{\mathbb{N}}$ $\forall m' \in \left\{0;1\right \}^{\mathbb{N}}$, $\forall n \in \mathbb{N}$: $m|_n= m'|_n \implies f(m,n)=f(m',n)$
let g be:
\begin{array}{} \left\{0;1\right \}^{\mathbb{N}}\rightarrow \left\{0;1\right \}\\ \ m \rightarrow \lim\limits_{n \rightarrow +\infty} f(m,n) \end{array}
well defined by hypothesis one. Third and last hypothesis is: $\forall m \in\left\{0;1\right \}^{\mathbb{N}} $and $ \forall l \in \mathbb{F}(\left\{0;1\right \}): g(l+m)= g(m)$
Then the result: $g$ is constant.
Remarks:
- let's $m$ be a finit word and $k\leq m$ size and $M$ infinite word such that $m<M$ then we introduce the notation $f(m,k)$ equal by definition to $f(M,k)$. Notation well define by the second hypothesis.
- let m and m' be two infinite word then $m|_0 = m'|_0 = \emptyset$. And so by hypotheisis 2: $f(m,0)= f(m',0)$
- the spirit of the first two propriety is to abstract the concept of a function from $ \left\{0;1\right \}^{\mathbb{N}}$ to $\left\{0;1\right \} $ that can see a finish amont of the entry word in a finite time, have an infinite time to give its answer, but after a finite time its answer need to stay the same.
- strangly we don't need f computable as a supplementary hypothesis, so you can say i'm on wrong forum lol.
proof: by absurd, let's suppose g is not constant. Then let's prove this by recursion: $\exists m_1,m_2,m_3.... $all in $\mathbb{F}(\left\{0;1\right \})$ such that:
- $m_1 < m_2 < m_3...$
- for all n $\in N$ we note $x_n$ the size of $m_n$ then $f(m_n,x_n -1)\ne f(m_n,x_n)$
construction of $m_1$: there is m and m' $\in \left\{0;1\right \}^{\mathbb{N}}$ such that $g(m) \neq g(m')$ meaning $\exists n $ such that $\forall k\geq n: f(m,k)\neq f(m',k)$ we take n minimum whose verify the last proposition. n is at least one cause $f(m,0) = f(m',0)$. Then as $f(m,n-1) = f(m', n-1)$ but $f(m,n) \neq f(m', n)$ we deduce $[f(m,n) \neq f(m,n-1)$ or $f(m',n) \neq f(m',n-1)]$. Let's say $f(m,n) \neq f(m,n-1)$. Now we take $m_1= m|_n$ and $x_1 = n$ ($= m_1$ size).
construction of $m_n$: let h be:
\begin{array}{} \left\{0;1\right \}^{\mathbb{N}}\rightarrow \left\{0;1\right \}\\ \ m \rightarrow \lim\limits_{n \rightarrow +\infty} f(m_{n-1}+m,n) \end{array}
as we can see: $\forall m \in \left\{0;1\right \}^{\mathbb{N}}: h(m) = g(m_{n-1}+m) = g(m)$ by the last hypothese, so $h=g$ and as $g$ non constante so is $h$. There is m and m' $\in \left\{0;1\right \}^{\mathbb{N}}$ such that $h(m) \neq h(m')$ meaning $\exists p $ such that $\forall k\geq p: f(m_{n-1}+m,k)\neq f(m_{n-1}+m',k)$ we take p minimum whose verify the last proposition. p is at least $m_{n-1}$ size $+ 1$ cause $\forall k<m_{n-1}$ size + 1$: f(m_{n-1}+m,k)=f(m_{n-1}+m',k)=f(m_{n-1},k)$. Then as $f(m_{n-1}+m,p-1) = f(m_{n-1}+m', p-1)$ but $f(m_{n-1}+m,p) \neq f(m_{n-1}+m', p)$ we deduce $[f(m_{n-1}+m,p) \neq f(m_{n-1}+m,p-1)$ or $f(m_1+m',p) \neq f(m_{n-1}+m',p-1)]$. Let's say $f(m_{n-1}+m,p) \neq f(m_{n-1}+m,p-1)$. Now we take $m_n= (m_{n-1}+m)|_p$ and $x_n = p$ ($=m_n$ size)
Conclusion: by recursion we made our construction. Let M= $\lim\limits_{x \rightarrow +\infty} m_n$ then: $\forall n\in \mathbb{N}: f(m,x_n-1) = f(m_n,x_n-1) \neq f(m_n,x_n) = f(m,x_n)$ and so M violate the first hypothesis. Contradiction, by the absurd g is constant.
thank you for reading
edited: number -> word