16 votos

Hacer cualquiera de estas secuencias han infinitamente muchos distintas recorre en virtud de la duración de ejecución de sustitución?

Vamos $$S = \{x \in \{1,2\}^\mathbb{N}: \ \text{every run in }x\text{ has finite length}\}$$ y definir $$T: S\to \mathbb{N}^\mathbb{N} $$ tal que para cualquier $x\in S$, ${T}x$ es la secuencia de ejecución de los tramos en $x$; es decir, $Tx$ es el resultado de la sustitución de cada uno (máximo) ejecutar por su longitud. El $T$-se itera de $x$ (cuando existen) son, a continuación, $x, Tx, T^2x, T^3x,...$

Terminología: Dada una secuencia infinita $x$, con una ejecución en $x$ es cualquier subsequence de $x$ que comprende uno o más contiguos de elementos iguales. Una carrera que se llama maximal si no es adyacente a un elemento iguales a los de la carrera. Si tiene un número finito de elementos, entonces su número se llama la longitud de la carrera; de lo contrario, la longitud de la carrera que se dice ser infinito.

Pregunta: ¿hay alguna $x \in S$ tener infinitamente muchos distintas $T$-repite? Si "no", ¿cómo demostrar? Si "sí", ¿cómo construir un ejemplo?

Sospecho que no $x\in S$ tiene infinitamente muchos distintas recorre, y que todos los $T$-trayectoria finaliza en algunos recorrer no en $S$, o, finalmente, entra en un ciclo (como en los ejemplos siguientes).

eventually-cyclic trajectories

Cada punto en $S$ tiene exactamente dos inmediata $T$predecesores, y estos son mutuos "complementa"; es decir, para cualquier $x\in S$, existen exactamente dos puntos en $S$, decir $w$$\overline{w}$, de tal manera que $Tw = T \ \overline{w} = x$ donde $\overline{w}$ es el resultado de la sustitución (en $w$) $1$ $2$ y viceversa. (En consecuencia, en la imagen de arriba, debe ser el caso que $y=\overline{z}$$q=\overline{t}$. Esto se aplica a los ejemplos numéricos que dan a continuación en $1b$.)


La pregunta puede ser formalmente reformulado mediante la partición de $S$ como sigue:

$$S = (A_{1a} \cup A_{1b}) \cup A_2$$ donde (con $i,j,k$ restringido a los números enteros no negativos) $$\begin{align} A_{1a} & = \{x \in S : \exists i (T^i x \notin S) \}\\ A_{1b} & = \{x \in S : \forall i (T^i x \in S) \ \mathrm{and} \ \exists\ j\ne k \ (T^jx = T^kx) \}\\ A_2 & = \{x \in S : \forall i (T^i x \in S) \ \mathrm{and} \ \forall\ j\ne k \ (T^jx \ne T^kx) \}. \end{align} $$

En otras palabras, para cualquier secuencia infinita $x\in S$, iterando $T$ repetidamente debe resultar en exactamente uno de los siguientes casos:

  1. $x$ tiene sólo finitely-muchos distintas recorre en $S$.

    1a. Las iteraciones terminar debido a una iteración que no en $S$ (es decir, tiene algún elemento que no es ni $1$ ni $2$, y/o que tiene un recorrido de longitud infinita). E. g., $1112...\to 3...$ o $121212...\to 1^\infty$.

    1b. Todas las recorre en permanecer en $S$, pero hay sólo un número finito de ellos (es decir, que, finalmente, entrar en un ciclo finito). E. g., los dos Kolakoski secuencias son el único 1-ciclos (puntos fijos) de $T$: $$12211212212211211221211212211... \a 12211212212211211221211212211...\\ 2211212212211211221211212211... \a 2211212212211211221211212211... $$ El primero de estos dos, he aquí un ejemplo correspondiente a la imagen de arriba: $$\begin{align} &.\\ &.\\ \to\ v =\ &22122112112212112112212212112...\\ \to\ w =\ &21221221121221211211221221211...\\ \to\ x =\ &11212211211212212112212211212...\\ \to\ y =\ &21122121121122122112122121122... \ (= \overline{z}) \\ \to\ z =\ &\mathbf{12211212212211211221211212211}...\\ \to\ z \to\ &z\ \to \ ... \end{align} $$ Comenzando con el primer elemento de cada secuencia de un ciclo de trabajo "hacia atrás", es fácil de construir ciclos de arbitraria de tamaño finito; por ejemplo, aquí es un 3-ciclo de la construcción (con etiquetas correspondientes a la imagen de arriba): $$\begin{align} &.\\ &.\\ \to\ p =\ &211221221211211221211212211211212212112212211...\\ \to\ q =\ &122121121221121122121121122122121121221121121...\ (= \overline{t})\\ \to\ r =\ &\mathbf{121121122122112122121121122121121221121121221...}\\ \to\ s =\ &\mathbf{112122122112112122112112212112...}\\ \to\ t =\ &\mathbf{2112122121122122112\dots}\\ \to\ r =\ &\underline{121121122122}112122121121122121121221121121221...\\ \to\ s\ \to &\ t\ \to\ r\ \to\ s\ \to t\ \to\ r\ \to\ ... \end{align}$$

  2. $x$ tiene infinitamente muchos distintas recorre en $S$.

