<p>The S and K combinators are a <a href="https://en.wikipedia.org/wiki/SKI_combinator_calculus" rel="nofollow noreferrer">known basis set</a> of combinators. Such a set is called <em>universal</em>. However, two combinators being universal is the limit on universality, as a single combinator <a href="https://math.stackexchange.com/questions/839926/is-there-a-proof-of-nonexistence-of-a-proper-universal-combinator">cannot be universal.</a></p>
<p>This brings an interesting question on how far we can go. Given any combinator X, does there exist a combinator X<span class="math-container">$^\prime$</span> such that X and X<span class="math-container">$^\prime$</span> are universal? It is important to clarify that X and X<span class="math-container">$^\prime$</span> are <em>proper</em>, because a single improper combinator <a href="https://en.wikipedia.org/wiki/Iota_and_Jot" rel="nofollow noreferrer">can be universal.</a></p>

CC BY-SA 4.0
2024-08-29T12:35:25.223Z
Is there such an $X'$ for $X=I$?
Emil Jeřábek
CC BY-SA 4.0
2024-08-29T21:29:46.383Z
@EmilJeřábek I actually considered that case before this more general one, but I was unable to prove it either way.
undefned
CC BY-SA 4.0
2024-09-01T17:58:32.537Z
@EmilJeřábek I think I found one. Let $X = I$. Then $X^\prime = \lambda a b c d e. b c (b e d)$. However, I have no proof that $X$ and $X^\prime$ are universal.
undefned
<combinatory-logic>
Can a combinator basis set of size two have an arbitrary combinator?
undefned
# Can a combinator basis set of size two have an arbitrary combinator?

(Asked by: username_0 on 2024-08-28)

The S and K combinators are a [known basis set](https://en.wikipedia.org/wiki/SKI_combinator_calculus) of combinators. Such a set is called *universal*. However, two combinators being universal is the limit on universality, as a single combinator [cannot be universal.](https://math.stackexchange.com/questions/839926/is-there-a-proof-of-nonexistence-of-a-proper-universal-combinator)

This brings an interesting question on how far we can go. Given any combinator X, does there exist a combinator X$^\prime$ such that X and X$^\prime$ are universal? It is important to clarify that X and X$^\prime$ are *proper*, because a single improper combinator [can be universal.](https://en.wikipedia.org/wiki/Iota_and_Jot)

**Tags:** combinatory-logic

> **Comments:**
> **username_1**: Is there such an $X'$ for $X=I$?  
> **username_0**: @EmilJeřábek I actually considered that case before this more general one, but I was unable to prove it either way.  
> **username_0**: @EmilJeřábek I think I found one. Let $X = I$. Then $X^\prime = \lambda a b c d e. b c (b e d)$. However, I have no proof that $X$ and $X^\prime$ are universal.  

---

## 0 answers

