Sobre una propiedad de los conjuntos de secuencias infinitas

Question

Considere un conjunto finito de símbolos $\Sigma$ y dos conjuntos cualesquiera $P$ y $Q$ de secuencias infinitas construidas a partir de los símbolos de $\Sigma$ .

También hay que tener en cuenta la propiedad $s$ definido con respecto a cualquier conjunto de secuencias infinitas $A$ tal que

$$s(A) = \lim_{n\to\infty} \sqrt[n]{f_n(A)}$$

donde $f_n(A)$ es igual al número de secuencias de símbolos distintas de longitud $n$ presente al principio de al menos una secuencia en $A$ . (Heurísticamente, $f_n(A)$ cuenta el número de "prefijos" distintos de longitud $n$ presente en elementos de $A$ .)

Teniendo en cuenta estas definiciones, ¿cómo se puede demostrar que: $$s(P\cup Q) = \max \{s(P),s(Q)\}$$

Intenté demostrarlo asumiendo $s(P) \geq s(Q)$ , "sandwiching" $\sqrt[n]{f_n(P) + f_n(Q)}$ entre $\sqrt[n]{f_n(P)}$ y $\sqrt[n]{f_n(P) + f_n(P)}$ y mostrando que ambos convergen al mismo límite. Sin embargo, no puedo utilizar este truco ya que no tengo ninguna declaración que $f_n(P) \geq f_n(Q)$ para todos $n$ , justo en el límite de estas expresiones en $n \to \infty$ .

Answer 1

Déjame escribir $\Sigma^*$ para el conjunto de todas las secuencias infinitas de elementos de $\Sigma$ . Para $P \subseteq \Sigma^*$ , dejemos que $p_n(P)$ sea el conjunto de secuencias de longitud $n$ que son prefijos de alguna secuencia en $P$ para que $f_n(P) = |p_n(P)|$ . Evidentemente, si $P, Q \subseteq \Sigma^*$ tenemos: $$ p_n(P \cup Q) = p_n(P) \cup p_n(Q) $$ por lo que por el principio de inclusión-exclusión: $$ |p_n(P \cup Q)| = |p_n(P)| + |p_n(Q)| - |p_n(P) \cap p_n(Q)| $$ Supongamos que $\lim_{n \to\infty}f_n(P) \ge \lim_{n \to \infty}f_n(Q)$ y que $T = \{n : \Bbb{N} \mid f_n(P) \ge f_n(Q)\}$ . Podemos suponer, por ejemplo, que $T$ es infinito, porque, si no, tenemos que $f_n(Q) > f_n(P)$ para un número infinito de $n$ pero luego $\lim_{n \to \infty}f_n(Q) = \lim_{n\to \infty}f_n(P)$ y, después de intercambiar $P$ y $Q$ el conjunto resultante $T$ será infinito, digamos $T = \{ t_1, t_2, \ldots\}$ con $t_1< t_2 < \ldots$ .

Ahora, para $n \in T$ si dividimos nuestra ecuación por $|p_n(P \cup Q)|$ a través de $|p_n(P)|$ y tomar $n$ -raíces, obtenemos $$ 1 \le \frac{\sqrt[n]{|p_n(P \cup Q)|}}{\sqrt[n]{|p_n(P)|}} = \sqrt[n]{1 + \frac{|p_n(Q)|}{|p_n(P|} - \frac{|p_n(P) \cap p_n(Q)|}{|p_n(P)|}} \le \sqrt[n]{2} $$ Por el teorema del apretón, obtenemos:

$$ \lim_{n \to \infty}\left( \frac{\sqrt[t_n]{f_{t_n}(P \cup Q)}}{\sqrt[t_n]{f_{t_n}(P)}}\right) = \lim_{n \to \infty}\left( \frac{\sqrt[t_n]{|p_{t_n}(P \cup Q)|}}{\sqrt[t_n]{|p_{t_n}(P)|}}\right) = 1 $$ que da a su reclamación.