Preface ..................................................... xiii
Glossary of Notation ......................................... xix
Picture Gallery ............................................ xxiii
Acknowledgments .............................................. xxv
I A Brief Introduction to Lattices ............................ 1
1 Basic Concepts .............................................. 3
1.1 Ordering ............................................... 3
1.1.1 Orders .......................................... 3
1.1.2 Diagrams ........................................ 5
1.1.3 Order constructions ............................. 5
1.1.4 Partitions ...................................... 6
1.2 Lattices and semilattices .............................. 8
1.2.1 Lattices ........................................ 8
1.2.2 Semilattices and closure systems ............... 10
1.3 Some algebraic concepts ............................... 12
1.3.1 Homomorphisms .................................. 12
1.3.2 Sublattices .................................... 13
1.3.3 Congruences .................................... 14
2 Special Concepts ........................................... 19
2.1 Elements and lattices ................................. 19
2.2 Direct and subdirect products ......................... 20
2.3 Polynomials and identities ............................ 23
2.4 Gluing ................................................ 26
2.5 Modular and distributive lattices ..................... 30
2.5.1 The characterization theorems .................. 30
2.5.2 Finite distributive lattices ................... 31
2.5.3 Finite modular lattices ........................ 32
3 Congruences ................................................ 35
3.1 Congruence spreading .................................. 35
3.2 Prime intervals ....................................... 37
3.3 Congruence-preserving extensions and variants ......... 39
II Basic Techniques .......................................... 45
4 Chopped Lattices ........................................... 47
4.1 Basic definitions ..................................... 47
4.2 Compatible vectors of elements ........................ 49
4.3 Compatible vectors of congruences ..................... 50
4.4 From the chopped lattice to the ideal lattice ......... 52
4.5 Sectional complementation ............................. 53
5 Boolean Triples ............................................ 57
5.1 The general construction .............................. 57
5.2 The congruence-preserving extension property .......... 60
5.3 The distributive case ................................. 62
5.4 Two interesting intervals ............................. 63
6 Cubic Extensions ........................................... 71
6.1 The construction ...................................... 71
6.2 The basic property .................................... 73
III Representation Theorems .................................. 77
7 The Dilworth Theorem ....................................... 79
7.1 The representation theorem ............................ 79
7.2 Proof-by-Picture ...................................... 80
7.3 Computing ............................................. 82
7.4 Sectionally complemented lattices ..................... 83
7.5 Discussion ............................................ 85
8 Minimal Representations .................................... 93
8.1 The results ........................................... 93
8.2 Proof-by-Picture for minimal construction ............. 94
8.3 The formal construction ............................... 95
8.4 Proof-by-Picture for minimality ....................... 97
8.5 Computing minimality .................................. 99
8.6 Discussion ........................................... 100
9 Semimodular Lattices ...................................... 105
9.1 The representation theorem ........................... 105
9.2 Proof-by-Picture ..................................... 106
9.3 Construction and proof ............................... 107
9.4 Discussion ........................................... 114
10 Modular Lattices .......................................... 115
10.1 The representation theorem ........................... 115
10.2 Proof-by-Picture ..................................... 116
10.3 Construction and proof ............................... 120
10.4 Discussion ........................................... 125
11 Uniform Lattices .......................................... 129
11.1 The representation theorem ........................... 129
11.2 Proof-by-Picture ..................................... 129
11.3 The lattice N(A, B) .................................. 132
11.4 Formal proof ......................................... 137
11.5 Discussion ........................................... 139
IV Extensions ................................................ 143
12 Sectionally Complemented Lattices ......................... 145
12.1 The extension theorem ................................ 145
12.2 Proof-by-Picture ..................................... 146
12.3 Simple extensions .................................... 148
12.4 Formal proof ......................................... 150
12.5 Discussion ........................................... 152
13 Semimodular Lattices ...................................... 153
13.1 The extension theorem ................................ 153
13.2 Proof-by-Picture ..................................... 153
13.3 The conduit .......................................... 156
13.4 The construction ..................................... 157
13.5 Formal proof ......................................... 159
13.6 Discussion ........................................... 159
14 Isoform Lattices .......................................... 161
14.1 The result ........................................... 161
14.2 Proof-by-Picture ..................................... 161
14.3 Formal construction .................................. 165
14.4 The congruences ...................................... 171
14.5 The isoform property ................................. 172
14.6 Discussion ........................................... 173
15 Independence Theorems ..................................... 177
15.1 Results .............................................. 177
15.2 Proof-by-Picture ..................................... 178
15.2.1 Frucht lattices ............................... 178
15.2.2 An automorphism-preserving simple extension ... 179
15.2.3 A congruence-preserving rigid extension ....... 180
15.2.4 Merging the two extensions .................... 181
15.2.5 The representation theorems ................... 182
15.3 Formal proofs ........................................ 183
15.3.1 An automorphism-preserving simple extension ... 183
15.3.2 A congruence-preserving rigid extension ....... 185
15.3.3 Proof of the independence theorems ............ 185
15.4 Discussion ........................................... 187
16 Magic Wands ............................................... 189
16.1 Constructing congruence lattices ..................... 189
16.1.1 Bijective maps ................................ 189
16.1.2 Surjective maps ............................... 190
16.2 Proof-by-Picture for bijective maps .................. 191
16.3 Verification for bijective maps ...................... 194
16.4 2/3-boolean triples .................................. 198
16.5 Proof-by-Picture for surjective maps ................. 204
16.6 Verification for surjective maps ..................... 206
16.7 Discussion ........................................... 207
V Two Lattices .............................................. 213
17 Sublattices ............................................... 215
17.1 The results .......................................... 215
17.2 Proof-by-Picture ..................................... 217
17.3 Multi-coloring ....................................... 219
17.4 Formal proof ......................................... 220
17.5 Discussion ........................................... 221
18 Ideals .................................................... 227
18.1 The results .......................................... 227
18.2 Proof-by-Picture for the main result ................. 228
18.3 A very formal proof: Main result ..................... 230
18.3.1 Categoric preliminaries ....................... 230
18.3.2 From  ................................ 232
18.3.3 From  ................................ 232
18.3.4 From  ................................. 233
18.3.5 From  ................................ 234
18.3.6 From  ................................ 237
18.3.7 The final step ................................ 237
18.4 Proof for sectionally complemented lattices .......... 238
18.5 Proof-by-Picture for planar lattices ................. 241
18.6 Discussion ........................................... 242
19 Tensor Extensions ......................................... 245
19.1 The problem .......................................... 245
19.2 Three unary functions ................................ 246
19.3 Defining tensor extensions ........................... 248
19.4 Computing ............................................ 250
19.4.1 Some special elements ......................... 250
19.4.2 An embedding .................................. 252
19.4.3 Distributive lattices ......................... 253
19.5 Congruences .......................................... 254
19.5.1 Congruence spreading .......................... 254
19.5.2 Some structural observations .................. 257
19.5.3 Lifting congruences ........................... 259
19.5.4 The main lemma ................................ 261
19.6 The congruence isomorphism ........................... 262
19.7 Discussion ........................................... 263
Bibliography .............................................. 265
Index ........................................................ 275
|
