Description

Prove that (Z; #), where a#b = a + b + 1, is a group (i.e. prove that # is associative, that there is an identity element, and that every element has an inverse).hint 1: For proving that the system has an identity element, we can provide an example such as e=0, and then show that it works as an identity elementhint 2: to solve if something is associative, we need to prove that (a∗b)∗c=a∗(b∗c). For this question, there is only one operation, #, so you would start with (a#b)#chint 3: a, b, and c are arbitrary integers here.

62025_10_front endsheet.qxd

4/22/10

11:09 PM

Page 1

Transition to Advanced Mathematics, 7th Edition

Sections and Prerequisites

Chapter 6

Chapter 5

Chapter 7

6.1, 6.2, 6.3, 6.4, 6.5

7.1, 7.2, 7.3, 7.4, 7.5

5.1, 5.2, 5.3, 5.4, 5.5

4.6

4.5

Chapter 4

4.1, 4.2, 4.3, 4.4

3.4

Chapter 3

3.5

3.1, 3.2, 3.3

2.6

Chapter 2

2.1, 2.2, 2.3, 2.4, 2.5

1.7

Chapter 1

1.1, 1.2, 1.3, 1.4, 1.5, 1.6

Preface to

the Student

Core

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page i

A TRANSITION

TO

ADVANCED MATHEMATICS

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page iii

S E V E N T H

E D I T I O N

A TRANSITION

TO

ADVANCED MATHEMATICS

Douglas Smith

University of North Carolina Wilmington

Maurice Eggen

Trinity University

Richard St. Andre

Central Michigan University

Australia • Brazil • Japan • Korea • Mexico • Singapore • Spain • United Kingdom • United States

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page iv

A Transition to Advanced Mathematics,

7th Edition

Douglas Smith, Maurice Eggen, and

Richard St. Andre

Publisher: Richard Stratton

Senior Sponsoring Editor: Molly Taylor

Associate Editor: Daniel Seibert

Editorial Assistant: Shaylin Walsh

Senior Marketing Manager: Jennifer Pursley

Jones

Marketing Communications Manager:

Mary Anne Payumo

Marketing Coordinator: Erica O’Connell

Content Project Manager: Alison Eigel Zade

Art Director: Jill Ort

Text Permissions Account Manager:

Margaret Chamberlain-Gaston

Photo Permissions Account Manager: Don

Schlotman

Senior Print Buyer: Diane Gibbons

Production Service: Elm Street Publishing

Services

Compositor: Integra Software Services, Inc.

© 2011, 2006, 2001 Brooks/Cole, Cengage Learning

ALL RIGHTS RESERVED. No part of this work covered by the

copyright herein may be reproduced, transmitted, stored, or used

in any form or by any means graphic, electronic, or mechanical,

including but not limited to photocopying, recording, scanning,

digitizing, taping, Web distribution, information networks, or

information storage and retrieval systems, except as permitted

under Section 107 or 108 of the 1976 United States Copyright Act,

without the prior written permission of the publisher.

For product information and technology assistance, contact us at

Cengage Learning Customer & Sales Support, 1-800-354-9706

For permission to use material from this text or product,

submit all requests online at www.cengage.com/permissions.

Further permissions questions can be emailed to

permissionrequest@cengage.com.

Library of Congress Control Number: 2009939573

Student Edition:

ISBN-13: 978-0-495-56202-3

ISBN-10: 0-495-56202-5

Brooks/Cole

20 Channel Center Street

Boston, MA 02210

USA

Cengage Learning is a leading provider of customized learning

solutions with ofﬁce locations around the globe, including

Singapore, the United Kingdom, Australia, Mexico, Brazil and Japan.

Locate your local ofﬁce at international.cengage.com/region

Cengage Learning products are represented in Canada by Nelson

Education, Ltd.

For your course and learning solutions, visit

www.cengage.com.

Purchase any of our products at your local college store

or at our preferred online store www.cengagebrain.com.

Printed in the United States of America

1 2 3 4 5 6 7 14 13 12 11 10

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page v

To our wives

Karen, Karen, and Karen

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page vi

C O N T E N T S

Preface viii

Preface to the Student xii

C H A P T E R

C H A P T E R

C H A P T E R

1

Logic and Proofs

1.1

1.2

1.3

1.4

1.5

1.6

1.7

Propositions and Connectives 1

Conditionals and Biconditionals 9

Quantifiers 18

Basic Proof Methods I 27

Basic Proof Methods II 40

Proofs Involving Quantifiers 48

Additional Examples of Proofs 60

2

Set Theory

2.1

2.2

2.3

2.4

2.5

2.6

Basic Concepts of Set Theory 71

Set Operations 79

Extended Set Operations and Indexed Families of Sets 89

Mathematical Induction 100

Equivalent Forms of Induction 114

Principles of Counting 122

3

Relations and Partitions

1

71

135

3.1 Cartesian Products and Relations 135

3.2 Equivalence Relations 147

vi

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page vii

Contents

vii

3.3 Partitions 157

3.4 Ordering Relations 163

3.5 Graphs 174

C H A P T E R

C H A P T E R

C H A P T E R

C H A P T E R

4

Functions

185

4.1

4.2

4.3

4.4

4.5

4.6

Functions as Relations 185

Constructions of Functions 195

Functions That Are Onto; One-to-One Functions 205

One-to-One Correspondences and Inverse Functions 213

Images of Sets 220

Sequences 225

5

Cardinality

5.1

5.2

5.3

5.4

5.5

Equivalent Sets; Finite Sets 233

Infinite Sets 242

Countable Sets 251

The Ordering of Cardinal Numbers 259

Comparability of Cardinal Numbers and the Axiom of Choice 267

6

Concepts of Algebra

6.1

6.2

6.3

6.4

6.5

Algebraic Structures 275

Groups 283

Subgroups 292

Operation Preserving Maps 298

Rings and Fields 306

7

Concepts of Analysis

7.1

7.2

7.3

7.4

7.5

Completeness of the Real Numbers 316

The Heine–Borel Theorem 324

The Bolzano–Weierstrass Theorem 336

The Bounded Monotone Sequence Theorem 341

Equivalents of Completeness 347

233

275

315

Answers to Selected Exercises 353

Index 393

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page viii

P R E F A C E

Excerpts from the Preface to the First Edition

“I understand mathematics but I just can’t do proofs.”

Our experience has led us to believe that the remark above, though contradictory,

expresses the frustration many students feel as they pass from beginning calculus

to a more rigorous level of mathematics. This book developed from a series of

lecture notes for a course at Central Michigan University that was designed to

address this lament. The text is intended to bridge the gap between calculus and

advanced courses in at least three ways. First, it provides a firm foundation in the

major ideas needed for continued work. Second, it guides students to think and to

express themselves mathematically—to analyze a situation, extract pertinent

facts, and draw appropriate conclusions. Finally, we present introductions to

modern algebra and analysis in sufficient depth to capture some of their spirit and

characteristics.

Exercises marked with a solid star (多) have complete answers at the back of the

text. Open stars (夡) indicate that a hint or a partial answer is provided. “Proofs to

Grade” are a special feature of most of the exercise sets. We present a list of claims

with alleged proofs, and the student is asked to assign a letter grade to each “proof”

and to justify the grade assigned. Spurious proofs are usually built around a single

type of error, which may involve a mistake in logic, a common misunderstanding

of the concepts being studied, or an incorrect symbolic argument. Correct proofs

may be straightforward, or they may present novel or alternate approaches. We

have found these exercises valuable because they reemphasize the theorems and

counterexamples in the text and also provide the student with an experience similar

to grading papers. Thus the student becomes aware of the variety of possible errors

and develops the ability to read proofs critically.

In summary, our main goals in this text are to improve the student’s ability to

think and write in a mature mathematical fashion and to provide a solid understanding of the material most useful for advanced courses. Student readers, take comfort

viii

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page ix

Preface

ix

from the fact that we do not aim to turn you into theorem-proving wizards. Few of

you will become research mathematicians. Nevertheless, in almost any mathematically related work you may do, the kind of reasoning you need to be able to do is

the same reasoning you use in proving theorems. You must first understand exactly

what you want to prove (verify, show, or explain), and you must be familiar with the

logical steps that allow you to get from the hypothesis to the conclusion. Moreover,

a proof is the ultimate test of your understanding of the subject matter and of mathematical reasoning.

We are grateful to the many students who endured earlier versions of the manuscript and gleefully pointed out misprints. We acknowledge also the helpful comments of Edwin H. Kaufman, Melvin Nyman, Mary R. Wardrop, and especially

Douglas W. Nance, who saw the need for a course of this kind at CMU and did a

superb job of reviewing the manuscript.

To the Seventh Edition

The seventh edition is based on the same goals and core material as previous editions, but with new organization in several places and many new and revised expositions, examples, and exercises. In the expanded Preface to the Student, we have

gathered together preliminary ideas that should already be familiar to students

(including properties of the number systems, definitions of even, odd and prime

numbers, naive notions of sets, and the basic terminology of functions). This

arrangement makes the prerequisite material easier to locate and keeps the focus of

the text on the use of mathematical reasoning.

The rewritten introduction to concepts of elementary number theory in Section

1.7 is deliberately placed early in the text, before any discussion of inductive proofs

and the Well-Ordering Principle, as an opportunity to practice basic proof methods

on a coherent set of results about divisibility, the greatest common divisor, and linear combinations. Placing this content here (and accepting the Division Algorithm

without proof until inductive proofs are introduced in Chapter 2) allows students to

experience significant results that are achieved with relatively simple proof forms.

Later, students can observe the power of inductive methods to prove the Division

Algorithm and related results.

In Chapter 4 properties of one-to-one and onto functions are now grouped

more efficiently and there is a separate section on one-to-one correspondences and

permutations of a set. In Section 5.3 on countable sets, the major results (that subsets and unions of countably many countable sets are countable) are moved up to

make them more accessible. In Chapter 7, there is even more emphasis on the

meaning of the completeness property of the real number system.

Chapter 1 introduces the propositional and predicate logic required by

mathematical arguments, not as formal logic, but as tools of reasoning for more

complete understanding of concepts (including some ideas of arithmetic, analytic geometry, and calculus with which the student is already familiar). We

present methods of proof and carefully analyze examples of each method, giving

special attention to the use of definitions and denials. The techniques in this

chapter are used and referred to throughout the text. In Chapters 2, 3, and 4 on

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

x

4/22/10

3:12 AM

Page x

Preface

sets, relations, and functions, we emphasize writing and understanding proofs

that require the student to deal precisely with the concepts of set operations,

equivalence relations and partitions, and properties of injective and surjective

functions.

These first four chapters contain the core material of the text and, in addition,

offer the opportunity for further work in several optional sections: basics of number

theory (Section 1.7), combinatorial counting (Section 2.6), order relations and

graph theory (Sections 3.4 and 3.5), and image sets and sequences (Sections 4.5 and

4.6). See the diagram on the inside front cover for a diagram that highlights the core

and shows the prerequisite relationships among sections. For a one-semester

course, we recommend the core material along with any one of Chapters 5, 6, or 7,

or a selection of optional sections and excursions into one or two of the later chapters—for example, Sections 4.6, 5.1, 5.2, 5.3, 7.1, and 7.2.

Chapters 5, 6, and 7 make use of the skills and concepts the student has acquired

in the first four chapters, and thus are a cut above the earlier chapters in terms of level

and rigor. Chapter 5 emphasizes a working knowledge of cardinality: finite and infinite sets, denumerable sets and the uncountability of the real numbers, and properties

of countable sets. We include sections on the ordering of cardinals and applications of

the Cantor–Schröder–Bernstein Theorem and a brief discussion of the Axiom of

Choice. In Chapter 6 we consider properties of algebras with a binary operation,

groups, substructures, and homomorphisms, and relate these concepts to rings and

fields. Chapter 7 considers the completeness property of the real numbers by tracing

its consequences: the Heine–Borel Theorem, the Bolzano–Weierstrass Theorem, and

the Bounded Monotone Sequence Theorem, and back to completeness.

We sincerely thank our reviewers for the seventh edition: David Bayer,

Columbia University; Fernando Burgos, University of South Florida; Yves

Nievergelt, Eastern Washington University; and Don Redmond, Southern Illinois

University.

We also thank our reviewers of earlier editions: Mangho Ahuja, Southeast

Missouri State University; William Ballard, University of Montana; David

Barnette, University of California at Davis; Gerald Beer, California State

University–Los Angeles; Harry Conce, Mankato State University; Sherralyn

Craven, Central Missouri State University; Robert Dean, Stephen F. Austin State

University; Ron Dotzel, University of Missouri; Harvey Elder, Murray State

University; Michael J. Evans, North Carolina State University; Gerald Farrell.

California Polytechnic State University; Benjamin Freed, Clarion University of

Pennsylvania; Robert Gamble, Winthrop College; Dennis Garity, Oregon State

University; Robert P. Hunter, Pennsylvania State University; Jack Johnson,

Brigham Young University–Hawaii; L. Christine Kinsey, Canisuis College; Daniel

Kocan, State University of New York, Potsdam; James McKinney, California

Polytechnic State University; Blair Madore, The State University of New York at

Potsdam; Andrew Martin, Morehead State University; Edward Mosley, Lyon

College; Van C. Nall, University of Richmond; Yves Nievergelt, Eastern

Washington University; Yewande Olubummo, Spelman College; Hoseph H.

Oppenheim, San Francisco State University; John S. Robertson, Georgia College &

State University; Victor Schneider, University of Southwestern Louisiana; Dale

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page xi

Preface

xi

Schoenefeld, University of Tulsa; Kenneth Slonnegar, State University of New

York at Fredonia; Douglas Smith, University of the Pacific; Joseph Teeters,

University of Wisconsin; Mary Treanor, Valparaiso University; and Lawrence

Williams, University of Texas, San Antonio.

We also wish to thank Roger Lipsett for his suggestions after proofreading of

the final manuscript and the staff at Cengage for their exceptional professional

assistance in the development of this edition and previous editions.

Finally, we note that instructors who adopt this text can sign up for online

access to complete solutions for all exercises via Cengage’s Solution Builder service at www.cengage.com/solutionbuilder.

Douglas D. Smith

Richard St. Andre

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page xii

P R E F A C E

T O

T H E

S T U D E N T

Welcome to the study of mathematical reasoning. The authors know that many students approach this material with some apprehension and uncertainty. Some students

feel that “This isn’t like other mathematics courses,” or expect that the study of

proofs is something they won’t really have to do or won’t use later. These feelings

are natural as you move from calculation-oriented courses where the goals emphasize performing computations or solving certain equations, to more advanced

courses where the goal may be to establish whether a mathematical structure has certain properties. This textbook is written to help ease the transition between these

courses. Let’s consider several questions students commonly have at the beginning

of a “transition” course.

Why write proofs?

Mathematicians often collect information and make observations about particular

cases or phenomena in an attempt to form a theory (a model) that describes patterns

or relationships among quantities and structures. This approach to the development

of a theory uses inductive reasoning. However, the characteristic thinking of the

mathematician is deductive reasoning, in which one uses logic to develop and

extend a theory by drawing conclusions based on statements accepted as true.

Proofs are essential in mathematical reasoning because they demonstrate that the

conclusions are true. Generally speaking, a mathematical explanation for a conclusion has no value if the explanation cannot be backed up by an acceptable proof.

Why not just test and repeat enough examples to confirm

a theory?

After all, as is typically done in natural and social sciences, the test for truth of a

theory is that the results of an experiment conform to predictions, and that when

the experiment is repeated under the same circumstances the result is always the

same. The difference is that in mathematics we need to know whether a given

xii

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page xiii

Preface to the Student

xiii

statement is always true, so while the statement may be true for many (even infinitely many) examples, we would never know whether another example might

show the statement to be false. By studying examples, we might conclude that the

statement

“x 2 − 3x + 43 is a prime number”

is true for all positive integers x. We could reach this conclusion testing the first 10

or 20 or even the first 42 integers 1, 2, 3, Á , 42. In each of these cases and others,

such as 44, 45, 47, 48, 49, 50 and more, x 2 − 3x + 43 is a prime number. But the

statement is not always true because 432 − 3(43) + 43 = 1763, which is 41 · 43.

Checking examples is helpful in gaining insight for understanding concepts and

relationships in mathematics, but is not a valid proof technique unless we can

somehow check all examples.

Why not just rely on proofs that someone else has done?

One answer follows from the statement above that deductive reasoning characterizes the way mathematicians think. In the sciences, a new observation may force a

complete rethinking of what was thought to be true; in mathematics what we know

to be true (by proof) is true forever unless there was a flaw in the reasoning. By

learning the techniques of reasoning and proof, you are learning the tools of the

trade.

The first goal of this text is to examine standard proof techniques, especially

concentrating on how to get started on a proof, and how to construct correct proofs

using those techniques. You will discover how the logical form of a statement can

serve as a guide to the structure of a proof of the statement. As you study more

advanced courses, it will become apparent that the material in this book is indeed

fundamental and the knowledge gained will help you succeed in those courses.

Moreover, many of the techniques of reasoning and proof that may seem so difficult at first will become completely natural with practice. In fact, the reasoning that

you will study is the essence of advanced mathematics and the ability to reason

abstractly is a primary reason why applicants trained in mathematics are valuable

to employers.

What am I supposed to know before beginning Chapter 1?

The usual prerequisite for a transition course is at least one semester of calculus. We

will sometimes refer to topics that come from calculus and earlier courses (for

example, differentiable functions or the graph of a parabola), but we won’t be solving equations or finding derivatives.

You will need a good understanding of the basic concepts and notations from

earlier courses. The list of definitions and relationships below includes the main

things you will need to have ready for immediate use at any point in the text.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

xiv

4/22/10

3:12 AM

Page xiv

Preface to the Student

Be aware that definitions in mathematics, however, are not like definitions in ordinary English, which are based on how words are typically used. For example, the ordinary English word “cool” came to mean something good or popular when many people

used it that way, not because it has to have that meaning. If people stop using the word

that way, this meaning of the word will change. Definitions in mathematics have precise, fixed meanings. When we say that an integer is odd, we do not mean that it’s

strange or unusual. Our definition below tells you exactly what odd means. You may

form a concept or a mental image that you may use to help understand (such as “ends

in 1, 3, 5, 7, or 9”), but the mental image you form is not what has been defined. For this

reason, definitions are usually stated with the “if and only if ” connective because they

describe exactly—no more, no less—the condition(s) to meet the definition.

Sets

A set is a collection of objects, called the elements, or members of the set. When

the object x is in the set A, we write x 僆 A; otherwise x 僆 A. The set

K = {6, 7, 8, 9} has four elements; we see that 7 僆 K but 3 僆 K. We may use setbuilder notation to write the set K as

{x: x is an integer greater than 5 and less than 10},

which we read as “the set of x such that x is . . .” Observe that the set whose only

element is 5 is not the same as the number 5; that is, {5} =

5. The empty set ⭋ is

a set with no elements.

We say that A is a subset of B, and write A ⊆ B, if and only if every element of

A is an element of B. If sets A and B have exactly the same elements, we say they

are equal and write A = B.

We use these notations for the number systems:

⺞ = {1, 2, 3, Á} is the set of natural numbers.

⺪ = {Á −3, −2, −1, 0, 1, 2, Á} is the set of integers.

⺡ is the set of all rational numbers.

⺢ is the set of all real numbers.

⺓ is the set of all complex numbers.

A set is finite if it is empty or if it has n elements for some natural number n.

Otherwise it is infinite. Thus the set {6, 7, 8, 9} is finite. All the number systems

listed above are infinite.

The Natural Numbers

The properties below describe the basic arithmetical and ordering structure of the set ⺞.

1.

Successor properties

1 is a natural number.

Every natural number x has a unique successor x + 1.

1 is not the successor of any natural number.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page xv

Preface to the Student

2.

3.

xv

Closure properties

The sum of two natural numbers is a natural number.

The product of two natural numbers is a natural number.

Associativity properties

For all x, y, z 僆 ⺞, x + ( y + z) = (x + y) + z.

For all x, y, z 僆 ⺞, x (yz) = (xy)z.

4.

Commutativity properties

For all x, y 僆 ⺞, x + y = y + x.

For all x, y 僆 ⺞, xy = yx.

5.

Distributivity properties

For all x, y, z 僆 ⺞, x (y + z) = xy + xz.

For all x, y, z 僆 ⺞, ( y + z)x = yx + zx.

6.

Cancellation properties

For all x, y, z 僆 ⺞, if x + z = y + z, then x = y.

For all x, y, z 僆 ⺞, if xz = yz, then x = y.

For natural numbers a and b we say a divides b (or a is a divisor of b, or b is

a multiple of a) if and only if there is a natural number k such that b = ak. For

example, 7 divides 56 because there is a natural number (namely 8) such that

56 = 7 · 8.

A natural number p is prime if and only if p is greater than 1 and the only natural numbers that divide p are 1 and p. A composite is a natural number that is

neither 1 nor prime.

The Fundamental Theorem of Arithmetic:

Every natural number larger than 1 is prime or can be expressed uniquely as a product of primes. For example, 440 can be expressed as 440 = 23 · 5 · 11. If we list the

prime factors in increasing order, then there is only one prime factorization: the

primes and their exponents are uniquely determined.

The Integers

The integers share properties 2 through 6 listed above for ⺞ (with the exception that

we can’t cancel z = 0 from the product xz = yz). Other important properties are:

For all x in ⺪, x + 0 = 0, x · 0 = 0 and x + (−x) = 0.

For all x, y, z in ⺪, if x 0, xy 0 we say a divides b if and only if there is an integer k such that

b = ak.

Real and Rational Numbers

We think of the real numbers as being all the numbers along the number line. Each

real number can be represented as an integer together with a finite or infinite decimal part. We use the standard notations for intervals on the number line. For real

numbers a and b with a 0, such that x = p/q.

The rationals are exactly the numbers along the number line that have terminating or repeating decimal expressions.

√ All other real numbers are irrational. In

Chapter 1 we will see a proof that 2 is irrational. The number systems ⺢ and ⺡

share many of the arithmetic and ordering properties of the naturals and integers,

along with a new property:

Every number x except 0 has a multiplicative inverse; that is, there is a number

y such that xy = 1.

Complex Numbers

A complex

number has the form a + bi, where a and b are real numbers and

√

i = −1. The conjugate of a + bi is a − bi and (a + bi)(a − bi) = a 2 + b 2. The

set of reals is a subset of the complex numbers because any real number x may be written as x + 0i. Complex numbers do not share the ordering properties of the reals.

Functions

A function (or a mapping) is a rule of correspondence that associates to each element in a set A a unique element in a second set B. No restriction is placed on the

sets A and B, which may be sets of numbers, or functions, or vegetables. To denote

that f is a function from A to B, we write

f: A → B

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

4/22/10

3:12 AM

Page xvii

Preface to the Student

xvii

and say “f maps A to B.” If a 僆 A and the corresponding element of B is b, we write

f (a) = b.

The elements of A are sometimes called the arguments or inputs of the function.

If f (a) = b we say that b is the image of a, or b is the value of the function f at a.

We also say that a is a pre-image of b.

For example, f : ⺢ → ⺢ given by f (x) = x 2 + 1 represents the correspondence

that assigns to each real number x the number that is one more than the square of x.

The image of the real number 2 is 5 and −3 is a pre-image of 10.

The features that make f a function from A to B are that every element of A

must have an image, that image must be in B, and most importantly, that no element

of A has more than one image. It is this single-valued property that make functions

so useful.

If f : A → B, the set A is the domain of f, denoted Dom ( f ), and B is the

codomain of f . The set

Rng ( f ) = { f (x): x 僆 A}

of all images under the function f is called the range of f. The range of the function

f : ⺢ → ⺢ given by f (x) = x 2 + 1 is [1, ∞).

It is sometimes convenient to describe a function by giving only a domain and

a rule. For functions whose domains and codomains are subsets of ⺢, the domain is

sometimes left unspecified and assumed to be the largest possible subset of ⺢ for

which image

values may be obtained. With this assumption, the domain of

√

g(x)

√ = x + 1 is [−1, ∞), because this is the largest set of real numbers for which

x + 1 may be calculated.

When we say that f : A → B, it is required that Rng ( f ) ⊆ B. However, it may

be that some elements of the codomain are not images under the function f ; that is,

the set Rng ( f ) may not be equal to B. In the special case when the range of f is

equal to B, we say f maps A onto B. It may also be that two different elements of

A have the same image in B. In the special case when any two different arguments

have different images, we say that f is one-to-one. Because the range of

f (x) = x 2 + 1 is [1, ∞), f is not onto ⺢. Since f (3) and f (−3 ) have value 10, f

is not one-to-one.

What am I allowed to assume for a proof?

You may be given specific instructions for some proof writing exercises, but generally the idea is that you may use what someone studying the topic of your proof

would know. That is, when we prove something about intersecting lines we might

use facts about the slope of a line, but we probably would not use properties of

derivatives. This really is not much of a problem, except for our first proof examples, which deal with elementary concepts such as even and odd (because they provide meaningful examples and a familiar context in which to study logic and

reasoning). For these proofs we are allowed to use the properties of integers and

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_00a_fm_pi-xviii.qxd

xviii

4/22/10

3:12 AM

Page xviii

Preface to the Student

natural numbers that we already know except what we already know about evenness and oddness.

Remember, we don’t expect you to become an expert at proving theorems

overnight. With practice—studying lots of examples and exercises—the skills will

come. Our goal is to help you write and think as mathematicians do, and to present a solid foundation in material that is useful in advanced courses. We hope you

enjoy it.

Douglas D. Smith

Richard St. Andre

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 1

C H A P T E R

1

Logic and Proofs

We recommend that you read the Preface to the Student before beginning this first

chapter. Most of the terms and concepts in that Preface should be familiar to you,

but it is well worth making sure you know the terminology and notations we will

use throughout the book. It is especially important that you know precisely the definitions of such terms as: “divides,” “prime,” “rational,” and “even” and “odd.”

As described in the Preface, mathematics is concerned with the formation of a

theory (collection of true statements) that describes patterns or relationships

among quantities and structures. It is characterized by deductive reasoning, in

which one uses logic to develop and extend a theory by drawing conclusions based

on statements accepted as true. We give proofs to demonstrate that our conclusions

are true. This chapter will provide a working knowledge of the basics of logic and

how to construct a proof.

1.1

Propositions and Connectives

Our goal in this section is to understand truth values of propositions and how propositions can be combined using logical connectives.

Most sentences, such as “π > 3” and “Earth is the closest planet to the sun,”

have a truth value. That is, they are either true or false. We call these sentences

propositions. Other sentences, such as “What time is it?” and “Look out!” are interrogatory or exclamatory; they express complete thoughts but have no truth value.

DEFINITION A proposition is a sentence that has exactly one truth

value: true, which we denote by T, or false, which we denote by F.

Some propositions, such as “72 = 60,” have easily determined truth values. It

will take years to determine the truth value of the proposition “The North Pacific

right whale will be an extinct species before the year 2525.” Other statements, such

1

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

2

CHAPTER 1

4/22/10

1:42 AM

Page 2

Logic and Proofs

as “Euclid was left-handed,” are propositions whose truth values may never be

known.

Sentences like “She lives in New York City” and “x 2 = 36” are not propositions because each could be true or false depending upon the person to whom “she”

refers and what numerical value is assigned to x. We will deal with sentences like

these in Section 1.3.

The statement “This sentence is false” is not a proposition because it is neither

true nor false. It is an example of a paradox—a situation in which, from premises

that look reasonable, one uses apparently acceptable reasoning to derive a conclusion that seems to be contradictory. If the statement “This sentence is false” is true,

then by its meaning it must be false. On the other hand, if the given statement is

false, then what it claims is false, so it must be true. The study of paradoxes such as

this has played a key role in the development of modern mathematical logic. A

famous example of a paradox formulated in 1901 by Bertand Russell* is discussed

in Section 2.1.

By applying logical connectives to propositions, we can form new propositions.

DEFINITION The negation of a proposition P, denoted ∼P, is the

proposition “not P.” The proposition ∼P is true exactly when P is false.

The truth value of the negation of a proposition is the opposite of the truth

value of the proposition. For example, the negation of the false proposition “7 is

divisible by 2” is the true statement “It is not the case that 7 is divisible by 2,” or “7

is not divisible by 2.”

DEFINITIONS Given propositions P and Q, the conjunction of P and

Q, denoted P ∧ Q, is the proposition “P and Q.” P ∧ Q is true exactly

when both P and Q are true.

The disjunction of P and Q, denoted P ∨ Q, is the proposition

“P or Q.” P ∨ Q is true exactly when at least one of P or Q is true.

Examples. If C is the proposition “19 is composite” and M is “45 is a multiple of

3,” we know C is false and M is true. Thus “19 is composite and 45 is a multiple of

3,” written using logical connectives as C ∧ M, is a false proposition, while “19 is

composite or 45 is a multiple of 3,” which has form C ∨ M, is true. The false proposition “Either 19 is composite or 45 is not a multiple of 3” has the form C ∨ ∼M.

The English words but, while, and although are usually translated symbolically

with the conjunction connective, because they have the same meaning as and. For

* Bertrand Russell (1872–1970) was a British philosopher, mathematician, and advocate for social

reform. He was a strong voice for precision and clarity of arguments in mathematics and logic. He coauthored Principia Mathematica (1910–1913), a monumental effort to derive all of mathematics from a

specific set of axioms and well-defined rules of inference.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 3

1.1

Propositions and Connectives

3

example, we would write “19 is not composite, but 45 is a multiple of 3” in symbolic form as: (∼C) ∧ M.

An important distinction must be made between a statement and the form of a

statement. In the previous example “19 is composite and 45 is a multiple of 3” is a

proposition with truth value F. We used the form C ∧ M to represent this proposition, but the form C ∧ M itself has no truth value unless C and M are assigned to be

specific propositions. If we let C be “Copenhagen is the capital of Denmark” and M

be “Madrid is the capital of Spain,” then C ∧ M would have the value T.

To repeat: a propositional form does not have a truth value. Instead, each form

has a list of truth values that depend on the values assigned to its components. This

list is displayed by presenting all possible combinations for the truth values of its

components in a truth table. Since the connectives ∧ and ∨ involve two components,

their truth tables must list the four possible combinations of the truth values of those

components:

P

Q

P∧Q

P

Q

P∨Q

T

F

T

F

T

T

F

F

T

F

F

F

T

F

T

F

T

T

F

F

T

T

T

F

Since the value of ∼P depends only on the two possible values for P, its truth

table is

P

∼P

T

F

F

T

Frequently you will encounter compound propositions formed from more than

two propositional variables. The propositional form (P ∧ Q) ∨ ∼R has three variables P, Q, and R; it follows that there are 23 = 8 possible combinations of truth

values. The two main components are P ∧ Q and ∼R. We make truth tables for

these and combine them by using the truth table for ¡.

P

Q

R

P∧Q

∼R

(P ∧ Q) ∨ ∼R

T

F

T

F

T

F

T

F

T

T

F

F

T

T

F

F

T

T

T

T

F

F

F

F

T

F

F

F

T

F

F

F

F

F

F

F

T

T

T

T

T

F

F

F

T

T

T

T

The statement “Either 7 is prime and 9 is even or else 11 is not less than 3” may

be symbolized by (P ∧ Q) ∨ ∼R, where P is “7 is prime,” Q is “9 is even,” and R

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4

CHAPTER 1

4/22/10

1:42 AM

Page 4

Logic and Proofs

is “11 is less than 3.” We know P is true, Q is false and R is false. Therefore,

(P ∧ Q) is false and ∼R is true. Thus ( P ∧ Q) ∨ ∼R is true, in agreement with line

7 of the table. Thus the proposition “Either 7 is prime and 9 is even or else 11 is not

less than 3” is a true statement.

Some compound forms always yield the value true just because of the way they

are formed; others are always false.

DEFINITIONS A tautology is a propositional form that is true for

every assignment of truth values to its components.

A contradiction is a propositional form that is false for every assignment

of truth values to its components.

For example, the Law of Excluded Middle, P ∨ ∼P, is a tautology because

P ∨ ∼P is true when P is true and true when P is false. We know that a statement

like “The absolute value function is continuous or it is not continuous” must be true

because it has the form of the Law of Excluded Middle.

Example.

Show that (P ∨ Q) ∨ (∼P ∧ ∼Q) is a tautology.

The truth table for this propositional form is

P

Q

P∨Q

∼P

∼Q

∼P ∧ ∼Q

(P ∨ Q) ∨ (∼P ∧ ∼Q )

T

F

T

F

T

T

F

F

T

T

T

F

F

T

F

T

F

F

T

T

F

F

F

T

T

T

T

T

Since the last column is all true, ( P ∨ Q) ∨ (∼P ∧ ∼Q) is a tautology.

Both ∼(P ∨ ∼P) and Q ∧ ∼Q are examples of contradictions. The negation

of a contradiction is, of course, a tautology.

Writing a proof requires the ability to connect statements so that the truth

of any given statement in the proof follows logically from previous statements

in the proof, from known results, or from basic assumptions. Particularly

important is the ability to recognize or write a statement equivalent to another.

Sometimes, it is the form of a compound statement that may be used to find a

useful equivalent.

DEFINITION Two propositional forms are equivalent if and only

if they have the same truth tables.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 5

1.1

Propositions and Connectives

5

Example. The propositional forms P and ∼(∼P) are equivalent. The truth tables

for these forms may be combined in one table to show that they are the same:

P

∼P

∼( ∼P)

T

F

F

T

T

F

The fact that P and ∼(∼P) have the same truth value for each line of the truth

table means that whatever proposition we choose for P, the truth value of P and

∼(∼P) are identical.

Some of the most commonly used equivalent forms are presented in the following theorem.

Theorem 1.1.1

For propositions P, Q, and R, the following are equivalent:

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

P

P∨Q

P∧Q

P ∨ (Q ∨ R)

P ∧ (Q ∧ R)

P ∧ (Q ∨ R)

P ∨ (Q ∧ R)

∼(P ∧ Q)

∼(P ∨ Q)

and

and

and

and

and

and

and

and

and

∼( ∼P)

Q∨P

Q∧P

(P ∨ Q) ∨ R

(P ∧ Q) ∧ R

(P ∧ Q) ∨ (P ∧ R)

(P ∨ Q) ∧ (P ∨ R)

∼P ∨ ∼Q

∼P ∧ ∼Q

Double Negation Law

f

Commutative Laws

f

Associative Laws

f

Distributive Laws

f

DeMorgan’s* Laws

Proof.

(a)

See the discussion above.

(h) By examining the fourth and seventh columns of their combined truth tables

as shown here,

P

Q

P∧Q

∼( P ∧ Q )

∼P

∼Q

∼P ∨ ∼Q

T

F

T

F

T

T

F

F

T

F

F

F

F

T

T

T

F

T

F

T

F

F

T

T

F

T

T

T

we see that the truth tables for ∼(P ∧ Q) and ∼P ∨ ∼Q are identical. Thus

∼(P ∧ Q) and ∼P ∨ ∼Q are equivalent propositional forms.

Proofs of the remaining parts are left as exercises.

䡲

In addition to making tables to verify the remaining parts of Theorem 1.1.1,

you should also think about why two propositional forms are equivalent by looking

* Augustus DeMorgan (1806–1871) was an English logician and mathematician whose contributions

include his notational system for symbolic logic. He also introduced the term “mathematical induction”

(see Section 2.4) and developed a rigorous foundation for that proof technique.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

6

CHAPTER 1

4/22/10

1:42 AM

Page 6

Logic and Proofs

at their meanings. For part (h), negation is applied to a conjunction. The form

∼ ( P ∧ Q) is true precisely when P ∧ Q is false. This happens when one of P or Q

is false, or in other words, when one of ∼P or ∼Q is true. Thus, ∼ ( P ∧ Q) is

equivalent to ∼P ∨ ∼Q. That is, to say “You don’t have both P and Q” is the same

as saying “You don’t have P or you don’t have Q.”

As an example of how this theorem might be useful in dealing with statements,

suppose we are told that the statement “The function f is increasing and concave

upward” is false. The statement has the form P ∧ Q, where P is the statement “f is

increasing” and Q is the statement “f is concave upward.” The negation ∼ ( P ∧ Q)

is “It is not the case that f is increasing and f is concave upward.” By part (h) above,

this is equivalent to ∼P ∨ ∼Q, which is

“It is not the case that f is increasing or it is not the case that f is concave

upward.”

An easier way to say this is

“f is not increasing or f is not concave upward.”

A denial of a proposition P is any proposition equivalent to ∼P. A proposition

has only one negation, ∼P, but always has many denials, including ∼P, ∼∼∼P,

∼∼∼∼∼P, etc. DeMorgan’s Laws provide others ways to construct useful denials.

Example. A denial of “Either Miss Scarlet is not guilty or the crime did not take

place in the ballroom” is “The crime took place in the ballroom and Miss Scarlet is

guilty.” This can be verified by writing the two propositions symbolically as

(∼S) ∨ (∼B) and B ∧ S, respectively, and checking that their truth tables have

exactly opposite values. We could also observe that B ∧ S is equivalent to S ∧ B so

a denial of B ∧ S is equivalent to ∼ ( S ∧ B), which we know by DeMorgan’s Laws

is equivalent to (∼S) ∨ (∼B).

Example. The statement “Line L1 has slope 3/5 or line L2 does not have slope −4”

may be symbolized using the form P ∨ ∼Q, so its negation is ∼(P ∨ ∼Q). We can

write a simpler denial (∼P) ∧ Q by applying DeMorgan’s Laws and the Double

Negation Law. The simplified denial says “Line L1 does not have slope 3/5 and line

L2 has slope −4.”

Notice that someone might read the negation ∼(P ∨ ∼Q) as “It is not the case

that L1 has slope 3/5 or line L2 does not have slope −4.” This sentence is ambiguous because without some further explanation, it is not clear if the phrase “It is not

the case” refers to the entire remainder of the sentence or to just “L1 has slope 3/5.”

Ambiguities like the one above are sometimes allowable in English but can

cause trouble in mathematics. To avoid ambiguities, you should use delimiters,

such as parentheses ( ), square brackets [ ], and braces { }.

To avoid writing large numbers of delimiters, we use the following rules,

which we refer to as the hierarchy of connectives.

First, ∼ always is applied to the smallest proposition following it.

Then, ¿ always connects the smallest propositions surrounding it.

Finally, ¡ connects the smallest propositions surrounding it.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 7

1.1

Propositions and Connectives

7

Thus, ∼P ∨ Q is an abbreviation for (∼P) ∨ Q, but ∼( P ∨ Q) is the only way to

write the negation of P ∨ Q. Here are some other examples:

P ∨ Q ∧ R abbreviates P ∨ ( Q ∧ R).

P ∧ ∼Q ∨ ∼R abbreviates [P ∧ (∼Q)] ∨ (∼R).

∼P ∨ ∼Q abbreviates (∼P) ∨ (∼Q).

∼P ∧ ∼R ∨ ∼P ∧ R abbreviates [(∼P) ∧ (∼R)] ∨ [(∼P) ∧ R].

When the same connective is used several times in succession, parentheses

may be omitted. We reinsert parentheses from the left, so that P ∨ Q ∨ R is really

(P ∨ Q) ∨ R. For example, R ∧ P ∧ ∼P ∧ Q abbreviates [(R ∧ P) ∧ (∼P)] ∧ Q,

whereas R ∨ P ∧ ∼P ∨ Q, which does not use the same connective consecutively,

abbreviates (R ∨ [P ∧ (∼P)]) ∨ Q. Leaving out parentheses is not required;

some propositional forms are much easier to read with a few well-chosen “unnecessary” parentheses.

Exercises 1.1

1. Use your knowledge of number systems to determine whether each is true or

false.

(a) 11 is a rational number.

多 (b) 5π is a rational number.

(c) There are exactly 3 prime numbers between 40 and 50.

(d) There are exactly 5 prime numbers less than 10.

(e) 29 is a composite number.

(f) 0 is a natural number.

多 (g) (5 + 2i )(5 − 2i) is a real number.

(h) 18 is a multiple of 12.

2. Which of the following are propositions? Give the truth value of each proposition.

(a) What time is dinner?

(b) It is not the case that 5 + π is not a rational number.

多 (c) x/2 is a rational number.

(d) 2x + 3y is a real number.

(e) Either 3 + π is rational or 3 − π is rational.

多 (f) Either 2 is rational and π is irrational, or 2π is rational.

(g) Either 5π is rational and 4.9 is rational, or 3π is rational.

(h) −12 is rational, and either 3π 15.

(i) It is not the case that 39 is prime, or that 64 is a power of 2.

(j) There are more than three false statements in this book and this statement is one of them.

3. Make truth tables for each of the following propositional forms.

多 (a) P ∧ ∼P.

(b) P ∨ ∼P.

多 (c) P ∧ ∼Q.

(d) P ∧ (Q ∨ ∼Q).

多 (e) (P ∧ Q) ∨ ∼Q.

(f) ∼(P ∧ Q).

(g) (P ∨ ∼Q) ∧ R.

(h) ∼P ∧ ∼Q.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

8

CHAPTER 1

4/22/10

1:42 AM

Page 8

Logic and Proofs

多 (i) P ∧ (Q ∨ R).

(j) (P ∧ Q) ∨ (P ∧ R).

(k) P ∧ P.

(l) (P ∧ Q) ∨ (R ∧ ∼S).

4. If P, Q, and R are true while S and T are false, which of the following are true?

多 (a) Q ∧ (R ∧ S).

(b) Q ∨ (R ∧ S).

多 (c) (P ∨ Q ) ∧ (R ∨ S).

(d) (∼P ∨ ∼Q) ∨ (∼R ∨ ∼S).

(e) ∼P ∨ ∼Q.

多 (f) (∼Q ∨ S) ∧ (Q ∨ S).

多 (g) (P ∨ S) ∧ (P ∨ T).

5. Use truth tables to prove the remaining parts of Theorem 1.1.1.

6. Which of the following pairs of propositional forms are equivalent?

多 (a) P ∧ P, P.

(b) P ∨ P, P.

多 (c) P ∧ Q, Q ∧ P.

(d) (∼P) ∨ (∼Q), ∼ (P ∨ ∼Q).

多 (e) ∼P ∧ ∼Q, ∼(P ∧ ∼Q).

(f) ∼(P ∧ Q), ∼P ∧ ∼Q.

多 (g) (P ∧ Q ) ∨ R, P ∧ (Q ∨ R).

(h) (P ∧ Q) ∨ R, P ∨ (Q ∧ R).

7. Determine the propositional form and truth value for each of the following:

(a) It is not the case that 2 is odd.

(b) f (x) = e x is increasing and concave up.

(c) Both 7 and 5 are factors of 70.

(d) Perth or Panama City or Pisa is located in Europe.

8. P, Q, and R are propositional forms, and P is equivalent to Q, and Q is equivalent to R. Prove that

多 (a) Q is equivalent to P.

(b) P is equivalent to R.

(c) ∼Q is equivalent to ∼P.

9. Use a truth table to determine whether each of the following is a tautology, a

contradiction, or neither.

(a) (P ∧ Q) ∨ (∼P ∧ ∼Q).

(b) ∼(P ∧ ∼P).

多 (c) (P ∧ Q) ∨ (∼P ∨ ∼Q).

(d) (A ∧ B) ∨ (A ∧ ∼B) ∨ (∼A ∧ B) ∨ (∼A ∧ ∼B).

(e) (Q ∧ ∼P) ∧ ∼ (P ∧ R).

(f) P ∨ [(∼Q ∧ P) ∧ (R ∨ Q)].

10. Suppose A is a tautology and B is a contradiction. Are the following tautologies, contradictions, or neither?

多 (a) A ∧ B.

(b) A ∧ ∼B.

多 (c) A ∨ B.

(d) ∼( ∼A ∧ B).

11. Give a useful denial of each statement.

多 (a) x is a positive integer. (Assume that x is some fixed integer.)

(b) Cleveland will win the first game or the second game.

多 (c) 5 ≥ 3.

(d) 641,371 is a composite integer.

多 (e) Roses are red and violets are blue.

(f) T is not bounded or T is compact. (Assume that T is a fixed object.)

(g) M is odd and one-to-one. (Assume that M is some fixed function.)

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 9

1.2

Conditionals and Biconditionals

9

(h) The function f has positive first and second derivatives at x0. (Assume

that f is a fixed function and x0 is a fixed real number.)

(i) The function g has a relative maximum at x = 2 or x = 4 and a relative

minimum at x = 3. (Assume that g is a fixed function.)

(j) Neither z

∨ , has its uses in English, as in “She will marry Heckle or she

will marry Jeckle.” The “inclusive or” is much more useful in mathematics and is the accepted meaning unless there is a statement to the contrary.

多 (i) Make a truth table for the “exclusive or” connective

∨.

(ii) Show that A

∨ B is equivalent to (A ∨ B) ∧ ∼ (A ∧ B).

(b) “NAND” and “NOR” circuits are commonly used as a basis for flash

memory chips. A NAND B is defined to be the negation of “A and B.” A

NOR B is defined to be the negation of “A or B.”

(i) Write truth tables for NAND and NOR connectives.

(ii) Show that (A NAND B) ∨ (A NOR B) is equivalent to (A NAND B).

(iii) Show that (A NAND B) ∧ (A NOR B) is equivalent to (A NOR B).

1.2

Conditionals and Biconditionals

Sentences of the form “If P, then Q” are the most important kind of propositions in

mathematics. You have seen many examples of such statements in mathematics

courses: from precalculus, “If two lines in a plane have the same slope, then the

lines are parallel”; from trigonometry, “If sec u = 53, then sin u = 45.”; from calculus, “If f is differentiable at x0 and f (x0) is a relative minimum for f, then

f (x0) = 0.”

DEFINITIONS For propositions P and Q, the conditional sentence

P ⇒ Q is the proposition “If P, then Q.” Proposition P is called the

antecedent and Q is the consequent. The conditional sentence P ⇒ Q is

true if and only if P is false or Q is true.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

10

CHAPTER 1

4/22/10

1:42 AM

Page 10

Logic and Proofs

The truth table for P ⇒ Q is

P

Q

P⇒Q

T

F

T

F

T

T

F

F

T

T

F

T

According to this table, there is only one way that P ⇒ Q can be false: when P is

true and Q is false. Thus, this truth table agrees with the way we understand promises: the only situation where a promise is broken is when the antecedent is true but

the person making the promise fails to make the consequent true.

Example. Suppose someone says to a friend “If the concert is sold out, I’ll take you

sailing.” This promise is broken (the conditional sentence is false) only when the

concert was sold out (the antecedent is true) and the person who made the promise

did not take the other person sailing (the consequent is false). This is line 3 of the

truth table. In all other situations, the promise is true. If there were tickets left (lines

2 and 4 of the table), we don’t say the promise was broken, regardless of whether the

friends decided to go sailing. The promise is also kept in the situation where the concert is sold out and the friends went sailing, which is line 1 of the table.

One curious consequence of the truth table for P ⇒ Q is that a conditional sentence may be true even when there is no connection between the antecedent and the

consequent. The reason for this is that the truth value of P ⇒ Q depends only on the

truth value of components P and Q, not on their interpretation. For this reason all of

the following are true:

“If sin π = 1, then 6 is prime.” (line 4 of the truth table)

“13 > 7 ⇒ 2 + 3 = 5.” (line 1 of the truth table)

“π = 3 ⇒ Paris is the capital of France.” (line 2 of the truth table)

and both of these are false by line 3 of the truth table:

“If Saturn has rings, then (2 + 3)2 = 22 + 32.”

“If 4π > 10, then 1 is a prime number.”

Other consequences of the truth table for P ⇒ Q are worth noting. When P is

false, it doesn’t matter what truth value Q has: P ⇒ Q will be true by lines 2 and 4.

When Q is true, it doesn’t matter what truth value P has: P ⇒ Q will be true by lines

1 and 2. Finally, when P and P ⇒ Q are both true (on line 1), Q must also be true.

Example.

Both propositions

“If Isaac Newton was born in 1642, then 3 · 5 = 15”

“If Isaac Newton was born in 1643, then 3 · 5 = 15”

are true because the consequent “3 · 5 = 15” is true.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 11

1.2

Conditionals and Biconditionals

11

Our truth table definition for P ⇒ Q captures the same meaning for “If Á ,

then Á ” that you have always used in mathematics. For example, if we think of x

as some fixed real number, we all know that

“If x > 8, then x > 5”

is a true statement, no matter what number x we have in mind. Let’s examine why

we say this sentence is true for some specific values of x, where the antecedent P is

“x > 8” and the consequent Q is “x > 5.”

In the case x = 11, both P and Q are true, as in line 1 of the truth table. The case

x = 7 corresponds to the second line of the table, and for x = 3 we have the situation in

line 4. There is no case corresponding to line 3 because P ⇒ Q is true. Note that when

we say “If P, then Q” is true, we don’t claim that either P or Q is true. What we do say

is that no matter what number we think of, if it’s larger than 8, it’s also larger than 5.

Two propositions closely related to P ⇒ Q are its converse and contrapositive.

DEFINITION Let P and Q be propositions.

The converse of P ⇒ Q is Q ⇒ P.

The contrapositive of P ⇒ Q is (∼Q ) ⇒ (∼P).

For the conditional sentence “If π is an integer, then 14 is even,” the converse

of the sentence is “If 14 is even, then π is an integer” and the contrapositive is “If

14 is not even, then π is not an integer.” The converse is false, but the sentence and

its contrapositive are true.

√

+ 1 = 2, then 10 > 3,” the converse

For the sentence “If 1√

√ and contrapositive are, respectively, “If 10 > 3, then 1 + 1 = 2 ” and “If 10 is not greater

than 3, then 1 + 1 is not equal to 2.” In this example, all three sentences are true.

The previous two examples suggest that the truth values of a conditional sentence and its contrapositive are related, but there seems to be little connection

between the truth values of P ⇒ Q and its converse. We describe the relationships

in the following theorem.

Theorem 1.2.1

For propositions P and Q,

(a)

(b)

P ⇒ Q is equivalent to its contrapositive (∼Q) ⇒ (∼P).

P ⇒ Q is not equivalent to its converse Q ⇒ P.

Proof. The proofs are carried out by examination of the truth tables.

P

Q

P⇒Q

∼P

∼Q

(∼Q ) ⇒ (∼P )

Q⇒P

T

F

T

F

T

T

F

F

T

T

F

T

F

T

F

T

F

F

T

T

T

T

F

T

T

F

T

T

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

12

CHAPTER 1

4/22/10

1:42 AM

Page 12

Logic and Proofs

(a)

(b)

P ⇒ Q is equivalent to (∼Q) ⇒ (∼P) because the third column in the truth

table is identical to the sixth column in the table.

P ⇒ Q is not equivalent to Q ⇒ P because column 3 in the truth table differs from column 7 in rows 2 and 3.

䡲

We have seen cases where a conditional sentence and its converse have the

same truth value. Theorem 1.2.1(b) simply says that this need not always be the

case—the truth values of P ⇒ Q cannot be inferred from its converse Q ⇒ P.

The next connective we need is the biconditional connective ⇐

⇒. The double

arrow ⇐

⇒ reminds one of both ⇐ and ⇒, and this is no accident, because P ⇐

⇒Q

is equivalent to (P ⇒ Q) ∧ (Q ⇒ P).

DEFINITION For propositions P and Q, the biconditional sentence

P⇐

⇒ Q is the proposition “P if and only if Q.” P ⇐

⇒ Q is true exactly

when P and Q have the same truth values. We also write P iff Q to abbreviate P if and only if Q.

The truth table for P ⇐

⇒ Q is

P

Q

P⇐

⇒Q

T

F

T

F

T

T

F

F

T

F

F

T

Examples. The proposition “23 = 8 iff 49 is a perfect

√ square” is true because both

components are true. The proposition “π = 22/7 iff 2 is a rational number” is true

because both components are false. The proposition “6 + 1 = 7 iff Lake Michigan

is in Kansas” is false because the truth values of the components differ.

Definitions, fully stated with the “if and only if” connective, are important

examples of biconditional sentences because they describe exactly the condition(s)

to meet the definition. Although sometimes a definition does not explicitly use the

iff wording, biconditionality does provide a good test of whether a statement could

serve as a definition or just a description.

Example. The statement “Vertical lines have undefined slope” could be used as a

definition because a line is vertical iff its slope is undefined. However, “A zebra is

a striped animal” is not a definition, because the sentence “An animal is a zebra iff

the animal is striped” is false.

Because the biconditional sentence P ⇐

⇒ Q is true exactly when the truth

values of P and Q agree, we can use the biconditional connective to restate the

meaning of equivalent propositional forms:

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 13

1.2

Conditionals and Biconditionals

13

The propositional forms P and Q are equivalent precisely when P ⇐

⇒ Q is a

tautology.

Thus each statement in Theorem 1.1.1 may be restated using the ⇐

⇒ connective. For example, DeMorgan’s Laws are:

∼( P ∧ Q) ⇐

⇒ (∼P ∨ ∼Q) and

∼( P ∨ Q) ⇐

⇒ (∼P ∧ ∼Q).

All of the statements in Theorem 1.1.1 are used regularly in proofs. The next theorem contains several additional important pairs of equivalent propositional forms

that involve implication. They, too, will be used often.

Theorem 1.2.2

For propositions P, Q, and R,

(a)

(b)

(c)

(d)

(e)

(f)

(g)

P ⇒ Q is equivalent to ∼P ∨ Q.

P⇐

⇒ Q is equivalent to (P ⇒ Q) ∧ (Q ⇒ P).

∼(P ⇒ Q) is equivalent to P ∧ ∼Q.

∼(P ∧ Q) is equivalent to P ⇒ ∼Q and to Q ⇒ ∼P.

P ⇒ (Q ⇒ R) is equivalent to (P ∧ Q) ⇒ R.

P ⇒ (Q ∧ R) is equivalent to (P ⇒ Q) ∧ ( P ⇒ R).

(P ∨ Q) ⇒ R is equivalent to (P ⇒ R) ∧ (Q ⇒ R).

Exercise 8 asks you to prove each part of Theorem 1.2.2. The natural way to

proceed is by constructing and then comparing truth tables, but you should also

think about the meaning of both sides of each statement of equivalence. With part

(a), for example, we reason as follows: P ⇒ Q is false exactly when P is true and

Q is false, which happens exactly when both ∼P and Q are false. Since this happens

exactly when ∼P ∨ Q is false, the truth tables for P ⇒ Q and ∼P ∨ Q are identical.

Note that many of the statements in Theorems 1.1.1 and 1.2.2 are related. For

example, once we have established Theorem 1.1.1 and 1.2.2(a), we reason that part

(c) is correct as follows:

∼(P ⇒ Q) is equivalent, by part (a), to

∼ (∼P ∨ Q), which is equivalent, by Theorem 1.1.1(i), to

∼ (∼P) ∧ ∼Q, which is equivalent, by Theorem 1.1.1(a), to

P ∧ ∼Q.

Recognizing the structure of a sentence and translating the sentence into symbolic form using logical connectives are aids in determining its truth or falsity. The

translation of sentences into propositional symbols is sometimes very complicated

because some natural languages such as English are rich and powerful with many

nuances. The ambiguities that we tolerate in English would destroy structure and

usefulness if we allowed them in mathematics.

Even the translations of simple sentences can present special problems. Suppose a teacher says to a student

“If you score 74% or higher on the next test, you will pass this course.”

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

14

CHAPTER 1

4/22/10

1:42 AM

Page 14

Logic and Proofs

This sentence clearly has the form of a conditional sentence, although almost everyone will interpret the meaning as a biconditional.

Contrast this with the situation in mathematics where “If x = 2, then x is a

solution to x 2 = 2x” must have only the meaning of the connective ⇒, because

x 2 = 2x does not imply x = 2.

Shown below are some phrases in English that are ordinarily translated by

⇒. In the accompanying examples, think of a and t as

using the connectives ⇒ or ⇐

fixed real numbers.

Use P ⇒ Q to translate:

Examples:

If P, then Q.

P implies Q.

P is sufficient for Q.

P only if Q.

Q, if P.

Q whenever P.

Q is necessary for P.

Q, when P.

If a > 5, then a > 3.

a > 5 implies a > 3.

a > 5 is sufficient for a > 3.

a > 5 only if a > 3.

a > 3, if a > 5.

a > 3 whenever a > 5.

a > 3 is necessary for a > 5.

a > 3, when a > 5.

⇒ Q to translate:

Use P ⇐

Examples:

P if and only if Q.

P if, but only if, Q.

P is equivalent to Q.

P is necessary and sufficient for Q.

|t |

|t|

|t|

|t|

= 2 if and only if t2 = 4.

= 2 if, but only if, t 2 = 4.

= 2 is equivalent to t 2 = 4.

= 2 is necessary and sufficient

for t 2 = 4.

The word unless is one of those connective words in English that poses special

problems because it has so many different interpretations. See Exercise 11.

Examples. In these sentence translations, we assume that S, G, and e have been

specified. It is not necessary to know the meanings of all the words because the

form of the sentence is sufficient to determine the correct translation.

“S is compact is sufficient for S to be bounded” is translated

S is compact ⇒ S is bounded.

“A necessary condition for a group G to be cyclic is that G is abelian” is

translated

G is cyclic ⇒ G is abelian.

“A set S is infinite if S has an uncountable subset” is translated

S has an uncountable subset ⇒ S is infinite.

“A necessary and sufficient condition for the graph G to be a tree is that

G is connected and every edge of G is a bridge” is translated

⇒ (G is connected ¿ every edge of G is a bridge).

G is a tree ⇐

Example. If we let P denote the proposition “Roses are red” and Q denote the

proposition “Violets are blue,” we can translate the sentence “It is not the case that

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 15

1.2

Conditionals and Biconditionals

15

roses are red, nor that violets are blue” in at least two ways: ∼(P ∨ Q) or

(∼P) ∧ (∼Q). Fortunately, these are equivalent by Theorem 1.1.1(h). Note that the

proposition “Violets are purple” requires a new symbol, say R, since it expresses a

new idea that cannot be formed from the components P and Q.

The sentence “17 and 35 have no common divisors” shows that the meaning,

and not just the form of the sentence, must be considered in translating; it cannot be

broken up into the two propositions: “17 has no common divisors” and “35 has no

common divisors.” Compare this with the proposition “17 and 35 have digits totaling 8,” which can be written as a conjunction.

Example. Suppose b is a fixed real number. The form of the sentence “If b is an

integer, then b is either even or odd” is P ⇒ (Q ∨ R), where P is “b is an integer,”

Q is “b is even,” and R is “b is odd.”

Example. Suppose a, b, and p are fixed integers. “If p is a prime number that

divides ab, then p divides a or b” has the form (P ∧ Q) ⇒ (R ∨ S), where P is “p

is a prime,” Q is “p divides ab,” R is “p divides a,” and S is “p divides b.”

The hierarchy of connectives in Section 1.1 that governs the use of parentheses

for propositional forms can be extended to the connectives ⇒ and ⇐

⇒:

The connectives ∼, ∧, ∨, ⇒, and ⇐

⇒ are always applied in the order listed.

Thus, ∼ applies to the smallest possible proposition, then ¿ is applied with the next

smallest scope, and so forth. For example,

P ⇒ ∼Q ∨ R ⇐

⇒ S is an abbreviation for (P ⇒ [(∼Q ) ∨ R]) ⇐

⇒ S,

P ∨ ∼Q ⇐

⇒ R ⇒ S is an abbreviation for [P ∨ (∼Q)] ⇐

⇒ (R ⇒ S),

and

P ⇒ Q ⇒ R is an abbreviation for (P ⇒ Q) ⇒ R.

Exercises 1.2

1. Identify the antecedent and the consequent for each of the following conditional sentences. Assume that a, b, and f represent some fixed sequence,

integer, or function, respectively.

多 (a) If squares have three sides, then triangles have four sides.

(b) If the moon is made of cheese, then 8 is an irrational number.

(c) b divides 3 only if b divides 9.

多 (d) The differentiability of f is sufficient for f to be continuous.

(e) A sequence a is bounded whenever a is convergent.

多 (f) A function f is bounded if f is integrable.

(g) 1 + 2 = 3 is necessary for 1 + 1 = 2.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

16

CHAPTER 1

4/22/10

1:42 AM

Page 16

Logic and Proofs

夡

(h) The fish bite only when the moon is full.

多 (i) A time of 3 minutes, 48 seconds or less is necessary to qualify for the

Olympic team.

2. Write the converse and contrapositive of each conditional sentence in Exercise 1.

3. What can be said about the truth value of Q when

(a) P is false and P ⇒ Q is true? (b) P is true and P ⇒ Q is true?

⇒ Q is true?

(c) P is true and P ⇒ Q is false? (d) P is false and P ⇐

⇒ Q is false?

(e) P is true and P ⇐

4. Identify the antecedent and consequent for each conditional sentence in the

following statements from this book.

(a) Theorem 1.3.1(a)

(b) Exercise 3 of Section 1.6

(c) Theorem 2.1.4

(d) The PMI, Section 2.4

(e) Theorem 2.6.4

(f) Theorem 3.4.2

(g) Theorem 4.2.2

(h) Theorem 5.1.7(a)

5. Which of the following conditional sentences are true?

多 (a) If triangles have three sides, then squares have four sides.

(b) If a hexagon has six sides, then the moon is made of cheese.

多 (c) If 7 + 6 = 14, then 5 + 5 = 10.

(d) If 5 6.

6. Which of the following are true?

多 (a) Triangles have three sides iff squares have four sides.

(b) 7 + 5 = 12 iff 1 + 1 = 2.

多 (c) b is even iff b + 1 is odd. (Assume that b is some fixed integer.)

(d) m is odd iff m2 is odd. (Assume that m is some fixed integer.)

(e) 5 + 6 = 6 + 5 iff 7 + 1 = 10.

(f) A parallelogram has three sides iff 27 is prime.

(g) The Eiffel Tower is in Paris if and only if the chemical symbol for

helium

is√H.

√

√

√

√

√

√

√

10 + 13 (x0) = 0.

(b) If n is prime, then n = 2 or n is odd.

(c) A number x is real and not rational whenever x is irrational.

多 (d) If x = 1 or x = −1, then |x| = 1.

多 (e) f has a critical point at x0 iff f (x0 ) = 0 or f (x0 ) does not exist.

(f) S is compact iff S is closed and bounded.

(g) B is invertible is a necessary and sufficient condition for det B = 0.

(h) 6 ≥ n − 3 only if n > 4 or n > 10.

(i) x is Cauchy implies x is convergent.

(j) f is continuous at x0 whenever lim f (x) = f ( x0).

x→x0

11.

多

12.

多

13.

多

多

14.

(k) If f is differentiable at x0 and f is strictly increasing at x0, then f (x0) > 0.

Dictionaries indicate that the conditional meaning of unless is preferred, but

there are other interpretations as a converse or a biconditional. Discuss the

translation of each sentence.

(a) I will go to the store unless it is raining.

(b) The Dolphins will not make the playoffs unless the Bears win all the rest

of their games.

(c) You cannot go to the game unless you do your homework first.

(d) You won’t win the lottery unless you buy a ticket.

Show that the following pairs of statements are equivalent.

(a) (P ∨ Q) ⇒ R and ∼R ⇒ (∼P ∧ ∼Q).

(b) (P ∧ Q) ⇒ R and (P ∧ ∼R) ⇒ ∼Q.

(c) P ⇒ (Q ∧ R) and (∼Q ∨ ∼R) ⇒ ∼P.

(d) P ⇒ (Q ∨ R) and ( P ∧ ∼R) ⇒ Q.

(e) (P ⇒ Q) ⇒ R and (P ∧ ∼Q) ∨ R.

⇒ Q and (∼P ∨ Q) ∧ (∼Q ∨ P).

(f) P ⇐

Give, if possible, an example of a true conditional sentence for which

(a) the converse is true.

(b) the converse is false.

(c) the contrapositive is false.

(d) the contrapositive is true.

Give, if possible, an example of a false conditional sentence for which

(a) the converse is true.

(b) the converse is false.

(c) the contrapositive is false.

(d) the contrapositive is true.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

18

CHAPTER 1

4/22/10

1:42 AM

Page 18

Logic and Proofs

15. Give the converse and contrapositive of each sentence of Exercises 10(a), (b),

(c), and (d). Tell whether each converse and contrapositive is true or false.

16. Determine whether each of the following is a tautology, a contradiction, or neither.

多 (a) [(P ⇒ Q) ⇒ P] ⇒ P.

⇒ P ∧ (P ∨ Q).

(b) P ⇐

⇒ P ∧ ∼Q.

(c) P ⇒ Q ⇐

多 (d) P ⇒ [P ⇒ ( P ⇒ Q)].

⇒ P.

(e) P ∧ (Q ∨ ∼Q) ⇐

(f) [Q ∧ (P ⇒ Q)] ⇒ P.

⇒ Q) ⇐