Pregunta: ¿Cómo probar si $A_2$ está vacía? Si $A_2$ no está vacío, cómo construir un ejemplo de elemento?


Ya que, por cualquier $x \in \{1,2\}^\mathbb{N}$, un infinito de ejecución sólo puede producirse como un sufijo, $S$ parece tener la misma cardinalidad que el conjunto de irrationals la vida real en el intervalo de $[0,1]$ (es decir, uncountably infinito); cf. todos los reales en ese intervalo, excepto aquellos con "terminar" binario expansiones. Por otro lado, aunque parece que $A_{1b}$ es contable, estoy seguro de que la cardinalidad de a $A_{1a}$ (incontable?). Así que yo soy incapaz de deducir incluso la cardinalidad de a $A_2$.

4voto

Mirko Puntos 5620

La respuesta es sí.

Deje $\mathbb N$ denota el conjunto $\{1,2,...\}$ de los enteros positivos y $P=\{1,2\}^{\mathbb N}$. Dado cualquier $\rho\in P$ vamos a definir $\varphi_\rho\in S$ de manera tal que todos los $T$-se itera de $\varphi_\rho$ permanecen en $S$ y $(T^{k-1}(\varphi_\rho))(1)=\rho(k)$ para todos los $k\in\mathbb N$ donde $\rho(k)$ indica el $k$-ésimo elemento de a $\rho$, e $(T^{k-1}(\varphi_\rho))(1)$ indica el primer elemento de la $(k-1)$-st recorrer, $(T^{k-1}(\varphi_\rho))$$\varphi_\rho$.

Si $T^k(\varphi_\rho)$, $k\in\mathbb N$, es el tiempo cíclico, es decir, si hay $n,m$ tal que $T^{k+m}(\varphi_\rho)=T^k(\varphi_\rho)$ todos los $k\ge n-1$, entonces claramente la secuencia de la correspondiente de la primera de las coordenadas, es decir, $(T^k(\varphi_\rho))(1)$, $k\in\mathbb N$, también sería eventualmente cíclico. Por lo tanto $\rho$ resulta ser, finalmente, cíclico, con $\rho(k+m)=\rho(k)$ todos los $k\ge n$.

Desde $P$ es incontable (con $|P|=\mathfrak c =2^{\aleph_0}$) y ya sólo hay countably muchos con el tiempo cíclico de las secuencias de $\rho\in P$, se sigue que para todo el una cantidad no numerable resto de opciones de $\rho$ la recorre en $T$ $\varphi_\rho$ nunca se repita. Por lo tanto, para completar la prueba, sólo queda por definir $\varphi_\rho$ con las propiedades anteriormente mencionadas, para cada una de las $\rho\in P$.

Me limitaré a ilustrar la construcción de $\varphi_\rho$, determinado $\rho\in P$, con un par de ejemplos. En primer lugar, decir $\rho$ comienza como $\langle 2,1,2,2,1,... \rangle$ o, abreviado, como $21221..$. Lista de los elementos de $\rho$ en una columna, de arriba a abajo, como se ilustra:
$\\ 2\\ 1\\ 2\\ 2\\ 1\\ ... $

