Logic and the Axiomatic Method

Introduction

Mathematicians use a large number of methods to discover new results---trial and error, computation of special cases, inspired guessing, pulling results from thin air. The difference in this and an astrologer, for example, is that we have an accepted method, called the axiomatic method, for proving that these results are correct. Proofs give us assurance that results are correct. In many cases they also give more general results. For example, the Egyptians and Hindus knew by experiment that if a triangle has sides of lengths 3, 4, and 5, it is then a right triangle. But the Greeks proved that if a triangle has sides of lengths a, b, and c, and if a²+b²= c², then the triangle is a right triangle. There is no amount of checking by experiment that could give this general result. Proofs give us insight into relationships among different things that we are studying, forcing us to organize our thoughts in a coherent way. If you gain nothing else from the course than this, you have still gained the greatest gift that mathematics has to offer.

I wish to persuade you that a certain statement is true or false by pure reasoning. I could do this by showing you that the statement follows logically from some other statement that you may already believe. I may have to convince you that that statement is also true, and follows from another statement. This process may continue until I reach a statement which you are willing to believe, one which does not need justification. That statement plays the role of an axiom. If no such statement exists, then I will be caught in an infinite regress, giving one proof after another ad infinitum. There are three requirements that must be met before we can agree that a proof is correct.

There must be mutual understanding of the words and symbols used in the discourse.
There must be acceptance of certain statements called axioms without justification.
There must be agreement on how and when one statement follows logically from another, i.e., agreement on certain rules of reasoning.

There should be no problem in reaching mutual understanding so long as we use terms familiar to both and use them consistently. If I use an unfamiliar term, you have the right to demand a definition of this term. Definitions cannot be given arbitrarily; they are subject to the rules of reasoning referred to in Requirement 2. Also, we cannot define every term that we use. In order to define one term we must use other terms, and to define these terms we must use still other terms, and so on. If we were not allowed to leave some terms undefined, we would get involved in infinite regress.

Let us begin with this.

Sets

We need some basic information about sets in order to study the logic and the axiomatic method. This is not a formal study of sets, but consists only of basic definitions and notation.

Braces { and } are used to name or enumerate sets. The roster method for naming sets is simply to list all of the elements of a set between a pair of braces. For example the set of integers 1, 2, 3, and 4 could be named {1,2,3,4}. This does not work well for sets containing a large number of elements, though it can be used. The more common method for this is known as the set builder notation. A property is specified which is held by all objects in a set. P(x), read P of x, will denote a sentence referring to the variable x. For example,

x = 23
x is an odd integer.

The set of all objects x such that x satisfies P(x) is denoted by {x | P(x)}. The set {1,2,3,4} can be named .

From hence forth, the words object, element, and member mean the same thing when referring to sets. Sets will be denoted mainly by capital Roman letters and elements of the sets by small letters. The following have the same meaning:

a is in set A
a is a member of set A
a is an element of set A.

Likewise, means that a is not an element of set A. A is a subset of B if every element of A is also an element of B. The following have the same meaning:

Every element of A is an element of B
If , then
A is included in B
B contains A
A is a subset of B

Note that a set is always a subset of itself.

If A and B are sets, then we say that A = B if A and B represent the same set:

A = B
A and B are the same set
A and B have the same members

The set which contains no elements is known as the empty set, and is denoted by . Note that for each set A, .

The intersection of two sets A and B is the set of all elements common to both sets. The intersection is symbolized by or . The union of two sets A and B is the set of elements which are in A or B or both. The union is symbolized by or .

Universal Sets and Compliments

When we are working in an area or on a certain problem, we always have a frame of reference in which we are working called a universal set. In our geometry course, it will be the set of points that lie on a plane. In calculus we consider the set of real numbers, the set of real functions, the set of differentiable functions, and the set of continuous functions as universal sets.

The complement of a set A is defined to be the set of all elements of the universal set which are not in A, and is symbolized by CA = A' = A^c. Note that is always the universal set, while .

Sentences and Statements

Logic and mathematical proof can be studies just like algebra. In fact, much of symbolic logic is just that. A declarative sentence which is true or false, but not both, is called a statement. The following are statements:

Babe Ruth hit 714 home runs.
Jack Nicklaus has won 20 major golf titles.
2 + 3 = 6
The 25,000^th digit of is 7.

The following are not statements:

