text:
User:Tomaspgwk/sandbox

= Notacion y conceptos basicos =

Usaremos $\mathbf{R}$ para denotar el conjunto de los numeros reales, $\mathbf{Z}$  para denotar el conjunto de los numeros enteros, $\mathbf{N}$  para denotar el conjunto de los numeros naturales y $\omega$  para denotar al conjunto $\mathbf{N}\cup\{0\}$.

Dado un conjunto $A$, usaremos $\mathcal{P}(A)$ para denotar el conjunto formado por todos los subconjuntos de $A$ , es decir: $$\mathcal{P}(A)=\{S:S\subseteq A\}$$ Si $A$  es un conjunto finito, entonces $\left\vert A\right\vert$  denotara la cantidad de elementos de $A$.

Para $x,y\in\omega$, definamos $$x\dot{-}y=\left\{ \begin{array}{lll} x-y & & \text{si }x\geq y\\ 0 & & \text{caso contrario} \end{array}\right.$$ Dados $x,y\in\omega$ diremos que $x$  divide a $y$  cuando haya un $z\in\omega$  tal que $y=z.x$. Notar que $0$ divide a $0$, $3$  divide a $0$  y $0$  no divide a $23$. Escribiremos $x\mid y$ para expresar que $x$  divide a $y$. Dados $x,y\in\omega$, diremos que $x$ e $y$  son coprimos cuando $1$  sea el unico elemento de $\omega$  que divide a ambos. Notese que $x$ e $y$  no son son coprimos sii existe un numero primo $p\in\omega$  que los divide a ambos

Si bien no hay una definicion natural en matematica de cuanto vale $0^{0}$ ($0$  elevado a la $0$ ), por convencion para nosotros $0^{0}=1$

Conjuntos
Supondremos que el lector sabe las nociones basicas sobre conjuntos, aunque resaltaremos algunas de las mas importantes para que el lector las repase.

La propiedad de extensionalidad nos dice que, dados conjuntos $A,B$, se tiene que $A=B$ si y solo si para cada objeto $x$  se da que $$x\in A\text{ si y solo si }x\in B$$ Esta propiedad es importante metodologicamente ya que a la hora de probar que dos conjuntos $A,B$  son iguales, extensionalidad nos asegura que basta con ver que se dan las dos inclusiones $A\subseteq B$  y $B\subseteq A$.

Otro tema importante es manejar correctamente la notacion cuando definimos un conjunto usando llaves y mediante propiedades que caracterizan la pertenencia al mismo. Algunos ejemplos

 * 1) $\{x\in\mathbf{N}:x=1$  o $x\geq5\}$
 * 2) $\{x:x\in\mathbf{R}$  y $x^{2}\geq100\}$
 * 3) $\{x:x=100\}$
 * 4) $\{x^{2}+1:x\in\omega\}$
 * 5) $\{x+y+z:x,y,z\in\{1,2\}\}$

Dejamos al lector la tarea de entender en forma precisa que conjunto se esta denotando en cada caso.

Producto carteciano
Dados conjuntos $A_{1},...,A_{n}$, con $n\geq2$ , usaremos $A_{1}\times...\times A_{n}$ para denotar el producto Cartesiano de $A_{1},...,A_{n}$ , es decir el conjunto formado por todas las $n$ -uplas $(a_{1},...,a_{n})$  tales que $a_{1}\in A_{1},...,a_{n}\in A_{n}$. Si $A_{1}=...=A_{n}=A$, con $n\geq2$ , entonces escribiremos $A^{n}$ en lugar de $A_{1}\times...\times A_{n}$. Para $n=1$, definimos $A^{n}=A$ , es decir $A^{1}=A$. Usaremos $\Diamond$ para denotar la unica $0$ -upla. Definimos entonces $A^{0}=\{\Diamond\}$. Si $A$ es un conjunto denotaremos con $A^{\mathbf{N}}$  al conjunto formado por todas las infinituplas $(a_{1},a_{2},...)$  tales que $a_{i}\in A$  para cada $i\in\mathbf{N}$. Por ejemplo $$(1,2,3,4,...)\in\omega^{\mathbf{N}}$$ donde $(1,2,3,4,...)$ es una forma intuitiva de denotar la infinitupla cuyo $i$ -esimo elemento es el numero natural $i$.

Si $(A_{1},A_{2},...)$ es una infinitupla de conjuntos, entonces usaremos $\bigcup\nolimits _{i=1}^{\infty}A_{i}$  o $\bigcup\nolimits _{i\geq1}A_{i}$  para denotar al conjunto $$\{a:a\in A_{i}\mathrm{,\ para\ algun\ }i\in\mathbf{N}\}$$

Alfabetos
Un alfabeto es un conjunto finito de simbolos. Notese que $\emptyset$ es un alfabeto. Si $\Sigma$ es un alfabeto, entonces $\Sigma^{\ast}$  denotara el conjunto de todas las palabras formadas con simbolos de $\Sigma$. Las palabras de longitud $1$ son exactamente los elementos de $\Sigma$, en particular esto nos dice que $\Sigma\subseteq\Sigma^{\ast}$. La unica palabra de longitud $0$ es denotada con $\varepsilon$. Ya que en $\varepsilon$ no ocurren simbolos, tenemos que $\varepsilon\in\Sigma^{\ast}$, para cualquier alfabeto, mas aun notese que $\emptyset^{\ast}=\{\varepsilon\}$. Usaremos $\left\vert \alpha\right\vert$ para denotar la longitud de la palabra $\alpha$. Si $\alpha\in\Sigma^{\ast}$ y $\sigma\in\Sigma$, usaremos $\left\vert \alpha\right\vert _{\sigma}$  para denotar la cantidad de ocurrencias del simbolo $\sigma$  en $\alpha$. Usaremos $\Sigma^{+}$ para denotar al conjunto $\Sigma^{\ast}-\{\varepsilon\}$. Notese que funciones, $n$ -uplas y palabras son objetos de distinto tipo, por lo cual $\emptyset$, $\Diamond$ y $\varepsilon$  son tres objetos matematicos diferentes.

Si $\alpha_{1},...,\alpha_{n}\in\Sigma^{\ast}$, con $n\geq0$ , usaremos $\alpha_{1}...\alpha_{n}$ para denotar la concatenacion de las palabras $\alpha_{1},...,\alpha_{n}$  (notese que cuando $n=0$ , resulta que $\alpha_{1}...\alpha_{n}=\varepsilon$ ). Si $\alpha_{1}=...=\alpha_{n}=\alpha$, entonces escribiremos $\alpha^{n}$ en lugar de $\alpha_{1}...\alpha_{n}$. O sea que $\alpha^{0}=\varepsilon$.

Diremos que $\alpha$ es subpalabra (propia) de $\beta$  cuando ($\alpha\notin\{\varepsilon,\beta\}$  y) existan palabras $\delta,\gamma$  tales que $\beta=\delta\alpha\gamma$. Diremos que $\beta$ es un tramo inicial (propio) de $\alpha$  si hay una palabra $\gamma$  tal que $\alpha=\beta\gamma$  (y $\beta\notin\{\varepsilon,\alpha\}$ ). En forma similar se define tramo final (propio).

Dados $i\in\omega$ y $\alpha\in\Sigma^{\ast}$  definamos $$\left[\alpha\right]_{i}=\left\{ \begin{array}{lll} i\text{-esimo elemento de }\alpha & & \text{si }1\leq i\leq\left\vert \alpha\right\vert \\ \varepsilon & & \text{caso contrario} \end{array}\right.$$ Dada $\gamma\in\Sigma^{\ast}$, definamos $$\gamma^{R}=\left\{ \begin{array}{lll} \lbrack\gamma]_{\left\vert \gamma\right\vert }[\gamma]_{\left\vert \gamma\right\vert -1}...[\gamma]_{1} & & \text{si }\left\vert \gamma\right\vert \geq1\\ \varepsilon & & \text{caso contrario} \end{array}\right.$$ La palabra $\gamma^{R}$ es llamada la resiproca de $\gamma$.

Ocurrencias
Dadas palabras $\alpha,\beta\in\Sigma^{\ast}$, con $\left\vert \alpha\right\vert ,\left\vert \beta\right\vert \geq1$ , y un natural $i\in\{1,...,\left\vert \beta\right\vert \}$ , se dice que $\alpha$ ocurre a partir de $i$  en $\beta$  cuando se de que existan palabras $\delta,\gamma$  tales que $\beta=\delta\alpha\gamma$  y $\left\vert \delta\right\vert =i-1$. Intuitivamente hablando $\alpha$ ocurre a partir de $i$  en $\beta$  cuando se de que si comensamos a leer desde el lugar $i$ -esimo de $\beta$  en adelante, leeremos la palabra $\alpha$  completa y luego posiblemente seguiran otros simbolos.

Notese que una palabra $\alpha$ puede ocurrir en $\beta$, a partir de $i$ , y tambien a partir de $j$ , con $i\neq j$. En virtud de esto, hablaremos de las distintas ocurrencias de $\alpha$ en $\beta$. Por ejemplo hay dos ocurrencias de la palabra $aba$  en la palabra $$cccccccabaccccabaccccc$$ y tambien hay dos ocurrencias de la palabra $aba$  en la palabra $$cccccccababacccccccccc$$ En el primer caso diremos que dichas ocurrencias de $aba$ son disjuntas ya que ocupan espacios disjuntos dentro de la palabra. En cambio en el segundo caso puede apreciarse que las dos ocurrencias se superponen en una posicion. A veces diremos que una ocurrencia esta contenida o sucede dentro de otra. Por ejemplo la segunda ocurrencia de $ab$ en $babbbfabcccfabccc$  esta contenida en la primer ocurrencia de $fabc$  en $babbbfabcccfabccc$.

No definiremos en forma matematica precisa el concepto de ocurrencia pero el lector no tendra problemas en comprenderlo y manejarlo en forma correcta.

Reemplazos de ocurrencias
Tambien haremos reemplazos de ocurrencias por palabras. Por ejemplo el resultado de reemplazar la primer ocurrencia de $abb$ en $ccabbgfgabbgg$  por $oolala$  es la palabra $ccoolalagfgabbgg$. Cuando todas las ocurrencias de una palabra $\alpha$ en una palabra $\beta$  sean disjuntas entre si, podemos hablar del resultado de reeplazar simultaneamente cada ocurrencia de $\alpha$  en $\beta$  por $\gamma$. Por ejemplo si tenemos $$\begin{aligned} \alpha & =yet\\ \beta & =ghsyetcjjjyetbcpyeteabc\\ \gamma & =\%\% \end{aligned}$$ entonces $ghs\%\%cjjj\%\%bcp\%\%eabc$ es el resultado de reemplazar simultaneamente cada ocurrencia de $\alpha$  en $\beta$  por $\gamma$. Es importante notar que los reemplazos se hacen simultaneamente y no secuencialmente (i.e. reemplazando la primer ocurrencia de $\alpha$ por $\gamma$  y luego al resultado reemplazarle la primer ocurrencia de $\alpha$  por $\gamma$  y asi sucesivamente). Obviamente el reemplazo secuencial puede dar un resultado distinto al simultaneo (que es el que usaremos en general) e incluso puede suceder que en el reemplazo secuencial el proceso se pueda iterar indefinidamente. Dejamos al lector armar ejemplos de estas cituaciones.

Tambien se pueden hacer reemplazos simultaneos de distintas palabras en una palabra dada. Supongamos tenemos palabras $\alpha_{1},...,\alpha_{n}$ (con $\alpha_{i}\neq\alpha_{j}$, para $i\neq j$ ) las cuales tienen la propiedad de que las distintas ocurrencias de ellas en la palabra $\beta$  son siempre disjuntas de a pares, y tenemos ademas palabras $\gamma_{1},...,\gamma_{n}$. Entonces hablaremos del resultado de reemplazar simultaneamente:

 * 1) cada ocurrencia de $\alpha_{1}$  en $\beta$, por $\gamma_{1}$
 * 2) cada ocurrencia de $\alpha_{2}$  en $\beta$, por $\gamma_{2}$
 * 3) $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots$
 * 4) cada ocurrencia de $\alpha_{n}$  en $\beta$, por $\gamma_{n}$

Por ejemplo si tomamos $$\begin{aligned} \alpha_{1} & =gh\\ \alpha_{2} & =yet\\ \alpha_{3} & =ana\\ \beta & =ghbbbyetbbgh\%\%ana\#\#ana!!!ana\\ \gamma_{1} & =AA\\ \gamma_{2} & =BBBB\\ \gamma_{3} & =CCC \end{aligned}$$ entonces $AAbbbBBBBbbAA\%\%CCC\#\#CCC!!!CCC$ es el resultado de reemplazar simultaneamente:

 * 1) cada ocurrencia de $\alpha_{1}$  en $\beta$, por $\gamma_{1}$
 * 2) cada ocurrencia de $\alpha_{2}$  en $\beta$, por $\gamma_{2}$
 * 3) cada ocurrencia de $\alpha_{3}$  en $\beta$, por $\gamma_{3}$

Matematica orientada a objetos
Nuestro estilo o enfoque matematico pondra enfasis en los objetos, es decir haremos matematica prestando atencion a los distintos objetos matematicos involucrados, los cuales siempre seran definidos en forma precisa en terminos de objetos mas primitivos. Hay ciertos objetos matematicos los cuales no definiremos y supondremos que el lector tiene una idea clara y precisa de los mismos. Por ejemplo un tipo de objeto matematico, quizas el mas famoso, son los numeros. No diremos que es un numero pero supondremos que el lector tiene una intuicion clara acerca de este tipo de objetos y de sus propiedades basicas. Otro tipo de objeto que no definiremos y que sera clave para nuestro enfoque son los conjuntos. Nuevamente, no diremos que es un conjunto pero supondremos que el lector tiene una intuicion clara acerca de estos objetos y sus propiedades basicas. Es importante que en nuestro enfoque, numeros y conjuntos son objetos de distinta naturaleza por lo cual nunca un numero es un conjunto ni un conjunto es un numero. En particular esto nos dice que el numero $0$ y el conjunto $\emptyset$  son objetos distintos. Otro tipo de objeto matematico muy importante para la matematica discreta son los simbolos. No discutiremos que es un simbolo sino que aceptaremos este concepto en forma primitiva. Tambien constituyen un tipo de objeto matematico las palabras, las cuales intuitivamente hablando son juxtaposiciones de simbolos. Otro tipo de objeto matematico muy importante son los pares ordenados o 2-uplas, es decir los objetos de la forma $(a,b)$, donde $a$ y $b$  son objetos matematicos cualesquiera. Tambien son objetos matematicos y de distinta naturaleza las 3-uplas, las 4-uplas y en general las $n$ -uplas para $n$ un numero natural mayor o igual a $2$. Cabe destacar que en nuestro enfoque no habra 1-uplas. Sin envargo, si bien hay una sola 0-upla, ella constituye un tipo de objeto matematico distinto a los antes mensionados. El ultimo tipo de objeto matematico que consideraremos es aquel de las infinituplas.

Tenemos entonces dividido nuestro universo matematico en las distintas categorias de objetos: $$\begin{aligned} & \mathrm{NUMERO}\\ & \mathrm{CONJUNTO}\\ & \mathrm{PALABRA}\\ & 0\mathrm{-UPLA}\\ & 2\mathrm{-UPLA}\\ & 3\mathrm{-UPLA}\\ & \ \ \ \ \ \ \ \ \vdots\\ & \mathrm{INFINITUPLA} \end{aligned}$$ (Notar que los simbolos quedan contenidos en la categoria de las palabras). Es importante entender que las anteriores categorias o tipos de objetos son disjuntas entre si, es decir nunca un numero sera una palabra o una palabra sera una 3-upla etc. Esto nos permite definir una funcion $Ti$ la cual a un objeto matematico le asigna su tipo de objeto matematico segun la lista anterior. Por ejemplo: $$\begin{aligned} Ti(\pi) & =\mathrm{NUMERO}\\ Ti(\mathbf{N}) & =\mathrm{CONJUNTO}\\ Ti(\mathcal{P}(\mathbf{N})) & =\mathrm{CONJUNTO}\\ Ti((1,2,3)) & =3\mathrm{-UPLA}\\ Ti(\mathbf{\emptyset}) & =\mathrm{CONJUNTO}\\ Ti(\varepsilon) & =\mathrm{PALABRA}\\ Ti(\Diamond) & =0\mathrm{-UPLA}\\ Ti(\alpha) & =\mathrm{PALABRA}\text{, si }\alpha\text{ es un simbolo}\\ Ti(f) & =\mathrm{CONJUNTO}\text{, si }f\text{ es una funcion} \end{aligned}$$

El concepto de funcion
Asumiremos que el lector tiene una idea intuitiva del concepto de funcion. Daremos aqui una definicion matematica de dicho concepto. Una funcion es un conjunto $f$ de pares ordenados con la siguiente propiedad

 * 1) Si $(x,y)\in f$  y $(x,z)\in f$, entonces $y=z$.

Por ejemplo, si tomamos $f=\{(x,x^{2}):x\in\omega\}$ se puede ver facilmente que $f$  cumple la propiedad (F). Dada una funcion $f$, definamos $$\begin{aligned} D_{f} & =\text{ dominio de }f=\{x:(x,y)\in f\text{ para algun }y\}\\ I_{f} & =\text{ imagen de }f=\{y:(x,y)\in f\text{ para algun }x\} \end{aligned}$$ A veces escribiremos $\mathrm{Dom}(f)$ y $\operatorname{Im}(f)$  para denotar, respectivamente, el dominio y la imagen de una funcion $f$. Como es usual dado $x\in D_{f}$, usaremos $f(x)$ para denotar al unico $y\in I_{f}$  tal que $(x,y)\in f$. Notese que $\emptyset$ es una funcion y que $D_{\emptyset}=I_{\emptyset}=\emptyset$. Por ejemplo para $f=\{(x,x^{2}):x\in\omega\}$ se tiene que $D_{f}=\omega$  y $I_{f}=\{y:y=x^{2}$  para algun $x\in\omega\}$. Ademas notese que $f(x)=x^{2}$, para cada $x\in D_{f}$.

Escribiremos $f:S\subseteq A\rightarrow B$ para expresar que $f$  es una funcion tal que $D_{f}=S\subseteq A$  y $I_{f}\subseteq B$. Tambien escribiremos $f:A\rightarrow B$ para expresar que $f$  es una funcion tal que $D_{f}=A$  y $I_{f}\subseteq B$. En tal contexto llamaremos a $B$ conjunto de llegada. Por supuesto $B$ no esta determinado por $f$  ya que solo debe cumplir $I_{f}\subseteq B$.

Muchas veces para definir una funcion $f$, lo haremos dando su dominio y su regla de asignacion, es decir especificaremos en forma precisa que conjunto es el dominio de $f$ y ademas especificaremos en forma presisa quien es $f(x)$  para cada $x$  de dicho dominio. Obviamente esto determina por completo a la funcion $f$ ya que $f=\{(x,f(x)):x\in D_{f}\}$. Por ejemplo si decimos que $f$ es la funcion dada por: $$\begin{aligned} D_{f} & =\omega\\ f(x) & =23x^{2} \end{aligned}$$ nos estaremos refiriendo a la funcion $\{(x,23x^{2}):x\in\omega\}$. Tambien escribiremos $$\begin{array}{rll} f:\omega & \rightarrow & \omega\\ x & \rightarrow & 23x^{2} \end{array}$$ para describir a $f$. Es decir, a veces para hacer mas intuitiva aun la descripcion de la funcion, tambien incluiremos un conjunto de llegada de dicha funcion y a la regla de asignacion la escribiremos usando una flecha. Para dar otro ejemplo, si escribimos sea $f$ dada por: $$\begin{array}{rll} f:\mathbf{N} & \rightarrow & \omega\\ x & \rightarrow & \left\{ \begin{array}{ccc} x+1 & & \text{si }x\text{ es par}\\ x^{2} & & \text{si }x\text{ es impar} \end{array}\right. \end{array}$$ estaremos diciendo que $f$ es la funcion $$\{(x,x+1):x\text{ es par y }x\in\mathbf{N}\}\cup\{(x,x^{2}):x\text{ es impar y }x\in\mathbf{N}\}$$

Igualdad de funciones
Sean $f$ y $g$  dos funciones. Ya que las mismas son conjuntos, tendremos que $f$ sera igual a $g$  si y solo si para cada par $(a,b)$, se tiene que $(a,b)\in f$  sii $(a,b)\in g$. Muchas veces sera util el siguiente criterio de igualdad de funciones:

Lemma 1. Sean $f$ y $g$  funciones. Entonces $f=g$ sii $D_{f}=D_{g}$  y para cada $x\in D_{f}$  se tiene que $f(x)=g(x)$

Funcion identidad
Dado un conjunto $A$, a la funcion $$\begin{array}{rll} A & \rightarrow & A\\ a & \rightarrow & a \end{array}$$ La denotaremos con $Id_{A}$ y la llamaremos la funcion identidad sobre $A$. Notese que $Id_{A}=\{(a,a):a\in A\}$.

Composicion de funciones
Dadas funciones $f$ y $g$  definamos la funcion $f\circ g$  de la siguiente manera: $$\begin{aligned} D_{f\circ g} & =\{e\in D_{g}:g(e)\in D_{f}\}\\ f\circ g(e) & =f(g(e)) \end{aligned}$$ Notar que $f\circ g=\{(u,v):$ existe $z$  tal que $(u,z)\in g$  y $(z,v)\in f\}$. Notese que $f\circ g\neq\emptyset$ si y solo si $I_{g}\cap D_{f}\neq\emptyset$, lo cual nos dice que muchas veces sucedera que $f\circ g=\emptyset$

Funciones inyectivas, suryectivas y biyectivas
Una funcion $f$ es inyectiva cuando no se da que $f(a)=f(b)$  para algun par de elementos distintos $a,b\in D_{f}$. Dada una funcion $f:A\rightarrow B$ diremos que $f$  es suryectiva cuando $I_{f}=B$. Debe notarse que el concepto de suryectividad depende de un conjunto de llegada previamente fijado, es decir que no tiene sentido hablar de la suryectividad de una funcion $f$ si no decimos respecto de que conjunto de llegada lo es. Muchas veces diremos que una funcion $f$ es sobre para expresar que es suryectiva.

Dada una funcion $f:A\rightarrow B$ diremos que $f$  es biyectiva cuando $f$  sea inyectiva y suryectiva. Notese que si $f:A\rightarrow B$ es biyectiva, entonces podemos definir una nueva funcion $f^{-1}:B\rightarrow A$, de la siguiente manera: $$f^{-1}(b)=\text{ unico }a\in A\text{ tal que }f(a)=b$$ La funcion $f^{-1}$  sera llamada la inversa de $f$. Notese que $f\circ f^{-1}=Id_{B}$ y $f^{-1}\circ f=Id_{A}$. El siguiente lema muestra que esta ultima propiedad caracteriza la inversa.

Lemma 2. Supongamos $f:A\rightarrow B$ y $g:B\rightarrow A$  son tales que $f\circ g=Id_{B}$  y $g\circ f=Id_{A}$. Entonces $f$ y $g$  son biyectivas, $f^{-1}=g$  y $g^{-1}=f$ .

El nucleo de una funcion
Dada una funcion $f:A\rightarrow B$, definamos: $$\ker(f)=\{(a,b)\in A^{2}:f(a)=f(b)\}$$ El conjunto $\ker(f)$ sera llamado el nucleo de $f$. Notese que $f$ es inyectiva si y solo si $\ker(f)=\{(a,a):a\in A\}$.

Funcion caracteristica de un subconjunto
Sea $X$ un conjunto cualquiera y sea $S\subseteq X$. Usaremos $\chi_{S}^{X}$ para denotar la funcion $$\begin{array}{rcl} \chi_{S}^{X}:X & \rightarrow & \omega\\ x & \rightarrow & \left\{ \begin{array}{c} 1\text{ si }x\in S\\ 0\text{ si }x\notin S \end{array}\right. \end{array}$$ Llamaremos a $\chi_{S}^{X}$ la funcion caracteristica de $S$  con respecto a $X$. Muchas veces cuando el conjunto $X$ este fijo y sea claro el contexto, escribiremos $\chi_{S}$  en lugar de $\chi_{S}^{X}$.

Restriccion de una funcion
Dada una funcion $f$ y un conjunto $S\subseteq D_{f}$, usaremos $f|_{S}$  para denotar la restriccion de $f$  al conjunto $S$ , i.e. $f|_{S}=f\cap(S\times I_{f})$. Notese que $f|_{S}$ es la funcion dada por $$\begin{aligned} D_{f|_{S}} & =S\\ f|_{S}(e) & =f(e)\text{, para cada }e\in S \end{aligned}$$ Notese que cualesquiera sea la funcion $f$ tenemos que $f|_{\emptyset}=\emptyset$  y $f|_{D_{f}}=f$.

Funciones de la forma $[f_{1},...,f_{n}]$
Dadas funciones $f_{1},...,f_{n}$, con $n\geq2$ , definamos la funcion $[f_{1},...,f_{n}]$ de la siguiente manera: $$\begin{aligned} D_{[f_{1},...,f_{n}]} & =D_{f_{1}}\cap...\cap D_{f_{n}}\\ \lbrack f_{1},...,f_{n}](e) & =(f_{1}(e),...,f_{n}(e)) \end{aligned}$$ Notese que $I_{[f_{1},...,f_{n}]}\subseteq I_{f_{1}}\times\cdots\times I_{f_{n}}$. Por conveniencia notacional (que el lector entendera mas adelante) definiremos $[f_{1}]=f_{1}$. Es decir que hemos definido para cada sucecion de funciones $f_{1},...,f_{n}$, con $n\geq1$ , una nueva funcion la cual denotamos con $[f_{1},...,f_{n}]$.

Union de funciones con dominios disjuntos
Una observacion interesante es que si $f_{i}:A_{i}\rightarrow B_{i}$, $i=1,...,k$ , son funciones tales que $A_{i}\cap A_{j}=\emptyset$ para $i\neq j$ , entonces $f_{1}\cup...\cup f_{k}$  es la funcion $$\begin{array}{rll} A_{1}\cup...\cup A_{k} & \rightarrow & B_{1}\cup...\cup B_{k}\\ e & \rightarrow & \left\{ \begin{array}{clc} f_{1}(e) & & \text{si }e\in A_{1}\\ \vdots & & \vdots\\ f_{k}(e) & & \text{si }e\in A_{k} \end{array}\right. \end{array}$$

Relaciones binarias
Sea $A$ un conjunto. Por una relacion binaria sobre $A$ entenderemos un subconjunto de $A^{2}$. Algunos ejemplos:

 * 1) Sea $R=\{(1,2),(2,3)\}$ . Entonces $R$  es una relacion binaria sobre $\mathbf{N}$.
 * 2) Sea $R=\{(x,y)\in\omega^{2}:$  $x$  divide a $y\}$ . Entonces $R$  es una relacion binaria sobre $\omega$.
 * 3) Sea $R=\{(r,t)\in\mathbf{R}^{2}:r\leq t\}$ . Entonces $R$  es una relacion binaria sobre $\mathbf{R}$
 * 4) $\emptyset$  es una relacion binaria sobre $A$, cualesquiera sea el conjunto $A$.
 * 5) Sea $R=\{(x,y)\in\omega^{2}:x<y$  o $y=0\}$ . Entonces $R$  es una relacion binaria sobre $\omega$

Notese que si $R$ es una relacion binaria sobre $A$  y $A\subseteq B$  entonces $R$  es una relacion binaria sobre $B$. Por ejemplo las relaciones dadas en los ejemplos (E1), (E2), (E4) y (E5) tambien son relaciones binarias sobre $\mathbf{R}$. Sin envargo si $R$ es una relacion binaria sobre $B$  y $A\subseteq B$  entonces no necesariamente $R$  sera una relacion binaria sobre $A$  (por que?).

Como es usual, cuando $R$ sea una relacion binaria sobre un conjunto $A$, algunas veces escribiremos $aRb$  en lugar de $(a,b)\in R$.

Propiedades notables de relaciones binarias
Hay algunas propiedades que pueden tener o no las relaciones binarias sobre un conjunto $A$, las cuales son muy importantes en matematica. Algunas de estas son:

 * 1) $xRx$, cualesquiera sea $x\in A$
 * 2) $xRy$  y $yRz$  implica $xRz$, cualesquiera sean $x,y,z\in A$
 * 3) $xRy$  implica $yRx$, cualesquiera sean $x,y\in A$
 * 4) $xRy$  y $yRx$  implica $x=y$, cualesquiera sean $x,y\in A$

Cuando $R$ cumpla la primer propiedad diremos que $R$  es reflexiva, con respecto a $A$. Analogamente diremos que $R$ es transitiva, simetrica o antisimetrica, con respecto a $A$, cuando se den, respectivamente las otras propiedades. Notese que estas propiedades dependen del conjunto $A$, por ejemplo si tomamos $R=\{(r,t)\in\mathbf{N}^{2}:r\leq t\}$ entonces $R$  es una relacion binaria sobre $\mathbf{N}$  y tambien es una relacion binaria sobre $\omega$ , pero es relexiva con respepcto a $\mathbf{N}$  y no lo es con respecto a $\omega$  ya que $(0,0)$  no pertenece a $R$. Sin envargo $R$ es transitiva con respecto a $\mathbf{N}$  y tambien lo es con respecto a $\omega$.

Ordenes parciales
Una relacion binaria $R$ sobre un conjunto $A$  sera llamada un orden parcial sobre $A$  si es reflexiva, transitiva y antisimetrica respecto de $A$. Algunos ejemplos:

 * 1) Sea $R=\{(r,t)\in\mathbf{R}^{2}:r\leq t\}$ . Entonces $R$  es un orden parcial sobre $\mathbf{R}$, llamado el orden usual de $\mathbf{R}$
 * 2) Sea $R=\{(1,2),(1,3),(1,1),(2,2),(3,3)\}$ . Entonces $R$  es un orden parcial sobre $\{1,2,3\}$
 * 3) Sea $R=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subseteq T\}$ . Entonces $R$  es un orden parcial sobre $\mathcal{P}(\omega)$
 * 4) Sea $R=\{(x,y)\in\omega^{2}:$  $x\leq y\}$ . Entonces $R$  es un orden parcial sobre $\omega$.
 * 5) Sea $R=\{(1,1)\}$ . Entonces $R$  es un orden parcial sobre $\{1\}$.
 * 6) $\{(a,b):a=b\}$  es un orden parcial sobre $A$, cualesquira sea el conjunto $A$
 * 7) Sea $\mathrm{\leq}=\{(n,m)\in\mathbf{N}^{2}:n\mid m\}$ . Es facil ver que $\leq$  es un orden parcial sobre $\mathbf{N}$

Notese que las relaciones dadas en (E1) y (E4) son distintas, ademas la relacion dada en (E4) no es un orden parcial sobre $\mathbf{R}$ (por que?).

Muchas veces denotaremos con $\leq$ a una relacion binaria que sea un orden parcial. Esto hace mas intuitiva nuestra escritura pero siempre hay que tener en cuenta que $\leq$ en estos casos esta denotando cierto conjunto de pares ordenados previamente definido.

Usaremos la siguiente

 * 1) Si hemos denotado con $\leq$  a cierto orden parcial sobre un conjunto $A$, entonces
 * 2) Denotaremos con $<$  a la relacion binaria $\{(a,b)\in A^{2}:a\leq b$  y $a\neq b\}$ . Es decir que $\mathrm{<}=\{(a,b)\in A^{2}:a\leq b$  y $a\neq b\}$ . Cuando se de $a<b$  diremos que $a$  es menor que $b$  o que $b$  es mayor que $a$  (respecto de $\leq$ )
 * 3) Denotaremos con $\prec$  a la relacion binaria $$\{(a,b)\in A^{2}:a<b\text{ y no existe }z\text{ tal que }a<z<b\}$$ Cuando se de $a\prec b$  diremos que $a$  es cubierto por $b$  o que $b$  cubre a $a$  (respecto de $\leq$ )

Algunos ejemplos:

 * 1) Si $A=\mathbf{R}$  y $\mathrm{\leq}=\{(r,t)\in\mathbf{R}^{2}:r=t\}$, entonces $\mathrm{<}=\emptyset$
 * 2) Si $A=\{1,2,3,4\}$  y $\mathrm{\leq}=\{(1,2),(2,3),(1,3),(1,1),(2,2),(3,3),(4,4)\}$, entonces $\mathrm{<}=\{(1,2),(2,3),(1,3)\}$  y $\mathrm{\prec}=\{(1,2),(2,3)\}$ . En particular tenemos que $1\prec2$ , $1<3$  pero no se da que $1\prec3$.
 * 3) Si $A=\mathcal{P}(\omega)$  y $\mathrm{\leq}=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subseteq T\}$, entonces $\mathrm{<}=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subsetneq T\}$  y $S\prec T$  sii hay un $n\in T-S$  tal que $T=S\cup\{n\}$

Ordenes totales sobre un conjunto
Sea $A$ un conjunto cualquiera. Por un orden total sobre $A$ entenderemos un orden parcial $\leq$  sobre $A$  el cual cumpla:

 * 1) $a\leq b$  o $b\leq a$, cualesquiera sean $a,b\in A$

Supongamos $A$ es finito no vacio y $\leq$  es un orden total sobre $A$. La propiedad (C) nos permite probar que para cada conjunto no vacio $S\subseteq A$, hay un elemento $s\in S$ el cual cumple $s\leq s^{\prime}$  para cada $s^{\prime}\in S$. Por supuesto, $s$ es unico (por que?) y habitualmente es llamado el menor elemento de $S$, ya que es menor que todo otro elemento de $S$.

Si $A$ es finito no vacio y $\leq$  es un orden total sobre $A$, podemos definir recursivamente una funcion $f:\{1,...,\left\vert A\right\vert \}\rightarrow A$  de la siguiente manera:

 * 1) $f(1)=$  menor elemento de $A$
 * 2) Si $i\in\{1,...,\left\vert A\right\vert -1\}$, entonces
 * 3) $f(i+1)=$  menor elemento de $A-\{f(1),...,f(i)\}$

Como es habitual, $f(i)$ es llamado el $i$ -esimo elemento de $A$.

Muchas veces para dar un orden total sobre un conjunto finito $A$, daremos simplemente sus elementos en forma creciente ya que esto determina el orden por completo. Por ejemplo si $A=\{1,2,3\}$, el orden total dado por $2<1<3$ es la relacion $\mathrm{\leq}=\{(2,1),(1,3),(2,3),(1,1),(2,2),(3,3)\}$.

Un concepto importante relativo a los ordenes totales es el de sucesor. Si $\leq$ es un orden total sobre $A$  y $a,b\in A$, diremos que $b$  es el sucesor de $a$  cuando se de que $a<b$  y $b\leq c$ , para cada $c\in A$  tal que $a<c$ , i.e., $b$  es el menor elemento del conjunto $\{c\in A:$  tal que $a<c\}$. No siempre existe el sucesor de un elemento. Por ejemplo si $\leq$ es el orden usual de $\mathbf{R}$, entonces ningun elemento tiene sucesor (justifique).

Diagramas de Hasse
Dado un orden parcial $\leq$ sobre un conjunto finito $A$  podemos realizar un diagrama de $\leq$, llamado diagrama de Hasse, siguiendo las siguientes instrucciones:

 * 1) Asociar en forma inyectiva, a cada $a\in$  $A$  un punto $p_{a}$  del plano
 * 2) Trazar un segmento de recta uniendo los puntos $p_{a}$  y $p_{b}$, cada vez que $a\prec b$
 * 3) Realizar lo indicado en los puntos (1) y (2) en tal forma que
 * 4) Si $a\prec b$, entonces $p_{a}$  esta por debajo de $p_{b}$
 * 5) Si un punto $p_{a}$  ocurre en un segmento del diagrama entonces lo hace en alguno de sus extremos.

La relacion de orden $\leq$ puede ser facilmente obtenida de su diagrama, a saber, $a\leq b$  sucedera si y solo si $p_{a}=p_{b}$  o hay una sucesion de segmentos ascendentes desde $p_{a}$  hasta $p_{b}$.

Ejemplos:

Relaciones de equivalencia
Sea $A$ un conjunto cualquiera. Por una relacion de equivalencia sobre $A$ entenderemos una relacion binaria sobre $A$  la cual es reflexiva, transitiva y simetrica, con respecto a $A$, es decir, la cual cumple:

 * 1) $xRx$, cualesquiera sea $x\in A$
 * 2) $xRy$  y $yRz$  implica $xRz$, cualesquiera sean $x,y,z\in A$
 * 3) $xRy$  implica $yRx$, cualesquiera sean $x,y\in A$

Algunos ejemplos:

 * 1) Sea $R=\{(r,t)\in\mathbf{R}^{2}:r=t\}$ . Entonces $R$  es una relacion de equivalencia sobre $\mathbf{R}$
 * 2) Dada una funcion $f:A\rightarrow B$, el nucleo de $f$ , i.e. $\ker(f)=\{(a,b)\in A^{2}:f(a)=f(b)\}$  es una relacion de equivalencia sobre $A$.
 * 3) Sea $R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$ . Entonces $R$  es una relacion de equivalencia sobre $\{1,2,3\}$
 * 4) Sea $R=\{(x,y)\in\omega^{2}:x=y\}$ . Entonces $R$  es una relacion de equivalencia sobre $\omega$
 * 5) Sea $R=\{(S,T)\in\mathcal{P}(\omega)^{2}:(S-T)\cup(T-S)$  es finito$\}$ . Entonces $R$  es una relacion de equivalencia sobre $\mathcal{P}(\omega)$
 * 6) Sea $R=\{(1,1)\}$ . Entonces $R$  es una relacion de equivalencia sobre $\{1\}$.
 * 7) Sea $R=\{(x,y)\in\mathbf{Z}^{2}:x-y$  es multiplo de $2\}$ . Entonces $R$  es una relacion de equivalencia sobre $\mathbf{Z}$.

Dada una relacion de equivalencia $R$ sobre $A$  y $a\in A$, definimos: $$a/R=\{b\in A:aRb\}$$ El conjunto $a/R$  sera llamado la clase de equivalencia de $a$ , con respecto a $R$. Ejemplos:

 * 1) Si $R=\{(r,t)\in\mathbf{R}^{2}:r=t\}$, entonces $r/R=\{r\}$ , cualesquier sea $r\in\mathbf{R}$
 * 2) Si $R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$, entonces $1/R=2/R=\{1,2\}$  y $3/R=\{3\}$
 * 3) Si $R=\{(x,y)\in\mathbf{Z}^{2}:x-y$  es multiplo de $2\}$, entonces $0/R=\{t\in\mathbf{Z}:t$  es par$\}$ , $1/R=\{t\in\mathbf{Z}:t$  es impar$\}$  y en general notese que $n/R=\{t\in\mathbf{Z}:t$  es par$\}$  si $n$  es par y $n/R=\{t\in\mathbf{Z}:t$  es impar$\}$  si $n$  es impar. Es decir que hay solo dos clases de equivalencia con respecto a $R$

Algunas propiedades basicas son:

 Lemma 3. Sea $R$ una relacion de equivalencia sobre $A$. Sean $a,b\in A$ .

 * 1) '$a\in a/R$ '
 * 2) '$aRb$  si y solo si $a/R=b/R$ . Es decir que $b\in a/R$  implica $b/R=a/R$ '
 * 3) '$a/R\cap b/R=\emptyset$  o $a/R=b/R$ '

Proof. (1) es muy facil.

(2). Supongamos $aRb$. Veremos que $a/R\subseteq b/R$. Supongamos $c\in a/R$. Entonces $aRc$. Como $aRb$, tenemos que $bRa$ , por lo cual hemos probado que $bRa$ y $aRc$ , lo cual implica que $bRc$. O sea que $cRb$, lo cual nos dice que $c\in b/R$. Esto prueba que $a/R\subseteq b/R$. Similarmente se prueba que $b/R\subseteq a/R$, con lo cual se tiene que $a/R=b/R$.

Reciprocamente, si $a/R=b/R$, entonces $b\in a/R$ ya que $b\in b/R$. Pero esto nos dice que $aRb$.

o=(3). Supongamos que $a/R\cap b/R$ no es vacio, es decir hay un $c\in a/R\cap b/R$. Entonces es facil ver que $aRb$. Pero entonces por (2) tenemos que $a/R=b/R$.

-

Denotaremos con $A/R$ al conjunto $\{a/R:a\in A\}$. Llamaremos a $A/R$ el cociente de $A$  por $R$. Ejemplos:

 * 1) Si $R=\{(r,t)\in\mathbf{R}^{2}:r=t\}$, entonces $\mathbf{R}/R=\{\{r\}:r\in\mathbf{R}\}$
 * 2) Si $R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$, entonces $\{1,2,3\}/R=\{\{1,2\},\{3\}\}$
 * 3) Si $R=\{(x,y)\in\mathbf{Z}^{2}:x-y$  es multiplo de $2\}$, ya vimos que $\mathbf{Z}/R=\{\{t\in\mathbf{Z}:t$  es par$\},\{t\in\mathbf{Z}:t$  es impar$\}\}$

Si $R$ es una relacion de equivalencia sobre $A$, definamos la funcion $\pi_{R}:A\rightarrow A/R$  por $\pi_{R}(a)=a/R$ , para cada $a\in A$. La funcion $\pi_{R}$ es llamada la proyeccion canonica (respecto de $R$ ).

Lemma 4. Sea $R$ una relacion de equivalencia sobre $A$. Entonces $\ker\pi_{R}=R$. Es decir que $\pi_{R}$ es inyectiva sii $R=\{(x,y)\in A^{2}:x=y\}$

Definicion de funciones con dominio $A/R$
Supongamos $R$ es una relacion de equivalencia sobre $\mathbf{R}$  y supongamos definimos una funcion $f:\mathbf{R}/R\rightarrow\mathbf{R}$  de la siguiente manera: $$f(r/R)=r^{2}$$ A priori puede pareser que esta definicion es natural y que no esconde ninguna posible complicacion. Pero supongamos que $R$ es tal que $2R6$. Entonces tendriamos que $2/R=6/R$ lo cual produciria la siguiente contradiccion: $$\begin{aligned} 4 & =2^{2}\\ & =f(2/R)\\ & =f(6/R)\\ & =6^{2}\\ & =36 \end{aligned}$$ El problema aqui es que la ecuacion $f(r/R)=r^{2}$ no esta definiendo en forma correcta o inhambigua una funcion ya que el supuesto valor de la funcion en una clase de equivalencia dada depende de que representante de la clase usamos para denotarla. Si usamos el 2 la ecuacion nos dice que entonces $f$ debe valer 4 y si usamos el 6 la ecuacion nos dice que $f$  debe valer 36. Claramente no estamos definiendo una funcion.

Para dar un ejemplo mas concreto de este fenomeno de ambiguedad, supongamos $$R=\{(x,y)\in\mathbf{Z}^{2}:x-y\text{ es multiplo de }2\}$$ y definimos una funcion $f:\mathbf{Z}/R\rightarrow\mathbf{R}$ de la siguiente manera: $$f(n/R)=1/(n^{2}+1)$$ Como ya vimos $\mathbf{Z}/R=\{\{t\in\mathbf{Z}:t$  es par$\},\{t\in\mathbf{Z}:t$  es impar$\}\}$, por lo cual facilmente se puede llegar a que la ecuacion $f(n/R)=1/(n^{2}+1)$  no define correctamente una funcion. Dejamos al lector explicar esto mas detalladamente.

