- Shopping Bag ( 0 items )
1.1 A QUEST FOR CERTAINTY
The study of mathematics is the quest for a sort of certainty that can be attained in no other endeavor. In mathematics we can "prove" things. But what does this mean? Less than we might hope. Bertrand Russell, one of the foremost British philosophers of recent times, called mathematics "the subject in which we never know what we are talking about, nor whether what we are saying is true." If this is the case, how can we hope to prove anything? We can't! What we can do, however, is show with absolute certainty that each of a chain of statements is "as true as those before it." If we believe the statements at the beginning of the chain, and that the chain is properly assembled, we must believe the statements at the end.
Of course, we have to begin somewhere, and it is evident that statements at the beginning of such a chain can't be proved. Statements that we agree to accept without proof are called axioms. We may discuss whether an axiom is appropriate (that is, whether it describes life as we perceive it) and we might at some point want to spend time discussing which axioms we ought to believe and which we should reject. But once this issue has been settled (and for the purposes of this course we consider it to be so) we agree not to discuss whether an axiom is true or false. Though it certainly can be an activity of great value, it is not our goal to scrutinize a collection of axioms here. We are studying the "top floors" of a subject, not its "foundations." Besides, the chain of reasoning leading from the most basic axioms to this text is unimaginably long. Bertrand Russell and Alfred North Whitehead took it upon themselves to build such a chain in their monumental Principia Mathematica. After several hundred pages, they were able to prove from "first principles" that 1 + 1 = 2. Fortunately, this is not how we will be spending our time. Foundational questions are as much philosophical as mathematical, and as mathematics they fall under headings other than analysis.
1. What did Russell mean when he said that mathematics is "the subject in which we never know what we are talking about, nor whether what we are saying is true"?
2. Discuss the differences in meaning of a statement of the form "It is true" when the assertion is made by a mathematician, a physicist, a biologist, a sociologist, a politician, or a used-car salesperson.
1.2 PROOFS AS CHAINS
It is instructive in many ways to view a proof as a chain of reasoning. To build a chain, we need a supply of links and a way to connect one link to another. In geometry class, we sometimes made two-column proofs with "Steps" on one side of the paper and "Reasons" on the other. A step might have been "Angle a is congruent to angle b," with the reason "Alternate interior angles." Steps are the links in the chain; reasons are the connections between them. We can safely use a real chain only if each of its links and the connections between them are sound. In mathematics, a sequence of statements, each of which is properly formed and correctly justified by those before it, is called a proof.
We can construct a chain from either end, or from both ends at once. We can even assemble links bound for the middle into sections and then connect the sections. In the same way, we can work a proof from the beginning or the end (or even from the middle). A proof is almost never thought of straight through from beginning to end. In textbooks, though, proofs are usually written down from beginning to end, causing much unnecessary confusion. Here we will give a brief outline of the basic logical structures we will encounter in our work. We observe right off the bat that even the simplest of ideas sometimes warrant discussion.
We have already used this important word, even though we may not be entirely sure what it means. Since statements are the steps in our proofs—the links in our chains—we should examine the meaning of the word carefully. Unfortunately, it is a bit difficult to capture, and the results might be a bit unsatisfying: A statement is a grammatically meaningful sentence to which one or the other (but not both) of the words "true" or "false" can be attached. The appropriate one of these is called the truth value of the statement. We see that "1 + 1 = 2" is a statement, since it may be labeled "true," and that "1 + 1 = 3" is a statement because it is "false." A collection of words to which no truth value can be attached is simply not a statement. For instance, consider the phrase "This sentence is false." If we believe this to be true, then the assertion it seems to make is true, and consequently it is false. On the other hand, if we believe it to be false, the assertion it seems to make is false, and so the sentence must be true! However we view it, we are led to conclude that the phrase is both true and false, which cannot be. We resolve this paradox by saying that "This sentence is false" is not a statement. (We have hedged our bets by saying that the sentence seems to make an assertion. Since it is not a statement, it can't make any assertion at all.)
The discussion of which collections of words are statements and which are not is another subject, and we won't go into it here. It will be enough for our purposes to note that a statement must assert something. This means, among other things, that a statement must contain a verb (in mathematics the verb is often =). Here is a very simple (but remarkably useful) preliminary test to check whether a collection of words is a statement:
IF IT DOESN'T MAKE SENSE AS LANGUAGE, IT DOESN'T MAKE SENSE AS MATHEMATICS.
The very best way to check this is to read what you write, preferably out loud. If your writing doesn't sound meaningful, it isn't. Many of what seem to be errors in understanding are actually only errors in grammar. This principle is most often violated in the writing of sentences that make no assertion. Sentences with no verbs!
1. Decide whether the following are statements:
(a) 2 + 4 = 7.
(b) sin2x + cos2x = 1.
(c) This sentence no verb.
(d) The sequence of digits 0123456789 appears somewhere in the decimal expansion of π.
There is a limit to the depth of ideas that can be expressed in statements like "1 + 1 = 2" and "A pencil is a writing utensil" (these are called simple statements). More interesting are compound statements like "Either 1 + 1 = 2 or a pencil is a useful tool in neurosurgery" and the more mundane "A subset of the real line is closed if and only if its complement is open."
The tools with which we make compound statements out of simpler ones are called connectives, of which we need to consider only four. The simplest connective is negation: If "A" is a statement, so also is "not A," which is sometimes denoted [logical not] A (we will use the word instead of the symbol). Since A is a statement, it has a truth value. The statement "not A" is assigned the truth value not given to A. So "1 + 1 = 2" is a (true) statement whose (false) negation is "not (1 + 1 = 2)." Here we could also say "1 + 1 ≠ 2," but it often takes some effort to phrase the negation of a statement in ordinary language. (Since it doesn't really "connect" anything, negation is often referred to as a modifier rather than a connective.)
Our first genuine connective is conjunction. If A and B are statements, their conjunction is the statement "AandB" (or "A [conjunction] B"). We may describe the truth values of "A and B" with a truth table like the one below:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
All combinations of truth values of the two statements A and B appear in the first two columns of this table. The last column tells us that "A and B" is true only when A and B are both true. This agrees with our usual understanding of the word. (But the meaning of "and" is being defined in this table. It need not coincide with ordinary usage, though it is all the better if it does.) If we assert that "it is warm and sunny," we expect it both to be warm and to be sunny. By specifying truth values of the statement "A and B," we are also asserting that "A and B" is a statement as long as A and B are statements.
The next connective is disjunction. The disjunction of A and B is written "AorB" (or "A [disjunction] B "), and is given by:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
The mathematical "or" is not quite the same as the grammatical "or." In ordinary usage, "or" can mean "one or the other or both" and it can mean "one or the other but not both." The former is called inclusive disjunction and the latter exclusive disjunction. In mathematics "or" always refers to inclusive disjunction. Exclusive disjunction is not uncommon in everyday language ("You can eat your lima beans or you can skip dessert"), but we encounter it so seldom in mathematics that we don't have a separate term for it.
The most important connective is implication. We use implication to join the links in the "chains" that constitute our proofs. We write "A [??] B" and say "AimpliesB." Here A is called the hypothesis and B is the conclusion. Implication is defined by this table:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
This deserves more discussion. We may think of an implication as a rule that is true if it is being obeyed and false if it is being broken:
IF IT IS RAINING, THEN YOU MUST CARRY AN UMBRELLA (RAIN [??] UMBRELLA)
Suppose it's raining and you're carrying your umbrella. You are not breaking the rule, and all is well (because "true [??] true" is true). If it's raining and you don't have your umbrella, you are breaking the rule ("true [??] false" is false). If it's not raining, you are obeying the rule whether you have your umbrella or not. The rule is not being broken by "no rain and umbrella" (false [??] true) or by "no rain and no umbrella" (false [??] false). Mathematicians agree to consider "false [??] true" and "false [??] false" to be true, but they do so grudgingly. Such implications are said to be vacuously true.
Analyzing compound statements in this way is a very small part of symbolic logic. We use symbolic logic to help us understand complex statements in terms of their (simpler) component parts. Sometimes it is possible to deduce the truth value of a compound statement from its form rather than its content. For example, "A or not A" is true regardless of the content or truth value of the statement A, while "A and not A" is always false (be sure you see why this is so).
These examples are too simple to illustrate the value of symbolic logic. We will examine some that are more significant. For instance, it might be useful to have an alternative means of expressing the relationship "A [??] B." Is there another statement containing the letters A and B that is false only when A is true and B is false? The "Umbrella Rule" would be false only if it were raining but there were no umbrellas in sight. This would correspond to "A and not B." Perhaps "not (A and not B)" is the same as "A [??] B." We can check this with a truth table:
The two rightmost columns of this table tell us that the statements "A [??] B" and "not (A and not B)" have the same truth value for any combination of truth values of A and B. We may show "not (A and not B)" instead of "A [??] B" if the former is more convenient. If two statements X and Y always have the same truth value, we say that they are logically equivalent and write X [??] Y or X [??] Y. Were we to include a column in the previous table for "(A [??] B) [??] not (A and not B)," all its entries would be T. An expression that is always true is called a tautology. One that is always false is a contradiction. Symbolic logic, in the rudimentary form in which we use it, is a search for tautologies and contradictions. "A [??] B" is also read "A if and only if B" or "A is necessary and sufficient for B." You will show in Exercise 1.4.2 that "A [??] B" is equivalent to "(A [??] B) and (B [??] A)," thus avoiding a possible conflict in meaning.
1. Make up more examples to illustrate the inclusive and exclusive "or."
2. (a) Show that "A or not A" is a tautology and "A and not A" is a contradiction.
(b) Show that "(A [??] B) and (B [??] A)" is equivalent to "A [??] B."
3. Prove each of the following using truth tables:
(a) not (A or B) [??] ((not A) and (not B))
(b) not (A and B) [??] ((not A) or (not B)) [the statements in (a) and
(b) are called deMorgan's laws.]
(c) (A [??] B) [??] (not B [??] not A) [This is called the contrapositive.]
(d) ((A or B) [??] C) [??] ((A [??] C) and (B [??] C))
(e) (A [??] (B and C)) [??] ((A [??] B) and (A [??] C))
(f) not (not A) [??] A
(g) Discuss the importance of parentheses in the statements in this exercise. In part e), for instance, is "A [??] (B and C)" the same as either "(A [??] B) and C" or "A [??] B and C"?
4. (a) Can "A [??] B" and "A [??] (not B)" ever both be true?
(b) Can "A [??] B" and "(not A) [??] B" ever both be true?
5. How many lines are there in a truth table that involves n statements?
6. (a) Construct a truth table to show that "A [??] (B [??] C)" is equivalent to "(A and B) [??] C."
(b) Show that (A [??] B) [??] (not A [??] not B).
(c) Discuss why there is a "possible conflict in meaning" in the interpretation of "[??]".
(d) Show that "A [??] (B [??] C)" is equivalent to "(A and B) [??] C." by negating both statements and simplifying the results.
7. Show that the following are not true.
(a) (A [??] B) [??] (B [??] A).
(b) ((A [??] B) and B) [??] A.
(c) ((A or B) and B) [??] A.
(d) ((A or B) and B) [??] not A.
8. In this section we have referred to "not (A and not B)" as a statement. Where is the verb in this expression?
1.5 PROOF BY CONTRADICTION
The equivalence in the last table in Section 1.4 is the basis for a technique called proof by contradiction, which is taken in practice as:
(A [??] B) [??] ((A and not B) is false).
You will verify this in Exercise 1.5.1. A proof by contradiction usually begins with the phrase "Suppose B does not hold ...," or something like it, and ends with "This is a contradiction." Such proofs are also called "indirect." Because this technique is so useful, the negation of complex statements is an important skill. The most famous proof by contradiction is probably Euclid's proof that there are infinitely many prime numbers:
Suppose there were only finitely many prime numbers. Then we could make a list of them all: p1, p2, ..., pn. Consider the number p = (p1 × p2 × ... × pn) + 1. Observe that p is not divisible by any of the listed primes. But every number larger than 1 is divisible by some prime. This contradicts the assumption that our list contains all the primes, and the proof is finished.
Excerpted from Introduction to Real Analysis by Michael J. Schramm. Copyright © 1996 Michael J. Schramm. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.