IOWA STATE UNIVERSITY

Mathematics 567: Boolean Algebra

Instructor: Jonathan Smith, 496 Carver, 4-8172 (voice mail)

e-mail: jdhsmithATmathDOTiastateDOTedu (substitute punctuation)

Office Hours: Mon. 1:10pm, 3:10 pm; Wed. 1:10pm, 3:10pm, 4:10pm (subject to change)

Grading: based on five graded homework assignments.
Click here for information about special accommodations.

Textbook: P.T. Johnstone, Stone Spaces, Cambridge University Press, ISBN 0-521-33779-8

Study Plan: reserve 1 - 2 hours for homework between each pair of classes. Successful performance in the class depends critically on completion of the homework assignments.

Syllabus: Selected material from chapters I - III, with possible additional topics of specific interest.

Summary of the key concepts

Homework Assignments

Final graded homework due 4/27:
Three questions from the following:
  1. Let
    ( B , or , and , not, 0, 1 )
    be a Boolean algebra, considered also as a Boolean ring
    ( B , + , · , 0, 1 ) .
    Determine a polynomial  f ( x , y )  such that
    f ( x , y ) = x nand y
    for all  x , y  in  B .
  2. Let  B  be a finite Boolean algebra. Show that the distributive lattice  BJ  of ideals of  B  is a Boolean algebra.
  3. Let  B  be the power set of the set  N  of natural numbers. Show that the distributive lattice  BJ  of ideals of the Boolean algebra  B  is not a Boolean algebra.
  4. Let  G  be a group, and let  L  be the lattice of normal subgroups of  G, ordered by set-theoretic inclusion.
    1. Show that the lattice  L .is complete.
    2. Show that the lattice  L .is algebraic.
  5. Let  L  be the lattice of divisors of  72 , ordered by divisibility.
    1. Show that  L .is a locale.
    2. Determine the topological space  Pt L . of points of the locale  L . [For full credit, you should specify both the set  Pt L . and the set  W( Pt L)  of open sets in the topology.]
    3. Determine the topological space  Spec L  for the distributive lattice  L . [For full credit, you should specify both the set  Spec L . and the set  W( Spec L)  of open sets in the topology.]

Fourth graded homework due 4/11:
Three questions from the following:
  1. A bounded lattice L is atomic if for each non-zero element x of L, there is an atom a of L such that a < x . Give an example of a Boolean algebra that possesses an atom, but is not atomic. Justify your claims.
  2. Show that a locale is spatial if and only if each element is the meet of a set of prime elements.
  3. Let X be a topological space. Prove that the map
    y : X --> Pt W(X)
    taking an element  x  of  X  to the complement of the
    closure of  { x } is continuous.
  4. Let X be a topological space.
    1. Show that X is the object set of a small category in which there is a (unique) morphism from x to y if and only if
      x lies in the closure of the singleton {y} .
    2. Show that a continuous map
      f : X --> Y
      induces a functor from the category X to the category Y .
  5. Let ( X , W(X) ) be a T0-space. Show that the following conditions are equivalent:
    1. The topology W is the Alexandrov topology on the specialization order of the space X ;
    2. The meet semilattice W is complete;
    3. Every point of X has a smallest open neighborhood.

Third graded homework due 3/23:
Three questions from the following:
  1. Show that a lattice is a chain if and only if all its proper ideals are prime.
  2. Show that each distributive lattice is isomorphic to a sublattice of the lattice of subsets of some set.
    1. Show that a subset of a Boolean algebra is an ideal of the Boolean algebra if and only if it is an ideal of the corresponding Boolean ring.
    2. Show that a subset of a Boolean algebra is a prime ideal of the Boolean algebra if and only if it is a prime ideal of the corresponding Boolean ring.
  3. Give an example of a maximal ideal M in a lattice L such that M is not a prime ideal of L. Justify all your claims.
  4. Let M be a monoid. Recall that an M-set is a set X such that for each element m of M and x of X, a unique element x·m is defined, satisfying the unital law:
    x·1 = x
    and the mixed associative law:
    (x·mn = x·(m n) .
    A subset Y of X is called an M-subset if y in Y and m in M imply y·m in Y.
    1. Show that the set of M-subsets of X forms a Heyting algebra under the order relation of containment.
    2. If M is a group, show that this Heyting algebra is a Boolean algebra.

Second graded homework due 2/18:
Three questions from the following:
  1. Show that the de Morgan law
    ( x + y ) ' = x ' · y '
    holds in any Heyting algebra, while the dual statement may fail.
  2. Show that the identity
    ( x · y ) ' ' = x ' ' · y ' '
    holds in any Heyting algebra.
  3. Show that in a Heyting algebra H, the following statements are equivalent:
    1. For all  x , y  in H, the equation ( x · y ) ' = x ' + y ' holds;
    2. For all  x  in H, the equation  x ' + x ' ' = 1  holds;
    3. For all  x  in H, the equation  x = x ' '  implies that  x  has a complement;
    4. The subset  { x | x = x ' ' }  of H forms a sublattice of H .
  4. Recall the symmetric difference operation
    x xor y = ( x · y' ) + ( x' · y )
    in a Boolean algebra.
    1. In a Boolean algebra, show that the operation
      P ( x , y , z ) = x xor y xor z
      is a Mal'tsev operation.
    2. Express the operation  P  of (i) in terms of the meet, join, and implication.
    3. If the result of (ii) is interpreted in a Heyting algebra, is it still a Mal'tsev operation? Justify your answer.
  5. In a poset ( X, < ) , a subset U is said to be an upper set or upset if for each element x of X, the existence of an element u in U with u < x implies x in U . Prove that the set of all upsets of a poset ( X, < ) forms a topology on X .

First graded homework due 1/28:
Three questions from the following:
  1. Express  { x | if P (x) then Q (x) else R (x) }  in terms of  { x | P (x) } ,  { x | Q (x) } , and  { x | R (x) } .
  2. Define nand by
    { x | P (x) nand Q (x) } = [ { x | P (x) } · { x | Q (x) } ] ' .
    Show that in a general Boolean algebra, each of the Boolean algebra operations + , · , and ' may be expressed entirely in terms of the nand operation  x | y = ( x · y ) ' and the constant 0.
  3. In a ring R (with 1), each element x satisfies  x3 = x . Is  3 x = 0 ?
  4. In a ring R (with 1), each element x satisfies  x3 = x  and  3 x = 0 . Prove that R is commutative.
  5. Is the assumption of the existence of a multiplicative identity 1 necessary in Exercise 4?

1/10 for 1/14: Read Sections 1.1 - 3, do the Exercise at the end of 1.3.