A álgebra booleana pode ser expressa em lambda caclulus simplesmente digitado?

A álgebra booleana pode ser expressa em cálculo lambda sem tipo (por exemplo) desta maneira.

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;

Também a álgebra booleana pode ser codificada no Sistema F desta maneira :

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;

Existe uma maneira de expressar a álgebra booleana no cálculo lambda simplesmente digitado? Presumo que a resposta seja NÃO. ( Por exemplo, Predecessor e listas não são representáveis no cálculo lambda simplesmente digitado .) Se a resposta for NÃO, existe uma explicação intuitiva simples, por que é impossível codificar booleanos no cálculo lambda simplesmente digitado?

ATUALIZAÇÃO: Assumimos que existem tipos de base.

ATUALIZAÇÃO: A resposta negativa com explicação foi encontrada aqui (Comentário "Aqui está um esboço de prova para mostrar que o cálculo lambda de tipo simples com produtos e infinitamente muitos tipos de base não possui booleanos.") Era isso que eu estava procurando.

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

Tente digitar as definições no Haskell e veja o que acontece quando você atribui tipos a várias expressões. Você verá que o código depende muito do polimorfismo.

Dave Clarke

Desculpe ser pedante, mas as perguntas sobre a expressividade deste ou daquele cálculo se tornam significativas apenas com uma compreensão clara do que você quer dizer com "expresso", "codificado" e "representado", pois existem várias maneiras razoáveis de entender esses termos. Além disso, desde que você estipule a existência de tipos de base, você precisará ser específico sobre o que são e quais construtores / destruidores eles vêm.

Martin Berger

Desculpe por não ser pedante. A resposta foi encontrada aqui: math.andrej.com/2009/03/21/…

Ilya Klyuchnikov

Eu sinto que eu deveria receber algum crédito para a execução de um blog, tais bacana :-)

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)$ .

Emil Jeřábek supports Monica

A álgebra booleana pode ser expressa em lambda caclulus simplesmente digitado?

Respostas: