Notacion y conceptos basicos

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

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

Para ${\textstyle 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 ${\textstyle x,y\in \omega }$ diremos que ${\textstyle x}$ divide a ${\textstyle y}$ cuando haya un ${\textstyle z\in \omega }$ tal que ${\textstyle y=z.x}$ . Notar que ${\textstyle 0}$ divide a ${\textstyle 0}$ , ${\textstyle 3}$ divide a ${\textstyle 0}$ y ${\textstyle 0}$ no divide a ${\textstyle 23}$ . Escribiremos ${\textstyle x\mid y}$ para expresar que ${\textstyle x}$ divide a ${\textstyle y}$ . Dados ${\textstyle x,y\in \omega }$ , diremos que ${\textstyle x}$ e ${\textstyle y}$ son coprimos cuando ${\textstyle 1}$ sea el unico elemento de ${\textstyle \omega }$ que divide a ambos. Notese que ${\textstyle x}$ e ${\textstyle y}$ no son son coprimos sii existe un numero primo ${\textstyle p\in \omega }$ que los divide a ambos

Si bien no hay una definicion natural en matematica de cuanto vale ${\textstyle 0^{0}}$ ( ${\textstyle 0}$ elevado a la ${\textstyle 0}$ ), por convencion para nosotros ${\textstyle 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 ${\textstyle A,B}$ , se tiene que ${\textstyle A=B}$ si y solo si para cada objeto ${\textstyle 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 ${\textstyle A,B}$ son iguales, extensionalidad nos asegura que basta con ver que se dan las dos inclusiones ${\textstyle A\subseteq B}$ y ${\textstyle 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

${\textstyle \{x\in \mathbf {N} :x=1}$ o ${\textstyle x\geq 5\}}$
${\textstyle \{x:x\in \mathbf {R} }$ y ${\textstyle x^{2}\geq 100\}}$
${\textstyle \{x:x=100\}}$
${\textstyle \{x^{2}+1:x\in \omega \}}$
${\textstyle \{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 ${\textstyle A_{1},...,A_{n}}$ , con ${\textstyle n\geq 2}$ , usaremos ${\textstyle A_{1}\times ...\times A_{n}}$ para denotar el producto Cartesiano de ${\textstyle A_{1},...,A_{n}}$ , es decir el conjunto formado por todas las ${\textstyle n}$ -uplas ${\textstyle (a_{1},...,a_{n})}$ tales que ${\textstyle a_{1}\in A_{1},...,a_{n}\in A_{n}}$ . Si ${\textstyle A_{1}=...=A_{n}=A}$ , con ${\textstyle n\geq 2}$ , entonces escribiremos ${\textstyle A^{n}}$ en lugar de ${\textstyle A_{1}\times ...\times A_{n}}$ . Para ${\textstyle n=1}$ , definimos ${\textstyle A^{n}=A}$ , es decir ${\textstyle A^{1}=A}$ . Usaremos ${\textstyle \Diamond }$ para denotar la unica ${\textstyle 0}$ -upla. Definimos entonces ${\textstyle A^{0}=\{\Diamond \}}$ . Si ${\textstyle A}$ es un conjunto denotaremos con ${\textstyle A^{\mathbf {N} }}$ al conjunto formado por todas las infinituplas ${\textstyle (a_{1},a_{2},...)}$ tales que ${\textstyle a_{i}\in A}$ para cada ${\textstyle i\in \mathbf {N} }$ . Por ejemplo $(1,2,3,4,...)\in \omega ^{\mathbf {N} }$ donde ${\textstyle (1,2,3,4,...)}$ es una forma intuitiva de denotar la infinitupla cuyo ${\textstyle i}$ -esimo elemento es el numero natural ${\textstyle i}$ .

Si ${\textstyle (A_{1},A_{2},...)}$ es una infinitupla de conjuntos, entonces usaremos ${\textstyle \bigcup \nolimits _{i=1}^{\infty }A_{i}}$ o ${\textstyle \bigcup \nolimits _{i\geq 1}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 ${\textstyle \emptyset }$ es un alfabeto. Si ${\textstyle \Sigma }$ es un alfabeto, entonces ${\textstyle \Sigma ^{\ast }}$ denotara el conjunto de todas las palabras formadas con simbolos de ${\textstyle \Sigma }$ . Las palabras de longitud ${\textstyle 1}$ son exactamente los elementos de ${\textstyle \Sigma }$ , en particular esto nos dice que ${\textstyle \Sigma \subseteq \Sigma ^{\ast }}$ . La unica palabra de longitud ${\textstyle 0}$ es denotada con ${\textstyle \varepsilon }$ . Ya que en ${\textstyle \varepsilon }$ no ocurren simbolos, tenemos que ${\textstyle \varepsilon \in \Sigma ^{\ast }}$ , para cualquier alfabeto, mas aun notese que ${\textstyle \emptyset ^{\ast }=\{\varepsilon \}}$ . Usaremos ${\textstyle \left\vert \alpha \right\vert }$ para denotar la longitud de la palabra ${\textstyle \alpha }$ . Si ${\textstyle \alpha \in \Sigma ^{\ast }}$ y ${\textstyle \sigma \in \Sigma }$ , usaremos ${\textstyle \left\vert \alpha \right\vert _{\sigma }}$ para denotar la cantidad de ocurrencias del simbolo ${\textstyle \sigma }$ en ${\textstyle \alpha }$ . Usaremos ${\textstyle \Sigma ^{+}}$ para denotar al conjunto ${\textstyle \Sigma ^{\ast }-\{\varepsilon \}}$ . Notese que funciones, ${\textstyle n}$ -uplas y palabras son objetos de distinto tipo, por lo cual ${\textstyle \emptyset }$ , ${\textstyle \Diamond }$ y ${\textstyle \varepsilon }$ son tres objetos matematicos diferentes.

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

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

Dados ${\textstyle i\in \omega }$ y ${\textstyle \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 ${\textstyle \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 \geq 1\\\varepsilon &&{\text{caso contrario}}\end{array}}\right.$ La palabra ${\textstyle \gamma ^{R}}$ es llamada la resiproca de ${\textstyle \gamma }$ .

Ocurrencias

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

Notese que una palabra ${\textstyle \alpha }$ puede ocurrir en ${\textstyle \beta }$ , a partir de ${\textstyle i}$ , y tambien a partir de ${\textstyle j}$ , con ${\textstyle i\neq j}$ . En virtud de esto, hablaremos de las distintas ocurrencias de ${\textstyle \alpha }$ en ${\textstyle \beta }$ . Por ejemplo hay dos ocurrencias de la palabra ${\textstyle aba}$ en la palabra $cccccccabaccccabaccccc$ y tambien hay dos ocurrencias de la palabra ${\textstyle aba}$ en la palabra $cccccccababacccccccccc$ En el primer caso diremos que dichas ocurrencias de ${\textstyle 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 ${\textstyle ab}$ en ${\textstyle babbbfabcccfabccc}$ esta contenida en la primer ocurrencia de ${\textstyle fabc}$ en ${\textstyle 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 ${\textstyle abb}$ en ${\textstyle ccabbgfgabbgg}$ por ${\textstyle oolala}$ es la palabra ${\textstyle ccoolalagfgabbgg}$ . Cuando todas las ocurrencias de una palabra ${\textstyle \alpha }$ en una palabra ${\textstyle \beta }$ sean disjuntas entre si, podemos hablar del resultado de reeplazar simultaneamente cada ocurrencia de ${\textstyle \alpha }$ en ${\textstyle \beta }$ por ${\textstyle \gamma }$ . Por ejemplo si tenemos ${\begin{aligned}\alpha &=yet\\\beta &=ghsyetcjjjyetbcpyeteabc\\\gamma &=\%\%\end{aligned}}$ entonces ${\textstyle ghs\%\%cjjj\%\%bcp\%\%eabc}$ es el resultado de reemplazar simultaneamente cada ocurrencia de ${\textstyle \alpha }$ en ${\textstyle \beta }$ por ${\textstyle \gamma }$ . Es importante notar que los reemplazos se hacen simultaneamente y no secuencialmente (i.e. reemplazando la primer ocurrencia de ${\textstyle \alpha }$ por ${\textstyle \gamma }$ y luego al resultado reemplazarle la primer ocurrencia de ${\textstyle \alpha }$ por ${\textstyle \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 ${\textstyle \alpha _{1},...,\alpha _{n}}$ (con ${\textstyle \alpha _{i}\neq \alpha _{j}}$ , para ${\textstyle i\neq j}$ ) las cuales tienen la propiedad de que las distintas ocurrencias de ellas en la palabra ${\textstyle \beta }$ son siempre disjuntas de a pares, y tenemos ademas palabras ${\textstyle \gamma _{1},...,\gamma _{n}}$ . Entonces hablaremos del resultado de reemplazar simultaneamente:

cada ocurrencia de ${\textstyle \alpha _{1}}$ en ${\textstyle \beta }$ , por ${\textstyle \gamma _{1}}$
cada ocurrencia de ${\textstyle \alpha _{2}}$ en ${\textstyle \beta }$ , por ${\textstyle \gamma _{2}}$
${\textstyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots }$
cada ocurrencia de ${\textstyle \alpha _{n}}$ en ${\textstyle \beta }$ , por ${\textstyle \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 ${\textstyle AAbbbBBBBbbAA\%\%CCC\#\#CCC!!!CCC}$ es el resultado de reemplazar simultaneamente:

cada ocurrencia de ${\textstyle \alpha _{1}}$ en ${\textstyle \beta }$ , por ${\textstyle \gamma _{1}}$
cada ocurrencia de ${\textstyle \alpha _{2}}$ en ${\textstyle \beta }$ , por ${\textstyle \gamma _{2}}$
cada ocurrencia de ${\textstyle \alpha _{3}}$ en ${\textstyle \beta }$ , por ${\textstyle \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 ${\textstyle 0}$ y el conjunto ${\textstyle \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 ${\textstyle (a,b)}$ , donde ${\textstyle a}$ y ${\textstyle b}$ son objetos matematicos cualesquiera. Tambien son objetos matematicos y de distinta naturaleza las 3-uplas, las 4-uplas y en general las ${\textstyle n}$ -uplas para ${\textstyle n}$ un numero natural mayor o igual a ${\textstyle 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 ${\textstyle 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 ${\textstyle f}$ de pares ordenados con la siguiente propiedad

Si ${\textstyle (x,y)\in f}$ y ${\textstyle (x,z)\in f}$ , entonces ${\textstyle y=z}$ .

Por ejemplo, si tomamos ${\textstyle f=\{(x,x^{2}):x\in \omega \}}$ se puede ver facilmente que ${\textstyle f}$ cumple la propiedad (F). Dada una funcion ${\textstyle 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 ${\textstyle \mathrm {Dom} (f)}$ y ${\textstyle \operatorname {Im} (f)}$ para denotar, respectivamente, el dominio y la imagen de una funcion ${\textstyle f}$ . Como es usual dado ${\textstyle x\in D_{f}}$ , usaremos ${\textstyle f(x)}$ para denotar al unico ${\textstyle y\in I_{f}}$ tal que ${\textstyle (x,y)\in f}$ . Notese que ${\textstyle \emptyset }$ es una funcion y que ${\textstyle D_{\emptyset }=I_{\emptyset }=\emptyset }$ . Por ejemplo para ${\textstyle f=\{(x,x^{2}):x\in \omega \}}$ se tiene que ${\textstyle D_{f}=\omega }$ y ${\textstyle I_{f}=\{y:y=x^{2}}$ para algun ${\textstyle x\in \omega \}}$ . Ademas notese que ${\textstyle f(x)=x^{2}}$ , para cada ${\textstyle x\in D_{f}}$ .

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

Muchas veces para definir una funcion ${\textstyle f}$ , lo haremos dando su dominio y su regla de asignacion, es decir especificaremos en forma precisa que conjunto es el dominio de ${\textstyle f}$ y ademas especificaremos en forma presisa quien es ${\textstyle f(x)}$ para cada ${\textstyle x}$ de dicho dominio. Obviamente esto determina por completo a la funcion ${\textstyle f}$ ya que ${\textstyle f=\{(x,f(x)):x\in D_{f}\}}$ . Por ejemplo si decimos que ${\textstyle f}$ es la funcion dada por: ${\begin{aligned}D_{f}&=\omega \\f(x)&=23x^{2}\end{aligned}}$ nos estaremos refiriendo a la funcion ${\textstyle \{(x,23x^{2}):x\in \omega \}}$ . Tambien escribiremos ${\begin{array}{rll}f:\omega &\rightarrow &\omega \\x&\rightarrow &23x^{2}\end{array}}$ para describir a ${\textstyle 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 ${\textstyle 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 ${\textstyle 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 ${\textstyle f}$ y ${\textstyle g}$ dos funciones. Ya que las mismas son conjuntos, tendremos que ${\textstyle f}$ sera igual a ${\textstyle g}$ si y solo si para cada par ${\textstyle (a,b)}$ , se tiene que ${\textstyle (a,b)\in f}$ sii ${\textstyle (a,b)\in g}$ . Muchas veces sera util el siguiente criterio de igualdad de funciones:

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

Funcion identidad

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

Composicion de funciones

Dadas funciones ${\textstyle f}$ y ${\textstyle g}$ definamos la funcion ${\textstyle 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 ${\textstyle f\circ g=\{(u,v):}$ existe ${\textstyle z}$ tal que ${\textstyle (u,z)\in g}$ y ${\textstyle (z,v)\in f\}}$ . Notese que ${\textstyle f\circ g\neq \emptyset }$ si y solo si ${\textstyle I_{g}\cap D_{f}\neq \emptyset }$ , lo cual nos dice que muchas veces sucedera que ${\textstyle f\circ g=\emptyset }$

Funciones inyectivas, suryectivas y biyectivas

Una funcion ${\textstyle f}$ es inyectiva cuando no se da que ${\textstyle f(a)=f(b)}$ para algun par de elementos distintos ${\textstyle a,b\in D_{f}}$ . Dada una funcion ${\textstyle f:A\rightarrow B}$ diremos que ${\textstyle f}$ es suryectiva cuando ${\textstyle 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 ${\textstyle f}$ si no decimos respecto de que conjunto de llegada lo es. Muchas veces diremos que una funcion ${\textstyle f}$ es sobre para expresar que es suryectiva.

Dada una funcion ${\textstyle f:A\rightarrow B}$ diremos que ${\textstyle f}$ es biyectiva cuando ${\textstyle f}$ sea inyectiva y suryectiva. Notese que si ${\textstyle f:A\rightarrow B}$ es biyectiva, entonces podemos definir una nueva funcion ${\textstyle 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 ${\textstyle f^{-1}}$ sera llamada la inversa de ${\textstyle f}$ . Notese que ${\textstyle f\circ f^{-1}=Id_{B}}$ y ${\textstyle f^{-1}\circ f=Id_{A}}$ . El siguiente lema muestra que esta ultima propiedad caracteriza la inversa.

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

El nucleo de una funcion

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

Funcion caracteristica de un subconjunto

Sea ${\textstyle X}$ un conjunto cualquiera y sea ${\textstyle S\subseteq X}$ . Usaremos ${\textstyle \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 ${\textstyle \chi _{S}^{X}}$ la funcion caracteristica de ${\textstyle S}$ con respecto a ${\textstyle X}$ . Muchas veces cuando el conjunto ${\textstyle X}$ este fijo y sea claro el contexto, escribiremos ${\textstyle \chi _{S}}$ en lugar de ${\textstyle \chi _{S}^{X}}$ .

Restriccion de una funcion

Dada una funcion ${\textstyle f}$ y un conjunto ${\textstyle S\subseteq D_{f}}$ , usaremos ${\textstyle f|_{S}}$ para denotar la restriccion de ${\textstyle f}$ al conjunto ${\textstyle S}$ , i.e. ${\textstyle f|_{S}=f\cap (S\times I_{f})}$ . Notese que ${\textstyle 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 ${\textstyle f}$ tenemos que ${\textstyle f|_{\emptyset }=\emptyset }$ y ${\textstyle f|_{D_{f}}=f}$ .

Funciones de la forma ${\textstyle [f_{1},...,f_{n}]}$

Dadas funciones ${\textstyle f_{1},...,f_{n}}$ , con ${\textstyle n\geq 2}$ , definamos la funcion ${\textstyle [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 ${\textstyle 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 ${\textstyle [f_{1}]=f_{1}}$ . Es decir que hemos definido para cada sucecion de funciones ${\textstyle f_{1},...,f_{n}}$ , con ${\textstyle n\geq 1}$ , una nueva funcion la cual denotamos con ${\textstyle [f_{1},...,f_{n}]}$ .

Union de funciones con dominios disjuntos

Una observacion interesante es que si ${\textstyle f_{i}:A_{i}\rightarrow B_{i}}$ , ${\textstyle i=1,...,k}$ , son funciones tales que ${\textstyle A_{i}\cap A_{j}=\emptyset }$ para ${\textstyle i\neq j}$ , entonces ${\textstyle 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 ${\textstyle A}$ un conjunto. Por una relacion binaria sobre ${\textstyle A}$ entenderemos un subconjunto de ${\textstyle A^{2}}$ . Algunos ejemplos:

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

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

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

Propiedades notables de relaciones binarias

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

${\textstyle xRx}$ , cualesquiera sea ${\textstyle x\in A}$
${\textstyle xRy}$ y ${\textstyle yRz}$ implica ${\textstyle xRz}$ , cualesquiera sean ${\textstyle x,y,z\in A}$
${\textstyle xRy}$ implica ${\textstyle yRx}$ , cualesquiera sean ${\textstyle x,y\in A}$
${\textstyle xRy}$ y ${\textstyle yRx}$ implica ${\textstyle x=y}$ , cualesquiera sean ${\textstyle x,y\in A}$

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

Ordenes parciales

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

Sea ${\textstyle R=\{(r,t)\in \mathbf {R} ^{2}:r\leq t\}}$ . Entonces ${\textstyle R}$ es un orden parcial sobre ${\textstyle \mathbf {R} }$ , llamado el orden usual de ${\textstyle \mathbf {R} }$
Sea ${\textstyle R=\{(1,2),(1,3),(1,1),(2,2),(3,3)\}}$ . Entonces ${\textstyle R}$ es un orden parcial sobre ${\textstyle \{1,2,3\}}$
Sea ${\textstyle R=\{(S,T)\in {\mathcal {P}}(\omega )^{2}:S\subseteq T\}}$ . Entonces ${\textstyle R}$ es un orden parcial sobre ${\textstyle {\mathcal {P}}(\omega )}$
Sea ${\textstyle R=\{(x,y)\in \omega ^{2}:}$ ${\textstyle x\leq y\}}$ . Entonces ${\textstyle R}$ es un orden parcial sobre ${\textstyle \omega }$ .
Sea ${\textstyle R=\{(1,1)\}}$ . Entonces ${\textstyle R}$ es un orden parcial sobre ${\textstyle \{1\}}$ .
${\textstyle \{(a,b):a=b\}}$ es un orden parcial sobre ${\textstyle A}$ , cualesquira sea el conjunto ${\textstyle A}$
Sea ${\textstyle \mathrm {\leq } =\{(n,m)\in \mathbf {N} ^{2}:n\mid m\}}$ . Es facil ver que ${\textstyle \leq }$ es un orden parcial sobre ${\textstyle \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 ${\textstyle \mathbf {R} }$ (por que?).

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

Usaremos la siguiente

Si hemos denotado con ${\textstyle \leq }$ ${\textstyle \leq }$ a cierto orden parcial sobre un conjunto ${\textstyle A}$ ${\textstyle A}$ , entonces
1. Denotaremos con ${\textstyle <}$ a la relacion binaria ${\textstyle \{(a,b)\in A^{2}:a\leq b}$ y ${\textstyle a\neq b\}}$ . Es decir que ${\textstyle \mathrm {<} =\{(a,b)\in A^{2}:a\leq b}$ y ${\textstyle a\neq b\}}$ . Cuando se de ${\textstyle a<b}$ diremos que ${\textstyle a}$ es menor que ${\textstyle b}$ o que ${\textstyle b}$ es mayor que ${\textstyle a}$ (respecto de ${\textstyle \leq }$ )
2. Denotaremos con ${\textstyle \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 ${\textstyle a\prec b}$ diremos que ${\textstyle a}$ es cubierto por ${\textstyle b}$ o que ${\textstyle b}$ cubre a ${\textstyle a}$ (respecto de ${\textstyle \leq }$ )

Algunos ejemplos:

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

Ordenes totales sobre un conjunto

Sea ${\textstyle A}$ un conjunto cualquiera. Por un orden total sobre ${\textstyle A}$ entenderemos un orden parcial ${\textstyle \leq }$ sobre ${\textstyle A}$ el cual cumpla:

${\textstyle a\leq b}$ o ${\textstyle b\leq a}$ , cualesquiera sean ${\textstyle a,b\in A}$

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

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

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

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

Muchas veces para dar un orden total sobre un conjunto finito ${\textstyle A}$ , daremos simplemente sus elementos en forma creciente ya que esto determina el orden por completo. Por ejemplo si ${\textstyle A=\{1,2,3\}}$ , el orden total dado por ${\textstyle 2<1<3}$ es la relacion ${\textstyle \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 ${\textstyle \leq }$ es un orden total sobre ${\textstyle A}$ y ${\textstyle a,b\in A}$ , diremos que ${\textstyle b}$ es el sucesor de ${\textstyle a}$ cuando se de que ${\textstyle a<b}$ y ${\textstyle b\leq c}$ , para cada ${\textstyle c\in A}$ tal que ${\textstyle a<c}$ , i.e., ${\textstyle b}$ es el menor elemento del conjunto ${\textstyle \{c\in A:}$ tal que ${\textstyle a<c\}}$ . No siempre existe el sucesor de un elemento. Por ejemplo si ${\textstyle \leq }$ es el orden usual de ${\textstyle \mathbf {R} }$ , entonces ningun elemento tiene sucesor (justifique).

Diagramas de Hasse

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

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

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

Ejemplos:

Relaciones de equivalencia

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

${\textstyle xRx}$ , cualesquiera sea ${\textstyle x\in A}$
${\textstyle xRy}$ y ${\textstyle yRz}$ implica ${\textstyle xRz}$ , cualesquiera sean ${\textstyle x,y,z\in A}$
${\textstyle xRy}$ implica ${\textstyle yRx}$ , cualesquiera sean ${\textstyle x,y\in A}$

Algunos ejemplos:

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

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

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

Algunas propiedades basicas son:

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

' ${\textstyle a\in a/R}$ '
' ${\textstyle aRb}$ si y solo si ${\textstyle a/R=b/R}$ . Es decir que ${\textstyle b\in a/R}$ implica ${\textstyle b/R=a/R}$ '
' ${\textstyle a/R\cap b/R=\emptyset }$ o ${\textstyle a/R=b/R}$ '

Proof. (1) es muy facil.

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

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

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

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

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

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

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

Definicion de funciones con dominio ${\textstyle A/R}$

Supongamos ${\textstyle R}$ es una relacion de equivalencia sobre ${\textstyle \mathbf {R} }$ y supongamos definimos una funcion ${\textstyle 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 ${\textstyle R}$ es tal que ${\textstyle 2R6}$ . Entonces tendriamos que ${\textstyle 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 ${\textstyle 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 ${\textstyle f}$ debe valer 4 y si usamos el 6 la ecuacion nos dice que ${\textstyle 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 ${\textstyle f:\mathbf {Z} /R\rightarrow \mathbf {R} }$ de la siguiente manera: $f(n/R)=1/(n^{2}+1)$ Como ya vimos ${\textstyle \mathbf {Z} /R=\{\{t\in \mathbf {Z} :t}$ es par ${\textstyle \},\{t\in \mathbf {Z} :t}$ es impar ${\textstyle \}\}}$ , por lo cual facilmente se puede llegar a que la ecuacion ${\textstyle 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 ${\textstyle f:A\rightarrow B}$ es sobre, entonces la ecuacion ${\textstyle {\bar {f}}(a/\ker f)=f(a)}$ define en forma inhambigua una funcion ${\textstyle {\bar {f}}:A/\ker f\rightarrow B}$ la cual es biyectiva.'

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

Correspondencia entre relaciones de equivalencia y particiones

Dado un conjunto ${\textstyle A}$ por una particion de ${\textstyle A}$ entenderemos un conjunto ${\textstyle {\mathcal {P}}}$ tal que:

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

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

Si ${\textstyle A=\{1,2,3,4,5\}}$ , entonces ${\mathcal {P}}=\{\{1,5\},\{2,3\},\{4\}\}$

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

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

Dada una particion ${\textstyle {\mathcal {P}}}$ de un conjunto ${\textstyle A}$ podemos definir una relacion binaria asociada a ${\textstyle {\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 ${\textstyle A}$ un conjunto cualquiera. Entonces:'

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

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

(2). Sigue facilmente del Lema 3.

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

Theorem 7. 'Sea ${\textstyle 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:

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

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

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

El teorema anterior muestra que a nivel de informacion es lo mismo tener una relacion de equivalencia sobre ${\textstyle A}$ que tener una particion de ${\textstyle 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 ${\textstyle \{1,2,3,4,5\}}$ dada por la particion ${\mathcal {P}}=\{\{1,5\},\{4\},\{2,3\}\}$ nos estaremos refiriendo a ${\textstyle 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 ${\textstyle n}$ -arias sobre un conjunto

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

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

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

Relaciones ${\textstyle n}$ -arias sobre un conjunto

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

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

Funciones ${\textstyle \Sigma }$ -mixtas

Sea ${\textstyle \Sigma }$ un alfabeto finito. Dados ${\textstyle n,m\in \omega }$ , usaremos ${\textstyle \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, ${\textstyle \omega ^{3}\times \Sigma ^{\ast 4}}$ sera una forma abreviada de escribir ${\textstyle \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, ${\textstyle \omega ^{3}\times \Sigma ^{\ast 4}}$ denota un conjunto de pares y ${\textstyle \omega \times \omega \times \omega \times \Sigma ^{\ast }\times \Sigma ^{\ast }\times \Sigma ^{\ast }\times \Sigma ^{\ast }}$ es un conjunto de ${\textstyle 7}$ -uplas.

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

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

Definicion de funcion ${\textstyle \Sigma }$ -mixta

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

Existen ${\textstyle n,m\geq 0}$ , tales que ${\textstyle D_{f}\subseteq \omega ^{n}\times \Sigma ^{\ast m}}$
Ya sea ${\textstyle I_{f}\subseteq \omega }$ o ${\textstyle I_{f}\subseteq \Sigma ^{\ast }}$

Algunos ejemplos:

Sea ${\textstyle \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 ${\textstyle \Sigma }$ -mixta ya que se cumple (M1) con ${\textstyle n=m=1}$ y (M2). Notese que ${\textstyle f}$ no es ${\textstyle \{\square ,\%\}}$ -mixta ya que no cumple (M1) respecto del alfabeto ${\textstyle \{\square ,\%\}}$ . Sin envargo note que ${\textstyle f}$ es Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikibooks.org/v1/":): {\textstyle \{\square,\%,\blacktriangle,@\}} -mixta
La funcion ${\begin{array}{rll}\omega ^{4}&\rightarrow &\omega \\(x,y,z,w)&\rightarrow &x+y\end{array}}$ es ${\textstyle \Sigma }$ -mixta cualesquiera sea el alfabeto ${\textstyle \Sigma }$
Sea Failed to parse (syntax error): {\textstyle \Sigma=\{\square,@\}} . La funcion Failed to parse (unknown function "\begin{array}"): {\displaystyle \begin{array}{rll} \{\square\square\square,@@\} & \rightarrow & \omega\\ \alpha & \rightarrow & \left\vert \alpha\right\vert \end{array}}

es ${\textstyle \Sigma }$ -mixta ya que se cumple (M1) (con ${\textstyle n=0}$ y ${\textstyle m=1}$ ) y (M2)
Supongamos ${\textstyle \Sigma =\emptyset }$ . Tenemos entonces que ${\textstyle \Sigma ^{\ast }=\{\varepsilon \}}$ . Por ejemplo ${\begin{array}{rll}D&\rightarrow &\omega \\(x,\varepsilon ,\varepsilon ,\varepsilon )&\rightarrow &x^{2}\end{array}}$ donde ${\textstyle D=\{(x,\varepsilon ,\varepsilon ,\varepsilon ):x}$ es impar ${\textstyle \}}$ , es ${\textstyle \Sigma }$ -mixta (con ${\textstyle n=1}$ y ${\textstyle m=3}$ en (M1)). Tambien notese que ${\begin{array}{rll}\{(\varepsilon ,\varepsilon )\}&\rightarrow &\{\varepsilon \}\\(\varepsilon ,\varepsilon )&\rightarrow &\varepsilon \end{array}}$ es ${\textstyle \Sigma }$ -mixta.

Dejamos al lector la facil prueba del siguiente resultado basico.

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

Una funcion ${\textstyle \Sigma }$ -mixta ${\textstyle f}$ es ${\textstyle \Sigma }$ -total cuando haya ${\textstyle n,m\in \omega }$ tales que ${\textstyle D_{f}=\omega ^{n}\times \Sigma ^{\ast m}}$ . El lema anterior nos dice que si ${\textstyle \Sigma \subseteq \Gamma }$ , entonces toda funcion ${\textstyle \Sigma }$ -mixta es ${\textstyle \Gamma }$ -mixta. Sin envargo una funcion puede ser ${\textstyle \Sigma }$ -total y no ser ${\textstyle \Gamma }$ -total, cuando ${\textstyle \Sigma \subseteq \Gamma }$ . Por ejemplo tomemos ${\textstyle \Sigma =\{\square ,\%,\blacktriangle \}}$ y ${\textstyle \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 ${\textstyle f}$ es ${\textstyle \Sigma }$ -mixta y ${\textstyle \Sigma }$ -total. Tambien es ${\textstyle \Gamma }$ -mixta ya que ${\textstyle D_{f}\subseteq \omega \times \Gamma ^{\ast }}$ y ${\textstyle I_{f}\subseteq \omega }$ , por lo cual cumple (M1) y (M2). Sin envargo ${\textstyle f}$ no es ${\textstyle \Gamma }$ -total ya que ${\textstyle D_{f}}$ no es igual a ${\textstyle \omega ^{n}\times \Gamma ^{\ast m}}$ , cualesquiera sean ${\textstyle n}$ y ${\textstyle m}$ .

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

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

Funciones ${\textstyle Suc}$ y ${\textstyle 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}}$

Las funciones ${\textstyle d_{a}}$

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

Las funciones ${\textstyle p_{i}^{n,m}}$

Sea ${\textstyle \Sigma }$ un alfabeto. Para ${\textstyle n,m,i\in \omega }$ tales que ${\textstyle 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 ${\textstyle n,m,i\in \omega }$ tales que ${\textstyle 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 ${\textstyle p_{i}^{n,m}}$ son llamadas proyecciones. La funcion ${\textstyle p_{i}^{n,m}}$ es llamada la proyeccion ${\textstyle n,m,i}$ , respecto del alfabeto ${\textstyle \Sigma }$ . Notese que esta definicion requiere que ${\textstyle n+m\geq 1}$ ya que ${\textstyle i}$ debe cumplir ${\textstyle 1\leq i\leq n+m}$ .

Las funciones ${\textstyle C_{k}^{n,m}}$ y ${\textstyle C_{\alpha }^{n,m}}$

Sea ${\textstyle \Sigma }$ un alfabeto. Para ${\textstyle n,m,k\in \omega }$ , y ${\textstyle \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 ${\textstyle C_{k}^{0,0}:\{\Diamond \}\rightarrow \{k\}}$ y que ${\textstyle C_{\alpha }^{0,0}:\{\Diamond \}\rightarrow \{\alpha \}}$ .

La funcion ${\textstyle pr}$

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

El tipo de una funcion mixta

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

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

Funciones con imagen contenida en ${\textstyle \omega ^{n}\times \Sigma ^{\ast m}}$

Supongamos que ${\textstyle k,l,n,m\in \omega }$ y que ${\textstyle F:D_{F}\subseteq \omega ^{k}\times \Sigma ^{\ast l}\rightarrow \omega ^{n}\times \Sigma ^{\ast m}}$ . Supongamos ademas que ${\textstyle n+m\geq 1}$ . Entonces denotaremos con ${\textstyle F_{(i)}}$ a la funcion ${\textstyle 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 ${\textstyle F_{(i)}}$ son ${\textstyle \Sigma }$ -mixtas. Ademas notese que $F=[F_{(1)},...,F_{(n+m)}]$

Predicados ${\textstyle \Sigma }$ -mixtos

Un predicado ${\textstyle \Sigma }$ -mixto es una funcion ${\textstyle f}$ la cual es ${\textstyle \Sigma }$ -mixta y ademas cumple que ${\textstyle 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 ${\textstyle P:S\subseteq \omega ^{n}\times \Sigma ^{\ast m}\rightarrow \{0,1\}}$ y ${\textstyle Q:S\subseteq \omega ^{n}\times \Sigma ^{\ast m}\rightarrow \{0,1\}}$ , con el mismo dominio, definamos nuevos predicados ${\textstyle (P\vee Q)}$ , ${\textstyle (P\wedge Q)}$ y ${\textstyle \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 ${\textstyle \Sigma }$ -indexadas de funciones

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

Sea ${\textstyle {\mathcal {G}}}$ dada por ${\begin{array}{rcl}{\mathcal {G}}:\{\square ,\%,\blacktriangle \}&\rightarrow &\{Suc,Pred\}\\\square &\rightarrow &Suc\\\%&\rightarrow &Suc\\\blacktriangle &\rightarrow &Pred\end{array}}$ Claramente ${\textstyle {\mathcal {G}}}$ es una familia ${\textstyle \{\square ,\%,\blacktriangle \}}$ -indexada de funciones. Notar que ${\mathcal {G}}=\{(\square ,Suc),(\%,Suc),(\blacktriangle ,Pred)\}$ Se tiene tambien por ejemplo que ${\textstyle {\mathcal {G}}(\%)=Suc}$ por lo cual tambien es cierto que ${\textstyle {\mathcal {G}}(\%)(22)=23}$ , etc.
Si ${\textstyle \Sigma }$ es un alfabeto no vacio, la funcion ${\begin{array}{rcl}{\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 ${\textstyle \Sigma }$ -indexada de funciones. Notar que ${\mathcal {G}}=\{(a,d_{a}):a\in \Sigma \}$
${\textstyle \emptyset }$ es una flia ${\textstyle \emptyset }$ -indexada de funciones

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

Conjuntos ${\textstyle \Sigma }$ -mixtos

Un conjunto ${\textstyle S}$ es llamado ${\textstyle \Sigma }$ -mixto si hay ${\textstyle n,m\in \omega }$ tales que ${\textstyle 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 ${\textstyle \{\blacktriangle ,\%,!\}}$ -mixtos. Tambien notese que ${\textstyle \emptyset }$ y ${\textstyle \{\Diamond \}}$ son conjuntos ${\textstyle \Sigma }$ -mixtos, cualesquiera sea el alfabeto ${\textstyle \Sigma }$ . Por ultimo el conjunto $\{(x,\varepsilon ,\varepsilon ,\varepsilon ):x\in \omega {\text{ y }}x{\text{ es impar}}\}$ es ${\textstyle \emptyset }$ -mixto (con ${\textstyle n=1}$ y ${\textstyle m=3}$ ).

El tipo de un conjunto mixto

Dado un conjunto ${\textstyle \Sigma }$ -mixto ${\textstyle S}$ , si ${\textstyle n,m\in \omega }$ son tales que ${\textstyle S\subseteq \omega ^{n}\times \Sigma ^{\ast m}}$ , entonces diremos que ${\textstyle S}$ es un conjunto de tipo ${\textstyle (n,m)}$ . Notese que si ${\textstyle S\neq \emptyset }$ , entonces hay unicos ${\textstyle n,m\in \omega }$ tales que ${\textstyle S}$ es un conjunto de tipo ${\textstyle (n,m)}$ . De esta forma, cuando ${\textstyle S\neq \emptyset }$ hablaremos de "el tipo de ${\textstyle S}$ " para refererirnos a este unico par ${\textstyle (n,m)}$ . Tambien es importante notar que de la definicion anterior sale inmediatemante que ${\textstyle \emptyset }$ es un conjunto de tipo ${\textstyle (n,m)}$ cualesquiera sean ${\textstyle 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 ${\textstyle \omega }$ es de tipo ${\textstyle (1,0)}$ y ${\textstyle \Sigma ^{\ast }}$ es de tipo ${\textstyle (0,1)}$ .

Conjuntos rectangulares

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

Failed to parse (syntax error): {\textstyle \mathbf{N}\times\{1,2\}\times\{@@,\varepsilon\}} es rectangular (aqui ${\textstyle n=2}$ y ${\textstyle m=1}$ )
Failed to parse (syntax error): {\textstyle \{!!!,!!\}\times\{@@,\varepsilon\}} es rectangular (aqui ${\textstyle n=0}$ y ${\textstyle m=2}$ )

Tambien notese que ${\textstyle \emptyset =\emptyset \times \emptyset }$ por lo cual ${\textstyle \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 ${\textstyle S\subseteq \omega \times \Sigma ^{\ast }}$ . Entonces ${\textstyle S}$ es rectangular si y solo si se cumple la siguiente propiedad:'

'Si ${\textstyle (x,\alpha ),(y,\beta )\in S}$ , entonces ${\textstyle (x,\beta )\in S}$ '

Proof. Ejercicio.

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

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

Dejamos como ejercicio para el lector enunciar un lema analogo al anterior pero que caracterice cuando ${\textstyle S\subseteq \omega ^{2}\times \Sigma ^{\ast 3}}$ 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

Solo utilizaremos expresiones que involucran variables numericas, las cuales se valuaran en numeros de ${\textstyle \omega }$ , y variables alfabeticas, las cuales se valuaran en palabras del alfabeto previamente fijado. Las variables numericas seran seleccionadas de la lista ${\begin{aligned}&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}}$
Por ejemplo la expresion: $x+y+1$ tiene dos variables numericas ${\textstyle x}$ e ${\textstyle y}$ (y ninguna alfabetica). Si le asignamos a ${\textstyle x}$ el valor 2 y a ${\textstyle y}$ el valor 45, entonces la expresion ${\textstyle x+y+1}$ produce o representa el valor ${\textstyle 48=2+45+1}$ .
Otro ejemplo, consideremos la expresion $\left\vert \alpha \beta \right\vert +\left\vert \alpha \right\vert ^{x}$ la cual tiene una variable numerica ${\textstyle x}$ y dos variables alfabeticas ${\textstyle \alpha }$ y ${\textstyle \beta }$ . Supongamos ademas que el alfabeto previamente fijado es Failed to parse (syntax error): {\textstyle \{@,\%\}} . Si le asignamos a ${\textstyle x}$ el valor 2, a ${\textstyle \alpha }$ el valor Failed to parse (syntax error): {\textstyle @@} y a ${\textstyle \beta }$ el valor ${\textstyle \%\%\%}$ , entonces la expresion ${\textstyle \left\vert \alpha \beta \right\vert +\left\vert \alpha \right\vert ^{x}}$ produce o representa el valor Failed to parse (syntax error): {\textstyle \left\vert @@\%\%\%\right\vert +\left\vert @@\right\vert ^{2}=9} .
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 ${\textstyle \alpha }$ es ${\textstyle \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 ${\textstyle y}$ sea igual a la longitud del valor asignado a ${\textstyle \alpha }$ .
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, ${\textstyle y}$ , una variable alfabetica, ${\textstyle \beta }$ , y una vez valuadas estas variables produce un valor alfabetico, a saber el resultado de elevar el valor asignado a la variable ${\textstyle \beta }$ , a el valor asignado a ${\textstyle y}$ .
Una expresion ${\textstyle E}$ ${\textstyle E}$ para poder ser utilizada en la notacion lambda relativa a un alfabeto ${\textstyle \Sigma }$ ${\textstyle \Sigma }$ debera cumplir alguna de las dos siguientes propiedades
1. los valores que asuma ${\textstyle E}$ cuando hayan sido asignados valores de ${\textstyle \omega }$ a sus variables numericas y valores de ${\textstyle \Sigma ^{\ast }}$ a sus variables alfabeticas deberan ser siempre elementos de ${\textstyle \omega }$
2. los valores que asuma ${\textstyle E}$ cuando hayan sido asignados valores de ${\textstyle \omega }$ a sus variables numericas y valores de ${\textstyle \Sigma ^{\ast }}$ a sus variables alfabeticas deberan ser siempre elementos de ${\textstyle \Sigma ^{\ast }}$ .
Por ejemplo la expresion $x/2$ no cumple la propiedad dada en (6) ya que para ciertos valores de ${\textstyle \omega }$ asignados a la variable ${\textstyle x}$ , la expresion da valores numericos que se salen de ${\textstyle \omega }$ por lo cual no cumple ni (a) ni (b).
Otro ejemplo, si el alfabeto fijado es Failed to parse (syntax error): {\textstyle \Sigma=\{@,\%\}} , entonces la expresion Failed to parse (syntax error): {\displaystyle @^{x}\$^{y}} no cumple la propiedad dada en (6) ya que por ejemplo cuando le asignamos a ${\textstyle x}$ el valor 2 y a ${\textstyle y}$ el valor 6, la expresion nos da la palabra Failed to parse (syntax error): {\textstyle @@\$\$\$\$\$\$} la cual no pertenece a ${\textstyle \Sigma ^{\ast }}$ por lo cual no cumple ni (a) ni (b).
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 ${\textstyle \omega }$ asignado a la variable ${\textstyle x}$ produce o representa un valor concreto de ${\textstyle \omega }$ . Otro ejemplo: $\mathrm {el\ tercer\ simbolo\ de\ } \alpha$ notese que esta expresion, una ves fijado un alfabeto ${\textstyle \Sigma }$ , estara definida o producira un valor solo cuando le asignamos a ${\textstyle \alpha }$ una palabra de ${\textstyle \Sigma ^{\ast }}$ de longitud mayor o igual a ${\textstyle 3}$ .
Expresiones Booleanas. A las expresiones Booleanas tales como $x=y+1{\text{ y }}\left\vert \alpha \right\vert \leq 22$

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

La expresion $5$ no tiene variables por lo cual pensaremos que siempre produce el valor ${\textstyle 5}$ cualesquiera sean los valores asignados a las variables.

Expresiones lambdificables con respecto a ${\textstyle \Sigma }$

Dado un alfabeto ${\textstyle \Sigma }$ a las expresiones que cumplan las caracteristicas dadas anteriormente las llamaremos lambdificables con respecto a ${\textstyle \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:

${\textstyle x/2}$ no es lambdificable con respecto a ${\textstyle \Sigma }$ cualesquiera sea ${\textstyle \Sigma }$
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikibooks.org/v1/":): {\textstyle @^{x}\$^{y}} es lambdificable con respecto a Failed to parse (syntax error): {\textstyle \{@,\$\}} y no es lambdificable con respecto a Failed to parse (syntax error): {\textstyle \{@,\#,\%\}}
${\textstyle x=y+1}$ es lambdificable con respecto a ${\textstyle \Sigma }$ cualesquiera sea ${\textstyle \Sigma }$
la expresion $\mathrm {el\ menor\ numero\ primo\ que\ es\ mayor\ que\ } x^{\left\vert \beta \right\vert }$ es lambdificable con respecto a ${\textstyle \Sigma }$ cualesquiera sea ${\textstyle \Sigma }$
la expresion $5$ es lambdificable con respecto a ${\textstyle \Sigma }$ cualesquiera sea ${\textstyle \Sigma }$

Definicion de ${\textstyle \lambda x_{1}...x_{n}\alpha _{1}...\alpha _{m}\left[E\right]}$

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

El dominio de ${\textstyle \lambda x_{1}...x_{n}\alpha _{1}...\alpha _{m}\left[E\right]}$ es el conjunto de las ${\textstyle (n+m)}$ -uplas ${\textstyle (k_{1},...,k_{n},\beta _{1},...,\beta _{m})\in \omega ^{n}\times \Sigma ^{\ast m}}$ tales que ${\textstyle E}$ esta definida cuando le asignamos a cada ${\textstyle x_{i}}$ el valor ${\textstyle k_{i}}$ y a cada ${\textstyle \alpha _{i}}$ el valor ${\textstyle \beta _{i}}$ .
${\textstyle \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 ${\textstyle E}$ cuando le asignamos a cada ${\textstyle x_{i}}$ el valor ${\textstyle k_{i}}$ y a cada ${\textstyle \alpha _{i}}$ el valor ${\textstyle \beta _{i}}$ .

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

Supongamos fijamos el alfabeto Failed to parse (syntax error): {\textstyle \Sigma=\{@,?,} ${\textstyle \}}$ . Entonces ${\textstyle \lambda x\alpha \left[\alpha ^{2x}\right]}$ es la funcion Failed to parse (unknown function "\begin{array}"): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikibooks.org/v1/":): {\textstyle \Sigma=\{@,?,} ${\textstyle \}}$ hubieramos fijado ${\textstyle \Sigma =\{\%\}}$ , entonces ${\textstyle \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}}$
Supongamos fijamos el alfabeto Failed to parse (syntax error): {\textstyle \Sigma=\{@,?,} ${\textstyle \}}$ . Entonces ${\textstyle \lambda x\alpha \left[5\right]}$ es la funcion Failed to parse (unknown function "\begin{array}"): {\displaystyle \begin{array}{rll} \omega\times\{@,?,\text{\A1}\}^{\ast} & \rightarrow & \omega\\ (x,y,z,\alpha) & \rightarrow & 5 \end{array}}
Supongamos fijamos el alfabeto ${\textstyle \Sigma =\{\%,!\}}$ . Entonces ${\textstyle \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 ${\textstyle \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 ${\textstyle \lambda \alpha \beta \left[\alpha \beta \right](\%,!)=\%!}$ y ${\textstyle \lambda \beta \alpha \left[\alpha \beta \right](\%,!)=!\%}$
Independientemente de quien sea ${\textstyle \Sigma }$ el alfabeto previamente fijado, tenemos que ${\textstyle \lambda xy[x+y]}$ es la funcion ${\begin{array}{rll}\omega ^{2}&\rightarrow &\omega \\(x,y)&\rightarrow &x+y\end{array}}$ Tambien ${\textstyle \lambda xyzw[x+w]}$ es la funcion ${\begin{array}{rll}\omega ^{4}&\rightarrow &\omega \\(x,y,z,w)&\rightarrow &x+w\end{array}}$
Supongamos fijamos el alfabeto Failed to parse (syntax error): {\textstyle \Sigma=\{@,?,} ${\textstyle \}}$ . Entonces por la clausula (L1) tenemos que el dominio de la funcion ${\textstyle \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 ^{\ast 2}:\left\vert \alpha \right\vert \geq 1{\text{ y }}y\geq 1\right\}$ Es decir que ${\textstyle \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}}$
Atentos a (10) de mas arriba, la funcion ${\textstyle \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 ${\textstyle \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 ${\textstyle \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}}$
Notar que para ${\textstyle S\subseteq \omega ^{n}\times \Sigma ^{\ast m}}$ se tiene que ${\textstyle \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]}$
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 ${\textstyle \lambda }$ no tenga variables alfabeticas, la funcion representada no depende del alfabeto

Un par de ejemplos sutiles

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

Ordenes naturales sobre ${\textstyle \Sigma ^{\ast }}$

En esta seccion daremos biyecciones naturales entre ${\textstyle \Sigma ^{\ast }}$ y ${\textstyle \omega }$ , para cada alfabeto no vacio ${\textstyle \Sigma }$ . Dichas biyecciones dependen de tener asociado a ${\textstyle \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 ${\textstyle \omega }$ .

Notacion decimal sin ${\textstyle 0}$

Llamaremos numerales a los siguientes simbolos $0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9$ Usaremos ${\textstyle Num}$ para denotar el conjunto de numerales. Notese que ${\textstyle 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 ${\textstyle Num^{\ast }}$ denotan (notacion decimal) a los numeros de ${\textstyle \omega }$ pero debemos tener en cuenta que ${\textstyle Num^{\ast }\cap \omega =\emptyset }$ . Cuando tratamos con palabras de ${\textstyle 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 ${\textstyle 45}$ puede estar denotando al numero entero cuarenta y cinco o tambien ${\textstyle 45}$ puede estar denotando la palabra de longitud ${\textstyle 2}$ cuyo primer simbolo es el numeral ${\textstyle 4}$ y cuyo segundo simbolo es el numeral ${\textstyle 5}$ , es decir ella misma. Por dar otro ejemplo, el simbolo ${\textstyle 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 ${\textstyle Num}$ , denotan, de menor a mayor, a los numeros de ${\textstyle \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 ${\textstyle 0}$ .

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

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

Failed to parse (unknown function "\bigskip"): {\textstyle \bigskip}

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

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

${\textstyle 111,112,...,11d,121,122,...,12d,...}$

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

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

Notese que

El numero ${\textstyle 0}$ es representado en la lista anterior con la palabra ${\textstyle \varepsilon }$
El numero ${\textstyle 1}$ es representado en la lista anterior con la palabra ${\textstyle 1}$

${\textstyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots }$
El numero ${\textstyle 9}$ es representado en la lista anterior con la palabra ${\textstyle 9}$
El numero ${\textstyle 10}$ es representado en la lista anterior con la palabra ${\textstyle d}$
El numero ${\textstyle 11}$ es representado en la lista anterior con la palabra ${\textstyle 11}$

${\textstyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots }$
El numero ${\textstyle 19}$ es representado en la lista anterior con la palabra ${\textstyle 19}$
El numero ${\textstyle 20}$ es representado en la lista anterior con la palabra ${\textstyle 1d}$
El numero ${\textstyle 21}$ es representado en la lista anterior con la palabra ${\textstyle 21}$
El numero ${\textstyle 22}$ es representado en la lista anterior con la palabra ${\textstyle 22}$

${\textstyle \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots }$

Como puede notarse en estos primeros veinte y pico numeros solo dos (el ${\textstyle 0}$ y el ${\textstyle 20}$ ) se representan en forma distinta a la reprentacion decimal clasica. Es natural que ${\textstyle \varepsilon }$ denote al numero ${\textstyle 0}$ y ademas notese que la palabra ${\textstyle 1d}$ (que en la lista representa el ${\textstyle 20}$ ) puede leerse como "diecidiez" (es decir la palabra que sigue a "diecinueve") que justamente es ${\textstyle 20}$ . Por supuesto con esta manera de pensar la palabra ${\textstyle 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 ${\textstyle 6d}$ deberiamos leerla como "sesentidiez" y es natural ya que en la lista representa al setenta. Tambien, la palabra ${\textstyle 9d}$ puede leerse noventidiez ya que representa en la lista al numero ${\textstyle 100}$ .

La lista anterior va representando los numeros de ${\textstyle \omega }$ en forma muy natural pero aunque nuestra intuicion nos diga que no, en principio podria pasar que una misma palabra del alfabeto ${\textstyle {\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 ${\textstyle {\widetilde {Num}}}$ la cual nunca figure en la lista. Mas abajo probaremos que estas dos posibilidades no suceden, es decir muestran que

Toda palabra de ${\textstyle {\widetilde {Num}}^{\ast }}$ aparece en la lista
Ninguna palabra de ${\textstyle {\widetilde {Num}}^{\ast }}$ aparece mas de una ves

Notese que la propiedad (S) nos dice que la funcion ${\begin{array}{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 ${\textstyle \omega }$ y ${\textstyle {\widetilde {Num}}^{\ast }}$ .

Por supuesto, la pregunta que inmediatamente surge es como calcular la inversa de ${\textstyle \ast }$ . Llamemos ${\textstyle \#}$ a la inversa de ${\textstyle \ast }$ . Notese que dada una palabra ${\textstyle \alpha \in {\widetilde {Num}}^{\ast }}$ , el numero ${\textstyle \#(\alpha )}$ es justamente el numero representado por la palabra ${\textstyle \alpha }$ , o dicho de otra forma ${\textstyle \#(\alpha )}$ es la posicion que ocupa ${\textstyle \alpha }$ en la lista, contando desde el ${\textstyle 0}$ (es decir ${\textstyle \alpha }$ es la ${\textstyle (\#(\alpha )+1)}$ -esima palabra de la lista). Por ejemplo: Failed to parse (unknown function "\begin{gathered}"): {\displaystyle \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 ${\textstyle 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 ${\textstyle \#(\alpha )}$ se expresa como una suma de potencias de ${\textstyle 10}$ , con los coeficientes dados en funcion de los simbolos de ${\textstyle \alpha }$ . Mas concretamente si ${\textstyle \alpha =s_{1}s_{2}...s_{k}}$ con ${\textstyle k\geq 1}$ y ${\textstyle 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 ${\textstyle \#}$ 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 ${\textstyle {\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 ${\textstyle {\widetilde {Num}}}$ describiendo su suma de potencias asociada. Por ejemplo podriamos llamar "decenta" al numero ${\textstyle 100}$ , por analogia a "treinta", "cuarenta",...,"noventa". O sea una decenta es diez veces diez. De esta forma la palabra ${\textstyle d1}$ se leera "decenta y uno" y esto es natural ya que en la lista representa al ${\textstyle 101}$ . La palabra ${\textstyle dd}$ se leera "decenta y diez" y esto describe a la perfeccion el numero que representa, i.e. el ${\textstyle 10.10+10=110}$ . La palabra que sigue en la lista a ${\textstyle dd}$ es ${\textstyle 111}$ la cual representa al ${\textstyle 111}$ , es decir aqui como en los otros casos vistos en los cuales no hay ocurrencias del simbolo ${\textstyle d}$ la palabra representa al mismo numero que representa en la notacion decimal clasica. Por dar otro ejemplo, la palabra ${\textstyle 59d3}$ se leera "cinco mil novecientos decenta y tres" y representara al numero ${\textstyle 6003}$ .

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

Prueba de las propiedades (S) e (I)

Dado que el siguiente a un elemento ${\textstyle \alpha }$ de la lista es de la misma longitud que ${\textstyle \alpha }$ o tiene longitud igual a ${\textstyle \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 ${\textstyle B_{n}}$ es, por definicion, la parte de la lista en la cual las palabras tienen longitud exactamente ${\textstyle n}$ . Por ejemplo:

${\textstyle B_{0}}$ es ${\textstyle \varepsilon }$
${\textstyle B_{1}}$ es ${\textstyle 1,2,3,4,5,6,7,8,9,d}$
${\textstyle B_{2}}$ es ${\textstyle 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 ${\textstyle n}$ se de que ${\textstyle B_{n}}$ sea una lista infinita, lo cual ademas nos diria que los bloques ${\textstyle B_{n+1},B_{n+2},...}$ son todos vacios. Es decir podria pasar que la lista se estanque en una longitud ${\textstyle n}$ y nunca aparezca una palabra de longitud mayor que ${\textstyle n}$ . Esto por supuesto obligaria a que se repitan muchas veces palabras de dicha longitud ${\textstyle n}$ ya que hay una cantidad finita de las mismas ( ${\textstyle 10^{n}}$ ).

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

Si ${\textstyle B_{n}=\alpha _{1},...,\alpha _{k}}$ , entonces ${\textstyle \alpha _{1}=1^{n}}$ y ${\textstyle \alpha _{k}=d^{n}}$
Si ${\textstyle d^{n}}$ ocurre en ${\textstyle 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

Si ${\textstyle B_{n}=\alpha _{1},...,\alpha _{k}}$ , entonces ${\textstyle 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 ${\textstyle \sigma \in {\widetilde {Num}}}$ y supongamos ${\textstyle \alpha \in {\widetilde {Num}}^{\ast }}$ no es de la forma ${\textstyle d^{n}}$ . Entonces el siguiente a ${\textstyle \sigma \alpha }$ es ${\textstyle \sigma \beta }$ donde ${\textstyle \beta }$ es el siguiente a ${\textstyle \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

${\textstyle B_{n}}$ es una lista sin repeticiones de todas las palabras de longitud ${\textstyle n}$

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

El caso general

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

Failed to parse (unknown function "\small"): {\textstyle {\small\varepsilon,a}_{1}{\small,a}_{2}{\small,...,a}_{n}{\small,}}

Failed to parse (unknown function "\small"): {\textstyle {\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,}}

Failed to parse (unknown function "\small"): {\textstyle {\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,}}

Failed to parse (unknown function "\small"): {\textstyle {\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,}}

Failed to parse (unknown function "\small"): {\textstyle {\small\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\vdots}

Failed to parse (unknown function "\small"): {\textstyle {\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,}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikibooks.org/v1/":): {\textstyle {\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 ${\textstyle \Sigma ^{\ast }}$ , i.e. produce naturalmente una biyeccion entre ${\textstyle \omega }$ y ${\textstyle \Sigma ^{\ast }}$ . Pero antes debemos definir mas formalmente la lista. Para esto definamos ${\textstyle s^{\leq }:\Sigma ^{\ast }\rightarrow \Sigma ^{\ast }}$ de la siguiente manera

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

Notese que la definicion de ${\textstyle s^{\leq }}$ es correcta ya que una palabra de ${\textstyle \Sigma ^{\ast }}$ ya sea es de la forma ${\textstyle (a_{n})^{m}}$ , con ${\textstyle m\geq 0}$ , o es de la forma ${\textstyle \alpha a_{i}(a_{n})^{m}}$ , con ${\textstyle \alpha \in \Sigma ^{\ast }}$ , ${\textstyle 1\leq i<n}$ y ${\textstyle m\geq 0}$ ; 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 ${\textstyle \Sigma ={\widetilde {Num}}}$ que:

Toda palabra de ${\textstyle \Sigma ^{\ast }}$ aparece en la lista
Ninguna palabra de ${\textstyle \Sigma ^{\ast }}$ aparece mas de una ves en la lista

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

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

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

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

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

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

Ahora podemos definir la funcion ${\textstyle \#^{\leq }}$ de la siguiente manera ${\begin{array}{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 ${\textstyle \#^{\leq }}$ es la inversa de ${\textstyle \ast ^{\leq }}$ '

Proof. Primero probaremos por induccion en ${\textstyle x}$ que

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

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

Caso ${\textstyle i_{0}<n}$ . Entonces ${\textstyle \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 ${\textstyle i_{k}=i_{k-1}=...=i_{0}=n}$ . Entonces ${\textstyle \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 ${\textstyle i_{0}=i_{1}=...=i_{h}=n}$ , ${\textstyle \;i_{h+1}\not =n}$ , para algun ${\textstyle 0\leq h<k}$ . Entonces ${\textstyle \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 ${\textstyle \ast ^{\leq }}$ es la funcion con dominio ${\textstyle \Sigma ^{\ast }}$ que a una palabra ${\textstyle \alpha }$ le asocia el unico ${\textstyle x\in \omega }$ tal que ${\textstyle \ast ^{\leq }(x)=\alpha }$ . Es decir debemos probar que

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

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

Cabe destacar que dada una palabra ${\textstyle \alpha }$ , el numero ${\textstyle \#^{\leq }(\alpha )}$ nos dice en que posicion se hubica ${\textstyle \alpha }$ en la lista, es decir ${\textstyle \alpha }$ es la ( ${\textstyle \#^{\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 ${\textstyle n\geq 1}$ fijo. Entonces cada ${\textstyle x\geq 1}$ 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 ${\textstyle k\geq 0}$ y ${\textstyle 1\leq i_{k},i_{k-1},...,i_{0}\leq n}$ .'

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

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

Caracter recursivo de las funciones Failed to parse (unknown function "\protect"): {\textstyle s^{\protect\leq}} , Failed to parse (unknown function "\protect"): {\textstyle \ast^{\protect\leq}} y Failed to parse (unknown function "\protect"): {\textstyle \#^{\protect\leq}}

Es un ejercicio (dejado al lector) probar que cualquiera sea ${\textstyle \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 ${\textstyle s^{\leq }}$ ya que las ecuaciones anteriores nos muestran como obtener rapidamente ${\textstyle s^{\leq }(\alpha a)}$ en terminos de ${\textstyle s^{\leq }(\alpha )}$ y ${\textstyle a}$ , donde ${\textstyle a}$ es un elemento cualquiera de ${\textstyle \Sigma }$ . Por supuesto, en algun momento deberemos usar el dato inicial ${\textstyle s^{\leq }(\varepsilon )=a_{1}}$ . En un lenguaje de programacion funcional, las tres ecuaciones anteriores son directamente un programa para computar ${\textstyle 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 ${\textstyle s^{\leq }}$ (esto esta hecho mas adelante en la primera lista de funciones ${\textstyle \Sigma }$ -efectivamente computables).

Lo mismo sucede con la funcion ${\textstyle \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 ${\textstyle \#^{\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 ${\textstyle \Sigma }$ a ${\textstyle \Sigma ^{\ast }}$

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

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

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

Deberia ser intuitivamente claro que el orden recien definido sobre ${\textstyle \Sigma ^{\ast }}$ posee las mismas propiedades matematicas que el orden usual de ${\textstyle \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 ${\textstyle S\subseteq \Sigma ^{\ast }}$ es no vacio, entonces existe ${\textstyle \alpha \in S}$ tal que ${\textstyle \alpha \leq \beta }$ , para cada ${\textstyle \beta \in S}$ .'

Notacion y conceptos basicos

Conjuntos

Producto carteciano

Alfabetos

Ocurrencias

Reemplazos de ocurrencias

Matematica orientada a objetos

El concepto de funcion

Igualdad de funciones

Funcion identidad

Composicion de funciones

Funciones inyectivas, suryectivas y biyectivas

El nucleo de una funcion

Funcion caracteristica de un subconjunto

Restriccion de una funcion

Funciones de la forma [ f 1 , . . . , f n ] {\textstyle [f_{1},...,f_{n}]}

Union de funciones con dominios disjuntos

Relaciones binarias

Propiedades notables de relaciones binarias

Ordenes parciales

Ordenes totales sobre un conjunto

Diagramas de Hasse

Relaciones de equivalencia

Definicion de funciones con dominio A / R {\textstyle A/R}

Correspondencia entre relaciones de equivalencia y particiones

Operaciones n {\textstyle n} -arias sobre un conjunto

Relaciones n {\textstyle n} -arias sobre un conjunto

Funciones Σ {\textstyle \Sigma } -mixtas

Definicion de funcion Σ {\textstyle \Sigma } -mixta

Funciones S u c {\textstyle Suc} y P r e d {\textstyle Pred}

Las funciones d a {\textstyle d_{a}}

Las funciones p i n , m {\textstyle p_{i}^{n,m}}

Las funciones C k n , m {\textstyle C_{k}^{n,m}} y C α n , m {\textstyle C_{\alpha }^{n,m}}

La funcion p r {\textstyle pr}

El tipo de una funcion mixta

Funciones con imagen contenida en ω n × Σ ∗ m {\textstyle \omega ^{n}\times \Sigma ^{\ast m}}

Predicados Σ {\textstyle \Sigma } -mixtos

Operaciones logicas entre predicados

Familias Σ {\textstyle \Sigma } -indexadas de funciones

Conjuntos Σ {\textstyle \Sigma } -mixtos

El tipo de un conjunto mixto

Conjuntos rectangulares

Notacion lambda

Expresiones lambdificables con respecto a Σ {\textstyle \Sigma }

Definicion de λ x 1 . . . x n α 1 . . . α m [ E ] {\textstyle \lambda x_{1}...x_{n}\alpha _{1}...\alpha _{m}\left[E\right]}

Ordenes naturales sobre Σ ∗ {\textstyle \Sigma ^{\ast }}

Notacion decimal sin 0 {\textstyle 0}

Prueba de las propiedades (S) e (I)

El caso general

Caracter recursivo de las funciones Failed to parse (unknown function "\protect"): {\textstyle s^{\protect\leq}} , Failed to parse (unknown function "\protect"): {\textstyle \ast^{\protect\leq}} y Failed to parse (unknown function "\protect"): {\textstyle \#^{\protect\leq}}

Extension del orden total de Σ {\textstyle \Sigma } a Σ ∗ {\textstyle \Sigma ^{\ast }}

Funciones de la forma ${\textstyle [f_{1},...,f_{n}]}$

Definicion de funciones con dominio ${\textstyle A/R}$

Operaciones ${\textstyle n}$ -arias sobre un conjunto

Relaciones ${\textstyle n}$ -arias sobre un conjunto

Funciones ${\textstyle \Sigma }$ -mixtas

Definicion de funcion ${\textstyle \Sigma }$ -mixta

Funciones ${\textstyle Suc}$ y ${\textstyle Pred}$

Las funciones ${\textstyle d_{a}}$

Las funciones ${\textstyle p_{i}^{n,m}}$

Las funciones ${\textstyle C_{k}^{n,m}}$ y ${\textstyle C_{\alpha }^{n,m}}$

La funcion ${\textstyle pr}$

Funciones con imagen contenida en ${\textstyle \omega ^{n}\times \Sigma ^{\ast m}}$

Predicados ${\textstyle \Sigma }$ -mixtos

Familias ${\textstyle \Sigma }$ -indexadas de funciones

Conjuntos ${\textstyle \Sigma }$ -mixtos

Expresiones lambdificables con respecto a ${\textstyle \Sigma }$

Definicion de ${\textstyle \lambda x_{1}...x_{n}\alpha _{1}...\alpha _{m}\left[E\right]}$

Ordenes naturales sobre ${\textstyle \Sigma ^{\ast }}$

Notacion decimal sin ${\textstyle 0}$

Extension del orden total de ${\textstyle \Sigma }$ a ${\textstyle \Sigma ^{\ast }}$