Discrete Mathematics(ID) Spring 2013 Lecture 1: Lattice(I 1 Introduction In the first half of the nineteenth century, George Boole's attempt to formalize propositional logic led to the concept of boolean algebras. While investigating the axiomatics of boolean algebras at the end of the nineteenth century, Charles S. Pierce and Ernst Schroder, both provided many contributions to mathematical logic, found it useful to introduce the lattice concept. Independently, Richard Dedekind's research on ideals of algebraic numbers also led to the same discover Although some of the early results of these mathematicians are very elegant and far from trivial they did not attract the attention of the mathematical community. It was the work of Garrett Birkhoff in the mid-1930s that kicked off the general development of lattice theory. In a brilliant series of papers, he demonstrated the importance of lattice theory and showed that it provides a unifying framework for hitherto unrelated developments in many mathematical disciplines. Birkhoff attempted to sell it to the general mathematical community, which he did with astonishing success in the first edition of his monograph Lattice Theory The explosive growth of this field continued. While the 1960s provided under 1, 500 papers and books, the seventies up to 2, 700, the eighties over 3, 200, the nineties almost 3, 600, and the first decade of this century about 4,000 There are numerous topics covered by lattice theory. Several monographs are on lattice theory include Birkhoff's classic. In our course, we only introduce some elementary concepts and results of this theory. Traditionally, lattice theory should be taught under the category of abstract algebra However, it can be explored from two different points of view. First, a Lattice is just a partial order with two special operations, which will be discussed latter in detail. Second, it can also be defined in algebra approach 2 Review of partial order set In order to show a lattice from the order's perspective, we first simply review the partial order and some concepts associated with it, such as bound and extreme elements Definition 1. Given a set A and a relation R on it,< A, R> is called a partially ordered set( poset in brief if R is reflexive, antisymmetric and transitive Once a order is defined, elements in the set could be compared between each other to distinguish the bigger or the smaller one. So it is intuitive to define some general terms such as extreme element as the following Definition 2. Given a poset< A, <> we haveDiscrete Mathematics (II) Spring 2013 Lecture 1: Lattice(I) Lecturer: Yi Li 1 Introduction In the first half of the nineteenth century, George Boole’s attempt to formalize propositional logic led to the concept of boolean algebras. While investigating the axiomatics of boolean algebras at the end of the nineteenth century, Charles S. Pierce and Ernst Schr¨oder, both provided many contributions to mathematical logic, found it useful to introduce the lattice concept. Independently, Richard Dedekind’s research on ideals of algebraic numbers also led to the same discovery. Although some of the early results of these mathematicians are very elegant and far from trivial, they did not attract the attention of the mathematical community. It was the work of Garrett Birkhoff in the mid-1930s that kicked off the general development of lattice theory. In a brilliant series of papers, he demonstrated the importance of lattice theory and showed that it provides a unifying framework for hitherto unrelated developments in many mathematical disciplines. Birkhoff attempted to sell it to the general mathematical community, which he did with astonishing success in the first edition of his monograph Lattice Theory. The explosive growth of this field continued. While the 1960s provided under 1,500 papers and books, the seventies up to 2,700, the eighties over 3,200, the nineties almost 3,600, and the first decade of this century about 4,000. There are numerous topics covered by lattice theory. Several monographs are on lattice theory include Birkhoff’s classic. In our course, we only introduce some elementary concepts and results of this theory. Traditionally, lattice theory should be taught under the category of abstract algebra. However, it can be explored from two different points of view. First, a Lattice is just a partial order with two special operations, which will be discussed latter in detail. Second, it can also be defined in algebra approach. 2 Review of Partial Order Set In order to show a lattice from the order’s perspective, we first simply review the partial order and some concepts associated with it, such as bound and extreme elements. Definition 1. Given a set A and a relation R on it, < A, R > is called a partially ordered set( poset in brief ) if R is reflexive, antisymmetric and transitive. Once a order is defined, elements in the set could be compared between each other to distinguish the bigger or the smaller one. So it is intuitive to define some general terms such as extreme element as the following. Definition 2. Given a poset < A, ≤>, we have: 1