S has a left inverse

And Shin-Cheng Mu gives a rather accessible algebraic proof.

There's lots to say about this observation, but apart from saying I was surprised by it, I will leave comment to the comments.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Comment #1: invertability

Note the formulation of invertability depends upon the combinators having (propositional) types.


Sorry, I'm rather stupid. Can someone explain what 'S' is, and what a 'left inverse' is?

I kind of assume it's to do with inverse element on Wikipedia but this leaves me none the wiser ...

No sincere question is stupid

S is one of the two combinators forming the SK basis of combinatory logic.

You can think of a combinator as a funtion that converts functions into other functions.

The left inverse is another function that, when you apply it to the output of an application of S, gives you back the original input you fed to S.

So, for example, if you start with X, apply S to it to get S(X), then a left inverse L would give you L(S(X)) = X.

Hope that helps. ;-)

Ah, _that_ S ...

Thank you .. it definitely wasn't clear from the heading what 'S' this was.


Here's an article with some definitions.


I guess I'd be a lot more surprised if there existed a complete basis in which every combinator had an inverse... I haven't thought about this much, but my strong intuition is that any basis must contain something non-injective someplace.


Since T^-1 (S^-1 (S T)) = id, we have \x. T^-1(S^-1(x)) is the inverse of (S T), so a basis being invertible implies everything is invertible, by induction. ?

Edit: Ignore this terrible post :)

Statman's results on combinator bases

Rick Statman had some results (mid 80s, maybe?) about what properties a combinator basis had to have. The properties were syntactic in nature, so I don't know about non-injectivity. I recall there had to be at least some "parentheses" on the RHS of at least one combinator, perhaps something K-like (variable dropped from left to the right side), something S-like (in the sense that a LHS variable had to be repeated on the RHS).

OK, I googled it: the paper is from the 1986 LICS conference, but CiteSeer doesn't have a copy. The best I can find is a citation (but perhaps it's available at ACM if you have access -- I don't from home).

Statman, R., "On Translating Lambda Terms into Combinators: the Basis Problem." Proceedings of the 1st Symposium on Logic In Computer Science, pp 378--382. Cambridge, MA. June, 1986.

Unless I misread everything...

Will the SK basis do? If I'm not mistaken, k has an inverse too, k' = (\x -> x 42)

An injective basis only implies that a composition of combinators (x . y) has an inverse, not that (x y) has one.

(otherwise (k 42) would have an inverse, and that would just be weird)


Of course you (and Charles below) are right. Like I said, I hadn't thought about it very hard... :)

S does not have a right inverse...

...and so S's inverse does not have a left inverse.