[FOM] Boolean algebra/ Simplicity

Dana Scott dana.scott at cs.cmu.edu
Tue Oct 13 18:46:18 EDT 2015

Equational axioms and free-variable equational deduction
have much to recommend themselves, but sometimes the
approach can lead to complications (say, in trying to
limit the number of equations or the number of variables
to be used).  In the case of classical and intuitionistic
logic, an algebraic approach using a partial ordering
can be given very neatly:

Partial Ordering

	x =< x

	x =< y & y =< z ==> x =< z

	x =< y & y =< x ==> x = y

Bounded Ordering

	0 =< x =< 1

Lattice Ordering

	x \/ y =< z <==> x =< z & y =< z

	z =< x /\ y <==> z =< x & z =< y

Heyting Algebra with Implication

	x =< y --> z <==> x /\ y =< z

Boolean Algebra with Implication (alternative to last)

	x =< (y --> z) \/ w <==> x /\ y =< z \/ w

Boolean Algebra with Negation (alternative to last two)

	x =< - y ∨ z <==> x /\ y =< z

Notice that each new connective (or constant) needs
just ONE new axiom.  This idea is of course directly
related to (and copied from) the Gentzen-style meta-
theoretic axiomatizations.  The partial-order version
above might be easier to explain to beginning students,
however.  And there are many easy exercises:

(1) Show that the axioms determine the connectives and
constants uniquely.

(2) Show the axioms are equivalent to the known equational

(3) Explain why these axioms imply that Heyting algebras
(Boolean algebras) are closed under forming subalgebras 
and direct products.

(4) Without using the equational axioms, show directly that 
these kinds of algebras are closed under homomorphic images
(which by Birkhoff's Theorem means that equational axioms
must exist).

More information about the FOM mailing list