Kann Boolesche Algebra in einfach getipptem Lambda-Caclulus ausgedrückt werden?

Boolesche Algebra kann auf diese Weise (zum Beispiel) in nicht typisierter Lambda-Rechnung ausgedrückt werden.

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;

Auch die Boolesche Algebra kann in System F folgendermaßen codiert werden :

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;

Gibt es eine Möglichkeit, Boolesche Algebra in einfach getippter Lambda-Rechnung auszudrücken? Ich gehe davon aus, dass die Antwort NEIN ist. ( Zum Beispiel sind Vorgänger und Listen in einfach getippten Lambda-Berechnungen nicht darstellbar .) Wenn die Antwort in der Tat NEIN lautet, gibt es eine einfache intuitive Erklärung, warum es unmöglich ist, Boolesche Werte in einfach getippten Lambda-Berechnungen zu kodieren?

UPDATE: Wir gehen davon aus, dass es Basistypen gibt.

UPDATE: Die negative Antwort mit Erklärung wurde hier gefunden (Kommentar "Hier ist eine Beweisskizze, die zeigt, dass einfach getippte Lambda-Kalküle mit Produkten und unendlich vielen Basistypen keine Booleschen Werte enthält.") Dies ist, wonach ich gesucht habe.

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

Versuchen Sie, die Definitionen in Haskell einzugeben, und sehen Sie, was passiert, wenn Sie verschiedenen Ausdrücken Typen zuweisen. Sie werden sehen, dass der Code stark vom Polymorphismus abhängt.

Dave Clarke

Es tut mir leid, pedantisch zu sein, aber Fragen zur Ausdruckskraft dieses oder jenes Kalküls werden nur mit einem klaren Verständnis dessen, was Sie mit "ausgedrückt", "codiert" und "dargestellt" meinen, bedeutungslos, da es mehrere vernünftige Möglichkeiten gibt, diese Begriffe zu verstehen. Da Sie die Existenz von Basistypen festlegen, müssen Sie außerdem genau wissen, was diese Typen sind und mit welchen Konstruktoren / Destruktoren sie geliefert werden.

Martin Berger

Tut mir leid, dass ich nicht pedantisch war. Die Antwort wurde hier gefunden: math.andrej.com/2009/03/21/…

Ilya Klyuchnikov

Ich habe das Gefühl, ich sollte etwas Anerkennung dafür bekommen, dass ich so ein schickes Blog leite :-)

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

Kann Boolesche Algebra in einfach getipptem Lambda-Caclulus ausgedrückt werden?

Antworten: