On the Wikipedia page for relation algebra (RA), one encounters the following peculiar fact (see section Expressive power):
"RA can express any (and up to logical equivalence, exactly the) first-order logic (FOL) formulas containing no more than three variables."
This fact is similarly emphasized towards the end of the article under the section called Historical remarks:
"In 1912, Alwin Korselt proved that a particular formula in which the quantifiers were nested four deep had no RA equivalent."
My questions are:
- Where can I find proofs of the above two results? (books, lecture notes, papers, etc.)
- Is it possible to generalize the above scenario? That is to say, given a natural number $n$, does there exist an analogue to RA such that it can express any first-order logic formulas containing no more than $n$ variables?
Aside:
I'm not sure whether my second question is well-founded, as there are two interpretations of Korselt's result. One possible interpretation is that he proved RA is not a "rich enough" algebraic structure to capture the fragment of FOL characterized by formulas whose quantifier rank (quantifier depth) is 4. Under this interpretation, his result does not explicitly preclude the existence of a "more powerful" algebra—one whose properties might allow it to capture the fragment of FOL characterized by formulas whose quantifier rank is 4.
On the other hand, perhaps his result is a hard and fast impossibility theorem. In which case, the quotation taken from the Historical remarks section is really saying that no such "more powerful" algebra can exist. That is to say, for the fragment of FOL characterized by formulas whose quantifier rank is equal to 4, there does not exist a corresponding algebra which can capture it. In a loose sense, it's "algebraically inexpressible". This may lead one to believe that the same is true regarding the non-existence of "more powerful" algebras that can capture the fragments of FOL characterized by formulas whose quantifier ranks is some $n\geq4$.
Then again, perhaps this is misleading. Rather, could it be the case that these "more powerful" algebras exist only for a particular subset of $\mathbb{N}$? We know RA describes the set of FOL formulas whose quantifier rank is $n\leq3$. Maybe it's actually the case that analogues to RA for greater values of $n$ only exist for a particular subset of the natural numbers. In which case, a natural question arises: is this subset definable?
I suppose the above justifies these follow-up questions:
- Which of the interpretations is the correct content of Korselt's result?
- Depending upon which of the above interpretations is correct, is it the case that the fragment(s) of FOL with quantifier rank $n\geq4$ cannot have algebraic analogues OR there do exist such algebras for some FOL fragments whose formulas possess rank $n\geq4$ and if so, is the subset definable?