### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# MATHFOUNDCOMPSCI CIS160

Penn

GPA 3.73

### View Full Document

## 36

## 0

## Popular in Course

## Popular in Computer Information Technology

This 181 page Class Notes was uploaded by Kathleen Cartwright on Monday September 28, 2015. The Class Notes belongs to CIS160 at University of Pennsylvania taught by Staff in Fall. Since its upload, it has received 36 views. For similar materials see /class/215381/cis160-university-of-pennsylvania in Computer Information Technology at University of Pennsylvania.

## Reviews for MATHFOUNDCOMPSCI

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/28/15

Introduction to Proof Theory 24th Septem ber 2004 Introduction to Proof Theory Outline of the talk 9 Hilbert s Proof System 0 Proofs via Natural Deduction 0 LK Sequent Calculus 0 Examples of Proofs in LK Sequent Calculus 0 Cut Elimination Theorem and the Subformula Property 0 Symmetry and Non Constructivism of LK 0 Introducing Intuitionistic Logic 9 Comparison between Intuitionistic and Classical Provability 0 Going further a Taste of Linear Logic Introduction to Proof Theory Hilbert39s Proof System propositional case Idea Logical Axioms and One Deduction Rule H1 A a B a A H2 ABCABgtAgtC H3 AABA H4 A A B a B H5 A a B a A A B H6 AjAVB H7 BjAVB H8 ACBCAVBC H9 HA A 1 H10 A 1 HA H11 1A H12 AVHA Introduction to Proof Theory Example of a proof in HPF Let us prove the following theorem F A a A 0AgtAgtAgtAgtAgtAgtAgtAgtA H2 oAAAA H1 oAAAAA MP oAAA H1 oAA MP Introduction to Proof Theory Meta properties Deduction theorem r A B then Fr A gt Introduction to Proof Theory Hilbert Proof System allows to study provability but is not convenient for studying the proofs themselves Introduction to Proof Theory Natural Deduction 1 Rules m Axiom FFA FFBA RAFB I FFA FFAAB FFA8 I39FAABA FFAAB WA A El FFB a FFA FFAgtB VFW FFB E FFMV VE For this rule X FV39A 7 IIIIIIIIIIIlllllll a llllllll I39FAABiCAX rrAAB AABCABrC Ea FAABCABC Introduction to Proof Theory Natural Deduction 2 Dynamics of Proofs One can consider transformations ofproofs via the notion of cut an introduction rule immediately by an elimination rule on the same connective H2 lll RAPE l FA l FAiB l FB i 55 a we This system has very good properties confluence strong normalization Introduction to Proof Theory Natural Deduction 3 Existential and Disjunction I39FA I39FB WAVBV L WAVBV 2 WAVB mwc 39BFC VE WC WAtX WaXA RAFC WW 35 W RAH I39toA WA FWAH I39F A Wt E WA LC X is not free in I397 C Introduction to Proof Theory Defects of Natural Deduction o The notion of cut is implicit there is no explicit rule for the cut 0 ND is satisfying only for a fragment of intuitionistic logic a A V Paradoxically the connectives which are the most interesting for intuitionistic logic are V and 3 Introduction to Proof Theory Natural Deduction is close to actual mathematical reasoning but lacks structure Introduction to Proof Theory Sequent Calculus Explicit Cut Rules dedicated to the management of the formulas Deep left right symmetry of the system introductionelimination rules on the right are replaced by leftright introduction rules Introduction to Proof Theory LK Rules 1 Identity Rules Axiom and Cut AX I 1FA7A1 r27AFA2 C ArA 0 quot rhrerIAZ t Structural Rules Exchange Weakening and Contraction r1BA 2FA LE I FA1787A7A2 RE r1ABr2rA X rrA1ABA2 X WA WA RAFALW WAA RW rAArA rrAAA rArA LC WAA RC Introduction to Proof Theory LK Rules 2 Logical Rules o A V i V 3 WAA rArA r7 AFA b FFoAA R rArA RBrA WAA rrBA rAABrA 1 rAABrA 2 rrAABA RA rArA RBrA WAA rrBA RAVBrA LV rrAvBA RVl rrAvBA RV2 Introduction to Proof Theory LK Rules 3 rerAl r2BrA2 rArBA R r1r2ABrA1A2 rrABA rAtx rA WAA varA LV rrvaA R m rArA rrAtXA r axA r A La m r r am A For these rules X FV A Introduction to Proof Theory Formal Theorems 0 A V B F B V A Commutativity of disjunction o F A V A Tertium non datur o F A a B a A a A Peirce s Law 0 F A A Elimination of Double Negation o F HXVyPX Py The Drinker Property 9 A V B F A A B An Instance of de Morgan s Laws 0 FABVBA o F A V A 39intuitionistic39 Tertium non datur piquwp oqiopwwiq Introduction to Proof Theory Alternative Rules for and rABrA rerAl rerAz rAABrAM rhrerABAhAz RA rhArA1 r2BrA2 rrABA Lv RV r1r2AvBrA1A2 rrAVBA These new rules are called multiplicative rules while the original rules of LK are called additive rules Both sets of rules are equivalent thanks to the structural rules Introduction to Proof Theory Gentzen39s Cut Elimination Result Gentzen s Hauptsatz The Cut rule is admissible in LK In fact Gentzen s result was more than simply a proof of admissibility of the cut since he gave an explicit procedure to eliminate the cuts from a proof starting with a proof with cuts we can step by step transform it into a cut free proof and this procedure is algorithmic Introduction to Proof Theory SubtormulaPropety Subformula Property A provable Sequent can be proved using only subformulas of the formulas appearing in the sequent A cut free proof only makes use ofsubformulas of the root sequent It reduces the search space a lot Introduction to Proof Theory Symmetry of LK l Sequents are now of the form V I39 Implication is a defined connective A a B E A V B Negation only appears on atomic formulas thanks to de Morgan s laws A V B E A A B VXA E Hx A A A B E A V B xA E VX A More precisely when writing A we will always mean the negation normal form of this formula for the obviously terminating and confluent rewriting system AVB gt AA B E VXAHHXE A AAB gt AV B E HXAHVXE A A gt A Introduction to Proof Theory Symmetry of LK 2 Identity Rules HAFH A m Axiom H RA Cut Structural Rules HER47A Hr W HAAJ C HnAaA X HAr HAr Logical Rules HArwar HAr war v1 v2 rAAar rAvar rAvar HAr HAtxJ 77 4 3 rwAr ram Introduction to Proof Theory N n Constructivism of LK Proposition There exist two irrational numbers a7 b such that ab is rational Consider the Irrational number Either f is rational or it is not In the first case we are done taking a b while in the latter we set a to be and b to be and obtain ab yi z 2 D The peculiarity with this proof is that having completed the proof 2 we have no evidence about the Irrationality of It Is actually irrational but the proof of this fact is much more complicated Introduction to Proof Theory LK is symmetric but non constructive Introduction to Proof Theory tionism All began with Brouwer who rejected the excluded middle principle Why A view of mathematics centered on the mathematician so that the formula A is understood as quotI know that A or more precisely as quotI have a proof of A With this in mind the logical connectives and the logical rules must be reconsidered In particular the disjunction AV B means quotI have a proof of A or I have a proof of B and the excluded middle is no more a suitable logical principle since A V A means that we always have a proof of a formula or of its negation which is a very strong requirement Constructivism a proof must provide a way to build an object that represents the property we proved Introduction to Proof Theory What Disjunction We saw two possible rules for disjunction on the right rrAaA rrAvaA and rrAA rraA rrAvaA rrAvaA Which one shall we choose for intuitionistic logic Introduction to Proof Theory LJ Sequent Calculus Identity Rules I39lkA F27AFE m axiom r17 D F E cut Structural Rules FLRAJ FE Fr Fr RAAFE rhABJ5r3Lamp nArELW rrARW nAr LC Logical Rules rrA RAF naAriL FFAA R nrA FBFE nArB ma jerL rrAstj Introduction to Proof Theory LJ Rules 2 r3252 FngELA2 FIESAREBRA F ArfAEVBr rstELV I39FI ZCBRVZL rgggsR For this rule X FV39 For this rule X FV39E Introduction to Proof Theory Disjunction and Existence Properties Thanks to cut elimination we have Disjunction Property Ifi LJAVB then i LJ A orPLJ B Existence Property If PLJ HxA then there exists a term t such that PLJ Atx Introduction to Proof Theory LJ is constructive but non symmetric Introduction to Proof Theory Correspondence between classical and intuitionistic provability 1 LJ is clearly weaker than LK I F A implies I km A Can we make more precise the relation between the two notions of provability We will see that LJ can be considered not to be weaker than LK but finer Introduction to Proof Theory Correspondence between classical and intuitionistic provability 2 Remember that in LJ contraction is not available on the right of h but it is freely available on the left AV A is not provable in LJ but AV A is m AXi0r71 A h A V A L A v A A r I A v A r A 7 A A rAv A Z m Axiom hA7 A r AA A RV AV A A A r RV A A r LC r A A R rAv AA A RC hAv A Correspondence between classical and intuitionistic provability 3 Gb39del Translation The idea of the intuitionistic proof of A V A is to send the formula to the left so that it is possible to use left contraction The occurrence of the double negation e precisely allows to cross twice the h and to use left contraction Definition Go39del Translation o Aquot A forA atomic o AAB AAB VXAY VXA A k s B A a 3 Introduction to Proof Theory on39dence between classical and intuitionistic r km A iff39 m A FLK A ltgt A Definition A is said to be stable when FLJ A 9 A For all formula A Aquot is stable lfi FLK A then P iA i LJ Correspondence between classical and intuitionistic provability 5 In what sense can we say that LJ is finer subtler than LK An intuitionistic logician cannot necessarily prove a formula A when a classical mathematician can BUT he can find another formula A that he is able to prove and that the classical mathematician cannot distinguish from the previous one In particular in intuitionistic logic the use of excluded middle or contraction on the right shall be explicitly mentioned in the formula thanks to the use of double negation Introduction to Proof Theory Is it possible to be even more drastic with structural rules7 Linear Logic Introduction to Proof Theory Does Classical Logic allow to model everything Introduction to Proof Theory Let us remove all the structural rules The two alternative presentations of disjunction and of conjunction are no more equivalent We have two different conjunctions and two different disjunctions We need to recover the contraction and weakening rules but in a controlled way Introduction to Proof Theory LL Sequent Calculus Identity Rules 7 3X M t r Al A r r A C Structural Rule F I397 B7 A7 A r 39A BA EX Introduction to Proof Theory LL Sequent Calculus Logical Rules FFG39 FF39 FGA FFQGJ39 FF G39A FF39 kGI39amp FF39 1 mar 2 FFampG39 FFGBGJGB FFGBGJGB 7 i F11 FLI39L FTJT FF397 FFJI39I HFJ39 HFquot H HFF HFr7W 7C FIRI Important Characteristics of Linear Logic Thanks to the additional structure put in the sequents themselves we can capture more things at the logical level and not at the term level like in classical logic The control on structural rules allows a careful study of cut elimination which via Curry Howard corresponds to execution of a functional program Thanks to the richness of the sequents it is possible to consider the sequents as storing a state of the computation in a process of proof search logic programming paradigm Lots of other directions Introduction to Proof Theory Conclusion The rules that at first seemed to be the less significant in logic at such an extent that they are missing in Natural Deduction are eventually crucial in the proof theoretic analysis of logic Indeed it is by controlling these rules that we can choose the focus we want to put on logic and the level of detail we desire Controlling the structural rules we can zoom and catch more details of the proofs From the computer science point of view the very structured object that a LL proof is allows for various uses and applications Less formally and more informally an interest of this study of structure is that we came from a logical study driven by the notion of truth and that now we can do logic as study of geometrical properties of proofs the logical character being assured by some formal requirement such as cut elimination symmetrical properties Introduction to Proof Theory Chapter 5 Partial Orders Lattices Well Founded Orderings Equivalence Relations Distributive Lattices Boolean Algebras Heyting Algebras 51 Partial Orders There are two main kinds of relations that play a very important role in mathematics and computer science 1 Partial orders 2 Equivalence relations In this section and the next few ones we de ne partial orders and investigate some of their properties 459 460 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES As we will see the ability to use induction is intimately related to a very special property of partial orders known as well foundedness lntuitiyely the notion of order arnong elements of a set X captures the fact some elements are bigger than oth ers perhaps more important or perhaps that they carry more information For example we are all familiar with the natural ordering g of the integers 3 2 10123 7 the ordering of the rationals where 1 g 1 iff 1 Z 0 16 292611 291612 2 0 if 611612 gt 0 else 92611 19qu g 0 if qqu lt 0 and the ordering of the real numbers In all of the above orderings note that for any two number a and I either a g b or b g a We say that such orderings are total orderings 51 PARTIAL ORDERS 461 A natural example of an ordering which is not total is provided by the subset ordering Given a set X we can order the subsets of X by the subset relation A Q B where A B are any subsets of X For example if X ab C we have a Q ab However note that neither a is a subset of I C nor 1 C is a subset of a We say that a and 1 C are incomparable Now not all relations are partial orders so which prop erties characterize partial orders 462 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES De nition 511 A binary relation 3 on a set X is a partial order or partial ordering iff it is reflexive transitive and antisymmetric that is 1 Re exivity a g a for all a E X 2 Transitivity If a g b and b g C then a g C for all a b C E X 3 Antisymrnetry If a g b and b g a then a b for all a b E X A partial order is a total order ordering or linear order ordering iff for all ab E X either a g b or b g a When neither a g b nor b g a we say that a and b are incomparable A subset C Q X is a Chain iff g induces a total order on C so for all a b E C either a g b or b g a 51 PARTIAL ORDERS 463 The strict order ordering lt associated with g is the relation de ned by a lt b iff a g b and a y b If g is a partial order on X we say that the pair X gt is a partially ordered set or for short a poset Remark Observe that if lt is the strict order associated With a partial order lt then lt is transitive and anti 7 7 reflexive which means that 4a7 aforalla X Conversely let lt be a relation on X and assume that lt is transitive and anti re exive Then we can de ne the relation 3 so that a g b iff a b or a lt b It is easy to check that g is a partial order and that the strict order associated with g is our original relation lt 464 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Given a poset ltX gt by abuse of notation we often refer to X gt as the poset X the partial order 3 being implicit If confusion may arise for example when we are dealing with several posets we denote the partial order on X by EX Here are a few examples of partial orders 1 The subset ordering We leave it to the reader to check that the subset relation Q on a set X is indeed a partial order For example if A Q B and B Q A where A B Q X then A B since these assumptions are exactly those needed by the extensionality axiom 2 The natural order on N Although we all know what is the ordering of the natural numbers we should realize that if we stick to our axiomatic presentation where we de ned the natural numbers as sets that belong to every inductive set see De nition 1103 then we haven t yet de ned this ordering 51 PARTIAL ORDERS 465 However this is easy to do since the natural numbers are sets For any m n E N de ne m g n as m n or m E n Then it is not hard check that this relation is a total order Actually some of the details are a bit tedious and require induction see Enderton 4 Chapter 4 3 Orderings on strings Let Z a1 an be an alphabet The pre x suf x and substring relations de ned in Section 211 are easily seen to be partial orders However these orderings are not total It is some times desirable to have a total order on strings and fortunately the lexicographic order also called dic tionnary order achieves this goal 466 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES In order to de ne the lexicographic order we assume that the symbols in Z are totally ordered on lt a2 lt lt on Then given any two strings uv E 2 we set if v uy for some 3 E 2 or if u maiy v majz and a lt a for some 51 y z E 2 ujv In other words either it is a pre x of v or else it and 1 share a common pre x x and then there is a differring symbol a in u and aj in v With a lt aj It is fairly tedious to prove that the lexicographic order is a partial order Moreover the lexicographic order is a total order 51 PARTIAL ORDERS 467 4 The divisibility order on N Let us begin by de ning divisibility in Z Given any two integers a b E Z with b 74 0 we say that b divides a a is a multiple of b iii a bq for some q E Z Such a q is called the quotient of a and Z Most number theory books use the notation b l a to express that b divides a For example 4 l 12 since 12 4 3 and 7 l 21 since 21 7 3 but 3 does not divide 16 since 16 is not an integer multiple of 3 We leave the veri cation that the divisibility relation is re exive and transitive as an easy exercise It is also transtive on N and so it indeed a partial order on N1 468 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Given a poset ltX gt if X is nite then there is a convenient way to describe the partial order 3 on X using a graph Consider an arbitrary poset ltX gt not necessarily nite Given any element a E X the following situations are of interest 1 For no b E X do we have b lt a We say that a is a minimal element of X 2 There is some b E X so that b lt a and there is no c E Xsothatb lt c lt a Wesaythatbisan immediate predecessor of a 3 For no b E X do we have a lt b We say that a is a maximal element of X 4 There is some b E X so that a lt b and there is no c E Xsothata lt c lt b Wesaythatbisan immediate successor of a 51 PARTIAL ORDERS 469 Note that an element may have more than one immediate predecessor or more than one immediate successor If X is a nite set then it is easy to see that every element that is not minimal has an immediate predecessor and any element that is not maximal has an immediate successor why But if X is in nite for example X Q this may not be the case lndeed given any two distinct rational numbers a b E Q we have 01 b 2lt alt Let us now use our notion of immediate predecessor to draw a diagram representing a nite poset ltX gt The trick is to draw a picture consisting of nodes and oriented edges where the nodes are all the elements of X and where we draw an oriented edge from a to b i a is an immediate predecessor of b 470 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Such a diagram is called a Hesse diagram for X gt Observe that if a lt c lt b then the diagram does not have an edge corresponding to the relation a lt b A Hasse diagram is an economical representation of a nite poset and it contains the same amount of information as the partial order g Here is the diagram associated with the partial order on the power set of the two element set a b M Figure 51 The partial order of the power set 29 51 PARTIAL ORDERS 471 Here is the diagram associated With the partial order on the power set of the three elemerit set a b C awe Figure 52 The partial order of the power set 2mm Note that 0 is a minimal element of the above poset in fact the smallest element and a b C is a maximal el emerit in fact the greatest element In the above example there is a unique miriimal resp maximal elemerit 472 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES A less trivial example with multiple minimal and maximal elements is Obtained by deleting 0 and a b C 97 c a c a b a b C Figure 53 Minimal and maximal elements in a poset Given a poset X gt Observe that if there is some ele ment m E X so that m g L fOI allCL E X thenmis unique Such an element m is called the smallest or the least element of X 51 PARTIAL ORDERS 473 Similarly an element b E X so that 1 g b for all 1 E X is unique and is called the greatest element of X We summarize some of our previous de nitions and in troduce a few more useful concepts in De nition 512 Let X gt be a poset and let A Q X be any subset of X An element b E X is a lower bound ofAiffbgaforallaEA An element m E X is an upper bound of A iff a g m for all a E A An element b E X is the least element of A iff b E A andbgaforallaEA An element m E X is the greatest element of A iff mEAandagmforallaEA 474 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES An element b E A is minimal m A iff a lt b for no a E A or equivalently if for all a E A a g b implies that a b An element m E A is maximal m A iff m lt a for no a E A or equivalently if for all a E A m g a implies that a m An element b E X is the greatest lower bound of A iff the set of lower bounds of A is nonempty and if b is the greatest element of this set An element m E X is the least upper bound of A iff the set of upper bounds of A is nonempty and if m is the least element of this set 51 PARTIAL ORDERS 475 Remarks 1 If b is a lower bound of A or m is an upper bound of A then b or m may not belong to A 2 The least element of A is a lower bound of A that also belongs to A and the greatest element of A is an upper bound of A that also belongs to A When A X the least element is often denoted i sometimes 0 and the greatest element is often denoted T sometimes 1 3 Minimal or maximal elements of A belong to A but they are not necessarily unique 4 The greatest lower bound or the least upper bound of A may not belong to A We use the notation A for the greatest lower bound of A and the notation V A for the least upper bound of A 476 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES In computer science some people also use A instead of V A and the symbol upside down instead of When A ab we write a b for ab and a V b for a b The element a b is called the meet of a and b and aVb is the join of a and I Some computer scientists useal lbforaAbandaleforaVb Observe that if it exists AU T the greatest ele ment of X and if its exists V 0 l the least element of X Also if it exists X J and if it exists X T For the sake of completeness we state the following fun damental result known as Zorn s Lemma even though it is unlikely that we will use it in this course 51 PARTIAL ORDERS 477 Figure 54 Max Zorn7 1906 1993 Zorn s lemma turns out to be equivalent to the axiom of choice Theorem 513 Zorn s Lemma Given a poset X 3 if every nonempty chain in X has an upper bound then X has some mammal element When we deal with posets7 it is useful to use functions that are order preserving as de ned next De nition 514 Given two posets X x and Y7 ygt7 a function7 f X gt Y7 is monotonic or order preserving iff for all a b 6 X7 if agxb then fa yfb 478 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES 52 Lattices and Tarski s Fixed Point Theorem We now take a closer look at posets having the property that every two elements have a meet and a join a greatest lower bound and a least upper bound Such posets occur a lot more than we think A typical example is the power set under inclusion Where meet is intersection and join is union De nition 521 A lattice is a poset in Which any two elements have a meet and a join A complete lattice is a poset in Which any subset has a greatest lower bound and a least upper bound According to part 5 of the remark just before Zorn s Lemma observe that a complete lattice must have a least element L and a greatest element T 52 LATTICES AND TARSKI S FIXED POINT THEOREM 479 Figure 55 JW Richard Dedekind7 1831 1916 left7 Garrett Birkhofl7 1911 1996 middle and Charles S Peirce7 1839 1914 right Figure 56 The lattice 2 7b70 Remark The notion of complete lattice is due to G Birkhoff 1933 The notion of a lattice is due to Dedekind 1897 but his de nition used properties LU L4 listed in Proposition 522 The use of meet and join in posets was rst studied by C S Peirce 1880 Figure 56 shows the lattice structure of the power set of a 190 It is actually a complete lattice 480 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES It is easy to show that any nite lattice is a complete lattice and that a nite poset is a lattice iff it has a least element and a greatest element The poset N under the divisibility ordering is a lattice Indeed it turns out that the meet operation corresponds to greatest common divisor and the join operation cor responds to least common multiple However it is not a complete lattice The power set of any set X is a complete lattice under the subset ordering The following proposition gathers some useful properties of meet and join 52 LATTICES AND TARSKI S FIXED POINT THEOREM 481 Proposition 522 IfX is a lattice then the follow ing identities hold for all a b c E X L1 aVbbVa abba L2 aVbVcaVch aAbcabc L3 aVaa aaa L4 aVbaa aAbVaa Properties L1 correspond to commutativity prop erties L2 to associativity properties L3 to idem potence and properties L4 to absorption Further more for all a b E X we have ago i aVbb i aba called consistency Properties LU L4 are algebraic properties that were found by Dedekind 1897 A pretty symmetry reveals itself in these identities they all come in pairs7 one involving A the other involving V 482 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES A useful consequence of this symmetry is duality namely that each equation derivable from LU L4 has a dual statement obtained by exchanging the symbols and V What is even more interesting is that it is possible to use these properties to de ne lattices Indeed if X is a set together with two operations and V satisfying LU L4 we can de ne the relation a g b by a V b b and then show that g is a partial order such that and V are the corresponding meet and join Proposition 523 Let X be a set together with two operations and V satisfying the axioms L1 L4 of proposition 522 If we de ne the relation 3 by a g b i aV b b equivalently a b a then 3 is a partial order and X g is a lattice whose meet and join agree with the original operations and V 52 LATTICES AND TARSKI S FIXED POINT THEOREM 483 Figure 57 Alferd Tarksi 1902 1983 The following proposition shows that the existence of ar bitrary least upper bounds or arbitrary greatest lower bounds is already enough ensure that a poset is a corn plete lattice Proposition 524 Let X g be a poset IfX has a greatest element T and if every nonempty subset A ofX has a greatest lower bound A then X is a complete lattice Dually le has a least element J and if every nonempty subset A ofX has a least upper bound VA then X is a complete lattice We are now going to prove a remarkable result due to A Tarski discovered in 1942 published in 1955 484 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES A special case for power sets was proved by B Knaster 1928 First we de ne xed points De nition 525 Let X gt be a poset and let f X gt X be a function An element 1 E X is a xed point of f sometimes spelled xpomt iff x 51 An element 1 E X is a least resp greatest xed point of f if it is a xed point of f and if 51 S 3 resp y g L for every xed point 3 of f Fixed points play an important role in certain areas of mathematics for example topology differential equa tions and also in economics because they tend to capture the notion of stability or equilibrium We now prove the following pretty theorem due to Tarski and then immediately proceed to use it to give a very short proof of the Schroder Bernstein Theorem Theorem 2918 52 LATTICES AND TARSKI S FIXED POINT THEOREM 485 Theorem 526 Tarski s F ired Point Theorem Let X gt be a complete lattice and let f X gt X be any monotonic function Then the set F of xed points off is a complete lattice In particular f has a least xed point aimin a e X i fa g L and a greatest xed point xmax E X l a g It should be noted that the least upper bounds and the greatest lower bounds in F do not necessarily agree with those in X In technical terms F is generally not a sub lattice of X Now as promised we use Tarski s Fixed Point Theorem to prove the Schr der Bernstein Theorem 486 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Theorem 2918 Given any two sets A and B if there is an injection from A to B and an injection from B to A then there is a bijection between A and B The proof is probably the shortest known proof of the Schr der Bernstein Theorem because it uses Tarski s fixed point theorem a powerful result If one looks carefully at the proof one realizes that there are two crucial ingredients 1 The set C is closed under gof that is gofC g C 2 A C Q gB Using these observations it is possible to give a proof that circumvents the use of Tarski s theorem Such a proof is given in Enderton 4 Chapter 6 We now turn to special properties of partial orders having to do With induction 53 WELL FOUNDED ORDERINGS AND COMPLETE INDUCTION 487 53 WellFounded Orderings and Complete Induction Have you ever wondered why induction on N actually works The answer of course is that N was de ned in such a way that by Theorem 1104 it is the smallest inductive set But this is not a very illuminating answer The key point is that every nonempty subset of N has a least ele ment This fact is intuitively clear since if we had some nonempty subset of N with no smallest element then we could con struct an in nite strictly decreasing sequence so gtl 1 gt gtk2ngt Butthisisabsurd assucha sequence would eventually run into 0 and stop It turns out that the deep reason why induction works on a poset is indeed that the poset ordering has a very special property and this leads us to the following de ni tion 488 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES De nition 531 Given a poset ltX gt we say that g is a wellorder well ordering and that X is well ordered by 3 iff every nonempty subset of X has a least element When X is nonempty if we pick any two element subset a b of X since the subset a b must have a least element we see that either a g b or b g a ie every wellorder is a total order First let us con rm that N is indeed well ordered Theorem 532 WellOrdering ofN The set of nat ural numbers N is wellordered Theorem 532 yields another induction principle which is often more exible that our original induction principle This principle called complete induction or sometimes strong induction was already encountered in Section 23 53 WELL FOUNDED ORDERINGS AND COMPLETE INDUCTION 489 It turns out that it is a special case of induction on a well ordered set but it does not hurt to review it in the special case of the natural ordering on N Recall that N N Complete Induction Principle on N In order to prove that a predicate PM holds for all n E N it is enough to prove that 1 P0 holds the base case and 2 for every m E N if Vic E Nl lt m gt then As a formula cornplete induction is stated as P0Vm e NVl e Nk lt m Pk Pom Vn e swam 490 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES The difference between ordinary induction and complete induction is that in complete induction the induction hypothesis Vic E Nl lt m gt 1306 assumes that PUC holds for all k lt m and not just for m 1 as in ordinary induction in order to deduce This gives us more proving power as we have more knowl edge in order to prove We will have many occasions to use cornplete induction but let us rst check that it is a valid principle Theorem 533 The complete induction principle for N is valid Remark In our statement of the principle of complete induction we singled out the base case 1 and conse quently we stated the induction step 2 for every m E N excluding the case m 0 which is already covered by the base case 53 WELL FOUNDED ORDERINGS AND COMPLETE INDUCTION 491 It is also possible to state the principle of complete induc tion in a more concise fashion as follows Vm E NVk E Nk lt m gt Pk gt Pm gt Vn E NPn In the above formula observe that when m 0 which is now allowed the premise Vic E Nl lt m gt of the implication within the brackets is trivially true and so PO must still be established In the end exactly the same amount of work is required but some people prefer the second more concise version of the principle of complete induction We feel that it would be easier for the reader to make the transition from ordinary induction to complete induction if we make explicit the fact that the base case must be established 492 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Let us illustrate the use of the complete induction prin ciple by proving that every natural number factors as a product of primes Recall that for any two natural numbers a b E N with b 7A 0 we say that b divides diff d bq for some q E N In this case we say that d is divisible by b and that b is a factor of d Then we say that a natural number p E N is a prime number for short a prime if p Z 2 and if p is only divisible by itself and by 1 Any prime number but 2 must be odd but the converse is false For example 2 3 5 7 11 13 17 are prime numbers but 9 is not There are in nitely many prime numbers but to prove this we need the following Theorem 53 WELL FOUNDED ORDERINGS AND COMPLETE INDUCTION 493 Theorem 534 Euery natural number n 2 2 can be factored as a product of primes that is n can be written as a product n p71 1 pg where the pZs are pairwise distinct prime numbers and m 2 1 1 g i g h For example 21 3171 98 2172 and 396 223341 Remark The prime factorization of a natural number is unique up to permutation of the primes p1 pk but this requires the Euclidean Division Lemma However we can prove right away that there are in nitely primes Theorem 535 Given any natural number n 2 1 there is a prime number p such that p gt n Conse quently there are in nitely many primes Proof Consider m nl 1 494 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES As an application of Theorem 532 we prove the Eu clidean Division Lemma for the integers Theorem 536 Euclidean Division Lemma for Z Given any two integers ab E Z with b 74 0 there is some unique integer q E Z the quotient and some unique natural number r E N the remainder 0r residue so that abqr with O rlt For example 12 5 2 2 200 5 40 0 and 42823 6409 X 6 4369 The remainder r in the Euclidean division a bq r of a by b is usually denoted a mod I 53 WELL FOUNDED ORDERINGS AND COMPLETE INDUCTION 495 We Will now show that complete induction holds for a very broad class of partial orders called wellfounded 0r derings that subsume well orderings De nition 537 Given a poset ltX gt we say that g is a wellfounded ordering order and that X is well fonnded iff X has no in nite strictly decreasing sequence 0gt1gt E2gtgtngtn1gt The following property of well founded sets is fundamen tal Proposition 538 A poset ltX gt is wellfounded i every nonempty subset of X has a minimal ele ment So the seemingly weaker condition that there is no in nite strictly decreasing sequence in X is equivalent to the fact that every nonempty subset of X has a minimal element 496 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES If X is a total order any minimal element is actually a least element and so we get Corollary 539 A poset X gt is wellordered i g is total and X is wellfounded Note that the notion of a well founded set is more general than that of a well ordered set since a well founded set is not necessarily totally ordered Remark ordinary induction on N is valid iff cornplete induction on N is valid iff N is well ordered These equivalences justify our earlier claim that the abil ity to do induction hinges on some key property of the ordering in this case that it is a well ordering 53 WELL FOUNDED ORDERINGS AND COMPLETE INDUCTION 497 We nally come to the principle of complete induction also called trans nite induction or structural induc tion which as we shall prove is valid for all well founded sets Since every well ordered set is also well founded complete induction is a very general induction method Let X g be a well founded poset and let P be a pred icate on X ie a function P X gt true false Principle of Complete Induction on 21 Well Founded Set To prove that a property P holds for all z E X it suf ces to show that for every 1 E X if 1 is minimal or Py holds for all y lt x gtllt then PI holds 498 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES The statement is called the induction hypothesis and the implication for all x implies is called the induction step Formally the induction principle can be stated as V56 E XlVy E Xy lt a 5 1320 Pm gt Vz E XPz CI Note that if 1 is minimal then there is no 3 E X such that y lt x and V3 6 Xy lt 1 gt Py is true Hence we must show that PI holds for every minimal element x These cases are called the base cases Complete induction is not valid for arbitrary posets see the problems but holds for well founded sets as shown in the following theorem 53 WELL FOUNDED ORDERINGS AND COMPLETE INDUCTION 499 Theorem 5310 The principle of complete induction holds for every wellfounded set As an illustration of well founded sets we de ne the lep icogrdphic ordering on pairs Given a partially ordered set X gt the lexicographic ordering ltlt on X X X induced by g is de ned a follows For all x y Lquot y E X x 3 ltlt 51 3 iff either L Lquot and 313 or xltx or L Lquot and ylty We leave it as an exercise to check that ltlt is indeed a partial order on X X X The following proposition will be useful 500 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Proposition 5311 If X gt is d wellfounded set then the lexicographic ordering ltlt on X X X is also well founded Example Ackerrndnn s function The following func tion A N X N gt N known as Ackermdnn s function is well known in recursive function theory for its extraor dinary rate of growth It is de ned recursively as follows AIy ifd Otheny1 else if y 0 then A5L 11 else A5L 1A5L y We wish to prove that A is a total function We proceed by complete induction over the lexicographic ordering on N X N l The base case is 1 0 y 0 In this case since A0 3 y l A0 0 is de ned and equal to l 53 WELL FOUNDED ORDERINGS AND COMPLETE INDUCTION 501 2 The induction hypothesis is that for any m n Am n is de ned for all m n ltlt mn With 77171 y m n 3 For the induction step we have three cases a If m 0 since A0 3 y 1 AO n is de ned and equal to n 1 b If m y 0 and n 0 since m 11 ltlt m0 and m 1 1 y m 0 by the induction hypothe sis Am 1 1 is de ned and so Am 0 is de ned since it is equal to Am 1 1 c If m y 0 and n y 0 since mn 1 ltlt mn and m n 1 y m n by the induction hypoth esis Am n 1 is de ned Since m 1y ltlt mz and m 1y y mz no matter What 3 and z are m 1Amn 1 ltlt mn and m 1 Am n 1 y m n and by the induc tion hypothesis Am 1 Am n 1 is de ned But this is precisely Am n and so Am n is de ned This concludes the induction step Hence 141 3 is de ned for all 51 y 2 0 11 502 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES 54 Unique Prime Factorization in Z and GCD S In the previous section we proved that every natural number n 2 2 can be factored as a product of primes numbers In this section we use the Euclidean Division Lemma to prove that such a factorization is unique For this we need to introduce greatest common divisors gcd s and prove some of their properties In this section it will be convenient to allow 0 to be a divisor So given any two integers d b E Z we will say that b divides d and that d is a multiple of b iff d bq for some q E Z Contrary to our previous de nition I 0 is allowed as a divisor However this changes very little because if 0 divides a then a 0g 0 that is the only integer divisible by 0 is 0 54 UNIQUE PRIME FACTORIZATION IN Z AND GOD S 503 Figure 58 Richard Dedekind 1831 1916 The notation b l a is usually used to denote that b divides a For example 3 l 21 since 21 2 7 5 l 20 since 20 5 4 but 3 does not divide 20 We begin by introducing a very important notion in alge bra that of an ideal due to Richard Dedekind and prove a fundamental property of the ideals of Z De nition 541 An ideal of Z is any nonenipty sub set 3 of Z satisfying the following two properties lDl If ab E 3 then b a E 3 IDZ If a E 3 then ak E 3 for every 16 E Z An ideal 3 is a principal ideal if there is some a E 3 called a generator such that 3 ak l k E Z The equality 3 ak l k E Z is also written as 3 aZ or as 3 a The ideal 3 0 0 is called the null ideal 504 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Note that if 7 is an ideal then 7 Z iff 1 E 7 Since by de nition an ideal J is nonempty there is some aE JandbyID1weget0a aE J Then for every a E 7 since 0 E J by HM we get a E 7 Theorem 542 Every ideal 7 of Z is a principal ideal ie J mZ for some unique m E N with mgt0 17740 Theorem 542 is often phrased Z is a principal ideal domain for short a PID Note that the natural number m such that J mZ is a divisor of every element in J 54 UNIQUE PRIME FACTORIZATION IN Z AND GCD S 505 Figure 59 Etienne B zout 1730 1783 Corollary 543 For any two integers a b E Z there is a unique natural number d E N and some integers uu E Z so that d divides both a and b and uaubd The above is called the Bezout identity Further more d0 t a0 audb0 Given any nonempty nite set of integers S ab an it is easy to verify that the set 3h1a1hnanlh1hnEZ is an ideal of Z and in fact the smallest under inclusion ideal containing S 506 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES This ideal is called the ideal generated by S and it is often denoted a1 an Corollary 543 can be restated by saying that for any two distinct integers a b E Z there is a unique natural number d E N such that the ideal a 9 generated by a and b is equal to the ideal dZ also denoted d that is a b dZ This result still holds when a b in this case we consider the ideal a With a slight but harrnless abuse of notation when a b we will also denote this ideal by a b The natural number d of corollary 543 divides both a and b Moreover every divisor of a and b divides d ua vb This motivates the de nition 54 UNIQUE PRIME FACTORIZATION INZ AND GOD S 507 De nition 544 Given any two integers a b E Z an integer d E Z is a greatest common divisor of a and b for short a god of a and b if d divides a and b and for any integer h E Z if h divides a and b then h divides d We say that a and b are relatively prime if 1 is a gcd of a and b Remarks 1 If a b 0 then any integer d E Z is a divisor of 0 In particular 0 divides 0 According to De nition 544 this implies gcd0 0 0 The ideal generated by 0 is the trivial ideal 0 so gcd00 0 is equal to the generator of the zero ideal If a y 0 or b y 0 then the ideal ab generated by a and b is not the zero ideal and there is a unique integer d gt 0 such that a b dZ 508 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES For any gcd d of a and b since d divides a and b we see that d must divide 01 As 01 also divides a and b the number 01 must also divide d Thus d d q and d dq for some qq E Z and so d dqq which implies qq 1 since d y 0 Therefore 01 id So according to the above de nition when a b y 0 gcd s are not unique However exactly one of d or d is positive and equal to the positive generator d of the ideal a b We will refer to this positive gcd as the gcd of a and b and write d gcda 9 Observe that gcda b gcdb a For example gcd208 4 gcd100050 gcd42823 6409 17 and gcd5 16 1 50 54 UNIQUE PRIME FACTORIZATION INZ AND GOD S 509 2 Another notation commonly found for gcda b is a b but this is confusing since a b also denotes the ideal generated by a and b 3 Observe that if d gcda b y 0 then d is indeed the largest positive common divisor of a and b since every divisor of a and b must divide d However we did not use this property as one of the conditions for being a gcd because such a condition does not generalize to other rings where a total order is not available Another minor reason is that if we had used in the de nition of a gcd the condition that gcda b should be the largest common divisor of a and b as every integer divides 0 gcd0 0 would be unde ned 4 If a 0 and b gt 0 then the ideal 0 9 generated by 0 and b is equal to the ideal b bZ which implies gcd0 b b and similarly if a gt 0 and b 0 then gcda 0 a 510 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Let p E N be a prime number Then note that for any other integer n ifp does not divide n then gcdp n 1 as the only divisors of p are 1 and p Proposition 545 Given any two integers a b E Z a natural number cl 6 N is the greatest common di visor ofa and b i d divides a and b and if there are some integers u v E Z so that ua vb cl Bezout Identity In particular a and b are relatively prime i there are some integers u v E Z so that ua vb 1 Bezout Identity The god of two natural numbers can be found using a method involving Euclidean division and so can the num bers u and v 54 UNIQUE PRIME FACTORIZATION INZ AND GOD S 511 This method is based on the following simple observation Proposition 546 If a b are any two positive inte gers with a 2 b then for every h E Z gcda b gcdb a hb In particular gcda b gcdb a b gcdb a b and if a bq r is the result of performing the Eu clidean division ofa by b with 0 g r lt a then gcda b gcdb r Using the fact that gcda 0 a we have the following algorithm for nding the god of two natural numbers a b with a b y 0 0 Euclidean Algorithm for Finding the god The input consists of two natural numbers m n with m n y 0 0 512 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES begin a c m b c n if a lt b then t b 1 a a c t swap a and b while I y 0 do 7 c a mod I divide a by b to obtain the remainder 7 a c b b c 7 endwhile gcdm n c a end In order to prove the correctness of the above algorithm we need to prove two facts 1 The algorithm always terminates 2 When the algorithm exits the while loop the current value of a is indeed gcdm The termination of the algorithm follows by induction on minm 54 UNIQUE PRIME FACTORIZATION INZ AND GOD S 513 The correctness of the algorithm is an immediate conse quence of Proposition 546 During any round through the while loop the invariant gcdab gcdmn is preserved and When we exit the While loop we have a gcda 0 gcdm n which proves that the current value of a When the algo rithm stops is indeed gcdm Let us run the above algorithm for m 42823 and n 6409 There are ve division steps 42823 6409 X 6 4369 6409 4369 X 1 2040 4369 2040 X 2 289 2040 289 X 7 17 289 17 gtlt170 so we nd that gcd42823 6409 17 514 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES You should also use your computation to nd numbers 51 3 so that 428231 64093 17 Check that 1 22 and y 147 work The complexity of the Euclidean algorithm to compute the gcd of two natural numbers is quite interesting and has a long history It turns out that Gabriel Lame published a paper in 1844 in which he proved that if m gt n gt 0 then the number of divisions needed by the algorithm is bounded by 56 1 Where 6 is the number of digits in n For this Lame realized that the maximum number of steps is achieved by taking m an n to be two consecutive Fibonacci numbers see Section 57 54 UNIQUE PRIME FACTORIZATION INZ AND GOD S 515 Dupre in a paper published in 1845 improved the upper bound to 47856 1 also making use of the Fibonacci numbers Using a variant of Euclidean division allowing negative rernainders in a paper published in 1841 Binet gave an algorithm with an even better bound 6 1 The Euclidean algorithm can be easily adapted to also cornpute two integers 1 and 3 such that ma my gcdm Such an algorithm is called the Extended Euclidean Al gom thm What can be easily shown is the following proposition 516 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Figure 510 Euclid of Alexandria about 325 BC 7 about 265 BC Proposition 547 The number of divisions mode by the Euclidean Algorithm for gcd applied to two positive integers m n with in gt n is at most log2 mlog2 n We now return to Proposition 545 as it implies a very crucial property of divisibility in any PlD Proposition 548 Eaclid s proposition Let dbc E E be any integers If a dioides be and d is relatively prime to b then a dioides c In particular if p is a prime number and if p divides db where db E Z are nonzero then either p divides d or p divides b 54 UNIQUE PRIME FACTORIZATION INZ AND GOD S 517 Proposition 549 Let a 1 bm E Z be any inte gers If a and b are relatively prime for all i with 1 g i g m then a and 1 bm are relatively prime One of the main applications of the Euclidean Algorithm is to nd the inverse of a number in rnodular arithmetic an essential step in the RSA algorithm the rst and still widely used algorithm for public key cryptography Given any natural number p Z 1 we can de ne a relation on Z called congruence as follows n E m mod p iffp l n rn ie iffnmpl forsornek E Z We say that m is a residue ofn modulo p The notation for congruence was introduced by Carl Friedrich Gauss 1777 1855 one of the greatest rnathe rnaticians of all time 518 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LAT T ICES Figure 511 Carl Friedrich Gauss 1777 1855 Gauss contributed signi cantly to the theory of congru ences and used his results to prove deep and fundamental results in number theory If n 2 1 and n and p are relatively prime an inverse of n modulo p is a number 8 Z 1 such that 718 E 1 mod p Using Proposition 548 Euclid s proposition it is easy to see that that if 51 and 52 are both inverse of n modulo p then 51 E 52 mod p Since nding an inverse of n modulo p means nding some numbers 17 y so that 711 2 1 py that is 7117 pg 2 1 we can nd 1 and y using the Extended Euclidean Algorithm 54 UNIQUE PRIME FACTORIZATION INZ AND GOD S 519 We can now prove the uniqueness of prime factorizations in N The rst rigorous proof of this theorem was given by Gauss Theorem 5410 Unique Prime Factorization in N For every natural number a Z 2 there exists a unique set 191 h1gt pm hmgt where the p s are distinct prime numbers and the h s are not necessarily dis tinct integers with m 2 1 h 2 1 so that k1 k pmm Theorem 5410 is a basic but very important result of number theory and it has many applications It also reveals the importance of the primes as the build ing blocks of all numbers 520 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Remark Theorem 5410 also applies to any nonzero integer a E Z 1 1 by adding a suitable sign in front of the prime factorization That is we have a unique prime factorization of the form k a Theorern 5410 shows that Z is a unique factorization domain for short a UFD Such rings play an important role because every nonzero element which is not a unit ie which is not invertible has a unique factorization up to some unit factor into so called irreducible elements which generalize the primes Readers who would like to learn more about number the ory are strongly advised to read Silverrnan s delightful and very friendly introductory text 13 55 EQUIVALENCE RELATIONS AND PARTITIONS 521 55 Equivalence Relations and Partitions Equivalence relations basically generalize the identity re lation Technically the de nition of an equivalence relation is obtained from the de nition of a partial order De nition 511 by changing the third condition antisyrnrnetry to symmetry De nition 551 A binary relation R on a set X is an equivalence relation iff it is reflexive transitive and symmetric that is 1 Re exiyity aRa for all a E X 2 Transitiyity If aRb and bRc then aRc for all a b c E X 3 symmetry If aRb then bRa for all a b E X 522 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Here are some examples of equivalence relations 1 The identity relation id X on a set X is an equivalence relation 2 The relation X X X is an equivalence relation 3 Let S be the set of students in 318160 De ne two students to be equivalent iff they were born the same year It is trivial to check that this relation is indeed an equivalence relation 4 Given any natural number p Z 1 recall that we can de ne a relation on Z as follows 71 E m mod p iffp l n m 226 n mpl for some 16 E Z It is an easy exercise to check that this is indeed an equivalence relation called congruence modulo p 55 EQUIVALENCE RELATIONS AND PARTITIONS 523 5 Equivalence of propositions is the relation de ned so that P E Q i P gt Q and Q gt P are both prov able say classically It is easy to check that logical equivalence is an equivalence relation Ch Suppose f X gt Y is a function Then we de ne the relation 2f on X by 56 Er 2 iff x y It is immediately veri ed that 2f is an equivalence relation Actually we are going to show that every equivalence relation arises in this way in terms of sur jective functions The crucial property of equivalence relations is that they partition their domain X into pairwise disjoint nonernpty blocks lntuitively they carve out X into a bunch of puz zle pieces 524 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES De nition 552 Given an equivalence relation R on a set X for any a E X the set Cali2 y E X l wRy is the equivalence class of x Each equivalence class 51 R is also denoted ER and the subscript R is often ornitted when no confusion arises The set of equivalence classes of R is denoted by X R The set X R is called the quotient of X by R or quotient of X modulo R The function 7T2 X gt XR given by 7Ta MR 1 E X is called the canonical projection or projection of X onto X R Since every equivalence relation is re exive ie 1in for every 1 E X observe that a E R for any a E R that is every equivalence class is nonempty It is also clear that the projection 7r X gt XR is surjective 55 EQUIVALENCE RELATIONS AND PARTITIONS 525 The main properties of equivalence classes are given by Proposition 553 Let R be an equivalence relation on a set X For any two elements a y E X we have x Wt w Moreover the equivalences classes of R satisfy the fol lowing properties 17 for all a E X HMMMWMWMW A useful way of interpreting Proposition 553 is to say that the equivalence classes of an equivalence relation form a partition as de ned next 526 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES De nition 554 Given a set X a partition of X is any family H X E 1 of subsets of X such that 1 X 7A 0 for all 2 E I each X is nonempty 2 If i y j then X H Xj 0 the X are pairwise disjoint 3 X U16 X the family is exhaustive Each set X is called a block of the partition In the example Where equivalence is determined by the same year of birth each equivalence class consists of those students having the same year of birth Let us now go back to the example of congruence modulo p with p gt 0 and gure out What are the blocks of the corresponding partition Recall that m E n modp iffm npkforsomekEZ 55 EQUIVALENCE RELATIONS AND PARTITIONS 527 By the division Theorem Theorem 536 we know that there exist some unique q 7 with m pq 7 and 0 g 7 g p 1 Therefore for every m E Z m2rltrnodp with Ogrgp l which shows that there are p equivalence classes Ola 1 39 39 39 7 p 1l7 where the equivalence class 7 with 0 g 7 g p 1 consists of all integers of the form pq 7 where q E Z 26 those integers whose residue modulo p is 7 Proposition 553 de nes a map from the set of equiva lence relations on X to the set of partitions on X 528 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Given any set X let EquivX denote the set of equiv alence relations on X and let PartX denote the set of partitions on X Then Proposition 553 de nes the function H EquivX gt PartX given by HR XR MR l 1 E X Where R is any equivalence relation on X We also write Hp instead of HR There is also a function R PartX gt EquivX that assigns an equivalence relation to a partition a shown by the next proposition 55 EQUIVALENCE RELATIONS AND PARTITIONS 529 Proposition 555 For any partition H XihE on a set X the relation ROD de ned by a RHy i 3i 6 Ixy E X is an equivalence relation whose equivalence classes are exactly the blocks Xi Putting Propositions 553 and 555 together we obtain the useful fact there is a bijection between EquiVX and PartX Therefore in principle it is a matter of taste whether we prefer to work with equivalence relations or partitions In computer science it is often preferable to work with partitions but not always 530 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Proposition 556 Given any set X the functions H EquivX gt PartX and R PartX gt EquivX are mutual inuerses that is Rollid and HoRid Consequently there is a bijection between the set EquivX of equivalence relations on X and the set PartX of partitions on X Now if f X gt Y is a surjective function we have the equivalence relation 2f de ned by 56 Er 2 iff x y It is clear that the equivalence class of any a E X is the inverse image f 1fa of x 6 Y 55 EQUIVALENCE RELATIONS AND PARTITIONS 531 Therefore there is a bijection between X 2f and Y Thus we can identify f and the projection 7r from X onto X 2f If f is not surjectiye note that f is surjectiye onto fX and so we see that f can be written as the composition f 2 o 7r where 7r X gt fX is the canonical projection and i fX gt Y is the inclusion function rnapping fX into Y ie y for every 3 E fX Given a set X the inclusion ordering on X X X de nes an ordering on binary relations on X namely R33 iff Vxy Xnygtng When R g S we say that R re nes S 532 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES If R and S are equivalence relations and R g S we observe that every equivalence class of R is contained in some equivalence class of S Actually in view of Proposition 553 we see that ev ery equivalence class of S ls the union of equivalence classes of R We also note that id X is the least equivalence relation on X and X X X is the largest equivalence relation on X This suggests the following question Is EquivX a lat tice under re nement The answer is yes It is easy to see that the meet of two equivalence relations is R H S their intersection But beware their join is not R U S because in general R U S is not transitive However there is a least equivalence relation containing R and S and this is the join of R and S This leads us to look at various closure properties of relations 5 6 TRAN SI TI VE CL OS URE REFLEXIVE AND TRAN SI TI VE CL OS URE 533 56 Transitive Closure Re exive and Transitive Clo sure Smallest Equivalence Relation Let R be any relation on a set X Note that R is re exive iff id X Q R Consequently the smallest re exive relation containing R is idX U B This relation is called the reflexive closure of R Note that R is transitive iff R o R g B This suggests a way of making the smallest transitive relation containing R if R is not already transitive De ne R by induction as follows R0 idX R 1 R o R 534 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES De nition 561 Given any relation R on a set X the transitive closure of R is the relation R given by R U R n21 The reflexive and transitive closure of R is the relation Rquot given by R UR 1dXoR n20 Proposition 562 Given any relation R on a set X the relation R is the smallest transitive relation containing R and Rquot is the smallest reflexive and transtive relation containing R If R is re exive then it is easy to see that R Q R2 and so Rk Q Rk1 for all h 2 0 5 6 TRAN SI TI VE CL OS URE REFLEXIVE AND TRAN SI TI VE CL OS URE 535 From this we can show that if X is a nite set then there is a smallest It so that Bk Bk In this case Bk is the re exive and transitive closure of R If X has n elements it can be shown that It 3 n 1 Note that a relation R is symmetric iff R 1 B As a consequence R U R 1 is the smallest symmetric relation containing B This relation is called the symmetric closure of R Finally given a relation B What is the smallest equiva lence relation containing R The answer is given by Proposition 563 For any relation R on a set X the relation R o 19 1quot is the smalest equivalence relation containing R 536 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES 57 Fibonacci and Lucas Numbers Mersenne Primes We have encountered the Fibonacci numbers after Leonardo Fibonacci also known as Leonardo of Pisa 1170 1250 in Section 23 These numbers show up unexpectedly in many places including algorithm design and analysis for example Fi bonacci heaps The Lucas numbers after Edouard Lucas 1842 1891 are closely related to the Fibonacci numbers Both arise as special instances of the recurrence relation n2 n1 an n 2 0 Where uo and u1 are some given initial values The Fibonacci sequence Fm arises for uo 0 and u1 1 and the Lucas sequence Ln for uo 2 and U1 1 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 537 Figure 512 Leonardo Pisano Fibonacci7 1170 1250 left and F Edouard Lucas7 1842 1891 right These two sequences turn out to be intimately related and they satisfy many remarquable identities The Lucas numbers play a role in testing for primality of certain kinds of numbers of the form 2p 17 where p is a prime7 known as Mersenne numbers In turns out that the largest known primes so far are Mersenne numbers and large primes play an important role in cryptography It is possible to derive a Closed formulae for both Fn and Ln using some simple linear algebra 538 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Observe that the recurrence relation n2 n1 11 yields the recurrence n1 7 1 1 un in 1 0 it for all n 2 1 and so 521 l 3113 Now the matrix 1 1 A 1 0 has characteristic polynomial A2 1 Which has two real roots 1 i V5 2 for all n 2 0 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 539 Observe that the larger root is the famous golden mtz o Often denoted 1 5 s0 Tf 1618083988749 and that Since A has two distinct eigenvalues it can be diagonal ized and it is easy to ShOW that A7117 ltp ltp1 ltp 0 1ltp1 10 511 0 ltp1 1gp It follows that f f1 iuigi n and so an ap1210 W ltqu anew5 for all n 2 0 540 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES For the Fibonacci sequence no 0 and U1 1 so Fn Luv s l 1 WWW 1 5 a formula established by Jacques Binet 1786 1856 in 1843 and already known to Euler Daniel Bernoulli and de Moivre Since W 7 V5 1 1 7 lt7 V5 2 2 we see that Fn is the closest integer to 07 and that wim 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 541 It is also easy to see that Fn1 01771 0 1n7 which shows that the ratio EH1 Fn approaches ltp as 71 goes to in nity For the Lucas sequence no 2 and U1 1 so 5 1 80 1qurU1 2 lt 2 1 V5 1 1 5 2 ag U12 andweget n n n 1 5 n Since 5 1 ltp1 2 lt 062 it follows that Ln is the Closest integer to w 542 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES When no 2L1 since ltp ltp 1 1 we get WnH ltp 1n17 VS un that is un qun1 Therefore from now on we assume that no y m It is easy to prove by induction that Proposition 571 The following identities hold F FEF5 FnFn1 F0F1quot39Fn Fn2 1 F2F4F2n anH l F1F3 F2n1 F2n2 ka new FM 2 k0 for all n 2 0 with the third sum interpreted as F0 for n 0 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 543 Following Knuth see 8 the third and fourth identities yield the identity Fnrnod22 Fn 2FnFn1 17 for all n 2 2 The above can be used to prove the Zeckendorf s repre sentation of the natural numbers see Knuth 8 Chapter 6 Proposition 572 Zeckendorf s representation Eu ery every natural number n E N with n gt 0 has a unique representation of the form nFk1Fk2 ka withinZk 12f0ri1r 1andkr22 For example 302181 nn 544 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES and 1000000 832040 121393 46368 144 55 F30 F26 F24 F12 F10 The fact that Fn1 WFn 4p 1 and the Zeckendorf s representation lead to an amusing method for converting between kilometers to miles see 8 Section 66 lndeed ltp is nearly the number of kilometers in a mile the exact number is 1609344 and ltp 1618033 It follows that a distance of EH1 kilometers is very nearly a distance of E miles Thus to convert a distance d expressed in kilometers into a distance expressed in miles rst nd the Zeck endorf s representation of d and then shift each Fk in this representation to Fkrl 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 545 For example 302181F8F6F2 so the corresponding distance in miles is F7F6F1 l35l19 The exact distance in miles is 1864 miles We can prove two simple formulas for obtaining the Lucas numbers from the Fibonacci numbers and Vice versa Proposition 573 The following identities hold Ln Fn 1Fn1 5Fn Ln 1Ln17 for all n 2 1 546 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES The Fibonaci sequence begins With 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 and the Lucas sequence begins With 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 Notice that L 71 1 F7111 is equivalent to 2F1 F Ln It can also be shown that F271 Fan for all n 2 1 The proof proceeds by induction but one nds that it is necessary to prove an auxiliary fact 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 547 Proposition 574 For any xed h 2 1 and all n 2 0 we have Fnk Fan1 Fk an The reader can also prove that LnLn2 L7211 L2 Li 2 1n L2n1 LnLn1 Li 5113 4 1 Usng the matrix representation derived earlier it can be shown that Proposition 575 The sequence given by the recur renee n2 n1 an satis es the following equation un1un1 nib 1 1u3 noul 548 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LAT T I CES Figure 513 Jean Dominique Cassini7 1748 1845 left and Eugene Charles Catalan7 1814 1984 right For the Fibonacci sequence7 where no O and ul 17 we get the Cassim identity after Jean Dominique Cassini7 also known as Giovanni Domenico Cassini7 1625 17127 11 le 1334 1 71 2 1 The above identity is a special case of Catalan s identity7 FWan F5 1 T1F3 n 2 7quot due to Eugene Catalan 1814 1894 For the Lucas numbers7 where no 2 and ul 1 we get Ln1Ln1 Lg 5 1 1 n 2 1 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 549 In general we have ukun1 uk lun u1unk UOUan la for all k 2 1 and all n 2 0 For the Fibonacci sequence where no 0 and U1 1 we just reproved the identity Fnk Fan1 Fk an For the Lucas sequence where no 2 and U1 1 we get LkLn1 Lk 1Ln Lnk 2Lnk 1 Lnk Lnk 1 Lnk 1 Lnk1 Lnk 1 5Fnk7 that is LkLn1 Lk an Lnk1 Lnk 1 5Fnk7 for all k 2 1 and all n 2 0 550 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES The identity Fnk Fan1 Fk iFn plays a key role in the proof of various divisibility prop erties of the Fibonacci numbers Here are two such prop erties Proposition 576 The following properties hold 1 Fn divides Fm for all m 7i 2 1 2 gcdFm Fn Fgcdmm for all m 7i 2 1 An interesting consequence of this divisibility property is that if Fn is a prime and n gt 4 then 7i must be a prime However there are prime numbers 7i 2 5 such that Fn is not prirne for example 7i 19 as F19 4181 37X 113 is not prirne 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 551 The gcd identity can also be used to prove that for all m n With 2 lt n lt m if Fn divides Fm then 71 divides m which provides a converse of our earlier divisibility property The formulae 2Lmn 1an are also easily established using the explicit formulae for Fn and Ln in terms of ltp and ltp1 The Fibonacci sequence and the Lucas sequence contain primes but it is unknown Whether they contain in nitely many primes Here are some facts about Fibonacci and Lucas primes taken from The Little Book of Bigger Primes by Paulo Ribenboim 12 552 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES As we proved earlier if E is a prime and n 74 4 then 71 must be a prime but the converse is false For example 173174 175177 F11 F13 17171723 are prime but F19 4181 37 X 113 is not a prime One of the largest prime Fibonacci numbers if 1781839 It has 17103 digits Concerning the Lucas numbers it can also be shown that if L is an odd prime and n is not a power of 2 then 71 is a prime Again the converse is false For example L07 L27L47L57L77L87L117L137L167 1177111971131 are prime but L23 64079 139 X 461 is not a prime Similarly L32 4870847 1087 X 4481 is not prime One of the largest Lucas primes is L51169 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 553 Generally divisibility properties of the Lucas numbers are not easy to prove because there is no simple formula for Lmn in terms of other Lk s Nevertheless we can prove that if n k 2 1 and k is odd then Ln divides Lkn This is not necessarily true if k is even For example L4 7 and L8 47 are prime It should also be noted that not every sequence an given by the recurrence n2 n1 an and With gcdu0 2L1 1 contains a prime number 554 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES According to Ribenboirn 12 Graham found an example in 1964 but it turned out to be incorrect Later Knuth gave correct sequences see Concrete Mathematics 8 Chapter 6 one of which beginning with no 62638280004239857 ul 49463435743205655 We just studied some properties of the sequences arising from the recurrence relation n2 n1 un Lucas investigated the properties of the more general re currence relation n2 Pun1 Quna where P Q E Z are any integers with P2 4Q y 0 in two serninal papers published in 1878 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 555 We can prove some of the basic results about these Lucas sequences quite easily using the matrix method that we used before The recurrence relation n2 Pun1 Qun yields the recurrence n1 P Q an an 1 0 71 1 for all n 2 1 and so aim P Q U1 U71 1 0 no foralanO 7 P Q AC 0 has characteristic polynomial P Q 2 P Q Which has discriminant D P2 4Q The matrix 556 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES If we assume that P2 4Q 7A 0 the polynomial A2 P Q has two distinct roots PE P a 2 2 Obviously oz P Oz Q oz The matrix A can be diagonalized as M om f a 2 lt21 2 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 557 Thus we get WM 7 1 06 5 5U0U106n un fox 1 1 onto mm and so 1 TL TL an Q uo u oz 0mg u Actually the above formula holds for n 0 only if oz y 0 and y 0 that is iff Q y 0 If Q 0 then either oz 0 or 0 in which case the formula still holds if we assume that 00 1 For no 0 and U1 1 we get a generalization of the Fibonacci nurnbers an n and for no 2 and U1 P we get a generalization of the Lucas nurnbers Un Vn oz 558 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES The orginal Fibonacci and Lucas numbers correspond to P 1 and Q 1 Since the vectors and are linearly independent every sequence arising from the recurrence relation n2 Pun1 Qun is a unique linear combination of the sequences UT and Vn lt possible to prove the following generalization of the Cassini identity Proposition 577 The sequence de ned by the T6 currence n2 Pun1 Qun with P2 4Q 7A 0 satis es the identity un1un1 ui Q 1 Qu3 Puoul 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 559 For the U sequerice no 0 and U1 1 so we get Un1Un1 U5 Q 1 For the V sequerioe uo 2 and U1 P so we get Vn1Vn1 V3 orb 11 Where D P2 4Q Since 052 Q Ma and 2 Q oz we easily get formulae expressing Un in terms of the V s arid Vice verse Proposition 578 We have the following identities relating the Un and the V Vn Un1 QUn l DUn Vn1 QVn la for all n 2 1 560 CHAPTER 5 PARTIAL ORDERS EQ UIVALENCE RELATIONS LAT T I CES Figure 514 Marin Mersenne7 1588 1648 The following identities are also easy to derive U271 V271 Umn Vmn UnVn V3 2Qn UmUn1 QUnUm l VmVn Qan n Lucas numbers play a crucial role in testing the primal ity of certain numbers of the form7 N 2p 17 called Mersenne numbers A Mersenne number which is prime is called a M ersenne prime 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 561 First if N 2P 1 is prime then 10 itself must be a prime Forp 2357we see that 3 22 1 7 23 1 31 25 1 127 27 1 are indeed prime However the condition that the exponent p be prime is not suf cient for N 219 1 to be prime since for p 11 mhmeT1 12M723x89 Mersenne 1588 1648 stated in 1644 that N 2P 1 is prime when p23571317193167127257 Mersenne was wrong about 10 67 and p 257 and he missed 10 6189107 562 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Euler showed that 231 1 was indeed prime in 1772 and at that time it was known that 21 1 is indeed prime for p 2 3 5 7 13 17 19 31 Then came Lucas In 1876 Lucas proved that 2127 1 was prime Lucas came up With a method for testing Whether a llersenne number is prime later rigorously proved correct by Lehmer and known as the LucasLemme test This test does not require the actual computation of N 2p 1 but it requires an ef cient method for squaring large numbers less that N and a way of computing the residue modulo 2P 1 just using p 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 563 Figure 515 Derrick Henry Lehmer 1905 1991 A version of the Lucas Lehmer test uses the Lucas se quence given by the recurrence Vn2 2Vn1 2V starting from V0 V1 2 This corresponds to P 2 and Q 2 In this case D 12 and it is easy to see that oz 1 1 y 80 v 1 1 x This sequence starts with 2 28 20 56 Here is the rst version of the Lucas Lehmer test for pri rnality of a Mersenne number 564 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Theorem 579 LucasLehmer test Version I The number N 2P 1 is prime for any Odd prime p Z N dz m des V2194 A proof of the Lucas Lehrner test can be found in The Little Book of Bigger Primes 12 Shorter proofs ex ist and are available on the Web but they require some knowledge of algebraic number theory The most accessible proof that we are aware of it only uses the quadratic reciprocity law is given in Volume 2 of Knuth 9 see Section 454 Note that the test does not apply to p 2 because 3 22 1 does not divide V2 8 but that s not a problem 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 565 The numbers V2194 get large very quickly but if we Observe that V271 V112 22n7 we may want to consider the sequence Sn given by Sn1 S2 2 TL starting with So 4 This sequence starts with 4714194376431416317954 Then it turns out that W Sic 122M for all k 2 1 It is also easy to see that Sk 2 V3216 2 V32 566 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Now N 2P 1 is prime iff N divides Vgpq iff N 2P 1 p72 divides Sp222 iff N divides Sp2 since if N divides 1072 22 then N is not prime Thus we obtain an improved version of the Lucas Lehmer test for primality of a Mersenne number Theorem 5710 LucasLehmer test Version 2 The number N 2P 1 is prime for any odd prime p i Sp2 E 0 mod N The test does not apply to p 2 because 3 22 1 does not divide So 4 but that s not a problem The above test can be performed by computing a se quence of residues mod N using the recurrence SW1 Si 2 starting from 4 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 567 As of January 2009 only 46 Mersenne primes are known The largest one was found in August 2008 by mathemati cians at UCLA This is M46 243112609 1 and it has 12 978 189 digits It is an open problem whether there are in nitely many Mersenne primes Going back to the second version of the Lucas Lehmer test since we are computing the sequence of Sk s modulo N the squares being computed never exceed N 2 221 There is also a clever way of computing 71 mod 21 1 without actually performing diyisions if we express n in binary This is because 71 271 mod 210 TL21 mod 21 1 568 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES But now if n is expressed in binary 71 mod 2 consists of the p rightmost least signi cant bits of n and TL21 consists of the bits remaining as the head of the string obtained by deleting the rightmost 0 bits of n Thus we can compute the remainder modulo 2P 1 by repeating this process until at most 0 bits remain Observe that if n is a multiple of 2P 1 the algorithm will produce 21 1 in binary as opposed to 0 but this exception can be handled easily For example 916 mod 25 1 11100101002 mod 25 1 101002 111002 mod 25 1 1100002 mod 25 1 100002 12 mod 25 1 100012 mod 25 1 100012 17 57 FIBONACCI AND LUCAS NUMBERS MERSENNE PRIMES 569 The Lucas Lehmer test applied to N 127 27 1 yields the following steps if we denote 3 mod 21 1 by 7 To 4 71 42 2 14 mod 127 76 71 14 m 142 2 194 mod 127 16 m 67 no 672 2 4487 mod 127 16 73 42 74 422 2 1762 mod 127 76 74 111 75 1112 2 12319 mod 127 16 r5 0 As 75 0 the Lucas Lehmer test con rms that N 127 27 1 is indeed prime 570 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES 58 Distributive Lattices Boolean Algebras Heyting Algebras If we go back to one of our favorite examples of a lattice namely the power set 2X of some set X we observe that it is more than a lattice For example if we look at Figure 56 we can check that the two identities D1 and D2 stated in the next de nition hold De nition 581 We say that a lattice X is a dis tributive lattice if D1 and D2 hold D1 achabvac D2 aVbcavbaVc Remark Not every lattice is distributive but many lat tices of interest are distributive It is a bit surprising that in a lattice D1 and D2 are actually equivalent 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 571 The reader should prove that every totally ordered poset is a distributive lattice The lattice N under the divisibility ordering also turns out to be a distributive lattice Another useful fact about distributivity is that in any lattice ach Z aAbVaC This is because in any lattice a b V c 2 a b and abVC ZaAc Therefore in order to establish distributivity in a lattice it suffices to show that ach abVaC 572 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Another important property of distributive lattices is the following Proposition 582 In a distributive lattice X if zL zy anszxsz thenxy for all 51 y z E X The power set lattice has yet some additional properties having to do with complementatiori First the power lattice 2X has a least element 0 0 and a greatest element 1 X If a lattice X has a least element 0 and a greatest element 1 the following properties are clear For all a E X we have aAOO aV0a a1a aV11 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 573 Figure 516 Augustus de Morgan7 1806 1871 More importantly7 for any suloset7 A Q X 7 we have the complement7 A7 of A in X 7 which satis es the identities AUZX7 AoZ0 Moreover7 we know that the de Morgan identities hold The generalization of these properties leads to What is called a complemented lattice De nition 583 Let X be a lattice and assume that X has a least element7 O7 and a greatest element7 1 we say that X is a bounded lattice For any a 6 X7 a complement of a is any element7 b 6 X7 so that aVbl and ab0 If every element of X has a complement7 we say that X is a complemented lattice 574 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Remarks 1 When 0 1 the lattice X collapses to the degenerate lattice consisting of a single element As this lattice is of little interest from now on we will always assume that 0 y 1 2 In a complemented lattice complements are generally not unique However as the next proposition shows this is the case for distributive lattices Proposition 584 Let X be a lattice with least ele ment 0 and greatest element 1 If X is distributive then complements are unique if they exist Moreover ifb is the complement of a then a is the complement of b In View of Proposition 584 if X is a complemented dis tributive lattice we denote the complement of any ele ment a E X by a 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 575 We have the identities gt lt QII 9 9 H O a a We also have the following proposition about the de Mor gan laws Proposition 585 Let X be a lattice with least ele ment 0 and greatest element 1 If X is distributive and complemented then the de Morgan laws hold aVb 5A5 ab avE All this leads to the de nition of a boolean lattice De nition 586 A Boolean lattice is a lattice With a least element 0 a greatest element 1 and which is dis tributive and complemented 576 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Of course every power set is a boolean lattice but there are boolean lattices that are not power sets Putting together what we have done we see that a boolean lattice is a set X with two special elements 0 1 and three operations A V and a I gt a satisfying the axioms stated in Proposition 587 IfX is a b00lean lattice then the following equations hold for all abeEX L1 L2 L3 L4 LHltD2 aVbbvm aVMVcaVVc aAwAcaAA aVaa avaaa aA VemAbMMaA aV AemeWWaV aVOm aV1 avaiL 5a aAbbAa aAaa aAMVaa aAOO aA1a aAaO aAbavE 58 DISTRIBUTIVE LATTIOES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 577 Conversely if X is a set together with two special elements 0 1 and three operations A V and a I gt a satisfying the axioms above then it is a boolean lattice under the ordering given by a g b i a V b b In view of Proposition 587 we make the de nition De nition 588 A set X together with two special elements 0 1 and three operations A V and a I gt a sat isfying the axioms of Proposition 587 is called a Boolean algebra Proposition 587 shows that the notions of a Boolean lattice and of a Boolean algebra are equivalent The rst one is order theoretic and the second one is algebraic Remarks 1 As the name indicates Boolean algebras were invented by G Boole 1854 One of the rst comprehensive accounts is due to E Schr der 1890 1895 578 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LAT T I CES Figure 517 George Boole7 1815 1864 left and Ernst Schroder 1841 1902 right 2 The axioms for Boolean algebras given in Proposition 587 are not independent There is a set of inde pendent axiorns known as the Huntington axioms 1933 Let p be any integer with p 2 2 Under the division ordering7 it turns out that the set7 Divp7 of divisors of p is a distributive lattice In general not every integer7 k E Divp7 has a comple ment but when it does7 k pk It can be shown that Divp is a Boolean algebra iff p is not divisible by any square integer an integer of the form m27 with m gt 1 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 579 Classical logic is also a rich source of Boolean algebras Indeed it is easy to show that logical equivalence is an equivalence relation and as Homework problems you have shown with great pain that all the axioms of Propo sition 587 are provable equivalences where V is disjunc tion is conjunction F P 26 negation 0 l and 1 T Furthermore again as Homework problems you have shown that logical equivalence is compatible with V A in the following sense If P1 E Q1 and P2 E Q2 then PiVP2 E QiVQ2 PiP2 QIAQZ P1 E Q1 Consequently for any set T of propositions we can de ne the relation ET by PETQ iff Tl PEQ 26 iff P E Q is provable from T 580 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Clearly ET is an equivalence relation on propositions and so we can de ne the operations V and on the set of equivalence classes BT of propositions as follows l l l l lPVQl lPAQl PHD PV P We also let 0 L and 1 Then we get the Boolean algebra BT called the Lindenbaum algebra of T It also turns out that Boolean algebras are just What s needed to give truth value semantics to classical logic 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 581 Let B be any Boolean algebra A truth assignment is any function u from the set PS P1P2 of propositional symbols to B Then we can evaluate recursively the truth value PBM in B of any proposition P with respect to the truth assignment 1 as follows POEM WP LB 1 0 TBU 1 P V QBU FEW V FEW P QBU PBU PBU plBlUl Plle In the equations above on the right hand side V and are the lattice operations of the Boolean algebra B 582 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES We say that a proposition P is valid in the Boolean algebra B 07 Bvalz d if PBM 1 for all truth assign rnents 1 We say that P is classlally valid if P is B yalid in all Boolean algebras B It can be shown that every provable proposition is valid This property is called soundness Conversely if P is valid then it is provable This second property is called completeness Actually cornpleteness holds in a much stronger sense If a proposition is valid in the two elernent Boolean algebra 0 1 then it is provable 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 583 Figure 518 Arend Heyting7 1898 1980 One might wonder if there are certain kinds of algebras similar to Boolean algebras well suited for intuitionistic logic The answer is yes Such algebras are called H eytmg algebras In our study of intuitionistic logic7 we learned that nega tion is not a primary connective but instead it is de ned in terms of irnplication by P P gt J This suggests adding to the two lattice operations V and a new operation7 gt7 that will behave like gt The trick is7 what kind of axioms should we require on gt to capture the properties of intuitionistic logic 584 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Now if X is a lattice With 0 and 1 given any two ele ments a b E X experience shows that a gt b should be the largest element 0 such that c a g b This leads to De nition 589 A lattice X With 0 and 1 is a Heyt tng lattice iff it has a third binary operation gt such that cAagb iff c a gtb for all a b c E X We de ne the negation or pseudo complement ofa as 5 a gt 0 At rst glance it is not clear that a Heyting lattice is distributive but in fact it is The following proposition stated Without proof gives an algebraic characterization of Heyting lattices Which is useful to prove various properties of Heyting lattices 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 585 Proposition 5810 Let X be a lattice with 0 and 1 and with a binary operation gt Then X is a Heyting lattice i the following equations hold for all a b c E X a gta1 aa gtb ab ba gtb b a gtbc a gtba gtc A lattice with 0 and 1 and with a binary operation gt satisfying the equations of Proposition 5810 is called a Heyting algebra So we see that Proposition 5810 shows that the notions of Heyting lattice and Heyting algebra are equivalent this is analogous to Boolean lattices and Boolean algebras 586 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES The reader will notice that these axioms are propositions that were shown to be provable intuitionistically in Horne work Problems The following theorem shows that every Heyting algebra is distributive as we Clairned earlier This theorem also shows how Close to a Boolean algebra a Heyting algebra is Theorem 5811 a Every Hegtmg algebra is dis trlbutlve b A Hegtmg algebra X is a b00learL algebra l 5af0r allaEX Remarks 1 Heyting algebras were invented by A Heyting in 1930 Heyting algebras are sometimes known as Brouwe rian lattices 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 587 2 Every Boolean algebra is automatically a Heyting al gebra Set a gt b 5V b 3 It can be shown that every nite distributive lattice is a Heyting algebra We conclude this brief exposition of Heyting algebras by explaining how they provide a truth semantics for in tuitionistic logic analogous to the thuth semantics that Boolean algebras provide for classical logic As in the classical case it is easy to show that intuitionis tic logical equivalence is an equivalence relation and you have shown with great pain that all the axioms of Heyt ing algebras are intuitionistically provable equivalences where V is disjunction is conjunction and gt is gt 588 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Furthermore you have also shown that intuitionistio log ical equivalence is compatible with V A gt in the follow ing sense If P1 E Q1 and P2 E Q2 then P1 V P2 E Q1 V Q2 P1 P2 E Q1 Q2 P1 gt P2 Q1 gt Q2 Consequently for any set T of propositions we can de ne the relation ET by PETQ if Tl PEQ 26 iff P E Q is provable intuitionistically from T 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 589 Clearly ET is an equivalence relation on propositions and we can de ne the operations V and gt on the set of equivalence classes HT of propositions as follows PlVlQllPVQl PllQllPQl Pl gt Q P Ql We also let 0 l and 1 Then we get the Heyting algebra HT called the Ltndenbaam algebra of T as in the Classical case Now let H be any Heyting algebra By analogy With the case of Boolean algebras a truth assignment is any func tion a from the set PS P1 P2 of propositional symbols to H 590 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Then we can evaluate recursively the truth value PHM in H of any proposition P With respect to the truth assignment 1 as follows Pam vltPgt LE 1 0 TIT 1 1 P V PHW V FEW P PHW PHU P gt QHlvl PHlvl gt PHlvl PHlUl PHlUl 0 In the equations above on the right hand side V and gt are the Operations of the Heyting algebra H 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 591 We say that a proposition P is valid in the Heytlng algebra H 07 H walla if PHM 1 for all truth assign rnents 1 We say that P is HAvalld 07 lntaltlonlstlcally valid if P is H Valid in all Heyting algebras H As in the classical case it can be shown that every intu itionistically provable proposition is HA Valid This prop erty is called soundness Conversely if P is HA Valid then it is intuitionistically provable This second property is called completeness A stronger cornpleteness result actually holds If a propo sition is H Valid in all nite Heyting algebras H then it is intuitionistically provable 592 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES As a consequence if a proposition is not provable intu itionistically then it can be falsi ed in some nite Heyting algebra Remark If X is any set a topology on X is a family 9 of subsets of X satisfying the following conditions DWEOandXEC 2 For every family even in nite UmE 1 of sets U E 9 we have UZEI U E 9 3 For every m te farnily U 1S Sn of sets U E 9 we have H136 U E 9 Every subset in 9 is called an open subset of X in the topology 9 The pair ltX Ogt is called a topological space 58 DISTRIBUTIVE LATTICES BOOLEAN ALGEBRAS HEYTING ALGEBRAS 593 Given any subset A of X the union of all open subsets contained in A is the largest open subset of A and is denoted A Given a topological space X Ogt we claim that 9 with the inclusion ordering is a Heyting algebra with O 0 1 X V U union intersection and with U gtVX UUV Here X U is the complement of U in X In this Heyting algebra we have 0 373 Since X U is usually not open we generally have U y U Therefore we see that topology yields another supply of Heyting algebras 594 CHAPTER 5 PARTIAL ORDERS EQUIVALENCE RELATIONS LATTICES Bibliography 1 Claude Berge Principles of Combinatorics Aca dernic Press rst edition 1971 2 J Carneron Peter Combinatorics Topics Tech niques Algorithms Cambridge University Press rst edition 1994 3 John H Conway and K Guy Richard The Book of Numbers Copernicus Springer Verlag rst edition 1996 4 Herbert B Enderton Elements of Set Theory Aca dernic Press rst edition 1977 5 Jean Callier Constructive Logics Part I A Tutorial on Proof Systems and Typed Ca1cu1i Theoretical Computer Science 11022497339 1993 6 Jean H Callier Logic for Computer Science Harper and Row New York 1986 595 596 BIBLIOGRAPHY 7 Timothy Gowers Mathematics A very Short In troduction Oxford University Press rst edition 2002 8 Ronald L Graham Donald E Knuth and Oren Patashnik Concrete Mathematics A Foundation For Computer Science Addison Wesley second edi tion 1994 9 Donald E Knuth The Art of Computer Program ming Volume 2 Seminumerical Algorithms Ad dison Wesley third edition 1997 10 L Lovasz J Pelikan and K Vesztergombi Discrete Mathematics Elementary and Beyond Under graduate Texts in Mathematics Springer rst edi tion 2003 11 Jiri Matousek Lectures on Discrete Geometry GTM No 212 Springer Verlag rst edition 2002 12 Paulo Ribenboim The Little Book of Bigger Primes Springer Verlag second edition 2004 13 Joseph H Silyerman A Friendly Introduction to Number Theory Prentice Hall rst edition 1997 14 Richard P Stanley Enumeratiue C0mbinat0rics Vol 1 Cambridge Studies in Advanced Mathemat BIBLIOGRAPHY 597 ics No 49 Cambridge University Press rst edition 1997 15 D van Dalen Logic and Structure Universitext Springer Verlag second edition 1980 16 JH van Lint and RM Wilson A Course m Com binatorics Cambridge University Press second edi tion 2001

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.