Assignment #9

Assignment due in lecture on Friday, March 14.

Reading: Review Burris and Sankappanavar, pp. 19-20 on algebraic lattices¹.

To do but not hand in:

DD-1;

B&S, p. 20 Problem 8.

To hand in:

AA-10 (see below);

DD-4, DD-5;

B&S p. 20 Problem 9, just the last assertion about an algebraic lattice.

For AA-10: Explanation of Shallon's graph algebra:

For a graph $G$, we can make an algebra ${\cal A} _ G = \langle G \cup \{0\} ; \cdot \rangle$, where 0 is a new element not in $G$. The ``multiplication'' operation $\cdot$ is defined for any $x, y$ by setting $x y = x$ if $x$ and $y$ are in $G$ and are connected by an edge, and $x y = 0$ otherwise. In particular $x 0 = 0 x = 0$ for all $x$, and $x x = x$ if there is a loop at $x$.

Consider this specific graph $G _ 3$ with loops:

$\parbox{1in}{\includegraphics{text/Adir/shallon2.eps}}$

Thus $a _ 1 a _ 1 = a _ 1$, $a _ 1 a _ 2 = a _ 1$, and $a _ 2 a _ 1 = a _ 2$, but $a _ 1 a _ 3 = 0$. ${\cal A} _ {G _ 3}$ is Shallon's algebra², referred to as ${\cal A} _ 3$ in Problem AA-10.