# Definitions of Boolean algebras

One definition I find of a Boolean algebra in the book that I am following (V. Manca, Logica matematica, 'matematical logic') is determined by the binary operations $\land$ and $\lor$ and the unary operation $\lnot$ on a set such that $$\varphi\land(\psi\land \chi)=(\varphi\land \psi)\land \chi,\quad \varphi\lor(\psi\lor \chi)=(\varphi\lor \psi)\lor \chi$$ $$\varphi\land \psi=\psi\land \varphi,\quad \varphi\lor \psi=\psi\lor \varphi$$ $$\varphi\lor (\psi\land \chi) = (\varphi\lor \psi) \land (\varphi \lor \chi) ,\quad \varphi \land (\psi\lor \chi) = (\varphi \land \psi) \lor (\varphi \land \chi)$$ $$\varphi \lor (\varphi \land \psi) = \varphi,\quad \varphi\land (\varphi\lor \psi) = \varphi$$ $$\varphi\land 0 =0,\quad \varphi\lor1=1$$ $$\varphi\lor\lnot \varphi=0,\quad \varphi\land\lnot \varphi=1$$

Another definition that I find in the same text is that a Boolean algebra is a complemented distributive lattice, i.e. a lattice where a maximum $1$ and a minimum $0$ exist and such that for all its elements $x$ there is an element $x'$ such that$$\inf(\{x,x'\})=0\text{ and }\sup(\{x,x'\})=1$$ and where the $\inf$ and the $\sup$ operations are distributive with respect to each other.

I wonder whether any Boolean algebra according to one of the two definitions is "isomorphic" in any way to a Boolean algebra according to the first definition and I think that I have been able to prove that a partial order can be defined on a Boolean algebra by letting $\varphi\le\psi\equiv\varphi\lor\psi=\psi$. Moreover, I think I have been to prove that, by letting $x\land y:=\inf(\{x,y\})$, $x\lor y:=\sup(\{x,y\})$ and $\lnot x:=x'$ a complemented distributive lattice is a Boolean algebra in the first definition.

There is one thing missing to prove that the two definitions are equivalent: how can we see that $\varphi\land\psi$ is the greatest lower bound of $\{\varphi,\psi\}$ and that $\varphi\lor\psi$ is the lowest upper bound of $\{\varphi,\psi\}$? I thank you very much for any answer!!!

*I have found all the axioms quite easily proved to be satisfied by a complemented distributive lattice, except for $$\inf(\{\inf(\{x,y\}),z\})=\inf(\{x,\inf(\{y,z\})\})\text{ and }\sup(\{\sup(\{x,y\}),z\})=\sup(\{x,\sup(\{y,z\})\})$$ but I think the following proves it.

Clearly$$\inf(\{\inf(\{x,y\}),z\})\le x,y,z\text{ and }\inf(\{x,\inf(\{y,z\})\})\le x,y,z.$$Therefore $\inf(\{\inf(\{x,y\}),z\})$ is a lower bound of $\{y,z\}$ and $\inf(\{\inf(\{x,y\}),z\})\le\inf(\{y,z\})$, by definition of $\inf$, which is the greatest lower bound, and, then, $\inf(\{\inf(\{x,y\}),z\})$, which is not greater than $z$, is a lower bound of $\{x,\inf(\{y,z\})\}$: we have that $\inf(\{\inf(\{x,y\}),z\})\le\inf(\{x,\inf(\{y,z\})\})$. But $\inf(\{x,\inf(\{y,z\})\})$ is a lower bound of $\{x,y\}$ and $\inf(\{x,\inf(\{y,z\})\})\le\inf(\{x,y\})$, and therefore, since $\inf(\{x,\inf(\{y,z\})\})\le z$, we have that $\inf(\{x,\inf(\{y,z\})\})\le\inf(\{\inf(\{x,y\}),z\})$. Repeating the same reasoning with $\sup$, $\ge$, upper and small-er/-est substituting $\inf$, $\le$, lower and great-er/-est proves that $\sup(\{\sup(\{x,y\}),z\})=\sup(\{x,\sup(\{y,z\})\})$.

If you have a lattice, that is a partially ordered set $L,\le$ where every two element set has a greatest lower bound and a least upper bound, you can define the operations $\land$ and $\lor$ by $$a\land b=\inf\nolimits_\le\{a,b\},\qquad a\lor b=\sup\nolimits_\le\{a,b\}$$ These operations satisfy the following properties

1. Idempotency: $a\land a=a$, $a\lor a=a$
2. Absorption: $a\land(a\lor b)=a$, $a\lor(a\land b)=a$
3. Commutativity: $a\land b=b\land a$, $a\lor b=b\lor a$
4. Associativity: $a\land(b\land c)=(a\land b)\land c$, $a\lor(b\lor c)=(a\lor b)\lor c$

These properties are easily proved from the fact that $\le$ is a partial order relation.

Conversely, suppose you have two operations $\land$ and $\lor$ on the set $L$ that satisfy the above properties. Define $$a\le b \quad\text{stands for}\quad a\land b=a$$ Then you can prove

1. $a\le a$ for all $a\in L$
2. If $a\le b$ and $b\le a$ then $a=b$
3. If $a\le b$ and $b\le c$, then $a\le c$

The first follows from idempotency, the second from commutativity, the third from associativity. Thus $\le$ is a partial order on $L$.

Moreover $a\land b=\inf_\le\{a,b\}$. Indeed, $$a\land b\le a$$ because $(a\land b)\land a=a\land(a\land b)=(a\land a)\land b=a\land b$. If $c\le a$ and $c\le b$, then $$c\land(a\land b)=(c\land a)\land b=c\land b=c$$ so $c\le a\land b$ and we have proved $a\land b$ is the greatest lower bound of $\{a,b\}$.

By symmetry, if we define $a\le'b$ to stand for $a\lor b=b$, we can prove that $\le'$ is a partial order on $L$ and $a\lor b=\sup_{\le'}\{a,b\}$.

We didn't use absorption yet. It is proved for showing that $a\le b$ if and only if $a\le' b$.

Suppose $a\le b$, that is $a\land b=a$. Then $$a\lor b=(a\land b)\lor b=b\lor(a\land b)=b\lor(b\land a)=b$$ and so $a\le' b$. Conversely, suppose $a\le'b$, that is $a\lor b=b$. Then $$a\land b=a\land(a\lor b)=a$$ so $a\le b$.

Since every two element set has a least upper bound with respect to $\le'$ and a greatest lower bound with respect to $\le$, but the two relations are the same, we have that $L,\le$ is a lattice.

Now add maximum, minimum, distributivity and complements and you have a Boolean algebra.

• @Self-teachingDavide Maybe you can find my own notes useful. By the way, prof. Manca's office is three doors from mine. ;-) – egreg Feb 8 '15 at 21:21
• Thank you so much again for your interesting notes and tell Prof. Manca that its book is great! – Self-teaching worker Feb 9 '15 at 15:52
• Dear Professor - Maybe I could impose on you for your comments on this question I asked math.stackexchange.com/questions/2810704/… in which I thought this criterium for defining an ideal in a Boolean algebra was superfluous by interpreting $\vee$ as a lub (which I should have made explicit in the question). Am I wrong in that presumption? Thanks for your kind attention. I'm a septuagenarian self-studier with no math background so I greatly value any help I get here. With regards, – user12802 Jun 9 '18 at 12:55

I think I have been able to prove the equivalence. I see that $\varphi\lor\psi=\psi\iff \varphi\land\psi=\varphi$.

Therefore, in order to show that $\varphi\land\psi$ is the greatest lower bound, we can see that, if $\varphi\land\psi\le\chi\le\varphi$ and $\varphi\land\psi\le\chi\le\varphi$, then $\chi=\chi\lor(\varphi\land\psi)=(\chi\lor\varphi)\land(\chi\lor\psi)=\varphi\land\psi$.

In order to show that $\varphi\land\psi$ is the lowest upper bound, we can see that, if $\varphi\lor\psi\ge\chi\ge\varphi$ and $\varphi\lor\psi\ge\chi\ge\varphi$, then $\chi=\chi\land(\varphi\lor\psi)=(\chi\land\varphi)\lor(\chi\land\psi)=\varphi\lor\psi$.