Assoziativität in Lambda-Kalkül

Question

Ich arbeite an den Übungsfragen Buch Der Lambda-Kalkül . Eine der Fragen, die ich stecken bin, ist die folgende Beweis: Zeigen Sie, dass die Anwendung nicht assoziativ ist; In der Tat, x (yz) nicht gleich (xy) z

Hier ist, was ich bisher gearbeitet habe:

Let x = λa.λb. ab
Let y = λb.λc. bc
Let z = λa.λc. ac

(xy)z => ((λa.λb. ab) (λb.λc. bc)) (λa.λc. ac)    
=> (λb. (λb.λc. bc) b) (λa.λc. ac)    
=> (λb.λc. bc) (λa.λc. ac)    
=> (λc. (λa.λc. ac) c)

x(yz) => (λa.λb. ab) ((λb.λc. bc) (λa.λc. ac))    
=> (λb. ((λb.λc. bc) (λa.λc. ac)) b)    
=> (λb. (λc. (λa.λc. ac) c) b)

Ist das richtig? Bitte helfen Sie mir zu verstehen.

Answer 1

Die Ableitungen scheinen in Ordnung, auf einen Blick.

Konzeptionell denke nur, dass x, y und z alle berechenbaren Funktionen darstellen kann, und klar, sind einige dieser Funktionen nicht assoziativ. Sprich, x 'subtrahieren 2', y 'durch 2' und z 'double'. Für dieses Beispiel x (yz) = 'subtrahieren 2' und (xy) = z 'subtrahiert 1'.

Answer 2

Ich denke auch, dass Ihr Gegenbeispiel richtig ist.
Sie können sich wahrscheinlich ein einfacheres Gegenbeispiel wie diese:

  

let x = ?a.n und y , z Variablen dann:

     

(xy) z => ((?a.n) y) z => n z
  x (yz) => (?a.n) (y z) => n

Answer 3

Es scheint in Ordnung, aber der Einfachheit halber, wie etwa durch Widerspruch zu beweisen?

Angenommen (xy) z = x (yz), und lassen

x = λa.λb. a     # x = const
y = λa. -a       # y = negate
z = 1            # z = 1

und zeigt, dass ((xy) z) 0 ? (x (yz)) 0.

Answer 4

Das Buch, das Sie von Barendregt erwähnen ist extrem formal und präzise (ein großes Buch), so dass es schön wäre, die genaue Angabe der Bewegung zu haben.

Ich denke, das eigentliche Ziel war instantiations für x zu finden, y und z, so dass x (y z) reduziert sich auf die Booleschen true = \ xy.x und (x y) z zum boolean false verringert = \ xy.y

Dann können Sie nehmen zum Beispiel x = \ z.true und z = I = \ z.z (y beliebig).

Aber wie können wir beweisen, dass wahr mit falschem nicht konvertierbar ist? Sie haben keine Möglichkeit, es im Inneren des Kalküls zu beweisen, da Sie keine Negation haben: Sie können nur Gleichheiten und nicht die Ungleichheiten unter Beweis stellen. Aber lassen Sie uns das beobachten, wenn wahr = false dann alle Begriffe gleich sind.

die Tat, für jeden M und N, wenn sie wahr = false dann

                         true M N = false M N

, aber wahr M N reduziert sich auf M, während falsche M N zu N reduziert, so

                              M = N

Wenn also wahr = false alle Begriffe gleich sein würden, und das Kalkül wäre trivial sein. Da wir nicht trivial Modelle der Lambda-Kalkül finden kann, keine solche Modell kann gleichsetzen wahr und falsch (allgemeiner Begriffe mit verschiedenen Normalformen gleichsetzen kann, das wäre uns verlangen über die Bohm-out-Technik zu sprechen).