Sin envargo hay muchos casos en los cuales este tipo de definiciones son inhambiguas y desde luego muy importantes en el algebra moderna. Como un primer ejemplo tenemos el siguiente lema el cual es una de las ideas fundamentales del algebra moderna.

Lemma 5. 'Si $f:A\rightarrow B$ es sobre, entonces la ecuacion $\bar{f}(a/\ker f)=f(a)$  define en forma inhambigua una funcion $\bar{f}:A/\ker f\rightarrow B$  la cual es biyectiva.'

Proof. Que la ecuacion $\bar{f}(a/\ker f)=f(a)$ define sin ambiguedad una funcion $\bar{f}:A/\ker f\rightarrow B$  es obvio ya que si $a/\ker f=b/\ker f$, entonces por definicion de $\ker f$  debera suceder que $a=b$. Dejamos al lector la prueba de que $\bar{f}$ es biyectiva

-

Correspondencia entre relaciones de equivalencia y particiones
Dado un conjunto $A$ por una particion de $A$  entenderemos un conjunto $\mathcal{P}$  tal que:

 * 1) Cada elemento de $\mathcal{P}$  es un subconjunto no vacio de $A$
 * 2) Si $S_{1},S_{2}\in\mathcal{P}$  y $S_{1}\neq S_{2}$, entonces $S_{1}\cap S_{2}=\emptyset$
 * 3) $A=\{a:a\in S$, para algun $S\in\mathcal{P}\}$

La ultima condicion dice simplemente que la union de todos los elementos de $\mathcal{P}$ debe ser $A$. Ejemplos:

  Si $A=\{1,2,3,4,5\}$, entonces $$\mathcal{P}=\{\{1,5\},\{2,3\},\{4\}\}$$ es una particion de $A$   $\mathcal{P}=\{\mathbf{N},\mathbf{R}-\mathbf{N}\}$ es una particion de $\mathbf{R}$   $\mathcal{P}=\{\{0\},\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{9,10\},...\}$ es una particion de $\omega$

Una observacion importante es que si $\mathcal{P}$ es una particion de $A$, entonces para cada $a\in A$  hay un unico $S\in\mathcal{P}$  tal que $a\in S$  (por que?). O sea que podemos hablar de EL elemento de $\mathcal{P}$ que contiene a $a$.

Dada una particion $\mathcal{P}$ de un conjunto $A$  podemos definir una relacion binaria asociada a $\mathcal{P}$  de la siguiente manera: $$R_{\mathcal{P}}=\{(a,b)\in A^{2}:a,b\in S\text{, para algun }S\in\mathcal{P}\}$$

Lemma 6. Sea $A$ un conjunto cualquiera. Entonces:

 * 1) 'Sea $\mathcal{P}$  una particion de $A$ . Entonces $R_{\mathcal{P}}$  es una relacion de equivalencia sobre $A$ .'
 * 2) 'Sea $R$  una relacion de equivalencia sobre $A$ . Entonces $A/R$  es una particion de $A$ .'

Proof. (1). Es facil ver que $R_{\mathcal{P}}$ es reflexiva y simetrica. Veamos que es transitiva. Supongamos que $aR_{\mathcal{P}}b$ y $bR_{\mathcal{P}}c$. O sea que hay $S_{1},S_{2}\in\mathcal{P}$ tales que $a,b\in S_{1}$  y $b,c\in S_{2}$. Ya que $S_{1}$ y $S_{2}$  tienen un elemento en comun, debera suceder que $S_{1}=S_{2}$. Pero entonces tenemos que $a,c\in S_{1}$, lo cual nos dice que $aR_{\mathcal{P}}c$.

(2). Sigue facilmente del Lema 3.

-

El siguiente teorema da una correspondencia natural entre relaciones de equivalencia sobre $A$ y particiones de $A$.

Theorem 7. Sea $A$ un conjunto cualquiera. Sean $$\begin{aligned} Part & =\{\text{particiones de }A\}\\ ReEq & =\{\text{relaciones de equivalencia sobre }A\} \end{aligned}$$ Entonces las funciones: $$\begin{array}{rll} Part & \rightarrow & ReEq\\ \mathcal{P} & \rightarrow & R_{\mathcal{P}} \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} ReEq & \rightarrow & Part\\ R & \rightarrow & A/R \end{array}$$ son biyecciones una inversa de la otra.

Proof. Notese que por el Lema 2 basta con probar:

 * 1) $A/R_{\mathcal{P}}=\mathcal{P}$, cualesquiera sea la particion $\mathcal{P}$  de $A$
 * 2) $R_{A/R}=R$, cualesquiera sea la relacion de equivalencia $R$  sobre $A$

Prueba de (1). Primero veamos que $A/R_{\mathcal{P}}\subseteq\mathcal{P}$. Sea $a\in A$, veremos que $a/R_{\mathcal{P}}=\{b:aR_{\mathcal{P}}b\}\in\mathcal{P}$. Sea $S$ el unico elemento de $\mathcal{P}$  que contiene a $a$. Es facil ver de la definicion de $R_{\mathcal{P}}$ que $a/R_{\mathcal{P}}=S$  por lo cual $a/R_{\mathcal{P}}\in\mathcal{P}$. Veamos ahora que $\mathcal{P}\subseteq A/R_{\mathcal{P}}$. Sea $S\in\mathcal{P}$. Sea $a\in S$. Es facil ver de la definicion de $R_{\mathcal{P}}$ que $a/R_{\mathcal{P}}=S$  por lo cual $S\in A/R_{\mathcal{P}}$.

Prueba de (2). Primero veamos que $R_{A/R}\subseteq R$. Supongamos $aR_{A/R}b$. Entonces $a,b\in c/R$, para algun $c\in A$. Es claro que entonces $aRb$. Veamos ahora que $R\subseteq R_{A/R}$. Supongamos que $aRb$. Entonces $a,b\in a/R$, lo cual nos dice que $aR_{A/R}b$.

-

El teorema anterior muestra que a nivel de informacion es lo mismo tener una relacion de equivalencia sobre $A$ que tener una particion de $A$. Esto es muy util ya que muchas veces es mas facil especificar una relacion de equivalencia via su particion asociada. Por ejemplo si hablamos de la relacion de equivalencia sobre $\{1,2,3,4,5\}$ dada por la particion $$\mathcal{P}=\{\{1,5\},\{4\},\{2,3\}\}$$ nos estaremos refiriendo a $R_{\mathcal{P}}$, es decir a la relacion: $$\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,5),(5,1),(2,3),(3,2)\}$$

Operaciones $n$ -arias sobre un conjunto
Sea $A$ un conjunto. Dado $n\in\omega$, por una operacion $n$ -aria sobre $A$ entenderemos una funcion cuyo dominio es $A^{n}$  y cuya imagen esta contenida en $A$. A las operaciones $2$ -arias (resp. $3$ -arias, $4$ -arias) tambien las llamaremos operacion binarias (resp. ternarias, cuaternarias). Algunos ejemplos:

 * 1) Sea $f:\mathbf{R\times R}\rightarrow\mathbf{R}$  dada por $f(x,y)=x+y$ . Entonces $f$  es una operacion $2$ -aria sobre $\mathbf{R}$
 * 2) Sea $f:\{\Diamond\}\rightarrow\omega$, dada por $f(\Diamond)=5$ . Entonces $f$  es una operacion $0$ -aria sobre $\omega$.
 * 3) Sea $f:\mathbf{N\times N\times N\times N\times N}\rightarrow\mathbf{N}$, dada por $f(x_{1},x_{2},x_{3},x_{4},x_{5})=(x_{1}.x_{2})+x_{3}$ . Entonces $f$  es una operacion $5$ -aria sobre $\mathbf{N}$.

Si $f$ es una operacion $n$ -aria sobre $A$  y $S\subseteq A$, entonces diremos que $S$  es cerrado bajo $f$   cuando se de que $f(a_{1},...,a_{n})\in S$ , cada ves que $a_{1},...,a_{n}\in S$. Notese que si $n=0$, entonces $S$ es cerrado bajo $f$  si y solo si $f(\Diamond)\in S$.

Relaciones $n$ -arias sobre un conjunto
Sea $A$ un conjunto. Dado $n\in\omega$, por una relacion $n$ -aria sobre $A$ entenderemos un subconjunto de $A^{n}$. A las relaciones $2$ -arias (resp. $3$ -arias, $4$ -arias) tambien las llamaremos relaciones binarias (resp. ternarias, cuaternarias). Algunos ejemplos:

 * 1) Sea $R=\{(r,t)\in\mathbf{R\times R}:r\leq t\}$ . Entonces $R$  es una relacion $2$ -aria sobre $\mathbf{R}$
 * 2) Hay exactamente dos relaciones $0$ -arias sobre $A$, a saber: $\emptyset$  y $\{\Diamond\}$.
 * 3) Sea $R=\{(x_{1},x_{2},x_{3},x_{4},x_{5})\in\mathbf{N}^{5}:x_{5}=x_{4}\}$ . Entonces $R$  es una relacion $5$ -aria sobre $\mathbf{N}$ . Notese que tambien $R$  es una relacion $5$ -aria sobre $\mathbf{R}$
 * 4) $\emptyset$  es una relacion $n$ -aria sobre $A$, cualesquiera sea $n\in\omega$  y $A$.

Funciones $\Sigma$ -mixtas
Sea $\Sigma$ un alfabeto finito. Dados $n,m\in\omega$, usaremos $\omega^{n}\times\Sigma^{\ast m}$ para abreviar la expresion $$\overset{n\text{ veces}}{\overbrace{\omega\times...\times\omega}}\times\overset{m\text{ veces}}{\overbrace{\Sigma^{\ast}\times...\times\Sigma^{\ast}}}$$ Por ejemplo, $\omega^{3}\times\Sigma^{\ast4}$  sera una forma abreviada de escribir $\omega\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}$. Debe quedar claro que estamos haciendo cierto abuso notacional ya que en principio si no hacemos esta convencion notacional, $\omega^{3}\times\Sigma^{\ast4}$ denota un conjunto de pares y $\omega\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}$  es un conjunto de $7$ -uplas.

Notese que cuando $n=m=0$, tenemos que $\omega^{n}\times\Sigma^{\ast m}$ denota el conjunto $\{\Diamond\}$  y si $m=0$ , entonces $\omega^{n}\times\Sigma^{\ast m}$  denota el conjunto $\omega^{n}$.

Con esta convencion notacional, un elemento generico de $\omega^{n}\times\Sigma^{\ast m}$ es una $(n+m)$ -upla de la forma $(x_{1},...,x_{n},\alpha_{1},...,\alpha_{m})$. Para abreviar, escribiremos $(\vec{x},\vec{\alpha})$ en lugar de $(x_{1},...,x_{n},\alpha_{1},...,\alpha_{m})$.

Definicion de funcion $\Sigma$ -mixta
Sea $\Sigma$ un alfabeto finito. Dada una funcion $f$, diremos que $f$ es $\Sigma$ -mixta si cumple las siguientes propiedades

 * 1) Existen $n,m\geq0$, tales que $D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}$
 * 2) Ya sea $I_{f}\subseteq\omega$  o $I_{f}\subseteq\Sigma^{\ast}$

Algunos ejemplos:

  Sea $\Sigma=\{\square,\%,\blacktriangle\}$. La funcion $$\begin{array}{rll} f:\omega\times\{\square,\%,\blacktriangle\}^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & x+\left\vert \alpha\right\vert \end{array}$$ es $\Sigma$ -mixta ya que se cumple (M1) con $n=m=1$ y (M2). Notese que $f$ no es $\{\square,\%\}$ -mixta ya que no cumple (M1) respecto del alfabeto $\{\square,\%\}$. Sin envargo note que $f$ es $\{\square,\%,\blacktriangle,@\}$ -mixta   La funcion $$\begin{array}{rll} \omega^{4} & \rightarrow & \omega\\ (x,y,z,w) & \rightarrow & x+y \end{array}$$ es $\Sigma$ -mixta cualesquiera sea el alfabeto $\Sigma$   Sea $\Sigma=\{\square,@\}$. La funcion $$\begin{array}{rll} \{\square\square\square,@@\} & \rightarrow & \omega\\ \alpha & \rightarrow & \left\vert \alpha\right\vert \end{array}$$ es $\Sigma$ -mixta ya que se cumple (M1) (con $n=0$ y $m=1$ ) y (M2) </li> <li> Supongamos $\Sigma=\emptyset$. Tenemos entonces que $\Sigma^{\ast}=\{\varepsilon\}$. Por ejemplo $$\begin{array}{rll} D & \rightarrow & \omega\\ (x,\varepsilon,\varepsilon,\varepsilon) & \rightarrow & x^{2} \end{array}$$ donde $D=\{(x,\varepsilon,\varepsilon,\varepsilon):x$ es impar$\}$, es $\Sigma$ -mixta (con $n=1$  y $m=3$  en (M1)). Tambien notese que $$\begin{array}{rll} \{(\varepsilon,\varepsilon)\} & \rightarrow & \{\varepsilon\}\\ (\varepsilon,\varepsilon) & \rightarrow & \varepsilon \end{array}$$ es $\Sigma$ -mixta. </li></ol>

Dejamos al lector la facil prueba del siguiente resultado basico.

Lemma 8. Supongamos $\Sigma\subseteq\Gamma$ son alfabetos finitos. Entonces si $f$ es una funcion $\Sigma$ -mixta, $f$  es $\Gamma$ -mixta

Una funcion $\Sigma$ -mixta $f$ es $\Sigma$ -total cuando haya $n,m\in\omega$  tales que $D_{f}=\omega^{n}\times\Sigma^{\ast m}$. El lema anterior nos dice que si $\Sigma\subseteq\Gamma$, entonces toda funcion $\Sigma$ -mixta es $\Gamma$ -mixta. Sin envargo una funcion puede ser $\Sigma$ -total y no ser $\Gamma$ -total, cuando $\Sigma\subseteq\Gamma$. Por ejemplo tomemos $\Sigma=\{\square,\%,\blacktriangle\}$ y $\Gamma=\{\square,\%,\blacktriangle,!\}$, y consideremos la funcion $$\begin{array}{rll} f:\omega\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & x+\left\vert \alpha\right\vert \end{array}$$ Es claro que $f$ es $\Sigma$ -mixta y $\Sigma$ -total. Tambien es $\Gamma$ -mixta ya que $D_{f}\subseteq\omega\times\Gamma^{\ast}$ y $I_{f}\subseteq\omega$, por lo cual cumple (M1) y (M2). Sin envargo $f$ no es $\Gamma$ -total ya que $D_{f}$  no es igual a $\omega^{n}\times\Gamma^{\ast m}$, cualesquiera sean $n$  y $m$.

