Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Introduction to mathematical arguments
(background handout for courses requiring proofs)
by Michael Hutchings
A mathematical proof is an argument which convinces other people that
something is true
...
In principle
we try to prove things beyond any doubt at all — although in real life people
make mistakes, and total rigor can be impractical for large projects
...
)
Anyway, there is a certain vocabulary and grammar that underlies all
mathematical proofs
...
These words have very precise meanings in mathematics which can
differ slightly from everyday usage
...

These notes give a very basic introduction to the above
...
Solow)
...
So I have
tried to keep this introduction brief and I hope it will be a useful guide
...

In §2 and §3 we introduce the basic principles for proving statements
...
This chart does not include uniqueness proofs
and proof by induction, which are explained in §3
...
Apendix A
reviews some terminology from set theory which we will use and gives some
more (not terribly interesting) examples of proofs
...
If you find any
mistakes or have any suggestions for improvement please let me know
...
For example,
6 is an even integer
and
4 is an odd integer
are statements
...
) We will use
letters such as ‘p’ and ‘q’ to denote statements
...
1

Logical operations

In arithmetic, we can combine or modify numbers with operations such as
‘+’, ‘×’, etc
...
then’
...
In some cases, the mathematical meanings of these words differ
slightly from, or are more precise than, common English usage
...
The simplest logical operation is ‘not’
...

The statement ‘not p’ is called the negation of p
...
If p and q are two statements, then the statement ‘p and q’ is defined
to be
• true, when p and q are both true;
• false, when p is false or q is false or both p and q are false
...
If p and q are two statements, then the statement ‘p or q’ is defined to
be
• true, when p is true or q is true or both p and q are true;
• false, when both p and q are false
...
However, this is never the case in mathematics
...

If
...
If p and q are statements, then the statement ‘if p then q’ is
defined to be
• true, when p and q are both true or p is false;
• false, when p is true and q is false
...
If p is false, then we say that p ⇒ q is vacuously true
...
If p and q are statements, then the statement ‘p if and only
if q’ is defined to be
• true, when p and q are both true or both false;
• false, when one of p, q is true and the other is false
...
When p ⇐⇒ q is true, we say
that p and q are equivalent
...
2

Quantifiers

Consider the sentence
x is even
...

There are three basic ways to turn this sentence into a statement
...

The following are two more interesting ways of turning the sentence into a
statement:
For every integer x, x is even
...

The phrases ‘for every’ and ‘there exists’ are called quantifiers
...

Definition
...

(The ‘if’ in this definition is really an ‘if and only if’
...
)
Definition
...


Notation for quantifiers
...
We can denote the
sentence ‘x is even’ by ‘P (x)’; then P (5) is the statement ‘5 is even’, P (72)
is the statement ‘72 is even’, and so forth
...
(See Appendix A for a
discussion of sets
...

We denote the set of integers by ‘Z’
...

4

Of course, this is still a statement about x
...
For instance, the statement
(∀x ∈ Z) (∃y ∈ Z) x = 2y
says that all integers are even
...
) The statement
(∃x ∈ Z) (∃y ∈ Z) x = 2y
says that there exists at least one even integer
...
)
The sentence
(∃y ∈ Z) x = 2y + 1
means that x is odd
...

The order of quantifiers is very important; changing the order of the
quantifiers in a statement will often change the meaning of a statement
...
However the statement
(∃y ∈ Z) (∀x ∈ Z) x < y
is false
...
3

How to negate statements
...
How do
you deny that something is true? The rules for doing this are given in the
right-hand column of Table 1
...

First, we put a ‘not’ in front of it:
not (∀x ∈ Z) (∃y ∈ Z) x = 3y + 1 ⇒ (∃y ∈ Z) x2 = 3y + 1
...


Using the rule for negating an ‘if
...


(∃x ∈ Z) (∃y ∈ Z) x = 3y + 1

