Next: 3.2 Sets Defined by Up: 3. Propositions and Functions Previous: 3. Propositions and Functions   Index

# 3.1 Propositions

3.1   Definition (Proposition.) A proposition is a statement that is either true or false. I will sometimes write a proposition inside of quotes ( ''), when I want to emphasize where the proposition begins and ends.

3.2   Examples.

If '', then is a true proposition.

If '', then is a false proposition.

If '', then is a true proposition.

If '', then I will not consider to be a proposition (unless lucky number has been defined.)

3.3   Definition (And, or, not.) Suppose that and are propositions. Then we can form new propositions denoted by  and '',  or '', and not ''.

 and '' is true if and only if both of are true.

 or '' is true if and only if at least one of is true.

not '' is true if and only if is false.

Observe that in mathematics, or'' is always assumed to be inclusive or: If '' and '' are both true, then  or '' is true.

3.4   Examples.

 and '' is false.

 or '' is true.

 or '' is true.

not(not )'' is true if and only if is true.

For each element of Q let be the proposition
 ''. Thus =  '', so is true, while =  '', so is false. Here I consider to be a rule which assigns to each element of Q a proposition

3.5   Definition (Proposition form.) Let be a set. A rule that assigns to each element of a unique proposition is called a proposition form over .

Thus the rule defined in the previous paragraph is a proposition form over Q. Note that a proposition form is neither true nor false, i.e. a proposition form is not a proposition.

3.6   Definition ( , Equivalent propositions.) Let be two propositions. We say that  is equivalent to '' if either ( are both true) or ( are both false). Thus every proposition is equivalent either to '' or to  '' We write  '' as an abbreviation for  is equivalent to '' If are propositions, then  '' is a proposition, and

 '' is true if and only if (( are both true) or ( are both false)).

Ordinarily one would not make a statement like

 )''

even though this is a true proposition. One writes  '' in an argument, only when the person reading the argument can be expected to see the equivalence of the two statements and .

If and are propositions,then

 (3.7)

is an abbreviation for

Thus if we know that (3.7) is true, then we can conclude that is true. The statement  '' is sometimes read as  if and only if ''.

3.8   Example. Find all real numbers such that
 (3.9)

Let be an arbitrary real number. Then

Thus the set of all numbers that satisfy equation (3.9) is {2,3}.

3.10   Definition ( , Implication.) If and are propositions then we say  implies '' and write  '', if the truth of follows from the truth of . We make the convention that if is false then is true for all propositions , and in fact that
 (3.11)

Hence for all propositions and
 (3.12)

3.13   Example. For every element in Q
 (3.14)

In particular, the following statements are all true.
 (3.15) (3.16) (3.17)

In proposition 3.16, is false, is true, and is true.

In proposition 3.17, is false, is false, and is true.

The usual way to prove is to assume that is true and show that then must be true. This is sufficient by our convention in (3.11).

If and are propositions, then  '' is also a proposition, and

 (3.18)

(the right side of (3.18) is true if and only if are both true or both false.) An alternate way of writing  '' is if then ''.

We will not make much use of the idea of two propositions being equal. Roughly, two propositions are equal if and only if they are word for word the same. Thus '' and '' are not equal propositions, although they are equivalent. The only time I will use an '' sign between propositions is in definitions. For example, I might define a proposition form over N by saying

for all '',

or

for all .

The definition we have given for implies'' is a matter of convention, and there is a school of contemporary mathematicians (called constructivists) who define to be true only if a constructive'' argument can be given that the truth of follows from the truth of . For the constructivists, some of the propositions of the sort we use are neither true nor false, and some of the theorems we prove are not provable (or disprovable). A very readable description of the constructivist point of view can be found in the article Schizophrenia in Contemporary Mathematics[10, pages 1-10].

3.19   Exercise.

a) Give examples of propositions such that  '' and  '' are both true, or else explain why no such examples exist.

b) Give examples of propositions such that  '' and  '' are both false, or explain why no such examples exist.

c) Give examples of propositions such that  '' is true but  '' is false, or explain why no such examples exist.

3.20   Exercise. A Let be two propositions. Show that the propositions  '' and  '' are equivalent. ( '' is called the contrapositive of the statement  ''.)

3.21   Exercise. Which of the proposition forms below are true for all real numbers ? If a proposition form is not true for all real numbers , give a number for which it is false.

a)
.
b)
.
c)
.
d)
. (Here assume .)
e)
.
f)
.
g)
.
h)
.

3.22   Exercise. Both of the arguments A and B given below are faulty, although one of them leads to a correct conclusion. Criticize both arguments, and correct one of them.

Problem: Let be the set of all real numbers such that . Describe the set of all elements such that

 (3.23)

Note that if then is defined.

ARGUMENT A: Let be an arbitrary element of . Then

Hence the set of all real numbers that satisfy inequality (3.23) is the set of all real numbers such that .

ARGUMENT B: Let be an arbitrary element of . Then

Now

Hence the set of all real numbers that satisfy inequality (3.23) is the set of all such that either or .

Next: 3.2 Sets Defined by Up: 3. Propositions and Functions Previous: 3. Propositions and Functions   Index
Ray Mayer 2007-09-07