¿Se puede expresar el álgebra booleana en un simple lambda caclulus?

El álgebra booleana se puede expresar en cálculo lambda sin tipo de (por ejemplo) de esta manera.

true  = \t. \f. t;
false = \t. \f. t;
not   = \x. x false true;
and   = \x. \y. x y false;
or    = \x. \y. x true y;

También el álgebra booleana se puede codificar en el Sistema F de esta manera :

CBool = All X.X -> X -> X;
true  = \X. \t:X. \f:X. t;
false = \X. \t:X. \f:X. f;
not   = \x:CBool. x [CBool] false true;
and   = \x:CBool. \y:CBool. x [CBool] y false;
or    = \x:CBool. \y:CBool. x [CBool] true y;

¿Hay alguna manera de expresar el álgebra booleana en un cálculo lambda simplemente escrito? Supongo que la respuesta es NO. ( Por ejemplo, el predecesor y las listas no son representables en cálculo lambda simplemente tipado ). Si la respuesta es NO, ¿existe una explicación intuitiva simple, por qué es imposible codificar booleanos en cálculo lambda simplemente tipado?

ACTUALIZACIÓN: Suponemos que hay tipos base.

ACTUALIZACIÓN: La respuesta negativa con explicación se encontró aquí (Comentario "Aquí hay un bosquejo de prueba para mostrar que el cálculo lambda de tipo simple con productos e infinitos tipos de bases no tiene booleanos"). Esto es lo que estaba buscando.

lo.logic type-theory lambda-calculus Ilya Klyuchnikov
fuente

Intente escribir las definiciones en Haskell y vea qué sucede cuando asigna tipos a varias expresiones. Verá que el código depende en gran medida del polimorfismo.

Dave Clarke

Lamento ser pedante, pero las preguntas sobre la expresividad de este o aquel cálculo se vuelven significativas solo con una comprensión clara de lo que quiere decir con "expresado", "codificado" y "representado", ya que hay múltiples formas razonables de entender estos términos. Además, dado que estipulas la existencia de tipos base, deberías ser específico sobre cuáles son y con qué constructores / destructores vienen.

Martin Berger

Lamento no haber sido pedante. La respuesta se encontró aquí: math.andrej.com/2009/03/21/…

Ilya Klyuchnikov

Siento que debería obtener algo de crédito por ejecutar un blog tan ingenioso :-)

Andrej Bauer

O

$O$

B = O \to O \to O

$B=O\to O\to O$

t r u e = λ x : O . λ y : O . x

$\mathrm{true}=\lambda x:O.\lambda y:O.x$

f a l s e = λ x : O . λ y : O . y

$\mathrm{false}=\lambda x:O.\lambda y:O.y$

n o t = λ a : B . λ x : O . λ y : O . a y x

$\mathrm{not}=\lambda a:B.\lambda x:O.\lambda y:O.ayx$

a n d = λ a : B . λ b : B . λ x : O . λ y : O . a (b x y) y

$\mathrm{and}=\lambda a:B.\lambda b:B.\lambda x:O.\lambda y:O.a(bxy)y$

o r = λ a : B . λ b : B . λ x : O . λ y : O . a x (b x y)

$\mathrm{or}=\lambda a:B.\lambda b:B.\lambda x:O.\lambda y:O.ax(bxy)$

¿Se puede expresar el álgebra booleana en un simple lambda caclulus?

Respuestas: