Adição no Cálculo Lambda

---

Summary

A adição é realizada no cálculo lambda, utilizando numerais de Church e a função de sucessor, mostrando passo a passo como $2+3=5$ é computado a partir de $2S3$, resultando em $\lambda sz.s(s(s(s(s(z)))))$.

No cálculo lambda, operações aritméticas como a adição são expressas de forma puramente funcional, sem usar símbolos numéricos tradicionais como ”+”. Em vez disso, usamos os numerais de Church — que representam números como funções — e a função de sucessor para “somar”.

De forma simplifica a adição como uma maneira de aplicar repetidamente a ideia de “incrementar” um número a outro.

Definição

A adição no cálculo lambda pode ser entendida como a aplicação repetida da função de sucessor ($S$) de um número ao outro. Formalmente, para somar dois numerais de Church $m$ e $n$, podemos definir $m+n$ como:

• Pegar o numeral $m$ e usá-lo para aplicar $S$ (sucessor) $m$ vezes ao numeral $n$.

No exemplo dado:

• $2\equiv \lambda sz.s(s(z))$,
• $S\equiv \lambda wyx.y(wyx)$ (função de sucessor),
• $3\equiv \lambda sz.s(s(s(z)))$,

A adição $2+3$ é expressa como $2S3$, onde o numeral 2 atua como uma função que aplica $S$ duas vezes ao numeral 3.

Detalhando a Adição

Vamos dissecar o processo para entender como a adição emerge dessa construção.

Numerais de Church como Iteradores

Os numerais de Church são funções que “repetem” uma operação um certo número de vezes:

• $2=\lambda sz.s(s(z))$ significa “aplique $s$ duas vezes a $z$”.
• Quando usamos $2S3$, estamos dizendo: “pegue $S$ como a operação e aplique-a duas vezes a 3”.

Isso reflete a ideia intuitiva de soma: $2+3$ é o mesmo que incrementar 3 duas vezes ($S(S(3))$).

Passos da substituição

A expressão $2S3$ envolve substituições no cálculo lambda (β-redução).

Exemplo

Exemplo: Calculando $2+3$

Dado:

• $2=\lambda sz.s(s(z))$,
• $S=\lambda wyx.y(wyx)$,
• $3=\lambda sz.s(s(s(z)))$,

Queremos resolver:

$$2S3$$

Passo 1: Substituição de $s$ por $S$

Substituímos $s$ por $S$ (primeiro argumento):

$$2S3=(\lambda sz.s(s(z)))S3$$

Isso significa que $s=S$, e agora aplicamos o corpo da função ao próximo argumento $3$:

$$(\lambda z.S(Sz))3$$

Aqui, $s(s(z))$ se torna $S(Sz)$, ou seja, aplicar $S$ duas vezes a $z$.

Passo 2: Aplicação a 3

Substituímos $z$ por $3$:

$$(\lambda z.S(Sz))3$$

Isso é uma aplicação direta:

$$SS3$$

Passo 3: Calcular $S3$

Sabemos que $S$ incrementa um numeral:

• $3=\lambda sz.s(s(s(z)))$,
• $S3=(\lambda wyx.y(wyx))(\lambda sz.s(s(s(z))))$.

Resolvendo:

• Substituímos $w$ por $\lambda sz.s(s(s(z)))$: $$\lambda yx.y((\lambda sz.s(s(s(z)))yx)$$
• Avaliamos $(\lambda sz.s(s(s(z)))yx)$:
  • $s=y$, $z=x$, então $s(s(s(z)))=y(y(y(x)))$,
  • Resultado: $\lambda yx.y(y(y(x)))=\lambda sz.s(s(s(s(z))))=4$.

Assim, $S3=4$.

Passo 4: Calcular $S4$

Agora aplicamos $S$ a $4$:

• $4=\lambda sz.s(s(s(s(z))))$,
• $S4=(\lambda wyx.y(wyx))(\lambda sz.s(s(s(s(z)))))$.

Resolvendo:

• Substituímos $w$ por $\lambda sz.s(s(s(s(z))))$: $$\lambda yx.y((\lambda sz.s(s(s(s(z))))yx)$$
• Avaliamos: $s(s(s(s(z))))=y(y(y(y(x))))$,
• Resultado: $\lambda yx.y(y(y(y(x))))=\lambda sz.s(s(s(s(s(z)))))=5$.

Assim, $S(S3)=S4=5$.

Resultado

A expressão inicial $2S3$ se reduz a $S(S3)$, que é 5:

$$2S3=S(S3)=5$$

Referências

---

Aula 1 - Cálculo Lambda