Is there a combinator that introduces brackets to a combinatory logic expression using just B?

Question

Suppose I have the expression $abcdef$ and I want a combinator $X$ that does this:

$Xabcdef=a(bcd)(ef)$.

Is it possible to express $X$ using just the $B$ combinator, defined by

$Babc=a(bc)$?

Is this possible in general? That is, if I have a string of letters without brackets, is there always a combinator in terms of $B$ only that parenthesizes my expression in the way I want, leaving the order of the letters unchanged?

• chi: What is a "combinator in terms of a $B$ only", precisely? I.e. are $BBBabcdef, B(BB)abcdef, Ba(Bbcd)(Bef)$ allowed as "only in terms of $B$"? (Note that none of these is a solution, I just want to understand the rules of the game.) Which ones could be allowed?
• baronbrixius: The first two are allowed, the third one is not.

Answer 1

$X=B(BBB)(BB)$ answers the first question. Indeed,

$B(BBB)(BB)abcdef=BBB(BBa)bcdef=B(B(BBa))bcdef=B(BBa)(bc)def=BBa(bcd)ef=B(a(bcd))ef=a(bcd)(ef).$

For the second question, yes, this may be done in general. Here's a rough proof: if we have $Xabc\ldots xyz = (\textrm{expr})(yz),ドル this becomes $Xabc\ldots xyz=B(\textrm{expr})yz,ドル so $Xabc\ldots x = B(\textrm{expr})$. If $(yz)$ is nested inside other brackets, like, for example, $Xabc\ldots xyz=(\textrm{expr})(x(yz)),ドル we get $Xabc\ldots xyz=B(\textrm{expr})x(yz)=B(B(\textrm{expr})x)yz,ドル and again we may then consider just $Xabc\ldots x=B(B(\textrm{expr})x)$. We may then do a further step: $Xabc\ldots x=B(B(\textrm{expr})wx)=BB(B(\textrm{expr}))x,ドル which means that $Xabc\ldots w=BB(B(\textrm{expr}))$. Continuing doing this, we end up with just $X$ on the left hand side and an expression involving (possibly bracketed) $B$'s on the right hand side.

Answer 2

Set $x_1 = x$ and $x_{n+1} = B x_n$, where $x ∈ \{B, C, K, W\}$; and note that - up to η-equivalence, $x_n = x_{n+1} I$, since $B f I = f = B I f$ under η-equivalence. We can then also write $x_0 = x I$. The combinators $\{B, C, K, W\}$ are given by the rules $$I x = x,\quad B x y z = x (y z),\quad C x y z = x z y,\quad W x y = x y y,\quad K x y = x.$$

Up to η-equivalence $B_0 = B I = I$.

Instead of explaining the general case, it should suffice to see an example: $$\begin{align} x v (z y) (y x) &= I x v (z y) (y x)\\ &= B_4 I x v (z y) y x\\ &= B_3 (B_4 I) x v z y y x\\ &= C_3 X_b x v y z y x\\ &= C_4 (C_3 X_b) x v y y z x\\ &= C_5 (C_4 (C_3 X_b)) x v y y x z\\ &= C_4 (C_5 (C_4 (C_3 X_b))) x v y x y z\\ &= C_3 (C_4 (C_5 (C_4 (C_3 X_b)))) x v x y y z\\ &= C_1 (C_3 (C_4 (C_5 (C_4 (C_3 X_b))))) v x x y y z\\ &= W_4 X_c v x x y z\\ &= W_2 (W_4 X_c) v x y z\\ &= K_2 X_w v w x y z\\ &= X_k v w x y z, \end{align}$$ where $$ X_b = B_3 (B_4 I) = B_3 B_3,\quad X_c = C_1 (C_3 (C_4 (C_5 (C_4 (C_3 X_b))))),\\ X_w = W_2 (W_4 X_c),\quad X_k = K_2 X_w. $$ The $X_b$ sub-term applies to your question. The remainder applies to the more general question that you didn't ask.

You could also write it as $$K_2 (W_2 (C_1 (W_4 (C_3 (B_3 (C_4 (B_4 C_2))))))) v w x y z = x v (z y) (y x).$$

Edit: Before I forget, your example: $$\begin{align} a(bcd)(ef) &= Ia(bcd)(ef)\\ &= B_3Ia(bcd)ef\\ &= B_2(B_3I)a(bc)def\\ &= B_2(B_2(B_3I))abcdef\\ &= B_2(B_2B_2)abcdef \end{align}$$