Preface to the Second Edition ................................... v
Preface to the First Edition .................................. vii
List of Figures ................................................ ix
List of Tables ................................................. xi
1 Logic and Proofs ............................................. 1
1.1 Introduction ............................................ 1
1.2 Statements, Connectives and Truth Tables ................ 2
1.3 Relations between Statements ............................ 5
1.4 Quantifiers ............................................. 6
1.5 Methods of Proof ........................................ 9
1.6 Exercises .............................................. 11
2 Set Theory .................................................. 13
2.1 Initial Concepts ....................................... 13
2.2 Relations between Sets ................................. 15
2.3 Operations Defined on Sets - or New Sets from Old ...... 16
2.4 Exercises .............................................. 19
3 Cartesian Products, Relations, Maps and Binary Operations ... 23
3.1 Introduction ........................................... 23
3.2 Cartesian Product ...................................... 23
3.3 Maps ................................................... 29
3.4 Binary Operations ...................................... 37
3.5 Exercises .............................................. 51
4 The Integers ............................................... 55
4.1 Introduction ........................................... 55
4.2 Elementary Properties .................................. 55
4.3 Divisibility ........................................... 61
4.4 The Fundamental Theorem of Arithmetic .................. 67
4.5 Congruence Modulo n and the Algebraic System
( n, +, •) ............................................. 69
4.6 Linear Congruences in and Linear Equations in n ..... 75
4.7 Exercises .............................................. 80
5 Groups ...................................................... 85
5.1 Introduction ........................................... 85
5.2 Definitions and Elementary Properties .................. 86
5.3 Alternative Axioms for Groups .......................... 93
5.4 Subgroups .............................................. 96
5.5 Cyclic Groups ......................................... 109
5.6 Exercises ............................................. 113
6 Further Properties of Groups ............................... 117
6.1 Introduction .......................................... 117
6.2 Cosets ................................................ 117
6.3 Isomorphisms and Homomorphisms ........................ 123
6.4 Normal Subgroups and Factor Groups .................... 134
6.5 Direct Product of Groups .............................. 145
6.6 Exercises ............................................. 152
7 The Symmetric Groups ...................................... 157
7.1 Introduction .......................................... 157
7.2 The Cayley Representation Theorem ..................... 157
7.3 Permutations as Products of Disjoint Cycles ........... 159
7.4 Even and Odd Permutations ............................. 166
7.5 The Simplicity oi An .................................. 176
7.6 Exercises ............................................. 180
8 Rings, Integral Domains and Fields ........................ 183
8.1 Rings ................................................. 183
8.2 Ring Homomorphisms, Ring Isomorphisms, and Ideals ..... 192
8.3 Isomorphism Theorems .................................. 198
8.4 Direct Product and Direct Sum of Rings ................ 199
8.5 Principal Ideal Domains and Unique Factorization
Domains ............................................... 207
8.6 Embedding an Integral Domain in a Field ............... 211
8.7 The Characteristic of an Integral Domain .............. 214
8.8 Exercises ............................................. 217
9 Polynomial Rings ........................................... 225
9.1 Introduction .......................................... 225
9.2 The Ring of Power Series with Coefficients in a
Commutative Unital Ring R ............................. 226
9.3 The Ring of Polynomials with Coefficients in a
Commutative Unital Ring ............................... 228
9.4 The Division Algorithm and Applications ............... 234
9.5 Irreducibility and Factorization of Polynomials ....... 240
9.6 Polynomials over  ................................... 245
9.7 Irreducible Polynomials over  and  ................. 250
9.8 Quotient Rings of the Form F[x]/(ƒ), F a Field ........ 253
9.9 Exercises ............................................. 259
10 Field Extensions ........................................... 263
10.1 Introduction .......................................... 263
10.2 Definitions and Elementary Results .................... 263
10.3 Algebraic and Transcendental Elements ................. 267
10.4 Algebraic Extensions .................................. 270
10.5 Finite Fields ......................................... 276
10.6 Exercises ............................................. 284
11 Latin Squares and Magic Squares ............................ 289
11.1 Introduction .......................................... 289
11.2 Magic Squares ......................................... 294
11.3 Exercises ............................................. 296
12 Group Actions, the Class Equation, and the Sylow Theorems .. 299
12.1 Group Actions ......................................... 299
12.2 The Class Equation of a Finite Group .................. 303
12.3 The Sylow Theorems .................................... 304
12.4 Applications of the Sylow Theorems .................... 307
12.5 Exercises ............................................. 322
13 Finitely Generated Abelian Groups .......................... 327
13.1 Introduction and Prehminary Results ................... 327
13.2 Direct Sum of AbeHan Groups ........................... 330
13.3 Free Abelian Groups ................................... 332
13.4 Finite Abelian Groups ................................. 336
13.5 The Structure of the Group of Units of n ............. 340
13.6 Exercises ............................................. 345
14 Semigroups and Automata .................................... 347
14.1 Introduction .......................................... 347
14.2 Semigroups ............................................ 347
14.3 The Semigroup of Relations on a Set ................... 364
14.4 Green's Relations ..................................... 367
14.5 Semigroup Actions ..................................... 377
14.6 Automata Theory ....................................... 385
14.7 Exercises ............................................. 399
15 Isometrics ................................................. 407
15.1 Isometries of n ...................................... 407
15.2 Finite Subgroups of the Isometry Group of 2 .......... 412
15.3 The Classification of the Finite Subgroups of SO(3) ... 416
15.4 The Platonic Solids ................................... 421
15.5 Exercises ............................................. 428
16 Polya-Burnside Enumeration ................................. 431
16.1 Introduction .......................................... 431
16.2 A Theorem of Polya .................................... 434
16.3 Enumeration Examples .................................. 436
16.4 Exercises ............................................. 440
17 Group Codes ................................................ 445
17.1 Introduction .......................................... 445
17.2 Group Codes ........................................... 451
17.3 Construction of Group Codes ........................... 454
17.4 At the Receiving End .................................. 457
17.5 Nearest Neighbor Decoding for Group Codes ............. 457
17.6 Hamming Codes ......................................... 460
17.7 Exercises ............................................. 463
18 Polynomial Codes ........................................... 467
18.1 Definitions and Elementary Results .................... 467
18.2 BCH Codes ............................................. 472
18.3 Decoding for a BCH Code ............................... 477
18.4 Exercises ............................................. 482
Appendix A Rational, Real, and Complex Numbers ............... 485
A.l Introduction .......................................... 485
A.2 The Order Relation on the Real Number System .......... 486
A.3 Decimal Representation of Rational Numbers ............ 489
A.4 Complex Numbers ....................................... 492
A.5 The Polar Form of a Complex Number .................... 495
A 6 Exercises ............................................. 499
Appendix В Linear Algebra .................................... 503
B.l Vector Spaces ......................................... 503
B 2 Linear Transformations ................................ 513
B.3 Determinants .......................................... 525
B.4 Eigenvalues and Eigenvectors .......................... 536
B.5 Exercises ............................................. 541
Index ......................................................... 545
|
