I. Posets, Lattices, and Categories (chapter 2) ------------------------------------------ ASCII NOTATION In the following, we write ``.'' for function application, ``!'' for complement, ``;'' for forward composition, ``o'' for backward composition _ ``\meet'' for meet (| |), ``\intersect'' for intersection, ``\join'' for join (|_|), ``\union'' for union, ``<='' for the ordering (\sqsubseteq), ``>='' for the inverse ordering, ``<'' for strict ordering (\sqsubset), ``>'' for strict inverse ordering ``\subseteq'' for non-strict subset, ``\supseteq'' for nonstrict superset, ``\subset'' for strict subset, ``\supset'' for strict superset, ``=='' for equality, ``/\'' for conjunction (and), ``\/'' for disjunction (or) ``==>'' for implication ``<=='' for consequence ``<==>'' for logical equivalence This table is also arranged in precedence order, with "not" having the highest precedence (binding most tightly). ------------------------------------------ A. partially ordered sets (2.1) what is a preorder? what is a preordered set? what is a partial order? what is a partially ordered set (poset)? what's the smallest example of a partially ordered set? what's another example? are there infinite partially ordered sets? what's an example of a set with a discrete order? what's an example of a set with a linear order? do does it make sense to talk about the least element of a preordered set? what is the greatest element of an entire partially ordered set? does that always exist? Is it unique? what's the Hasse diagram for the booleans ordered by implication look like? for the subsets of the set {6, 4, 1}? 1. congruence and monotonicity What's an example of a monotonic function on the natural numbers? what's an example of a antimonotonic function on the natural numbers? what's on several function that is neither monotonic nor antimonotonic on the natural numbers? what's an order embedding of the natural numbers into the Booleans? Is every order embedding injective (i.e., 1 to 1)? Is every injective monotonic function an order embedding? consider subtraction on integers, in what argument is it monotonic? 2. meet and join how would you define a lower bound of a set? The greatest lower bound? in a poset, is a lower bound of a subset an element of that subset? what is the greatest lower bound (infimum, or meet) of a subset in a partially ordered set? does it always exist? is it meaningful to take the glb of an empty set? what properties characterize the mean of two elements in a partially ordered set? How does all this relate to upper bounds and the least upper bound (supremum, join)? ------------------------------------------ Lemma 2.1 (correspondence) Let a, b be elements of a poset. Then a \meet b == a <==> a <= b a \join b == b <==> a <= b. ------------------------------------------ how would you prove this? What's join in the Booleans? what is the join operation in the power set poset? in the natural numbers? B. lattices (2.2) In a lattice, can we consider meet and join to be operators? What's the unit of the meet operator in the Booleans? the zero? Is the unit of the meet operator in a lattice always the top element? what's an example of a partially ordered set that is not a lattice? What does absorbtion mean for the booleans? If a poset has a top element is it a lattice? If a poset has a bottom element, do meets exist in it? If a poset is bounded, is it a lattice? 1. complete lattices what's an example of a lattice that is not a complete lettuce? is every finite lattice a complete lattice? does every complete lattice have a top and a bottom? Why? what do meet and join of infinite sets correspond to in the Booleans? are the natural numbers a complete lattice? what about the set of functions from a complete lattice to another complete lattice? Does the domain have to be a complete lattice? If a lattice has a bottom and a top element, is it complete? 2. distributive lattices what is the advantage of having distributivity? Which lattices we've seen are distributive? Is Nat distributive? 3. Boolean Lattices what does a complete Boolean lattice have that a complete distributive lattice doesn't? is the subset lattice a boolean lattice? Are the natural numbers a complete Boolean lattice? why? 4. atomic lattices what is an atom in a lattice? what are atoms useful for? So what's the best example of a complete, boolean, and atomic lattice? 5. duality What's the dual (or opposite) of a lattice? what's the dual of the Boolean lattice? The subset lattice? what properties are preserved by taking the dual of a lattice? should de Morgan have published two papers or just one? C. product and function spaces (2.3) 1. product spaces Is (1,3) less than (6,4)? Why? how is the ordering defined on the product? what's the bottom element of Nat x Nat? 2. function spaces what is the ordering for functions? can you give an example function ordering, on Nat -> Nat? Are functions on Nat -> Nat always comparable? Is Nat -> Nat a poset? A lattice? A complete lattice? Are functions on Nat -> Bool always comparable? Is Nat -> Bool a poset? A lattice? A complete lattice? What does the pointwise extension Lemma (2.5) tell us about relations? Are binary relations ordered by subset inclusion an atomic lattice? D. Lattice Homomorphisms (2.4) What's a meet homomorphism? a join homomorphism? What kind of homomorphism is a strict function? How would you summarize the property of preserving X (being X-homomorphic)? What's an embedding? Why is that an appropriate term? An epimorphism? An image? What's an isomorphism? Is being "isomorphic" an equivalence relation? 1. binary lattice operations as homomorphisms how could we regard the meet operation as a homomorphism? What property defines a function that is universally meet homomorphic? Positively meet homomorphic? Can a function a universal join homomorphism if it is strict and preserves least upper bounds of nonempty sets? can a function be a positive meet homomorphism without being a meet homomorphism? 2. tabular representation (skip) E. categories (2.5) What is a concrete category? what's an example of a concrete category? Would the collection of posets and non-monotonic functions be a category? 1. abstract categories what's the difference between an abstract and concrete category? what features does a category have? Why isn't the category of relations a concrete category? How is an abstract category different than a directed graph? How is an abstract category different than a preorder? 2. functors and homomorphisms if we consider categories themselves to the objects, what structure would their morphisms preserve? If a category is like a preorder, how is a functor like a monotonic function? 3. order-enriched categories what is an order enriched category? what is a left order-enriched category? Is the category of relations in the subset ordering order-enriched?