A First Course in Mathematical Logic and Set Theory E-Book

Michael L. O'Leary

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 750

Veröffentlichungsjahr: 2015

Beschreibung

A mathematical introduction to the theory and applications of logic and set theory with an emphasis on writing proofs

Highlighting the applications and notations of basic mathematical concepts within the framework of logic and set theory, A First Course in Mathematical Logic and Set Theory introduces how logic is used to prepare and structure proofs and solve more complex problems.

The book begins with propositional logic, including two-column proofs and truth table applications, followed by first-order logic, which provides the structure for writing mathematical proofs. Set theory is then introduced and serves as the basis for defining relations, functions, numbers, mathematical induction, ordinals, and cardinals. The book concludes with a primer on basic model theory with applications to abstract algebra. A First Course in Mathematical Logic and Set Theory also includes:

• Section exercises designed to show the interactions between topics and reinforce the presented ideas and concepts
• Numerous examples that illustrate theorems and employ basic concepts such as Euclid’s lemma, the Fibonacci sequence, and unique factorization
• Coverage of important theorems including the well-ordering theorem, completeness theorem, compactness theorem, as well as the theorems of Löwenheim–Skolem, Burali-Forti, Hartogs, Cantor–Schröder–Bernstein, and König

An excellent textbook for students studying the foundations of mathematics and mathematical proofs, A First Course in Mathematical Logic and Set Theory is also appropriate for readers preparing for careers in mathematics education or computer science. In addition, the book is ideal for introductory courses on mathematical logic and/or set theory and appropriate for upper-undergraduate transition courses with rigorous mathematical reasoning involving algebra, number theory, or analysis.

Leseprobe

Table of Contents

COVER

TITLE Page

COPYRIGHT

DEDICATION

PREFACE

ACKNOWLEDGMENTS

LIST OF SYMBOLS

CHAPTER 1: PROPOSITIONAL LOGIC

1.1 SYMBOLIC LOGIC

1.2 INFERENCE

1.3 REPLACEMENT

1.4 PROOF METHODS

1.5 THE THREE PROPERTIES

CHAPTER 2: FIRST-ORDER LOGIC

2.1 LANGUAGES

2.2 SUBSTITUTION

2.3 SYNTACTICS

2.4 PROOF METHODS

CHAPTER 3: SET THEORY

3.1 SETS AND ELEMENTS

3.2 SET OPERATIONS

3.3 SETS WITHIN SETS

3.4 FAMILIES OF SETS

CHAPTER 4: RELATIONS AND FUNCTIONS

4.1 RELATIONS

4.2 EQUIVALENCE RELATIONS

4.3 PARTIAL ORDERS

4.4 FUNCTIONS

4.5 INJECTIONS AND SURJECTIONS

4.6 IMAGES AND INVERSE IMAGES

CHAPTER 5: AXIOMATIC SET THEORY

5.1 AXIOMS

5.2 NATURAL NUMBERS

5.3 INTEGERS AND RATIONAL NUMBERS

5.4 MATHEMATICAL INDUCTION

5.5 STRONG INDUCTION

5.6 REAL NUMBERS

CHAPTER 6: ORDINALS AND CARDINALS

6.1 ORDINAL NUMBERS

6.2 EQUINUMEROSITY

6.3 CARDINAL NUMBERS

6.4 ARITHMETIC

6.5 LARGE CARDINALS

CHAPTER 7: MODELS

7.1 FIRST-ORDER SEMANTICS

7.2 SUBSTRUCTURES

7.3 HOMOMORPHISMS

7.4 THE THREE PROPERTIES REVISITED

7.5 MODELS OF DIFFERENT CARDINALITIES

APPENDIX

REFERENCES

INDEX

End User License Agreement

Pages

xiii

xiv

xvii

xviii

xix

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

435

436

437

438

439

440

441

442

443

Guide

Cover

Table of Contents

Preface

Begin Reading

A FIRST COURSE IN MATHEMATICAL LOGIC AND SET THEORY

Michael L. O'Leary

College of DuPage

Copyright ©2016 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data applied for.

ISBN: 9780470905883

For my parents

PREFACE

This book is inspired by The Structure of Proof: With Logic and Set Theory published by Prentice Hall in 2002. My motivation for that text was to use symbolic logic as a means by which to learn how to write proofs. The purpose of this book is to present mathematical logic and set theory to prepare the reader for more advanced courses that deal with these subjects either directly or indirectly. It does this by starting with propositional logic and first-order logic with sections dedicated to the connection of logic to proof-writing. Building on this, set theory is developed using first-order formulas. Set operations, subsets, equality, and families of sets are covered followed by relations and functions. The axioms of set theory are introduced next, and then sets of numbers are constructed. Finite numbers, such as the natural numbers and the integers, are defined first. All of these numbers are actually sets constructed so that they resemble the numbers that are their namesakes. Then, the infinite ordinal and cardinal numbers appear. The last chapter of the book is an introduction to model theory, which includes applications to abstract algebra and the proofs of the completeness and compactness theorems. The text concludes with a note on Gödel’s incompleteness theorems.

MICHAEL L. O’LEARY

Glen Ellyn, Illinois

July 2015

ACKNOWLEDGMENTS

Thanks are due to Susanne Steitz–Filler, Senior Editor at Wiley, for her support of this project. Thanks are also due to Sari Friedman and Katrina Maceda, both at Wiley, for their work in producing this book. Lastly, I wish to thank the anonymous reviewer whose comments proved beneficial.

On a personal note, I would like to express my gratitude to my parents for their continued caring and support; to my brother and his wife, who will make sure my niece learns her math; to my dissertation advisor, Paul Eklof, who taught me both set theory and model theory; to Robert Meyer, who introduced me to symbol logic; to David Elfman, who taught me about logic through programming on an Apple II; and to my wife, Barb, whose love and patience supported me as I finished this book.

SYMBOLS

Propositions

To study arguments, one must first study sentences because they are the main parts of arguments. However, not just any type of sentence will do. Consider

The purpose of this sentence is to affirm that things called squares also belong to the category of things called rectangles. In this case, the assertion made by the sentence is correct. Also, consider,