En general en nuestro lenguaje matemático utilizamos diversas expresiones las cuales involucran variables y las cuales tienen la propiedad que cuando a sus variables les asignamos ciertos objetos matemáticos concretos, entonces la expresión produce o representa en forma precisa e inambigua un determinado objeto matemático. También puede suceder que para cierta otra elección de objetos matemáticos asignados a sus variables la expresión no represente en forma precisa e inambigua un objeto matemático. Veamos algunos ejemplos
adhocprefix(2)adhocsufix La expresión: \[x+y\] tiene dos variables (\(x\) e \(y\)). Si le asignamos a \(x\) el numero 2 y a \(y\) el numero 45, entonces la expresión \(x+y\) produce o representa el valor \(47\) (\(=2+45\)). Pero cuando le asignamos a \(x\) el conjunto \(\{5,6\}\) y a \(y\) el numero \(45\), esta expresión no produce o representa de forma precisa ningún objeto matemático ya que en principio no esta claro que significaría \(\{5,6\}+45\).
adhocprefix(3)adhocsufix La expresión \[\alpha^{x}\] tiene dos variables (\(x\) y \(\alpha\)). Si le asignamos a \(x\) el numero \(2\) y a \(\alpha\) la palabra \(@@\%\%\%\) entonces la expresión \(\alpha^{x}\) produce o representa la palabra \(@@\%\%\%@@\%\%\%\) (\(=(@@\%\%\%)^{2}\)). Sin embargo, si le asignamos a \(x\) el numero \(-10\) y a \(\alpha\) la palabra \(@@\%\%\%\) entonces la expresión \(\alpha^{x}\) no produce o representa en forma precisa ningún objeto matemático ya que en principio no esta claro que representaría la expresión \((@@\%\%\%)^{-10}\).
adhocprefix(4)adhocsufix La expresión \[\text{el mayor primo menor que }x\] tiene una sola variable (\(x\)). Si le asignamos a \(x\) el numero 16, entonces esta expresión produce o representa el numero \(13\) ya que \(13\) es el mayor número primo menor que \(16\). Pero cuando le asignamos a \(x\) la función \(Suc\), no representa ningún objeto matemático ya que no tiene sentido hablar del mayor primo menor que \(Suc\).
adhocprefix(4)adhocsufix La expresión \[\{x,Suc\}\times\{y\}\] tiene dos variables (\(x\) e \(y\)). Si le asignamos a \(x\) el numero 2 y a \(y\) el numero \(20\) entonces esta expresión produce o representa el conjunto \(\{(2,20),(Suc,20)\}\) (\(=\{2,Suc\}\times\{20\}\)). Cabe destacar que esta expresión siempre representa en forma precisa e inambigua un objeto matemático, cualquiera sean los objetos asignados a sus variables.
adhocprefix(4)adhocsufix La expresión \[X\cup Y\] tiene dos variables (\(X\) y \(Y\)). Si le asignamos a \(X\) el conjunto \(\{100,1\}\) y a \(Y\) el conjunto \(\{20,90\}\) entonces esta expresión produce o representa el conjunto \(\{100,1,20,90\}\). Pero si le asignamos a \(X\) el numero \(20\) y a \(Y\) la palabra \(@@@@\) entonces esta expresión no produce o representa un objeto matemático ya que en principio no hemos definido que significa \(20\cup@@@@\) ya que la operación unión solo se aplica a conjuntos.
Tambien hay expresiones que no involucran variables y en tal caso la expresión deberá representar directamente, en forma precisa y sin ambiguedad un objeto matemático concreto. Ejemplos:
adhocprefix(4)adhocsufix \(100\)
adhocprefix(4)adhocsufix \(\text{el mayor número primo perteneciente a }\{1,2,...,100\}\)
adhocprefix(4)adhocsufix \(5^{4}+347+6^{100}\)
adhocprefix(4)adhocsufix \(Suc\)
adhocprefix(4)adhocsufix \(\mathbf{N}\times\omega\)
adhocprefix(4)adhocsufix \(@^{20}!^{100}\)
adhocprefix(4)adhocsufix \(Suc\circ Pred\)
adhocprefix(4)adhocsufix \((Suc\circ Pred)(5+6+7+11^{100})\)
Otro tipo de expresiones son aquellas que involucran variables pero las cuales, para ciertas asignaciones de objetos concretos a sus variables, se vuelven un enunciado matemático preciso el cual es ya sea verdadero o falso (aunque puede suceder que para ciertas otras asignaciones de elementos concretos a sus variables esto no suceda). Algunos ejemplos
adhocprefix(1)adhocsufix La expresión \[x=y+1\] cuando le asignamos a \(x\) el objeto \(11\) y a \(y\) el objeto \(10\), ella se vuelve un enunciado matemático preciso y verdadero, a saber \[11=10+1\] Tambien si le asignamos a \(x\) el objeto \(1\) y a \(y\) el objeto \(2\), ella se vuelve un enunciado matemático preciso y falso, a saber \[1=2+1\] Nótese que si le asignamos a \(x\) el objeto \(\{100,1000\}\) y a \(y\) el objeto \(\{5\}\), esta expresión produce \[\{100,1000\}=\{5\}+1\] lo cual no puede ser considerado un enunciado matemático preciso ya que no hemos definido en forma precisa en nuestra matemática que significa \(\{5\}+1\). Tampoco produce o representa un enunciado matemático preciso cuando le asignamos a \(x\) el objeto \(Suc\) y a \(y\) el objeto \(Pred\) ya que no hemos definido en forma precisa en nuestra matemática que significa \(Pred+1\).
adhocprefix(1)adhocsufix La expresión \[x=y\] cualquiera sean los objetos matemáticos concretos que les asignemos a las variables \(x\) e \(y\) siempre producirá un enunciado matemático preciso, a saber el enunciado que dice que dichos objetos son iguales.
adhocprefix(1)adhocsufix La expresión \[Pred(x)=5\text{ y }x\leq z+u\] cuando le asignamos a \(x\) un el objeto \(10\), a \(z\) el objeto \(0\) y a \(u\) el objeto \(9\) produce el enunciado matemático \[Pred(10)=5\text{ o }10\leq0+9\] el cual es claramente falso. Si le asignamos a \(x\) el objeto \(0\), a \(z\) el objeto \(0\) y a \(u\) el objeto \(9\) dicha expresión produce la oración \[Pred(0)=5\text{ o }0\leq0+9\] la cual no es un enunciado matemático ya que tiene la imprecisión de aplicar \(Pred\) a \(0\) y \(0\notin D_{Pred}\). Nótese que esto sucederá siempre que asignemos a \(x\) un objeto que no esta en el dominio de \(Pred\). Si le asignamos a \(x\) el objeto \(100\), a \(z\) el objeto \(\{5,9\}\) y a \(u\) el objeto \(Suc\) dicha expresión produce la oración \[Pred(100)=5\text{ o }100\leq\{5,9\}+Suc\] la cual no es un enunciado matemático ya que no hemos definido que significa matemáticamente \(\{5,9\}+Suc\).
adhocprefix(1)adhocsufix La expresión \[(\exists y\in\mathbf{N})\text{ }x=y^{2}\] cuando le asignamos a \(x\) el objeto \(10\), produce o representa el objeto \(0\) ya que el enunciado \[(\exists y\in\mathbf{N})\text{ }10=y^{2}\] es falso. Cuando le asignamos a \(x\) el objeto \(\{1,9\}\), produce o representa el objeto \(0\) ya que el enunciado \[(\exists y\in\mathbf{N})\text{ }\{1,9\}=y^{2}\] es falso. Notese que esta expresion siempre produce o representa en forma precisa un objeto matematico (\(0\) o \(1\)) cualquiera sea el objeto que le asignamos a \(x\)
Si usamos los numeros \(0\) y \(1\) para representar verdadero y falso respectivamente, entonces podemos pensar que cuando estas expresiones producen un enunciado matematico preciso ellas producen ya sea el objeto \(0\) o el objeto \(1\), dependiendo de que dicho enunciado sea falso o verdadero, respectivamente. De esta manera este tipo de expresiones se comportan en forma analoga a las vistas en los ejemplos (1),...,(100) en el sentido que bajo ciertas asignaciones producen o representan en forma precisa objetos matematicos concretos. Veamos algunos ejemplos:
adhocprefix(1)adhocsufix La expresion \[x=y+1\] representa asume o produce el valor \(1\) cuando le asignamos a \(x\) el valor 11 y a \(y\) el valor 10. Notese que si le asignamos a \(x\) el objeto \(\{100,1000\}\) y a \(y\) el objeto \(\{5\}\), esta expresion no produce o representa un objeto matematico concreto ya que no hemos definido en forma precisa en nuestra matematica que significa \(\{5\}+1\). Tampoco produce o representa un objeto matematico concreto cuando le asignamos a \(x\) el objeto \(Suc\) y a \(y\) el objeto \(Pred\) ya que no hemos definido en forma precisa en nuestra matematica que significa \(Pred+1\).
adhocprefix(1)adhocsufix La expresion \[\text{ el mayor elemento de \ensuremath{\{1,5,7,17\}}es igual a }x\] representa asume o produce el valor \(1\) cuando le asignamos a \(x\) el valor \(17\). Si le asignamos a \(x\) el objeto \(\{100,1000\}\) la expresion produce o representa el objeto \(0\) ya que \(17\) no es igual a \(\{100,1000\}\). Notese que esta expresion siempre produce o representa en forma precisa un objeto matematico (\(0\) o \(1\)) cualquiera sea el objeto que le asignamos a \(x\)
adhocprefix(1)adhocsufix La expresion \[Pred(x)=5\text{ o }x\leq z+u\] cuando le asignamos a \(x\) el objeto \(10\), a \(z\) el objeto \(0\) y a \(u\) el objeto \(9\) produce o representa el objeto \(0\) ya que \[Pred(10)=5\text{ o }10\leq0+9\] no es un enunciado verdadero. Si le asignamos a \(x\) el objeto \(0\) entonces independientemente de que otros objetos asignemos a \(z\) y \(u\), la expresion no produce o representa un objeto en forma precisa ya que \(Pred(0)\) no esta definido en forma precisa
adhocprefix(1)adhocsufix La expresion \[(\exists y\in\mathbf{N})\text{ }x=y^{2}\] cuando le asignamos a \(x\) el objeto \(10\), produce o representa el objeto \(0\) ya que el enunciado \[(\exists y\in\mathbf{N})\text{ }10=y^{2}\] es falso. Cuando le asignamos a \(x\) el objeto \(\{1,9\}\), produce o representa el objeto \(0\) ya que el enunciado \[(\exists y\in\mathbf{N})\text{ }\{1,9\}=y^{2}\] es falso. Notese que esta expresion siempre produce o representa en forma precisa un objeto matematico (\(0\) o \(1\)) cualquiera sea el objeto que le asignamos a \(x\)
A las expresiones antes descriptas las llamaremos Booleanas ya que cuando estan definidas producen o representan valores Booleanos. Cabe destacar que una expresion Booleana puede no tener variables y en tal caso sera directamente un enunciado matematico preciso, el cual asume o representa ya sea el objeto \(0\) si es falso o el objeto \(1\) si es verdadero. Ejemplos:
adhocprefix(1)adhocsufix La expresion \[12=1+10\] representa o produce el objeto \(0\)
adhocprefix(1)adhocsufix La expresion \[24=2.(1+10+1)\] representa o produce el objeto \(1\)
adhocprefix(1)adhocsufix La expresion \[(\forall x,y\in\mathbf{N})\text{ }(x+y)^{2}=x^{2}+2.x.y+y^{2}\] representa o produce el objeto \(1\)
adhocprefix(1)adhocsufix
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 previamente fijado.
Sea \(\Sigma\) un alfabeto. Diremos que \(E\) es una expresion lambdificable con respecto a \(\Sigma\) si \(E\) es una expresion que cumple las siguientes propiedades:
adhocprefix(1)adhocsufix Cada variable de \(E\) pertenece a alguna de las siguientes listas de variables \[\begin{aligned} \text{Variables numericas:} & x,y,z,w,n,m,k,...\\ & x_{1},y_{1},z_{1},w_{1},n_{1},m_{1},...\\ & x_{2},y_{2},z_{2},w_{2},n_{2},m_{2},...\\ & etc \end{aligned}\] \[\begin{aligned} \text{Variables alfabeticas:} & \alpha,\beta,\gamma,\eta,...\\ & \alpha_{1},\beta_{1},\gamma_{1},\eta_{1},...\\ & \alpha_{2},\beta_{2},\gamma_{2},\eta_{2},...\\ & etc \end{aligned}\]
adhocprefix(2)adhocsufix \(E\) puede no tener variables y en tal caso \(E\) debe representar en forma inambigua a un objeto matematico concreto
adhocprefix(2)adhocsufix \(E\) deberá cumplir alguna de las dos siguientes propiedades:
Cuando hacemos una asignacion de valores de \(\omega\) a sus variables numéricas y valores de \(\Sigma^{\ast}\) a sus variables alfabéticas entonces, en caso de que \(E\) represente o produzca en forma precisa e inambigua un objeto, dicho objeto debe ser siempre un elemento de \(\omega\)
Cuando hacemos una asignacion de valores de \(\omega\) a sus variables numéricas y valores de \(\Sigma^{\ast}\) a sus variables alfabéticas entonces, en caso de que \(E\) represente o produzca en forma precisa e inambigua un objeto, dicho objeto debe ser siempre un elemento 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(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(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\).