# UMass Amherst LINGUIST 726 - LINGUIST 726 Lecture Notes (6 pages)

Previewing pages*1, 2*of 6 page document

**View the full content.**## LINGUIST 726 Lecture Notes

Previewing pages
*1, 2*
of
actual document.

**View the full content.**View Full Document

## LINGUIST 726 Lecture Notes

0 0 39 views

- Pages:
- 6
- School:
- University of Massachusetts Amherst
- Course:
- Linguist 726 - Mathematical Linguistics

**Unformatted text preview:**

Ling 726 Mathematical Linguistics Algebra Section 2 V Borschev and B Partee September 21 26 2006 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 for Sept 28 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 21 26 2006 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 ao ob 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 21 26 2006 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 as an algebra in a signature But not every algebra in that signature is a lattice To be a lattice its operations should have some properties It is easy to see that operations defined by Op have the properties L1 L4 L1 L2 L3 L4 a a a a a a a b b a a b b a a b c a b c a b c a b c a a b a a a b a idempotent law commutative law associative law absorption law With the help of these properties we can give another definition of lattices Definition 2 An algebra A in the signature on the carrier A is a lattice if properties L1 L4 hold for its operations It is not very difficult to show that these two definitions are equivalent Indeed as we have seen for the lattice A with the order from definition 1 the operations and given by Op define on A the algebra A and have the properties L1 L4 If we consider the order 1 defined by these operations by the condition Ord a 1 b iff a b a we will get the same order that we have in the lattice A On the other hand if we begin from definition 2 and define on the carrier A of the algebra A the order corresponding to the condition Ord the conditions of the …

View Full Document