Como hemos visto recien, una funcion $f$ puede ser $\Sigma$ -mixta y $\Gamma$ -mixta para dos alfabetos distintos $\Sigma$  y $\Gamma$  e incluso es facil construir un ejemplo en el cual $\Sigma$  y $\Gamma$  sean incomparables como conjuntos, es decir que ninguno incluya al otro. Dejamos al lector convencerse de que si $f$ es una funcion que es $\Sigma$ -mixta para algun alfabeto $\Sigma$, entonces hay un alfabeto $\Sigma_{0}$  el cual es el menor de todos los alfabetos respecto de los cuales $f$  es mixta, es decir $\Sigma_{0}$  cumple que $f$  es $\Sigma_{0}$ -mixta y si $\Gamma$  es tal que $f$  es $\Gamma$ -mixta, entonces $\Sigma_{0}\subseteq\Gamma$.

A continuacion daremos algunas funciones $\Sigma$ -mixtas basicas las cuales seran frecuentemente usadas.

Funciones $Suc$ y $Pred$
La funcion sucesor es definida por $$\begin{array}{rll} Suc:\omega & \rightarrow & \omega\\ n & \rightarrow & n+1 \end{array}$$ La funcion predecesor es definida por $$\begin{array}{rll} Pred:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n-1 \end{array}$$

<span id="las-funciones-d_a">

Las funciones $d_{a}$
Sea $\Sigma$ un alfabeto no vacio. Para cada $a\in\Sigma$, definamos $$\begin{array}{rll} d_{a}:\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ \alpha & \rightarrow & \alpha a \end{array}$$ La funcion $d_{a}$ es llamada la funcion derecha sub $a$, respecto del alfabeto $\Sigma$.

<span id="las-funciones-p_inm">

Las funciones $p_{i}^{n,m}$
Sea $\Sigma$ un alfabeto. Para $n,m,i\in\omega$ tales que $1\leq i\leq n$, definamos $$\begin{array}{rll} p_{i}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & x_{i} \end{array}$$ Para $n,m,i\in\omega$ tales que $n+1\leq i\leq n+m$, definamos $$\begin{array}{rll} p_{i}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \Sigma^{\ast}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \alpha_{i-n} \end{array}$$ Las funciones $p_{i}^{n,m}$ son llamadas proyecciones. La funcion $p_{i}^{n,m}$ es llamada la proyeccion $n,m,i$, respecto del alfabeto $\Sigma$. Notese que esta definicion requiere que $n+m\geq1$ ya que $i$  debe cumplir $1\leq i\leq n+m$.

<span id="las-funciones-c_knm-y-c_alphanm">

Las funciones $C_{k}^{n,m}$ y $C_{\alpha}^{n,m}$
Sea $\Sigma$ un alfabeto. Para $n,m,k\in\omega$, y $\alpha\in\Sigma^{\ast}$ , definamos $$\begin{array}{rll} C_{k}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & k \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} C_{\alpha}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \Sigma^{\ast}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \alpha \end{array}$$ Notese que $C_{k}^{0,0}:\{\Diamond\}\rightarrow\{k\}$ y que $C_{\alpha}^{0,0}:\{\Diamond\}\rightarrow\{\alpha\}$.

La funcion $pr$
Definamos $$\begin{array}{rll} pr:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n\text{-esimo numero primo} \end{array}$$ Notese que $pr(1)=2$, $pr(2)=3$ , $pr(3)=5$ , etc.

El tipo de una funcion mixta
Dada una funcion $\Sigma$ -mixta $f$, si $n,m\in\omega$ son tales que $D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}$  y ademas $I_{f}\subseteq\omega$ , entonces diremos que $f$  es una funcion de tipo $(n,m,\#)$. Similarmente si $n,m\in\omega$ son tales que $D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}$  y ademas $I_{f}\subseteq\Sigma^{\ast}$, entonces diremos que $f$  es una funcion de tipo $(n,m,\ast)$. Notese que si $f\neq\emptyset$, entonces hay unicos $n,m\in\omega$ y $s\in\{\#,\ast\}$  tales que $f$  es una funcion de tipo $(n,m,s)$. Sin envargo $\emptyset$ es una funcion de tipo $(n,m,s)$  cualesquiera sean $n,m\in\omega$  y $s\in\{\#,\ast\}$. De esta forma, cuando $f\neq\emptyset$ hablaremos de "el tipo de $f$ " para refererirnos a esta unica terna $(n,m,s)$. Notese que $Suc$ es de tipo $(1,0,\#)$  y $d_{a}$  es de tipo $(0,1,\ast)$.

Tambien notese que la relacion "$f$ es una funcion de tipo $(n,m,s)$ " no depende del alfabeto $\Sigma$  (que significa esto?).

Funciones con imagen contenida en $\omega^{n}\times\Sigma^{\ast m}$
Supongamos que $k,l,n,m\in\omega$ y que $F:D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega^{n}\times\Sigma^{\ast m}$. Supongamos ademas que $n+m\geq1$. Entonces denotaremos con $F_{(i)}$ a la funcion $p_{i}^{n,m}\circ F$. Notar que $$\begin{aligned} F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega\text{, para cada }i=1,...,n\\ F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\Sigma^{\ast}\text{, para cada }i=n+1,...,n+m \end{aligned}$$ Por lo cual cada una de las funciones $F_{(i)}$ son $\Sigma$ -mixtas. Ademas notese que $$F=[F_{(1)},...,F_{(n+m)}]$$

<span id="wiki-predicado._sigma._-mixto" label="wiki-predicado._sigma._-mixto">

<span id="wiki-predicados._sigma._-mixtos" label="wiki-predicados._sigma._-mixtos">

Predicados $\Sigma$ -mixtos
Un predicado $\Sigma$ -mixto es una funcion $f$ la cual es $\Sigma$ -mixta y ademas cumple que $I_{f}\subseteq\{0,1\}$. Por ejemplo $$\begin{array}{rll} \omega\times\omega & \rightarrow & \omega\\ (x,y) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=y\\ 0\text{ si }x\neq y \end{array}\right. \end{array}\ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} \{1,2,3,4,5\}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=\left\vert \alpha\right\vert \\ 0\text{ si }x\neq\left\vert \alpha\right\vert \end{array}\right. \end{array}$$

Operaciones logicas entre predicados
Dados predicados $P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}$ y $Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}$, con el mismo dominio, definamos nuevos predicados $(P\vee Q)$ , $(P\wedge Q)$  y $\lnot P$  de la siguiente manera $$\begin{array}{rll} (P\vee Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ o }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}$$ $$\begin{array}{rll} (P\wedge Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ y }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}$$ $$\begin{array}{rll} \lnot P:S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=0\\ 0 & & \text{si }P(\vec{x},\vec{\alpha})=1 \end{array}\right. \end{array}$$

Familias $\Sigma$ -indexadas de funciones
Dado un alfabeto $\Sigma$, una familia $\Sigma$ -indexada de funciones sera una funcion $\mathcal{G}$ tal que $D_{\mathcal{G}}=\Sigma$  y para cada $a\in D_{\mathcal{G}}$  se tiene que $\mathcal{G}(a)$  es una funcion. Algunos ejemplos:

\mathcal{G}:\{\square,\%,\blacktriangle\} & \rightarrow & \{Suc,Pred\}\\ \square & \rightarrow & Suc\\ \% & \rightarrow & Suc\\ \blacktriangle & \rightarrow & Pred \end{array}$$ Claramente $\mathcal{G}$ es una familia $\{\square,\%,\blacktriangle\}$ -indexada de funciones. Notar que $$\mathcal{G}=\{(\square,Suc),(\%,Suc),(\blacktriangle,Pred)\}$$ Se tiene tambien por ejemplo que $\mathcal{G}(\%)=Suc$ por lo cual tambien es cierto que $\mathcal{G}(\%)(22)=23$, etc. \mathcal{G}:\Sigma & \rightarrow & \{f:f\text{ es una funcion de }\Sigma^{\ast}\text{ en }\Sigma^{\ast}\}\\ a & \rightarrow & d_{a} \end{array}$$ es una familia $\Sigma$ -indexada de funciones. Notar que $$\mathcal{G}=\{(a,d_{a}):a\in\Sigma\}$$
 * 1) Sea $\mathcal{G}$  dada por $$\begin{array}{rcl}
 * 1) Si $\Sigma$  es un alfabeto no vacio, la funcion $$\begin{array}{rcl}
 * 1) $\emptyset$  es una flia $\emptyset$ -indexada de funciones

Si $\mathcal{G}$ es una familia $\Sigma$ -indexada de funciones, entonces para $a\in\Sigma$, escribiremos $\mathcal{G}_{a}$  en lugar de $\mathcal{G}(a)$.

<span id="wiki-conjunto._:sigma._-mixto" label="wiki-conjunto._:sigma._-mixto">

<span id="wiki-conjuntos._:sigma._-mixtos" label="wiki-conjuntos._:sigma._-mixtos">

Conjuntos $\Sigma$ -mixtos
Un conjunto $S$ es llamado $\Sigma$ -mixto si hay $n,m\in\omega$  tales que $S\subseteq\omega^{n}\times\Sigma^{\ast m}$. Por ejemplo, $$\{(x,\alpha)\in\omega\times\{\blacktriangle,!\}^{\ast}:\left\vert \alpha\right\vert =x\}$$ $$\{(0,\blacktriangle\blacktriangle\blacktriangle,\varepsilon),(1,\%\blacktriangle\%,\blacktriangle\blacktriangle)\}$$ son conjuntos $\{\blacktriangle,\%,!\}$ -mixtos. Tambien notese que $\emptyset$ y $\{\Diamond\}$  son conjuntos $\Sigma$ -mixtos, cualesquiera sea el alfabeto $\Sigma$. Por ultimo el conjunto $$\{(x,\varepsilon,\varepsilon,\varepsilon):x\in\omega\text{ y }x\text{ es impar}\}$$ es $\emptyset$ -mixto (con $n=1$ y $m=3$ ).

El tipo de un conjunto mixto
Dado un conjunto $\Sigma$ -mixto $S$, si $n,m\in\omega$ son tales que $S\subseteq\omega^{n}\times\Sigma^{\ast m}$ , entonces diremos que $S$  es un conjunto de tipo $(n,m)$. Notese que si $S\neq\emptyset$, entonces hay unicos $n,m\in\omega$ tales que $S$  es un conjunto de tipo $(n,m)$. De esta forma, cuando $S\neq\emptyset$ hablaremos de "el tipo de $S$ " para refererirnos a este unico par $(n,m)$. Tambien es importante notar que de la definicion anterior sale inmediatemante que $\emptyset$ es un conjunto de tipo $(n,m)$  cualesquiera sean $n,m\in\omega$, por lo cual cuando hablemos de EL tipo de un comjunto deberemos estar seguros de que dicho conjunto es no vacio.

Notese que $\omega$ es de tipo $(1,0)$  y $\Sigma^{\ast}$  es de tipo $(0,1)$.

Conjuntos rectangulares
Un conjunto $\Sigma$ -mixto $S$ es llamado rectangular si es de la forma $$S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m},$$ con cada $S_{i}\subseteq\omega$  y cada $L_{i}\subseteq\Sigma^{\ast}$. Notar que todo subconjunto de $\omega$ es rectangular (es el caso $n=1$  y $m=0$ ). Tambien $\{\Diamond\}$ es rectangular (es el caso $n=m=0$ ). Otros ejemplos:

 * 1) $\mathbf{N}\times\{1,2\}\times\{@@,\varepsilon\}$  es rectangular (aqui $n=2$  y $m=1$ )
 * 2) $\{!!!,!!\}\times\{@@,\varepsilon\}$  es rectangular (aqui $n=0$  y $m=2$ )

Tambien notese que $\emptyset=\emptyset\times\emptyset$ por lo cual $\emptyset$  es un conjunto rectangular.

El concepto de conjunto rectangular es muy importante en nuestro enfoque. Aunque en general no habra restricciones acerca del dominio de las funciones y predicados, nuestra filosofia sera tratar en lo posible que los dominios de las funciones que utilicemos para hacer nuestro analisis de recursividad de los distintos paradigmas, sean rectangulares. Aunque en principio puede pareser que todos los conjuntos son rectangulares, el siguiente lema mostrara cuan ingenua es esta vision.

Lemma 9. Sea $S\subseteq\omega\times\Sigma^{\ast}$. Entonces $S$ es rectangular si y solo si se cumple la siguiente propiedad:

 * 1) 'Si $(x,\alpha),(y,\beta)\in S$, entonces $(x,\beta)\in S$ '

Proof. Ejercicio.

-

