Linear Orderings (eBook)

Front Cover 1
Linear Orderings 4
Copyright Page 5
Contents 8
Preface 14
Acknowledgments 18
PART I: INTRODUCTION TO LINEAR ORDERINGS 20
Chapter 1. Introduction 22
1. Basic Definitions 22
2. Relations between Linear Orderings 25
3. Characteristics of Linear Orderings 29
4. Operations on Linear Orderings 33
5. Countable Linear Orderings 42
Chapter 2. Dense Linear Orderings 44
1. Dense Linear Orderings 44
2. Countable Dense Linear Orderings Properties of ?
3. Scattered Linear Orderings 51
4. Uncountable Dense Linear Orderings Completeness
Chapter 3. Well-Orderings and Ordinals 60
1. Well-Orderings 60
2. Ordinals and Cardinal Numbers 66
3. Ordinals and Induction 71
4. The Arithmetic of Ordinals 78
5. Continuous Functions 81
6. The Arithmetic of Cardinal Numbers 83
References 85
PART II: COMBINATORIAL ASPECTS OF LINEAR ORDERINGS 86
Chapter 4. Condensing Linear Orderings 88
1. Condensations and Homomorphisms 88
2. The Condensation cF 90
3. The Condensation cW 91
4. The Condensation cS 93
References 94
Chapter 5. Hausdorff’s Theorem 95
1. Introduction 95
2. Iterated Condensations 98
3. Hausdorff’s Theorem 103
4. Z and Its Powers 109
References 111
Chapter 6. The Ehrenfeucht–Fraisse Game 112
I . The Play of the Game 112
2. Games and Ordinals 124
References 128
Chapter 7. Ramsey’s Theorem and Ehrenfeucht Games 129
1. Ramsey’s Theorem 129
2. The Theorem of Läuchli and Leonard for Scattered Linear Orderings 132
3. Dense Partitions of ? The Shuffle Operation
4. The Theorem of Läuchli and Leonard 137
References 139
Chapter 8. Transitive Linear Orderings 140
1. Transitive Linear Orderings 140
2. The Order Types of Ordered Abelian Groups 143
3. Lexicographic Products and the Order Type of the Irrationals 146
4. Transitivity and the Exponentration of Linear Orderings 149
5. Automorphisms of Linear Orderings 151
6. Almost Transitive Linear Orderings 155
References 162
Chapter 9. Uncountable Dense Linear Orderings 164
1. Diagonal Arguments and the Theorem of Dushnik and Miller 164
2. The Theorems of Sierpinski 171
3. Suborderings of ?, Continued 174
4. ?x-Orderings 182
References 190
Chapter 10. Embeddings of Linear Orderings and Fraïssé’s Conjecture 193
1. Indecomposable Order Types 193
2. Fraïssé’s Results and Conjectures 196
3. Well-Quasi-Orderings 202
4. Better-Quasi-Orderings 207
5. Additively Indecomposable Linear Orderings and Fraïssé’s Conjecture 215
References 222
Chapter 11. Partition Theorems 224
References and Bibliography on Partition Theorems 235
PART lll: LOGICAL ASPECTS OF LINEAR ORDERINGS 240
Chapter 12. Linear Orderings and Formal Languages 242
1. Introduction 242
2. First-Order Languages 248
3. Infinitary Languages 255
4. Second-Order Languages 259
5. Algorithms and Decision Procedures 260
References 265
Chapter 13. The First-Order Theory of Linear Orderings 266
1. The Ehrenfeucht–Fraïssé’s Games and First-Order Theories 266
2. The Ehrenfeucht Games and the First-Order Theory of Linear Orderings 272
3. Decidability of First-Order Theories of Linear Orderings 286
4. Model Theory and Linear Orderings 292
5. The Number of Countable Models of a Complete Theory 315
6. Finitely Axiomatizable Linear Orderings 344
References 361
Chapter 14. The Infinitary Theories of Linear Orderings 363
1. The Expressive Power of L?1? and L?? 363
2. The Karp Game 368
3. Scott Sentences 377
4. Completely Characterizable Linear Orderings 382
5. Additional Results 386
References 388
Chapter 15. The Second-Order Theories of Linear Orderings 389
1. The Generalized Ehrenfeucht Games 389
2. The Generalized Ehrenfeucht Game and the Weak Second-Order Theory of Linear Orderings 397
3. Decidability of the Weak Second-Order Theory of Linear Orderings 402
4. The Monadic Second-Order Theory of Linear Orderings 415
References 418
Chapter 16. Linear Orderings and Recursion Theory 420
1. Introduction 420
2. Looking at Q Effectively 424
3. Recursive Linear Orderings 428
4. The Arithmetical Hierarchy 433
5. Recursive Linear Orderings and the Arithmetical Hierarchy 440
6. Diagonal Arguments in Recursion Theory 454
7. Effective Versions of Combinatorial Theorems 457
References 473
Complete Bibliography of Linear Orderings 475
List of Notation 496
Author Index 498
Subject Index 501
Pure and Applied Mathematics 507