Introduction to Set Theory, Third Edition, Revised, and Expanded (Pure and Applied Mathematics (Marcel Dekker))

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
The concept......Page 11
To instructors and lecturers – a moment of your valuable time......Page 12
I’d just like to thank…......Page 13
PART I Study skills for mathematicians......Page 15
Sets......Page 17
Natural numbers......Page 18
The empty set......Page 19
Operations on sets......Page 22
Maps and functions......Page 24
Exercises......Page 26
Summary......Page 27
CHAPTER 2 Reading mathematics......Page 28
Read with pen and paper at hand......Page 29
Identify what is important......Page 30
Read statements first – proofs later......Page 31
Reflect......Page 32
Exercises......Page 33
Summary......Page 34
CHAPTER 3 Writing mathematics I......Page 35
An example......Page 36
Write in sentences......Page 37
Use punctuation......Page 38
Keep it simple......Page 39
Explain what you are doing – keeping the reader informed......Page 40
Explain your assertions......Page 41
Words or symbols?......Page 42
Displaying results with the equals sign......Page 44
Don’t draw arrows everywhere......Page 45
Exercises......Page 46
Summary......Page 48
If you use ‘if’, then use ‘then’......Page 49
Decimal approximations......Page 50
The curse of the implication symbol......Page 51
Define your symbols and notation......Page 52
Use synonyms......Page 53
Summary......Page 54
Sample problems......Page 55
Understand all the words and symbols in the problem......Page 56
Work backwards and forwards......Page 57
Draw a picture......Page 58
Devising a plan......Page 59
Give things names......Page 60
Check the answer......Page 61
Exercises......Page 62
Summary......Page 63
PART II How to think logically......Page 65
Statements......Page 67
An important example......Page 68
Using non-mathematical examples......Page 69
Negation......Page 70
Truth tables......Page 71
Statements using ‘and’......Page 72
Statements using ‘or’......Page 73
Negation of ‘and’ and ‘or’......Page 74
Summary......Page 75
‘If…, then…’ statements......Page 77
Hypothesis, assumption and conclusion......Page 78
False statements can imply true statements......Page 79
‘B if A’ is the same as…......Page 80
Exercises......Page 81
Summary......Page 82
The inverse: a common mistake......Page 83
Necessary conditions......Page 85
The contrapositive......Page 86
Exercises......Page 87
Summary......Page 88
The converse......Page 89
Logical equivalence......Page 90
Another example......Page 91
Exercises......Page 92
Summary......Page 93
For all – the universal quantifier......Page 94
There exists – the existential quantifier......Page 95
Warning! The order of quantifiers is important......Page 96
Summary......Page 97
One quantifier......Page 98
Statements beginning ‘for all’......Page 99
Statements beginning ‘there exists’......Page 100
Negation of quantifiers......Page 101
Exercises......Page 102
Summary......Page 103
CHAPTER 12 Examples and counterexamples......Page 104
Reversing worked examples......Page 105
Counterexamples......Page 106
How to create examples and counterexamples......Page 107
Exercises......Page 108
Summary......Page 109
CHAPTER 13 Summary of logic......Page 110
PART III Definitions, theorems and proofs......Page 111
Definitions......Page 113
Proofs......Page 114
Fermat’s Last Theorem......Page 115
Summary......Page 116
What is a Definition?......Page 117
The ‘if and only if’ nature of mathematical Definitions......Page 118
Find standard examples......Page 119
Find extreme examples......Page 120
Exercises......Page 121
Summary......Page 122
Three theorems......Page 123
Rate the strength of the assumptions and conclusions......Page 124
Compare with earlier theorems......Page 125
Apply to trivial examples and other extreme cases......Page 126
What happens to non-examples?......Page 127
Exercises......Page 128
Summary......Page 129
Why prove statements?......Page 130
Proofs are hard to create – but there is hope......Page 131
Summary......Page 132
A simple theorem and its proof......Page 133
Identify the methods used......Page 134
Draw a picture......Page 135
Look for mistakes – try extreme cases......Page 136
Reflection......Page 137
Exercises......Page 138
Summary......Page 139
Study of the theorem......Page 140
Compare with previous theorems......Page 141
Draw a picture......Page 142
Apply the theorem to non-examples......Page 143
Proof of Pythagoras’ Theorem......Page 144
Check the text......Page 145
What about the converse?......Page 146
Exercises......Page 147
Summary......Page 149
PART IV Techniques of proof......Page 151
Examples of the direct method......Page 153
How to show that an equation holds......Page 156
If and only if proofs......Page 157
Proving that two sets are equal......Page 159
Exercises......Page 160
Summary......Page 161
Don’t assume what had to be proved......Page 163
Square root is a function so it gives a single number......Page 164
Don’t divide by zero…......Page 165
Exercises......Page 167
Summary......Page 168
Examples of cases......Page 169
The modulus function......Page 170
The importance of cases in extreme examples......Page 172
Exercises......Page 173
Summary......Page 174
Simple examples of proof by contradiction......Page 175
The irrationality of the square root of 2......Page 177
How to write a proof by contradiction......Page 178
Summary......Page 179
The Principle of Mathematical Induction......Page 180
Examples of induction......Page 182
Exercises......Page 186
Summary......Page 188
First variant......Page 189
Second variant......Page 190
Third variant......Page 191
Exercises......Page 192
Summary......Page 193
Revision of the contrapositive......Page 194
Don’t confuse contradiction and contrapositive......Page 196
Summary......Page 197
PART V Mathematics that all good mathematicians need......Page 199
Divisibility......Page 201
There exist an infinite number of primes......Page 205
Greatest common divisor......Page 206
A common mistake......Page 207
Summary......Page 208
The Division Lemma......Page 210
More general version of the Division Lemma......Page 213
The Euclidean Algorithm......Page 214
Calculating gcd......Page 215
Euclid’s Lemma......Page 217
Diophantine equations......Page 218
Exercises......Page 220
Summary......Page 221
Modular arithmetic......Page 222
The arithmetic of mod......Page 224
Fermat’s Little Theorem......Page 225
Finding remainders......Page 227
Divisibility tests......Page 228
Exercises......Page 229
Summary......Page 230
Injective functions......Page 232
Surjective functions......Page 234
Composition of functions......Page 235
Inverse functions......Page 236
Problems with trigonometrical notation......Page 237
Types of infinity – countable and uncountable......Page 238
The rationals are countable......Page 239
The reals are uncountable......Page 240
Exercises......Page 241
Summary......Page 242
Relations......Page 244
Equivalence relations......Page 245
A subtlety......Page 246
Equivalence classes......Page 247
Partitions......Page 248
Modular arithmetic......Page 252
Exercises......Page 253
Summary......Page 254
PART VI Closing remarks......Page 255
Play with examples......Page 257
Change the problem......Page 258
Ask ‘What happens if…?’......Page 259
Exercises......Page 260
Summary......Page 261
Weakening the hypotheses......Page 262
Specialization......Page 263
Exercises......Page 264
Summary......Page 265
Understanding theorems......Page 266
Understanding a major topic......Page 267
Summary......Page 268
CHAPTER 35 The biggest secret......Page 269
Summary......Page 270
APPENDIX A Greek alphabet......Page 271
APPENDIX B Commonly used symbols and notation......Page 272
How to prove that two numbers are equal......Page 274
Proving with quantifiers......Page 275
How to prove a map is bijective......Page 276
Index......Page 277