Entonces, comenzando con más y más filas, trabajar hacia atrás, para definir más grandes y más grandes segmentos inicial de la primera fila, el cual será nuestro $\varphi_\rho$. Es decir, comenzar con la fila $2$, trabajar hacia atrás, a continuación, comience con la fila $3$, trabajar hacia atrás, etc. Aquí es cómo funciona cuando empezamos con la fila $2$ (y trabajar hacia atrás, es decir, parcialmente definir fila $1$, de modo que una aplicación de $T$ fila $1$ resultados en la fila $2$):
$\\ 21\\ 1\\ 2\\ 2\\ 1\\ ... $

A continuación, comience con la fila $3$ y trabajar hacia atrás (de manera que una aplicación de $T$ fila $2$ resultados en la fila $3$, y una aplicación de $T$ fila $1$ resultados en la fila $2$:
$\\ 21221\\ 112\\ 2\\ 2\\ 1\\ ... $
Hacemos todo lo que esta sujeta al requisito de que cada fila permanece en $S$ y tiene pistas de longitud en la mayoría de las $2$.

En el segmento inicial de $\rho$ después de este procedimiento se obtiene:
$\\ 2122112112212\\ 11221221\\ 2212\\ 21\\ 1\\ ... $
donde la primera fila representa un segmento inicial de la $\varphi_\rho$ que construimos.

Como un ejemplo diferente decir $\rho$ se inicia en $\rho=\langle 2,1,1,1,2,1,,... \rangle=211121..$. Listado de los elementos de $\rho$ en una columna, de arriba a abajo, tenemos:
$\\ 2\\ 1\\ 1\\ 1\\ 2\\ 1\\ ... $

De trabajo de la fila $3$ hacia atrás, tenemos:
$\\ 2112\\ 12\\ 1\\ 1\\ 2\\ 1\\ ... $
y de trabajo de la fila $6$ hacia atrás, tenemos:
$\\ 21122122121121\\ 122121121\\ 121121\\ 1121\\ 21\\ 1\\ ... $
donde, de nuevo, la primera fila representa un segmento inicial de la correspondiente $\varphi_\rho$ que construimos.

Claramente, por construcción, cada una de las $T^k(\varphi_\rho)$ permanece en $S$, y $(T^{k-1}(\varphi_\rho))(1)=\rho(k)$, lo que completa nuestra respuesta.

Lo que sigue a continuación una mayor y más complicado recursivo de construcción de $\varphi_\rho$. Usted no tiene que leer, aunque tengo que salir a las disponibles.

He puesto una segunda respuesta (en comparación con el no a la anterior, pero para las versiones publicadas incluso antes), que utiliza las mismas ideas, como mi respuesta anterior (es decir, anterior respuesta publicada por separado), pero es por escrito mejor (creo (bueno, en retrospectiva, claro que no es tan buena como la de la simple descripción dada anteriormente)). Me gustaría que la respuesta anterior también (... alguien votó (ya no, tal vez la votación se retrae o también hubo otro voto hacia abajo, pero en fin) así que me odio a borrar ahora, además de que podría ser de algún interés, pero por favor no lea mi respuesta, a menos que a usted le gustaría ver cómo encontré con este ejemplo, y a menos que usted está listo para poner para arriba con las inconsistencias, que no tengo la intención de limpiar).

Así que aquí es lo que espero que el mejor ejemplo.

La respuesta es `sí". Describir un procedimiento que produce muchos ejemplos (sólo se produzca un ejemplo para una contables subconjunto de un producto determinado espacio de multitud de cardinalidad).

Deje $\mathbb N$ denota el conjunto de números enteros positivos y $P=\{1,2\}^{\mathbb N}$. (Hay algunos buenos métodos de representación de los ajustes que se podrían hacer en lo que sigue, dependiendo de si uno toma $0\in\mathbb N$ o $0\not\in\mathbb N$; mi notación es consistente con la última opción, que es, $1=\min\mathbb N$.)

Vamos a definir un mapa de $\varphi$ de$P$$S$. Es decir, $$\varphi: P \a S, \mathrm{\ si\ } \rho\en P \mathrm {\\ } \varphi_\rho\in S$$

El $n$-ésimo elemento de una secuencia será denotado como $\rho(n)$ o $\varphi_\rho(n)$. El mapa de $\varphi$ tendrá las siguientes dos propiedades:

  1. $T^k(\varphi_\rho)\in S$ todos los $k\in \mathbb N\cup\{0\}$ y todos los $\rho\in P$,

  2. Para todos $k\in\mathbb N$, $(T^{k-1}(\varphi_\rho))(1)=\rho(k)$.

Condición 2 implica que si la secuencia de $\langle \varphi_\rho,T(\varphi_\rho),T^2(\varphi_\rho),..., T^k(\varphi_\rho),... \rangle$ es el tiempo cíclico, es decir, si hay $n,m\in\mathbb N$ con $T^k(\varphi_\rho)=T^{k+m}(\varphi_\rho)$ para todos los $k\ge n-1$, entonces la secuencia de $\rho=\langle\rho(1),\rho(2),...\rangle$ es el tiempo cíclico, con $\rho(k)= \rho(k+m)$ todos los $k\ge n$.

Deje $P_0$ ser el subconjunto de $P$ consistente todo el tiempo y secuencias cíclicas, y deje $P_1=P\setminus P_0$. Desde $P_0$ es contable y $P$ es incontable (con $|P|=\mathfrak c = 2^{\aleph_0}$, la cardinalidad del continuo), tenemos que $P_1$ es incontable (con $|P_1|=\mathfrak c$). Por lo tanto, todos los $T$-se itera de $\varphi_\rho$ permanecen en $S$ y nunca se repiten, siempre que $\rho\in P_1$. Esto demuestra que no sólo ejemplos existen, pero hay uncountably (continuum) muchos de ellos.

Con el fin de construir $\varphi$ en primer lugar, construir otro mapa $$\beta: P \a P, \mathrm{\ si\ } \rho\en P \mathrm {\\ } \beta_\rho\en P$$

Para definir $\beta$, tomamos todos los segmentos inicial de $\rho$, la inversa de cada una, y poner uno después del otro. Para ilustrar, decir $\rho$ comienza como $\langle2,1,1,1,2,1,... \rangle$, abreviada o $211121..$. A continuación, los segmentos inicial de $\rho$$\langle2 \rangle$, $\langle2,1 \rangle$, $\langle2,1,1 \rangle$, $\langle2,1,1,1 \rangle$, $\langle2,1,1,1,2, \rangle$, $\langle2,1,1,1,2,1 \rangle$, ... , o abreviado,

$$2,21,211,2111,21112,211121,...$$

Invertir cada segmento inicial obtenemos

$$2,12,112,1112,21112,121112,...$$

y la concatenación de estos obtenemos que $\beta_\rho$ comienza como

$$212112111221112121112...= \langle2,1,2,1,1,2,1,1,1,2,2,1,1,1,2,1,2,1,1,1,2,... \rangle $$

Formalmente deje $t_n=\frac{n(n+1)}2$ el valor del $n$-ésimo número triangular. A continuación, $\beta_\rho(t_n-m)=\rho(m+1)$ todos los $n$, y todos los $m\in\{0,1,...,n-1\}$.

Ahora podemos iniciar la construcción de la $\varphi_\rho$. Para ilustrar, vamos de nuevo a $\rho$ inicio como $211121..$., así $\beta_\rho$ comienza como $212112111221112121112..$. Lista de los elementos de $\beta_\rho$ en una columna vertical, comenzando en la parte inferior y va como esto:

$\\ ... \\ 2\\ 1\\ 1\\ 2\\ 1\\ 2 $

De trabajo "hacia atrás" definir parcial filas coherente con la columna de la izquierda, como se describe a continuación. Deje $p^j$ el valor parcial de la fila $j$ (contados a partir de la parte inferior) y $p^j(n)$ indicar el $n$-ésimo elemento de a $p^j$. El requisito es que el $T(p^{j+1})=p^j$. Por ejemplo, $p^2$ debe ser parte de una secuencia que se inicia con $\beta_\rho(2)$, en nuestro ejemplo,$\beta_\rho(2)=1$, y de tal manera que $T(p^2)$ comienza como $p^1$. Por lo tanto, $p^2$ debe comenzar como $11$, y para su comodidad (y para asegurarse de que las longitudes de las $p^j$ estrictamente aumentar incluso en los casos en que $\beta_\rho(1)=1$) también vamos a añadir un carácter de elemento coherente con $p^2$ siendo un segmento inicial de una secuencia en $S$ y tener pistas de longitud en la mayoría de las $2$, lo $p^2$ comienza como $112$. (Aquí podemos aplicar la restricción de $T$ a sólo una secuencia finita, por lo que el resto de la secuencia (que no puede ser determinada por la información) puede ser representada por un $*$, por ejemplo, $p^2=112*$.) A continuación, $p^3$ debe ser parte de una secuencia que se inicia con $\beta_\rho(3)$, en nuestro ejemplo,$\beta_\rho(3)=2$, y de tal manera que $T(p^3)$ comienza como $p^2$. Por lo tanto, $p^3$ comienza como $21221$. Desde el primer elemento de $p^j$ es dado, es decir, $p^j(1)=\beta_\rho(j)$ la construcción como el descrito hasta ahora es ambigua, y produce el siguiente parcial filas para nuestro ejemplo.

$\\ ... \\ 211212212211212212112\\ 12112122112112\\ 112112212\\ 21221\\ 112\\ 2 $

Deje $|p^j|$ denotar la longitud de la parte definida de) $p^j$, y deje $|p^j|_2$ la cuenta de cuantas veces el número de $2$ se produce en $p^j$. Por ejemplo,$|21221|=5$$|21221|_2=3$. Es fácilmente demostrado que $|p^{j+1}|=|p^j|+|p^j|_2 +1$ todos los $j$, y (el uso que los dos últimos elementos de $p^j$ son siempre diferentes) que $|p^j|_2\le |p^j|-1$ para todos los $j\ge2$. De ello se desprende que $|p^j|<|p^{j+1}|\le 2 |p^j|$$j\ge2$.

Deje $J_1=\{\frac{n(n+1)}2: n\in\mathbb N\}$ ser el conjunto de todos los números triangulares. Vamos a construir una disminución de la secuencia de conjuntos infinitos $J_1\supset J_2 \supset J_3 \supset ...$, y que a la vez definen $\varphi_\rho(n)$ como sigue. Set $\varphi_\rho(1)=\rho(1)$. Tenga en cuenta que $p^j(1)=\beta_\rho(j)=\beta_\rho(t_n)=\rho(1)$ todos los $j\in J_1$ (donde $j=t_n$ es un número triangular para algunos $n$).

Para cada una de las $j\ge2$, $p^j(2)$ está definido y es en $\{1,2\}$. Split $J_1\setminus\{1\}$ en la inconexión de la unión de dos conjuntos, $J_1(1)=\{j\in J_1\setminus\{1\}:p^j(2)=1\}$, y $J_1(2)=\{j\in J_1\setminus\{1\}:p^j(2)=2\}$. Al menos uno de estos dos conjuntos tiene que ser infinita. Si $J_1(1)$ es infinito, entonces deje $J_2=J_1(1)$ y $\varphi_\rho(2)=1$. Otra cosa deje $J_2=J_1(2)$ y $\varphi_\rho(2)=2$. Continuar por la recursividad de la siguiente manera.

Split $J_n\setminus\{1,...,n\}$ en dos conjuntos, $J_n(1)=\{j\in J_n\setminus\{1,...,n\}:p^j(n+1)=1\}$, y $J_n(2)=\{j\in J_n\setminus\{1,...,n\}:p^j(n+1)=2\}$. Si $J_n(1)$ es infinito, entonces deje $J_{n+1}=J_n(1)$ y $\varphi_\rho(n+1)=1$. Otra cosa deje $J_{n+1}=J_n(2)$ y $\varphi_\rho(n+1)=2$.

Esto define $\varphi_\rho(n)$ todos los $n$. Tenga en cuenta que si $j\in J_n$ $|p^j|\ge n$ $p^j(k)=\varphi_\rho(k)$ todos los $k\in\{1,2,...,n\}$. (Usar ese $J_n\subset J_{n-1}\subset ... \subset J_1$ .)

A continuación se muestra que para todos los $k\in\mathbb N$ tenemos $(T^{k-1}(\varphi_\rho))(1)=\rho(k)$. Al $k=1$, $(T^{0}(\varphi_\rho))(1)=\varphi_\rho(1)=\rho(1)$. Ahora fix $k>1$. Tenga en cuenta que si $|p^j|$ es lo suficientemente grande, por ejemplo, si $|p^j|\ge3^k$, $(T^{k-1}(p^j))(1)$ está definido (usar ese $|T(p^{m+1})|=|p^m|\ge\frac{|p^{m+1}|}2$ todos los $m\ge2$). Pick $j$ lo suficientemente grande como sujeto a las siguientes condiciones: $j\in J_{3^k}$, $|p^j|\ge3^k$, y $j=t_n$$n>k$. A continuación,$(T^{k-1}(\varphi_\rho))(1)=(T^{k-1}(p^j))(1) =\beta_\rho(t_n-(k-1))=\rho((k-1)+1)=\rho(k)$.

La prueba de que $T^k(\varphi_\rho)\in S$ todos los $k$, y todos los $\rho\in P$ es similar. De hecho, si $T^k(\varphi_\rho)\not\in S$ a continuación, cualquiera de $(T^k(\varphi_\rho))(m)\ge3$ algunos $m$, o $(T^k(\varphi_\rho))$ tiene una infinita ejecutar. En el último caso, $(T^{k+1}(\varphi_\rho))(m)\ge3$ algunos $m$, lo que reduce la ex. Pero si $(T^k(\varphi_\rho))(m)\ge3$ entonces podríamos recoger lo suficientemente grande como $n$ $j$ con $j\in J_n$ $|p^j|\ge n$ tales que $3\le(T^k(\varphi_\rho))(m)= (T^k(p^j))(m)\in\{1,2\}$, una contradicción.

0voto

Mirko Puntos 5620

Este es mi mayor respuesta por favor, no leer, y leer mi más reciente responder en su lugar. Si usted lee esto, usted puede ver cómo llegué a mi respuesta, pero puede ser difícil de leer (y tengo la intención de dejarlo tal y como es, sin intentar editar más de limpiar). El otro es escrito mucho mejor (espero).

Esta es la tercera versión que he puesto hoy, y yo soy el funcionamiento de vapor. Creo que tengo suficiente para publicar (y quizás editar más tarde si es necesario). Aquí está.

Estoy construyendo un ejemplo de nuevo. Creo que la compacidad juega un papel importante (tanto en la topología y como en la lógica, y que tiene algo que ver con la inversa de los límites demasiado), pero no acabo de conseguir, sin embargo a mí mismo, así que voy a tratar de describir mi idea, hasta el punto de que cuando alguien sería capaz de verificar. Así que, tratando de construir una secuencia $\sigma$ de manera tal que todas las recorre en $T$ permanecen en $S$ pero nunca se repita.

La primera revisión de la secuencia de $\beta=\langle\beta(1),\beta(2),\beta(3),...\rangle= \langle 1, 2,1,2,2,1,2,2,2,1,2,2,2,2,1,2,2,2,2,2,1,...\rangle$.
Es decir, tenemos grupos de $2$'s, separadas por una sola $1$'s, y el número de $2$'s en cada grupo aumenta. (Eventualmente ese "empuje de la longitud del ciclo hasta el infinito".)

Ahora, $\beta$ $\beta$patas arriba. Es decir, podemos empezar haciendo una lista de los elementos de $\beta$ hacia atrás, en una sola columna, de abajo a arriba, como este:
.
.
1
2
2
2
1
2
2
1
2
1

A continuación, empezaremos por la parte inferior y proceder hacia atrás (en la forma que se describe en el OP, en la pregunta), y la preservación de la primera columna (a la que nos dice si para iniciar una secuencia de con $1$ o con $2$). Obtenemos:
.
.
1
2
2
2 etc, yendo hacia atrás
112212211212212112
22122112112
212212
1121
21
1

Para ilustrar, si tomamos cualquier (parcial) de la fila y se aplican $T$ obtenemos el siguiente (parcial) de la fila (por esta vez), por ejemplo,
$T(112212211212212112*)=22122112112*$
$T(22122112112*)=212212*$
$T(212212*)=1121*$
$T(1121*)=21*$
$T(21*)=1*$

Así tenemos
.
.
1121
21
1
y consideramos que estas filas para ser etiquetados con los números naturales, comenzando en la parte inferior, por lo que el primer raw comienza con 1, el segundo de la fila comienza a 21, la tercera fila comienza 1121, etc.

Permítanme presentarles a más de notación. El anterior procedimiento se describe cómo llegar las secuencias parciales, parciales o filas, comenzando desde la parte inferior y va hacia atrás. Déjame llamar a estos parcial de filas $p^j$, por lo que $p^1=1$, $p^2=21$, $p^3=1121$, etc. También, $p^j(k)$ indican el $k$-ésimo elemento de la fila $j$, por ejemplo, $p^3(1)=1$, $p^3(3)=2$, $p^3(5)$ no está definido por nuestra construcción.

Deje $\sigma(1)=1$, y deje $J_1=\{j:$ fila $j$ comienza con $\sigma(1)\}= \{j: p^j(1)=\sigma(1)\}$.
Por construcción, $J_1$ es infinito.

El conjunto $J_1\setminus\{1\}$ naturalmente se divide en dos conjuntos:
$J_1(1)=\{j\in J_1\setminus\{1\}: p^j(2)=1\}$ y
$J_1(2)=\{j\in J_1\setminus\{1\}: p^j(2)=2\}$.
Al menos uno de estos dos conjuntos es infinito.
Si $J_1(1)$ es infinito, entonces deje $\sigma(2)=1$$J_2=J_1(1)$.
Otra cosa, vamos a $\sigma(2)=2$$J_2=J_1(2)$.

De forma recursiva definir conjuntos infinitos $J_{n+1}\subseteq J_{n}\setminus\{1,2,...,n\}$ $\sigma(n+1)\in\{1,2\}$ tal que $p^j(n+1)=\sigma(n+1)$ siempre $j\in J_{n+1}$.

De esta forma se define la secuencia de $\sigma$, que es, por encima de la construcción, finalmente, define $\sigma(n)$ para todos los números naturales $n$.

Primero vamos a mostrar que $T^k(\sigma)\in S$ todos los $k$. Suponer lo contrario. La idea se asemeja a la compacidad (como en la lógica), o si no tengo mi terminología de derecho, la idea es que, si hay algo de $k$ tal que $T^k(\sigma)\not\in S$, entonces hay algunas coordinar $m$ (dependiendo $k$) tal que $(T^k(\sigma))(m)\ge3$. Hay un largo segmento inicial de $\sigma$, se $\tau$, de tal manera que la primera $m$-muchas de las coordenadas de $T^k(\sigma)$ coincide con el primer $m$-muchas de las coordenadas de $T^k(\tau)$. (Infinitamente muchos coordenadas de $T^k(\tau)$ permanecen indefinidos pero no hay necesidad de preocuparse acerca de ellos. También sigo pensando que de $S$ como consta de $x\in \{1,2\}^\mathbb{N}$ de manera tal que cada ejecución de $x$ tiene una longitud en la mayoría de las $2$, mientras que el OP dice longitud finita: Pero no hace mucha diferencia. Si $T^k(\sigma)\not\in S$ entonces $(T^k(\sigma))(m)\ge3$ algunos $m$ o más $(T^{k+1}(\sigma))(m)\ge3$ algunos $m$, por lo que si es necesario nos puede reemplazar a $k$$k+1$.) Hay una gran suficientemente $n$ tal que $\tau$ es un segmento inicial de la fila parcial $p^n$. Pero, a continuación,$T^k(p^n)\ge3$, una contradicción.

La idea es mostrar que $T^k(\sigma)$ nunca se repite es similar. Tomando el tiempo suficiente segmentos inicial de $\sigma$ pudimos demostrar que:
1. Para cada una de las $m$ hay $n$ tal que $(T^k(\sigma))(1)=2$ para todos los $k\in\{n,n+1,...,n+m\}$, sin embargo,
2. hay infinidad de $k$ tal que $(T^k(\sigma))(1)=1$.

Me pueden combinar las dos condiciones en uno solo (que no es exactamente equivalente a la conjunción de los dos anteriores, pero hace el mismo trabajo):
(*) Para cada una de las $m$ hay $n$ tal que $(T^n(\sigma))(1)=1$ pero $(T^k(\sigma))(1)=2$ todos los $k\in\{n+1,...,n+m\}$.

Creo que uno puede variar $\beta$ para obtener una cantidad no numerable de ejemplos (pero no he verificado todos los detalles de esta parte). Al menos, creo que el de arriba $\sigma$ obras. (Yo pensaba que era un poco más, y ver sin interrupciones, y estoy convencido de que es el correcto. Puede beneficiarse de una mejor exposición y quizás un poco más de detalles, pero por favor, hágamelo saber si usted tiene alguna pregunta específica.)

Voy a seguir con la respuesta anterior (por supuesto, tal vez añadiendo más detalles más adelante). Lo que sigue a continuación son mis respuestas anteriores, que deben ser ignoradas, a menos que usted está interesado en ver algunos de mis primeros pasos e ideas.

He cambiado mi mente (de lo que se encuentra en la parte inferior) así que me permito publicar un opuesto respuesta (aquí) a lo que yo había publicado anteriormente (en la parte inferior). (Advertencia, tengo un hueco en esta prueba.)

No hay ningún contraejemplo. Me refiero a que no hay secuencia $\sigma=\langle\sigma(1),\sigma(2),\sigma(3),...\rangle$ de manera tal que todos los $T$ itera son diferentes. Por una contradicción, supongamos $\sigma$ fue dicha secuencia. Deje $K_1=\{n:T^n\sigma$ comienza con $1\}$, e $K_2=\{n:T^n\sigma$ comienza con $2\}$. Al menos uno de $K_1$ $K_2$ debe ser infinito (tal vez ambos lo son). Considere el caso en que $K_1$ es infinito. Entonces podríamos recoger $n$ tan grande como se quiera, en $K_1$, y comenzando con el primer elemento de $T^n\sigma$,$1$, trabajar hacia atrás, y al hacerlo, vamos a obtener, en la parte superior, más grande y más grande de los segmentos de la Kolakoski secuencia que comienza con $1$. Así que en la parte superior debemos tener la Kolakowski secuencia que comienza con $1$, una contradicción. Una similar contradicción se obtiene si $K_2$ es infinito.

Hay algunos detalles que deben completarse, voy a hacerlo ahora (a menos que me enredarnos de nuevo, pero creo que tengo derecho a este tiempo:) Bueno, no sé, la diferencia esta vez es que a medida que vamos hacia atrás, digamos que de $T^n\sigma$$T^{n-1}\sigma$, no sabemos si $T^{n-1}\sigma$ comienza con $1$ o con $2$. (Si es que siempre se inicia con $1$ luego de hacer llegar más y más segmentos inicial de $\sigma$, coincidiendo con los segmentos inicial de la Kolakowski secuencia que comienza con $1$, pero por supuesto que uno necesita para tomar la manija de las otras posibilidades, y no sé cómo.)

Lo que sigue es mi respuesta anterior (desde el momento en que yo, aunque no era un ejemplo). Supongo que se podría escoger la respuesta que usted desea ... ahora que tengo lagunas en cada versión de mi respuesta ...

Creo que hay un ejemplo. Voy a editar mi respuesta a proporcionar más detalles formales las próximas horas, pero aquí es una descripción informal que podría ser lo suficientemente bueno como para seguir.

La idea principal es trabajar hacia atrás, y al mismo tiempo diagonalize, así como para empujar la duración del ciclo hasta el infinito.

Acaba de ser definido, en el ejemplo se va a empezar con 1. Cuando trabajamos hacia atrás podríamos inicio de cada secuencia anterior con 1 o 2. Podemos trabajar hacia atrás a partir de la secuencia con 2 tantos pasos como deseamos (esto en el largo plazo se cuenta para empujar la duración del ciclo hasta el infinito), entonces podemos trabajar hacia atrás para tantos pasos como sea necesario, esta vez a partir de la secuencia con 1, hasta que coincida con el segmento inicial de la que está actualmente bajo consideración. (Hay un argumento que esto tiene que suceder, porque de lo contrario tenemos un ciclo en donde todas las secuencias comienzan con 1, por otro lado ya tenemos secuencias por el camino que se inicio con 2.) Así obtenemos un nuevo segmento inicial, trabajar hacia atrás de nuevo, esta vez con el nuevo segmento inicial, el uso de un mayor número de secuencias que comienzan con 2 (antes de volver a las secuencias que comienzan con 1 para coincidir con el nuevo segmento inicial), obligando a la longitud del ciclo para ser aún más largo, etc. Me permito publicar esto y luego intentar escribir algo más formal.

Dado que yo no tengo todos los detalles, sin embargo, quizá este ejemplo no debe ser tomado demasiado en serio, pero estoy trabajando en ello. "De lo contrario, tenemos un ciclo en donde todas las secuencias comienzan con 1" de parte de mis argumentos necesidades de un análisis más cuidadoso. Así que, por ahora esto es sólo una idea, a ver si me puede hacer el trabajo. (Si lo hace, entonces sería también muestran que hay un continuum muchos ejemplos, es decir, una cantidad no numerable con la misma cardinalidad como los reales.) Creo que funciona, pero es un poco desordenado. La idea de límite inversa juega un papel. Pero todavía tengo que poner todos los detalles juntos.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X