SCHAUM'S ouTlines DISCRETE MATHEMATICS Third Edition SEYMOUR LIPSCHUTZ MARC LIPSON Hundreds of fully solved problems New chapters on computer arithmatic and cryptology Covers all course fundamentals- supplements any course text TRUSTED BY MORE THAN 40 MILLION STUDENTS Use WiththeseouDisrete Mathematies Discrete Mathematics
PREFACE Discrete mathematics,the study of finite systems,has become increasingly important as the computer age has advanced.The digital computer is basically a finite structure,and many of its properties can be understood and interpreted within the framework of finite mathematical systems.This book,in presenting the more essential material,may be used as a textbook for a formal course in discrete mathematics or as a supplement to all current texts. The first three chapters cover the standard material on sets,relations,and functions and algorithms.Next come chapters on logic,counting,and probability.We then have three chapters on graph theory:graphs,directed graphs,and binary trees.Finally there are individual chapters on properties of the integers,languages,machines, ordered sets and lattices,and Boolean algebra,and appendices on vectors and matrices,and algebraic systems. The chapter on functions and algorithms includes a discussion of cardinality and countable sets,and complexity. The chapters on graph theory include discussions on planarity,traversability,minimal paths,and Warshall's and Huffman's algorithms.We emphasize that the chapters have been written so that the order can be changed without difficulty and without loss of continuity. Each chapter begins with a clear statement of pertinent definitions,principles,and theorems with illustrative and other descriptive material.This is followed by sets of solved and supplementary problems.The solved problems serve to illustrate and amplify the material,and also include proofs of theorems.The supplementary problems furnish a complete review of the material in the chapter.More material has been included than can be covered in most first courses.This has been done to make the book more flexible,to provide a more useful book of reference,and to stimulate further interest in the topics. SEYMOUR LIPSCHUTZ MARC LARS LIPSON Copyright2007,1997,1976 by The McGraw-Hill Companies,Inc.Click here for terms of use
PREFACE Discrete mathematics, the study of finite systems, has become increasingly important as the computer age has advanced. The digital computer is basically a finite structure, and many of its properties can be understood and interpreted within the framework of finite mathematical systems. This book, in presenting the more essential material, may be used as a textbook for a formal course in discrete mathematics or as a supplement to all current texts. The first three chapters cover the standard material on sets, relations, and functions and algorithms. Next come chapters on logic, counting, and probability. We then have three chapters on graph theory: graphs, directed graphs, and binary trees. Finally there are individual chapters on properties of the integers, languages, machines, ordered sets and lattices, and Boolean algebra, and appendices on vectors and matrices, and algebraic systems. The chapter on functions and algorithms includes a discussion of cardinality and countable sets, and complexity. The chapters on graph theory include discussions on planarity, traversability, minimal paths, and Warshall’s and Huffman’s algorithms. We emphasize that the chapters have been written so that the order can be changed without difficulty and without loss of continuity. Each chapter begins with a clear statement of pertinent definitions, principles, and theorems with illustrative and other descriptive material. This is followed by sets of solved and supplementary problems. The solved problems serve to illustrate and amplify the material, and also include proofs of theorems. The supplementary problems furnish a complete review of the material in the chapter. More material has been included than can be covered in most first courses. This has been done to make the book more flexible, to provide a more useful book of reference, and to stimulate further interest in the topics. Seymour Lipschutz Marc Lars Lipson v Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use
For more information about this title,click here CONTENTS CHAPTER 1 Set Theory y 1.1 Introduction 1.2 Sets and Elements,Subsets 1.3 Venn Diagrams 1.4 Set Operations 1.5 Algebra of Sets,Duality > 1.6 Finite Sets,Counting Principle P 1.7 Classes of Sets,Power Sets,Partitions 10 1.8 Mathematical Induction 12 Solved Problems 12 Supplementary Problems 18 CHAPTER 2 Relations 23 2.1 Introduction 2.2 Product Sets 2.3 Relations 2.4 Pictorial Representatives of Relations 2.5 Composition of Relations 2.6 Types of Relations 2.7 Closure Properties 2.8 Equivalence Relations 2.9 Partial Ordering Relations 334357283013460 Solved Problems Supplementary Problems CHAPTER 3 Functions and Algorithms 43 3.1 Introduction 43 3.2 Functions 43 3.3 One-to-One,Onto,and Invertible Functions 3.4 Mathematical Functions,Exponential and Logarithmic Functions 3.5 Sequences,Indexed Classes of Sets 3.6 Recursively Defined Functions 3.7 Cardinality 3.8 Algorithms and Functions 3.9 Complexity of Algorithms Solved Problems 1702567606 Supplementary Problems vii
CONTENTS CHAPTER 1 Set Theory 1 1.1 Introduction 1 1.2 Sets and Elements, Subsets 1 1.3 Venn Diagrams 3 1.4 Set Operations 4 1.5 Algebra of Sets, Duality 7 1.6 Finite Sets, Counting Principle 8 1.7 Classes of Sets, Power Sets, Partitions 10 1.8 Mathematical Induction 12 Solved Problems 12 Supplementary Problems 18 CHAPTER 2 Relations 23 2.1 Introduction 23 2.2 Product Sets 23 2.3 Relations 24 2.4 Pictorial Representatives of Relations 25 2.5 Composition of Relations 27 2.6 Types of Relations 28 2.7 Closure Properties 30 2.8 Equivalence Relations 31 2.9 Partial Ordering Relations 33 Solved Problems 34 Supplementary Problems 40 CHAPTER 3 Functions and Algorithms 43 3.1 Introduction 43 3.2 Functions 43 3.3 One-to-One, Onto, and Invertible Functions 46 3.4 Mathematical Functions, Exponential and Logarithmic Functions 47 3.5 Sequences, Indexed Classes of Sets 50 3.6 Recursively Defined Functions 52 3.7 Cardinality 55 3.8 Algorithms and Functions 56 3.9 Complexity of Algorithms 57 Solved Problems 60 Supplementary Problems 66 vii For more information about this title, click here
viii CONTENTS CHAPTER 4 Logic and Propositional Calculus 70 4.1 Introduction 70 4.2 Propositions and Compound Statements 4.3 Basic Logical Operations 4.4 Propositions and Truth Tables 4.5 Tautologies and Contradictions 4.6 Logical Equivalence 4.7 Algebra of Propositions 4.8 Conditional and Biconditional Statements 4.9 Arguments 4.10 Propositional Functions,Quantifiers 4.11 Negation of Quantified Statements 012445567936 Solved Problems Supplementary Problems CHAPTER 5 Techniques of Counting 88 5.1 Introduction 5.2 Basic Counting Principles 5.3 Mathematical Functions 5.4 Permutations 5.5 Combinations 5.6 The Pigeonhole Principle 5.7 The Inclusion-Exclusion Principle 5.8 Tree Diagrams 88999459 Solved Problems Supplementary Problems 103 CHAPTER 6 Advanced Counting Techniques,Recursion 107 6.1 Introduction 107 6.2 Combinations with Repetitions 107 6.3 Ordered and Unordered Partitions 108 6.4 Inclusion-Exclusion Principle Revisited 108 6.5 Pigeonhole Principle Revisited 110 6.6 Recurrence Relations 111 6.7 Linear Recurrence Relations with Constant Coefficients 113 6.8 Solving Second-Order Homogeneous Linear Recurrence Relations 114 6.9 Solving General Homogeneous Linear Recurrence Relations 116 Solved Problems 118 Supplementary Problems 121 CHAPTER 7 Probability 123 7.1 Introduction 123 7.2 Sample Space and Events 123 7.3 Finite Probability Spaces 126 7.4 Conditional Probability 127 7.5 Independent Events 129 7.6 Independent Repeated Trials,Binomial Distribution 130 7.7 Random Variables 132
viii CONTENTS CHAPTER 4 Logic and Propositional Calculus 70 4.1 Introduction 70 4.2 Propositions and Compound Statements 70 4.3 Basic Logical Operations 71 4.4 Propositions and Truth Tables 72 4.5 Tautologies and Contradictions 74 4.6 Logical Equivalence 74 4.7 Algebra of Propositions 75 4.8 Conditional and Biconditional Statements 75 4.9 Arguments 76 4.10 Propositional Functions, Quantifiers 77 4.11 Negation of Quantified Statements 79 Solved Problems 82 Supplementary Problems 86 CHAPTER 5 Techniques of Counting 88 5.1 Introduction 88 5.2 Basic Counting Principles 88 5.3 Mathematical Functions 89 5.4 Permutations 91 5.5 Combinations 93 5.6 The Pigeonhole Principle 94 5.7 The Inclusion–Exclusion Principle 95 5.8 Tree Diagrams 95 Solved Problems 96 Supplementary Problems 103 CHAPTER 6 Advanced Counting Techniques, Recursion 107 6.1 Introduction 107 6.2 Combinations with Repetitions 107 6.3 Ordered and Unordered Partitions 108 6.4 Inclusion–Exclusion Principle Revisited 108 6.5 Pigeonhole Principle Revisited 110 6.6 Recurrence Relations 111 6.7 Linear Recurrence Relations with Constant Coefficients 113 6.8 Solving Second-Order Homogeneous Linear Recurrence Relations 114 6.9 Solving General Homogeneous Linear Recurrence Relations 116 Solved Problems 118 Supplementary Problems 121 CHAPTER 7 Probability 123 7.1 Introduction 123 7.2 Sample Space and Events 123 7.3 Finite Probability Spaces 126 7.4 Conditional Probability 127 7.5 Independent Events 129 7.6 Independent Repeated Trials, Binomial Distribution 130 7.7 Random Variables 132
CONTENTS ix 7.8 Chebyshev's Inequality,Law of Large Numbers 135 Solved Problems 136 Supplementary Problems 149 CHAPTER 8 Graph Theory 154 8.1 Introduction,Data Structures 154 8.2 Graphs and Multigraphs 156 8.3 Subgraphs,Isomorphic and Homeomorphic Graphs 158 8.4 Paths,Connectivity 159 8.5 Traversable and Eulerian Graphs,Bridges of Konigsberg 160 8.6 Labeled and Weighted Graphs 162 8.7 Complete,Regular,and Bipartite Graphs 162 8.8 Tree Graphs 164 8.9 Planar Graphs 166 8.10 Graph Colorings 168 8.11 Representing Graphs in Computer Memory 171 8.12 Graph Algorithms 173 8.13 Traveling-Salesman Problem 176 Solved Problems 178 Supplementary Problems 191 CHAPTER 9 Directed Graphs 201 9.1 Introduction 201 9.2 Directed Graphs 201 9.3 Basic Definitions 202 9.4 Rooted Trees 204 9.5 Sequential Representation of Directed Graphs 206 9.6 Warshall's Algorithm,Shortest Paths 209 9.7 Linked Representation of Directed Graphs 211 9.8 Graph Algorithms:Depth-First and Breadth-First Searches 213 9.9 Directed Cycle-Free Graphs,Topological Sort 216 9.10 Pruning Algorithm for Shortest Path 218 Solved Problems 221 Supplementary Problems 228 CHAPTER 10 Binary Trees 235 10.1 Introduction 235 10.2 Binary Trees 235 10.3 Complete and Extended Binary Trees 237 10.4 Representing Binary Trees in Memory 239 10.5 Traversing Binary Trees 240 10.6 Binary Search Trees 242 10.7 Priority Queues,Heaps 244 10.8 Path Lengths,Huffman's Algorithm 248 10.9 General(Ordered Rooted)Trees Revisited 251 Solved Problems 252 Supplementary Problems 259
CONTENTS ix 7.8 Chebyshev’s Inequality, Law of Large Numbers 135 Solved Problems 136 Supplementary Problems 149 CHAPTER 8 Graph Theory 154 8.1 Introduction, Data Structures 154 8.2 Graphs and Multigraphs 156 8.3 Subgraphs, Isomorphic and Homeomorphic Graphs 158 8.4 Paths, Connectivity 159 8.5 Traversable and Eulerian Graphs, Bridges of Königsberg 160 8.6 Labeled and Weighted Graphs 162 8.7 Complete, Regular, and Bipartite Graphs 162 8.8 Tree Graphs 164 8.9 Planar Graphs 166 8.10 Graph Colorings 168 8.11 Representing Graphs in Computer Memory 171 8.12 Graph Algorithms 173 8.13 Traveling-Salesman Problem 176 Solved Problems 178 Supplementary Problems 191 CHAPTER 9 Directed Graphs 201 9.1 Introduction 201 9.2 Directed Graphs 201 9.3 Basic Definitions 202 9.4 Rooted Trees 204 9.5 Sequential Representation of Directed Graphs 206 9.6 Warshall’s Algorithm, Shortest Paths 209 9.7 Linked Representation of Directed Graphs 211 9.8 Graph Algorithms: Depth-First and Breadth-First Searches 213 9.9 Directed Cycle-Free Graphs, Topological Sort 216 9.10 Pruning Algorithm for Shortest Path 218 Solved Problems 221 Supplementary Problems 228 CHAPTER 10 Binary Trees 235 10.1 Introduction 235 10.2 Binary Trees 235 10.3 Complete and Extended Binary Trees 237 10.4 Representing Binary Trees in Memory 239 10.5 Traversing Binary Trees 240 10.6 Binary Search Trees 242 10.7 Priority Queues, Heaps 244 10.8 Path Lengths, Huffman’s Algorithm 248 10.9 General (Ordered Rooted) Trees Revisited 251 Solved Problems 252 Supplementary Problems 259
CONTENTS CHAPTER 11 Properties of the Integers 264 11.1 Introduction 264 11.2 Order and Inequalities,Absolute Value 265 11.3 Mathematical Induction 266 11.4 Division Algorithm 267 11.5 Divisibility,Primes 269 11.6 Greatest Common Divisor,Euclidean Algorithm 270 11.7 Fundamental Theorem of Arithmetic 273 11.8 Congruence Relation 274 11.9 Congruence Equations 278 Solved Problems 283 Supplementary Problems 299 CHAPTER 12 Languages,Automata,Grammars 303 12.1 Introduction 303 12.2 Alphabet,Words,Free Semigroup 303 12.3 Languages 304 12.4 Regular Expressions,Regular Languages 305 12.5 Finite State Automata 306 12,6 Grammars 310 Solved Problems 314 Supplementary Problems 319 CHAPTER 13 Finite State Machines and Turing Machines 323 13.1 Introduction 323 13.2 Finite State Machines 323 13.3 Godel Numbers 326 13.4 Turing Machines 326 13.5 Computable Functions 330 Solved Problems 331 Supplementary Problems 334 CHAPTER 14 Ordered Sets and Lattices 337 14.1 Introduction 337 14.2 Ordered Sets 337 14.3 Hasse Diagrams of Partially Ordered Sets 340 14.4 Consistent Enumeration 342 14.5 Supremum and Infimum 342 14.6 Isomorphic (Similar)Ordered Sets 344 14.7 Well-Ordered Sets 344 14.8 Lattices 346 14.9 Bounded Lattices 348 14.10 Distributive Lattices 349 14.11 Complements,Complemented Lattices 350 Solved Problems Supplementary Problems 360
x CONTENTS CHAPTER 11 Properties of the Integers 264 11.1 Introduction 264 11.2 Order and Inequalities, Absolute Value 265 11.3 Mathematical Induction 266 11.4 Division Algorithm 267 11.5 Divisibility, Primes 269 11.6 Greatest Common Divisor, Euclidean Algorithm 270 11.7 Fundamental Theorem of Arithmetic 273 11.8 Congruence Relation 274 11.9 Congruence Equations 278 Solved Problems 283 Supplementary Problems 299 CHAPTER 12 Languages, Automata, Grammars 303 12.1 Introduction 303 12.2 Alphabet, Words, Free Semigroup 303 12.3 Languages 304 12.4 Regular Expressions, Regular Languages 305 12.5 Finite State Automata 306 12.6 Grammars 310 Solved Problems 314 Supplementary Problems 319 CHAPTER 13 Finite State Machines and Turing Machines 323 13.1 Introduction 323 13.2 Finite State Machines 323 13.3 Gödel Numbers 326 13.4 Turing Machines 326 13.5 Computable Functions 330 Solved Problems 331 Supplementary Problems 334 CHAPTER 14 Ordered Sets and Lattices 337 14.1 Introduction 337 14.2 Ordered Sets 337 14.3 Hasse Diagrams of Partially Ordered Sets 340 14.4 Consistent Enumeration 342 14.5 Supremum and Infimum 342 14.6 Isomorphic (Similar) Ordered Sets 344 14.7 Well-Ordered Sets 344 14.8 Lattices 346 14.9 Bounded Lattices 348 14.10 Distributive Lattices 349 14.11 Complements, Complemented Lattices 350 Solved Problems 351 Supplementary Problems 360
CONTENTS xi CHAPTER 15 Boolean Algebra 368 15.1 Introduction 368 15.2 Basic Definitions 368 15.3 Duality 369 15.4 Basic Theorems 370 15.5 Boolean Algebras as Lattices 370 15.6 Representation Theorem 371 15.7 Sum-of-Products Form for Sets 371 15.8 Sum-of-Products Form for Boolean Algebras 372 15.9 Minimal Boolean Expressions,Prime Implicants 375 15.10 Logic Gates and Circuits 377 15.11 Truth Tables,Boolean Functions 381 15.12 Karnaugh Maps 383 Solved Problems 389 Supplementary Problems 403 APPENDIX A Vectors and Matrices 409 A.1 Introduction 409 A.2 Vectors 409 A.3 Matrices 410 A.4 Matrix Addition and Scalar Multiplication 411 A.5 Matrix Multiplication 412 A.6 Transpose 414 A.7 Square Matrices 414 A.8 Invertible (Nonsingular)Matrices,Inverses 415 A.9 Determinants 416 A.10 Elementary Row Operations,Gaussian Elimination (Optional) 418 A.11 Boolean (Zero-One)Matrices 422 Solved Problems 423 Supplementary Problems 429 APPENDIX B Algebraic Systems 432 B.1 Introduction 432 B.2 Operations 432 B.3 Semigroups 435 B.4 Groups 438 B.5 Subgroups,Normal Subgroups,and Homomorphisms 440 B.6 Rings,Internal Domains,and Fields 443 B.7 Polynomials Over a Field 446 Solved Problems 450 Supplementary Problems 461 Index 467
CONTENTS xi CHAPTER 15 Boolean Algebra 368 15.1 Introduction 368 15.2 Basic Definitions 368 15.3 Duality 369 15.4 Basic Theorems 370 15.5 Boolean Algebras as Lattices 370 15.6 Representation Theorem 371 15.7 Sum-of-Products Form for Sets 371 15.8 Sum-of-Products Form for Boolean Algebras 372 15.9 Minimal Boolean Expressions, Prime Implicants 375 15.10 Logic Gates and Circuits 377 15.11 Truth Tables, Boolean Functions 381 15.12 Karnaugh Maps 383 Solved Problems 389 Supplementary Problems 403 APPENDIX A Vectors and Matrices 409 A.1 Introduction 409 A.2 Vectors 409 A.3 Matrices 410 A.4 Matrix Addition and Scalar Multiplication 411 A.5 Matrix Multiplication 412 A.6 Transpose 414 A.7 Square Matrices 414 A.8 Invertible (Nonsingular) Matrices, Inverses 415 A.9 Determinants 416 A.10 Elementary Row Operations, Gaussian Elimination (Optional) 418 A.11 Boolean (Zero-One) Matrices 422 Solved Problems 423 Supplementary Problems 429 APPENDIX B Algebraic Systems 432 B.1 Introduction 432 B.2 Operations 432 B.3 Semigroups 435 B.4 Groups 438 B.5 Subgroups, Normal Subgroups, and Homomorphisms 440 B.6 Rings, Internal Domains, and Fields 443 B.7 Polynomials Over a Field 446 Solved Problems 450 Supplementary Problems 461 Index 467
CHAPTER 1 Set Theory 1.1 INTRODUCTION The concept of a set appears in all mathematics.This chapter introduces the notation and terminology of set theory which is basic and used throughout the text.The chapter closes with the formal definition of mathematical induction,with examples 1.2 SETS AND ELEMENTS.SUBSETS A set may be viewed as any well-defined collection of objects,called the elements or members of the set. One usually uses capital letters,A.B.X.Y.....to denote sets,and lowercase letters,a,b,x,y....,to denote elements of sets.Synonyms for“set”are“class,”“collection,.”and“family." Membership in a set is denoted as follows: a e S denotes that a belongs to a set S a,bS denotes that a and b belong to a set S Here∈is the symbol meaning“is an element of..”We use年to mean“is not an element of..” Specifying Sets There are essentially two ways to specify a particular set.One way,if possible,is to list its members separated by commas and contained in braces {)Asecond way is to state those properties which characterized the elements in the set.Examples illustrating these two ways are: A=(1,3,5,7,9)and B={x Ix is an even integer,x>0) That is.A consists of the numbers 1.3.5.7.9.The second set.which reads: B is the set of x such that x is an even integer and x is greater than 0, denotes the set B whose elements are the positive integers.Note that a letter,usuallyx,is used to denote a typical member of the set;and the vertical line|is read as“such that'”and the comma as“and.” EXAMPLE 1.1 (a)The set A above can also be written as A={xIx is an odd positive integer,x 10). (b)We cannot list all the elements of the above set B although frequently we specify the set by B={2,4,6,} where we assume that everyone knows what we mean.Observe that 8 B,but 3B. Copyright@2007,1997,1976 by The McGraw-Hill Companies,Inc.Click here for terms of use
CHAPTER 1 Set Theory 1.1 INTRODUCTION The concept of a set appears in all mathematics. This chapter introduces the notation and terminology of set theory which is basic and used throughout the text. The chapter closes with the formal definition of mathematical induction, with examples. 1.2 SETS AND ELEMENTS, SUBSETS A set may be viewed as any well-defined collection of objects, called the elements or members of the set. One usually uses capital letters, A, B, X, Y, . . . , to denote sets, and lowercase letters, a, b, x, y, . . ., to denote elements of sets. Synonyms for “set” are “class,” “collection,” and “family.” Membership in a set is denoted as follows: a ∈ S denotes that a belongs to a set S a, b ∈ S denotes that a and b belong to a set S Here ∈ is the symbol meaning “is an element of.” We use ∈ to mean “is not an element of.” Specifying Sets There are essentially two ways to specify a particular set. One way, if possible, is to list its members separated by commas and contained in braces { }. A second way is to state those properties which characterized the elements in the set. Examples illustrating these two ways are: A = {1, 3, 5, 7, 9} and B = {x | x is an even integer, x > 0} That is, A consists of the numbers 1, 3, 5, 7, 9. The second set, which reads: B is the set of x such that x is an even integer and x is greater than 0, denotes the set B whose elements are the positive integers. Note that a letter, usually x, is used to denote a typical member of the set; and the vertical line | is read as “such that” and the comma as “and.” EXAMPLE 1.1 (a) The set A above can also be written as A = {x | x is an odd positive integer, x < 10}. (b) We cannot list all the elements of the above set B although frequently we specify the set by B = {2, 4, 6,...} where we assume that everyone knows what we mean. Observe that 8 ∈ B, but 3 ∈/ B. 1 Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.
2 SET THEORY [CHAP.1 (c)Let E ={xlx2-3x+2=0),F=(2,1)and G=(1,2,2,1).Then E=F=G We emphasize that a set does not depend on the way in which its elements are displayed.A set remains the same if its elements are repeated or rearranged. Even if we can list the elements of a set,it may not be practical to do so.That is,we describe a set by listing its elements only if the set contains a few elements;otherwise we describe a set by the property which characterizes its elements. Subsets Suppose every element in a set A is also an element of a set B,that is,suppose aA implies a B.Then A is called a subset of B.We also say that A is contained in B or that B contains A.This relationship is written A≤BorB2A Two sets are equal if they both have the same elements or,equivalently,if each is contained in the other.That is: A=B if and only if A≤B and B∈A If A is not a subset of B,that is,if at least one element of A does not belong to B,we write A g B. EXAMPLE 1.2 Consider the sets: A={1,3,4,7,8,91,B={1,2,3,4,5,C={1,3} Then CC A and CC B since 1 and 3,the elements of C,are also members of A and B.But B A since some of the elements of B,e.g.,2 and 5,do not belong to A.Similarly,A B. Property 1:It is common practice in mathematics to put a vertical line""or slanted line""through a symbol to indicate the opposite or negative meaning of a symbol. Property 2:The statement A B does not exclude the possibility that A=B.In fact,for every set A we have A C A since,trivially,every element in A belongs to A.However,if A C B and A B,then we say A is a proper subset of B(sometimes written AC B). Property 3:Suppose every element of a set A belongs to a set B and every element of B belongs to a set C. Then clearly every element of A also belongs to C.In other words,if A B and BCC,then A CC. The above remarks yield the following theorem. Theorem 1.1:Let A,B,C be any sets.Then: ①)A≤A (i)IfA≤B and B≤A,then A=B (ii)IfA≤B and B≤C,then A∈C Special symbols Some sets will occur very often in the text,and so we use special symbols for them.Some such symbols are: N=the set of natural numbers or positive integers:1,2,3.... Z=the set of all integers:...,-2,-1,0,1,2,... Q the set of rational numbers R=the set of real numbers C=the set of complex numbers Observe that NCZCQCRC C
2 SET THEORY [CHAP. 1 (c) Let E = {x | x2 − 3x + 2 = 0}, F = {2, 1} and G = {1, 2, 2, 1}. Then E = F = G. We emphasize that a set does not depend on the way in which its elements are displayed. A set remains the same if its elements are repeated or rearranged. Even if we can list the elements of a set, it may not be practical to do so. That is, we describe a set by listing its elements only if the set contains a few elements; otherwise we describe a set by the property which characterizes its elements. Subsets Suppose every element in a set A is also an element of a set B, that is, suppose a ∈ A implies a ∈ B. Then A is called a subset of B. We also say that A is contained in B or that B contains A. This relationship is written A ⊆ B or B ⊇ A Two sets are equal if they both have the same elements or, equivalently, if each is contained in the other. That is: A = B if and only if A ⊆ B and B ⊆ A If A is not a subset of B, that is, if at least one element of A does not belong to B, we write A ⊆ B. EXAMPLE 1.2 Consider the sets: A = {1, 3, 4, 7, 8, 9}, B = {1, 2, 3, 4, 5}, C = {1, 3}. Then C ⊆ A and C ⊆ B since 1 and 3, the elements of C, are also members of A and B. But B ⊆ A since some of the elements of B, e.g., 2 and 5, do not belong to A. Similarly, A ⊆ B. Property 1: It is common practice in mathematics to put a vertical line “|” or slanted line “/” through a symbol to indicate the opposite or negative meaning of a symbol. Property 2: The statement A ⊆ B does not exclude the possibility that A = B. In fact, for every set A we have A ⊆ A since, trivially, every element in A belongs to A. However, if A ⊆ B and A = B, then we say A is a proper subset of B (sometimes written A ⊂ B). Property 3: Suppose every element of a set A belongs to a set B and every element of B belongs to a set C. Then clearly every element of A also belongs to C. In other words, if A ⊆ B and B ⊆ C, then A ⊆ C. The above remarks yield the following theorem. Theorem 1.1: Let A, B, C be any sets. Then: (i) A ⊆ A (ii) If A ⊆ B and B ⊆ A, then A = B (iii) If A ⊆ B and B ⊆ C, then A ⊆ C Special symbols Some sets will occur very often in the text, and so we use special symbols for them. Some such symbols are: N = the set of natural numbers or positive integers: 1, 2, 3,... Z = the set of all integers: ..., −2, −1, 0, 1, 2,... Q = the set of rational numbers R = the set of real numbers C = the set of complex numbers Observe that N ⊆ Z ⊆ Q ⊆ R ⊆ C.
CHAP.1] SET THEORY 3 Universal Set,Empty Set All sets under investigation in any application of set theory are assumed to belong to some fixed large set called the universal set which we denote by ◇ unless otherwise stated or implied. Given a universal set U and a property P,there may not be any elements of U which have property P.For example,the following set has no elements: S=xx is a positive integer,x2=3} Such a set with no elements is called the empty set or null set and is denoted by 分 There is only one empty set.That is,if S and T are both empty,then S=T,since they have exactly the same elements,namely,none. The empty set is also regarded as a subset of every other set.Thus we have the following simple result which we state formally. Theorem 1.2:For any set A,we have 0A C U. Disjoint Sets Two sets A and B are said to be disjoint if they have no elements in common.For example,suppose A={1,2,B={4,5,6,andC={5,6,7,8} Then A and B are disjoint,and A and C are disjoint.But B and C are not disjoint since B and C have elements in common,e.g.,5 and 6.We note that if A and B are disjoint,then neither is a subset of the other (unless one is the empty set). 1.3 VENN DIAGRAMS A Venn diagram is a pictorial representation of sets in which sets are represented by enclosed areas in the plane.The universal set U is represented by the interior of a rectangle,and the other sets are represented by disks lying within the rectangle.If A C B,then the disk representing A will be entirely within the disk representing B as in Fig.1-1(a).If A and B are disjoint,then the disk representing A will be separated from the disk representing B as in Fig.1-1(b). B (a)ACB (b)A and B are disjoint (c) Fig.1-1
CHAP. 1] SET THEORY 3 Universal Set, Empty Set All sets under investigation in any application of set theory are assumed to belong to some fixed large set called the universal set which we denote by U unless otherwise stated or implied. Given a universal set U and a property P, there may not be any elements of U which have property P. For example, the following set has no elements: S = {x | x is a positive integer, x2 = 3} Such a set with no elements is called the empty set or null set and is denoted by ∅ There is only one empty set. That is, if S and T are both empty, then S = T , since they have exactly the same elements, namely, none. The empty set ∅ is also regarded as a subset of every other set. Thus we have the following simple result which we state formally. Theorem 1.2: For any set A, we have ∅ ⊆ A ⊆ U. Disjoint Sets Two sets A and B are said to be disjoint if they have no elements in common. For example, suppose A = {1, 2}, B = {4, 5, 6}, and C = {5, 6, 7, 8} Then A and B are disjoint, and A and C are disjoint. But B and C are not disjoint since B and C have elements in common, e.g., 5 and 6. We note that if A and B are disjoint, then neither is a subset of the other (unless one is the empty set). 1.3 VENN DIAGRAMS A Venn diagram is a pictorial representation of sets in which sets are represented by enclosed areas in the plane. The universal set U is represented by the interior of a rectangle, and the other sets are represented by disks lying within the rectangle. If A ⊆ B, then the disk representing A will be entirely within the disk representing B as in Fig. 1-1(a). If A and B are disjoint, then the disk representing A will be separated from the disk representing B as in Fig. 1-1(b). Fig. 1-1