1. Prerrequisitos

Abril 29, 2012

Índice

Alfabetos y Lenguajes

Teoría de la Computación

Topología

Probabilidad


 

Alfabetos y Lenguajes

Fijemos $A=\{a_1,\dots,a_Q\}$, $Q\geq 2$, un alfabeto finito.

Definición: $A^*$ es el conjunto de cadenas finitas de elementos de $A$. $\lambda$ es la cadena vacía.

Teorema: $A^*$ dotada de la concatenación es un monoide libre con $\lambda$ igual al elemento nulo.

Definición: $A^+=A^*\setminus \{\lambda\}$. Si $x\in A^*$, $|x|$ es la longitud de $x$. $|\lambda|=0.$

Cualquier orden total sobre $A$ induce un orden lexicográfico sobre $A^*$. Si $a_1<a_2<\dots <a_Q$, el orden lexicográfico sobre $A^*$ es

$$\lambda<a_1<\dots<a_Q<a_1a_1<\dots a_1a_Q<\dots <a_Qa_Q<a_1a_1a_1<\dots$$

Consideramos la siguiente biyección entre los enteros no negativos y las cadenas binarias basadas en el alfabeto binario $A_2=\{0,1\}:$

$$
\begin{aligned}
0&\to \lambda\\
1&\to 0\\
2&\to 1\\
3&\to 00\\
4&\to 10\\
5&\to 10\\
6&\to 11\\
&\,\,\,\vdots
\end{aligned}
$$

La imagen de $n$ será notada $\text{bin}(n)$ y es la representación binaria del número natural $n+1$ sin el 1 inicial. El orden lexicográfico de las cadenas binarias inducido por el orden natural $0<1$ se puede definir en términos de esta biyección: $x,y\in\{0,1\}^*$, $x<y$ si y solo si $\text{bin}^{-1}(x)<\text{bin}^{-1}(y).$

Definición: $\log_Q$ es el logaritmo en base $Q$. $\displaystyle \log n=\lfloor \log_2 (n+1)\rfloor.$

Lema: $|\log_2 n-\log n|\leq 1,$ para todo $n\geq 1$.

Lema: $\log n+\log m-1\leq \log (mn)\leq \log n+\log m +1$ para todo $n,m>0$.

Teorema: La longitud de $\text{bin}(n)$ es igual a $\log n$: $|\text{bin}(n)|=\log n$.

Definición: $\text{string}_Q(n)$ es la $n$-esima cadena sobre el alfabeto $A$ con $Q$ elementos ordenada de acuerdo con el orden lexicográfico. En particular $\text{string}_2(n)=\text{bin}(n)$.

Teorema: La aplicación $\text{string}_Q:\mathbb N\to A^*$ es una función biyectiva que cumple

$$|\text{string}_Q(n)|=\lfloor \log_Q(n(Q-1)+1)\rfloor.$$

Nota: Cuando el alfabeto esté claro escribiremos $\text{string}(n)$ en lugar de $\text{string}_Q(n)$.

Definición:  $x\in A^*$ es prefijo de $y\in A^*$ si existe $z\in A^*$ tal que $y=xz$. Escribimos $x<_p y$. Si $x\in A^*$, $i\in\mathbb N$, entonces $x^i$ es la concatenación $xx\dots x$ ($i$ veces) en el caso $i>0$; $x^0=\lambda$. Dados dos subconjuntos $S,T\subset A^*$, la concatenación $ST$ se define como el conjunto $\{xy: x\in S,y\in T\}$. Para $m\in\mathbb N$, $A^m=\{x\in A^*: |x|=m\}$. Si $m\geq 1$ consideramos el alfabeto $B=A^m$. Se define el monoide libre $B^*=(A^m)^*$.

Nota: Cada $x\in B^*$ pertenece a $A^*$, pero el recíproco es falso.

Definición: Para $x\in B^*$ denotamos por $|x|_m$ la longitud de $x$ de acuerdo con $B$, que es exactamente $|x|/m$. Para $Q\in\mathbb N$, $Q\geq 2$, sea $A_Q$ el alfabeto $\{0,1,\dots,Q-1\}$.

Nota: Los elementos de $A_Q$ son considerados como dígitos usados para representar números en base $Q$. Así, un elemento $a\in A_Q$ denota a la vez el símbolo usado en la representación de números y también el valor numérico en el rango de $0$ a $Q-1$ que representa.

Definición: $(n)_Q$ es la representación del número $n$ en base $Q$. $A^\omega$ es el conjunto de sucesiones infinitas de elementos de $A$.

$$A^\omega=\{\mathbf x=x_1x_2 \dots x_n \ldots : x_i\in A\}.$$

Definición: Para $\mathbf x\in A^\omega$, y $n\in\mathbb N$, $\mathbf x(n)=x_1\dots x_n \in A^*$.

Definición: Para $S\subset A^*$: $SA^\omega=\{\mathbf x\in A^\omega: \mathbf x(n)\in S, \text { para algún } n\geq 1\}$. Para $x\in A^*$: $xA^\omega=\{x\}A^\omega$.

Definición: Una función parcial $\varphi: X \overset{o}{\to} Y$ (también suele notarse como $\varphi: X -\to Y$) es una función definida sobre un subconjunto $Z$ de $X$, llamado dominio de $\varphi$ y escrito $\text{dom}(\varphi)=Z$.

Definición: Si $\text{dom}(\varphi)=X$ diremos que $\varphi$ es total y se indica escribiendo $\varphi: X\to Y$.

Nota: Para $x\in \text{dom}(\varphi)$ escribiremos $\varphi(x)<\infty$ (también $\varphi(x)\downarrow$); si $x \notin \text{dom}(\varphi)$ escribimos $\varphi(X)=\infty$ ($\varphi(x)\uparrow$).

Definición: El rango de $\varphi$ es el conjunto $\text{rango}(\varphi)=\{\varphi(x): x\in \text{dom}(\varphi)\}$. El grafo de $\varphi$ es el conjunto $\text{grafo}(\varphi)=\{(x,\varphi(x)): x\in \text{dom}(\varphi)\}$. 

Definición: Dos funciones parciales $\varphi,f: X\overset{o}{\to} Y$ son iguales si tienen el mismo dominio y $f(x)=\varphi(x)$ para todo $x$ punto del dominio.

Teoría de la computación

Un algoritmo para computar una función parcial $\varphi: \mathbb N \to^o \mathbb N$ es un conjunto finito de instrucciones que, dado como entrada $x\in \text{dom}(\varphi)$, devuelve después de un número finito de pasos la salida $y=\varphi(x)$. El algoritmo debe especificar sin ambigüedades cómo se realiza cada paso de la computación a partir del anterior.

Si $\varphi$ es una función parcial que se computa por un algoritmo entonces dicemos que $\varphi$ es una función parcial computable; si $\varphi$ es total diremos simplemente que $\varphi$ es una función computable.

Topología

Definición: Dado un conjunto $X$, una topología es una colección $\tau$ de subconjuntos de $X$ que cumplen las siguientes propiedades:

  1. $\emptyset \in \tau$, $X\in \tau$
  2. Para todo $U\in \tau, V \in \tau$, $U\cap V\in \tau$.
  3. Para cualquier colección $U_\alpha$ de elementos de $\tau$, $\bigcup U_\alpha \in \tau$.

Definición: Los elementos de la topología se llaman abiertos y sus complementarios se llaman cerrados. El par $(X,\tau)$ se llama espacio topológico.

Definición: Dada una topología se define el operador clausura

$$Z\to \text{Cl}(Z)=\bigcap \{F| Z\subset F, F \text{ cerrado }\}$$

Teorema: [Kuratowski] Propiedades del operador clausura:

  1. $\text{Cl}(\emptyset)=\emptyset$.
  2. $ \text{Cl}(\text{Cl}(Z))=\text{Cl}(Z)$.
  3. $\text{Cl}(Y\cup Z)=\text{Cl}(Y)\cup \text{Cl}(Z).$

Probabilidad

Definición: Un anillo de Boole es una clase de conjuntos $R$ cerrada por uniones y por diferencias. Un álgebra de conjuntos es una clase de conjuntos $R$ cerrada por unión y complementarios. Un $\sigma$-anillo es un anillo cerrado por uniones numerables. Una $\sigma$-álgebra es un álgebra cerrada por uniones numerables.

Ejemplo: Si $X$ es un conjunto cualquiera, la clase de los subconjuntos finitos de $X$ es un anillo pero no es un álgebra a menos que $X$ sea un conjunto finito.

