On Saturday, I got Relation Algebras by Games by Hirsch and Hodkinson via Inter-Library Loan. I am still debating whether to use this book for a Study With Me blog series. I’ve only gotten through the preliminaries so far, so we’ll see.
From the title of the book, I was expecting the authors to take various games and use them to derive relation algebras. Instead, the authors are going to take several variants of one particular game and use them to show thing about pre-existing relation algebras or classes thereof. The approach sounds very much like Zero-knowledge proofs. I think I may have titled the book An Information Theoretic Approach To Relation Algebras.
The basic idea of the game is that there are two players: Abelard and Eloise. Eloise’s goal is to prove that her model of a relation algebra is complete. Abelard’s goal is to stump Eloise. On Abelard’s turn, he asks a question about Eloise’s model of the algebra. On Eloise’s turn, she adds whatever is needed to the model she’s presented thus far so that she can answer Abelard’s question. Abelard wins if he stumps Eloise. Eloise wins if she can answer every infinite series of questions Abelard poses.
This is an interesting concept. The two major variants seem to be: limiting the game to a certain number of rounds or limiting the blackboard space upon which the model is presented. In the prior, there are apparently situations where you can prove things like: If Eloise can win every game of length
In the latter case, there may be turns where Eloise has to erase stuff from the board and put other stuff there. At any given time in the latter case, Eloise can only depend on what is on the board to answer Abelard’s question.
At the moment, I’m still trying to get my head around what kinds of things Abelard might ask and what kinds of things Eloise might answer. I’m also trying to think of what other sorts of open questions might benefit from this sort of reasoning. The Riemann hypothesis? The Goldbach conjecture?