Using the rule for negating a ‘there exists’ statement, we get
(∃x ∈ Z) (∃y ∈ Z) x = 3y + 1

2

and (∀y ∈ Z) x2 = 3y + 1
...
Consider the following conversation between mathematicians Alpha and Beta
...

Beta: Hmm
...

Alpha: OK, I’ll tell you what
...
Challenge me
...

Alpha: That’s easy
...
Give me a harder one
...

Alpha: Since 62 is even, I guess I have to show you that 622 is even
...


6

Alpha (counting on her fingers furiously): According to my calculations, 622 =
3844, and 3844 is clearly even
...
It’s not so clear to me that 3844 is even
...
If you
want to go around saying that 3844 is even, you have to produce an integer
y that works
...

Beta: Yes, you have a point there
...
But there are
billions of integers that x could be
...

Beta: Which integer?
Alpha: Any integer at all
...
I’m going to show you,
using only the fact that x is an integer and nothing else, that if x is even
then x2 is even
...
go on
...

Beta: But what if it isn’t?
Alpha: If x isn’t even, then the statement ‘if x is even, then x2 is even’ is
vacuously true
...

Beta: OK, so what do you do when x is even?
Alpha: By the definition of ‘even’, we know that there exists at least one integer
y such that x = 2y
...

Alpha: I think so
...
Squaring both
sides of this equation, we get x2 = 4y 2
...

Beta: Doesn’t 2y 2 work?

7

Alpha: Yes, it does
...

Beta: And since you haven’t said anything about what x is, except that it’s an
integer, you know that this will work for any integer at all
...

Beta: OK, I understand now
...
For every integer x, if x is odd,
then x2 is
...
First, a proof is an
explanation which convinces other mathematicians that a statement is true
...
The dialogue also
illustrates several of the basic techniques for proving that statements are
true
...

It lists the basic ways to prove, use, and negate every type of statement
...
Don’t worry if some of the entries in the table appear cryptic at first;
they will make sense after you have seen some examples
...
then’ statements, and how to use ‘there exists’ statements
...

Example
...

This is a ‘for every’ statement, so the first thing we do is write
Let x be any integer
...
So we write
Suppose x is odd
...
Recall
that the statement ‘x is odd’ means that there exists an integer y such that
x = 2y + 1
...
So to use the assumption that x
is odd, we write
8

Statement
p

•
•

p and q

•
•

p or q

•
•
•
•

p⇒q
•
•
p ⇐⇒ q
•
•
•
(∃x ∈ S) P (x)
•
(∀x ∈ S) P (x)

Ways to Prove it
Prove that p is true
...

Prove p, and
then prove q
...

Assume q is false, and
deduce that p is true
...

Prove that q is true
...

Assume q is false, and
deduce that p is false
...

Prove p and q
...

Find an x in S for
which P (x) is true
...


•

Say “let x be an element of S such that
P (x) is true
...

If P (x) is false, then
x ∈ S
...
” Prove
that P (x) is true
...

If p is false, you have
a contradiction
...

q is true
...

If p is false, then
q is true
...

If p is true, then
q is true
...


•

Table 1: Logic in a nutshell
...

Now we want to prove that x + 1 is even, i
...
, that there exists an integer y
such that x + 1 = 2y
...

Let y = w + 1; then y is an integer and x + 1 = 2y, so x + 1 is
even
...
E
...

which stands for something in Latin which means “that which was to be
shown”
...

Example
...