⇒ ∼(∼P ∨ Q) ∨ (∼P ∧ Q).

(g) (P ⇐

(h) [P ⇒ (Q ∨ R)] ⇒ [(Q ⇒ R) ∨ (R ⇒ P)].

⇒ Q) ∧ ∼Q.

(i) P ∧ (P ⇐

(j) (P ∨ Q) ⇒ Q ⇒ P.

(k) [P ⇒ (Q ∧ R)] ⇒ [R ⇒ ( P ⇒ Q)].

(l) [P ⇒ (Q ∧ R)] ⇒ R ⇒ (P ⇒ Q).

17. The inverse, or opposite, of the conditional sentence P ⇒ Q is ∼P ⇒ ∼Q.

(a) Show that P ⇒ Q and its inverse are not equivalent forms.

(b) For what values of the propositions P and Q are P ⇒ Q and its inverse

both true?

(c) Which is equivalent to the converse of a conditional sentence, the contrapositive of its inverse, or the inverse of its contrapositive?

1.3

Quantifiers

Unless there has been a prior agreement about the value of x, the statement “x ≥ 3” is

neither true nor false. A sentence that contains variables is called an open sentence or

predicate, and becomes a proposition only when its variables are assigned specific values. For example, “x ≥ 3” is true when x is given the value 7 and false when x = 2.

When P is an open sentence with a variable x, the sentence is symbolized by

P(x). Likewise, if P has variables x1, x2, x3, Á , xn, the sentence may be denoted by

P(x1, x2, x3, Á , xn). For example, for the sentence “x + y = 3z” we write P(x, y, z),

and we see that P(4, 5, 3) is true because 4 + 5 = 3(3), while P(1, 2, 4) is false.

The collection of objects that may be substituted to make an open sentence a

true proposition is called the truth set of the sentence. Before a truth set can be

determined, we must be given or must decide what objects are available for consideration; that is, we must have specified a universe of discourse. In many cases the

universe will be understood from the context. For a sentence such as “x likes chocolate,” the universe is presumably the set of all people. We will often use the number

systems ⺞, ⺪, ⺡, ⺢, and ⺓ as our universes. (See the Preface to the Student.)

Example. The truth set of the open sentence “x2 3.” To decide the truth value of the given

sentence in the universe ⺞ it is not enough to observe that 32 > 3, 42 > 3, and so

on. In fact, the sentence is false in ⺞ because 1 is in the universe but not in the truth

set. The sentence is true, however, in the universe [1.74, ∞ ) because with this universe the truth set for x2 > 3 is the same as the universe.

DEFINITION For an open sentence P( x), the sentence (∀x) P (x) is read

“For all x, P (x)” and is true iff the truth set of P(x) is the entire universe.

The symbol ∀ is called the universal quantifier.

Examples. For the universe of all real numbers,

(∀x)(x + 2 > x) is true.

(∀x)(x > 0 ∨ x = 0 ∨ x 0) is false, because 0 is not in the truth set.

There are many ways to express a quantified sentence in English. Look for key

words such as “for all,” “for every,” “for each,” or similar words that require universal quantifiers. Look for phrases such as “some,” “at least one,” “there exist(s),”

“there is (are),” and others that indicate existential quantifiers.

You should also be alert for hidden quantifiers because natural languages allow for

imprecise quantified statements where the words “for all” and “there exists” are not

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 21

1.3 Quantifiers

21

present. Someone who says “Polynomial functions are continuous” means that “All

polynomial functions are continuous,” but someone who says “Rational functions have

vertical asymptotes” must mean “Some rational functions have vertical asymptotes.”

We agree that “All apples have spots” is quantified with ∀, but what form does

it have? If we limit the universe to just apples, a correct symbolization would be

(∀x)(x has spots). But if the universe is all fruits, we need to be more careful. Let

A(x) be “x is an apple” and S(x) be “x has spots.” Should we write the sentence as

(∀x)[A(x) ∧ S( x)] or (∀x)[A(x) ⇒ S( x)]?

The first quantified form, (∀x)[A( x) ∧ S(x)], says “For all objects x in the universe, x is an apple and x has spots.” Since we don’t really intend to say that all fruits are

spotted apples, this is not the meaning we want. Our other choice, ( ∀x)[A(x) ⇒ S(x)],

is the correct one because it says “For all objects x in the universe, if x is an apple then

x has spots.” In other words, “If a fruit is an apple, then it has spots.”

Now consider “Some apples have spots.” Should this be (Ex)[A(x) ∧ S( x)] or

(Ex)[A(x) ⇒ S(x)]? The first form says “There is an object x such that it is an apple

and it has spots,” which is correct. On the other hand, (Ex)[A( x) ⇒ S(x)] reads

“There is an object x such that, if it is an apple, then it has spots,” which does not

ensure the existence of apples with spots. The sentence (Ex)[A( x) ⇒ S( x)] is true

in every universe for which there is an object x such that either x is not an apple or

x has spots, which is not the meaning we want.

In general, a sentence of the form “All P (x) are Q (x)” should be symbolized

( ∀x)[P(x) ⇒ Q( x)]. And, in general, a sentence of the form “Some P (x) are Q (x)”

should be symbolized ( Ex)[P(x) ∧ Q( x)].

Examples. The sentence “For every odd prime x less than 10, x 2 + 4 is prime”

means that if x is prime, and odd, and less than 10, then x 2 + 4 is prime. It is written symbolically as

(∀x)(x is prime ∧ x is odd ∧ x x)]

