University of California Davis Transition to Advanced Mathematics Questions

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 office locations around the globe, including
Singapore, the United Kingdom, Australia, Mexico, Brazil and Japan.
Locate your local office 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