He is a golfer.
Why is a duck?
x + 1 = 0
x - y = a

The sentence

He is a golfer.

cannot be judged true or false because we do not know who He is. If the word {\em He} is replaced by Greg Norman forming the sentence

Greg Norman is a golfer.

the sentence becomes a true statement. Similarly, if x in the sentence x + 1 = 0 is replaced by 2, forming the sentence 2 + 1 = 0, the sentence then becomes a false statement.

The letter x is a variable in the sentence x + 1 = 0. A letter or other symbol that can represent various elements of a universal set is called a variable. We can make a sentence a statement by replacing its variables by elements of the universal set or by attaching phrases such as For every or There exists to the sentence. For example, x < 3 is not a statement, but each of the following is a statement:

1 < 3
5 <3
For every real number x, x < 3.
There exists a real number x, such that x < 3.

Replacements for variables of a sentence are always chosen from some universal set. Any replacement which makes a sentence true is called a solution. The set of all solutions is called the solution set of the sentence.

Connectives

If P and Q are sentences, then the sentence P and Q is called the conjunction of P and Q, denoted by . For any statement there are just two possible truth values, true (T) or false (F). If P and Q are both true, then is true. If one or both of P and Q are false, then is false. The truth table below defines the truth values of for all possible truth value combinations of P and Q.

If P and Q are sentences, then the sentence P or Q is called the disjunction of P and Q, denoted by . In mathematics we use an {\em inclusive} or. That is, is true when P is true, or Q is true, or both are true. is false only when P and Q are false. the truth table for is thus defined below.

P	Q		P	Q
T	T	T	T	T	T
T	F	F	T	F	T
F	T	F	F	T	T
F	F	F	F	F	F

A negation, or denial, of a sentence is formed in many ways. For example the negation of the statement P: 2 is rational is represented by each of the following:

P	~P
T	F
F	T

~P
It is false that 2 is rational.
2 is not rational.
2 is irrational.

The truth table for negation is obvious. You need to realize that there are other symbols, besides ~, for negations that are in common usage.

means ~( a = b )
means ~( a < b )
means ~()

If P and Q are sentences, the sentence If P, then Q is denoted by or . We construct a truth table for just as for the the other connectives , , and ~. However, the definition is not at all obvious. Consider the sentence:

If I get an A in mathematics, then I will take the next course.

Suppose a fellow student says this. When is the sentence true and when is it false? Let P denote the statement I get an A in mathematics and let Q denote the statement I will take the next course. Consider the following four cases.

P (true): He gets an A in mathematics.
Q (true): He takes the next course.
P (true): He gets an A in mathematics.
Q (false): He does not take the next course.
P (false): He does not get an A in mathematics.
Q (true): He takes the next course.
P (false): He does not get an A in mathematics.
Q (false): He does not take the next course.

P	Q
T	T	T
T	F	F
F	T	T
F	F	T

It is easy to see that (1) is true and that (2) is false. You cannot claim that the original statement was false in (3) since he takes the next course even though he did not get an A. Likewise, in (4) you cannot claim that the statement was false, since he did not get an A and he did not take the next course. The truth table for this sentence is shown.

The sentence is called a conditional with P the antecedent and Q the consequent. In mathematics the conditional is encountered in many forms. The following have the same meaning:

If P, then Q
P implies Q
Q if P, P only if Q
Q provided P
Q whenever P, Q when P
P is a sufficient condition for Q
Q is a necessary condition for P.

Biconditionals and Combinations of Connectives

P	Q
T	T	T
T	F	F
F	T	F
F	F	T

A sentence of the type is called a biconditional, denoted . When P and Q are sentences, the truth table for is as shown.

In mathematics the biconditional is encountered in many forms. The following have the same meaning:

P is equivalent to Q
P if and only if Q
Q if and only if P
P iff Q
If P, then Q and conversely
If Q, then P and conversely
P is a necessary and sufficient condition for Q
Q is a necessary and sufficient condition for P.

Combinations of ~, , , , and often occur. A facility at recognizing them is essential for mathematical reading and proof. Consider the following statement:

If P is prime, then if P is even P must be smaller than 7.

This breaks up into three statements:

P: P is prime.
Q: P is even.
R: P must be smaller than 7.

We can then translate the original statement into .

If k is perpendicular to and is perpendicular to m, then k is parallel to m.

Let

P: k is perpendicular to
Q: is perpendicular to m
R: k is parallel to m.

