The q-theory of finite semigroups / John Rhodes, Benjamin Steinberg.

Format:

Book

Author/Creator:

Rhodes, John L.

Contributor:

Steinberg, Benjamin.

Series:

Springer monographs in mathematics

Springer monographs in mathematics, 1439-7382

Language:

English

Subjects (All):

Semigroups.

Physical Description:

xviii, 666 pages : illustrations ; 25 cm.

Place of Publication:

New York : Springer, [2009]

Summary:

Discoveries in finite semigroups have influenced several mathematical fields, including theoretical computer science, tropical algebra via matrix theory with coefficients in semirings, and other areas of modern algebra. This comprehensive, encyclopedic text will provide the reader - from the graduate student to the researcher/practitioner - with a detailed understanding of modern finite semigroup theory, focusing in particular on advanced topics on the cutting edge of research.

Key features: Develops q-theory, a new theory that provides a unifying approach to finite semigroup theory via quantization; Contains the only contemporary exposition of the complete theory of the complexity of finite semigroups; Introduces spectral theory into finite semigroup theory; Develops the theory of profinite semigroups from first principles, making connections with spectra of Boolean algebras of regular languages; Presents over 70 research problems, most new, and hundreds of exercises.

Additional features: For newcomers, an appendix on elementary finite semigroup theory; Extensive bibliography and index. The q-theory of Finite Semigroups presents important techniques and results, many for the first time in book form, and thereby updates and modernizes the literature of semigroup theory.

Contents:

Part I The q-operator and Pseudovarieties of Relational Morphisms

1 Foundations for Finite Semigroup Theory 15

1.1.1 General and philosophical remarks 16

1.1.2 Galois connections and adjunctions 17

1.2.1 Some adjunctions 22

1.2.2 Wreath and semidirect products 23

1.2.3 Going from monoid constructions to semigroup constructions 26

1.2.4 Block and two-sided semidirect products 30

1.2.5 Limits in FSgp 31

1.2.6 Division and pseudovarieties of semigroups 32

1.2.7 Terminology from lattice theory 34

1.3 Relational Morphisms 36

1.3.1 The category FSgp with arrows relational morphisms 36

1.3.2 Weak products and pullbacks 38

1.3.3 Divisions 40

1.3.4 Relational morphisms between relational morphisms 41

1.3.5 Divisions between relational morphisms 42

2 The q-operator 49

2.1 Axioms for Sets of Relational Morphisms 50

2.1.1 The axioms 50

2.1.2 Continuously closed classes and pseudovarieties of relational morphisms 51

2.1.3 First examples 56

2.2 Continuous Operators 57

2.3 Definition of the q-operator 61

2.3.1 Remarks on the determined meet of Cnt(PV) versus the pointwise meet 67

2.3.2 The generalized Mal'cev product and global Mal'cev condition 69

2.3.3 Minimal models for Cnt(PV) 79

2.4 Key Examples 80

2.4.1 Important examples of members of PVRM and GMC(PV) 81

2.4.2 Compact elements of GMC(PV) 87

2.4.3 Examples of continuous operators and continuously closed classes 88

2.5 The Derived Semigroupoid Theorem 93

2.5.1 The derived semigroupoid 93

2.5.2 The construction of the pseudovariety V[subscript D] 99

2.5.3 Digression on pseudovarieties of semigroupoids 103

2.6 The Kernel Semigroupoid Theorem 104

2.6.1 The kernel semigroupoid 104

2.6.2 The construction of the pseudovariety V[subscript K] 110

2.6.3 Non-associativity of the two-sided semidirect product 112

2.7 The Slice Theorem and Joins 114

2.8 Composition 115

2.8.1 Composition of sets of relational morphisms 116

2.8.2 The map q is a homomorphism 120

2.8.3 Modeling q by composition 120

2.8.4 The composition theorem for the semidirect product 122

2.9 Reverse Global Mal'cev Condition 123

3 The Equational Theory 127

3.1 Profinite Semigroups 128

3.1.1 Compact semigroups 128

3.1.2 Inverse limits, profinite spaces and profinite semigroups 132

3.2 Reiterman's Theorem 142

3.2.1 pro-V semigroups 142

3.2.2 Pseudoidentities and Reiterman's Theorem 143

3.3 On pro-V Relational Morphisms 147

3.4 Generators and Free pro-V Relational Morphisms 153

3.4.1 Generators for relational morphisms 153

3.5 Relational Pseudoidentities 157

3.5.1 Relational pseudoidentities 157

3.5.2 Digression on quasivarieties and min vs. max 166

3.6 Composition and Inevitable Substitutions 168

3.6.1 Free relational morphisms over compositions 168

3.6.2 Inevitable substitutions 171

3.6.3 Finitely equivalent collections 177

3.6.4 Membership in V [open dot in circle] W 181

3.6.5 Some decidability results 186

3.7 Basis Theorems 188

3.7.1 A compactness theorem 189

3.7.2 The basis theorems 191

3.7.3 A discussion of tameness 196

3.7.4 A projective basis theorem 196

3.8 Flows and the Basis Theorem for Semidirect Products 199

3.9 The Equational Theory for Continuously Closed Classes 206

3.9.1 Pseudoidentities for continuously closed classes 208

Part II Complexity in Finite Semigroup Theory

4 The Complexity of Finite Semigroups 215

4.1 The Prime Decomposition Theorem 216

4.1.1 Some wreath product decompositions 217

4.1.2 Augmented monoids 222

4.1.3 Proof of the Prime Decomposition Theorem 226

4.2 Brown's Theorem 234

4.3 The Definition of Complexity 237

4.4 Aperiodics and Schutzenberger's Theorem 242

4.5 Stiffler's Theorem 247

4.6 The Semilocal Theory 249

