¿Existe una secuencia de cadenas en la que siempre haya un elemento entre dos elementos cualesquiera?

Question

¿ Puedo definir una forma de ordenar cadenas tal que para dos cadenas cualesquiera X y Z, pueda encontrar otra Y tal que X < Y < Z ?

Evidentemente, no es el caso de la clasificación alfanumérica: no hay ninguna cadena entre "4a" y "4a0".

Pero no me resulta obvio si podría haber una definición de secuencia que aproveche el hecho de que las cadenas pueden ser infinitamente largas, donde siempre se podría encontrar una cadena entre otras dos.

No he podido hacerlo, pero carezco de los conocimientos formales para poder decidir si esto no es fundamentalmente posible.

Answer 1

Sí, basta con construir una biyección entre el conjunto de cadenas y y el conjunto de números racionales. A continuación, tire hacia atrás el orden en $\mathbb Q$ en las cuerdas.

Probablemente no necesites una biyección en $\mathbb Q$ sólo necesita una función $f: S \to \mathbb R$ que tiene una imagen densa.

Por ejemplo, piense que cada carácter es un número que empieza por 0. Así, cualquier carácter fuerte se convierte en $a_1.. a_n$ donde cada $a_i \in \{ 0, 1, 2, ..,35 \}$ .

Ahora defina $f(a_1.. a_n)=2^{a_1}3^{-a_2}5^{a_3} ... p_n^{(-1)^{n+1}a_n}$ donde $p_n$ es el $n$ número primo.

Defina $a_1.. a_n < b_1...b_k$ sólo si $f(a_1..a_n) < f(b_1...b_k)$ .

Answer 2

Para responder a esta pregunta, primero debemos tener una definición precisa de lo que es una "cadena".

La formalización habitual es que tenemos un "alfabeto" que contiene un número finito de símbolos. El "alfabeto" no consiste necesariamente en las letras de un idioma; por ejemplo, podríamos tener un alfabeto de $36$ símbolos ( $26$ cartas y $10$ dígitos numéricos) o un alfabeto de $1000$ símbolos. Una "cadena" es una secuencia de estos símbolos, posiblemente con repeticiones. Una "cadena" puede ser tan larga como queramos, así que dada cualquier cadena siempre hay otra más larga. En podría incluir cadenas de longitud infinita en nuestro modelo, pero (al menos por ahora) consideremos sólo cadenas de longitud finita.

Ahora observa que si tomas el alfabeto formado por los diez dígitos decimales 0, 1, 2, 3, 4, 5, 6, 7, 8, y 9, formamos cadenas sobre este alfabeto, y luego escribimos un punto decimal antes del primer símbolo de cada una de estas cadenas, tenemos todas las fracciones decimales terminales en el intervalo $[0,1).$

Ahora bien, si este conjunto estuviera estrictamente ordenado por valor numérico, casi habríamos terminado. Desafortunadamente, estas fracciones decimales terminales incluyen muchas que terminan con uno o más ceros, y estos son numéricamente iguales a los decimales con menos dígitos.

Así que para cualquier decimal con ceros al final, cuenta el número de ceros al final y escribe ese número antes de el punto decimal. Por ejemplo, de esta forma la cadena "123000" corresponde al número $3.123.$ Utilícelo como regla para definir una asignación $f$ a partir de cadenas sobre los dígitos decimales hasta números racionales. Cada cadena sobre este alfabeto se mapeada a un número único (diferente de cualquier otra cadena). Ahora bien, si $X$ y $Y$ son dos cadenas cualesquiera sobre este alfabeto, digamos que $X < Y$ si $f(X) < f(Y).$

Ahora observa que cualquier número decimal $x$ con un número finito de dígitos es igual a $f(X)$ para alguna cadena $X$ de dígitos decimales; específicamente, $X$ consiste en todos los dígitos de $x$ después del punto decimal (excluyendo los ceros finales), seguido de $\lfloor x \rfloor$ ceros.

Entre dos números decimales terminales cualesquiera hay otro número decimal terminal. Por lo tanto, para cualquier cadena $X$ y $Z$ tal que $X < Z,$ hay un número decimal de terminación $y$ tal que $f(X) < y < f(Z).$ Construir la cadena $Y$ tal que $f(Y) = y,$ y tenemos $X < Y < Z.$

Cualquier otro alfabeto puede tratarse de forma similar. Para un alfabeto de $N$ símbolos, dar a cada símbolo un valor único en el rango $0$ a $N-1,$ y definir la ordenación de las cadenas como hicimos para los diez dígitos decimales, pero utilizando una base- $N$ representación en lugar de la base $10$ si $N \neq 10.$

Hay algunas pequeñas complicaciones si permitimos cadenas infinitamente largas.

Por cierto, ¿qué pasa si no estipulamos explícitamente que nuestro alfabeto tiene una número finito de símbolos? Los alfabetos finitos son la norma para los ejercicios de teoría de la computación. (o al menos lo eran cuando yo estudiaba ese campo), y esto tiene sentido si imaginamos que cada símbolo debe escribirse en un número fijo de bits de memoria en un ordenador, como $8$ -cadenas ANSI de bits. Pero hay codificaciones que permiten codificar diferentes "caracteres" en diferentes número de bits; por ejemplo, Unicode tiene varios $8$ -bit, entonces un número de $16$ -y $24$ -de bits. Podríamos definir una codificación "Unicode infinitamente extendida" que repitiera este patrón para simplemente aumentar el tamaño del siguiente grupo de caracteres en $8$ bits, indefinidamente. Y entonces podríamos definir el orden de los caracteres de este alfabeto para que siempre haya un $8n+8$ -que precede léxicamente a cualquier carácter carácter de $8n$ o menos bits. Usando tal alfabeto, hay sería sea una cadena que se encuentre léxicamente entre "4a" y "4a0", y otras cadenas que léxicamente entre otras dos cadenas cualesquiera que podamos elegir como contraejemplos.