Ejemplo: La colección de todos los conjuntos finitos y cofinitos de $X$ es un álgebra; no es una $\sigma$-álgebra a menos que $X$ sea finito.

Definición: La colección de todos los subconjuntos de $X$ es una $\sigma$-álgebra.

Teorema: Dada $\mathcal C$ una colección de subconjuntos de $X$, existe la menor $\sigma$-álgebra que contiene a $\mathcal C$.

Definición: La menor $\sigma$-algebra que contiene a $\mathcal C$ es la $\sigma$-álgebra generada por $\mathcal C$. La $\sigma$-álgebra generada por los abiertos de un espacio topológico se llama $\sigma$-álgebra de Borel. Los conjuntos de esta $\sigma$-álgebra se llaman borelianos.

Definición: Sea $R$ un anillo. Una medida es una función de conjuntos definida sobre $R$, a valores reales, no negativa, numerablemente aditiva, tal que $\mu(\emptyset)=0.$

Nota: Numerablemente aditiva es que $\displaystyle \sum_{n=1}^\infty \mu(A_n)=\mu(\bigcup_{n=1}^\infty A_n)$ para toda colección $\{A_n\}_{n\in \mathbb N}$ de elementos de $R$, disjuntos y tales que $ \bigcup A_n \in R$.

Definición: Una medida para la que el espacio total tiene medida uno es una probabilidad.

Todo anillo $R$ genera un único $\sigma$-anillo $S(R)$. Si $\mu$ es una medida finita sobre $R$, existe una única medida $\overline \mu$ sobre $S(R)$ tal que $\overline\mu(A)=\mu(A)$ para todo $A\in R$. La medida $\overline\mu$ es finita.

Sea $A^\omega$ el espacio total. La clase de conjuntos
$$\mathcal P=\{xA^\omega: x\in A^*\}\bigcup \{\emptyset\},$$
tiene las siguientes propiedades:

  1. $xA^\omega \subset yA^\omega$ si y solo si $y<_p x.$
  2. $xA^\omega \cap yA^\omega \neq \emptyset $ si y solo si $y<_p x$ o si $x<_p y$.
  3. $X\cap Y\in\{X,Y,\emptyset\}$ para todos $X,Y\in\mathcal P$.

Consideramos sobre $A^\omega$ la topología generada por $\mathcal P$, que coincide con la topología producto sobre $A^\omega$.

Teorema: Todo elemento de $\mathcal P$ es abierto y compacto.

Teorema: La $\sigma$-álgebra generada por $\mathcal P$ es la $\sigma$-álgebra de Borel.

Demostración: Cada elemento de $\mathcal P$ es abierto, luego $\mathcal P$ está contenido en la $\sigma$-álgebra de Borel. Recíprocamente, cualquier abierto es una unión numerable de la base de elementos que genera la topología producto, y cada conjunto de esta base es una unión finita de elementos de $\mathcal P$.

Ejemplo: Sea $$X=\{\mathbf x \in A^\omega | \lim_{n\to+\infty}\frac{x_1+\dots+x_n}{n}=\frac{1}{2}\}.$$
En término de conjuntos podemos escribir
$$X=\bigcap_{k=1}^\infty\bigcup_{m=1}^\infty\bigcap _{n=m}^\infty \left\{ \mathbf x\in A^\omega: \left|\frac{x_1+\dots+x_n}{n}-\frac{1}{2}\right|<\frac{1}{k}\right\}.$$
Para cada $k,n$ el conjunto $\displaystyle \left\{ \mathbf x\in A^\omega: \left|\frac{x_1+\dots+x_n}{n}-\frac{1}{2}\right|<\frac{1}{k}\right\}$ es una unión finita de conjuntos abiertos del tipo $uA^\omega\in \mathcal P$ con $u$ cadena de longitud $n$ tal que $\displaystyle \left|\frac{u_1+\dots+u_n}{n}-\frac{1}{2}\right|<\frac{1}{k}.$ $X$ es por tanto un boreliano.

Teorema: Si $X$ y $X_i$ están en $\mathcal P$, $X=\bigcup X_i$, y los $X_i$ son disjuntos, entonces todos los $X_i=\emptyset$ salvo a lo sumo una cantidad finita de ellos.