4.6.1 K'-morphisms 250

4.6.2 Maximal K'-congruences 255

4.7 The Classification of Subdirectly Indecomposable Semigroups 267

4.7.1 Congruence-free finite semigroups 272

4.8 The Exclusion Classes of U[subscript 2] and 2 276

4.9 The Fundamental Lemma of Complexity 281

4.10 The Decidability of Complexity for DS and Related Pseudovarieties 288

4.11 The Karnofsky-Rhodes Decompositions and G * A 292

4.12 Lower Bounds for Complexity 295

4.12.1 Constructing lower bounds for complexity 296

4.12.2 The complexity of full transformation and linear monoids 303

4.13 The Topology of Graphs and Graham's Theorem 308

4.13.1 Topology of labeled graphs 310

4.13.2 The incidence graph of a Rees matrix semigroup 314

4.14 The Presentation Lemma 323

4.14.1 Cross sections 325

4.14.2 Presentations 327

4.15 Tilson's Two J-class Theorem 338

4.16 Complexity Pseudovarieties Are Not Local 343

4.16.1 Proof of Theorem 4.16.1 344

4.16.2 The Type II subsemigroup of S[subscript n] 347

4.17 The Type II Theorem 349

4.17.1 Stallings folding and inverse graphs: an excursion into combinatorial group theory 349

4.17.2 The profinite topology on a free group 355

4.18 The Ribes and Zalesskii Theorem 363

4.18.1 Expansion by cyclic groups of prime order 363

4.19 Henckell's Theorem 368

4.19.1 An aperiodic variant of the Rhodes expansion 370

4.19.2 Blowup operators 376

4.19.3 Construction of the blowup operator 381

5 Two-Sided Complexity and the Complexity of Operators 387

5.1 Complexity of Operators 387

5.1.1 Complexity of a single operator 387

5.1.2 Complexity of two operators and the two-sided complexity function 388

5.2 Maximal Proper Surmorphisms 393

5.3 The Two-Sided Decomposition Theory 396

5.3.1 The MPS Decomposition Theorem 396

5.3.2 Consequences of the MPS Decomposition Theorem 402

5.4 The Ideal Theorem 407

5.4.1 Expansions 407

5.4.2 Proof of the Ideal Theorem 408

5.5 Translational Hulls and Ideal Extensions 409

5.5.1 Translational hulls 409

5.5.2 Ideal extensions 412

5.5.3 Constructing Examples 415

5.6 Two-Sided Complexity of 2 J-Semigroups 418

5.6.1 Two-sided complexity for small monoids 418

5.7 Lower Bounds 421

Part III The Algebraic Lattice of Semigroup Pseudovarieties

6 Algebraic Lattices, Continuous Lattices and Closure Operators 427

6.1 Complete and Algebraic Lattices 427

6.1.1 Algebraic lattices 428

6.1.2 Some lattice terminology 430

6.2 Continuous Lattices 433

6.2.1 Philosophical discussion on continuous lattices 435

6.3 Closure and Kernel Operators, Ideals and Morphisms 436

6.3.1 Homomorphism and substructure theorems 439

6.3.2 Some further facts about algebraic and continuous lattices 445

6.3.3 Continuous lattices and q-theory 450

6.4 Topologies on Algebraic Lattices 454

7 The Abstract Spectral Theory of PV 461

7.1 Birkhoff's Subdirect Representation Theorem 462

7.1.1 Atoms 467

7.1.2 Elementary examples of smi decompositions 470

7.2 Locally Dually Algebraic Lattices 471

7.3 A Brief Survey of Join Irreducibility 480

7.3.1 First examples of fji semigroups 480

7.3.2 Non-compact fji and sfji pseudovarieties 491

7.4 Kovacs-Newman Semigroups 497

7.4.1 Kovacs-Newman groups 497

7.4.2 Kovacs-Newman semigroups 501

7.4.3 Applications: Join irreducibility of H 506

7.5 Irreducibility for the Semidirect Product 509

7.6 Irreducibility for Pseudovarieties of Relational Morphisms 512

7.7 The Abstract Spectral Theory of Cnt(PV) 513

Part IV Quantales, Idempotent Semirings, Matrix Algebras and the Triangular Product

8 Quantales 523

8.1 Ordered Semigroups and Quantales 524

8.2 Green's Preorders vs.

the Quantale Ordering 527

8.3 Homomorphism and Substructure Theorems for Quantales 530

8.3.1 Examples in the context of semigroup theory 532

8.4 The Bialgebra of Regular Languages 535

8.5 Matrix Quantales and an Embedding Theorem 540

8.5.1 Matrix quantales 541

8.5.2 An embedding theorem 542

9 The Triangular Product and Decomposition Results for Semirings 547

9.1 Semirings 547

9.1.1 Ideals and quotient modules 553

9.2 The Triangular Product 558

9.2.1 A wreath product embedding 562

9.2.2 The Schutzenberger product 564

9.3 The Triangular Decomposition Theorem 566

9.4 The Prime Decomposition Theorem for Idempotent Semirings 573

9.4.1 The Prime Decomposition Theorem 573

9.4.2 Irreducibility for the triangular product 575

9.5 Complexity of Idempotent Semirings 587

9.5.1 Applications to the group complexity of power semigroups 590

A The Green-Rees Local Structure Theory 595

A.1 Ideal Structure and Green's Relations 595

A.2 Stable Semigroups 598

A.3 Green's Lemma and Maximal Subgroups 601

A.3.1 The Schutzenberger group 604

A.4 Rees's Theorem 606

B Tables on Preservation of Sups and Infs 613.

Notes:

Includes bibliographical references (pages [623]-642) and indexes.

ISBN:

9780387097800

0387097805

OCLC:

311458897