Introduction to Proof in Abstract Mathematics

Read an Excerpt

Introduction to Proof in Abstract Mathematics

Dover Publications, Inc.

Sets and Rules of Inference

1.1 DEFINITIONS

We begin this section with a review of some notation and informal ideas about sets now common in the school curriculum. A set is a collection of things viewed as a whole. The things in a set are called elements or members of the set. The expression "x [member of] A" means that x is a member of set A and is read "x is an element of A" or "x is a member of A". The expression "x [not member of] A" means that x is not a member of A. We will assume that all sets are formed of elements from some universal set [union] under consideration. The set of real numbers will be denoted by R, integers by Z, and positive integers by N.

We will not give a formal definition of set. It will be an undefined term—a starting point in terms of which we will define other things. While the idea of a set is undefined, we will assume that any particular set may be defined by giving a rule for deciding which elements of the universal set are in the particular set and which are not.

For example, if R is our universal set, then the set of all real numbers between 0 and 1 is written {x [member of] R | 0 < x< 1}. This is read "the set of all x in R such that zero is less than x and x is less than one". In the expression "{x [member of] R | 0 < x< 1}", the symbol "x" is used as a local variable or a dummy variable. That is, x has no meaning outside the expression and any other letter (except R, of course) would do as well. Thus {x [member of] R | 0 < x< 1} and {y [member of] R | 0 < y< 1} have exactly the same meaning. Sometimes the rule for deciding set membership is not explicitly stated but is nevertheless obvious. For example, a set may be given by listing its elements, such as N3 = {1, 2, 3}. In particular, = {1, 2, 3, 4, ...} and Z = {0, 1, -1, 2, -2, ...}. The set {1, 2, 3, ..., k} will be denoted by Nk.

A statement is a mathematical expression that is either true or false. For example, 2 [member of] {x [member of] R | x< 5} (true), 32 + 42 = 52 (true), and b√2 = a for some a, b [member of] Z. (false) are statements. The rule 0 <x< 1 used to define the set A = {x [member of] R | 0 < x< 1} is an example of an open statement; that is, the truth of 0 < x< 1 depends on the value substituted for x. For example, if x = 1/2, then 0 < x< 1 is true, and if x = 2, then 0 < x< 1 is false. The open statement 0 < x< 1 is considered to be a property that real numbers may or may not have—the defining property of the set A above. Thus if a is some real number that makes 0 < a< 1 true, then a satisfies the defining property of the set A and is therefore a member of A. If 0 < a< 1 is false, then a [not member of] A. In our definitions of some particular set, say, A, we will always have in mind some universal set of elements that are allowed to be substituted in the open statement that gives the defining property for A.

In the definition A = {x [member of] R | 0 < x< 1}, the universal set is R. When this universal set is either clear or not important to our discussion, we will sometimes not mention it explicitly. For example, A above can be written A = {x | 0 < x< 1}. In order to avoid logic contradictions, it is important to know what sort of thing can be substituted for the variable in an open statement. This is the role of the universal set.

The set with no elements is called the empty set and is denoted by [empty set]. One reason for considering an empty collection as a set is to provide consistency in notation. For example, we want {a [member of] R | a2 = -1} to be a set as well as {a [member of] R | a2 = 2}.

A formal mathematical proof consists of a numbered sequence of statements. Each statement must follow logically from previous statements (or steps) in the sequence. In our proofs, beside each statement we will give in parentheses: (1) the numbers of the previous steps from which the given statement follows, (2) a semicolon, and (3) the reason that the given statement follows logically from the indicated previous steps. For example, in the hypothetical proof steps below, the justification (1, 3; Theorem 14) for Step 4 indicates that Statement 4 is a logical consequence of the statements in Steps 1 and 3 when Theorem 14 is applied:

1. · · ·

2. · · ·

3. · · ·

4. x [member of] B (1, 3; Theorem 14)

In the set D = {x [member of] R | x< 1}, the open statement x< 1 gives the property that defines the set. Thus, if y [member of] D, then y must have the property defining D, namely, y< 1. Conversely, if a< 1, that is, if a satisfies the defining property, then we must have a [member of] D. This shows the two ways the definition of a particular set can be used as a reason for proof steps.

Example 1:

Define C = {x [member of] R | x< 2}. The definition of C tells us in both cases below why Step 2 follows from Step 1.

1. a [member of] C

2. a< 2 (1; def. C)

1. b< 2

2. b [member of] C (1; def. C)

This example illustrates our first inference rule:

Inference Rule

Set definition rule: If an element is in a set, we may infer that it satisfies the defining property. Conversely, if it satisfies the defining property, we may infer that it is in the set.

Note in Example 1 that it is understood, but not stated, that all elements are in the universal set R. If we know that a [member of] C, then by the definition of C we know both a< 2 and a [member of] R, but the latter is not stated.