Supongamos $\Sigma=\{\#,\blacktriangle,\%\}$. Notese que podemos usar el lema anterior para probar por ejemplo que los siguientes conjuntos no son rectangulares

 * 1) $\{(0,\#\#),(1,\%\%\%)\}$
 * 2) $\{(x,\alpha):\left\vert \alpha\right\vert =x\}$

Dejamos como ejercicio para el lector enunciar un lema analogo al anterior pero que caracterice cuando $S\subseteq\omega^{2}\times\Sigma^{\ast3}$ es rectangular.

Notacion lambda
Usaremos la notacion lambda de Church en la forma que se explica a continuacion. Esta notacion siempre depende de un alfabeto finito previamente fijado. En general en nuestro lenguaje matematico utilizamos diversas expresiones las cuales involucran variables que una vez fijadas en sus valores hacen que la expresion tambien represente un determinado valor

En el contexto de la notacion lambda solo se podran utilizar expresiones con caracteristicas muy especiales por lo cual a continuacion iremos describiendo que condiciones tienen que cumplir las expresiones para que puedan ser usadas en la notacion lambda

& x,y,z,w,n,m,k,...\\ & x_{1},x_{2},...\\ & y_{1},y_{2},...\\ & etc \end{aligned}$$ Las variables alfabeticas seran seleccionadas de la lista $$\begin{aligned} & \alpha,\beta,\gamma,\eta,...\\ & \alpha_{1},\alpha_{2},...\\ & \beta_{1},\beta_{2},...\\ & etc \end{aligned}$$
 * 1) Solo utilizaremos expresiones que involucran variables numericas, las cuales se valuaran en numeros de $\omega$, y variables alfabeticas, las cuales se valuaran en palabras del alfabeto previamente fijado. Las variables numericas seran seleccionadas de la lista $$\begin{aligned}
 * 1) Por ejemplo la expresion: $$x+y+1$$ tiene dos variables numericas $x$  e $y$  (y ninguna alfabetica). Si le asignamos a $x$  el valor 2 y a $y$  el valor 45, entonces la expresion $x+y+1$  produce o representa el valor $48=2+45+1$.
 * 2) Otro ejemplo, consideremos la expresion $$\left\vert \alpha\beta\right\vert +\left\vert \alpha\right\vert ^{x}$$ la cual tiene una variable numerica $x$  y dos variables alfabeticas $\alpha$  y $\beta$ . Supongamos ademas que el alfabeto previamente fijado es $\{@,\%\}$ . Si le asignamos a $x$  el valor 2, a $\alpha$  el valor $@@$  y a $\beta$  el valor $\%\%\%$, entonces la expresion $\left\vert \alpha\beta\right\vert +\left\vert \alpha\right\vert ^{x}$  produce o representa el valor $\left\vert @@\%\%\%\right\vert +\left\vert @@\right\vert ^{2}=9$.
 * 3) Para ciertas valuaciones de sus variables la expresion puede no estar definida. Por ejemplo la expresion $$Pred(\left\vert \alpha\right\vert )$$ no asume valor o no esta definida cuando el valor asignado a $\alpha$  es $\varepsilon$ . Otro ejemplo, consideremos la expresion $$x/(y-\left\vert \alpha\right\vert )^{2}$$ Esta expresion no esta definida o no asume valor para aquellas asignaciones de valores a sus variables en las cuales el valor asignado a $y$  sea igual a la longitud del valor asignado a $\alpha$.
 * 4) En los ejemplos anteriores las expresiones producen valores numericos pero tambien trabajaremos con expresiones que producen valores alfabeticos. Por ejemplo la expresion $$\beta^{y}$$ tiene una variable numerica, $y$, una variable alfabetica, $\beta$ , y una vez valuadas estas variables produce un valor alfabetico, a saber el resultado de elevar el valor asignado a la variable $\beta$ , a el valor asignado a $y$.
 * 5) Una expresion $E$  para poder ser utilizada en la notacion lambda relativa a un alfabeto $\Sigma$  debera cumplir alguna de las dos siguientes propiedades
 * 6) los valores que asuma $E$  cuando hayan sido asignados valores de $\omega$  a sus variables numericas y valores de $\Sigma^{\ast}$  a sus variables alfabeticas deberan ser siempre elementos de $\omega$
 * 7) los valores que asuma $E$  cuando hayan sido asignados valores de $\omega$  a sus variables numericas y valores de $\Sigma^{\ast}$  a sus variables alfabeticas deberan ser siempre elementos de $\Sigma^{\ast}$.
 * 8) Por ejemplo la expresion $$x/2$$ no cumple la propiedad dada en (6) ya que para ciertos valores de $\omega$  asignados a la variable $x$, la expresion da valores numericos que se salen de $\omega$  por lo cual no cumple ni (a) ni (b).
 * 9) Otro ejemplo, si el alfabeto fijado es $\Sigma=\{@,\%\}$, entonces la expresion $$@^{x}\$^{y}$$ no cumple la propiedad dada en (6) ya que por ejemplo cuando le asignamos a $x$  el valor 2 y a $y$  el valor 6, la expresion nos da la palabra $@@\$\$\$\$\$\$$  la cual no pertenece a $\Sigma^{\ast}$  por lo cual no cumple ni (a) ni (b).
 * 10) No necesariamente las expresiones que usaremos en la notacion lambda deben ser hechas como combinacion de operaciones matematicas conocidas. Muchas veces usaremos expresiones que involucran incluso lenguaje coloquial castellano. Por ejemplo la expresion $$\mathrm{el\ menor\ numero\ primo\ que\ es\ mayor\ que\ }x$$ Es claro que esta expresion para cada valor de $\omega$  asignado a la variable $x$  produce o representa un valor concreto de $\omega$ . Otro ejemplo: $$\mathrm{el\ tercer\ simbolo\ de\ }\alpha$$ notese que esta expresion, una ves fijado un alfabeto $\Sigma$, estara definida o producira un valor solo cuando le asignamos a $\alpha$  una palabra de $\Sigma^{\ast}$  de longitud mayor o igual a $3$.
 * 11) Expresiones Booleanas. A las expresiones Booleanas tales como $$x=y+1\text{ y }\left\vert \alpha\right\vert \leq22$$

las pensaremos que asumen valores del conjunto $\{0,1\}\subseteq\omega$. Por ejemplo la expresion anterior asume o produce el valor $1$ cuando le asignamos a $x$  el valor 11, a $y$  el valor 10 y a $\alpha$  la palabra $\varepsilon$. Las expresiones Booleanas pensadas de esta forma podran ser utilizadas en la notacion lambda si es que tambien cumplen con las anteriores condiciones.

 * 1) La expresion $$5$$ no tiene variables por lo cual pensaremos que siempre produce el valor $5$  cualesquiera sean los valores asignados a las variables.

Expresiones lambdificables con respecto a $\Sigma$
Dado un alfabeto $\Sigma$ a las expresiones que cumplan las caracteristicas dadas anteriormente las llamaremos lambdificables con respecto a $\Sigma$. Notese que este concepto es intuitivo y no un concepto matematicamente definido en forma precisa. Mas aun el concepto de expresion tampoco ha sido definido matematicamente (aunque obviamente si sabemos que una expresion es una palabra de cierto alfabeto). Esto no nos traera problemas para el uso notacional que las utilizaremos. Recien en las secciones de logica veremos la matematizacion de ciertas expresiones (no las lambdificables) y nos servira de ejemplo para imaginar como podriamos matematizar el concepto de expresion.

Algunos ejemplos:

 * 1) $x/2$  no es lambdificable con respecto a $\Sigma$  cualesquiera sea $\Sigma$
 * 2) $@^{x}\$^{y}$  es lambdificable con respecto a $\{@,\$\}$  y no es lambdificable con respecto a $\{@,\#,\%\}$
 * 3) $x=y+1$  es lambdificable con respecto a $\Sigma$  cualesquiera sea $\Sigma$
 * 4) la expresion $$\mathrm{el\ menor\ numero\ primo\ que\ es\ mayor\ que\ }x^{\left\vert \beta\right\vert }$$ es lambdificable con respecto a $\Sigma$  cualesquiera sea $\Sigma$
 * 5) la expresion $$5$$ es lambdificable con respecto a $\Sigma$  cualesquiera sea $\Sigma$

<span id="definicion-de-lambda-x_1...x_nalpha_1...alpha_mlefteright">

Definicion de $\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]$
Supongamos ya hemos fijado un alfabeto finito $\Sigma$ y supongamos $E$  es una expresion la cual es lambdificable con respecto a $\Sigma$. Sea $x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}$ una lista de variables todas distintas tal que las variables numericas que ocurren en $E$  estan todas contenidas en la lista $x_{1},...,x_{n}$  y las variables alfabeticas que ocurren en $E$  estan en la lista $\alpha_{1},...,\alpha_{m}$  (puede suceder que haya variables de la lista $x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}$  las cuales no ocurran en $E$ ). Entonces $$\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]$$ denotara la funcion definida por:

 * 1) El dominio de $\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]$  es el conjunto de las $(n+m)$ -uplas $(k_{1},...,k_{n},\beta_{1},...,\beta_{m})\in\omega^{n}\times\Sigma^{\ast m}$  tales que $E$  esta definida cuando le asignamos a cada $x_{i}$  el valor $k_{i}$  y a cada $\alpha_{i}$  el valor $\beta_{i}$.
 * 2) $\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right](k_{1},...,k_{n},\beta_{1},...,\beta_{m})=$  valor que asume o representa $E$  cuando le asignamos a cada $x_{i}$  el valor $k_{i}$  y a cada $\alpha_{i}$  el valor $\beta_{i}$.

Notese que por tener $E$ la propiedad (6) de mas arriba, la funcion $\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]$  es $\Sigma$ -mixta de tipo $(n,m,s)$  para algun $s\in\{\#,\ast\}$. Algunos ejemplos:

<ol> <li> Supongamos fijamos el alfabeto $\Sigma=\{@,?,$ $\}$. Entonces $\lambda x\alpha\left[\alpha^{2x}\right]$ es la funcion $$\begin{array}{rll} \omega\times\{@,?,\text{\A1}\}^{\ast} & \rightarrow & \{@,?,\text{\A1}\}^{\ast}\\ (x,\alpha) & \rightarrow & \alpha^{2x} \end{array}$$ Aqui el lector puede notar la dependencia de la notacion lambda respecto del alfabeto fijado. Si en lugar de fijar $\Sigma=\{@,?,$ $\}$ hubieramos fijado $\Sigma=\{\%\}$, entonces $\lambda x\alpha\left[\alpha^{2x}\right]$  denotaria otra funcion, a saber $$\begin{array}{rll} \omega\times\{\%\}^{\ast} & \rightarrow & \{\%\}^{\ast}\\ (x,\alpha) & \rightarrow & \alpha^{2x} \end{array}$$ </li> <li> Supongamos fijamos el alfabeto $\Sigma=\{@,?,$ $\}$. Entonces $\lambda x\alpha\left[5\right]$ es la funcion $$\begin{array}{rll} \omega\times\{@,?,\text{\A1}\}^{\ast} & \rightarrow & \omega\\ (x,y,z,\alpha) & \rightarrow & 5 \end{array}$$ </li> <li> Supongamos fijamos el alfabeto $\Sigma=\{\%,!\}$. Entonces $\lambda\alpha\beta\left[\alpha\beta\right]$ es la funcion $$\begin{array}{rll} \{\%,!\}^{\ast}\times\{\%,!\}^{\ast} & \rightarrow & \{\%,!\}^{\ast}\\ (\alpha,\beta) & \rightarrow & \alpha\beta \end{array}$$ Tambien tenemos que $\lambda\beta\alpha\left[\alpha\beta\right]$ es la funcion $$\begin{array}{rll} \{\%,!\}^{\ast}\times\{\%,!\}^{\ast} & \rightarrow & \{\%,!\}^{\ast}\\ (\beta,\alpha) & \rightarrow & \alpha\beta \end{array}$$ Notese que estas funciones son distintas. Por ejemplo $\lambda\alpha\beta\left[\alpha\beta\right](\%,!)=\%!$ y $\lambda\beta\alpha\left[\alpha\beta\right](\%,!)=!\%$ </li> <li> Independientemente de quien sea $\Sigma$ el alfabeto previamente fijado, tenemos que $\lambda xy[x+y]$  es la funcion $$\begin{array}{rll} \omega^{2} & \rightarrow & \omega\\ (x,y) & \rightarrow & x+y \end{array}$$ Tambien $\lambda xyzw[x+w]$ es la funcion $$\begin{array}{rll} \omega^{4} & \rightarrow & \omega\\ (x,y,z,w) & \rightarrow & x+w \end{array}$$ </li> <li> Supongamos fijamos el alfabeto $\Sigma=\{@,?,$ $\}$. Entonces por la clausula (L1) tenemos que el dominio de la funcion $\lambda xy\alpha\beta\left[Pred(\left\vert \alpha\right\vert )+Pred(y)\right]$ es $$D=\left\{ (x,y,\alpha,\beta)\in\omega^{2}\times\Sigma^{\ast2}:\left\vert \alpha\right\vert \geq1\text{ y }y\geq1\right\}$$ Es decir que $\lambda xy\alpha\beta\left[Pred(\left\vert \alpha\right\vert )+Pred(y)\right]$  es la funcion $$\begin{array}{rll} D & \rightarrow & \omega\\ (x,y,\alpha,\beta) & \rightarrow & Pred(\left\vert \alpha\right\vert )+Pred(y) \end{array}$$ </li> <li> Atentos a (10) de mas arriba, la funcion $\lambda xy\left[x=y\right]$ es el predicado $$\begin{array}{rll} \omega\times\omega & \rightarrow & \omega\\ (x,y) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=y\\ 0\text{ si }x\neq y \end{array}\right. \end{array}$$ y $\lambda x\alpha\left[Pred(x)=\left\vert \alpha\right\vert \right]$ es el predicado $$\begin{array}{rll} \mathbf{N}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }Pred(x)=\left\vert \alpha\right\vert \\ 0\text{ si }Pred(x)\neq\left\vert \alpha\right\vert \end{array}\right. \end{array}$$ Tambien $\lambda\alpha\beta\left[\alpha=\beta\right]$ es el predicado $$\begin{array}{rll} \Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \omega\\ (\alpha,\beta) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }\alpha=\beta\\ 0\text{ si }\alpha\neq\beta \end{array}\right. \end{array}$$ </li> <li> Notar que para $S\subseteq\omega^{n}\times\Sigma^{\ast m}$ se tiene que $\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}=\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[(\vec{x},\vec{\alpha})\in S\right]$ </li> <li> Como dijimos, la notacion lambda depende del alfabeto previamnete fijado, aunque para el caso en que la lista de variables que sigue a la letra $\lambda$ no tenga variables alfabeticas, la funcion representada no depende del alfabeto </li></ol>

Un par de ejemplos sutiles

 * 1) La expresion $$Suc$$ no es lambdificable respecto de cualquier alfabeto $\Sigma$ . Esto es porque si bien cualesquiera sea el valor asignado a las variables, ella asume el valor $Suc$, no cumple (6) de mas arriba ya que $Suc$  no es un elemento de $\omega$  ni tampoco una palabra (es una funcion!)
 * 2) La expresion $$Suc+(\left\vert \beta\right\vert +1)$$ es lambdificable con respecto a $\Sigma$  cualesquiera sea $\Sigma$ . Por ejemplo $\lambda x\beta\lbrack Suc+(\left\vert \beta\right\vert +1)]$  es la funcion $\emptyset$, ya que la expresion $Suc+(\left\vert \beta\right\vert +1)$  cualesquiera sean los valores de $x$  y $\beta$  no esta definida.

Ordenes naturales sobre $\Sigma^{\ast}$
En esta seccion daremos biyecciones naturales entre $\Sigma^{\ast}$ y $\omega$, para cada alfabeto no vacio $\Sigma$. Dichas biyecciones dependen de tener asociado a $\Sigma$ un orden total. Primero haremos un caso particular pero que tiene un interes extra ya que esta emparentado con nuestra notacion decimal clasica de los numeros de $\omega$.