Pero las cadenas infinitas y los alfabetos infinitos son una digresión. Las cadenas finitas sobre alfabetos finitos son suficientemente interesantes para el propósito de esta pregunta.

Answer 3

Sí, y muy fácilmente. Para simplificar, supongamos que sólo tenemos las letras $0$ y $1$ (pero cualquier número de letras funcionará perfectamente, sólo será un sistema de base diferente). Podríamos interpretar cualquier cadena como un número, en base $2$ entre $0$ y $1$ - como, la cadena "0110" se convierte en el número $.0110_2=\frac{3}{8}$ . Sin embargo, tenemos un problema con los ceros finales, ya que las cadenas "011", "0110" y "01100" se considerarían todas iguales. Para remediarlo, podemos dividir las cadenas en varias clases distintas, en función del número de ceros que tengan y, si las cadenas pertenecen a clases distintas, utilizamos la siguiente regla:

• Si la cadena $A$ tiene más ceros al final que la cadena $B$ , dejemos que $A>B$ . (por ejemplo, "0100" > "10", ya que el primero tiene dos ceros al final. Del mismo modo, "0100" > "010" - lo que evita el hecho de que $.0100_2=.010_2$ )

A continuación, debemos definir el orden dentro de cada clase. Ingenuamente, nos limitaríamos a comparar representaciones binarias, con un punto decimal al principio. Sin embargo, esto significaría que $1$ es la mayor representación binaria obtenible en cada clase, y $0$ es el menor (como se ha señalado en un comentario) - lo cual es un problema, ya que entonces nuestro orden tiene elementos adyacentes (por ejemplo, el $1$ de una clase determinada y el $0$ de la clase inmediatamente superior). Así, consideramos que una cadena $A$ debe asociarse a la cadena de bits en binario, con el decimal antes del primer $0$ - por lo que "11001" se convierte en $11.001_2$ por ejemplo. Entonces, si $A$ tiene un número asociado mayor que $B$ decimos $A>B$ . No puede haber ningún elemento máximo en cada clase, ya que $A$ es siempre inferior a $A$ con un "1" añadido.

Entonces, podemos construir fácilmente una cadena entre cualquier $A$ y $B$ . En particular, supongamos $A>B$ y $A$ tiene más ceros al final. Entonces $B$ con un "1" antepuesto es mayor que $B$ y menos de $A$ . Si tienen el mismo número de ceros al final, elegimos un número binario (con parte entera) $2^{k}-1$ para algunos $k$ - números como $10_2$ no son representables) entre ellos y escribirlo con el mismo número de ceros finales.

Answer 4

En el caso de las cadenas finitas, el orden lexicográfico es suficiente si se manipula un poco para que una (o más) de las letras del alfabeto se ordene antes que la cadena vacía.

Más detalladamente, supongamos que tenemos un alfabeto de dos letras $\Sigma=\{+,-\}$ . Dadas dos cadenas diferentes $X,Y\in\Sigma^{<\omega}$ donde sin pérdida de generalidad $Y$ no es una subcadena inicial de $X$ (de lo contrario, podemos intercambiarlos): si $a$ es la primera letra de $Y$ tras la mayor subcadena común inicial de $X$ y $Y$ , poner $X<Y$ si $a=+$ y $X>Y$ si $a=-$ .

Esto da un orden lineal denso: dado $X<Z$ tenemos $X<X+<Z$ ou $X<Z-<Z$ .

En el caso de un alfabeto general $\Sigma$ con un orden fijo $\prec$ sobre las letras $a\in\Sigma$ divide el alfabeto en dos conjuntos no vacíos disjuntos $\Sigma=\Sigma^-\cup\Sigma^+$ para que $\Sigma^+$ se cierra hacia arriba en $\prec$ y poner \begin{align*} XaY&<XbZ&&\text{if }a\prec b,\\ X&<XaY&&\text{if }a\in\Sigma^+,\\ XaY&<X&&\text{if }a\in\Sigma^- \end{align*} para todas las cadenas $X,Y,Z$ y cartas $a,b$ . Obsérvese que la única diferencia con el orden lexicográfico estándar se encuentra en la tercera cláusula.

Otra forma de verlo es que consideres cadenas finitas como extendidas en el lado derecho a cadenas infinitas utilizando un símbolo especial $\epsilon\notin\Sigma$ y las ordenas según el orden lexicográfico de las extensiones infinitas, con respecto a alguna ordenación $\prec$ de $\Sigma\cup\{\epsilon\}$ . Si hace $\epsilon$ más pequeño que todas las letras reales $a\in\Sigma$ se obtiene el orden lexicográfico habitual en cadenas finitas, mientras que si hay $a,b\in\Sigma$ tal que $a\prec\epsilon\prec b$ obtienes una orden densa.