Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I think this might be more suitable for MO. –  Kaveh Apr 30 '11 at 20:54
    
@Kaveh: perhaps so, though I suspect the answer is quite simple for someone who know it. –  András Salamon Apr 30 '11 at 21:20
    
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. –  Kaveh Apr 30 '11 at 21:23
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. –  András Salamon Apr 30 '11 at 22:24
    
I think you may post it as a reference request question, if your guess is wrong they will tell you. :) –  Kaveh Apr 30 '11 at 22:32

1 Answer 1

up vote 2 down vote accepted

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).

share|improve this answer
    
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? –  András Salamon Mar 26 '12 at 11:17
    
@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 en.wikipedia.org/wiki/… or 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. –  Rachel Mar 27 '12 at 3:32
    
@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. –  Rachel Mar 27 '12 at 3:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.