3
$\begingroup$

The Wikipedia article on Relation Algebra notes that this is a formal system which has essentially the same expressive power as the three-variable fragment of first-order logic. Peano Arithmetic can be encoded in the three-variable fragment, so this means that the satisfiability of an arbitrary RA formula is undecidable. There is an unsourced but intriguing remark:

(N.B. The Boolean algebra fragment of RA is complete and decidable.)

What is meant by "the Boolean algebra fragment of RA"?

I have tried to track down references, but I don't have access to the Tarski and Givant book which is one of the main texts (and which seems relevant judging by Monk's 1989 review). Any hints, references, or pointers (especially to journal articles or lecture notes that are online) would be welcome.

  • 0
    I think this might be more suitable for MO.2011-04-30
  • 0
    @Kaveh: perhaps so, though I suspect the answer is quite simple for someone who know it.2011-04-30
  • 0
    My guess would be what the first sentence of the WP article says, but I guess you have seen that already: "a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation.", i.e. formulas restricted to the Boolean part.2011-04-30
  • 1
    @Kaveh: yes, that would be my guess too. I'm hoping for a reference or a definite statement, since I would like to build on this result -- a guess is not my favourite kind of foundation.2011-04-30
  • 0
    I think you may post it as a reference request question, if your guess is wrong they will tell you. :)2011-04-30

1 Answers 1

3

I think the WIkipedia article is trying to say that Boolean algebra is Complete and decidable, i.e.:

The "Boolean fragment" refers to the set of sentences in the language of Boolean algebras (which is a subset of the language of relation algebras) which is derivable from the axioms of Boolean algebra.

Completeness, he is saying that: any sentence in the language of Boolean algebra is derivable from the axioms of Boolean algebra if and only if it is true in the Boolean algebra consisting of two elements (i.e. is a tautology).

Decidability: there is an algorithm for deciding whether or not a given sentence in the language of Boolean algebra is derivable from the axioms (namely, use Completeness to check to see if it is true in the Boolean algebra consisting of two elements - truth table method).

  • 0
    The phrase "the Boolean Algebra fragment of RA" seems to refer to a logic, about which one can make statements of the form "this is undecidable". I do not understand what you mean by the Boolean fragment being "just the Boolean algebra"; I do not know what meaning to assign to statements of the form "a Boolean algebra is decidable". Could you perhaps edit this answer to clarify?2012-03-26
  • 0
    @AndrásSalamon, I would take "boolean algebra is decidable" to mean that the (presumably first-order) theory of Boolean algebras is decidable, i.e., FOL + the three axioms B1-B3 listed in the article. The FO theory of BA is indeed decidable, as established by Tarski in 1949. See http://en.wikipedia.org/wiki/Decidability_(logic)#Some_decidable_theories or http://www.math.psu.edu/simpson/notes/master.pdf (page 30 4.2.2) or google for plenty of info. It's not some particular Boolean algebra that is decidable but rather the set of sentences about this class of structures.2012-03-27
  • 0
    @AndrásSalamon, also, to address the other connection with logics (the algebraic logic connection), note that (the 2 element) BA is equivalent to propositional logic, which is also well-known to be decidable.2012-03-27