(Note that the first ‘and’ in this statement is not a logical ‘and’; it is just
there to smooth things out when we translate the symbols
(∀x ∈ Z) (∀y ∈ Z)
into English
...

We need to prove that if x is odd and y is odd then xy is odd
...
then’ statements, we write
Suppose x is odd and y is odd
...
We can use it to conclude that x is odd
...
In our proof, we write
Since x is odd, choose an integer w such that x = 2w + 1
...
We write
Since y is odd, choose an integer v such that y = 2v + 1
...
We can do this as follows:
Then xy = 4vw + 2v + 2w + 1
...

2
Next, we will illustrate how to prove and use ‘if and only if’ statements
...
Write a proof that for every integer x, x is even if and only if
x + 1 is odd
...
We must show x is even if and only if x + 1
is odd
...
Choose an integer y such that x = 2y
...

(⇐) Suppose x + 1 is odd
...
Then y is also an integer such that x = 2y, so x is even
...
For example, mathematicians Alpha and Beta proved in the dialogue that
For every integer x, if x is even then x2 is even
So the following is also a true statement:
For every integer x, if x + 1 is odd then x2 is even
...
All the statements we are proving here about even and odd numbers can be proved more simply using some basic facts about mod 2 arithmetic
...

Exercises
...
Prove the following statements:
(a) For every integer x, if x is even, then for every integer y, xy is even
...

(c) For every integer x, if x is odd then x3 is odd
...
Prove that for every integer x, x + 4 is odd if and only if x + 7 is even
...
Figure out whether the statement we negated in §1
...

4
...


3
3
...
The first entry in
the box in the table is what we call “proof by cases”
...

Example
...

Proof
...
Then x is even or x is odd
...
2, which here tells us that every integer can be

12

divided by 2 with a remainder of 0 or 1
...

Case 1: suppose x is even
...
Then
x(x+1) = 2k(2k+1)
...

Case 2: suppose x is odd
...

Then x(x + 1) = (2k + 1)(2k + 2)
...

2

3
...
This is
a useful and fun technique called “proof by contradiction”
...
Suppose that we want to prove that the statement
P is true
...
We then try to deduce a
contradiction, i
...
some statement Q which we know is false
...

We will give two examples involving rational numbers
...
If x is not rational it is called irrational
...
Prove that if x is rational and y is irrational, then x + y is
irrational
...
)
Let us assume the negation of what we are trying to prove: namely that
there exist a rational number x and an irrational number y such that x + y
is rational
...

Now x+y and x are rational by assumption, and the difference of two rational
numbers is rational (since p/q − p /q = (pq − qp )/(qq ))
...

But that contradicts our assumptions
...

2
13

√
Example
...

√
√
Suppose 2 is rational, i
...
2 = a/b for some integers a and b with b = 0
...
(Then a is positive too, although we will not need this
...
(We can do this by the Well-Ordering Principle, which
says that every nonempty set of positive integers has a smallest element; see
§4
...
)
√
Squaring both sides of the equation 2 = a/b and multiplying both sides
by b2 , we obtain a2 = 2b2
...
Thus
a = 2k for some integer k, so a2 = 4k 2 , and hence b2 = 2k 2
...
Since a and b are both even, a/2 and b/2 are
√
integers with b/2 > 0, and 2 = (a/2)/(b/2), because (a/2)/(b/2) = a/b
...

√
Therefore 2 cannot be rational
...
If
√
there exist positive integers a and b such that a/b = 2, then the above proof
shows that we can find smaller positive integers a and b with the same property, and repeating this process, we will get an infinite descending sequence
of positive integers, which is impossible
...

Another way to write this would be
Without loss of generality, b > 0
...


3
...
There is a standard strategy for doing this
...

A classic example of a uniqueness proof comes from group theory
...
The definition of a group requires that
this multiplication is associative (though not necessarily commutative), and
that there is an identity element e ∈ G such that
(∀x ∈ G) ex = xe = x
...
)
Example
...

Let e1 , e2 be elements of G satisfying e1 x = xe1 = x and e2 x = xe2 = x
for all x ∈ G
...
The trick is to multiply e1 and
e2 together in order to obtain an “identity crisis”
...
But since e2 is an identity element, we have
2
e1 e2 = e1
...

Exercise
...


4

Proof by induction

Mathematical induction is a useful technique for proving statements about
natural numbers
...
1

