I had originally posted the following questions on math stack exchange but feel they are better suited for mathoverflow (original post$-$updated & reorganized for clarity).
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.)
- Insofar as I can tell, there are two possible 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". My question is, which of these two interpretations is the correct content of Korselt's theorem?
- If it is the case that no such more powerful algebra exists which can capture the fragment of FOL characterized by formulas whose quantifier depth is equal to 4, then perhaps the same is true of those fragments of FOL characterized by quantifier depth $n>4$. However, this stance ought to be qualified. Perhaps these "more powerful" algebras only exist for certain values of $n$. That analogues of RA do in fact exist, but they only pertain to particular values of $n$, i.e. only a select subset of $\mathbb{N}$. If so, a natural question arises: is this subset definable?
- A friend of mine suggested that Peirce's reduction thesis might be relevant here. Admittedly, I don't know all that much about the thesis. But from what I can gather (and someone please do correct me if I am mistaken) the thesis posits something about the expressibility of arbitrary relations from triadic (ternary) ones. Please see this article for a brief introduction. While it is a little different, I believe it's nonetheless relevant and there are parallels to be drawn. For instance, the underlying concept of "three-ness" going on here. My question is then, why is it called a thesis as opposed to a theorem? Can the reduction thesis be used to say something about fragments of FOL whose quantifier depth is $n\geq4$? For instance, my friend hypothesized that maybe it can be used to take a statement of FOL with quantifier depth $n\geq4$ and reduce it to one whose depth is 3. Naturally, if this were true, one can simply use RA to express the reduced statement and go on their merry way. But is this actually possible?