Para cada cadena $x\in A^*$ y para cada $k\geq |x|$, existe una partición natural de $xA^\omega$ del siguiente modo

$$x A^\omega=\bigcup xyA^\omega$$
donde la unión recorre el conjunto de los $y\in A^*$, $|y|=k-|x|$.

Definición: $\mathcal C$ es la clase de conjuntos formados por uniones finitas y disjuntas de elementos de $\mathcal P$.

Teorema: $\mathcal C$ es un álgebra.

Demostración: Como el total $A^\omega$ está en $\mathcal C$, entonces es lo mismo álgebra que anillo. Hay que probar que $\mathcal C$ es cerrada por uniones y por complementario.

Si $X,Y\in \mathcal C$, entonces $X\cup Y$ también está en $\mathcal C$ puesto que la unión se puede poner como una unión disjunta de elementos de $\mathcal P$ ya que dados dos elementos de $\mathcal P$ o son disjuntos, o uno está contenido dentro de otro.

Sea $X\in \mathcal C$, $\displaystyle X=\bigcup_{i=1}^n x_i A^\omega$. El complementario de $X$ es
$$\displaystyle A^\omega\setminus X=\bigcap_{i=1}^n (A^\omega \setminus x_iA^\omega).$$
Es claro que $\displaystyle A^\omega \setminus x_iA^\omega=\bigcup_{y} yA^\omega$, donde la suma es en los $y\in A^*$, tales que $|y|=|x_i|$, $y\neq x_i$, luego está en $\mathcal C$.

Lo único que queda por demostrar es que $\mathcal C$ es estable por intersecciones.


Sean $X,Y\in \mathcal C$, $X=\bigcup_{i=1}^m x_i A^\omega$ e $Y=\bigcup_{j=1}^n y_iA^\omega$. Entonces
$$X\cap Y=\bigcup_{i=1}^m \bigcup_{j=1}^n X_i\cap Y_j$$
y como $X_i\cap Y_j\in \mathcal Q$ se deduce que $X\cap Y\in \mathcal C.$

Teorema: Existe una biyección entre las medidas de probabilidad definidas sobre la $\sigma$-álgebra generada por $\mathcal C$ y las funciones $h:A^*\to[0,1]$ que cumplen las propiedades:

  1. $h(\lambda)=1$.
  2. $\displaystyle h(x)=\sum_{i=1}^Q h(xa_ i)$

Demostración: Obsérvese que para todo $x\in A^*$:
$$h(x)=\sum_{|v|=l} h(xv)$$
Para cada $h$ definimos la medida $\mu_h:\mathcal C\to [0,1]$ como
$$\mu_h(\emptyset)=0, \mu_h\left(\bigcup_{i=1}^m x_i A^\omega \right)=\sum_{i=1}^m h(x_i)$$

La definición es correcta pues si $X\in \mathcal C$ tiene dos representaciones distintas como uniones disjuntas:
$$X=\bigcup_{i=1}^n x_iA^\omega=\bigcup_{j=1}^n y_jA^\omega,$$
se tiene que $$\sum_{i=1}^m h(x_i)=\sum_{j=1}^n y_jA^\omega.$$

Probemos que $\mu_h$ es finitamente aditiva. Si $\displaystyle X=\bigcup-{i=1}^m x_i A^\omega\in \mathcal C$, y $\displaystyle X=\bigcup_{j=1}^n Y_j$, con $Y_j=\bigcup_{k=1}^{n_j} y_{j,k}A^\omega\in \mathcal C$ disjuntos dos a dos. Entonces:
$$X=\bigcup_{j=1}^n \bigcup_{k=1}^{n_j} y_{j,k} A^\omega.$$

De acuerdo con la definición de $\mu_h$
$$\mu_h(X)=\sum_{i=1}^n h(x_i),$$
$$\sum_{j=1}^n \mu_h(Y_j)=\sum_{j=1}^n \sum_{k=1}^{n_j} h(y_{j,k}),$$
y la suma de la derecha es igual a $\mu_h(X)$, puesto que
$$X=\bigcup_{j=1}^n \bigcup_{k=1}^{n_j} y_{j,k} A^\omega=\bigcup_{i=1}^m x_iA^\omega,$$
y $\mu$ está bien definida.