Then the sentence translates as .

Quantifiers

Sentences involving the phrases For every … and There exists … also play a very important role in the structure of mathematical sentences. The symbol

, called the universal quantifier, denotes phrases such as For each, For every, For all. A sentence such as

For every x, P(x)

can be translated symbolically into x P(x); or x, P(x). The following sentences have the same meaning:

x, x is an integer ,
For every x, if x is an integer, then ,
For all x, if x is an integer, then ,
For each x, if x is an integer, then ,
Every integer belongs to Q,
Every integer is a rational number,
If x is an integer, then .

Note that in the last sentence the universal quantifier is understood and not written.

The symbol , called the existential quantifier symbolizes phrases such as There exists, There is at least one, For at least one, and Some. A sentence such as

There exists an x such that P(x)

translates symbolically to x P(x) or x, P(x).

The following have the same meaning:

x, x is a natural number.
There exists an x such that x is a natural number.
Some number is a natural number.
There is at least one natural number.

Quantifiers often appear together. Consider the following examples.

x y, x + y = 0	For every x and for every y, x + y = 0.
x y, x + y=0	For every x there exists a y so that x + y = 0.
x y, x + y=0	There exists an x such that for all y, x + y=0.
x y, x + y=0	There exists an x and there exists a y such that x + y=0.

The following sentence

For every x, if x is even, then there exists a y such that x = 2y.

translates as x (x is even y, x=2y).

These quantifiers refer to some universal set, which if not explicitly given, must be easily inferred from the context. We will be interested only in nonempty universal sets.

Definition: The sentence x P(x) is true if and only if the solution set of P(x) equals the universal set. This sentence is false if the solution set is a proper subset of the universal set; i.e., if there is at least one element of the universal set for which P(x) is false.

Definition: The sentence x P(x) is true if the solution set of P(x) is nonempty. This sentence is false if the solution set of P(x) is empty; i.e., if for every replacement of x by a member a of the universal set, P(a) is false.

For more complicated mathematical sentences containing more quantifiers let us look at a few examples.

Example: Suppose P(x,y) is a sentence with variables x and y. The sentence xy P(x,y) is true if and only if for every replacement of x and y by members a and b from the universal set, the statement P(a,b) is true. The sentence is false if there is a replacement for x or a replacement for y for which the statement is false.

Example: The sentence xy, P(x,y) is true if there exists a replacement A for x such that y P(a,y) is true. This same A makes the sentence P(a,b) true for every B in the universal set. Note that the sentence xy, x > y is false. There is no replacement A for x which makes the sentence y, a > y true.

Rules of Reasoning

Mathematicians assume a certain class of sentences to be true before we ever prove any theorems in a mathematical system. We call these sentences rules of reasoning. They could be called reasoning axioms.

An important class of these rules of reasoning are known as tautologies. A tautology is a sentence which is true no matter what the truth value of its constituent parts.

P Q

T T T T

T F F T

F T F T

F F F T

Example: The sentence is a tautology, where P and Q represent arbitrary mathematical sentences. We can show that this is a tautology from a truth table. The way in which we do this is to compute the truth values for in the third column first, and then use columns one and three to compute the truth values in column four.

Logic Axiom 1: Every tautology is a rule of reasoning.

The following are tautologies that we commonly use. You will find these listed in the Rules of Logic that you have been given.

contrapositive
Modus ponens
Law of Syllogism
(Law of the Excluded Middle)
(Law of Syllogism)
(Proof by Cases)

Valid Arguments

The tautologies in the preceding section are not all that there are. If you want to make a deduction based on a sentence, check its truth table. If it is a tautology, use it. Tautologies provide lots of reasoning theorems before we ever start deduction within a mathematical system.

There are actually two branches of formal logic: the statement calculus, involving statements and reasoning by tautology; and the predicate calculus, involving quantified sentences. All we are doing is taking a quick guided tour through informal logic, and so we will not study these areas in great detail. However, from the predicate calculus we get another collection of reasoning sentences, some of which are listed below. These cannot be verified by tautology.

Logic Axiom 2: Let U be a universal set. Each of the following is a rule of reasoning.

An argument is an assertion that from a certain set of sentences (called premises or assumptions) one can deduce another sentence Q (called an inference or conclusion). Such an argument can be denoted by . Arguments are either valid (correct) or invalid (incorrect).