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

---

Sets, Logic and Proofs
Extra notes for Mathematics 114

1

Sets

A set is any collection of things, called elements
...
If x is
an element of a set S, we write
x ∈ S
...

In what follows, you will see lots of new notation (weird-looking mathematical symbols)
...
For example, ∈ can be considered an abbreviation for “is an element of”
...
1

defining sets

To define a set, you have to specify what elements it contains
...
For example:
S := {2, 3, 5}
is the set containing as elements the three numbers 2, 3 and 5
...
The order in which they are listed doesn’t matter, and listing an
element more than once also makes no difference:
{2, 3, 5} = {3, 2, 5} = {5, 3, 2} = {3, 2, 3, 2, 5, 5, 5, 5, 3, 2}
...
For example
S := {x | x is a whole number greater than 5}
is the set of all whole numbers greater than 5, i
...
S = {6, 7, 8,
...
2

Important sets

Here are some basic sets that you need to be familiar with:
• ∅ = {} is the empty set
...

• N = {1, 2, 3,
...
Note that 0 6∈ N
(although not everybody follows this convention - computer scientists in particular often
define N to contain 0 as well)
...
, −3, −2, −1, 0, 1, 2, 3,
...


1

• Q = {m
n | m, n ∈ Z, n 6= 0} is the set of all rational numbers (whole numbers and
fractions), i
...
numbers which can be written as an integer divided by another non-zero
integer
...

• R is the set of all real numbers, i
...
those√
numbers represented by points on the number line
...


1
...
We write
this as
A⊂B
or
B ⊃ A
...
For the sets we saw above, we have the
inclusions
∅ ⊂ N ⊂ Z ⊂ Q ⊂ R
...

Intervals are subsets of R
...

Two sets A and B are equal if they contain exactly the same elements
...

(Note: some textbooks write A ⊆ B for subsets, and reserve the notation A ⊂ B only for those
situations when A is strictly contained in B, i
...
when A 6= B
...
)

1
...

The union of two sets A and B is a new set, called A ∪ B, which combines the elements of A
and B:
A ∪ B := {x | x ∈ A or x ∈ B}
The intersection of two sets A and B is a new set, called A ∩ B, which contains precisely
those elements which lie in both A and in B:
A ∩ B := {x | x ∈ A and x ∈ B}
One can also form unions and intersections of more than one set at a time
...


i∈I

The complement of a set B in a set A is a new set, called A \ B (“A minus B”), which
contains those elements of A which are not elements of B:
A \ B := {x | x ∈ A and x 6∈ B}

2

1
...
If A, B and C are sets, prove that the following statements are always true:
(a) A ⊂ A ∪ B

(b) A ∩ B ⊂ A

(d) A \ A = ∅

(c) (A ∩ B) ∪ (A ∩ C) = A ∩ (B ∪ C)

(e) A ∪ ∅ = A

(f ) A ∩ ∅ = ∅

2
...
The following is the set of all sets which are not elements of themselves:
S := {x | x 6∈ x}
Does this make sense? Is S and element of itself? What is going on here?!

2

Mathematical Statements

Mathematical statements are claims about mathematical objects which are either true or false
...

Examples:
• A⊂B
is short for “A is a subset of B
...

Whether the statement is true or false depends on whether A really is a subset of B
...

• −3 ∈ N is false
...

Two statements, P and Q are equivalent, written P ⇔ Q, if P is true exactly when Q is true
...

The truth of the statemens x ∈ [−3, 1) and −3 ≤ x < 1 depend on x, but for any given x they are
either both true or both false, that is why they are equivalent
...
1

Combining statements

Mathematical statements can be combined to form longer statements, the truth of which will
depend on the truth of its component statements, and on the way they are combined
...
For example
x > 0 and x ∈ Z
is true precisely when x is a positive integer, i
...
the above statement is equivalent to x ∈ N
...
For example
x>0

or x ∈ Z

is true if x is positive, or if x is any integer (or both)
...

If P is a statement, then its negation, written not P (or ¬P ), is true precisely when P is false
...


2
...

In other words, P ⇒ Q is a statement which means “If P then Q”
...

For example
x > 5 ⇒ x > 2,
because if x > 5 then certainly x > 2 also
...

Implication is transitive, in other words, if P ⇒ Q and Q ⇒ R, then P ⇒ R
...

One strange property of implication is that a false statement implies anything, i
...

False ⇒ P
is true for any statement P , regardless of whether P itself is true or not
...


2
...
Show that the following statements are always true:
(a) (P ⇒ Q) ⇔ (¬Q ⇒ ¬P )

(b) ¬(P ∨ Q) ⇔ (¬P ) ∧ (¬Q)

(c) ¬(P ∧ Q) ⇔ (¬P ) ∨ (¬Q)

3

Mathematical Proofs

Unlike all other fields of study, in mathematics it is possible to prove things completely
...
“Proof beyond reasonable doubt” in a court of law is even weaker
...

A mathematical proof is a series of strict logical steps, where each step is an implication
from something already known to be true (either an axiom, or a previously proved statement)
to a new statement
...
A statement proved in such a manner is called a theorem, although for statements of
lesser importance one also uses the terms proposition or lemma
...
1

Axioms

Any chain of implications has to start somewhere, so before we can prove anything, we must choose
statements which we will accept as true without proof
...
For
example, you may be familiar with Euclid’s axioms from highschool geometry
...
They are merely mathematical statements from which other mathematical statements can
be deduced
...

One must be very careful to choose axioms which do not contradict each other, even very
indirectly - we say that the axioms must be consistent (technically this means that it must
not be possible to prove both a statement and its negation)
...

The precise axioms on which modern mathematics is based are beyond the scope of this course
(they are the Zermelo-Fraenkel axioms of set theory), but here is one axiom we will use later:
Axiom 1 (Well-ordering Principle) Every non-empty subset of N has a least element
...
This certainly makes sense
...


3
...
The first few prime numbers are 2, 3, 5, 7, 11, 13, 17,
...

Proof
...
There are two options:
• A = ∅, or
• A 6= ∅
...
We will eliminate the other option, A 6= ∅, by showing that it
leads to a contradiction (it implies a false statement, hence must itself be false):
Suppose A 6= ∅
...
This n cannot
be prime, since n divides n, and n ∈ A means that n is not divisible by any primes
...
Since m < n, and n is the smallest element of A, it follows that m 6∈ A
...
Call this prime
number p
...
But this implies that p divides n, which is
impossible, since n ∈ A
...
This completes the proof
...
3

Proof techniques

There are several standard techniques used in proofs
...
3
...
For example:
Theorem 2 The sum of two odd integers is an even integer
...
An integer is odd if it can be written in the form 2n + 1 for some n ∈ Z
...
Now (2n + 1) + (2m + 1) =
2n + 2m + 2 = 2(n + m + 1), which is even
...
3
...
In other words, if
we want to prove a statement P , we show that ¬P implies a statement which is false
...

We used this technique in our proof of Theorem 1: We assumed that A 6= ∅ (i
...
that there
exist positive integers greater than 1 which are not divisible by prime numbers), and deduced a
contradiction from this
...

Here is another example:
√
Theorem 3 2 is irrational
...
Suppose that 2 is rational, i
...
that 2 = m
n for some m, n ∈ Z, n 6= 0
...
e
...
Squaring both sides give 2 = n2 , so m = 2n2
...
Hence we can write m = 2k for
some k ∈ Z, and so 2n2 = m2 = (2k)2 = 4k 2
...
This
means that n2 is even, which in turn implies that n itself is also even
...

This
contradiction
shows
that
our
assumption
(that
2 is rational) is wrong
...


Here is yet another example (which dates back to Euclid, some 2300 years ago):
Theorem 4 There are infinitely many prime numbers
...
Suppose that there are only finitely many prime numbers, and let p1 , p2 ,
...
Consider the number N := p1 · p2 · · · pn + 1, the product of all primes, plus one
...
But
this means that N is not divisible by any prime number, and certainly N > 1
...
This is a contradiction, hence
our assumption (that there are only finitely many primes) must be false
...


3
...
3

Mathematical induction

A proof by mathematical induction is a clever way of using Axiom 1 (the well-ordering
principle)
...
e
...
In other words, assuming that Sn holds true (for some n ∈ N we’re not assuming this for all n), deduce that Sn+1 must also hold true
...

Thus S2 is true (this follows from (ii), using the fact that S1 is true)
...

Thus S4 is true (this follows from (ii), using the fact that S3 is true)
...

One can compare this to knocking over a line of dominoes: (i) says that the first domino falls
(perhaps because you tipped it with your finger), and (ii) says that any domino that falls will
knock over the one behind it
...

Example:
Theorem 5 For all n ∈ N we have
1 + 2 + 3 + ··· + n =

n(n + 1)

...
Let Sn denote the statement 1 + 2 + 3 + · · · + n = n(n+1)

...

2
1(1+1)
But S1 is the statement 1 = 2 , which is true
...
We want to deduce Sn+1 , which says that
1 + 2 + · · · + (n + 1) =

(n + 1)(n + 2)

...
Therefore, the theorem follows by mathematical induction
...

For suppose (i) and (ii) above hold, and let
A := {n ∈ N | ¬Sn }
be the set of all n ∈ N for which Sn does not hold
...
From (i) follows
that 1 6∈ A
...
Write m = n + 1
with n ∈ N, which we can, because m ≥ 2
...
But now (ii) asserts that Sn ⇒ Sn+1 , so Sn+1 is true, which is a
contradiction
...


3
...
4

Counter-examples

Remember that to prove a statement like Theorem 5 above it is not enough to give a handful of
examples of numbers n for which the statement is satisfied
...
If a statement seems to be true in a number of cases then one can
start looking for a proof
...
For example
the statement
√
x∈N⇒ x∈Q
is false
...
So it
is often much easier to disprove a false statement than to prove a true statement
...
4

Where do proofs come from?

Proofs are found (created? discovered?) by human beings, and you can learn to do this, too!
3
...
1

Two stages of proof

There are two very different stages in finding a proof of a theorem
...
It involves coming up
with some clever ideas, some “reasons for which the theorem is true”
...

The second stage is very logical and pedantic (and uses mostly the left brain hemisphere)
...

These steps must be written in such a way that the reader can verify each step, and be satisfied
at the end that the proof is correct and thus the theorem is true
...

The exact amount of detail required at the second stage depends very much on the intended
reader
...
Such a proof is called a formal
proof, and is usually so long (and painful to read), that formal proofs are rarely written down in
practice
...
Since the intended readers are
expert researchers in that particular area of mathematics, one can expect the readers to take
fairly large steps, and basically be able to fill in much of the detail themselves
...

If the intended reader is a student (or the professor marking an exam!), then the level of detail
required falls between these two extremes
...
This is the level of detail presented in the
example proofs in these notes
...

When reading a proof, try to understand the underlying ideas behind the proof (the clever ideas
from the first stage above)
...
But when you have understood these ideas, you have understood
the proof
...

3
...
2

An example

As an example, consider the following alternate proof of Theorem 4, which states that there are
infinitely many prime numbers
...
Some proofs can be simpler or more beautiful than others, and different proofs might
lead to different insights)
...
This means that, for any n ∈ Z, n and
n + 1 share no common factors
...
The clever
8

idea is to repeat this trick with n(n + 1) – since n(n + 1) and n(n + 1) + 1 are relatively prime,
and n(n + 1) is divisible by at least two different primes, their product n(n + 1) · [n(n + 1) + 1]
must be divisible by at least three different primes
...
Hence there must be
infinitely many primes
...
We can simplify matters by observing that any n > 1 will do in the above argument, so we can pick n = 2
...
So in
our proof we will define the sequence of integers 2, 6, 42,
...
We need a name for our sequence of numbers, we’ll call them a1 , a2 , a3 ,
...
This we can do using induction,
since am+1 = am (am + 1), we can use information about am to make deductions about am+1
...
Consider the sequence of natural numbers defined by a1 := 2
and am+1 := am (am + 1) for m ∈ N
...

Next, suppose that Sm holds for some m ∈ N, so am is divisible by at least m distinct primes,
call them p1 , p2 ,
...
We want to show that Sm+1 holds
...
Since am + 1 > 1 it is divisible by some prime number, which we’ll call
pm+1 (by Theorem 1), but this prime cannot be one of the divisors pi of am , since am and am + 1
have no common factors
...
, pm+1 , which
are m + 1 distinct prime numbers
...

Hence, by mathematical induction, Sm must be true for all m ∈ N
...


3
...
3

Exercises

1
...

(b) xn − 1 is divisible by x − 1 for all n ∈ N
...

2
...
For
starters, let
n
Fn := 22 + 1,
n ∈ N ∪ {0}
...

(a) Use induction on n to prove that, for all n ≥ 0,
F0 F1 · · · Fn = Fn+1 − 2
...

(c) Deduce from (b) above that there must be infinitely many prime numbers
...
The following theorem is called the Pigeonhole principle:
9

If you put n + 1 balls into n boxes (n ∈ N), then at least one box will contain at
least two balls
...

4
...
Given that nobody has more than
1,000,000 hairs on his or her head, show that there exist two people in Cape Town who both
have the same number of hairs on their head
...
Consider the following claim:
For all n ∈ N, given n lines in the plane, no two of which are parallel to each other,
all lines must pass through a common point
...

(b) What’s wrong with the following “proof” of the above claim?
Proof
...
The claim is clearly true if n = 1 (and even if n = 2 :
two non-parallel lines will pass through the same point)
...
So consider n + 1 lines
in the plane, no two of which are parallel
...
Last last n of these lines also pass through
a common point for the same reason
...
Therefore all the
lines must pass through a common point, which is what we wanted to prove
...



10



---