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 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
    @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