The principle of mathematical induction

Let P (n) be a statement about the positive integer n
...
”
or
P (n) = “If n is even, then n2 is divisible by 4
...
How
can we do this? One way is to prove the following two statements:
15

(a) P (1) is true
...

Why is this sufficient? Well, suppose we have proved (a) and (b) above
...
Since P (1) ⇒ P (2), we know that P (2) is
true
...
Since P (3) ⇒ P (4),
we know that P (4) is true
...

By analogy, suppose we have a chain of dominoes standing on end
...
This reasoning is called
the principle of mathematical induction
...
Let us state it
precisely
...
Let P (n) be a statement
about the positive integer n
...


P (1),

2
...

A proof by induction consists of two parts
...
In the second part, called the
inductive step, we assume that n is a positive integer such that P (n) is true,
(although we don’t know what n is), and we deduce that P (n + 1) is true
...
(This
may look like circular reasoning, but it is not! Think about the dominoes
again
...
For every positive integer n,
1 + 2 + ··· + n =

Proof
...

16

n(n + 1)

...

Inductive step: Suppose that for a given n ∈ Z+ ,
1 + 2 + ··· + n =

n(n + 1)

...
e
...

2
Adding (n + 1) to both sides of the inductive hypothesis, we get
1 + 2 + · · · + n + (n + 1) =

n(n + 1)
+ (n + 1)
2
n(n + 1) 2(n + 1)
=
+
2
2
(n + 2)(n + 1)
=

...

Using induction, we can extend this to the following:
Example
...
, an are real numbers and a1 a2 · · · an = 0, then ai = 0
for some i with 1 ≤ i ≤ n
...
We will use induction on n
...

Inductive step: Suppose the statement is true for n
...
Suppose a1 ,
...
Since (a1 · · · an )an+1 = 0, it follows that
a1 · · · an = 0 or an+1 = 0
...
If an+1 = 0, we are also done
...
For example, one might write “since the product of two nonzero real
numbers is nonzero, it follows by induction that the product of n nonzero
real numbers is nonzero”
...

There are many (equivalent) variants of the principle of induction
...
One can also prove a statement about several
positive integers by doing induction on one variable at a time
...
Let P (n) be a statement about the positive integer n
...

Then P (n) is true for all positive integers n
...
To see this, suppose we have proved
(*) for all positive integers n
...
Putting n = 2 into (*) we deduce that P (2) is true
...
And so on
...

Theorem
...

Proof
...
Let n > 1
be an integer and suppose that every integer n with 2 ≤ n < n is a product
of primes
...
If n is prime then
n is the product of one prime number (itself) and we are done
...
By inductive hypothesis, a and b are
18

both products of primes, and since n = ab, it follows that n is a product of
primes
...
2

The Well-Ordering Principle

If S is a set of integers, then a least element of S is an element x ∈ S such
that x ≤ y for all y ∈ S
...

Well-Ordering Principle (WOP)
...


Any nonempty set of positive inte-

However, it is not true for negative integers, rational numbers, or real
numbers
...

The well-ordering principle is equivalent to the principle of mathematical
induction
...
In other words, we will prove WOP by
induction
...
Suppose PMI is true
...
Let S be a set
of positive integers with no least element
...
To
do this, we will prove by induction on n that for every positive integer n, S
does not contain any numbers less than n
...

Inductive step: Suppose S does not contain any numbers smaller than
n
...

It is enough to show that n ∈ S
...
But we assumed that S has no
least element, so this is a contradiction
...
Suppose WOP is true
...
Let P (n) be
a statement about the positive integer n
...
We must show that for all n, P (n) is
true
...
Let
S := {n ∈ Z+ | P (n) is false}
...
Now
n0 = 1, because we know that P (1) is true
...
Then n0 − 1 is a
positive integer, and since it is smaller than n0 , it is not in the set S
...
But P (n0 − 1) implies P (n0 ), so P (n0 ) is true
...

/
2
There are some variants of the well-ordering principle which are easily seen
to be equivalent to it
...
(A lower bound on
S is a number L such that x ≥ L for all x ∈ S
...
A largest element of S is an
element x ∈ S such that x ≥ y for all y ∈ S
...
If a and b are integers with b > 0, then there exist
unique integers q and r such that a = qb + r and 0 ≤ r < b
...
In elementary school you learned an algorithm for finding q
and r
...
)
Proof
...

So let
S := {q ∈ Z | a − qb ≥ 0}
...
It also has an upper
bound, since a − qb ≥ 0 implies q ≤ |a|
...
Let r = a − qb
...
Also r < b, or else we would have a − (q + 1)b = r − b ≥ 0, so q + 1 ∈ S,
contradicting the fact that q is the largest element of S
...

Uniqueness is pretty easy to see; if q is any smaller then the remainder
will be too big
...

Suppose a = qb + r = q b + r with 0 ≤ r, r < b
...
We must have q − q = 0, because there is no way to obtain
a nonzero multiple of b by subtracting two elements of the set {0, 1,
...

Since q − q = 0, it follows that r − r = 0 also
...
2
Exercises
...
Fix a real number x = 1
...
+ xn =

xn+1 − 1

...
Guess a formula for
1
1
1
+
+ ··· +
1·2 2·3
n(n + 1)
and prove it by induction
...

3
...
(An L-triomino is a shape consisting of three squares joined
in an ‘L’-shape
...
Show that the smallest element of a nonempty set of positive integers is
unique
...


A
...
Some commonly used sets are:
R = the set of real numbers,
Q = the set of rational numbers,
Z = the set of integers,
N = the set of natural numbers (nonnegative integers),
Z+ = the set of positive integers
...
For example, the statement
S = {1, 2, 3}

21

defines S to be the set containing the numbers 1, 2, and 3
...
) to save ink, especially for sets with infinitely many elements;
for example,
N = {0, 1, 2, 3,
...
So 1 is an element of N, while −4 is not
...
The notation ‘x ∈ A’ means that x
/
is not an element of A
...
(A proof of the last assertion is given in §3
...
)
/
The elements of a set can be other sets; for example, {1, {2}} is the set
whose elements are 1 and {2}
...
The empty set, denoted ∅, is a special set which doesn’t have
/
any elements; in other words, ∅ = {}
...

Another way to describe a set is to give a criterion for deciding whether
or not an object is an element of the set
...

If P (x) is a statement about x, we use the notation {x | P (x)} to indicate
the set of all x for which P (x) is true
...

Another notation for this is
{x ∈ Z | x ≥ 0}
...
” Some more examples:
Q
∅
{1, 2, 3}
the set of even integers

=
=
=
=

{x ∈ R | (∃a, b ∈ Z) b = 0 and x = a/b},
{x ∈ Z | x2 = 3},
{x ∈ N | x > 0 and x < 4}
{x ∈ Z | (∃y ∈ Z) x = 2y}
...
In symbols,
A ⊂ B ⇐⇒ (∀x) x ∈ A ⇒ x ∈ B
22

For example, Z is a subset of R, but R is not a subset of Z
...
Also, the empty set is a subset of every set; for any set A,
the statement
(∀x) x ∈ ∅ ⇒ x ∈ A
is vacuously true, since the statement “x ∈ ∅” is always false
...

Two sets are equal if and only if they have the same elements; in terms
of subsets,
A = B ⇐⇒ A ⊂ B and B ⊂ A
For example,
{1, 2, 3} = {2, 3, 1},
but
{1, {2}} = {1, 2}
...
2

Unions and intersections

The union of two sets A and B, denoted by A ∪ B, is the set of all objects
that are in A or B (or both):
A ∪ B := {x | x ∈ A or x ∈ B}
...

For example,
{1, 2, 3} ∪ {2, 3, 4} = {1, 2, 3, 4},
{1, 2, 3} ∩ {2, 3, 4} = {2, 3}
...
In Figure ??(a), the inside of the circle on the left represents the contents of A, while the inside of the circle on the right represents
B
...
In Figure ??(b), the shaded region is A ∩ B
...
We will leave the proofs of most of these facts as exercises
...

A∪B =B∪A

A∩B =B∩A

Associative properties
...

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∪ C) = (A ∪ B) ∪ (A ∪ C)
A ∩ (B ∩ C) = (A ∩ B) ∩ (A ∩ C)
Other facts
...


24

Example
...

(⊂) Suppose x ∈ A∪(B ∩C)
...

By definition of union, x ∈ A or x ∈ B ∩ C
...
Then x ∈ A or x ∈ B, so x ∈ A ∪ B
...
Thus x ∈ A ∪ B and x ∈ A ∪ C, so x ∈ (A ∪ B) ∩ (A ∪ C)
...
Then x ∈ B and x ∈ C
...
Since x ∈ C, it follows that x ∈ A ∪ C
...

(⊃) Suppose x ∈ (A ∪ B) ∩ (A ∪ C)
...

We wish to show that x ∈ A ∪ (B ∩ C), i
...
, x ∈ A or x ∈ B ∩ C
...
It is enough to show that x ∈ B ∩ C
...
Likewise, since x ∈ A ∪ C, x ∈ C
...
2
In this example we have written down a lot of the details, but not every
single one
...
Likewise, since
/
x ∈ A ∪ C, x ∈ C
...

If we wanted to include every single detail, we would write
Since x ∈ A ∪ B, x ∈ A or x ∈ B
...
Since x ∈ A ∪ C, x ∈ A or x ∈ C
...
Thus x ∈ A and x ∈ C, so x ∈ B ∩ C
...
Usually a proof is centered around a
few simple ideas, and excessive writing will tend to obscure them
...
These are binary operations, which means that they can only
operate on two sets at once
...

But the associative property says that these two expressions are equal
...
Also, the commutative property
implies that we can change the order in which A, B, and C appear
...

Similarly, if n is any positive integer and A1 , A2 ,
...
∪ A n
and
A 1 ∩ A 2 ∩
...

The union of A1 , A2 ,
...
, An is the set of all things which
are in all n sets
...
3

Set difference

The difference between two sets A and B, denoted by A − B, is defined as
follows:
A − B := {x | x ∈ A and x ∈ B}
...
For example,
Z \ N is the set of negative integers
...

The following are some basic properties of the set difference operation
which you should remember
...

A − (B ∪ C) = (A − B) ∩ (A − C)
A − (B ∩ C) = (A − B) ∪ (A − C)
Other facts
...
Prove that A − (B ∪ C) = (A − B) ∩ (A − C)
...
Then x ∈ A, and x ∈ B ∪ C
...
Since
/
/
x ∈ A and x ∈ B, we have x ∈ (A − B)
...
Thus
/
x ∈ (A − B) ∩ (A − C)
...
Then x ∈ A, x ∈ B, and x ∈ C
...
Thus x ∈ A − (B ∪ C)
...

However, instead of memorizing a huge list of identities, it is better to figure
out and prove identities as they are needed
...
(But don’t do that for the
exercises in this chapter
...

1
...
(There are
2 elements and 4 subsets
...
Explain why if A ⊂ B and B ⊂ C, then A ⊂ C
...
If a set has exactly n elements, how many subsets does it have? Why?
4
...
Is this justified? If A
and B are both sets that contain no elements, then is A necessarily equal to
B?
5
...
Prove the all the properties of union, intersection, and set difference that we
stated without proof in the text
...
Show that A∩(B−C) = (A∩B)−(A∩C)
...
Find some more set theoretic identities and prove them

---