Lógica: Infinite $K$-secuencias, y $n$libre de problemas

Question

Hay dos problemas que parecen ser similares, que estoy atascado en. Esto no es tarea para mí, pero que le gustaría mucho a entender lo que está pasando.

Primer problema es este: Un infinito $k$-secuencia es una función de $s: \Bbb{N} \to \{0, \ldots ,k-1\}$ $k$- secuencia de longitud $l$ es una función de $s: \{0,\ldots ,l-1\} \to \{0, \ldots ,k-1\}$.

Decimos que un $k$-secuencia $s$ (finito o infinito) es $n$libre si no existe un número finito de $k$-secuencia $x$ tal que $x^n$ (repetido $n$ a veces) es una subcadena de $s$.

una. Demostrar que no existe ninguna infinito $2$-secuencia que es $2$-libre.

b. El uso de Konig del lexema, muestran que hay un infinito $3$libre de $2$-secuencia, si y sólo si para cada a $n$, hay un $3$libre de $2$-secuencia de longitud $n$.

Intento:

Un $2$-secuencia es una s.t. s: $\Bbb{N} \to \{0,1\}$ (hay un número infinito de maneras de hacer mapas de $\Bbb{N} \to \{0,1\}$, por ejemplo,$\{751,752\} \to \{0,1\}$, o supongo que incluso $\{751,752,753,754\} \to \{0,1\}$ como podríamos haber $\Bbb{N}$ mod $2$. Ok, ahora si hay un infinito $2$-secuencia que se $2$libre, entonces no sería un número finito de cadena que se repite en las $n$ veces sería una subcadena de $s$. Esto daría algo de $\{0,1\}\{0,1\}\{0,1\}\{0,1\}\{0,1\}\ldots\{0,1\} - n$ a veces, y para que algo que es $2$libre nos habrían $00, 01, 10,$ o $11$ ser un elemento de $s$. Pero desde $s$ no contiene ningún doble dígito de los elementos, no es $2$-secuencia que es $2$-libre. - También, me pregunto, si estoy en el camino correcto, acerca de si $\{0,1\}\{0,1\}$ serían los elementos $\{00,01,10,11\}$.

b. Konig del lema de los estados que tenemos un gráfico de $G$ que tiene un número infinito de vértices, pero que cada vértice tiene sólo un número finito de adyacencia a otros vértices, entonces existe un ser infinitamente largo camino simple. Ahora si tenemos un $3$libre de $2$ secuencia de entonces? Estoy un poco confundido sobre esto no sería posible (por la $2$-secuencia que se $2$-libre). O tal vez este problema se supone que para ser tal que, si esto $3$libre de $2$-secuencia podría existir, entonces tendríamos que para cada $n$ que es un porcentaje ($3$libre de $2$-secuencia de longitud $n$ y viceversa? tanto de ellos, sin embargo, puede que en realidad no existen, pero que dada uno existe el otro?

Gracias.

Answer 1

No entiendo su intento (a), debido a que escribe $\mathbb N\to\{0,1\}$, pero luego de darle mapas cuyo dominio es mucho menor que $\mathbb N$, como $\{751,752\}$. También, la frase que comienza con "OK, ahora $\dots$" se refiere a un 2-libre de la secuencia, pero en esencia la cita la definición de "no $n$-gratis".

Creo que (a) se convierte en mucho más fácil si usted no se preocupe de $n$-libertad para cualquier $n$ otro de 2, y ver cuales son las opciones para el primer par de términos en un (hipotético) 2-libre 2-secuencia. Tenga en cuenta que "2-libre" significa que ninguna finito subcadena puede ser de forma inmediata. Así que, después de elegir ya sea 0 o 1 como el primer término de su hipotética secuencia infinita, todos los términos son obligados, ya que no se puede repetir inmediatamente incluso un solo término. Pero, a continuación, usted encontrará una repetición inmediata de dos términos larga, ya en los primeros cuatro términos.

Para los que no trivial de la dirección de (b), la forma de un gráfico de $G$ cuyos nodos son las finito 3-libre 2-secuencias (todos los largos), y poner una arista que une dos de tales secuencias de $u$ $v$ si uno de ellos se obtiene a partir de la otra mediante la adición de un solo término (0 o 1) en la final. El uso de König del Lema para obtener un camino infinito $P$$G$, vamos a $v$ ser un vértice en este camino cuya longitud (como un 3-libre 2-secuencia) es tan corto como sea posible, y contemplar la parte de $P$ después $v$.