Ling 726: Mathematical Linguistics, Algebra, Section 2 V. Borschev and B. Partee, September 24, 2004 p. 1 Lecture 4. Algebra, continued Section 2: Lattices and Boolean algebras CONTENTS 1. Lattices. ...................................................................................................................................................... 1 1.0. Why lattices? ....................................................................................................................................... 1 1.1. Posets................................................................................................................................................... 1 1.1.1. Upper and lower bounds. Duality................................................................................................. 1 1.1.2. Diagrams of posets. ...................................................................................................................... 2 1.2. Lattices and semilattices...................................................................................................................... 3 1.2.1. Lattices. ........................................................................................................................................ 3 1.2.2. Semilattices................................................................................................................................... 4 2. Boolean algebras. ....................................................................................................................................... 4 Homework 5. .................................................................................................................................................. 5 Reading: Chapter 11: 11.1 – 11.2 of PtMW, pp. 275-281; Chapter 12: 12.1 – 12.2 of PtMW, pp.295 –299. Supplementary material on Boolean algebra in xeroxed extract from: Partee (1979) Fundamentals of Mathematics for Linguists. Stamford, CT: Greylock Publishers. Reprinted by D.Reidel, Dordrecht. (III.D. Boolean algebras. 127-136.) Some aspects of what’s covered in both readings will make more sense after we have looked at logic, but if you know a little logic already you can probably make sense of it. When we look at logic, we’ll come back to this so that we can see how useful quotient algebras are for showing how propositional logic can be a Boolean algebra. 1. Lattices. 1.0. Why lattices? There is a special class of algebraic structures, called lattices, which are used widely in many fields, and it is useful to be familiar with their basic properties. Lattices can be defined as algebras and they will be our first example of a specific kind of algebra. In this lecture we will also consider Boolean algebras, which are a special case of lattices. We will just be introducing the basic structure of lattices and Boolean algebras with some examples; there are many directions one can go from here, both in algebraic studies and in applications. 1.1. Posets. In Lecture 1 we considered the relation of weak order (reflexive, anti-symmetric and transitive). Such a relation is also called a partial order (because it is not obligatorily a total order). Any set A on which a partial order ≤ is defined is called a partially ordered set or poset and write it as <A, ≤ > or just A assuming the intended order. 1.1.1. Upper and lower bounds. Duality. Elements a and b of a poset A are called comparable if a ≤ b or b ≤ a. If they are not comparable, they are called incomparable.Ling 726: Mathematical Linguistics, Algebra, Section 2 V. Borschev and B. Partee, September 24, 2004 p. 2 In an arbitrary poset A we define an upper bound of B ⊆ A [note1] as an element a ∈ A, if it exists, such that for all b ∈ B, b ≤ a. An upper bound a of B is the least upper bound of B or the supremum of B (abbreviated to sup B) if, for any upper bound c of B, we have a ≤ c. We write a = sup B, since by antisymmetry of the ordering ≤ we know that if B has a least upper bound, this is a unique least bound. It is easy to see that the inverse relation of the partial order ≤ is also a partial order. We write a ≥ b for b ≤ a, call the order ≥ the dual order to ≤ and call the poset <A, ≥ > with a dual order the dual poset to the poset <A, ≤ >. Many notions on posets and other structures will have their dual versions when we replace all the occurrences of the order ≤ in definitions on the order ≥ . The first examples will be lower bound and the greatest lower bound. We define the dual of an upper bound of B ⊆ A, called a lower bound of B ⊆ A, as an element a ∈ A, such that for all b ∈ B, b ≥ a which is equivalent to a ≤ b. A lower bound a of B is the greatest lower bound of B or the infimum of B (abbreviated to inf B) if, for any lower bound c of B, we have a ≥ c. We write a = inf B. 1.1.2. Diagrams of posets. Partial ordering may be represented visually by so called Hasse diagrams. The diagram of poset A represents the elements of the set A as points on the plane and the ordering relation pictured as a line reflecting the order from the bottom to top in the representation. Assuming reflexivity and transitivity of the order, only lines for immediate successors are pictured. See examples of diagrams below (examples are extracted from PtMW). In the Figure 11-1 below 0 ≤ a, 0 ≤ b, a ≤ 1, b ≤ 1 and corresponding “reflexive” and “transitive” pairs also belong to the order. 1 o a o o b o 0 Figure 11-1: the diagram of a poset A = <{0,a,b,1}, ≤ >. 1 A note on terminology. When we write “an upper bound of B ⊆ A”, that is a shortcut way of writing “an upper bound of a subset B in a set A”, i.e. an upper bound in A of some subset B of elements of A.Ling 726: Mathematical Linguistics, Algebra, Section 2 V. Borschev and B. Partee, September 24, 2004 p. 3 1.2. Lattices and semilattices. 1.2.1. Lattices. There is a special class of posets, called lattices. On the other hand, lattices can also be defined as algebras. We consider both definitions. Definition 1. A poset <A, ≤ > is a lattice if sup{a,b} and inf{a,b} exist for all a,b ∈ A. In order to develop the second definition, we introduce two new operations on A: (Op) a ∧ b = inf{a,b} and a ∨ b = sup{a,b}, calling a ∧ b the meet and a ∨ b the join of a and b. In lattices these operations are binary. So we can consider a lattice