El último paso consiste en probar que $\mu_h$ es numerablemente aditiva. Sea $\displaystyle X=\bigcup_{i=1}^m Y_I \in \mathcal C$, donde los $Y_i\in \mathcal P$ son disjuntos dos a dos. Supóngase que $\displaystyle X=\bigcup_{n=1}^\infty X_n$ donde $(X_n)\subset \mathcal C$ es una sucesión de conjuntos disjuntos. Tenemos que demostrar que
$$\mu_h(X)=\sum_{n=1}^\infty \mu_h(X_n).$$
Probaremos la igualdad demostrando que en realidad sólo una cantidad finita de $X_n$ puede ser no vacío. Esto se tiene por compacidad.

Si ahora $\mu$ es una medida de probabilidad, definimos $h_\mu$ como
$$h_\mu(x)=\mu(xA^\omega),$$
Primero, $h_\mu(\lambda)=\mu(\lambda A^\omega)=\mu(A^\omega)=1$. Ahora, sea $x\in A^*$ y calculamos
$$\sum_{i=1}^Q h_\mu(xa_i)=\sum_{i=1}^Q \mu(xa_iA^\omega)=\mu(xA^\omega)=h_\mu(x),$$
debido a la igualdad
$$xA^\omega=\bigcup_{i=1}^Q xa_iA^\omega,$$
una unión disjunta.

Las asignaciones $\mu\to h_\mu$ y $h\to \mu_h$ son inversas. Sea $h$ una función cumpliendo las propiedades y $\mu$ la medida asociada; probemos que $h_\mu=h$. Para $x\in A^*$ tenemos
$$h_\mu(x)=\mu_h(xA^\omega)=h(x).$$
Recíprocamente, sea $\mu$ una medida de probabilidad, $h$ la función asociada, y $\mu_h$ la medida asociada a $h$. Tenemos que probar que $\mu=\mu_h$. Es inmediato comprobar que coinciden sobre $\mathcal P$ y por ello sobre $\mathcal C$.

 Definición: Un semianillo $\mathcal{SR}$ es una clase no vacía de conjuntos tales que

  1. es cerrada por intersecciones.
  2. si $E,F\subset \mathcal{SR}$, $E\subset F$, entonces existe una cadena finita $E=C_0\subset C_1\subset C_2\subset \dots \subset C_n=F$ de modo que $C_i-C_{i-1}\in \mathcal{SR}$ para $i=1,2,\dots,n$.

Teorema: La case $\mathcal P$ es un semianillo si y solo si $Q=2$.

Demostración: Supongamos que $Q=2$.Sean $X=xyA^\omega\subset xA^\omega=Y$ en $\mathcal P$, $y=y_1y_2\dots y_t$. Entonces
$$X=X_0=xy_1y_2\dots y_t A^\omega \subset X_1=xy_1y_2\dots y_{t-1} A^\omega \subset X_{t-1}=xy_1A^\omega \subset X_t=Y,$$
y las diferencias
$$
\begin{aligned}
X_i-X_{i-1}&=xy_1\dots y_{t-i}A^\omega \setminus xy_1\dots y_{t-i+1}A^\omega\\
&=xy_1\dots y_{t-i}\overline{y_{t-i+1}}A^\omega\\
\end{aligned}
$$
donde $\overline{y_{j}}$ es $a_1$ si $y_j=a_2$ y $a_2$ si $y_j=a_1$. Por lo tanto, las diferencias $X_i-X_{i-1}\in \mathcal P$.

Si $Q>2$ las cosas cambian. Sea $X=xa_iA^\omega\subset xA^\omega=Y$. Si $X\subset Z\subset Y$ y $Z$ no es $X$, entonces $Z=Y$ y la diferencia
$$Y\setminus X=\bigcup_{j=1,j\neq i}^n xa_jA^\omega$$
y consecuentemente la diferencia $Z\setminus Y$ no pertenece a $\mathcal P$.

Nota: El teorema de extensión de medidas de un semianillo al anillo generado no se aplica para $Q>2$.

Nota: La medida más importante es la medida uniforme

$$\mu(xA^\omega)=Q^{-|x|}$$
que obviamente satisface las condiciones del teorema 7.
Existe una correspondencia entre esta medida y la medida de Lebesgue sobre el intervalo $[0,1]$.