Notacion decimal sin $0$
Llamaremos numerales a los siguientes simbolos $$0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9$$ Usaremos $Num$ para denotar el conjunto de numerales. Notese que $Num\cap\omega=\emptyset$. Es decir, no debemos confundir los simbolos que usualmente denotan los primeros diez numeros enteros con los numeros que ellos denotan. De hecho en china o japon los primeros diez numeros enteros se denotan con otros simbolos. Similarmente las palabras pertenecientes a $Num^{\ast}$ denotan (notacion decimal) a los numeros de $\omega$  pero debemos tener en cuenta que $Num^{\ast}\cap\omega=\emptyset$. Cuando tratamos con palabras de $Num^{\ast}$, debemos ser cuidadosos ya que muchas veces en nuestro discurso matematico (es decir las guias, el apunte, lo que escriben los profesores en el pizarron, etc) representamos dos objetos diferentes de la misma forma. Por ejemplo $45$ puede estar denotando al numero entero cuarenta y cinco o tambien $45$  puede estar denotando la palabra de longitud $2$  cuyo primer simbolo es el numeral $4$  y cuyo segundo simbolo es el numeral $5$, es decir ella misma. Por dar otro ejemplo, el simbolo $1$ en nuestro discurso algunas veces se denotara a si mismo y otras veces denotara al numero uno.

Es bien conocido que, en notacion decimal, las siguientes palabras del alfabeto $Num$, denotan, de menor a mayor, a los numeros de $\omega$ $$0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...$$ Por supuesto esta lista de palabras es infinita pero asumimos que el lector sabe como obtener la palabra siguiente a cada miembro de la lista (i.e. sumar 1 en notacion decimal), lo cual determina por completo la lista conociendo que la misma comienza con la palabra $0$.

Cabe destacar que debido a la presencia del numeral $0$ en la lista, la $n$ -esima palabra representa o denota al numero $n-1$  o, dicho de otra forma, el numero $n\in\omega$  es representado por la $(n+1)$ -esima palabra de la lista.

Un detalle de la representacion decimal de numeros de $\omega$ mediante palabras de $Num^{\ast}$  es que la misma no nos da una biyeccion entre $Num^{\ast}$  y $\omega$  ya que por ejemplo las palabras $00016$  y $16$  representan el mismo numero. Dicho de otra forma en la lista anterior no figuran todas las palabras de $Num^{\ast}$, a saber estan omitidas todas las palabras que comienzan con el simbolo $0$ y tienen longitud mayor que uno. A continuacion daremos una representacion de los numeros de $\omega$ mediante palabras, la cual no tendra este problema. El alfabeto que usaremos tendra todos los numerales menos el $0$ y ademas tendra un simbolo para denotar al numero diez, a saber el simbolo $d$. Es decir $$\widetilde{Num}=\{1,2,3,4,5,6,7,8,9,d\}$$ Representaremos a los numeros de $\omega$ con la siguiente lista infinita de palabras de $\widetilde{Num}$

$\bigskip$

$\varepsilon,1,2,3,4,5,6,7,8,9,d,$

$11,12,...,1d,21,22,...,2d,...,91,92,...,9d,d1,d2,...,dd,$

$111,112,...,11d,121,122,...,12d,...$

El lector ya se habra dado cuenta de que el siguiente a una palabra $\alpha$ de la lista anterior se obtiene aplicando las siguientes clausulas

 * 1) si $\alpha=d^{n}$, con $n\geq0$  entonces el siguiente de $\alpha$  es $1^{n+1}$
 * 2) si $\alpha$  no es de la forma $d^{n}$, con $n\geq0$ , entonces el siguiente de $\alpha$  se obtiene de la siguiente manera:
 * 3) buscar de derecha a izquierda el primer simbolo no igual a $d$
 * 4) reemplazar dicho simbolo por su siguiente en la lista $1,2,3,4,5,6,7,8,9,d$
 * 5) reemplazar por el simbolo $1$  a todos los simbolos iguales a $d$  que ocurrian a la derecha del simbolo reemplazado

Notese que

<ol> <li> El numero $0$ es representado en la lista anterior con la palabra $\varepsilon$ </li> <li> El numero $1$ es representado en la lista anterior con la palabra $1$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots$ </li> <li> El numero $9$ es representado en la lista anterior con la palabra $9$ </li> <li> El numero $10$ es representado en la lista anterior con la palabra $d$ </li> <li> El numero $11$ es representado en la lista anterior con la palabra $11$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots$ </li> <li> El numero $19$ es representado en la lista anterior con la palabra $19$ </li> <li> El numero $20$ es representado en la lista anterior con la palabra $1d$ </li> <li> El numero $21$ es representado en la lista anterior con la palabra $21$ </li> <li> El numero $22$ es representado en la lista anterior con la palabra $22$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots$ </li></ol>

Como puede notarse en estos primeros veinte y pico numeros solo dos (el $0$ y el $20$ ) se representan en forma distinta a la reprentacion decimal clasica. Es natural que $\varepsilon$ denote al numero $0$  y ademas notese que la palabra $1d$  (que en la lista representa el $20$ ) puede leerse como "diecidiez" (es decir la palabra que sigue a "diecinueve") que justamente es $20$. Por supuesto con esta manera de pensar la palabra $2d$ deberiamos leerla como "ventidiez" y si nos fijamos en la lista ella representa al numero treinta lo cual nuevamente es muy natural. Otro ejemplo: a $6d$ deberiamos leerla como "sesentidiez" y es natural ya que en la lista representa al setenta. Tambien, la palabra $9d$ puede leerse noventidiez ya que representa en la lista al numero $100$.

La lista anterior va representando los numeros de $\omega$ en forma muy natural pero aunque nuestra intuicion nos diga que no, en principio podria pasar que una misma palabra del alfabeto $\widetilde{Num}$  ocurra dos veces en la lista y esto nos diria que una misma palabra estaria representando a dos numeros distintos. Tambien, en principio podria suceder que haya una palabra del alfabeto $\widetilde{Num}$ la cual nunca figure en la lista. Mas abajo probaremos que estas dos posibilidades no suceden, es decir muestran que

 * 1) Toda palabra de $\widetilde{Num}^{\ast}$  aparece en la lista
 * 2) Ninguna palabra de $\widetilde{Num}^{\ast}$  aparece mas de una ves

Notese que la propiedad (S) nos dice que la funcion $$\begin{array}[t]{rll} \ast:\omega & \rightarrow & \widetilde{Num}^{\ast}\\ n & \rightarrow & (n+1)\text{-esimo elemento de la lista} \end{array}$$ es sobreyectiva y la propiedad (I) nos garantiza que dicha funcion es inyectiva, por lo cual entre las dos nos garantizan que dicha representacion establece una biyeccion entre $\omega$ y $\widetilde{Num}^{\ast}$.

Por supuesto, la pregunta que inmediatamente surge es como calcular la inversa de $\ast$. Llamemos $\#$ a la inversa de $\ast$. Notese que dada una palabra $\alpha\in\widetilde{Num}^{\ast}$, el numero $\#(\alpha)$ es justamente el numero representado por la palabra $\alpha$ , o dicho de otra forma $\#(\alpha)$  es la posicion que ocupa $\alpha$  en la lista, contando desde el $0$  (es decir $\alpha$  es la $(\#(\alpha)+1)$ -esima palabra de la lista). Por ejemplo: $$\begin{gathered} \#(\varepsilon)=0\\ \#(1)=1\\ \vdots\\ \#(9)=9\\ \#(d)=10\\ \#(11)=11\\ \#(12)=12\\ \vdots\\ \#(19)=19\\ \#(1d)=20 \end{gathered}$$ Aqui hay que tener cuidado como leemos las igualdades anteriores. Por ejemplo en la igualdad $$\#(1)=1$$ la primera ocurrencia del simbolo $1$ se refiere al numeral uno, es decir denota una palabra y la segunda ocurrencia se esta refiriendo al numero uno, es decir denota un numero.

Dejamos al lector el ejercicio de ganar intuicion con ejemplos hasta que se convensa de que tal como en el caso de la notacion decimal, el numero $\#(\alpha)$ se expresa como una suma de potencias de $10$, con los coeficientes dados en funcion de los simbolos de $\alpha$. Mas concretamente si $\alpha=s_{1}s_{2}...s_{k}$ con $k\geq1$  y $s_{1},s_{2},...,s_{k}\in\widetilde{Num}$, entonces $$\#(\alpha)=\#(s_{1}).10^{k-1}+\#(s_{2}).10^{k-2}+...+\#(s_{k}).10^{0}$$ No daremos aqui una prueba de este hecho ya que lo probaremos abajo para el caso general. Para ganar intuicion sobre el mismo el lector puede ver mas abajo la prueba de las propiedades (S) e (I), desde donde se ve con mas claridad como va aumentando la funcion $\#$ a medida que recorremos la lista de izquierda a derecha. Algunos ejemplos $$\begin{aligned} \#(1d) & =1.10^{1}+10.10^{0}=10+10=20\\ \#(dd) & =10.10^{1}+10.10^{0}=100+10=110\\ \#(111) & =1.10^{2}+1.10^{1}+1.10^{0}=100+10+1=111\\ \#(1d3d) & =1.10^{3}+10.10^{2}+3.10^{1}+10.10^{0} \end{aligned}$$

Ahora que sabemos que las palabras de $\widetilde{Num}$ representan los numeros como suma de potencias de diez, en forma analoga a la notacion decimal clasica, podemos refozar aun mas la analogia poniendo nombres adecuados que, tal como en el caso clasico, nos permitan leer las palabras de $\widetilde{Num}$  describiendo su suma de potencias asociada. Por ejemplo podriamos llamar "decenta" al numero $100$, por analogia a "treinta", "cuarenta",...,"noventa". O sea una decenta es diez veces diez. De esta forma la palabra $d1$ se leera "decenta y uno" y esto es natural ya que en la lista representa al $101$. La palabra $dd$ se leera "decenta y diez" y esto describe a la perfeccion el numero que representa, i.e. el $10.10+10=110$. La palabra que sigue en la lista a $dd$ es $111$  la cual representa al $111$, es decir aqui como en los otros casos vistos en los cuales no hay ocurrencias del simbolo $d$  la palabra representa al mismo numero que representa en la notacion decimal clasica. Por dar otro ejemplo, la palabra $59d3$ se leera "cinco mil novecientos decenta y tres" y representara al numero $6003$.

Para seguir debemos ponerle nombre a "diez veces cien", es decir, "decientos" (por analogia con "novecientos = nueve veces cien") denotara al numero $1000=10.100$. De esta forma la palabra $d51$ se leera "decientos cincuenta y uno" y esto es natural ya que pensando un rato se puede ver que ella representa al $1051$. Tambien, la palabra $ddd$ se leera "decientos decenta y diez" y representara al numero $1110$.

Prueba de las propiedades (S) e (I)
Dado que el siguiente a un elemento $\alpha$ de la lista es de la misma longitud que $\alpha$  o tiene longitud igual a $\left\vert \alpha\right\vert +1$, podemos representar la lista anterior de la siguiente manera: $$B_{0};B_{1};B_{2};B_{3};B_{4};...$$ donde cada $B_{n}$  es, por definicion, la parte de la lista en la cual las palabras tienen longitud exactamente $n$. Por ejemplo:

 * 1) $B_{0}$  es $\varepsilon$
 * 2) $B_{1}$  es $1,2,3,4,5,6,7,8,9,d$
 * 3) $B_{2}$  es $11,12,...,1d,21,22,...,2d,...,91,92,...,9d,d1,d2,...,dd$

Notese que hasta el momento nada nos asegura que no suceda que para algun $n$ se de que $B_{n}$  sea una lista infinita, lo cual ademas nos diria que los bloques $B_{n+1},B_{n+2},...$  son todos vacios. Es decir podria pasar que la lista se estanque en una longitud $n$ y nunca aparezca una palabra de longitud mayor que $n$. Esto por supuesto obligaria a que se repitan muchas veces palabras de dicha longitud $n$ ya que hay una cantidad finita de las mismas ($10^{n}$ ).

Por supuesto nuestra intuicion nos dice que en el bloque $B_{n}$ estan listadas sin repeticion todas las palabras de $\widetilde{Num}^{\ast}$  de longitud $n$, pero debemos justificar esto con argumentos solidos. Algunas propiedades basicas que se pueden probar facilmente son:

 * 1) Si $B_{n}=\alpha_{1},...,\alpha_{k}$, entonces $\alpha_{1}=1^{n}$  y $\alpha_{k}=d^{n}$
 * 2) Si $d^{n}$  ocurre en $B_{n}$  lo hace en la ultima posicion

estas propiedades son consecuencias inmediatas de como se calcula el elemento siguiente a uno dado en la lista y son dejadas como ejercicio. Otra propiedad importante es la siguiente

 * 1) Si $B_{n}=\alpha_{1},...,\alpha_{k}$, entonces $B_{n+1}=1\alpha_{1},...,1\alpha_{k},2\alpha_{1},...,2\alpha_{k},...,d\alpha_{1},...,d\alpha_{k}$

Para probar (3) es muy util el siguiente resultado obvio

Lemma 10. Sea $\sigma\in\widetilde{Num}$ y supongamos $\alpha\in\widetilde{Num}^{\ast}$  no es de la forma $d^{n}$. Entonces el siguiente a $\sigma\alpha$ es $\sigma\beta$  donde $\beta$  es el siguiente a $\alpha$

Dejamos como ejercicio al lector hacer la prueba de (3) usando el lema anterior y las propiedades (1) y (2). Ahora es facil usando (3) probar inductivamente que

 * 1) $B_{n}$  es una lista sin repeticiones de todas las palabras de longitud $n$

Pero claramente de (4) se desprenden en forma obvia las propiedades (S) y (I).

El caso general
Sea $\Sigma$ un alfabeto no vacio y supongamos $\leq$  es un orden total sobre $\Sigma$. Supongamos que $\Sigma=\{a_{1},...,a_{n}\}$, con $a_{1}<a_{2}<...<a_{n}$. Inspirados en la lista dada anteriormente de las palabras de $\widetilde{Num}^{\ast}$, podemos dar la siguiente lista de palabras de $\Sigma^{\ast}$

${\small\varepsilon,a}_{1}{\small,a}_{2}{\small,...,a}_{n}{\small,}$

${\small a}_{1}{\small a}_{1}{\small,a}_{1}{\small a}_{2}{\small,...,a}_{1}{\small a}_{n}{\small,a}_{2}{\small a}_{1}{\small,a}_{2}{\small a}_{2}{\small,...,a}_{2}{\small a}_{n}{\small,...,a}_{n}{\small a}_{1}{\small,a}_{n}{\small a}_{2}{\small,...,a}_{n}{\small a}_{n}{\small,}$

${\small a}_{1}{\small a}_{1}{\small a}_{1}{\small,a}_{1}{\small a}_{1}{\small a}_{2}{\small,...,a}_{1}{\small a}_{1}{\small a}_{n}{\small,a}_{1}{\small a}_{2}{\small a}_{1}{\small,a}_{1}{\small a}_{2}{\small a}_{2}{\small,...,a}_{1}{\small a}_{2}{\small a}_{n}{\small,...,a}_{1}{\small a}_{n}{\small a}_{1}{\small,a}_{1}{\small a}_{n}{\small a}_{2}{\small,a}_{1}{\small a}_{n}{\small a}_{n}{\small,}$