or

(∀x 僆 ⺡)(Ez 僆 ⺪)(z > x).

DEFINITION Two quantified sentences are equivalent in a given

universe iff they have the same truth value in that universe. Two quantified sentences are equivalent iff they are equivalent in every universe.

Example. (∀x)(x > 3) and ( ∀x)(x ≥ 4) are equivalent in the universe of integers

(because both are false), the universe of natural numbers greater than 10 (because

both are true), and in many other universes. However, if we chose a number

between 3 and 4, say 3.7, and let U be the universe of real numbers larger than 3.7,

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 23

1.3 Quantifiers

23

then (∀x)(x > 3) is true and ( ∀x)(x ≥ 4) is false in U. The sentences are not equivalent in this universe, so they are not equivalent sentences.

As was noted with propositional forms, it is necessary to make a distinction

between a quantified sentence and its logical form. With the universe all integers, the sentence “All integers are odd” is an instance of the logical form

(∀x) P (x), where P( x) is “x is odd.” The form itself, (∀x) P (x), is neither true nor

false, but becomes false when “x is odd” is substituted for P( x) and the universe

is all integers.

The pair of quantified forms (Ex)([P(x) ∧ Q( x)] and ( Ex)([Q( x) ∧ P(x)] are

equivalent because for any choices of P and Q, P ∧ Q and Q ∧ P are equivalent

propositional forms. Another pair of equivalent sentences is (∀x)[P(x) ⇒ Q(x)]

and (∀x)[∼Q(x) ⇒ ∼P(x)].

The next two equivalences are essential for reasoning about quantifiers.

Theorem 1.3.1

If A(x) is an open sentence with variable x, then

(a)

(b)

∼(∀x) A (x) is equivalent to ( Ex) ∼A(x).

∼(Ex) A (x) is equivalent to (∀x) ∼A(x).

Proof.

(a)

Let U be any universe.

The sentence ∼(∀x) A (x) is true in U

iff (∀x) A (x) is false in U

iff the truth set of A(x) is not the universe

iff the truth set of ∼ A(x) is nonempty

iff (Ex) ∼A(x) is true in U.

(b)

The proof of this part is Exercise 7.

䡲

Theorem 1.3.1 is helpful for finding useful denials (that is, simplified forms of

negations) of quantified sentences. For example, in the universe of natural numbers,

the sentence “All primes are odd” is symbolized (∀x)(x is prime ⇒ x is odd). The

negation is ∼(∀x)(x is prime ⇒ x is odd). By applying Theorem 1.3.1(a), this

becomes (Ex)[∼(x is prime ⇒ x is odd)]. By Theorem 1.2.2(c) this is equivalent to

(Ex)[x is prime ∧ ∼(x is odd)]. We read this last statement as “There exists a number that is prime and is not odd” or “Some prime number is even.”

Example. A simplified denial of (∀x)(Ey)(Ez)(∀u)(Ev)(x + y + z > 2u + v)

begins with its negation

‘ (∀x)(Ey)(Ez)(∀u)(Ev)(x + y + z > 2u + v).

After 5 applications of Theorem 1.3.1, beginning with the outermost quantifier

(∀x), we arrive at the simplified form

(E x)(∀y)(∀z)(Eu)(∀v)(x + y + z ≤ 2u + v).

Example. For the universe of all real numbers, find a denial of “Every positive

real number has a multiplicative inverse.”

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

24

CHAPTER 1

4/22/10

1:42 AM

Page 24

Logic and Proofs

The sentence is symbolized (∀x)[x > 0 ⇒ (Ey)(xy = 1)]. The negation and

successively rewritten equivalents are:

∼( ∀x)[x > 0 ⇒ (Ey)(xy = 1)]

(Ex) ∼[x > 0 ⇒ (Ey)(xy = 1)]

(Ex)[x > 0 ∧ ∼ (Ey)(xy = 1)]

(Ex)[x > 0 ∧ (∀y) ∼(xy = 1)]

(Ex)[x > 0 ∧ (∀y)(xy = 1)]

This last sentence may be translated as “There is a positive real number that has no

multiplicative inverse.”

Example. For the universe of living things, find a denial of “Some children do not

like clowns.”

The sentence is (Ex) [x is a child ∧ (∀y) (y is a clown ⇒ x does not like y)]. Its

negation and several equivalents are:

∼ (Ex) [x is a child ∧ (∀y)(y is a clown ⇒ x does not like y)]

(∀x) ∼ [x is a child ∧ (∀y)(y is a clown ⇒ x does not like y)]

(∀x) [x is a child ⇒ ∼(∀y)(y is a clown ⇒ x does not like y)]

(∀x) [x is a child ⇒ (Ey) ∼( y is a clown ⇒ x does not like y)]

(∀x) [x is a child ⇒ (Ey)(y is a clown ∧ ∼ x does not like y)]

(∀x) [x is a child ⇒ (Ey)(y is a clown ∧ x likes y)]

The denial we seek is “Every child has some clown that he/she likes.”

We sometimes hear statements like the complaint one fan had after a great Little

League baseball game. “The game was fine,” he said, “but everybody didn’t get to

play.” We easily understand that the fan did not mean this literally, because otherwise

there would have been no game. The meaning we understand is “Not everyone got to

play” or “Some team members did not play.” Such misuse of quantifiers, while tolerated in casual conversations, is always to be avoided in mathematics.

The E! quantifier, defined next, is a special case of the existential quantifier.

DEFINITION For an open sentence P (x), the proposition ( E!x) P (x) is

read “there exists a unique x such that P(x)” and is true iff the truth set

of P (x) has exactly one element. The symbol E! is called the unique existential quantifier.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

4/22/10

1:42 AM

Page 25

1.3 Quantifiers

25

Recall that for (E x) P (x) to be true it is unimportant how many elements are in

the truth set of P(x), as long as there is at least one. For (E!x) P (x) to be true, the

number of elements in the truth set of P(x) is crucial—there must be exactly one.

In the universe of natural numbers, (E!x) (x is even and x is prime) is true

because the truth set of “x is even and x is prime” contains only the number 2. The

sentence (E!x)(x 2 = 4) is true in the universe of natural numbers, but false in the

universe of all integers.

Theorem 1.3.2

If A(x) is an open sentence with variable x, then

(a)

(b)

(E!x) A(x) ⇒ (Ex) A(x).

(E!x) A(x) is equivalent to (Ex) A(x) ∧ ( ∀y)(∀z)(A( y) ∧ A(z) ⇒ y = z).

Part (a) of Theorem 1.3.2 says that E! is indeed a special case of the quantifier

E . Part (b) says that “There exists a unique x such that A(x)” is equivalent to “There

is an x such that A(x) and if both A( y) and A(z), then y = z.” The proofs are left to

Exercise 11.

Exercises 1.3

夡

1. Translate the following English sentences into symbolic sentences with quantifiers. The universe for each is given in parentheses.

多 (a) Not all precious stones are beautiful. (All stones)

夡

(b) All precious stones are not beautiful. (All stones)

(c) Some isosceles triangle is a right triangle. (All triangles)

(d) No right triangle is isosceles. (All triangles)

(e) All people are honest or no one is honest. (All people)

(f) Some people are honest and some people are not honest. (All people)

(g) Every nonzero real number is positive or negative. (Real numbers)

多 (h) Every integer is greater than −4 or less than 6. (Real numbers)

(i) Every integer is greater than some integer. (Integers)

多 (j) No integer is greater than every other integer. (Integers)

(k) Between any integer and any larger integer, there is a real number. (Real

numbers)

多 (l) There is a smallest positive integer. (Real numbers)

多 (m) No one loves everybody. (All people)

(n) Everybody loves someone. (All people)

(o) For every positive real number x, there is a unique real number y such

that 2 y = x. (Real numbers)

2. For each of the propositions in Exercise 1, write a useful denial, and give a

translation into ordinary English.

3. Translate these definitions from the Preface to the Student into quantified

sentences.

(a) The integer x is even.

(b) The integer x is odd.

Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part.

62025_01_ch01_p001-070.qxd

26

CHAPTER 1

4/22/10

1:42 AM

Page 26

Logic and Proofs

4.

夡

5.

6.

多

(c) The integer a divides the integer b.

(d) The natural number n is prime.

(e) The natural number n is composite.

Translate these definitions in this text into quantified sentences. You need not

know the specifics of the terms and symbols to complete this exercise.

(a) The relation R is symmetric. (See page 147.)

(b) The relation R is transitive. (See page 147.)

(c) The function f is one-to-one. (See page 208.)

(d) The operation * is commutative. (See page 277.)

The sentence “People dislike taxes” might be interpreted to mean “All people

dislike all taxes,” “All people dislike some taxes,” “Some people dislike all

taxes,” or “Some people dislike some taxes.” Give a symbolic translation for

each of these interpretations.

Let T = {17}, U = {6}, V = {24}, and W = {2, 3, 7, 26}. In which of these

four different universes is the statement true?

a) (Ex) (x is odd ⇒ x > 8).

b) (Ex) (x is odd ∧ x > 8).

(∀x) (x is odd ⇒ x > 8).

c)

d) (∀x) (x is odd ∧ x > 8).

7. (a)

夡

8.

多

多

多

Complete this proof of Theorem 1.3.1(b):

Proof: Let U be any universe.

The sentence ∼ (Ex) A(x) is true in U

iff . . .

iff (∀x) ∼ A(x) is true in U.

(b) Give a proof of part (b) of Theorem 1.3.1 that uses part (a).

Which of the following are true? The universe for each statement is given in

parentheses.

(a) (∀x)(x + x ≥ x). (⺢)

(b) (∀x)(x + x ≥ x). (⺞)

(c) (Ex)(2x + 3 = 6x + 7). (⺞)

(d) (Ex)(3x = x 2). (⺢)

(e) (Ex)(3x = x). (⺢)

(f) (Ex)(3(2 − x) = 5 + 8(1 − x)). (⺢)

(g) (∀x)(x 2 + 6x + 5 ≥ 0). (⺢)

(h) (∀x)(x 2 + 4x + 5 ≥ 0). (⺢)

(i) (Ex)(x 2 − x + 41 is prime). (⺞)

(j) (∀x)(x 2 − x + 41 is prime). (⺞)

(k) (∀x)(x 3 + 17x 2 + 6x + 100 ≥ 0). (⺢)

(l) (∀x)(∀y)[x 0 ⇒ ( Ey)(y 0)].

(e) (∀y)(Ex)(∀z)(xy = xz).

(f) (Ex)(∀y)(x ≤ y).

(g) (∀y)(Ex)(x ≤ y).

(h) (E!y)(y 0).

(i) (E!x)(∀y)(x = y2).

(j) (∀y)(E!x)(x = y2).

(k) (E!x)(E!y)(∀w)(w2 > x − y).

Let A(x) be an open sentence with variable x.

(a) Prove Theorem 1.3.2 (a).

(b) Show that the converse of Theorem 1.3.2 (a) is false.

(c) Prove Theorem 1.3.2 (b).

(d) Prove that ( E!x) A (x) is equivalent to (Ex)[A(x) ∧ (∀y)(A(y) ⇒ x = y)].

(e) Find a usef…

Purchase answer to see full

attachment

Order your essay today and save **15%** with the discount code: VACCINE