In this text we will have certain standard phrases and very precise ways of dealing with these phrases. They will be part of our formal proof language (for brevity's sake called our language) and will be printed in boldface type. Thus the letters A, B, X, ... a, b, x, ..., which stand for numbers, sets, or elements in sets, will be part of our language. Statements about numbers (such as x2 + 2 < 3) or set membership (such as a [member of] X or 5 [not member of] A) will also be part of our language. Sentences like the one you are now reading, the purpose of which is to communicate ideas in ordinary English, are part of our informal language (called metalanguage) and printed in ordinary type. Metalanguage statements may contain symbols or statements of our language, but the reverse is not possible. Thus we may write, "For all real numbers x, if x [member of] C, then x< 2." This sentence is in our metalanguage but contains the statements x [member of] C and x< 2, which are part of our language.

As we progress, we will enlarge our stock of language statements. These are the statements used in proof steps and for which very precise rules of inference are given. Our theorems, on the other hand, will be given in metalanguage and will contain language statements. For example, consider the following statement:

Theorem (example)

If X = {x [member of] R | x < 1} and a [member of] X, then a< 2.

In developing a proof of this theorem, our first task will be to decide, from the metalanguage statement, which language statements we may assume for the sake of proof (these are called hypotheses) and which statement we are to show (this is called the conclusion). The hypotheses and conclusion will form the first part of our proof:

Proof:

Assume: 1. X = {x [member of] R | x< 1}

2. a [member of] X

Show: a< 2

The statements of the hypotheses and conclusion must be part of our language. The conclusion will always be the last step in the proof. The hypotheses may be used to draw inferences or written down as steps at any stage of the proof. We could, for example, continue with the development of the proof of the sample theorem as follows:

1. a [member of] X (hyp. 2)

2. a< 1 (1, hyp. 1; def. X)

.

.

(last step) k. a< 2

From the facts that a [member of] X (Step 1) and that X is defined to be {x [member of] R | x< 1} (hypothesis), we may infer that a< 1; that is, a has the property defining the set X. The formal justification for this is "definition of X" since, by our rule of inference, this is how we use the definition. To complete the proof, we need to show that a< 2. This follows from the step a< 1, the fact that 1 < 2, and the "transitivity" of the order relation "<" on the real numbers.

Appendix 1 gives the algebraic and order properties of the familiar number systems. These are the properties derived from the axioms of arithmetic stressed in school mathematics. It is these properties that let us solve equations and inequalities and perform the ordinary computations and algebraic manipulations with which you are familiar from previous courses—and which allow us to conclude a< 2 from a< 1 above. As we develop our mathematical and logical ideas, we will occasionally use examples from the sets R, Z, and N. For these examples (only), we will allow changes in proof steps according to the following inference rule:

Inference Rule

Computation rule: Steps in a proof that follow from other steps by the familiar techniques of algebra applied toR, Z,andNare allowed. Justification for such steps is given, for example, as "property of the real numbers" (abbreviated "prop.R"). These properties are found in Appendix 1.

A complete proof of our sample theorem is then given by:

Proof:

Assume: 1. X = {x [member of] R | x< 1}

2. a [member of] X

Show: a< 2

1. a [member of] X (hyp. 2)

2. a< 1 (1, hyp. 1; def. X)

3. 1 < 2 (prop. R)

4. a< 2 (2, 3; prop. R)

Proofs are differentiated from other parts of the text by shading, and the symbol [??] signals the end of a proof.

Step 4 follows from Steps 2 and 3 by the transitive property of <. Since we will not define the real numbers, it is not possible to prove either the transitive property or the fact 1 < 2. Students who have not yet fully understood what a proof is generally find proofs of such things hopelessly unenlightening. Only a mathematician could feel that the idea of proof was more fundamental than the fact 1 < 2, which would therefore require proof.

In our proofs we will usually combine adjacent steps whose justification is "property of R (or Z or N)". Thus we may omit Step 3 above and go right to Step 4 (now renumbered Step 3). The new steps would be:

1. a [member of] X (hyp. 2)

2. a<1 (1, hyp. 1; def. X)

3. a< 2 (2; prop. R)

In doing proofs, we will assume that the hypotheses of the theorem being proved are true (for the sake of argument). We will also assume all previously proved theorems are true. Thus a proof for us will be a sequence of statements (that is, steps), the truth of each of which follows by our rules of inference from the truth of previous steps, hypotheses, and theorems.

Example 2:

Consider the statements

(a)For sets A, B and a real number x, if x [member of] A, then x [member of] B.

(b) For real numbers x, y, if x [??] y and x ≠ y, then y< x.

The hypotheses for (a) are

A, B sets x real x [member of] A

We consider the symbols "A", "B", and "x" defined for the sake of a proof so that we may use them in the proof without definition in the proof itself. We will include as hypotheses an identification of all such symbols used in the proof and the language statements we may take as true for the sake of argument.

Hypotheses and conclusion for (a) are:

Assume: A, B sets

x real

x [member of] A

Show: x [member of] B

Hypotheses and conclusion for (b) are:

Assume: x, y [member of] R

1. x [??] y

2. x ≠ y

Show: y < x

1. Define A = {z [member of] R | z ≠ 1}.

(a) Suppose we are given Step 4 and the reason for Step 5 in some proof:

4. b [member of] A

5. (4; definition of A)

What must Step 5 be?

(b) Suppose we are given the following:

4.

5. b [member of] A (4; definition of A)

What must Step 4 be?

2. Suppose we are given the following:

5. x [member of] B

6. x ≤ 7(5; def. B)

7. x ≤ 8 (6; prop. R)

8. x [member of] C (7; def. C)

What must the definitions of sets B and C be?

---

Excerpted from Introduction to Proof in Abstract Mathematics by Andrew Wohlgemuth. Copyright © 2011 Andrew Wohlgemuth. 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.

---