Usaremos \(\mathbf{R}\) para denotar el conjunto de los números reales, \(\mathbf{Z}\) para denotar el conjunto de los números enteros, \(\mathbf{N}\) para denotar el conjunto de los números naturales y \(\omega\) para denotar al conjunto \(\mathbf{N}\cup\{0\}\).
Dado un conjunto \(A\), usaremos \(\mathcal{P}(A)\) para denotar el conjunto formado por todos los subconjuntos de \(A\), es decir: \[\mathcal{P}(A)=\{S:S\subseteq A\}\] Si \(A\) es un conjunto finito, entonces \(\left\vert A\right\vert\) denotará la cantidad de elementos de \(A\).
Para \(x,y\in\omega\), definamos \[x\dot{-}y=\left\{ \begin{array}{lll} x-y & & \text{si }x\geq y\\ 0 & & \text{caso contrario} \end{array}\right.\] Dados \(x,y\in\omega\) diremos que \(x\) divide a \(y\) cuando haya un \(z\in\omega\) tal que \(y=z.x\). Notar que \(0\) divide a \(0\), \(3\) divide a \(0\) y \(0\) no divide a \(23\). Escribiremos \(x\mid y\) para expresar que \(x\) divide a \(y\). Dados \(x,y\in\omega\), diremos que \(x\) e \(y\) son coprimos cuando \(1\) sea el único elemento de \(\omega\) que divide a ambos. Nótese que \(x\) e \(y\) no son son coprimos sii existe un número primo \(p\in\omega\) que los divide a ambos
Si bien no hay una definición natural en matemática de cuanto vale \(0^{0}\) (\(0\) elevado a la \(0\)), por convención para nosotros \(0^{0}=1\)
Supondremos que el lector sabe las nociones básicas sobre conjuntos, aunque resaltaremos algunas de las mas importantes para que las repase.
La propiedad de extensionalidad nos dice que, dados conjuntos \(A,B\), se tiene que \(A=B\) si y solo si para cada objeto \(x\) se da que \[x\in A\text{ si y solo si }x\in B\] Esta propiedad es importante metodológicamente ya que a la hora de probar que dos conjuntos \(A,B\) son iguales, extensionalidad nos asegura que basta con ver que se dan las dos inclusiones \(A\subseteq B\) y \(B\subseteq A\).
Otro tema importante es manejar correctamente la notación cuando definimos un conjunto usando llaves y mediante propiedades que caracterizan la pertenencia al mismo. Algunos ejemplos
adhocprefix-adhocsufix \(\{x\in\mathbf{N}:x=1\) o \(x\geq5\}\)
adhocprefix-adhocsufix \(\{x:x\in\mathbf{R}\) y \(x^{2}\geq100\}\)
adhocprefix-adhocsufix \(\{x:x=100\}\)
adhocprefix-adhocsufix \(\{x^{2}+1:x\in\omega\}\)
adhocprefix-adhocsufix \(\{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.
1.1. V o F o I, justifique.
adhocprefix(1)adhocsufix \(\{x.y:x,y\in\omega\}=\omega\)
adhocprefix(2)adhocsufix \(\left\vert \{x.y:x,y\in\omega\text{ y }1\leq x,y\leq5\}\right\vert =25\)
adhocprefix(3)adhocsufix Dados \(A,B\subseteq\omega\), se tiene que \(\{a\in A\) y \(b\in B:a+b=1000\}\subseteq A\times B\)
adhocprefix(4)adhocsufix \(\{a\in\mathbf{N},a\geq3\}\subseteq\omega\)
adhocprefix(5)adhocsufix \(\{x+1:x\in\{1,2,3\}\}=\{1,2,3,4\}\)
Dados conjuntos \(A_{1},...,A_{n}\), con \(n\geq2\), usaremos \(A_{1}\times...\times A_{n}\) para denotar el producto Cartesiano de \(A_{1},...,A_{n}\), es decir el conjunto formado por todas las \(n\)-uplas \((a_{1},...,a_{n})\) tales que \(a_{1}\in A_{1},...,a_{n}\in A_{n}\). Si \(A_{1}=...=A_{n}=A\), con \(n\geq2\), entonces escribiremos \(A^{n}\) en lugar de \(A_{1}\times...\times A_{n}\). Para \(n=1\), definimos \(A^{n}=A\), es decir \(A^{1}=A\). Usaremos \(\lozenge\) para denotar la única \(0\)-upla. Definimos entonces \(A^{0}=\{\lozenge\}\). Si \(A\) es un conjunto denotaremos con \(A^{\mathbf{N}}\) al conjunto formado por todas las infinituplas \((a_{1},a_{2},...)\) tales que \(a_{i}\in A\) para cada \(i\in\mathbf{N}\). Por ejemplo \[(1,2,3,4,...)\in\omega^{\mathbf{N}}\] donde \((1,2,3,4,...)\) es una forma intuitiva de denotar la infinitupla cuyo \(i\)-ésimo elemento es el número natural \(i\).
Si \((A_{1},A_{2},...)\) es una infinitupla de conjuntos, entonces usaremos \(\bigcup\nolimits_{i=1}^{\infty}A_{i}\) o \(\bigcup\nolimits_{i\geq1}A_{i}\) para denotar al conjunto \[\{a:a\in A_{i}\mathrm{,\ para\ algun\ }i\in\mathbf{N}\}\]
El concepto de símbolo es un concepto primitivo, es decir no definiremos que es un símbolo. Tampoco definiremos matemáticamente el concepto de palabra solo diremos en forma intuitiva que una palabra es una yuxtaposición de símbolos. Asumiremos que el lector tiene una intuición clara acerca de este tipo de objetos y de sus propiedades básicas. Las palabras de longitud \(1\) son exactamente los símbolos. Usaremos \(\left\vert \alpha\right\vert\) para denotar la longitud de la palabra \(\alpha\). Si \(\alpha\) es una palabra y \(\sigma\) es un símbolo, usaremos \(\left\vert \alpha\right\vert _{\sigma}\) para denotar la cantidad de ocurrencias de \(\sigma\) en \(\alpha\). Si \(\alpha,\beta\) son palabras, entonces \(\alpha\beta\) denotará la concatenación de las palabras \(\alpha\text{ y }\beta\). La única palabra de longitud \(0\) es denotada con \(\varepsilon\). Nótese que \(\alpha\varepsilon=\varepsilon\alpha\), para cualquier palabra \(\alpha\). También concatenaremos una sucesión de palabras, es decir si \(\alpha_{1},...,\alpha_{n}\), son palabras, con \(n\geq0\), usaremos \(\alpha_{1}...\alpha_{n}\) para denotar la concatenación de las palabras \(\alpha_{1},...,\alpha_{n}\) (nótese que cuando \(n=0\), resulta que \(\alpha_{1}...\alpha_{n}=\varepsilon\)). Si \(\alpha_{1}=...=\alpha_{n}=\alpha\), entonces con \(\alpha^{n}\) denotaremos la palabra \(\alpha_{1}...\alpha_{n}\). O sea que \(\alpha^{0}=\varepsilon\).
Si \(\alpha,\beta\) son palabras, entonces diremos que \(\alpha\) es subpalabra (propia) de \(\beta\) cuando (\(\alpha\notin\{\varepsilon,\beta\}\) y) existan palabras \(\delta,\gamma\) tales que \(\beta=\delta\alpha\gamma\). Diremos que \(\beta\) es un tramo inicial (propio) de \(\alpha\) si hay una palabra \(\gamma\) tal que \(\alpha=\beta\gamma\) (y \(\beta\notin\{\varepsilon,\alpha\}\)). En forma similar se define tramo final (propio).
Dada una palabra \(\alpha\) y \(i\in\omega\), definamos \[\left[\alpha\right]_{i}=\left\{ \begin{array}{lll} i\text{-ésimo elemento de }\alpha & & \text{si }1\leq i\leq\left\vert \alpha\right\vert \\ \varepsilon & & \text{caso contrario} \end{array}\right.\] Dada una palabra \(\gamma\), definamos \[\gamma^{R}=\left\{ \begin{array}{lll} [\gamma]_{\left\vert \gamma\right\vert }[\gamma]_{\left\vert \gamma\right\vert -1}...[\gamma]_{1} & & \text{si }\left\vert \gamma\right\vert \geq1\\ \varepsilon & & \text{caso contrario} \end{array}\right.\] La palabra \(\gamma^{R}\) es llamada la reciproca de \(\gamma\).
Dada una palabra \(\alpha\), definamos \[^{\curvearrowright}\alpha=\left\{ \begin{array}{lll} \left[\alpha\right]_{2}...\left[\alpha\right]_{\left\vert \alpha\right\vert } & \text{si} & \left\vert \alpha\right\vert \geq2\\ \varepsilon & \text{si} & \left\vert \alpha\right\vert \leq1 \end{array}\right.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \alpha^{\curvearrowleft}=\left\{ \begin{array}{lll} \left[\alpha\right]_{1}...\left[\alpha\right]_{\left\vert \alpha\right\vert -1} & \text{si} & \left\vert \alpha\right\vert \geq2\\ \varepsilon & \text{si} & \left\vert \alpha\right\vert \leq1 \end{array}\right.\]
Dadas palabras \(\alpha,\beta\), con \(\left\vert \alpha\right\vert ,\left\vert \beta\right\vert \geq1\), y un natural \(i\in\{1,...,\left\vert \beta\right\vert \}\), se dice que \(\alpha\) ocurre a partir de \(i\) en \(\beta\) cuando se de que existan palabras \(\delta,\gamma\) tales que \(\beta=\delta\alpha\gamma\) y \(\left\vert \delta\right\vert =i-1\). Intuitivamente hablando \(\alpha\) ocurre a partir de \(i\) en \(\beta\) cuando se de que si comenzamos a leer desde el lugar \(i\)-ésimo de \(\beta\) en adelante, leeremos la palabra \(\alpha\) completa y luego posiblemente seguirán otros símbolos.
Nótese que una palabra \(\alpha\) puede ocurrir en \(\beta\), a partir de \(i\), y también a partir de \(j\), con \(i\neq j\). En virtud de esto, hablaremos de las distintas ocurrencias de \(\alpha\) en \(\beta\). Por ejemplo hay dos ocurrencias de la palabra \(aba\) en la palabra \[cccccccabaccccabaccccc\] y también hay dos ocurrencias de la palabra \(aba\) en la palabra \[cccccccababacccccccccc\] En el primer caso diremos que dichas ocurrencias de \(aba\) son disjuntas ya que ocupan espacios disjuntos dentro de la palabra. En cambio en el segundo caso puede apreciarse que las dos ocurrencias se superponen en una posición. A veces diremos que una ocurrencia esta contenida o sucede dentro de otra. Por ejemplo la segunda ocurrencia de \(ab\) en \(babbbfabcccfabccc\) esta contenida en la primer ocurrencia de \(fabc\) en \(babbbfabcccfabccc\).
No definiremos en forma matemática precisa el concepto de ocurrencia pero el lector no tendrá problemas en comprenderlo y manejarlo en forma correcta.
También haremos reemplazos de ocurrencias por palabras. Por ejemplo el resultado de reemplazar la primer ocurrencia de \(abb\) en \(ccabbgfgabbgg\) por \(oolala\) es la palabra \(ccoolalagfgabbgg\). Cuando todas las ocurrencias de una palabra \(\alpha\) en una palabra \(\beta\) sean disjuntas entre si, podemos hablar del resultado de reemplazar simultáneamente cada ocurrencia de \(\alpha\) en \(\beta\) por \(\gamma\). Por ejemplo si tenemos \[\begin{aligned} \alpha & =yet\\ \beta & =ghsyetcjjjyetbcpyeteabc\\ \gamma & =\%\% \end{aligned}\] entonces \(ghs\%\%cjjj\%\%bcp\%\%eabc\) es el resultado de reemplazar simultáneamente cada ocurrencia de \(\alpha\) en \(\beta\) por \(\gamma\). Es importante notar que los reemplazos se hacen simultáneamente y no secuencialmente (i.e. reemplazando la primer ocurrencia de \(\alpha\) por \(\gamma\) y luego al resultado reemplazarle la primer ocurrencia de \(\alpha\) por \(\gamma\) y así 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 situaciones.
También se pueden hacer reemplazos simultáneos de distintas palabras en una palabra dada. Supongamos tenemos palabras \(\alpha_{1},...,\alpha_{n},\beta\) tales que
adhocprefix-adhocsufix \(\alpha_{i}\neq\alpha_{j}\), para \(i\neq j\)
adhocprefix-adhocsufix Para cada \(i\), las distintas ocurrencias de \(\alpha_{i}\) en \(\beta\) son disjuntas
adhocprefix-adhocsufix Si \(\alpha_{i}\) ocurre en \(\beta\) y \(\alpha_{j}\) ocurre en \(\beta\), con \(i\neq j\), entonces dichas ocurrencias son disjuntas
entonces dadas palabras cualesquiera \(\gamma_{1},...,\gamma_{n}\) hablaremos del resultado de reemplazar simultáneamente:
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{1}\) en \(\beta\), por \(\gamma_{1}\)
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{2}\) en \(\beta\), por \(\gamma_{2}\)
adhocprefix adhocsufix \(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\)
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{n}\) en \(\beta\), por \(\gamma_{n}\)
Por ejemplo si tomamos \[\begin{aligned} \alpha_{1} & =gh\\ \alpha_{2} & =yet\\ \alpha_{3} & =ana\\ \beta & =ghbbbyetbbgh\%\%ana\#\#ana!!!ana\\ \gamma_{1} & =AA\\ \gamma_{2} & =BBBB\\ \gamma_{3} & =CCC \end{aligned}\] entonces \(AAbbbBBBBbbAA\%\%CCC\#\#CCC!!!CCC\) es el resultado de reemplazar simultáneamente:
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{1}\) en \(\beta\), por \(\gamma_{1}\)
adhocprefix-adhocsufix cada ocurrencia de \(\alpha_{2}\) en \(\beta\), por \(\gamma_{2}\)
adhocprefix -adhocsufix cada ocurrencia de \(\alpha_{3}\) en \(\beta\), por \(\gamma_{3}\)
Un alfabeto es un conjunto finito de símbolos. Nótese que \(\emptyset\) es un alfabeto. Si \(\Sigma\) es un alfabeto, entonces \(\Sigma^{\ast}\) denotará el conjunto de todas las palabras formadas con símbolos de \(\Sigma\). En particular esto nos dice que \(\Sigma\subseteq\Sigma^{\ast}\). Ya que en \(\varepsilon\) no ocurren símbolos, tenemos que \(\varepsilon\in\Sigma^{\ast}\), para cualquier alfabeto \(\Sigma\). Más aún nótese que \(\emptyset^{\ast}=\{\varepsilon\}\).
Un lenguaje sobre \(\Sigma\) será un subconjunto de \(\Sigma^{*}\). Si \(L\) es un lenguaje sobre \(\Sigma\), entonces denotaremos con \(L^{+}\) al conjunto formado por todas las concatenaciones de sucesiones finitas no nulas de elementos de \(L\). Es decir: \[L^{+}=\{\alpha_{1}...\alpha_{n}:\alpha_{1},...,\alpha_{n}\in L\text{ y }n\geq1\}\] Definamos también \[L^{*}=L^{+}\cup\{\varepsilon\}\] Nótese que en particular obtenemos que \(\Sigma^{+}=\Sigma^{\ast}-\{\varepsilon\}\).
Llamaremos numerales a los siguientes símbolos \[0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\] Usaremos \(Num\) para denotar el conjunto de numerales. Nótese que \(Num\cap\omega=\emptyset\). Es decir, no debemos confundir los símbolos que usualmente denotan los primeros diez elementos de \(\omega\) con los números que ellos denotan. De hecho en china o japón los primeros diez elementos de \(\omega\) se denotan con otros símbolos. Similarmente las palabras pertenecientes a \(Num^{\ast}\) denotan (notación decimal) a los números de \(\omega\) pero debemos tener en cuenta que \(Num^{\ast}\cap\omega=\emptyset\). Cuando tratamos con palabras de \(Num^{\ast}\), debemos ser cuidadosos ya que muchas veces en nuestro discurso matemático (es decir las guías, y este apunte, lo que escriben los profesores en el pizarrón, etc) representamos dos objetos diferentes de la misma forma. Por ejemplo \(45\) puede estar denotando al número entero cuarenta y cinco o también \(45\) puede estar denotando la palabra de longitud \(2\) cuyo primer símbolo es el numeral \(4\) y cuyo segundo símbolo es el numeral \(5\), es decir en este segundo caso \(45\) se esta denotando a si misma. Por dar otro ejemplo, el símbolo \(1\) en nuestro discurso algunas veces se denotará a si mismo y otras veces denotará al número uno. Resumiendo, hay muchas palabras que algunas veces en nuestro discurso se representan a si mismas y otras veces representan a otro objeto matemático y es tarea del lector saber que corresponde en cada caso.
Los numerales bold son los numerales en modo negrita, es decir \[\mathbf{0}\mathbf{\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9}\] Cabe aclarar que estos numerales bold son distintos a los numerales antes introducidos. También usaremos los numerales itálicos \[\mathit{0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9}\] que obviamente son símbolos distintos a los numerales clásicos y a los bold.
Nuestro estilo o enfoque matemático pondrá énfasis en los objetos, es decir haremos matemática prestando atención a los distintos objetos matemáticos involucrados, los cuales siempre serán definidos en forma precisa en términos de objetos mas primitivos. Hay ciertos objetos matemáticos los cuales no definiremos y supondremos que el lector tiene una idea clara y precisa de los mismos. Por ejemplo un tipo de objeto matemático, quizás el mas famoso, son los números. No diremos que es un número pero supondremos que el lector tiene una intuición clara acerca de este tipo de objetos y de sus propiedades básicas. Otro tipo de objeto que no definiremos y que será clave para nuestro enfoque son los conjuntos. Nuevamente, no diremos que es un conjunto pero supondremos que el lector tiene una intuición clara acerca de estos objetos y sus propiedades básicas. Es importante que en nuestro enfoque, números y conjuntos son objetos de distinta naturaleza por lo cual nunca un número es un conjunto ni un conjunto es un número. En particular esto nos dice que el número \(0\) y el conjunto \(\emptyset\) son objetos distintos. Otro tipo de objetos matemáticos muy importante para la matemática discreta son los símbolos. No discutiremos que es un símbolo sino que aceptaremos este concepto en forma primitiva. También constituyen un tipo de objeto matemático las palabras, las cuales intuitivamente hablando son yuxtaposiciones de símbolos. Asumiremos que el lector tiene una intuición clara acerca de este tipo de objetos y de sus propiedades básicas. Las palabras de longitud \(1\) son exactamente los símbolos asique todo símbolo es una palabra. Otro tipo de objeto matemático muy importante son los pares ordenados o 2-uplas, es decir los objetos de la forma \((a,b)\), donde \(a\) y \(b\) son objetos matemáticos cualesquiera. También son objetos matemáticos y de distinta naturaleza las 3-uplas, las 4-uplas y en general las \(n\)-uplas para \(n\) un número natural mayor o igual a \(2\). Cabe destacar que en nuestro enfoque no habrá 1-uplas. Sin embargo, si bien hay una sola 0-upla, ella constituye un tipo de objeto matemático distinto a los antes mencionados. El último tipo de objeto matemático que consideraremos es aquel de las infinituplas.
Tenemos entonces dividido nuestro universo matemático en las distintas categorías o tipos 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 símbolos quedan contenidos en la categoría de las palabras). Es importante entender que las anteriores categorías o tipos de objetos son disjuntas entre si, es decir nunca un número será una palabra o una palabra será una 3-upla etc. En particular \(0\), \(\emptyset\), \(\lozenge\) y \(\varepsilon\) son cuatro objetos matemáticos diferentes. Esto nos permite definir una función \(Ti\) la cual a un objeto matemático le asigna su tipo de objeto matemático según 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(0) & =\mathrm{NUMERO}\\ Ti(\mathbf{\emptyset}) & =\mathrm{CONJUNTO}\\ Ti(\varepsilon) & =\mathrm{PALABRA}\\ Ti(\lozenge) & =0\mathrm{-UPLA}\\ Ti(\alpha) & =\mathrm{PALABRA}\text{, si }\alpha\text{ es un simbolo} \end{aligned}\]
Para hacer divertido nuestro desarrollo crearemos dos personajes que con su personalidad nos dejaran analizar las distintas maneras de hacer matemática. El escarabajo es netamente sintáctico y mecánico, no le gusta pensar los conceptos matemáticos imaginando los objetos involucrados en los mismos, simplemente quiere avanzar (sin mucho pensamiento) aplicando reglas sintácticas que le permitan obtener nuevas ecuaciones o expresiones matemáticas. El vive en el mundo plano de las palabras y ahí se siente apasionado por sus hábiles movimientos mecánicos. El escarabajo es en algún sentido una maravilla de la destreza mecánico-simbólica. La mariposa es todo lo contrario, le interesa pensar en los objetos matemáticos como si fueran reales dentro de su imaginación fantástica y con su habilidad de volar contempla el universo matemático desde un punto de vista conceptual e independiente de la manipulación sintáctica. Reconoce como objetos reales de su universo matemático no solo a los objetos finitarios (palabras, números, etc) sino también a toda la gama de objetos sofisticados transfinitos que se pueden construir con la imaginación y la especulación matemática. Mantiene este universo matemático en su imaginación dándole existencia y coherencia mas allá del mundo limitado de los objetos sintácticos que usa para expresarse. La mariposa es en algún sentido una maravilla de la imaginación matemática coherente.
A modo de ejemplo, al escarabajo la matemática orientada a objetos descripta en la sección anterior no le hace mucha gracia ya que es perezoso para imaginar los objetos asociados a los símbolos. Al contrario, la mariposa solo concibe la matemática orientada a objetos, los cuales piensa e imagina con un grado de realidad exacerbado.
En general la matemática se enseña con un estilo muy escarabajo y aun en las universidades esto persiste, manifestándose mas en las carreras de ciencias de la computación que en las vinculadas a la matemática clásica. Es natural que esto suceda ya que los informáticos manipulan constantemente objetos sintácticos usando reglas mecánicas y a veces los objetos subyacentes (semántica) pasan a un segundo plano.
Asumiremos que el lector tiene una idea intuitiva del concepto de función. Daremos aquí una definición matemática de dicho concepto. Una función es un conjunto \(f\) de pares ordenados con la siguiente propiedad
adhocprefix(F)adhocsufix Si \((x,y)\in f\) y \((x,z)\in f\), entonces \(y=z\).
Por ejemplo, si tomamos \(f=\{(x,x^{2}):x\in\omega\}\) se puede ver fácilmente que \(f\) cumple la propiedad (F). Otro ejemplo, \(f=\{(x,1):x\in\{1,6,18\}\}\) es una función.
Dada una función \(f\), llamaremos dominio de \(f\) al conjunto \[\{x:(x,y)\in f\text{ para algún }y\}\] y lo denotaremos con \(D_{f}\) o \(\mathrm{Dom}(f)\).
Llamaremos imagen de \(f\) al conjunto \[\{y:(x,y)\in f\text{ para algún }x\}\] y la denotaremos con \(I_{f}\) o \(\mathrm{Im}(f)\). Nótese que \(\emptyset\) es una función y que \(D_{\emptyset}=I_{\emptyset}=\emptyset\). Si \(f=\{(x,x^{2}):x\in\omega\}\) se tiene que \(D_{f}=\omega\) y \(I_{f}=\{y:y=x^{2}\) para algún \(x\in\omega\}\). Si \(f=\{(x,1):x\in\{1,6,18\}\}\), entonces \(D_{f}=\{1,6,18\}\) y \(I_{f}=\{1\}\).
Convención Notacional 1: Dado \(x\in D_{f}\), usaremos \(f(x)\) para denotar al único \(y\in I_{f}\) tal que \((x,y)\in f\). Por ejemplo, si \(f=\{(x,x^{2}):x\in\omega\}\) se tiene que \(f(x)=x^{2}\), para cada \(x\in D_{f}=\omega\).
Tenemos el siguiente resultado obvio.
1.1. Para cualquier función \(f\) siempre se da que \(f=\{(x,f(x)):x\in D_{f}\}\).
Proof. Llamemos \(A\) al conjunto \(\{(x,f(x)):x\in D_{f}\}\). Para probar que \(f=A\), ya que \(f\) y \(A\) son conjuntos, debemos ver que \((x,y)\in f\) sii \((x,y)\in A\). Supongamos \((x,y)\in f\). Es claro que \(x\in D_{f}\). La Convención Notacional 1 entonces nos dice que \(y=f(x)\), lo cual nos dice que \((x,y)=(x,f(x))\in A\) ya que \(x\in D_{f}\). Reciprocamente tomemos un elemento de \(A\), es decir un \((x,f(x))\), con \(x\in D_{f}\). La Convención Notacional 1 nos dice que \(f(x)\) es el único \(y\in I_{f}\) tal que \((x,y)\in f\), por lo cual claramente \((x,f(x))\in f\).
Convención Notacional 2: Escribiremos \(f:S\subseteq A\rightarrow B\) para expresar que \(f\) es una función tal que \(D_{f}=S\subseteq A\) y \(I_{f}\subseteq B\). También escribiremos \(f:A\rightarrow B\) para expresar que \(f\) es una función tal que \(D_{f}=A\) y \(I_{f}\subseteq B\). En tal contexto llamaremos a \(B\) conjunto de llegada. Por supuesto \(B\) no esta determinado por \(f\) ya que solo debe cumplir \(I_{f}\subseteq B\). Es decir que cualquier conjunto \(B\) que contenga a \(I_{f}\) puede ser considerado conjunto de llegada de \(f\).
Convención Notacional 3: Muchas veces para definir una función \(f\), lo haremos dando su dominio y su regla de asignación, es decir especificaremos en forma precisa que conjunto es el dominio de \(f\) y además especificaremos en forma precisa quien es \(f(x)\) para cada \(x\) de dicho dominio. Obviamente esto determina por completo a la función \(f\) ya que el lema anterior nos dice que siempre se da \(f=\{(x,f(x)):x\in D_{f}\}\). Por ejemplo si decimos que \(f\) es la función dada por: \[\begin{aligned} D_{f} & =\omega\\ f(x) & =23x^{2} \end{aligned}\] nos estaremos refiriendo a la función \(\{(x,23x^{2}):x\in\omega\}\). También escribiremos \[\begin{array}{rll} f:\omega & \rightarrow & \omega\\ x & \rightarrow & 23x^{2} \end{array}\] para describir a \(f\). Es decir, a veces para hacer mas intuitiva aun la descripción de la función, también incluiremos un conjunto de llegada de dicha función y a la regla de asignación la escribiremos usando una flecha. Para dar otro ejemplo, si escribimos sea \(f\) dada por: \[\begin{array}{rll} f:\mathbf{N} & \rightarrow & \omega\\ x & \rightarrow & \left\{ \begin{array}{ccc} x+1 & & \text{si }x\text{ es par}\\ x^{2} & & \text{si }x\text{ es impar} \end{array}\right. \end{array}\] estaremos diciendo que \(f\) es la función \[\{(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}\}\]
Sean \(f\) y \(g\) dos funciones. Ya que las mismas son conjuntos, tendremos que \(f\) será igual a \(g\) si y solo si para cada par \((a,b)\), se tiene que \((a,b)\in f\) sii \((a,b)\in g\). Muchas veces será útil el siguiente criterio de igualdad de funciones:
1.2. Sean \(f\) y \(g\) funciones. Entonces \(f=g\) sii \(D_{f}=D_{g}\) y para cada \(x\in D_{f}\) se tiene que \(f(x)=g(x)\)
Proof. \((\Rightarrow)\) Es obvio.
\((\Leftarrow)\) Supongamos que \(D_{f}=D_{g}\) y que para cada \(x\in D_{f}\) se tiene que \(f(x)=g(x)\). Por el lema anterior tenemos que \(f=\{(x,f(x)):x\in D_{f}\}\) y \(g=\{(x,g(x)):x\in D_{g}\}\). Es facil entonces ver que \(f=g\).
Dado un conjunto \(A\), a la función \[\begin{array}{rll} A & \rightarrow & A\\ a & \rightarrow & a \end{array}\] La denotaremos con \(Id_{A}\) y la llamaremos la función identidad sobre \(A\). Nótese que \(Id_{A}=\{(a,a):a\in A\}\).
Dadas funciones \(f\) y \(g\) definamos, basados en la Convención Notacional 3, la función \(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}\] Nótese que por un lema anterior tenemos que \[f\circ g=\{(e,f(g(e))):e\in D_{g}\text{ y }g(e)\in D_{f}\}\] Veamos un ejemplo. Si \(f\) es dada por \[\begin{array}{rll} f:\mathbf{N} & \rightarrow & \{@,\%\}^{*}\\ x & \rightarrow & @\%^{x}@ \end{array}\] y \(g\) es dada por \[\begin{array}{rll} g:\mathbf{R} & \rightarrow & \mathbf{R}\\ x & \rightarrow & x^{2} \end{array}\] entonces tenemos que \(f\circ g\) es la función \[\begin{array}{rll} f\circ g:\{x\in\mathbf{R}:x^{2}\in\mathbf{N}\} & \rightarrow & \{@,\%\}^{*}\\ x & \rightarrow & @\%^{x^{2}}@ \end{array}\]
1.3. Sean \(f,g\) funciones cualesquiera. Entonces:
adhocprefix(1)adhocsufix \(f\circ g=\{(u,v):\) existe \(z\) tal que \((u,z)\in g\) y \((z,v)\in f\}\)
adhocprefix(2)adhocsufix \(f\circ g\neq\emptyset\) si y solo si \(I_{g}\cap D_{f}\neq\emptyset\), lo cual nos dice que muchas veces sucederá que \(f\circ g=\emptyset\).
Proof. (1). Sea \[A=\{(u,v):\text{ existe }z\text{ tal que }(u,z)\in g\text{ y }(z,v)\in f\}\] Ya que \(f\circ g=\{(e,f(g(e))):e\in D_{g}\text{ y }g(e)\in D_{f}\}\) debemos probar que \[\{(e,f(g(e))):e\in D_{g}\text{ y }g(e)\in D_{f}\}=A\] Supongamos entonces que \((u,v)\in\{(e,f(g(e))):e\in D_{g}\text{ y }g(e)\in D_{f}\}\). Se tiene que \(u\in D_{g}\text{, }g(u)\in D_{f}\text{ y }v=f(g(u))\). Es claro que tomando \(z=g(u)\) se cumple la condición que define a \(A\), por lo cual hemos probado que \((u,v)\in A\). Recíprocamente supongamos que \((u,v)\in A\). O sea que hay un \(z\) tal que \((u,z)\in g\text{ y }(z,v)\in f\). Esto nos dice que \(u\in D_{g}\), \(z\in D_{f}\), \(z=g(u)\) y \(v=f(z)\). O sea que \((u,v)=(u,f(z))=(u,f(g(u))\) y como \(u\in D_{g}\text{ y }g(u)\in D_{f}\), tenemos que \((u,v)\in\{(e,f(g(e))):e\in D_{g}\text{ y }g(e)\in D_{f}\}\).
(2). Si \(f\circ g\neq\emptyset\), entonces \(D_{f\circ g}\) debe ser no vacío. Pero por definición tenemos que \(D_{f\circ g}=\{e\in D_{g}:g(e)\in D_{f}\}\). Es decir que existe un \(e\in D_{g}\) tal que \(g(e)\in D_{f}\). Obviamente \(g(e)\in I_{g}\cap D_{f}\), por lo cual \(I_{g}\cap D_{f}\neq\emptyset\). Recíprocamente supongamos que \(I_{g}\cap D_{f}\neq\emptyset\). Sea \(x_{0}\) un elemento de \(I_{g}\cap D_{f}\). Ya que \(x_{0}\in I_{g}\) tenemos que hay un \(e_{0}\in D_{g}\) tal que \(x_{0}=g(e_{0})\). Notar que entonces por definición de \(D_{f\circ g}\) tenemos que \(e_{0}\in D_{f\circ g}\). Esto claramente dice que \(f\circ g\neq\emptyset\).
A la hora de probar enunciados acerca de funciones hay una regla o idea básica que si la tenemos en cuenta nos facilitara la construcción de la prueba.
Regla Pertenecer a la Imagen: Si \(f\) es una función y Ud sabe que \(b\in I_{f}\), entonces escriba a \(b\) en la forma \(f(a)\) donde \(a\) denotará un elemento fijo de \(D_{f}\) tal que \(f(a)=b\)
Tener esta regla en mente es de suma utilidad al hacer pruebas. Por ejemplo el lector puede notar que fue usada tácitamente en la prueba de (2) del lema anterior.
Cabe destacar que esta regla aquí es simplemente un consejo o sugerencia pero gana su existencia material en un entorno de inteligencia artificial al transformarse en parte de la estructura de un probador automático de teoremas!
Una función \(f\) es inyectiva cuando no se da que \(f(a)=f(b)\) para algún par de elementos distintos \(a,b\in D_{f}\). Dicho de otra manera, \(f\) será inyectiva cuando se de la implicación \[f(a)=f(b)\text{ implica }a=b\] cualesquiera sean \(a,b\in D_{f}.\) Dada una función \(f:A\rightarrow B\) diremos que \(f\) es suryectiva cuando \(I_{f}=B\). Debe notarse que el concepto de suryectividad depende de un conjunto de llegada previamente fijado, es decir que no tiene sentido hablar de la suryectividad de una función \(f\) si no decimos respecto de que conjunto de llegada lo es. Muchas veces diremos que una función \(f\) es sobre para expresar que es suryectiva.
Dada una función \(f:A\rightarrow B\) diremos que \(f\) es biyectiva cuando \(f\) sea inyectiva y suryectiva. También diremos que \(f\) es una biyección de \(A\) en \(B\) cuando \(f:A\rightarrow B\) sea biyectiva.
Nótese que si \(f:A\rightarrow B\) es biyectiva, entonces para cada \(b\in B\) hay un único \(a\in A\) tal que \(f(a)=b.\) Entonces cuando \(f:A\rightarrow B\) es biyectiva podemos definir una nueva función \(f^{-1}:B\rightarrow A\), de la siguiente manera: \[f^{-1}(b)=\text{ único }a\in A\text{ tal que }f(a)=b\] La función \(f^{-1}\) será llamada la inversa de \(f\). Nótese que \(f\circ f^{-1}=Id_{B}\) y \(f^{-1}\circ f=Id_{A}\). El siguiente lema muestra que esta última propiedad caracteriza la inversa.
1.4. Supongamos \(f:A\rightarrow B\) y \(g:B\rightarrow A\) son tales que \(f\circ g=Id_{B}\) y \(g\circ f=Id_{A}\). Entonces \(f\) y \(g\) son biyectivas, \(f^{-1}=g\) y \(g^{-1}=f\).
Proof. Veamos que \(f\) es inyectiva. Supongamos \(f(a)=f(b)\), con \(a,b\in A\). Entonces \(g(f(a))=g(f(b))\). O sea que \(g\circ f(a)=g\circ f(b)\). Pero \(g\circ f=Id_{A}\) por lo cual obtenemos que \(a=b.\) Veamos que \(f\) es suryectiva. Sea \(b\in B.\) Ya que \(f\circ g=Id_{B}\) tenemos que \(f(g(b))=b\) lo cual nos dice que \(b\in I_{f}.\) Esto prueba que \(I_{f}=B\) por lo cual \(f\) es suryectiva. Veamos que \(f^{-1}=g\). Lo haremos aplicando el Lema 1.2. Por la definición de \(f^{-1}\) tenemos que \(D_{f^{-1}}=B=D_{g}\). Sea \(b\in B\). Veamos que \(f^{-1}(b)=g(b)\). Por definición de \(f^{-1}\) tenemos que \[f^{-1}(b)=\text{ unico }a\in A\text{ tal que }f(a)=b\] Pero sabemos que \(f(g(b))=b\) (ya que \(f\circ g=Id_{B}\)), por lo cual la unicidad nos asegura que \(f^{-1}(b)=g(b)\). Esto concluye la prueba de que \(f^{-1}=g\).
La prueba de que \(b\) es biyectiva y que \(g^{-1}=f\) es completamente análoga.
Dada una función \(f:A\rightarrow B\), definamos: \[\ker(f)=\{(a,b)\in A^{2}:f(a)=f(b)\}\] El conjunto \(\ker(f)\) será llamado el núcleo de \(f\). Nótese que \(f\) es inyectiva si y solo si \(\ker(f)=\{(a,a):a\in A\}\). Cabe destacar que \(\ker(f)\) es una relación de equivalencia muy importante asociada a la función \(f\).
Sea \(X\) un conjunto cualquiera y sea \(S\subseteq X\). Usaremos \(\chi_{S}^{X}\) para denotar la función \[\begin{array}{rcl} \chi_{S}^{X}:X & \rightarrow & \omega\\ x & \rightarrow & \left\{ \begin{array}{c} 1\text{ si }x\in S\\ 0\text{ si }x\notin S \end{array}\right. \end{array}\] Llamaremos a \(\chi_{S}^{X}\) la función característica de \(S\) con respecto a \(X\). Muchas veces cuando el conjunto \(X\) este fijo y sea claro el contexto, escribiremos \(\chi_{S}\) en lugar de \(\chi_{S}^{X}\).
Dada una función \(f\) y un conjunto \(S\subseteq D_{f}\), usaremos \(f|_{S}\) para denotar la restricción de \(f\) al conjunto \(S\), i.e. \(f|_{S}=f\cap(S\times I_{f})\). Nótese que \(f|_{S}\) es la función dada por \[\begin{aligned} D_{f|_{S}} & =S\\ f|_{S}(e) & =f(e)\text{, para cada }e\in S \end{aligned}\] Nótese que cualesquiera sea la función \(f\) tenemos que \(f|_{\emptyset}=\emptyset\) y \(f|_{D_{f}}=f\).
Dadas funciones \(f_{1},...,f_{n}\), con \(n\geq2\), definamos la función \([f_{1},...,f_{n}]\) de la siguiente manera: \[\begin{aligned} D_{[f_{1},...,f_{n}]} & =D_{f_{1}}\cap...\cap D_{f_{n}}\\{} [f_{1},...,f_{n}](e) & =(f_{1}(e),...,f_{n}(e)) \end{aligned}\] Nótese que \(I_{[f_{1},...,f_{n}]}\subseteq I_{f_{1}}\times\cdots\times I_{f_{n}}\). Por conveniencia notacional (que el lector entenderá mas adelante) definiremos \([f_{1}]=f_{1}\). Es decir que hemos definido para cada sucesión de funciones \(f_{1},...,f_{n}\), con \(n\geq1\), una nueva función la cual denotamos con \([f_{1},...,f_{n}]\).
Una observación interesante es que si \(f_{i}:A_{i}\rightarrow B_{i}\), \(i=1,...,k\), son funciones tales que \(A_{i}\cap A_{j}=\emptyset\) para \(i\neq j\), entonces el conjunto \(f_{1}\cup...\cup f_{k}\) es una función, mas concretamente la siguiente función: \[\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}\] Se suele decir que la función \(f_{1}\cup...\cup f_{k}\) es definida por casos a partir de las funciones \(f_{1},...,f_{k}\). Es importante notar que si no se da la condición \(A_{i}\cap A_{j}=\emptyset\) para \(i\neq j\), el conjunto \(f_{1}\cup...\cup f_{k}\) puede no ser una función. Dejamos al lector dar un ejemplo.
1.2. V o F o I, justifique.
adhocprefix(1)adhocsufix Si \[\begin{array}{rll} f:\mathbf{N} & \rightarrow & \omega\\ x & \rightarrow & x^{3} \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} g:\mathbf{N} & \rightarrow & \mathbf{R}\\ x & \rightarrow & x^{3} \end{array}\] entonces \(f=g\)
adhocprefix(2)adhocsufix Si \[\begin{array}{rll} f:\mathbf{N} & \rightarrow & \omega\\ x & \rightarrow & x^{3} \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} g:\mathbf{N} & \rightarrow & \omega\\ x & \rightarrow & x^{4}/x \end{array}\] entonces \(f=g\)
adhocprefix(3)adhocsufix Si \(f\) es una función y \(z\in D_{f}\), entonces \(Ti(z)=\mathrm{CONJUNTO}\)
adhocprefix(4)adhocsufix \(\mathrm{Dom}((1,2))=\{1\}\)
adhocprefix(5)adhocsufix \(\mathrm{Dom}(\{(1,2)\})+1=2\)
adhocprefix(6)adhocsufix Si \(f\) es una función, entonces \(D_{f}=\{a:(a,b)\in f\}\)
adhocprefix(7)adhocsufix Si \(f:A\rightarrow B\), entonces \(D_{f}\subseteq A\)
adhocprefix(8)adhocsufix Si \(f:A\rightarrow B\), entonces \(I_{f}=B\)
adhocprefix(9)adhocsufix Si \(f\) es una función y \(g\subseteq f\), entonces \(g\) es una función
1.3. V o F o I, justifique.
adhocprefix(1)adhocsufix Una función \(f\) es inyectiva si \(f(x)=f(y)\) cada vez que \(x=y\)
adhocprefix(2)adhocsufix \(F:A\rightarrow B\) es suryectiva sii para cada \(a\in A\) existe un \(b\in B\) tal que \(b=F(a)\)
1.4. Dar una biyección entre \(\mathbf{N}\) y \(\omega\). Ídem entre \(\omega\) y \(\{x\in\omega:x\) es par\(\}\)
1.5. Dar una función inyectiva de \(\omega^{2}\) en \(\omega\) y dar una función suryectiva de \(\omega\) en \(\omega^{5}\)
Consideremos el siguiente:
Principio de Inducción: Supongamos: \[\mathrm{Enu}_{1},\mathrm{Enu}_{2},\mathrm{Enu}_{3},\mathrm{Enu}_{4},...\] es una sucesión infinita de enunciados, cada uno de los cuales está escrito en forma precisa y es ya sea verdadero o falso. Supongamos además que
\(\mathrm{Enu}_{1}\) es verdadero
Cada vez que uno de los enunciados es verdadero, el siguiente también lo es.
Entonces todos los enunciados deben ser verdaderos
El principio anterior es obvio ya que al ser verdadero \(\mathrm{Enu}_{1}\) podemos inferir por la segunda propiedad que \(\mathrm{Enu}_{2}\) lo es pero esto a su ves nos dice que \(\mathrm{Enu}_{3}\) es verdadero, y así sucesivamente.
El Principio de Inducción da lugar a la siguiente regla la cual es extremadamente útil para realizar demostraciones en matemática.
Regla de Inducción: Supongamos: \[\mathrm{Enu}_{1},\mathrm{Enu}_{2},\mathrm{Enu}_{3},\mathrm{Enu}_{4},...\] es una sucesión infinita de enunciados, cada uno de los cuales está escrito en forma precisa y es ya sea verdadero o falso. Entonces para probar que cada uno de los enunciados es verdadero, basta con
Probar que \(\mathrm{Enu}_{1}\) es verdadero
Probar que para cada \(n\in\mathbf{N}\), se tiene que si \(\mathrm{Enu}_{n}\) es verdadero, entonces \(\mathrm{Enu}_{n+1}\) lo es.
Por supuesto, la Regla de Inducción es (como buena regla) netamente mecánico-operativa y nos dice como operar para probar infinitos enunciados cumpliendo dos tareas concretas. El Principio de Inducción justifica la corrección de esta regla. En algún sentido el Principio de Inducción es mas puro o primitivo ya que solo describe una situación acerca de los valores de verdad de los enunciados, bajo la cual todos resultan verdaderos. La Regla de Inducción se basa en este principio para decirnos que si hacemos ciertas demostraciones, entonces podemos concluir que hemos demostrado todos los enunciados \(\mathrm{Enu}_{n}\). Pero si esto le parece muy filosófico, tiene razón y siga leyendo que lo que viene es mas concreto y útil!
Veamos un ejemplo. Para cada \(n\in\mathbf{N}\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:
adhocprefixadhocsufix \(\mathrm{Enu}_{n}:\) \(1+2+...+n=\frac{n.(n+1)}{2}\)
Nótese que
adhocprefixadhocsufix \(\mathrm{Enu}_{1}:\) \(1=\frac{1.(1+1)}{2}\)
adhocprefixadhocsufix \(\mathrm{Enu}_{2}:\) \(1+2=\frac{2.(2+1)}{2}\)
adhocprefixadhocsufix \(\mathrm{Enu}_{3}:\) \(1+2+3=\frac{3.(3+1)}{2}\), etc.
Es fácil corroborar que alguno en particular es verdadero, simplemente hay que computar y ver si se da la igualdad. Pero por mas que corroboremos un millón de enunciados, no podremos garantizar la veracidad de todos, si no hacemos algún tipo de razonamiento genérico. Justamente la Regla de Inducción nos dice que cosas tenemos que probar para garantizar que todos los enunciados sean verdaderos. Hagamos entonces las pruebas encomendadas por la regla.
adhocprefixadhocsufix Prueba de \(\mathrm{Enu}_{1}\): Note que \[\frac{1.(1+1)}{2}=\frac{1.2}{2}=\frac{2}{2}=1\] por lo cual \(1=\frac{1.(1+1)}{2}\).
adhocprefixadhocsufix Prueba de que para cada \(n\in\mathbf{N}\), se tiene que si \(\mathrm{Enu}_{n}\) es verdadero, entonces \(\mathrm{Enu}_{n+1}\) lo es: Sea entonces un \(n_{0}\in\mathbf{N}\) fijo y supongamos que \(\mathrm{Enu}_{n_{0}}\) es verdadero. Probaremos que \(\mathrm{Enu}_{n_{0}+1}\) lo es. Tenemos entonces que \[1+2+...+n_{0}=\frac{n_{0}.(n_{0}+1)}{2}\] por lo cual \[1+2+...+n_{0}+(n_{0}+1)=\frac{n_{0}.(n_{0}+1)}{2}+(n_{0}+1)\] Pero \[\frac{n_{0}.(n_{0}+1)}{2}+(n_{0}+1)=\frac{n_{0}.(n_{0}+1)+2.(n_{0}+1)}{2}=\frac{(n_{0}+2).(n_{0}+1)}{2}=\frac{(n_{0}+1).(n_{0}+2)}{2}\] lo que nos dice que \[1+2+...+n_{0}+(n_{0}+1)=\frac{(n_{0}+1).((n_{0}+1)+1)}{2}\] que es justo lo que afirma \(\mathrm{Enu}_{n_{0}+1}\). Ya que \(n_{0}\) era arbitrario la implicación vale para cada \(n\in\mathbf{N}\).
Nada cambia si la sucesión de enunciados en lugar de comenzar desde \(1\), lo hace desde el \(0\). Es decir
Principio de Inducción desde \(0\): Supongamos: \[\mathrm{Enu}_{0},\mathrm{Enu}_{1},\mathrm{Enu}_{2},\mathrm{Enu}_{3},...\] es una sucesión infinita de enunciados, cada uno de los cuales está escrito en forma precisa y es ya sea verdadero o falso. Supongamos además que
\(\mathrm{Enu}_{0}\) es verdadero
Cada vez que uno de los enunciados es verdadero, el siguiente también lo es.
Entonces todos los enunciados deben ser verdaderos
Regla de Inducción desde \(0\): Supongamos: \[\mathrm{Enu}_{0},\mathrm{Enu}_{1},\mathrm{Enu}_{2},\mathrm{Enu}_{3},...\] es una sucesión infinita de enunciados, cada uno de los cuales está escrito en forma precisa y es ya sea verdadero o falso. Entonces para probar que cada uno de los enunciados es verdadero, basta con
Probar que \(\mathrm{Enu}_{0}\) es verdadero
Probar que para cada \(n\in\omega\), se tiene que si \(\mathrm{Enu}_{n}\) es verdadero, entonces \(\mathrm{Enu}_{n+1}\) lo es.
Este caso será muy usado tanto para la parte de computabilidad como para la parte de lógica.
También la sucesión de enunciados puede comenzar desde \(4\), por ejemplo la regla quedaría:
Regla de Inducción desde \(4\): Supongamos: \[\mathrm{Enu}_{4},\mathrm{Enu}_{5},\mathrm{Enu}_{6},\mathrm{Enu}_{7},...\] es una sucesión infinita de enunciados, cada uno de los cuales está escrito en forma precisa y es ya sea verdadero o falso. Entonces para probar que cada uno de los enunciados es verdadero, basta con
Probar que \(\mathrm{Enu}_{4}\) es verdadero
Probar que para cada \(n\geq4\), se tiene que si \(\mathrm{Enu}_{n}\) es verdadero, entonces \(\mathrm{Enu}_{n+1}\) lo es.
Por ejemplo para cada \(n\geq4\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:
adhocprefixadhocsufix \(\mathrm{Enu}_{n}:\) \(n!>2^{n}\)
O sea
adhocprefixadhocsufix \(\mathrm{Enu}_{4}:\) \(4!>2^{4}\)
adhocprefixadhocsufix \(\mathrm{Enu}_{5}:\) \(5!>2^{5}\)
adhocprefixadhocsufix \(\mathrm{Enu}_{6}:\) \(6!>2^{6}\), etc.
Dejamos al lector la prueba de que \(\mathrm{Enu}_{4},\mathrm{Enu}_{5},\mathrm{Enu}_{6},\mathrm{Enu}_{7},...\) son verdaderos usando la Regla de Inducción desde \(4\).
Nótese que para \(n<4\) no es cierto el enunciado \(n!>2^{n}\) por lo cual la Regla de Inducción desde \(4\) nos viene justo para este caso. Obviamente en otros casos en lugar de \(4\) nos será útil otro elemento de \(\omega\). Enunciamos entonces la regla en forma mas gral:
Regla de Inducción desde \(n_{0}\): Supongamos: \[\mathrm{Enu}_{n_{0}},\mathrm{Enu}_{n_{0}+1},\mathrm{Enu}_{n_{0}+2},\mathrm{Enu}_{n_{0}+3},...\] es una sucesión infinita de enunciados, con \(n_{0}\in\omega\), cada uno de los cuales está escrito en forma precisa y es ya sea verdadero o falso. Entonces para probar que cada uno de los enunciados es verdadero, basta con
Probar que \(\mathrm{Enu}_{n_{0}}\) es verdadero
Probar que para cada \(n\geq n_{0}\), se tiene que si \(\mathrm{Enu}_{n}\) es verdadero, entonces \(\mathrm{Enu}_{n+1}\) lo es.
Consideremos la siguiente:
Regla de Inducción Completa desde \(n_{0}\): Supongamos: \[\mathrm{Enu}_{n_{0}},\mathrm{Enu}_{n_{0}+1},\mathrm{Enu}_{n_{0}+2},\mathrm{Enu}_{n_{0}+3},...\] es una sucesión infinita de enunciados, con \(n_{0}\in\omega\), cada uno de los cuales está escrito en forma precisa y es ya sea verdadero o falso. Entonces para probar que cada uno de los enunciados es verdadero, basta con
Probar que \(\mathrm{Enu}_{n_{0}}\) es verdadero
Probar que para cada \(n\geq n_{0}\), si \(\mathrm{Enu}_{j}\) es verdadero para cada \(j\in\{n_{0},...,n\}\), entonces \(\mathrm{Enu}_{n+1}\) lo es.
El lector no tendrá inconvenientes en comprender la validez de esta regla. Hay casos en los cuales la Regla de Inducción desde \(n_{0}\) no nos es útil ya que de saber que es cierto \(\mathrm{Enu}_{n}\) no se nos ocurre como probar \(\mathrm{Enu}_{n+1}\), pero si asumimos que \(\mathrm{Enu}_{j}\) es verdadero para cada \(j\in\{n_{0},...,n\}\) entonces si se nos ocurre como probar \(\mathrm{Enu}_{n+1}\). En estos casos es natural aplicar la Regla de Inducción Completa desde \(n_{0}\). Veamos un ejemplo.
Para cada \(n\geq2\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:
adhocprefixadhocsufix \(\mathrm{Enu}_{n}:\) Existen números primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(n=p_{1}.p_{2}.....p_{k}\)
O sea
adhocprefixadhocsufix \(\mathrm{Enu}_{2}:\) Existen números primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(2=p_{1}.p_{2}.....p_{k}\)
adhocprefixadhocsufix \(\mathrm{Enu}_{3}:\) Existen números primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(3=p_{1}.p_{2}.....p_{k}\)
adhocprefixadhocsufix \(\mathrm{Enu}_{4}:\) Existen números primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(4=p_{1}.p_{2}.....p_{k}\)
etc. Para probar que \[\mathrm{Enu}_{2},\mathrm{Enu}_{3},\mathrm{Enu}_{4},...\] son verdaderos, hagamos las pruebas encomendadas por la Regla de Inducción Completa desde 2.
adhocprefixadhocsufix Prueba de \(\mathrm{Enu}_{2}\): Podemos tomar \(k=1\) y \(p_{1}=2\)
adhocprefixadhocsufix Prueba de que para cada \(n\geq2\), si \(\mathrm{Enu}_{j}\) es verdadero para cada \(j\in\{2,...,n\}\), entonces \(\mathrm{Enu}_{n+1}\) lo es: Sea entonces \(n\geq2\) fijo y supongamos que \(\mathrm{Enu}_{j}\) es verdadero para cada \(j\in\{2,...,n\}\). Probaremos que \(\mathrm{Enu}_{n+1}\) lo es. Si \(n+1\) es primo, entonces podemos tomar \(k=1\) y \(p_{1}=n+1\) para concluir que \(\mathrm{Enu}_{n+1}\) es cierto. Supongamos entonces que \(n+1\) no es primo. Entonces hay \(a,b\) tales que \(n+1=a.b\) y \(a,b\geq2\). Nótese que entonces \(a,b\leq n\). Por hipótesis tenemos que entonces \(\mathrm{Enu}_{a}\) y \(\mathrm{Enu}_{b}\) son ciertos por lo cual existen primos \(p_{1},...,p_{k}\), con \(k\geq1\) tales que \(a=p_{1}.....p_{k}\) y existen primos \(q_{1},...,q_{m}\), con \(m\geq1\) tales que \(b=q_{1}.....q_{m}\). Tenemos entonces que \[n+1=p_{1}.....p_{k}.q_{1}.....q_{m}\] de lo cual claramente obtenemos que \(\mathrm{Enu}_{n+1}\) es verdadero.
Dejamos al lector que experimente un rato la dificultad de intentar usar la Regla de Inducción desde 2 para este caso.
Algunas veces la sucesión de los enunciados \(\mathrm{Enu}_{n}\) es finita y esto no afecta para nada la idea de la inducción descripta anteriormente. Ya que es muy natural sólo enunciaremos las dos reglas que corresponden a este caso finito.
Regla de Inducción desde \(n_{0}\) hasta \(m_{0}\): Supongamos \(n_{0}<m_{0}\) son elementos de \(\omega\) y \[\mathrm{Enu}_{n_{0}},\mathrm{Enu}_{n_{0}+1},\mathrm{Enu}_{n_{0}+2},...,\mathrm{Enu}_{m_{0}}\] es una sucesión de enunciados cada uno de los cuales está escrito en forma precisa y es ya sea verdadero o falso. Entonces para probar que cada uno de los enunciados es verdadero, basta con
Probar que \(\mathrm{Enu}_{n_{0}}\) es verdadero
Probar que para cada \(n\in\{n_{0},...,m_{0}-1\}\), se tiene que si \(\mathrm{Enu}_{n}\) es verdadero, entonces \(\mathrm{Enu}_{n+1}\) lo es.
Regla de Inducción Completa desde \(n_{0}\) hasta \(m_{0}\): Supongamos \(n_{0}<m_{0}\) son elementos de \(\omega\) y \[\mathrm{Enu}_{n_{0}},\mathrm{Enu}_{n_{0}+1},\mathrm{Enu}_{n_{0}+2},...,\mathrm{Enu}_{m_{0}}\] es una sucesión de enunciados cada uno de los cuales está escrito en forma precisa y es ya sea verdadero o falso. Entonces para probar que cada uno de los enunciados es verdadero, basta con
Probar que \(\mathrm{Enu}_{n_{0}}\) es verdadero
Probar que para cada \(n\in\{n_{0},...,m_{0}-1\}\), si \(\mathrm{Enu}_{j}\) es verdadero para cada \(j\in\{n_{0},...,n\}\), entonces \(\mathrm{Enu}_{n+1}\) lo es.
Casi siempre que en matemática probamos algún enunciado, nuestro argumento involucra cierta ficción. Es decir en general, los enunciados matemáticos tienen hipótesis las cuales suponen que ciertos objetos cumplen ciertas propiedades y tienen su conclusión o tesis que es justamente lo que el enunciado asegura debe suceder si se dan las hipótesis. Esto hace que en la prueba se comience suponiendo que se dan las hipótesis y luego se empiece a desarrollar una ficción dentro de la cual vía cierto desarrollo se llegará a la conclusión (que también es parte de esa ficción). Por ejemplo consideremos el siguiente famoso enunciado:
adhocprefixadhocsufix \(\mathrm{Enu}_{1}\): Supongamos \(p\) es un polinomio a coeficientes complejos de grado mayor que \(0\). Entonces \(p\) tiene al menos una raíz compleja, es decir hay un número complejo \(c\) tal que \(p(c)=0\).
En la prueba del mismo asumiremos que \(p\) es un polinomio a coeficientes complejos de grado mayor que \(0\). Este sera el actor inicial de nuestra demostración (película) la cual nos terminara convenciendo de que hay un número complejo \(c\) tal que \(p(c)=0\). Para dar otro ejemplo, consideremos el enunciado:
adhocprefixadhocsufix \(\mathrm{Enu}_{2}\): Sean \(f,g\) funciones. Supongamos \(f\circ g\neq\emptyset\). Entonces \(I_{g}\cap D_{f}\neq\emptyset\).
En la prueba asumiremos que \(f,g\) son funciones y que \(f\circ g\neq\emptyset\). Ellas serán los actores iniciales de nuestra (ficción) demostración, la cual nos terminará convenciendo que \(I_{g}\cap D_{f}\neq\emptyset\).
Pero debemos notar que a lo largo de una demostración pueden surgir nuevos actores en escena. Es muy común que en el medio de una demostración probemos que existe al menos un objeto con cierta propiedad y que inmediatamente digamos sea \(e\) uno de tales objetos, fijado para el resto de nuestra demostración. Claramente \(e\) es un nuevo actor en la ficción de nuestra prueba (película). Para dar otro ejemplo, dentro de una demostración puede suceder que probemos que cierto objeto \(r\) es un número racional. Obviamente \(r\) ya era un actor dentro de la ficción de la prueba, pero ahora podemos incorporar dos nuevos actores \(a,b\in\mathbf{Z}\)tales que \(r=a/b\). Y nuestro argumento (película) sigue ahora con dos nuevos actores. Por ejemplo en la prueba de \(\mathrm{Enu}_{2}\), la cual puede verse aqui, aparte de los actores \(f\) y \(g\) surge el nuevo actor \(e\) tal que \(e\in D_{g}\) y \(g(e)\in D_{f}\), el cual sirve para concluir que \(I_{g}\cap D_{f}\neq\emptyset\).
Resumiendo, en una prueba, aparte de los objetos reales de la matemática, pueden estar involucrados objetos que son solo parte de la ficción correspondiente al argumento de la prueba. Cabe destacar que parte de la madurez de un matemático profesional consiste en tratar e imaginar a dichos objetos como si fueran reales y concretos. Muchas veces en el transcurso de una prueba, se usará alguna versión de la Regla de Inducción aplicada a una sucesión de enunciados que involucran objetos que sólo existen en la ficción de la prueba misma y no fuera de ella.
Esto no trae inconvenientes dado que aún dentro de la ficción de una prueba los conceptos de verdad y de demostración tienen las propiedades que hacen válidos al Principio de Inducción y a la Regla de Inducción, en todas sus versiones.
Sea \(A\) un conjunto. Por una relación binaria sobre \(A\) entenderemos un subconjunto de \(A^{2}\). Algunos ejemplos:
adhocprefix(E1)adhocsufix Sea \(R=\{(1,2),(2,3)\}\). Entonces \(R\) es una relación binaria sobre \(\mathbf{N}\).
adhocprefix(E2)adhocsufix Sea \(R=\{(x,y)\in\omega^{2}:\) \(x\) divide a \(y\}\). Entonces \(R\) es una relación binaria sobre \(\omega\).
adhocprefix(E3)adhocsufix Sea \(R=\{(r,t)\in\mathbf{R}^{2}:r\leq t\}\). Entonces \(R\) es una relación binaria sobre \(\mathbf{R}\)
adhocprefix(E4)adhocsufix \(\emptyset\) es una relación binaria sobre \(A\), cualesquiera sea el conjunto \(A\).
adhocprefix(E5)adhocsufix Sea \(R=\{(x,y)\in\omega^{2}:x<y\) o \(y=0\}\). Entonces \(R\) es una relación binaria sobre \(\omega\)
Nótese que si \(R\) es una relación binaria sobre \(A\) y \(A\subseteq B\) entonces \(R\) es una relación binaria sobre \(B\). Por ejemplo las relaciones dadas en los ejemplos (E1), (E2), (E4) y (E5) también son relaciones binarias sobre \(\mathbf{R}\). Sin embargo si \(R\) es una relación binaria sobre \(B\) y \(A\subseteq B\) entonces no necesariamente \(R\) será una relación binaria sobre \(A\) (por que?).
Como es usual, cuando \(R\) sea una relación binaria sobre un conjunto \(A\), algunas veces escribiremos \(aRb\) en lugar de \((a,b)\in R\).
Hay algunas propiedades que pueden tener o no las relaciones binarias sobre un conjunto \(A\), las cuales son muy importantes en matemática. Algunas de estas son:
Reflexividad: \(xRx\), cualesquiera sea \(x\in A\)
Transitividad: \(xRy\) y \(yRz\) implica \(xRz\), cualesquiera sean \(x,y,z\in A\)
Simetría: \(xRy\) implica \(yRx\), cualesquiera sean \(x,y\in A\)
Antisimetría: \(xRy\) y \(yRx\) implica \(x=y\), cualesquiera sean \(x,y\in A\)
Cuando \(R\) cumpla la primer propiedad diremos que \(R\) es reflexiva, con respecto a \(A\). Análogamente diremos que \(R\) es transitiva, simétrica o antisimétrica, con respecto a \(A\), cuando se den, respectivamente las otras propiedades. Nótese que estas propiedades dependen del conjunto \(A\), por ejemplo si tomamos \(R=\{(r,t)\in\mathbf{N}^{2}:r\leq t\}\) entonces \(R\) es una relación binaria sobre \(\mathbf{N}\) y también es una relación binaria sobre \(\omega\), pero es reflexiva con respecto a \(\mathbf{N}\) y no lo es con respecto a \(\omega\) ya que \((0,0)\) no pertenece a \(R\). Sin embargo \(R\) es transitiva con respecto a \(\mathbf{N}\) y también lo es con respecto a \(\omega\).
Una relación binaria \(R\) sobre un conjunto \(A\) será llamada un orden parcial sobre \(A\) si es reflexiva, transitiva y antisimétrica respecto de \(A\). Algunos ejemplos:
adhocprefix(E1)adhocsufix Sea \(R=\{(r,t)\in\mathbf{R}^{2}:r\leq t\}\). Entonces \(R\) es un orden parcial sobre \(\mathbf{R}\), llamado el orden usual de \(\mathbf{R}\)
adhocprefix(E2)adhocsufix Sea \(R=\{(1,2),(1,3),(1,1),(2,2),(3,3)\}\). Entonces \(R\) es un orden parcial sobre \(\{1,2,3\}\)
adhocprefix(E3)adhocsufix Sea \(R=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subseteq T\}\). Entonces \(R\) es un orden parcial sobre \(\mathcal{P}(\omega)\)
adhocprefix(E4)adhocsufix Sea \(R=\{(x,y)\in\omega^{2}:\) \(x\leq y\}\). Entonces \(R\) es un orden parcial sobre \(\omega\).
adhocprefix(E5)adhocsufix Sea \(R=\{(1,1)\}\). Entonces \(R\) es un orden parcial sobre \(\{1\}\).
adhocprefix(E6)adhocsufix \(\{(a,b)\in A^{2}:a=b\}\) es un orden parcial sobre \(A\), cualesquiera sea el conjunto \(A\)
adhocprefix(E7)adhocsufix Sea \(\mathrm{\leq}=\{(n,m)\in\mathbf{N}^{2}:n\mid m\}\). Es fácil ver que \(\leq\) es un orden parcial sobre \(\mathbf{N}\)
Nótese que las relaciones dadas en (E1) y (E4) son distintas, además la relación dada en (E4) no es un orden parcial sobre \(\mathbf{R}\) (por que?).
Muchas veces denotaremos con \(\leq\) a una relación binaria que sea un orden parcial. Esto hace mas intuitiva nuestra escritura pero siempre hay que tener en cuenta que \(\leq\) en estos casos esta denotando cierto conjunto de pares ordenados previamente definido.
Usaremos la siguiente
Convención Notacional: Si hemos denotado con \(\leq\) a cierto orden parcial sobre un conjunto \(A\), entonces
Denotaremos con \(<\) a la relación binaria \(\{(a,b)\in A^{2}:a\leq b\) y \(a\neq b\}\). Es decir que \(\mathrm{<}=\{(a,b)\in A^{2}:a\leq b\) y \(a\neq b\}\). Cuando se dé \(a<b\) diremos que \(a\) es menor que \(b\) o que \(b\) es mayor que \(a\) (respecto de \(\leq\))
Denotaremos con \(\prec\) a la relación binaria \[\{(a,b)\in A^{2}:a<b\text{ y no existe }z\text{ tal que }a<z<b\}\] Cuando se dé \(a\prec b\) diremos que \(a\) es cubierto por \(b\) o que \(b\) cubre a \(a\) (respecto de \(\leq\))
Algunos ejemplos:
adhocprefix(E1)adhocsufix Si \(A=\mathbf{R}\) y \(\mathrm{\leq}=\{(r,t)\in\mathbf{R}^{2}:r=t\}\), entonces \(\mathrm{<}=\emptyset\)
adhocprefix(E2)adhocsufix Si \(A=\{1,2,3,4\}\) y \(\mathrm{\leq}=\{(1,2),(2,3),(1,3),(1,1),(2,2),(3,3),(4,4)\}\), entonces \(\mathrm{<}=\{(1,2),(2,3),(1,3)\}\) y \(\mathrm{\prec}=\{(1,2),(2,3)\}\). En particular tenemos que \(1\prec2\), \(1<3\) pero no se da que \(1\prec3\).
adhocprefix(E3)adhocsufix Si \(A=\mathcal{P}(\omega)\) y \(\mathrm{\leq}=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subseteq T\}\), entonces \(\mathrm{<}=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subsetneq T\}\) y \(S\prec T\) sii hay un \(n\in T-S\) tal que \(T=S\cup\{n\}\)
Sea \(A\) un conjunto cualquiera. Por un orden total sobre \(A\) entenderemos un orden parcial \(\leq\) sobre \(A\) el cual cumpla:
adhocprefix(C)adhocsufix \(a\leq b\) o \(b\leq a\), cualesquiera sean \(a,b\in A\)
Supongamos \(A\) es finito no vacío y \(\leq\) es un orden total sobre \(A\). La propiedad (C) nos permite probar que para cada conjunto no vacío \(S\subseteq A\), hay un elemento \(s\in S\) el cual cumple \(s\leq s^{\prime}\) para cada \(s^{\prime}\in S\). Por supuesto, \(s\) es único (por que?) y habitualmente es llamado el menor elemento de \(S\), ya que es menor que todo otro elemento de \(S\).
Si \(A\) es finito no vacío y \(\leq\) es un orden total sobre \(A\), podemos definir recursivamente una función \(f:\{1,...,\left\vert A\right\vert \}\rightarrow A\) de la siguiente manera:
adhocprefix-adhocsufix \(f(1)=\) menor elemento de \(A\)
adhocprefix-adhocsufix Si \(i\in\{1,...,\left\vert A\right\vert -1\}\), entonces
adhocprefix-adhocsufix \(f(i+1)=\) menor elemento de \(A-\{f(1),...,f(i)\}\)
Como es habitual, \(f(i)\) es llamado el \(i\)-ésimo elemento de \(A\).
Muchas veces para dar un orden total sobre un conjunto finito \(A\), daremos simplemente sus elementos en forma creciente ya que esto determina el orden por completo. Por ejemplo si \(A=\{1,2,3\}\), el orden total dado por \(2<1<3\) es la relación \(\mathrm{\leq}=\{(2,1),(1,3),(2,3),(1,1),(2,2),(3,3)\}\).
Un concepto importante relativo a los ordenes totales es el de sucesor. Si \(\leq\) es un orden total sobre \(A\) y \(a,b\in A\), diremos que \(b\) es el sucesor de \(a\) cuando se dé que \(a<b\) y \(b\leq c\), para cada \(c\in A\) tal que \(a<c\), i.e., \(b\) es el menor elemento del conjunto \(\{c\in A:\) tal que \(a<c\}\). No siempre existe el sucesor de un elemento. Por ejemplo si \(\leq\) es el orden usual de \(\mathbf{R}\), entonces ningún elemento tiene sucesor (justifique).
Dado un orden parcial \(\leq\) sobre un conjunto finito \(A\) podemos realizar un diagrama de \(\leq\), llamado diagrama de Hasse, siguiendo las siguientes instrucciones:
adhocprefix(1)adhocsufix Asociar en forma inyectiva, a cada \(a\in\) \(A\) un punto \(p_{a}\) del plano
adhocprefix(2)adhocsufix Trazar un segmento de recta uniendo los puntos \(p_{a}\) y \(p_{b}\), cada vez que \(a\prec b\)
adhocprefix(3)adhocsufix Realizar lo indicado en los puntos (1) y (2) en tal forma que
adhocprefix(i)adhocsufix Si \(a\prec b\), entonces \(p_{a}\) esta por debajo de \(p_{b}\)
adhocprefix(ii)adhocsufix Si un punto \(p_{a}\) ocurre en un segmento del diagrama entonces lo hace en alguno de sus extremos.
La relación de orden \(\leq\) puede ser fácilmente obtenida de su diagrama, a saber, \(a\leq b\) sucederá si y solo si \(p_{a}=p_{b}\) o hay una sucesión de segmentos ascendentes desde \(p_{a}\) hasta \(p_{b}\).
Ejemplos:
Sea \(A\) un conjunto cualquiera. Por una relación de equivalencia sobre \(A\) entenderemos una relación binaria sobre \(A\) la cual es reflexiva, transitiva y simétrica, con respecto a \(A\), es decir, la cual cumple:
Reflexividad: \(xRx\), cualesquiera sea \(x\in A\)
Transitividad: \(xRy\) y \(yRz\) implica \(xRz\), cualesquiera sean \(x,y,z\in A\)
Simetría: \(xRy\) implica \(yRx\), cualesquiera sean \(x,y\in A\)
Algunos ejemplos:
adhocprefix(E1)adhocsufix Sea \(R=\{(r,t)\in\mathbf{R}^{2}:r=t\}\). Entonces \(R\) es una relación de equivalencia sobre \(\mathbf{R}\)
adhocprefix(E2)adhocsufix Dada una función \(f:A\rightarrow B\), el núcleo de \(f\), i.e. \(\ker(f)=\{(a,b)\in A^{2}:f(a)=f(b)\}\) es una relación de equivalencia sobre \(A\).
adhocprefix(E3)adhocsufix Sea \(R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\). Entonces \(R\) es una relación de equivalencia sobre \(\{1,2,3\}\)
adhocprefix(E4)adhocsufix Sea \(R=\{(x,y)\in\omega^{2}:x=y\}\). Entonces \(R\) es una relación de equivalencia sobre \(\omega\)
adhocprefix(E5)adhocsufix Sea \(R=\{(S,T)\in\mathcal{P}(\omega)^{2}:(S-T)\cup(T-S)\) es finito\(\}\). Entonces \(R\) es una relación de equivalencia sobre \(\mathcal{P}(\omega)\)
adhocprefix(E7)adhocsufix Sea \(R=\{(1,1)\}\). Entonces \(R\) es una relación de equivalencia sobre \(\{1\}\).
adhocprefix(E8)adhocsufix Sea \(R=\{(x,y)\in\mathbf{Z}^{2}:x-y\) es múltiplo de \(2\}\). Entonces \(R\) es una relación de equivalencia sobre \(\mathbf{Z}\).
Dada una relación de equivalencia \(R\) sobre \(A\) y \(a\in A\), definimos: \[a/R=\{b\in A:aRb\}\] El conjunto \(a/R\) será llamado la clase de equivalencia de \(a\), con respecto a \(R\). Ejemplos:
adhocprefix(E1)adhocsufix Si \(R=\{(r,t)\in\mathbf{R}^{2}:r=t\}\), entonces \(r/R=\{r\}\), cualesquier sea \(r\in\mathbf{R}\)
adhocprefix(E2)adhocsufix Si \(R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\), entonces \(1/R=2/R=\{1,2\}\) y \(3/R=\{3\}\)
adhocprefix(E3)adhocsufix Si \(R=\{(x,y)\in\mathbf{Z}^{2}:x-y\) es múltiplo de \(2\}\), entonces \(0/R=\{t\in\mathbf{Z}:t\) es par\(\}\), \(1/R=\{t\in\mathbf{Z}:t\) es impar\(\}\) y en general nótese que \(n/R=\{t\in\mathbf{Z}:t\) es par\(\}\) si \(n\) es par y \(n/R=\{t\in\mathbf{Z}:t\) es impar\(\}\) si \(n\) es impar. Es decir que hay solo dos clases de equivalencia con respecto a \(R\)
Algunas propiedades básicas son:
1.5. Sea \(R\) una relación de equivalencia sobre \(A\). Sean \(a,b\in A\).
adhocprefix(1)adhocsufix \(a\in a/R\)
adhocprefix(2)adhocsufix \(aRb\) si y solo si \(a/R=b/R\). Es decir que \(b\in a/R\) implica \(b/R=a/R\)
adhocprefix(3)adhocsufix \(a/R\cap b/R=\emptyset\) o \(a/R=b/R\)
Proof. (1) es muy fácil.
(2) Supongamos \(aRb\). Veremos que \(a/R\subseteq b/R\). Supongamos \(c\in a/R\). Entonces \(aRc\). Como \(aRb\), tenemos que \(bRa\), por lo cual hemos probado que \(bRa\) y \(aRc\), lo cual implica que \(bRc\). O sea que \(cRb\), lo cual nos dice que \(c\in b/R\). Esto prueba que \(a/R\subseteq b/R\). Similarmente se prueba que \(b/R\subseteq a/R\), con lo cual se tiene que \(a/R=b/R\).
Recíprocamente, si \(a/R=b/R\), entonces \(b\in a/R\) ya que \(b\in b/R\). Pero esto nos dice que \(aRb\).
(3) Supongamos que \(a/R\cap b/R\) no es vacío, es decir hay un \(c\in a/R\cap b/R\). Entonces es fácil ver que \(aRb\). Pero entonces por (2) tenemos que \(a/R=b/R\).
Denotaremos con \(A/R\) al conjunto \(\{a/R:a\in A\}\). Llamaremos a \(A/R\) el cociente de \(A\) por \(R\). Ejemplos:
adhocprefix(E1)adhocsufix Si \(R=\{(r,t)\in\mathbf{R}^{2}:r=t\}\), entonces \(\mathbf{R}/R=\{\{r\}:r\in\mathbf{R}\}\)
adhocprefix(E2)adhocsufix Si \(R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\), entonces \(\{1,2,3\}/R=\{\{1,2\},\{3\}\}\)
adhocprefix(E3)adhocsufix Si \(R=\{(x,y)\in\mathbf{Z}^{2}:x-y\) es múltiplo de \(2\}\), ya vimos que \(\mathbf{Z}/R=\{\{t\in\mathbf{Z}:t\) es par\(\},\{t\in\mathbf{Z}:t\) es impar\(\}\}\)
Si \(R\) es una relación de equivalencia sobre \(A\), definamos la función \(\pi_{R}:A\rightarrow A/R\) por \(\pi_{R}(a)=a/R\), para cada \(a\in A\). La función \(\pi_{R}\) es llamada la proyección canónica (respecto de \(R\)).
1.6. Sea \(R\) una relación de equivalencia sobre \(A\). Entonces \(\ker(\pi_{R})=R\). Es decir que \(\pi_{R}\) es inyectiva sii \(R=\{(x,y)\in A^{2}:x=y\}\)
Dado un conjunto \(A\) por una partición de \(A\) entenderemos un conjunto \(\mathcal{P}\) tal que:
adhocprefix-adhocsufix Cada elemento de \(\mathcal{P}\) es un subconjunto no vacío de \(A\)
adhocprefix-adhocsufix Si \(S_{1},S_{2}\in\mathcal{P}\) y \(S_{1}\neq S_{2}\), entonces \(S_{1}\cap S_{2}=\emptyset\)
adhocprefix-adhocsufix \(A=\{a:a\in S\), para algún \(S\in\mathcal{P}\}\)
La última condición dice simplemente que la unión de todos los elementos de \(\mathcal{P}\) debe ser \(A\). Ejemplos:
adhocprefix(E1)adhocsufix Si \(A=\{1,2,3,4,5\}\), entonces \[\mathcal{P}=\{\{1,5\},\{2,3\},\{4\}\}\]
es una partición de \(A\)
adhocprefix(E2)adhocsufix \(\mathcal{P}=\{\mathbf{N},\mathbf{R}-\mathbf{N}\}\) es una partición de \(\mathbf{R}\)
adhocprefix(E3)adhocsufix \(\mathcal{P}=\{\{0\},\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{9,10\},...\}\) es una partición de \(\omega\)
Una observación importante es que si \(\mathcal{P}\) es una partición de \(A\), entonces para cada \(a\in A\) hay un único \(S\in\mathcal{P}\) tal que \(a\in S\) (por que?). O sea que podemos hablar de EL elemento de \(\mathcal{P}\) que contiene a \(a\).
Dada una partición \(\mathcal{P}\) de un conjunto \(A\) podemos definir una relación binaria asociada a \(\mathcal{P}\) de la siguiente manera: \[R_{\mathcal{P}}=\{(a,b)\in A^{2}:a,b\in S\text{, para algún }S\in\mathcal{P}\}\]
1.7. Sea \(A\) un conjunto cualquiera. Entonces:
adhocprefix(1)adhocsufix Sea \(\mathcal{P}\) una partición de \(A\). Entonces \(R_{\mathcal{P}}\) es una relación de equivalencia sobre \(A\).
adhocprefix(2)adhocsufix Sea \(R\) una relación de equivalencia sobre \(A\). Entonces \(A/R\) es una partición de \(A\).
Proof. (1). Es fácil ver que \(R_{\mathcal{P}}\) es reflexiva y simétrica. Veamos que es transitiva. Supongamos que \(aR_{\mathcal{P}}b\) y \(bR_{\mathcal{P}}c\). O sea que hay \(S_{1},S_{2}\in\mathcal{P}\) tales que \(a,b\in S_{1}\) y \(b,c\in S_{2}\). Ya que \(S_{1}\) y \(S_{2}\) tienen un elemento en común, deberá suceder que \(S_{1}=S_{2}\). Pero entonces tenemos que \(a,c\in S_{1}\), lo cual nos dice que \(aR_{\mathcal{P}}c\).
(2). Sigue fácilmente del Lema 1.5.
El siguiente teorema da una correspondencia natural entre relaciones de equivalencia sobre \(A\) y particiones de \(A\).
1.1. Sea \(A\) un conjunto cualquiera. Sean \[\begin{aligned} Part & =\{\text{particiones de }A\}\\ ReEq & =\{\text{relaciones de equivalencia sobre }A\} \end{aligned}\] Entonces las funciones: \[\begin{array}{rll} Part & \rightarrow & ReEq\\ \mathcal{P} & \rightarrow & R_{\mathcal{P}} \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} ReEq & \rightarrow & Part\\ R & \rightarrow & A/R \end{array}\] son biyecciones una inversa de la otra.
Proof. Nótese que por el Lema 1.4 basta con probar:
adhocprefix(1)adhocsufix \(A/R_{\mathcal{P}}=\mathcal{P}\), cualesquiera sea la partición \(\mathcal{P}\) de \(A\)
adhocprefix(2)adhocsufix \(R_{A/R}=R\), cualesquiera sea la relación de equivalencia \(R\) sobre \(A\)
Prueba de (1). Primero veamos que \(A/R_{\mathcal{P}}\subseteq\mathcal{P}\). Sea \(a\in A\), veremos que \(a/R_{\mathcal{P}}=\{b:aR_{\mathcal{P}}b\}\in\mathcal{P}\). Sea \(S\) el único elemento de \(\mathcal{P}\) que contiene a \(a\). Es fácil ver de la definición de \(R_{\mathcal{P}}\) que \(a/R_{\mathcal{P}}=S\) por lo cual \(a/R_{\mathcal{P}}\in\mathcal{P}\). Veamos ahora que \(\mathcal{P}\subseteq A/R_{\mathcal{P}}\). Sea \(S\in\mathcal{P}\). Sea \(a\in S\). Es fácil ver de la definición de \(R_{\mathcal{P}}\) que \(a/R_{\mathcal{P}}=S\) por lo cual \(S\in A/R_{\mathcal{P}}\).
Prueba de (2). Primero veamos que \(R_{A/R}\subseteq R\). Supongamos \(aR_{A/R}b\). Entonces \(a,b\in c/R\), para algún \(c\in A\). Es claro que entonces \(aRb\). Veamos ahora que \(R\subseteq R_{A/R}\). Supongamos que \(aRb\). Entonces \(a,b\in a/R\), lo cual nos dice que \(aR_{A/R}b\).
El teorema anterior muestra que a nivel de información es lo mismo tener una relación de equivalencia sobre \(A\) que tener una partición de \(A\). Esto es muy útil ya que muchas veces es mas fácil especificar una relación de equivalencia vía su partición asociada. Por ejemplo si hablamos de la relación de equivalencia sobre \(\{1,2,3,4,5\}\) dada por la partición \[\mathcal{P}=\{\{1,5\},\{4\},\{2,3\}\}\] nos estaremos refiriendo a \(R_{\mathcal{P}}\), es decir a la relación: \[\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,5),(5,1),(2,3),(3,2)\}\]
Supongamos \(R\) es una relación de equivalencia sobre \(\mathbf{R}\) y supongamos definimos una función \(f:\mathbf{R}/R\rightarrow\mathbf{R}\) de la siguiente manera: \[f(r/R)=r^{2}\] A priori puede parecer que esta definición es natural y que no esconde ninguna posible complicación. Pero veamos que pueden surgir problemas dependiendo de como es \(R\). Supongamos que \(R\) es tal que \(2R6\). Entonces tendríamos que \(2/R=6/R\), lo cual nos diría obviamente que \(f(2/R)=f(6/R)\). Pero \(f(2/R)=2^{2}=4\) y \(f(6/R)=6^{2}=36\), por lo cual debería suceder que \(4\) sea igual a \(36\). El problema aquí es que la ecuación \(f(r/R)=r^{2}\) no esta definiendo en forma correcta o inambigua una función ya que el supuesto valor de la función en una clase de equivalencia dada depende de que representante de la clase usamos para denotarla. Si usamos el 2 la ecuación nos dice que entonces \(f\) debe valer 4 y si usamos el 6 la ecuación nos dice que \(f\) debe valer 36. Claramente no estamos definiendo una función.
Para dar un ejemplo mas concreto de este fenómeno de ambigüedad, supongamos \[R=\{(x,y)\in\mathbf{Z}^{2}:x-y\text{ es multiplo de }2\}\] y definimos una función \(f:\mathbf{Z}/R\rightarrow\mathbf{R}\) de la siguiente manera: \[f(n/R)=1/(n^{2}+1)\] Como ya vimos \(\mathbf{Z}/R=\{\{t\in\mathbf{Z}:t\) es par\(\},\{t\in\mathbf{Z}:t\) es impar\(\}\}\), por lo cual fácilmente se puede llegar a que la ecuación \(f(n/R)=1/(n^{2}+1)\) no define correctamente una función. Por ejemplo, si llamamos \(c\) a la clase \(\{t\in\mathbf{Z}:t\) es par\(\}\) tenemos que la ecuación nos diría que \(f(c)=f(0/R)=1/(0^{2}+1)=1\) y que también \(f(c)=f(2/R)=1/(2^{2}+1)=1/5\).
Sin embargo hay muchos casos en los cuales este tipo de definiciones son inambiguas y desde luego muy importantes en el álgebra moderna. Como un primer ejemplo tenemos el siguiente lema el cual es una de las ideas fundamentales del álgebra moderna.
1.8. Si \(f:A\rightarrow B\), entonces la ecuación \(\bar{f}(a/\ker(f))=f(a)\) define en forma inambigua una función \(\bar{f}:A/\ker(f)\rightarrow B\) la cual es inyectiva. Si \(f\) es suryectiva, entonces \(\bar{f}\) lo es y por lo tanto es una biyección.
Proof. Que la ecuación \(\bar{f}(a/\ker(f))=f(a)\) define sin ambigüedad una función \(\bar{f}:A/\ker(f)\rightarrow B\) es obvio ya que si \(a/\ker(f)=b/\ker(f)\), entonces por definición de \(\ker(f)\) deberá suceder que \(a=b\). Dejamos al lector la prueba de que \(\bar{f}\) es inyectiva. Es obvio que \(f\) y \(\bar{f}\) tienen la misma imagen por lo cual si \(f\) es suryectiva, \(\bar{f}\) lo será.
Sea \(A\) un conjunto. Dado \(n\in\omega\), por una operación \(n\)-aria sobre \(A\) entenderemos una función cuyo dominio es \(A^{n}\) y cuya imagen esta contenida en \(A\). A las operaciones \(2\)-arias (resp. \(3\)-arias, \(4\)-arias) también las llamaremos operaciones binarias (resp. ternarias, cuaternarias). Algunos ejemplos:
adhocprefix(E1)adhocsufix Sea \(f:\mathbf{R\times R}\rightarrow\mathbf{R}\) dada por \(f(x,y)=x+y\). Entonces \(f\) es una operación \(2\)-aria sobre \(\mathbf{R}\)
adhocprefix(E2)adhocsufix Sea \(f:\{\lozenge\}\rightarrow\omega\), dada por \(f(\lozenge)=5\). Entonces \(f\) es una operación \(0\)-aria sobre \(\omega\) (recuerde que \(\omega^{0}=\{\lozenge\}\)).
adhocprefix(E3)adhocsufix Sea \(f:\mathbf{N\times N\times N\times N\times N}\rightarrow\mathbf{N}\), dada por \(f(x_{1},x_{2},x_{3},x_{4},x_{5})=(x_{1}.x_{2})+x_{3}\). Entonces \(f\) es una operación \(5\)-aria sobre \(\mathbf{N}\).
Si \(f\) es una operación \(n\)-aria sobre \(A\) y \(S\subseteq A\), entonces diremos que \(S\) es cerrado bajo \(f\) cuando se dé que \(f(a_{1},...,a_{n})\in S\), cada ves que \(a_{1},...,a_{n}\in S\). Nótese que si \(n=0\), entonces \(S\) es cerrado bajo \(f\) si y solo si \(f(\lozenge)\in S\).
Sea \(A\) un conjunto. Dado \(n\in\omega\), por una relación \(n\)-aria sobre \(A\) entenderemos un subconjunto de \(A^{n}\). A las relaciones \(2\)-arias (resp. \(3\)-arias, \(4\)-arias) también las llamaremos relaciones binarias (resp. ternarias, cuaternarias). Algunos ejemplos:
adhocprefix(E1)adhocsufix Sea \(R=\{(r,t)\in\mathbf{R\times R}:r\leq t\}\). Entonces \(R\) es una relación \(2\)-aria sobre \(\mathbf{R}\)
adhocprefix(E2)adhocsufix Hay exactamente dos relaciones \(0\)-arias sobre \(A\), a saber: \(\emptyset\) y \(\{\lozenge\}\).
adhocprefix(E3)adhocsufix Sea \(R=\{(x_{1},x_{2},x_{3},x_{4},x_{5})\in\mathbf{N}^{5}:x_{5}=x_{4}\}\). Entonces \(R\) es una relación \(5\)-aria sobre \(\mathbf{N}\). Nótese que también \(R\) es una relación \(5\)-aria sobre \(\mathbf{R}\)
adhocprefix(E4)adhocsufix \(\emptyset\) es una relación \(n\)-aria sobre \(A\), cualesquiera sean \(n\in\omega\) y \(A\).
adhocprefix(E5)adhocsufix \(\omega\) es una relación \(1\)-aria sobre \(\mathbf{R}\).
Sea \(\Sigma\) un alfabeto finito. Dados \(n,m\in\omega\), usaremos \(\omega^{n}\times\Sigma^{\ast m}\) para abreviar la expresión \[\overset{n\text{ veces}}{\overbrace{\omega\times...\times\omega}}\times\overset{m\text{ veces}}{\overbrace{\Sigma^{\ast}\times...\times\Sigma^{\ast}}}\] Por ejemplo, \(\omega^{3}\times\Sigma^{\ast4}\) será una forma abreviada de escribir \(\omega\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\). Debe quedar claro que estamos haciendo cierto abuso notacional ya que en principio si no hacemos esta convención notacional, \(\omega^{3}\times\Sigma^{\ast4}\) denota un conjunto de pares y \(\omega\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\) es un conjunto de \(7\)-uplas.
Nótese que:
adhocprefix-adhocsufix Cuando \(n=m=0\), tenemos que \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\{\lozenge\}\)
adhocprefix-adhocsufix Si \(m=0\), entonces \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\omega^{n}\)
adhocprefix-adhocsufix Si \(n=0\), entonces \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\Sigma^{\ast m}\)
adhocprefix-adhocsufix Cuando \(\Sigma=\emptyset\), tenemos que \(\Sigma^{\ast}=\{\varepsilon\}\). O sea que por ejemplo \[\omega^{n}\times\Sigma^{\ast5}=\{(x_{1},...,x_{n},\varepsilon,\varepsilon,\varepsilon,\varepsilon,\varepsilon):x_{1},...,x_{n}\in\omega\}\]
Es decir que tenemos que tener cuidado cuando leemos esta notación y no caer en la confusión de interpretarla mal.
Con esta convención notacional, un elemento genérico de \(\omega^{n}\times\Sigma^{\ast m}\) es una \((n+m)\)-upla de la forma \((x_{1},...,x_{n},\alpha_{1},...,\alpha_{m})\). Para abreviar, escribiremos \((\vec{x},\vec{\alpha})\) en lugar de \((x_{1},...,x_{n},\alpha_{1},...,\alpha_{m})\).
Sea \(\Sigma\) un alfabeto finito. Dada una función \(f\), diremos que \(f\) es \(\Sigma\)-mixta si cumple las siguientes propiedades
adhocprefix(M1)adhocsufix Existen \(n,m\geq0\), tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\)
adhocprefix(M2)adhocsufix Ya sea \(I_{f}\subseteq\omega\) o \(I_{f}\subseteq\Sigma^{\ast}\)
Algunos ejemplos:
adhocprefix(E1)adhocsufix Sea \(\Sigma=\{\square,\%,\blacktriangle\}\). La función \[\begin{array}{rll} f:\{(1,\square\%\%),(100,\%\blacktriangle\blacktriangle)\} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & x+\left\vert \alpha\right\vert \end{array}\] es \(\Sigma\)-mixta ya que se cumple (M1) con \(n=m=1\) y también cumple (M2). Nótese que \(f\) no es \(\{\square,\%\}\)-mixta ya que no cumple (M1) respecto del alfabeto \(\{\square,\%\}\). Sin embargo note que \(f\) es \(\{\square,\%,\blacktriangle,@\}\)-mixta
adhocprefix(E2)adhocsufix La función \[\begin{array}{rll} \omega^{4} & \rightarrow & \omega\\ (x,y,z,w) & \rightarrow & x+y \end{array}\] es \(\Sigma\)-mixta cualesquiera sea el alfabeto \(\Sigma\)
adhocprefix(E3)adhocsufix Sea \(\Sigma=\{\square,@\}\). La función \[\begin{array}{rll} \{\square\square\square,@@\} & \rightarrow & \omega\\ \alpha & \rightarrow & \left\vert \alpha\right\vert \end{array}\]
es \(\Sigma\)-mixta ya que se cumple (M1) (con \(n=0\) y \(m=1\)) y (M2)
adhocprefix(E4)adhocsufix Supongamos \(\Sigma=\emptyset\). Tenemos entonces que \(\Sigma^{\ast}=\{\varepsilon\}\). Por ejemplo \[\begin{array}{rll} D & \rightarrow & \omega\\ (x,\varepsilon,\varepsilon,\varepsilon) & \rightarrow & x^{2} \end{array}\] donde \(D=\{(x,\varepsilon,\varepsilon,\varepsilon):x\) es impar\(\}\), es \(\Sigma\)-mixta (con \(n=1\) y \(m=3\) en (M1)). También nótese que \[\begin{array}{rll} \{(\varepsilon,\varepsilon)\} & \rightarrow & \{\varepsilon\}\\ (\varepsilon,\varepsilon) & \rightarrow & \varepsilon \end{array}\] es \(\Sigma\)-mixta (con \(n=0\) y \(m=2\) en (M1)).
Dejamos al lector la fácil prueba del siguiente resultado básico.
1.9. Supongamos \(\Sigma\subseteq\Gamma\) son alfabetos finitos. Entonces si \(f\) es una función \(\Sigma\)-mixta, \(f\) es \(\Gamma\)-mixta
Una función \(\Sigma\)-mixta \(f\) es \(\Sigma\)-total cuando haya \(n,m\in\omega\) tales que \(D_{f}=\omega^{n}\times\Sigma^{\ast m}\). El lema anterior nos dice que si \(\Sigma\subseteq\Gamma\), entonces toda función \(\Sigma\)-mixta es \(\Gamma\)-mixta. Sin embargo una función puede ser \(\Sigma\)-total y no ser \(\Gamma\)-total, cuando \(\Sigma\subseteq\Gamma\). Por ejemplo tomemos \(\Sigma=\{\square,\%,\blacktriangle\}\) y \(\Gamma=\{\square,\%,\blacktriangle,!\}\), y consideremos la función \[\begin{array}{rll} f:\omega\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & x+\left\vert \alpha\right\vert \end{array}\] Es claro que \(f\) es \(\Sigma\)-mixta y \(\Sigma\)-total. También es \(\Gamma\)-mixta ya que \(D_{f}\subseteq\omega\times\Gamma^{\ast}\) y \(I_{f}\subseteq\omega\), por lo cual cumple (M1) y (M2). Sin embargo \(f\) no es \(\Gamma\)-total ya que \(D_{f}\) no es igual a \(\omega^{n}\times\Gamma^{\ast m}\), cualesquiera sean \(n\) y \(m\).
Como hemos visto recién, una función \(f\) puede ser \(\Sigma\)-mixta y \(\Gamma\)-mixta para dos alfabetos distintos \(\Sigma\) y \(\Gamma\) e incluso es fácil construir un ejemplo en el cual \(\Sigma\) y \(\Gamma\) sean incomparables como conjuntos, es decir que ninguno incluya al otro. Dejamos al lector convencerse de que si \(f\) es una función que es \(\Sigma\)-mixta para algún alfabeto \(\Sigma\), entonces hay un alfabeto \(\Sigma_{0}\) el cual es el menor de todos los alfabetos respecto de los cuales \(f\) es mixta, es decir \(\Sigma_{0}\) cumple que \(f\) es \(\Sigma_{0}\)-mixta y si \(\Gamma\) es tal que \(f\) es \(\Gamma\)-mixta, entonces \(\Sigma_{0}\subseteq\Gamma\).
A continuación daremos algunas funciones \(\Sigma\)-mixtas básicas las cuales serán frecuentemente usadas.
La función sucesor es definida por \[\begin{array}{rll} Suc:\omega & \rightarrow & \omega\\ n & \rightarrow & n+1 \end{array}\] La función predecesor es definida por \[\begin{array}{rll} Pred:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n-1 \end{array}\]
Sea \(\Sigma\) un alfabeto no vacío. Para cada \(a\in\Sigma\), definamos \[\begin{array}{rll} d_{a}:\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ \alpha & \rightarrow & \alpha a \end{array}\] La función \(d_{a}\) es llamada la función derecha sub \(a\), respecto del alfabeto \(\Sigma\).
Sea \(\Sigma\) un alfabeto. Para \(n,m,i\in\omega\) tales que \(1\leq i\leq n\), definamos \[\begin{array}{rll} p_{i}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & x_{i} \end{array}\] Para \(n,m,i\in\omega\) tales que \(n+1\leq i\leq n+m\), definamos \[\begin{array}{rll} p_{i}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \Sigma^{\ast}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \alpha_{i-n} \end{array}\] Las funciones \(p_{i}^{n,m}\) son llamadas proyecciones. La función \(p_{i}^{n,m}\) es llamada la proyección \(n,m,i\), respecto del alfabeto \(\Sigma\). Nótese que esta definición requiere que \(n+m\geq1\) ya que \(i\) debe cumplir \(1\leq i\leq n+m\). Además nótese que siempre la función \(p_{i}^{n,m}\) aplicada a una \((n+m)\)-upla da la coordenada \(i\)-ésima de dicha \((n+m)\)-upla. Por ejemplo: \[\begin{array}{rll} p_{3}^{1,3}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ (x,\alpha_{1},\alpha_{2},\alpha_{3}) & \rightarrow & \alpha_{2} \end{array}\]
Sea \(\Sigma\) un alfabeto. Para \(n,m,k\in\omega\), y \(\alpha\in\Sigma^{\ast}\), definamos \[\begin{array}{rll} C_{k}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & k \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} C_{\alpha}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \Sigma^{\ast}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \alpha \end{array}\] Por ejemplo: \[\begin{array}{rll} C_{3}^{1,3}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha_{1},\alpha_{2},\alpha_{3}) & \rightarrow & 3 \end{array}\ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} C_{\varepsilon}^{1,3}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ (x,\alpha_{1},\alpha_{2},\alpha_{3}) & \rightarrow & \varepsilon \end{array}\] Nótese que \(C_{k}^{0,0}:\{\lozenge\}\rightarrow\{k\}\) y que \(C_{\alpha}^{0,0}:\{\lozenge\}\rightarrow\{\alpha\}\).
Definamos \[\begin{array}{rll} pr:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n\text{-esimo número primo} \end{array}\] Nótese que \(pr(1)=2\), \(pr(2)=3\), \(pr(3)=5\), etc.
Dada una función \(\Sigma\)-mixta \(f\), si \(n,m\in\omega\) son tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\) y además \(I_{f}\subseteq\omega\), entonces diremos que \(f\) es una función de tipo \((n,m,\#)\). Similarmente si \(n,m\in\omega\) son tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\) y además \(I_{f}\subseteq\Sigma^{\ast}\), entonces diremos que \(f\) es una función de tipo \((n,m,\ast)\). Nótese que si \(f\neq\emptyset\), entonces hay únicos \(n,m\in\omega\) y \(s\in\{\#,\ast\}\) tales que \(f\) es una función de tipo \((n,m,s)\). Sin embargo \(\emptyset\) es una función de tipo \((n,m,s)\) cualesquiera sean \(n,m\in\omega\) y \(s\in\{\#,\ast\}\). De esta forma, cuando \(f\neq\emptyset\) hablaremos de "el tipo de \(f\)" para referirnos a esta única terna \((n,m,s)\). Nótese que \(Suc\) es de tipo \((1,0,\#)\) y \(d_{a}\) es de tipo \((0,1,\ast)\).
También nótese que la relación "\(f\) es una función de tipo \((n,m,s)\)" no depende del alfabeto \(\Sigma\) (que significa esto?).
Supongamos que \(k,l,n,m\in\omega\) y que \(F:D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega^{n}\times\Sigma^{\ast m}\). Supongamos además que \(n+m\geq1\). Entonces denotaremos con \(F_{(i)}\) a la función \(p_{i}^{n,m}\circ F\). Notar que \[\begin{aligned} F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega\text{, para cada }i=1,...,n\\ F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\Sigma^{\ast}\text{, para cada }i=n+1,...,n+m \end{aligned}\] Por lo cual cada una de las funciones \(F_{(i)}\) son \(\Sigma\)-mixtas. Además nótese que \[F=[F_{(1)},...,F_{(n+m)}]\]
Un predicado \(\Sigma\)-mixto es una función \(f\) la cual es \(\Sigma\)-mixta y además cumple que \(I_{f}\subseteq\{0,1\}\). Por ejemplo \[\begin{array}{rll} \omega\times\omega & \rightarrow & \omega\\ (x,y) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=y\\ 0\text{ si }x\neq y \end{array}\right. \end{array}\ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} \{1,2,3,4,5\}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=\left\vert \alpha\right\vert \\ 0\text{ si }x\neq\left\vert \alpha\right\vert \end{array}\right. \end{array}\]
Dados predicados \(P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}\) y \(Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}\), con el mismo dominio, definamos nuevos predicados \((P\vee Q)\), \((P\wedge Q)\) y \(\lnot P\) de la siguiente manera \[\begin{array}{rll} (P\vee Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ o }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\] \[\begin{array}{rll} (P\wedge Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ y }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\] \[\begin{array}{rll} \lnot P:S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=0\\ 0 & & \text{si }P(\vec{x},\vec{\alpha})=1 \end{array}\right. \end{array}\]
Dado un alfabeto \(\Sigma\), una familia \(\Sigma\)-indexada de funciones será una función \(\mathcal{G}\) tal que \(D_{\mathcal{G}}=\Sigma\) y para cada \(a\in D_{\mathcal{G}}\) se tiene que \(\mathcal{G}(a)\) es una función. Algunos ejemplos:
adhocprefix(E1)adhocsufix Sea \(\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 \(\mathcal{G}\) es una familia \(\{\square,\%,\blacktriangle\}\)-indexada de funciones. Notar que \[\mathcal{G}=\{(\square,Suc),(\%,Suc),(\blacktriangle,Pred)\}\] Se tiene también por ejemplo que \(\mathcal{G}(\%)=Suc\) por lo cual también es cierto que \(\mathcal{G}(\%)(22)=23\), etc.
adhocprefix(E2)adhocsufix Si \(\Sigma\) es un alfabeto no vacío, la función \[\begin{array}{rcl} \mathcal{G}:\Sigma & \rightarrow & \{f:f\text{ es una función de }\Sigma^{\ast}\text{ en }\Sigma^{\ast}\}\\ a & \rightarrow & d_{a} \end{array}\] es una familia \(\Sigma\)-indexada de funciones. Notar que \[\mathcal{G}=\{(a,d_{a}):a\in\Sigma\}\]
adhocprefix(E3)adhocsufix \(\emptyset\) es una flia \(\emptyset\)-indexada de funciones
Si \(\mathcal{G}\) es una familia \(\Sigma\)-indexada de funciones, entonces para \(a\in\Sigma\), escribiremos \(\mathcal{G}_{a}\) en lugar de \(\mathcal{G}(a)\).
Un conjunto \(S\) es llamado \(\Sigma\)-mixto si hay \(n,m\in\omega\) tales que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Por ejemplo, \[\{(x,\alpha)\in\omega\times\{\blacktriangle,!\}^{\ast}:\left\vert \alpha\right\vert =x\}\] \[\{(0,\blacktriangle\blacktriangle\blacktriangle,\varepsilon),(1,\%\blacktriangle\%,\blacktriangle\blacktriangle)\}\] son conjuntos \(\{\blacktriangle,\%,!\}\)-mixtos. También nótese que \(\emptyset\) y \(\{\lozenge\}\) son conjuntos \(\Sigma\)-mixtos, cualesquiera sea el alfabeto \(\Sigma\). Por último el conjunto \[\{(x,\varepsilon,\varepsilon,\varepsilon):x\in\omega\text{ y }x\text{ es impar}\}\] es \(\emptyset\)-mixto (con \(n=1\) y \(m=3\)).
Dado un conjunto \(\Sigma\)-mixto \(S\), si \(n,m\in\omega\) son tales que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\), entonces diremos que \(S\) es un conjunto de tipo \((n,m)\). Nótese que si \(S\neq\emptyset\), entonces hay únicos \(n,m\in\omega\) tales que \(S\) es un conjunto de tipo \((n,m)\). De esta forma, cuando \(S\neq\emptyset\) hablaremos de "el tipo de \(S\)" para referirnos a este único par \((n,m)\). También es importante notar que de la definición anterior sale inmediatamente que \(\emptyset\) es un conjunto de tipo \((n,m)\) cualesquiera sean \(n,m\in\omega\), por lo cual cuando hablemos de EL tipo de un conjunto deberemos estar seguros de que dicho conjunto es no vacío.
Nótese que \(\omega\) es de tipo \((1,0)\) y \(\Sigma^{\ast}\) es de tipo \((0,1)\).
Un conjunto \(\Sigma\)-mixto \(S\) es llamado rectangular si es de la forma \[S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m},\] con cada \(S_{i}\subseteq\omega\) y cada \(L_{i}\subseteq\Sigma^{\ast}\). Notar que todo subconjunto de \(\omega\) es rectangular (es el caso \(n=1\) y \(m=0\)). También \(\{\lozenge\}\) es rectangular (es el caso \(n=m=0\)). Otros ejemplos:
adhocprefix-adhocsufix \(\mathbf{N}\times\{1,2\}\times\{@@,\varepsilon\}\) es rectangular (aquí \(n=2\) y \(m=1\))
adhocprefix-adhocsufix \(\{!!!,!!\}\times\{@@,\varepsilon\}\) es rectangular (aquí \(n=0\) y \(m=2\))
También nótese que \(\emptyset=\emptyset\times\emptyset\) por lo cual \(\emptyset\) es un conjunto rectangular.
El concepto de conjunto rectangular es muy importante en nuestro enfoque. Aunque en general no habrá restricciones acerca del dominio de las funciones y predicados, nuestra filosofía será tratar en lo posible que los dominios de las funciones que utilicemos para hacer nuestro análisis de recursividad de los distintos paradigmas, sean rectangulares. Aunque en principio puede parecer que todos los conjuntos son rectangulares, el siguiente lema mostrara cuan ingenua es esta visión.
1.10. Sea \(S\subseteq\omega\times\Sigma^{\ast}\). Entonces \(S\) es rectangular si y solo si se cumple la siguiente propiedad:
adhocprefix(R)adhocsufix Si \((x,\alpha),(y,\beta)\in S\), entonces \((x,\beta)\in S\)
Proof. Ejercicio.
Supongamos \(\Sigma=\{\#,\blacktriangle,\%\}\). Nótese que podemos usar el lema anterior para probar por ejemplo que los siguientes conjuntos no son rectangulares
adhocprefix-adhocsufix \(\{(0,\#\#),(1,\%\%\%)\}\)
adhocprefix-adhocsufix \(\{(x,\alpha):\left\vert \alpha\right\vert =x\}\)
Dejamos como ejercicio para el lector enunciar un lema análogo al anterior pero que caracterice cuando \(S\subseteq\omega^{2}\times\Sigma^{\ast3}\) es rectangular.
Usaremos la notación lambda de Church en la forma que se explica a continuación. La idea de usar la notación lambda fue sacada del libro de Bell y Machover. Esta notación siempre depende de un alfabeto finito previamente fijado. En general en nuestro lenguaje matemático utilizamos diversas expresiones las cuales involucran variables que una vez fijadas en sus valores hacen que la expresión también represente un determinado valor. No definiremos en forma precisa el concepto de expresión pero debería quedar claro que una expresión como objeto es una palabra. Podriamos pensar que una expresión es una palabra la cual tiene algún significado matemático. Obviamente esta es una descripción intuitiva y no precisa del concepto de expresión pero a los fines del uso que nosotros daremos a este concepto nos será suficiente.
En el contexto de la notación lambda solo se podrán utilizar expresiones con características muy especiales por lo cual a continuación iremos describiendo que condiciones tienen que cumplir las expresiones para que puedan ser usadas en la notación lambda.
adhocprefix(1)adhocsufix Solo utilizaremos expresiones que involucran variables numéricas, las cuales se valuarán en números de \(\omega\), y variables alfabéticas, las cuales se valuaran en palabras del alfabeto previamente fijado. Las variables numéricas serán 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 alfabéticas serán seleccionadas de la lista \[\begin{aligned} & \alpha,\beta,\gamma,\eta,...\\ & \alpha_{1},\alpha_{2},...\\ & \beta_{1},\beta_{2},...\\ & etc \end{aligned}\]
adhocprefix(2)adhocsufix Por ejemplo la expresión: \[x+y+1\] tiene dos variables numéricas \(x\) e \(y\) (y ninguna alfabética). Si le asignamos a \(x\) el valor 2 y a \(y\) el valor 45, entonces la expresión \(x+y+1\) produce o representa el valor \(48=2+45+1\).
adhocprefix(3)adhocsufix Otro ejemplo, consideremos la expresión \[\left\vert \alpha\beta\right\vert +\left\vert \alpha\right\vert ^{x}\] la cual tiene una variable numérica \(x\) y dos variables alfabéticas \(\alpha\) y \(\beta\). Supongamos además que el alfabeto previamente fijado es \(\{@,\%\}\). Si le asignamos a \(x\) el valor 2, a \(\alpha\) el valor \(@@\) y a \(\beta\) el valor \(\%\%\%\), entonces la expresión \(\left\vert \alpha\beta\right\vert +\left\vert \alpha\right\vert ^{x}\) produce o representa el valor \(\left\vert @@\%\%\%\right\vert +\left\vert @@\right\vert ^{2}=9\).
adhocprefix(4)adhocsufix Para ciertas valuaciones de sus variables la expresión puede no estar definida en el sentido que cuando reemplazamos en ella dichos valores la palabra obtenida no representa en forma precisa un objeto. Por ejemplo la expresión \[Pred(\left\vert \alpha\right\vert )\] cuando le asignamos a \(\alpha\) la palabra \(\varepsilon\), nos queda la expresión \(Pred(\left\vert \varepsilon\right\vert )\) la cual no representa un objeto matemático en forma precisa. Otro ejemplo, consideremos la expresión \[x/(y-\left\vert \alpha\right\vert )^{2}\] Esta expresión no esta definida o no asume valor para aquellas asignaciones de valores a sus variables en las cuales el valor asignado a \(y\) sea igual a la longitud del valor asignado a \(\alpha\). Un último ejemplo, la expresión \[x/y/z\] no esta definida en forma precisa cuando le damos a \(x,y,z\) los valores \(100,10,5\) ya que nos queda la expresión \(100/10/5\) la cual es imprecisa puesto que es ambigua ya que no sabemos en que orden dividir.
adhocprefix(5)adhocsufix En los ejemplos anteriores las expresiones producen valores numéricos pero también trabajaremos con expresiones que producen valores alfabéticos. Por ejemplo la expresión \[\beta^{y}\] tiene una variable numérica, \(y\), una variable alfabética, \(\beta\), y una vez valuadas estas variables produce un valor alfabético, a saber el resultado de elevar el valor asignado a la variable \(\beta\), a el valor asignado a \(y\).
adhocprefix(6)adhocsufix También consideraremos expresiones en las cuales no ocurren variables, es decir ellas representan un valor concreto. Por ejemplo la expresión \[5\] siempre produce el valor \(5\). O la expresión \[17+11\] siempre produce el valor 28. También la expresión \[1/0\] no tiene variables y además es siempre indefinida. Es decir no representa un valor u objeto.
adhocprefix(7)adhocsufix Una expresión \(E\) para poder ser utilizada en la notación lambda relativa a un alfabeto \(\Sigma\) deberá cumplir alguna de las dos siguientes propiedades
los valores que asuma \(E\) cuando hayan sido asignados valores de \(\omega\) a sus variables numéricas y valores de \(\Sigma^{\ast}\) a sus variables alfabéticas deberán ser siempre elementos de \(\omega\)
los valores que asuma \(E\) cuando hayan sido asignados valores de \(\omega\) a sus variables numéricas y valores de \(\Sigma^{\ast}\) a sus variables alfabéticas deberán ser siempre elementos de \(\Sigma^{\ast}\)
Cabe destacar que la expresión \(E\) puede, para alguna asignación de valores de \(\omega\) a sus variables numéricas y valores de \(\Sigma^{\ast}\) a sus variables alfabéticas, no estar definida o representar en forma precisa algún objeto matemático.
adhocprefix(8)adhocsufix Por ejemplo la expresión \[x/2\] no cumple la propiedad dada en (7) ya que para ciertos valores de \(\omega\) asignados a la variable \(x\), la expresión da valores numéricos que se salen de \(\omega\) por lo cual no cumple ni (a) ni (b).
adhocprefix(9)adhocsufix Otro ejemplo, si el alfabeto fijado es \(\Sigma=\{@,\%\}\), entonces la expresión \[@^{x}\$^{y}\] no cumple la propiedad dada en (7) ya que por ejemplo cuando le asignamos a \(x\) el valor 2 y a \(y\) el valor 6, la expresión nos da la palabra \(@@\$\$\$\$\$\$\) la cual no pertenece a \(\Sigma^{\ast}\) por lo cual no cumple ni (a) ni (b).
adhocprefix(10)adhocsufix No necesariamente las expresiones que usaremos en la notación lambda deben ser hechas como combinación de operaciones matemáticas conocidas. Muchas veces usaremos expresiones que involucran incluso lenguaje coloquial castellano. Por ejemplo la expresión \[\mathrm{el\ menor\ n\acute{u}mero\ primo\ que\ es\ mayor\ que\ }x\] Es claro que esta expresión para cada valor de \(\omega\) asignado a la variable \(x\) produce o representa un valor concreto de \(\omega\). Otro ejemplo: \[\mathrm{el\ tercer\ simbolo\ de\ }\alpha\] nótese que esta expresión, una ves fijado un alfabeto \(\Sigma\), estará definida o producirá un valor solo cuando le asignamos a \(\alpha\) una palabra de \(\Sigma^{\ast}\) de longitud mayor o igual a \(3\).
adhocprefix(11)adhocsufix Expresiones Booleanas. A las expresiones Booleanas tales como \[x=y+1\text{ y }\left\vert \alpha\right\vert \leq22\] las pensaremos que asumen valores del conjunto \(\{0,1\}\subseteq\omega\). Por ejemplo la expresión anterior asume o produce el valor \(1\) cuando le asignamos a \(x\) el valor 11, a \(y\) el valor 10 y a \(\alpha\) la palabra \(\varepsilon\). Las expresiones Booleanas pensadas de esta forma podrán ser utilizadas en la notación lambda si es que también cumplen con las anteriores condiciones. Otro ejemplo \[11=17\] es una expresión Booleana que no tiene variables y siempre produce el valor 0.
adhocprefix(12)adhocsufix Seremos muy estrictos en lo que respecta a cuando “una expresión \(E\) esta definida (o representa o produce) en forma precisa un valor, para una valuación dada de sus variables”. El criterio será similar al usado en la tómbola con los vofois en el sentido que la mas mínima imprecisión ya implicara que para esa valuación la expresión no esta definida. Algunos ejemplos:
Consideremos la expresión \[0.Suc(z,z)\] Uno podría pensar que cualquiera sea el valor de \(\omega\) asignado a la variable \(z\), la expresión produce el valor \(0\), ya que cualquiera sea el valor de \(Suc(z,z)\), al multiplicarlo por \(0\) nos dará \(0\). Sin embargo para nosotros la expresión \(0.Suc(z,z)\) no estará definida en forma precisa cualquiera sea el valor que le asignemos a \(z\) y esto es porque \(Suc(z,z)\) tiene una imprecisión ya que \(Suc\) no se aplica a pares ordenados.
Consideremos la expresión \[0.(4/x/2)\] Esta expresión no estará definida en forma precisa para ningún valor de \(x\) ya que la expresión \(4/x/2\) es ambigua puesto que no aclara en que orden se realizan las definiciones. Nótese que aunque al multiplicar por \(0\) podríamos pensar que la expresión produce siempre \(0\), optamos por convenir que la expresión nunca produce en forma precisa valores u objetos.
Consideremos la expresión Booleana \[Pred(0)=1\text{ o }5\leq x\] Uno podría pensar que esta expresión produce el valor \(1\) cuando le asignamos a \(x\) un valor mayor o igual a \(5\) ya que independientemente de que signifique \(Pred(0)=1\) se hace verdadero que \(5\leq x\) por lo cual será verdadero el “o” de ambos enunciados. Sin embargo esta expresión no esta definida en forma precisa para ninguna asignación de valores a \(x\) ya que \(Pred(0)\) es una imprecisión que es parte de la expresión. (O sea sucede lo mismo que en los vofois).
Consideremos la expresión Booleana \[(\forall t\in\emptyset)\text{ }Pred(x).t\text{ es impar}\] Uno podría pensar que esta expresión produce el valor \(1\) independientemente de cuanto vale \(x\) ya que debemos chequear que \(Pred(x).t\) sea impar para \(0\) valores posibles de \(t\). Sin embargo esta expresión no esta definida en forma precisa para el caso en que hacemos valer \(0\) a \(x\) ya que en este caso \(Pred\) no esta definida. Obviamente para cualquier valor de \(\mathbf{N}\) que asignemos a \(x\) la expresión produce en forma precisa el valor \(1\)
Dado un alfabeto \(\Sigma\) a las expresiones que cumplan las características dadas anteriormente las llamaremos lambdificables con respecto a \(\Sigma\). Nótese que este concepto es intuitivo y no un concepto matemáticamente definido en forma precisa. Mas aun el concepto de expresión tampoco ha sido definido matemáticamente (aunque obviamente si sabemos que una expresión es una palabra de cierto alfabeto). Esto no nos traerá problemas para el uso notacional que las utilizaremos. Recién en las secciones de lógica veremos la matematización de ciertas expresiones (no las lambdificables) y nos servirá de ejemplo para imaginar como podríamos matematizar el concepto de expresión lambdificable.
Algunos ejemplos:
adhocprefix(E1)adhocsufix \(x/2\) no es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
adhocprefix(E2)adhocsufix \(@^{x}\$^{y}\) es lambdificable con respecto a \(\{@,\$\}\) y no es lambdificable con respecto a \(\{@,\#,\%\}\)
adhocprefix(E3)adhocsufix \(x=y+1\) es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
adhocprefix(E4)adhocsufix la expresión \[\mathrm{el\ menor\ n\acute{u}mero\ primo\ que\ es\ mayor\ que\ }x^{\left\vert \beta\right\vert }\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
adhocprefix(E5)adhocsufix la expresión \[5\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
adhocprefix(E6)adhocsufix la expresión \[Suc(x/20)\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\). Nótese que esta expresión no esta definida o no asume valor para aquellas asignaciones de valores a \(x\) en las cuales \(x/20\) no sea un elemento de \(\omega\) ya que en estos casos \(x/20\) no pertenece al dominio de \(Suc\). Mas concretamente dicha expresión esta definida o produce un valor cuando le asignamos a \(x\) un valor múltiplo de \(20\). Nótese que sin embargo, la expresión \[(x/20)+1\] no es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\) (por que?).
Supongamos ya hemos fijado un alfabeto finito \(\Sigma\) y supongamos \(E\) es una expresión la cual es lambdificable con respecto a \(\Sigma\). Sea \(x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\) (con \(n,m\in\omega\)) una lista de variables todas distintas tal que las variables numéricas que ocurren en \(E\) están todas contenidas en la lista \(x_{1},...,x_{n}\) y las variables alfabéticas que ocurren en \(E\) están en la lista \(\alpha_{1},...,\alpha_{m}\) (puede suceder que haya variables de la lista \(x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\) las cuales no ocurran en \(E\)). Entonces \[\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\] denotará la función definida por:
adhocprefix(L1)adhocsufix El dominio de \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\) es el conjunto de las \((n+m)\)-uplas \((k_{1},...,k_{n},\beta_{1},...,\beta_{m})\in\omega^{n}\times\Sigma^{\ast m}\) tales que \(E\) esta definida en forma precisa cuando le asignamos a cada \(x_{i}\) el valor \(k_{i}\) y a cada \(\alpha_{i}\) el valor \(\beta_{i}\).
adhocprefix(L2)adhocsufix \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right](k_{1},...,k_{n},\beta_{1},...,\beta_{m})=\) valor que asume, produce o representa \(E\) cuando le asignamos a cada \(x_{i}\) el valor \(k_{i}\) y a cada \(\alpha_{i}\) el valor \(\beta_{i}\).
Nótese que por tener \(E\) la propiedad (7) de mas arriba, la función \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\) es \(\Sigma\)-mixta de tipo \((n,m,s)\) para algún \(s\in\{\#,\ast\}\). También nótese que cuando \(n=m=0\) la expresión \(E\) deberá no tener variables y \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\) pasara a ser \(\lambda\left[E\right]\). Además \(\lambda\left[E\right]\) será la función vacía cuando \(E\) no produzca o represente un valor y en caso contrario \(\lambda\left[E\right]\) tendrá dominio igual a \(\{\lozenge\}\). Algunos ejemplos:
adhocprefix(a)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{@,?,\)¡\(\}\). Entonces \(\lambda x\alpha\left[\alpha^{2x}\right]\) es la función \[\begin{array}{rll} \omega\times\{@,?,\text{¡}\}^{\ast} & \rightarrow & \{@,?,\text{¡}\}^{\ast}\\ (x,\alpha) & \rightarrow & \alpha^{2x} \end{array}\] Aquí el lector puede notar la dependencia de la notación lambda respecto del alfabeto fijado. Si en lugar de fijar \(\Sigma=\{@,?,\)¡\(\}\) hubiéramos fijado \(\Sigma=\{\%\}\), entonces \(\lambda x\alpha\left[\alpha^{2x}\right]\) denotaría otra función, a saber \[\begin{array}{rll} \omega\times\{\%\}^{\ast} & \rightarrow & \{\%\}^{\ast}\\ (x,\alpha) & \rightarrow & \alpha^{2x} \end{array}\]
adhocprefix(b)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{@,?,\)¡\(\}\). Entonces \(\lambda x\alpha\left[5\right]\) es la función \[\begin{array}{rll} \omega\times\{@,?,\text{¡}\}^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & 5 \end{array}\]
adhocprefix(c)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{\%,!\}\). Entonces \(\lambda\alpha\beta\left[\alpha\beta\right]\) es la función \[\begin{array}{rll} \{\%,!\}^{\ast}\times\{\%,!\}^{\ast} & \rightarrow & \{\%,!\}^{\ast}\\ (\alpha,\beta) & \rightarrow & \alpha\beta \end{array}\]
También tenemos que \(\lambda\beta\alpha\left[\alpha\beta\right]\) es la función \[\begin{array}{rll} \{\%,!\}^{\ast}\times\{\%,!\}^{\ast} & \rightarrow & \{\%,!\}^{\ast}\\ (\beta,\alpha) & \rightarrow & \alpha\beta \end{array}\] Nótese que estas funciones son distintas. Por ejemplo \(\lambda\alpha\beta\left[\alpha\beta\right](\%,!)=\%!\) y \(\lambda\beta\alpha\left[\alpha\beta\right](\%,!)=!\%\)
adhocprefix(d)adhocsufix Independientemente de quien sea \(\Sigma\) el alfabeto previamente fijado, tenemos que \(\lambda xy[x+y]\) es la función \[\begin{array}{rll} \omega^{2} & \rightarrow & \omega\\ (x,y) & \rightarrow & x+y \end{array}\] También \(\lambda xyzw[x+w]\) es la función \[\begin{array}{rll} \omega^{4} & \rightarrow & \omega\\ (x,y,z,w) & \rightarrow & x+w \end{array}\]
adhocprefix(e)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{@,?,\)¡\(\}\). Entonces por la clausula (L1) tenemos que el dominio de la función \(\lambda xy\alpha\beta\left[Pred(\left\vert \alpha\right\vert )+Pred(y)\right]\) es \[D=\left\{ (x,y,\alpha,\beta)\in\omega^{2}\times\Sigma^{\ast2}:\left\vert \alpha\right\vert \geq1\text{ y }y\geq1\right\}\] Es decir que \(\lambda xy\alpha\beta\left[Pred(\left\vert \alpha\right\vert )+Pred(y)\right]\) es la función \[\begin{array}{rll} D & \rightarrow & \omega\\ (x,y,\alpha,\beta) & \rightarrow & Pred(\left\vert \alpha\right\vert )+Pred(y) \end{array}\]
adhocprefix(f)adhocsufix Atentos a (11) de mas arriba, la función \(\lambda xy\left[x=y\right]\) es el predicado \[\begin{array}{rll} \omega\times\omega & \rightarrow & \omega\\ (x,y) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=y\\ 0\text{ si }x\neq y \end{array}\right. \end{array}\] y \(\lambda x\alpha\left[Pred(x)=\left\vert \alpha\right\vert \right]\) es el predicado \[\begin{array}{rll} \mathbf{N}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }Pred(x)=\left\vert \alpha\right\vert \\ 0\text{ si }Pred(x)\neq\left\vert \alpha\right\vert \end{array}\right. \end{array}\] También \(\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}\]
adhocprefix(g)adhocsufix Notar que para \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) se tiene que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}=\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[(\vec{x},\vec{\alpha})\in S\right]\)
adhocprefix(h)adhocsufix Como dijimos, la notación lambda depende del alfabeto previamente fijado, aunque para el caso en que la lista de variables que sigue a la letra \(\lambda\) no tenga variables alfabéticas, la función representada no depende del alfabeto.
adhocprefix(i)adhocsufix La función \(\lambda x\left[Suc(x/20)\right]\) es la siguiente función: \[\begin{array}{rll} \{x\in\omega:20\text{ divide a }x\} & \rightarrow & \omega\\ x & \rightarrow & x+1 \end{array}\]
adhocprefix(j)adhocsufix La función \(\lambda\left[5\right]\) es la función \[\begin{array}{rll} \{\lozenge\} & \rightarrow & \omega\\ \lozenge & \rightarrow & 5 \end{array}\]
adhocprefix(k)adhocsufix La función \(\lambda\left[1/0\right]\) es la función vacía, es decir \(\lambda\left[1/0\right]=\emptyset\)
adhocprefix(l)adhocsufix La función \(\lambda\left[11=17\right]\) es la función \[\begin{array}{rll} \{\lozenge\} & \rightarrow & \omega\\ \lozenge & \rightarrow & 0 \end{array}\]
Algunos ejemplos sutiles
adhocprefix(a)adhocsufix La expresión \[Suc\] no es lambdificable respecto de cualquier alfabeto \(\Sigma\). Esto es porque si bien cualesquiera sea el valor asignado a las variables, ella asume el valor \(Suc\) (ya que no tiene variables), no cumple (6) de mas arriba ya que \(Suc\) no es un elemento de \(\omega\) ni tampoco una palabra (es una función!)
adhocprefix(b)adhocsufix La expresión \[Suc+(\left\vert \beta\right\vert +1)\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\). Por ejemplo \(\lambda x\beta[Suc+(\left\vert \beta\right\vert +1)]\) es la función \(\emptyset\), ya que la expresión \(Suc+(\left\vert \beta\right\vert +1)\) cualesquiera sean los valores de \(x\) y \(\beta\) no esta definida.
adhocprefix(c)adhocsufix La expresión \[Suc+1\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\) ya que no esta definida nunca y obtenemos entonces que \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}[Suc+1]\) es la función \(\emptyset\), cualesquiera sean las variables \(x_{1}...x_{n}\alpha_{1}...\alpha_{m}\). En particular \(\lambda[Suc+1]=\emptyset\).