B, C, K, W system (Ofer Abarbanel online library)

The B, C, K, W system is a variant of combinatory logic that takes as primitive the combinators B, C, K, and W. This system was discovered by Haskell Curry in his doctoral thesis Grundlagen der kombinatorischen Logik, whose results are set out in Curry (1930).

Definition

The combinators are defined as follows:

  • Bx y z = x (y z)
  • Cx y z = x z y
  • Kx y = x
  • Wx y = x y y

Intuitively,

  • Bx y z is the composition of the arguments x and y applied to the argument z;
  • Cx y z swaps the arguments y and z;
  • Kx y discards the argument y;
  • Wx y duplicates the argument y.

Connection to other combinators[edit]

In recent decades, the SKI combinator calculus, with only two primitive combinators, K and S, has become the canonical approach to combinatory logic. B, C, and W can be expressed in terms of S and K as follows:

  • BS (K SK
  • CS (S (K (S (K SK)) S) (K K)
  • KK
  • WS S (S K)

Going the other direction, SKI can be defined in terms of B,C,K,W as:

  • IW K
  • KK
  • SB (B (B WC) (B B) = B (B W) (B B C).[1]

Connection to intuitionistic logic[edit]

The combinators BCK and W correspond to four well-known axioms of sentential logic:

AB: (B → C) → ((A → B) → (A → C)),

AC: (A → (B → C)) → (B → (A → C)),

AKA → (B → A),

AW: (A → (A → B)) → (A → B).

Function application corresponds to the rule modus ponens:

MP: from A and A → B infer B.

The axioms ABACAK and AW, and the rule MP are complete for the implicational fragment of intuitionistic logic. In order for combinatory logic to have as a model:

  • The implicational fragment of classical logic, would require the combinatory analog to the law of excluded middle, e.g., Peirce’s law;
  • Complete classical logic, would require the combinatory analog to the sentential axiom F→ A.

References

  • Hendrik Pieter Barendregt (1984) The Lambda Calculus, Its Syntax and Semantics, Vol. 103 in Studies in Logic and the Foundations of Mathematics. North-Holland. ISBN 0-444-87508-5
  • Haskell Curry (1930) “Grundlagen der kombinatorischen Logik,”  J. Math. 52: 509-536; 789-834.
  • Curry, Haskell B.; Hindley, J. Roger; Seldin, Jonathan P. (1972). Combinatory Logic. Vol. II. Amsterdam: North Holland. ISBN 0-7204-2208-6.
  • Raymond Smullyan (1994) Diagonalization and Self-Reference. Oxford Univ. Press.

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library