86,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
A computational perspective on partial order and lattice theory, focusing on algorithms and their applications
This book provides a uniform treatment of the theory and applications of lattice theory. The applications covered include tracking dependency in distributed systems, combinatorics, detecting global predicates in distributed systems, set families, and integer partitions. The book presents algorithmic proofs of theorems whenever possible. These proofs are written in the calculational style advocated by Dijkstra, with arguments explicitly spelled out step by step. The author’s intent is for readers to learn not only the proofs, but the heuristics that guide said proofs.
Introduction to Lattice Theory with Computer Science Applications:
- Examines; posets, Dilworth’s theorem, merging algorithms, lattices, lattice completion, morphisms, modular and distributive lattices, slicing, interval orders, tractable posets, lattice enumeration algorithms, and dimension theory
- Provides end of chapter exercises to help readers retain newfound knowledge on each subject
- Includes supplementary material at www.ece.utexas.edu/~garg
Introduction to Lattice Theory with Computer Science Applications is written for students of computer science, as well as practicing mathematicians.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 381
Veröffentlichungsjahr: 2015
Ähnliche
Table of Contents
Cover
Title Page
Copyright
Dedication
List Of Figures
Nomenclature
Preface
Chapter 1: Introduction
1.1 Introduction
1.2 Relations
1.3 Partial Orders
1.4 Join and Meet Operations
1.5 Operations on Posets
1.6 Ideals and Filters
1.7 Special Elements in Posets
1.8 Irreducible Elements
1.9 Dissector Elements
1.10 Applications: Distributed Computations
1.11 Applications: Combinatorics
1.12 Notation and Proof Format
1.13 Problems
1.14 Bibliographic Remarks
Chapter 2: Representing Posets
2.1 Introduction
2.2 Labeling Elements of The Poset
2.3 Adjacency List Representation
2.4 Vector Clock Representation
2.5 Matrix Representation
2.6 Dimension-Based Representation
2.7 Algorithms to Compute Irreducibles
2.8 Infinite Posets
2.9 Problems
2.10 Bibliographic Remarks
Chapter 3: Dilworth's Theorem
3.1 Introduction
3.2 Dilworth's Theorem
3.3 Appreciation of Dilworth's Theorem
3.4 Dual of Dilworth's Theorem
3.5 Generalizations of Dilworth's Theorem
3.6 Algorithmic Perspective of Dilworth's Theorem
3.7 Application: Hall's Marriage Theorem
3.8 Application: Bipartite Matching
3.9 Online Decomposition of posets
3.10 A Lower Bound on Online Chain Partition
3.11 Problems
3.12 Bibliographic Remarks
Chapter 4: Merging Algorithms
4.1 Introduction
4.2 Algorithm to Merge Chains in Vector Clock Representation
4.3 An Upper Bound for Detecting an Antichain of Size
4.4 A Lower Bound for Detecting an Antichain of Size
4.5 An Incremental Algorithm for Optimal Chain Decomposition
4.6 Problems
4.7 Bibliographic Remarks
Chapter 5: Lattices
5.1 Introduction
5.2 Sublattices
5.3 Lattices as Algebraic Structures
5.4 Bounding The Size of The Cover Relation of a Lattice
5.5 Join-Irreducible Elements Revisited
5.6 Problems
5.7 Bibliographic Remarks
Chapter 6: Lattice Completion
6.1 INTRODUCTION
6.2 COMPLETE LATTICES
6.3 CLOSURE OPERATORS
6.4 TOPPED –STRUCTURES
6.5 DEDEKIND–MACNEILLE COMPLETION
6.6 STRUCTURE OF DEDEKIND—MACNEILLE COMPLETION OF A POSET
6.7 AN INCREMENTAL ALGORITHM FOR LATTICE COMPLETION
6.8 BREADTH FIRST SEARCH ENUMERATION OF NORMAL CUTS
6.9 DEPTH FIRST SEARCH ENUMERATION OF NORMAL CUTS
6.10 APPLICATION: FINDING THE MEET AND JOIN OF EVENTS
6.11 APPLICATION: DETECTING GLOBAL PREDICATES IN DISTRIBUTED SYSTEMS
6.12 APPLICATION: DATA MINING
6.13 PROBLEMS
6.14 BIBLIOGRAPHIC REMARKS
Chapter 7: Morphisms
7.1 INTRODUCTION
7.2 LATTICE HOMOMORPHISM
7.3 LATTICE ISOMORPHISM
7.4 LATTICE CONGRUENCES
7.5 QUOTIENT LATTICE
7.6 LATTICE HOMOMORPHISM AND CONGRUENCE
7.7 PROPERTIES OF LATTICE CONGRUENCE BLOCKS
7.8 APPLICATION: MODEL CHECKING ON REDUCED LATTICES
7.9 PROBLEMS
7.10 BIBLIOGRAPHIC REMARKS
Chapter 8: Modular Lattices
8.1 INTRODUCTION
8.2 MODULAR LATTICE
8.3 CHARACTERIZATION OF MODULAR LATTICES
8.4 PROBLEMS
8.5 BIBLIOGRAPHIC REMARKS
Chapter 9: Distributive Lattices
9.1 INTRODUCTION
9.2 FORBIDDEN SUBLATTICES
9.3 JOIN-PRIME ELEMENTS
9.4 BIRKHOFF'S REPRESENTATION THEOREM
9.5 FINITARY DISTRIBUTIVE LATTICES
9.6 PROBLEMS
9.7 BIBLIOGRAPHIC REMARKS
Chapter 10: Slicing
10.1 Introduction
10.2 Representing Finite Distributive Lattices
10.3 Predicates on Ideals
10.4 Application: Slicing Distributed Computations
10.5 Problems
10.6 Bibliographic Remarks
Chapter 11: Applications of Slicing to Combinatorics
11.1 Introduction
11.2 Counting Ideals
11.3 Boolean Algebra and Set Families
11.4 Set Families of Size
11.5 Integer Partitions
11.6 Permutations
11.7 Problems
11.8 Bibliographic Remarks
Chapter 12: Interval Orders
12.1 Introduction
12.2 Weak Order
12.3 Semiorder
12.4 Interval Order
12.5 Problems
12.6 Bibliographic Remarks
Chapter 13: Tractable posets
13.1 Introduction
13.2 Series–Parallel Posets
13.3 Two-Dimensional Posets
13.4 Counting Ideals of A Two-Dimensional Poset
13.5 Problems
13.6 Bibliographic Remarks
Chapter 14: Enumeration Algorithms
14.1 Introduction
14.2 BFS Traversal
14.3 DFS Traversal
14.4 Lex Traversal
14.5 Uniflow Partition of Posets
14.6 Enumerating Tuples of Product Spaces
14.7 Enumerating all Subsets
14.8 Enumerating all Subsets of Size
14.9 Enumerating Young'S Lattice
14.10 Enumerating Permutations
14.11 Lexical Enumeration of all Order Ideals of A Given Rank
14.12 Problems
14.13 Bibliographic Remarks
Chapter 15: Lattice of Maximal Antichains
15.1 Introduction
15.2 Maximal Antichain Lattice
15.3 An Incremental Algorithm Based on Union Closure
15.4 An Incremental Algorithm Based on BFS
15.5 Traversal of The Lattice of Maximal Antichains
15.6 Application: Detecting Antichain-Consistent Predicates
15.7 Construction and Enumeration of Width Antichain Lattice
15.8 Lexical Enumeration of Closed Sets
15.9 Construction of Lattices Based on Union Closure
15.10 Problems
15.11 Bibliographic Remarks
Chapter 16: Dimension Theory
16.1 Introduction
16.2 Chain Realizers
16.3 Standard Examples of Dimension Theory
16.4 Relationship Between The Dimension and The Width of A Poset
16.5 Removal Theorems for Dimension
16.6 Critical Pairs in The Poset
16.7 String Realizers
16.8 Rectangle Realizers
16.9 Order Decomposition Method and Its Applications
16.10 Problems
16.11 Bibliographic Remarks
Chapter 17: Fixed Point Theory
17.1 Complete Partial Orders
17.2 Knaster–Tarski Theorem
17.3 Application: Defining Recursion Using Fixed Points
17.4 Problems
17.5 Bibliographic Remarks
Bibliography
Index
End User License Agreement
Pages
xiii
xiv
xv
xvi
xvii
xviii
xix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
29
30
31
32
33
34
35
36
37
38
39
41
42
43
44
45
46
47
48
49
50
51
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
131
132
133
134
135
136
137
139
140
141
142
143
144
145
146
147
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
215
216
217
218
219
220
221
222
223
224
225
226
227
235
236
237
Guide
Cover
Table of Contents
Preface
Begin Reading
List of Illustrations
Chapter 1: Introduction
Figure 1.1 The graph of a relation.
Figure 1.2 Hasse diagram.
Figure 1.3 Only the first two posets are lattices.
Figure 1.4 (a) Pentagon() and (b) diamond().
Figure 1.5 Cross product of posets.
Figure 1.6 A computation in the happened-before model.
Figure 1.7 Ferrer's diagram for shown to contain .
Figure 1.8 Young's lattice for .
Chapter 2: Representing Posets
Figure 2.1 Adjacency list representation of a poset.
Figure 2.2 Vector clock labeling of a poset for a distributed computation.
Figure 2.3 Vector clock algorithm.
Figure 2.4 (a) An antichain of size 5 and (b) its two linear extensions.
Figure 2.6 (a) A p-diagram and (b) its corresponding infinite poset.
Figure 2.5 (a,b) Trivial examples of p-diagrams.
Chapter 3: Dilworth's Theorem
Figure 3.1 Decomposition of into chains.
Figure 3.2 Hall's Marriage Theorem.
Figure 3.3 A poset of width forcing an algorithm to use three chains for decomposition.
Figure 3.4 Chain partitioning algorithm.
Chapter 4: Merging Algorithms
Figure 4.1 Function that determines if an antichain of size exists.
Figure 4.2 An example of a failed naive strategy. (
a
) The initial configuration. (
b
) The point at which the strategy fails: there is nowhere to insert . (
c
) This example can be merged into two chains.
Figure 4.3 Generalized merge procedure for posets.
Figure 4.4 Function
FindQ
that finds the output queue to insert an element.
Figure 4.5 Using a queue insert graph to find the output queue.
Figure 4.6 Algorithm for the adversary. and , we get the lower bound of . However, the lower bound of is well known for this case.
Chapter 5: Lattices
Figure 5.1 Examples: lattices and sublattices.
Figure 5.2 Table notation for the algebra .
Figure 5.3 Join-irreducible elements: .
Chapter 6: Lattice Completion
Figure 6.1 (a) A poset. (b) Its completion (the unshaded vertex is the added element).
Figure 6.2 A poset that is not a complete lattice.
Figure 6.3 The completion of the poset from Figure 6.2.
Figure 6.4 Two posets and their completions.
Figure 6.5 The complete lattice via order ideals that embeds the poset from Figure 6.4(b).
Figure 6.6 Incremental algorithm IDML for DM construction.
Figure 6.7 Algorithm BFS-DML for BFS enumeration of DM-Lattice.
Figure 6.8 Algorithm DFS-DML for DFS enumeration of DM-lattice.
Figure 6.9 (a) The original poset. (b) Equivalent representation using vector clocks. (c) Its Lattice of normal cuts.
Chapter 7: Morphisms
Figure 7.1 Monotone .
Figure 7.2
Figure 7.4 Simple reduction of state graph does not preserve path based formulas.
Figure 7.5 (a,b) Proof of Lemma 7.13
Figure 7.6 Proof of Lemma 7.13.
Chapter 8: Modular Lattices
Figure 8.1 Proof of Theorem 8.5.
Figure 8.2 Theorem 8.9.
Figure 8.3 (a) A ranked poset, (b) A poset that is not ranked, (c) A ranked and graded poset, and (d) A ranked and graded lattice.
Chapter 9: Distributive Lattices
Figure 9.1 Diamond —a nondistributive lattice.
Figure 9.2 A lattice , its set of join-irreducible s , and their ideals .
Figure 9.3 A lattice with the “N-poset” as the set of join-irreducible s.
Figure 9.4 (a) poset of Join- (“”) and meet- (“”) irreducible elements are isomorphic; (b) Irreducibles in a nondistributive lattice.
Chapter 10: Slicing
Figure 10.1 (a) : A partial order. (b) The lattice of ideals. (c) The directed graph .
Figure 10.2 (a) A directed graph and (b) the lattice of its nontrivial ideals.
Figure 10.3 (a) The poset or directed graph for generating subsets of of size . (b) The ideal denoting the subset .
Figure 10.4 Graphs and slices for generating subsets of when .
Figure 10.5 An efficient algorithm to detect a linear predicate.
Figure 10.6 An efficient algorithm to compute the slice for a predicate .
Figure 10.7 An efficient algorithm to compute the slice for a linear predicate .
Chapter 11: Applications of Slicing to Combinatorics
Figure 11.1 Graphs and slices for generating subsets of when .
Figure 11.2 Slice for the predicate “does not contain consecutive numbers”.
Figure 11.3 Ferrer's diagram for the integer partition for .
Figure 11.4 An Application of Ferrer's diagram.
Figure 11.5 Young's lattice for .
Figure 11.6 The poset corresponding to Ferrer's diagram of .
Figure 11.7 Slice for .
Figure 11.8 Slice for “distinct parts.”
Figure 11.9 Poset
Figure 11.10 Slice for subsets of permutations.
Chapter 12: Interval Orders
Figure 12.1 A poset that is a ranking.
Figure 12.2 Examples of weak orders (or rankings.)
Figure 12.3 A poset and its normal ranking extension.
Figure 12.4 Mapping elements of poset to interval order.
Chapter 13: Tractable posets
Figure 13.1 Example series and parallel compositions. (a–c) posets. (d) Result of . (e) Result of .
Figure 13.2 (a) An SP tree for the poset in Figure 13.1(e). (b) The conjugate SP tree. (c) The conjugate poset.
Figure 13.3 (a) A two-dimensional poset. (b) Its comparability graph . (c) . (d) A valid conjugate for the original poset.
Figure 13.4 The poset .
Figure 13.5 (a) is a non-separating linear extension of the partial order (b), when at least one of the dotted edges holds.
Figure 13.6 A two-dimensional poset .
Figure 13.7 Conjugate of the poset .
Figure 13.8 The order imposed by .
Figure 13.9 A partial order that has a nonseparating linear extension.
Chapter 14: Enumeration Algorithms
Figure 14.1 (a) A computation. (b) Its lattice of consistent global states. (c) Traversals of the lattice.
Figure 14.2 BFS enumeration of CGS.
Figure 14.3 A vector clock based BFS enumeration of CGS.
Figure 14.4 A vector clock based DFS enumeration of CGS.
Figure 14.5 An algorithm for lexical traversal of all ideals of a poset with any chain partition.
Figure 14.6 with example of an ideal.
Figure 14.7 (a) poset with uniflow partition. (b) with an example of an ideal mapped to the subset
Figure 14.8 (a) poset with uniflow partition (b) with example of an ideal.
Figure 14.9 (a) Chain partition of a poset that is not uniflow. (b) Uniflow chain partition of the same poset.
Figure 14.12 (a) poset with a uniflow partition (b) poset with a uniflow partition.
Figure 14.10 An algorithm for traversal of product space in lex order.
Figure 14.11 posets for generating subsets of .
Figure 14.13 An algorithm for traversal of all subsets of of size in lex order.
Figure 14.14 (a) A Ferrer's diagram. (b) A poset for generating Young's lattice.
Figure 14.15 An algorithm for traversal of all integer partitions in in lex order.
Figure 14.17 (a) poset with a negative uniflow partition. (b) with example of an ideal.
Figure 14.16 An algorithm for traversal of a level set in lexical order.
Figure 14.18 An algorithm to find the lexically smallest ideal at level greater than .
Figure 14.19 An Algorithm to find the next bigger ideal in a level set.
Chapter 15: Lattice of Maximal Antichains
Figure 15.1 (a) The original poset. (b) Its lattice of ideals (consistent cuts). (c) Its lattice of maximal antichains.
Figure 15.2 (a) The original poset. (b) Its lattice of maximal ideals. (c) Its lattice of maximal antichains. (d) Its lattice of strict ideals.
Figure 15.3 The algorithm ILMA for construction of lattice of maximal antichains.
Figure 15.4 The algorithm OLMA for construction of lattice of strict ideals.
Figure 15.5 (a) The original poset. (b) Its lattice of maximal ideals. (c) Its lattice of maximal antichains. (d) Its lattice of strict ideals.
Figure 15.6 An algorithm for traversal of closed sets in lex order.
Chapter 16: Dimension Theory
Figure 16.1 An example of a realizer.
Figure 16.2 Standard example .
Figure 16.3 Example of a critical pair: .
Figure 16.4 Encoding an infinite poset with strings.
Figure 16.5 A poset with a chain realizer and a string realizer.
Figure 16.6 An example of converting a string realizer to a chain realizer.
Figure 16.7 A bipartite poset.
Figure 16.8 String realizer for the bipartite poset in Figure 16.7.
Figure 16.9 Encoding for the bipartite poset in Figure 16.7.
Figure 16.10 Another Encoding for the bipartite poset in Figure 16.7.
Figure 16.11 An example of a poset with rectangular dimension two.
Figure 16.12 An example of decomposing a poset into series-parallel posets.
List of Tables
Chapter 12: Interval Orders
Table 12.1 Forbidden Structures for Various Orders
Chapter 14: Enumeration Algorithms
Table 14.2 Special cases of lex enumeration of level sets of the ideal lattice of a poset
Chapter 15: Lattice of Maximal Antichains
Table 15.1 Incremental Construction of the Lattice of Maximal Antichains of a poset extended with
Table 15.2 Algorithms for Lattice Enumeration of Maximal Antichains
Table 15.3 The Notation Used in this Chapter
Table 15.4 Summary of Lattices Based on Antichains
Table 15.5 Definition of Closure Operators for Lattices
Table 15.6 Generation of Lattices based on Unions
Introduction To Lattice Theory With Computer Science Applications
VIJAY K. GARG
Department of Electrical and Computer Engineering
The University of Texas at Austin
Copyright © 2015 by John Wiley & Sons, Inc. All rights reserved
Published by John Wiley & Sons, Inc., Hoboken, New Jersey
Published simultaneously in Canada
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging-in-Publication Data:
Garg, Vijay K. (Vijay Kumar), 1963-
Introduction to lattice theory with computer science applications / Vijay K. Garg.
pages cm
Includes bibliographical references and index.
ISBN 978-1-118-91437-3 (cloth)
1. Computer science–Mathematics. 2. Engineering mathematics. 3. Lattice theory. I. Title.
QA76.9.L38G37 2015
004.01′51–dc23
2015003602
To my family
Nomenclature
Bottom element of the lattice
Set of join-irreducible elements of a poset
Lattice of ideals
Lattice of normal cuts
Lattice of maximal antichains
Lattice of width antichains
Set of meet-irreducible elements of a poset
Meet
Join
Top element of the lattice
A poset consisting of a single chain of length
is comparable to
in
Set of lower bounds of
Preface
As many books exist on lattice theory, I must justify writing another book on the subject. This book is written from the perspective of a computer scientist rather than a mathematician. In many instances, a mathematician may be satisfied with a nonconstructive existential proof, but a computer scientist is interested not only in construction but also in the computational complexity of the construction. I have attempted to give “algorithmic” proofs of theorems whenever possible.
This book is also written for the sake of students rather than a practicing mathematician. In many instances, a student needs to learn the heuristics that guide the proof, besides the proof itself. It is not sufficient just to learn an important theorem. One must also learn ways to extend and analyze a theorem. I have also made an effort to include exercises with each chapter. A mathematical subject can only be learned by solving problems related to that subject.
I would like to thank the students at the University of Texas at Austin, who took my course on lattice theory. I also thank my co-authors for various papers related to lattice theory and applications in distributed computing: Anurag Agarwal, Arindam Chakraborty, Yen-Jung Chang, Craig Chase, Himanshu Chauhan, Selma Ikiz, Ratnesh Kumar, Neeraj Mittal, Sujatha Kashyap, Vinit Ogale, Alper Sen, Alexander Tomlinson, and Brian Waldecker. I owe special thanks to Bharath Balasubramanina, Vinit Ogale, Omer Shakil, Alper Sen, and Roopsha Samanta who reviewed parts of the book.
I thank the Department of Electrical and Computer Engineering at The University of Texas at Austin, where I was given the opportunity to develop and teach a course on lattice theory.
I have also been supported in part by many grants from the National Science Foundation. This book would not have been possible without that support.
Finally, I thank my parents, wife, and children. Without their love and support, this book would not have been even conceived.
The list of known errors and the supplementary material for the book will be maintained on my homepage:
http://www.ece.utexas.edu/~garg
Vijay K. Garg
Austin, Texas.
Chapter 1Introduction
1.1 Introduction
Partial order and lattice theory play an important role in many disciplines of computer science and engineering. For example, they have applications in distributed computing (vector clocks and global predicate detection), concurrency theory (pomsets and occurrence nets), programming language semantics (fixed-point semantics), and data mining (concept analysis). They are also useful in other disciplines of mathematics such as combinatorics, number theory, and group theory.
This book differs from earlier books written on the subject in two aspects. First, this book takes a computational perspective—the emphasis is on algorithms and their complexity. While mathematicians generally identify necessary and sufficient conditions to characterize a property, this book focuses on efficient algorithms to test the property. As a result of this bias, much of the book concerns itself only with finite sets. Second, existing books do not dwell on applications of lattice theory. This book treats applications at par with the theory. In particular, I have given applications of lattice theory to distributed computing and combinatorics.
This chapter covers the basic definitions of partial orders.
1.2 Relations
A partial order is simply a relation with certain properties. A relation over any set is a subset of . For example, let
Then, one possible relation is
It is sometimes useful to visualize a relation as a graph on the vertex set such that there is a directed edge from to iff . The graph corresponding to the relation in the previous example is shown in Figure 1.1.
Figure 1.1 The graph of a relation.
A relation is reflexive if for each , , i.e., each element of is related to itself. In terms of a graph, this means that there is a self-loop on each node. If is the set of natural numbers, , then “divides” is a reflexive relation. is irreflexive if for each , . In terms of a graph, this means that there are no self-loops. An example on the set of natural numbers, , is the relation “less than.” Note that a relation may be neither reflexive nor irreflexive.
A relation is symmetric if for all , implies . An example of a symmetric relation on is
A symmetric relation can be represented using an undirected graph. is antisymmetric if for all , and implies . For example, the relation less than or equal to defined on is anti-symmetric. A relation is asymmetric if for all , implies . The relation less than on is asymmetric. Note that an asymmetric relation is always irreflexive.
A relation is transitive if for all , and implies . The relations less than and equal to on are transitive.
A relation is an equivalence relation if it is reflexive, symmetric, and transitive. When is an equivalence relation, we use (or simply when is clear from the context) to denote that . Furthermore, for each , we use , called the equivalence class of, to denote the set of all such that . It can be seen that the set of all such equivalence classes forms a partition of . The relation on defined in (1.1) is an example of an equivalence relation. It partitions the set of natural numbers into five equivalence classes.
Given any relation on a set , we define its irreflexive transitive closure, denoted by , as follows. For all iff there exists a sequence with and such that
Thus , iff there is a nonempty path from to in the graph of the relation . We define the reflexive transitive closure, denoted by , as
Thus iff is reachable from by taking a path with zero or more edges in the graph of the relation .
1.3 Partial Orders
A relation R is a reflexive partial order (or, a nonstrict partial order) if it is reflexive, antisymmetric, and transitive. The divides relation on the set of natural numbers is a reflexive partial order. A relation is an irreflexive partial order, or a strict partial order if it is irreflexive and transitive. The less than relation on the set of natural numbers is an irreflexive partial order. When is a reflexive partial order, we use (or simply when is clear from the context) to denote that . A reflexive partially ordered set, poset for short, is denoted by . When is an irreflexive partial order, we use (or simply when is clear from the context) to denote that . The set together with the partial order is denoted by . We use to denote a irreflexive poset defined on .
The two versions of partial orders—reflexive and irreflexive—are essentially the same. Given an irreflexive partial order, we can define as or , which gives us a reflexive partial order. Similarly, given a reflexive partial order , we can define an irreflexive partial order by defining as and .
A relation is a total order if is a partial order and for all distinct , either or . The natural order on the set of integers is a total order, but the divides relation is only a partial order.
Finite posets are often depicted graphically using Hasse diagrams. To define Hasse diagrams, we first define a relation covers as follows. For any two elements , covers if and implies . In other words, if covers then there should not be any element with . We use to denote that covers (or is covered by ). We also say that is an upper cover of and is a lower cover of . A Hasse diagram of a poset is a graph with the property that there is an edge from to iff . Furthermore, when drawing the graph on a Euclidean plane, is drawn lower than when covers . This allows us to suppress the directional arrows in the edges. For example, consider the following poset ,
The corresponding Hasse diagram is shown in Figure 1.2. Note that we will sometimes use directed edges in Hasse diagrams if the context demands it. In general, in this book, we switch between the directed graph and undirected graph representations of Hasse diagrams.
Figure 1.2 Hasse diagram.
Given a poset a subposet is simply a poset , where , and
Let with . If either or , we say and are comparable. On the other hand, if neither nor , then we say and are incomparable and write . A poset (or a subposet of ) is called a chain if every distinct pair of elements from is comparable. Similarly, we call a poset an antichain if every distinct pair of elements from is incomparable. For example, for the poset represented in Figure 1.2, is a chain, and is an antichain.
A chain of a poset is a longest chain if no other chain contains more elements than . We use a similar definition for the largest antichain. The height of the poset is the number of elements in a longest chain, and the width of the poset is the number of elements in a largest antichain. For example, the poset in Figure 1.2 has height equal to 3 (the longest chain is ) and width equal to 2 (a largest antichain is ).
Generalizing the notation for intervals on the real-line, we define an interval in a poset as
The meanings of , and are similar. A poset is locally finite if all intervals are finite. Most posets in this book will be locally finite if not finite.
A poset is well-founded iff it has no infinite decreasing chain. The set of natural numbers under the usual relation is well-founded but the set of integers is not well-founded.
Poset extends the poset if
If is a total order, then we call a linear extension of . For example, for the poset defined in 1.2, a possible linear extension is
We now give some special posets that will be used as examples in the book.
A poset consisting of a single chain of length
denotes a poset which is a chain of length
. The second poset in
Figure 1.3
is
.
We use
to denote the poset of
incomparable elements.
Figure 1.3 Only the first two posets are lattices.
1.4 Join and Meet Operations
We now define two operators on subsets of the set —meet and join. The operator meet is also called infimum (or inf). Similarly, the operator join is also called supremum (or sup).
Let , where is a poset. For any , we say that iff
and
.
The condition (1) says that
