5
$\begingroup$

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\})\})$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @Self-teachingDavide Maybe you can find my own notes useful. By the way, prof. Manca's office is three doors from mine. ;-) $\endgroup$ – egreg Feb 8 '15 at 21:21
  • $\begingroup$ Thank you so much again for your interesting notes and tell Prof. Manca that its book is great! $\endgroup$ – Self-teaching worker Feb 9 '15 at 15:52
  • $\begingroup$ 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, $\endgroup$ – user12802 Jun 9 '18 at 12:55
0
$\begingroup$

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

$\endgroup$

Your Answer

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

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