This is an old revision of the document!

Boolean algebras

Abbreviation: BA

Definition

A Boolean algebra is a structure $\mathbf{A}=\langle A,\vee ,0,\wedge ,1,-\rangle$ of type $\langle 2,0,2,0,1\rangle$ such that

$0,1$ are identities for $\vee,\wedge$: $x\vee 0=x$, $x\wedge 1=x$

$-$ gives a complement: $x\wedge -x=0$, $x\vee -x=1$

$\vee,\wedge$ are associative: $x\vee (y\vee z)=(x\vee y)\vee z$, $x\wedge (y\wedge z)=(x\wedge y)\wedge z$

$\vee,\wedge$ are commutative: $x\vee y=y\vee x$, $x\wedge y=y\wedge x$

$\vee,\wedge$ are mutually distributive: $x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)$, $x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)$

Definition

A Boolean algebra is a structure $\mathbf{A}=\langle A,\vee ,0,\wedge ,1,-\rangle$ of type $\langle 2,0,2,0,1\rangle$ such that

$\langle A,\vee ,0,\wedge ,1\rangle$ is a bounded distributive lattice

$-$ gives a complement: $x\wedge -x=0$, $x\vee -x=1$

Morphisms

Let $\mathbf{A}$ and $\mathbf{B}$ be Boolean algebras. A morphism from $\mathbf{A}$ to $\mathbf{B}$ is a function $h:Aarrow B$ that is a homomorphism:

$h(x\vee y)=h(x)\vee h(y)$, $h(-x)=-h(x)$

It follows that $h(x\wedge y)=h(x)\wedge h(y)$, $h(0)=0$, $h(1)=1$.

Definition

A Boolean ring is a structure $\mathbf{A}=\langle A,+ ,0,\cdot ,1\rangle$ of type $\langle 2,0,2,0\rangle$ such that

$\langle A,+ ,0,\cdot ,1\rangle$ is a commutative ring with unit

$\cdot$ is idempotent: $x\cdot x=x$

Remark: The term-equivalence with Boolean algebras is given by $x\wedge y=x\cdot y$, $-x=x+1$, $x\vee y=-(-x\wedge -y)$ and $x+y=(x\vee y)\wedge -(x\wedge y)$.

Definition

A Boolean algebra is a Heyting algebra $\mathbf{A}=\langle A,\vee ,0,\wedge ,1,arrow \rangle$ such that

$xarrow 0$ is an involution: $( xarrow 0) arrow 0=x$

Examples

Example 1: $\langle \mathcal P(S), \cup ,\emptyset, \cap, S, -\rangle$, the collection of subsets of a sets $S$, with union, intersection, and setcomplementation.

Properties

Classtype variety decidable in NPTIME decidable decidable yes yes yes, $n=2$ yes yes yes yes yes yes yes yes yes 2

Finite members

Number of algebras $=\{ \begin{array}{cc} 1 & \text{if size}=2^{n} \\ 0 & \text{otherwise}\end{array}.$

\hyperbaseurl{http://math.chapman.edu/structures/files/}