Muestran que ambos conjuntos son infinitos

Question

Supongamos que $\lbrace f_i : i \in \Bbb N\rbrace \subseteq \lbrace 0, 1\rbrace^{\Bbb N}$. Demostrar que existe $g \in \lbrace 0,1\rbrace^{\Bbb N}$ tal que para cada $i \in \Bbb N$, el conjunto de $\lbrace n\in\Bbb N : g(n) = f_i(n) \rbrace$ y el conjunto de % de $\lbrace n\in\Bbb N : g(n) \ne f_i(n) \rbrace$ tanto infinito.

He intentado atacar el problema desde diferentes ángulos pero simplemente no pude encontrar una conveniente función $g$.

Estoy buscando solo de orientación o de consejos. Por favor no publicar respuestas completos.

Gracias.

Answer 1

Sugerencia: Hacer $g(4 \cdot k+1) = f_0(4 \cdot k + 1)$...

y $g(4 \cdot k + 3) \ne f_0(4 \cdot k + 3)$.

...

Esto satisface la condición para $f_0$ y todos los números están todavía disponibles.

¿Ves cómo continuar?

Answer 2

Cada positivos $n$ puede escribirse de forma única como $(\sum_{i=1}^k i)+j;0\le j\le k$.

A fin de utilizar que.

O si desea utilizar cualquier bijection, $k$, entre el$\mathbb N\times \mathbb N$$\mathbb N$.

Para cada $i$, hay un número infinito de $k(m,i)=n$. Si dejamos $g (n=k(m,i))=f_i (n)$ habrá un infinito tal $n$, ($k(\mathbb N\times\{i\}))$ va a satisfacer.

Sólo necesita expandir esto a la infinita desigualdad conjuntos.

Deje $j:\{0,1\}\times \mathbb N^2\rightarrow \mathbb N$ ser un bijection.

Definir $g (j(0,k,m))=f_m (j(0,k,m))$ por cada $m$ habrá infinitos valores de $g (n)=f_m (n)$

Definir $g (j(1,k,m)= f_m (j(1,k,m))+1\mod 2$. A continuación, para cada una de las $m$ habrá infinitos valores de $g (n)\ne f_m (n)$.

====

Si desea definir una precisa $g$ tener en cuenta.

$j: \{0,1\}\times \mathbb N \times \mathbb N\rightarrow \mathbb N$ través $j(a, k,m) = 2((m-1) + \sum_{i=1}^{i+(m-1)} i)- a$.

$j$ puede ser demostrado ser un bijection[$*$].

Definir $g(n = j(a,k,m)):= f_m(n)+ a\mod 2$.

Para cada una de las $m$ habrá un número infinito de $A_m = \{n| n= f(0,k,m); k \in \mathbb N\}$ (todos los elementos de a $A_m$ están aún por el camino) y para todos $n \in A_m$, $g(n) = f_m(n)$. Y para cada una de las $m$ habrá un número infinito de $B_m = \{n| n = f(1,k,m); k \in N\}$ (todos los elementos de a $B_m$ será raro por cierto) y para todos $n \in B_m$, $g(n) \ne f_m(n)$.

[$*$] Que $j: \{0,1\}\times \mathbb N \times \mathbb N\rightarrow \mathbb N$ debería ser obvio. $k \ge 1; m-1 \ge 0;m,n \in \mathbb N$ $k + (m-1) \ge 1$ $\sum_{i= 1}^{k+ (m-1)} i \in \mathbb N$ $m-1 \ge 0$ $(m-1) +\sum_{i= 1}^{k+ (m-1)}i \in \mathbb N$ $(m-1) +\sum_{i= 1}^{k+ (m-1)}i \ge 1$ $a \le 1; a\in \mathbb N$ $j(a, k,m) = 2((m-1) + \sum_{i=1}^{i+(m-1)} i)- a\ge 1$ y es un número natural.

Surjective: Si $n \in \mathbb N$ entonces $n$ es incluso y $n = 2j$ naturales $c$ o $n$ es impar y $n = 2c - 1$ naturales $c$.

La secuencia de $1 = \sum_{i=1}^1 i < 1 + 2 = \sum_{i =1}^{2}i <..... < \sum_{i=0}^v i < \sum_{i=0}^v i + (v+ 1) = \sum_{i=0}^{v+1} i < ....$ abarca el rango de todos los números naturales. De modo que existe un natural $v$, de modo que $\sum_{i=1}^v i \le c < \sum_{i=1}^{v+1} i$.

Deje $m = 1+c-\sum_{i=1}^v i$. A continuación,$1 \le m < v+1$$k = v - (m-1) \ge 1$. y $c = \sum_{i=1}^{v=k+(m-1)}i + (m-1)$ $n = 2((m-1) + \sum_{i=1}^{i+(m-1)} i)- a= j(a,k,m)$ donde $a = 0$ si $n$ es incluso y $a = 1$ si $n$ es impar$.

Por lo $j$ es surjective.

$j$ es inyectiva:

$j(0,b,c)$ es incluso y $j(1,d,e)$ es impar. así que si $j(a,k,m) = j(a',k',m')$$a= a'$.

Si $b + c < d+ e$ $j(a,d,e)= 2((e-1) + \sum_{i=1}^{d+e}i) - a = 2((e-1) + \sum_{i=1}^{b+c} i + \sum_{i=b+c+1}^{d+e}i) -a$

$\ge 2((e-1) + d+e + \sum_{i=1}^{b+c}i) - a$

$> 2(c1 +\sum_{i=1}^{b+c}i) - a = j(a,,b,c)$.

Así que si $j(a,k,m) = j(a',k',m')$ $k+m = k' + m'$

Si $d < c$ $j(a,v-d, d) = 2((d-1) + \sum_{i=1}^{v-d + (d-1)=v-c+(c-1)}i) - a$

$< 2((c-1) + \sum_{i=1}^{v-d + (d-1)=v-c+(c-1)}i) - a=j(a,v-c,c)$

Así que si $j(a,,k,m) = j(a',k',m')$ $a = a'$; $k+m = k'+m'$ ; $m = m'$ y por lo $m= m'$

Por lo $j$ es inyectiva.

Answer 3

Para cada una de las $n$, vamos a llamar a $A_n$ el conjunto de $i$ sobre el que nos gustaría $g(i)= f_n(i)$, e $B_n$ el conjunto de $i$ sobre el que nos gustaría $g(i)\ne f_n(i)$. Idealmente, nos gustaría que todos los $A_n$, $B_n$ a ser distinto el uno del otro, de esa manera somos libres para poner a $g$ a ser lo que queremos en los juegos, con ninguna posibilidad de que nuestras definiciones interferir el uno con el otro.

Así que usted sólo tiene que encontrar un (contables) infinito de la familia de subconjuntos de $\mathbb N$, $C_n$, todos los que son distintos, y entonces se puede establecer $A_1 = C_1, B_1 = C_2, A_1 = C_3, B_1 = C_4$, y así sucesivamente.

Se puede encontrar una contables de la familia de pares de subconjuntos disjuntos de a $\mathbb N$?