${\small a}_{2}{\small a}_{1}{\small a}_{1}{\small,a}_{2}{\small a}_{1}{\small a}_{2}{\small,...,a}_{2}{\small a}_{1}{\small a}_{n}{\small,a}_{2}{\small a}_{2}{\small a}_{1}{\small,a}_{2}{\small a}_{2}{\small a}_{2}{\small,...,a}_{2}{\small a}_{2}{\small a}_{n}{\small,...,a}_{2}{\small a}_{n}{\small a}_{1}{\small,a}_{2}{\small a}_{n}{\small a}_{2}{\small,a}_{2}{\small a}_{n}{\small a}_{n}{\small,}$

${\small\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\vdots$

${\small a}_{n}{\small a}_{1}{\small a}_{1}{\small,a}_{n}{\small a}_{1}{\small a}_{2}{\small,...,a}_{n}{\small a}_{1}{\small a}_{n}{\small,a}_{n}{\small a}_{2}{\small a}_{1}{\small,a}_{n}{\small a}_{2}{\small a}_{2}{\small,...,a}_{n}{\small a}_{2}{\small a}_{n}{\small,...,a}_{n}{\small a}_{n}{\small a}_{1}{\small,a}_{n}{\small a}_{n}{\small a}_{2}{\small,a}_{n}{\small a}_{n}{\small a}_{n}{\small,}$

${\small a}_{1}{\small a}_{1}{\small a}_{1}{\small a}_{1}{\small,a}_{1}{\small a}_{1}{\small a}_{1}{\small a}_{2}{\small,...}$

El objetivo es probar que la lista anterior enumera sin repeticiones todas las palabras de $\Sigma^{\ast}$, i.e. produce naturalmente una biyeccion entre $\omega$ y $\Sigma^{\ast}$. Pero antes debemos definir mas formalmente la lista. Para esto definamos $s^{\leq}:\Sigma^{\ast}\rightarrow\Sigma^{\ast}$ de la siguiente manera

 * 1) $s^{\leq}((a_{n})^{m})=(a_{1})^{m+1}$, para cada $m\geq0$
 * 2) $s^{\leq}(\alpha a_{i}(a_{n})^{m})=\alpha a_{i+1}(a_{1})^{m}$, cada vez que $\alpha\in\Sigma^{\ast}$ , $1\leq i<n$  y $m\geq0$

Notese que la definicion de $s^{\leq}$ es correcta ya que una palabra de $\Sigma^{\ast}$  ya sea es de la forma $(a_{n})^{m}$, con $m\geq0$ , o es de la forma $\alpha a_{i}(a_{n})^{m}$ , con $\alpha\in\Sigma^{\ast}$ , $1\leq i<n$  y $m\geq0$ ; y estos dos casos posibles son mutuamente excluyentes.

Claramente se tiene entonces que la lista anterior puede ser escrita de la siguiente manera $$\varepsilon,s^{\leq}(\varepsilon),s^{\leq}(s^{\leq}(\varepsilon)),s^{\leq}(s^{\leq}(s^{\leq}(\varepsilon))),s^{\leq}(s^{\leq}(s^{\leq}(s^{\leq}(\varepsilon)))),...$$ Con esta definicion formal de la lista, podemos probar de la misma forma en la que lo hicimos arriba para el caso $\Sigma=\widetilde{Num}$ que:

 * 1) Toda palabra de $\Sigma^{\ast}$  aparece en la lista
 * 2) Ninguna palabra de $\Sigma^{\ast}$  aparece mas de una ves en la lista

(dejamos al lector los detalles por tratarse de un argumento completamente similar).

Definamos $\ast^{\leq}:\omega\rightarrow\Sigma^{\ast}$ recursivamente de la siguiente manera:

 * 1) $\ast^{\leq}(0)=\varepsilon$
 * 2) $\ast^{\leq}(i+1)=s^{\leq}(\ast^{\leq}(i))$

Es claro que entonces $\ast^{\leq}(i)$ nos da el $(i+1)$ -esimo elemento de la lista, o lo que es lo mismo, el $i$ -esimo elemento de la lista contando desde el $0$. O sea que las propiedades (S) y (I) nos garantizan que la funcion $\ast^{\leq}$ es biyectiva. A continuacion describiremos su inversa. Primero un lema facil pero muy importante.

Lemma 11. Sea $\Sigma$ un alfabeto no vacio y supongamos $\leq$  es un orden total sobre $\Sigma$. Supongamos que $\Sigma=\{a_{1},...,a_{n}\}$, con $a_{1}<a_{2}<...<a_{n}$. Entonces para cada $\alpha\in\Sigma^{\ast}-\{\varepsilon\}$ hay unicos $k\in\omega$  y $i_{0},i_{1},...,i_{k}\in\{1,...,n\}$  tales que $$\alpha=a_{i_{k}}...a_{i_{0}}$$

Notar que $k$ del lema anterior es $\left\vert \alpha\right\vert -1$  y los numeros $i_{k},...,i_{0}$  van dando el numero de orden de cada simbolo de $\alpha$  yendo de izquierda a derecha. Por ejemplo si $\Sigma=\{\%,!,@\}$ y $\leq$  es el orden total sobre $\Sigma$  dado por $\%<!<@$  (es decir que aqui $a_{1}=\%$, $a_{2}=!$  y $a_{3}=@$ ) entonces para la palabra $!\%@\%@$  tenemos $k=4$  y $i_{4}=2$ , $i_{3}=1$ , $i_{2}=3$ , $i_{1}=1$  y $i_{0}=3$. Sin envargo si hubieramos tomado el orden dado por $@<\%<!$, para la misma palabra hubieramos tenido $i_{4}=3$ , $i_{3}=2$ , $i_{2}=1$ , $i_{1}=2$ y $i_{0}=1$.

Ahora podemos definir la funcion $\#^{\leq}$ de la siguiente manera $$\begin{array}[t]{rll} \#^{\leq}:\Sigma^{\ast} & \rightarrow & \omega\\ \varepsilon & \rightarrow & 0\\ a_{i_{k}}...a_{i_{0}} & \rightarrow & i_{k}n^{k}+...+i_{0}n^{0} \end{array}$$

Lemma 12. 'La funcion $\#^{\leq}$ es la inversa de $\ast^{\leq}$ '

Proof. Primero probaremos por induccion en $x$ que

 * 1) Para cada $x\in\omega$, se tiene que $\#^{\leq}(\ast^{\leq}(x))=x$

El caso $x=0$ es trivial. Supongamos que $\#^{\leq}(\ast^{\leq}(x))=x$, veremos entonces que $\#^{\leq}(\ast^{\leq}(x+1))=x+1$. Sean $k\geq0$ y $i_{k},...,i_{0}$  tales que $\ast^{\leq}(x)=a_{i_{k}}...a_{i_{0}}$. Ya que $\#^{\leq}(\ast^{\leq}(x))=x$ tenemos que $x=i_{k}n^{k}+...+i_{0}n^{0}$. Hay varios casos.

Caso $i_{0}<n$. Entonces $\ast^{\leq}(x+1)=s^{\leq}(\ast^{\leq}(x))=a_{i_{k}}...a_{i_{0}+1}$ por lo cual $$\begin{array}{ll} \#^{\leq}(\ast^{\leq}(x+1)) & =i_{k}n^{k}+i_{k-1}n^{k-1}+...+(i_{0}+1)n^{0}\\ & =\left(i_{k}n^{k}+i_{k-1}n^{k-1}+...+i_{0}n^{0}\right)+1\\ & =x+1 \end{array}$$ Caso $i_{k}=i_{k-1}=...=i_{0}=n$. Entonces $\ast^{\leq}(x+1)=s^{\leq}(\ast^{\leq}(x))=(a_{1})^{k+2}$ por lo cual $$\begin{array}{ll} \#^{\leq}(\ast^{\leq}(x+1)) & =1n^{k+1}+1n^{k}+...+1n^{1}+1n^{0}\\ & =\left(nn^{k}+nn^{k-1}+...+nn^{0}\right)+1\\ & =x+1 \end{array}$$ Caso $i_{0}=i_{1}=...=i_{h}=n$, $\;i_{h+1}\not=n$ ,  para algun $0\leq h<k$. Entonces $\ast^{\leq}(x+1)=s^{\leq}(\ast^{\leq}(x))=a_{i_{k}}...a_{i_{h+2}}a_{i_{h+1}+1}(a_{1})^{h}$ por lo cual $$\begin{array}{ll} \#^{\leq}(\ast^{\leq}(x+1)) & =i_{k}n^{k}+...+i_{h+2}n^{h+2}+(i_{h+1}+1)n^{h+1}+1n^{h}+...+1n^{1}+1n^{0}\\ & =\left(i_{k}n^{k}+...+i_{h+2}n^{h+2}+i_{h+1}n^{h+1}+n^{h+1}+n^{h}+...+n^{1}\right)+1\\ & =\left(i_{k}n^{k}+...+i_{h+2}n^{h+2}+i_{h+1}n^{h+1}+nn^{h}+...+nn^{0}\right)+1\\ & =x+1 \end{array}$$ De esta forma hemos probado (a).

Por definicion la inversa de $\ast^{\leq}$ es la funcion con dominio $\Sigma^{\ast}$  que a una palabra $\alpha$  le asocia el unico $x\in\omega$  tal que $\ast^{\leq}(x)=\alpha$. Es decir debemos probar que

 * 1) $\#^{\leq}(\alpha)=$  unico $x\in\omega$  tal que $\ast^{\leq}(x)=\alpha$, para cada $\alpha\in\Sigma^{\ast}$

Pero (b) es una concecuencia inmediata de (a).

-

Cabe destacar que dada una palabra $\alpha$, el numero $\#^{\leq}(\alpha)$ nos dice en que posicion se hubica $\alpha$  en la lista, es decir $\alpha$  es la ($\#^{\leq}(\alpha)+1$ )-esima palabra de la lista.

De los desarrollos hechos se desprende el interesante resultado. Dejamos al lector la prueba como ejercicio.

Lemma 13. Sea $n\geq1$ fijo. Entonces cada $x\geq1$ se escribe en forma unica de la siguiente manera: $$x=i_{k}n^{k}+i_{k-1}n^{k-1}+...+i_{0}n^{0},$$ con $k\geq0$  y $1\leq i_{k},i_{k-1},...,i_{0}\leq n$ .

Como hemos visto las biyecciones dadas producen una "identificacion" entre numeros de $\omega$ y palabras del alfabeto $\Sigma$. Es decir, en algun sentido identificamos palabras y numeros ya que se corresponden biunivocamente. Supongamos que $\alpha$ es una palabra de $\Sigma^{\ast}-\{\varepsilon\}$  y queremos "verla como un numero". Entonces en ves de ver sus simbolos vemos los ordenes de aparicion en $\Sigma$ de los mismos y miramos la suma de potencias asociada.

Supongamos ahora que $x$ es un numero de $\omega-\{0\}$  y ademas supongamos que somos super inteligentes y que cuando vemos a $x$  vemos la secuencia unica de numeros $i_{k},i_{k-1},...,i_{0}$  que nos permite expresarlo como suma de potencias segun el lema anterior. Entonces si queremos ver a $x$ como una palabra simplemente miramos la secuencia $i_{k},i_{k-1},...,i_{0}$  como palabra, reemplazando cada $i_{j}$  por el simbolo $i_{j}$ -esimo de $\Sigma$.

Caracter recursivo de las funciones $s^{\protect\leq}$, $\ast^{\protect\leq}$ y $\#^{\protect\leq}$
Es un ejercicio (dejado al lector) probar que cualquiera sea $\alpha\in\Sigma^{\ast}$, se tiene que $$\begin{aligned} s^{\leq}(\varepsilon) & =a_{1}\\ s^{\leq}(\alpha a_{i}) & =\alpha a_{i+1}\text{, }i<n\\ s^{\leq}(\alpha a_{n}) & =s^{\leq}(\alpha)a_{1} \end{aligned}$$ Notese que esto nos permite calcular recursivamente el valor de $s^{\leq}$ ya que las ecuaciones anteriores nos muestran como obtener rapidamente $s^{\leq}(\alpha a)$  en terminos de $s^{\leq}(\alpha)$  y $a$, donde $a$  es un elemento cualquiera de $\Sigma$. Por supuesto, en algun momento deberemos usar el dato inicial $s^{\leq}(\varepsilon)=a_{1}$. En un lenguaje de programacion funcional, las tres ecuaciones anteriores son directamente un programa para computar $s^{\leq}$ o si se quiere una definicion de dicha funcion. Dejamos al lector que intente usar las ecuaciones anteriores para dar un programa imperativo que compute $s^{\leq}$ (esto esta hecho mas adelante en la primera lista de funciones $\Sigma$ -efectivamente computables).

Lo mismo sucede con la funcion $\ast^{\leq}$ la cual fue directamente definida en forma recursiva por las ecuaciones $$\begin{aligned} \ast^{\leq}(0) & =\varepsilon\\ \ast^{\leq}(i+1) & =s^{\leq}(\ast^{\leq}(i)) \end{aligned}$$ Dejamos al lector corroborar que la funcion $\#^{\leq}$ verifica las siguientes ecuaciones, las cuales obviamente pueden ser usadas para calcular recursivamente sus valores $$\begin{aligned} \#^{\leq}(\varepsilon) & =0\\ \#^{\leq}(\alpha a_{i}) & =\#^{\leq}(\alpha).n+i \end{aligned}$$

Extension del orden total de $\Sigma$ a $\Sigma^{\ast}$
Podemos extender el orden de $\Sigma$ a $\Sigma^{\ast}$  de la siguiente manera

 * 1) $\alpha\leq\beta$  sii $\#^{\leq}(\alpha)\leq\#^{\leq}(\beta)$

Es decir $\alpha\leq\beta$ sii $\alpha=\beta$  o $\alpha$  ocurre antes que $\beta$  en la lista. Dejamos como ejercicio para el lector probar que $\leq$ es un orden total sobre $\Sigma^{\ast}$.

Deberia ser intuitivamente claro que el orden recien definido sobre $\Sigma^{\ast}$ posee las mismas propiedades matematicas que el orden usual de $\omega$. Esto se entendera en forma mas profunda cuando veamos el concepto de isomorfismo de posets en los capitulos de logica. Veamos un ejemplo:

Lemma 14. 'Si $S\subseteq\Sigma^{\ast}$ es no vacio, entonces existe $\alpha\in S$  tal que $\alpha\leq\beta$, para cada $\beta\in S$ .'

title: User:Tomaspgwk/sandbox