As far as I understood, Boolean algebra is just one of the many first-order theories (1). It has the signature $\{\sqcap, \sqcup, \neg, \bot, \top\}$ and the axioms: associativity, commutativity, absorption, identity, distributivity, and complements (2). (I used $\sqcup$ and $\sqcap$ to distinguish them from the Boolean operators $\vee$ and $\wedge$, they seem to be different things.)

  1. Can we say that the theory of linear integer arithmetic (with the signature $\{+, -, n\cdot_{n\in\{..., -2, -1, 1, 2, ...\}}, <, ..., -2, -1, 0, 1, 2, ...\}$) forms a Boolean algebra? I.e., we can map elements of the Boolean-algebra theory to the elements of the LIA theory? How would you map $\sqcap$, $\sqcup$, $\neg$, $\bot$, $\top$? I guess, $\top \mapsto 1$, $\bot \mapsto 0$, $\neg \mapsto -1\cdot$ (multiplication by constant -1), but what about $\sqcap$ and $\sqcup$?

  2. What about other FOTs, e.g. Presburger arithmetic (which does not have multiplication by a constant $const\cdot$)? Is it true that many FOTs form a Boolean algebra?

(Related references would be appreciated.)

Update: Essentially, the question is whether the numbers in the theory of linear integer arithmetic form a Boolean algebra. I don't think that is true. But it is possible to form Boolean algebra using sets of numbers, i.e., predicates of the linear integer arithmetic form a Boolean algebra. For example, $a<10 \sqcup b<10$ becomes $a<10 \vee b<10$, $a<10 \sqcap b<10$ becomes $a<10 \wedge b<10$, the negation operator $\neg$ of the Boolean algebra is simply the logical operator $\neg$, and so on. Hm, I wonder if the numbers of the non-linear arithmetic can form a Boolean algebra.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.