Fundamentals of Pure Mathematics - St Andrews

Fundamentals of Pure Mathematics

Kenneth Falconer

Martinmas Semester 2010-11

About the Course

In this course we shall mostly talk and think about numbers, working carefully from definitions. The course will have the following components:

1. Proof and Mathematical Argument 2. Sets, Relations and Functions 3. Construction and Properties of Number Systems 4. Some Number Theory 5. Countability If you wish to read further about various topics covered in this course and related to the course, the following books may be helpful (note that the texts are for further reading and it is certainly not compulsory to buy them). I. Stewart and D. Tall, The Foundations of Mathematics, Oxford University Press, 1977;

QA107.S8T2. M. Liebeck, A Concise Introduction to Pure Mathematics, Chapman & Hall/ CRC, 2000;

QA8.4L5. H.-D. Ebbinghaus et al., Numbers, Springer-Verlag, New York, 1991; QA241.E3E8. All three books are available on short loan in the Mathematics and Physics Library. The assessment for the course will be by a 2 hour exam in January.

1 Proof and Mathematical Argument

Writing mathematics clearly and carefully becomes increasingly important as you get further into the subject. Advanced mathematical arguments can have a complicated logical structure, and this structure must be clear to any reader (and even more importantly to the writer!).

1

In particular, written mathematics should not just be a list of equations but should make clear

their logical relationship to each other. The careful use of words to express such relationships is important. For example, writing "x 1, x2 x" is ambiguous, but "For all x 1 we have x2 x" makes clear what is intended.

Styles of mathematical writing vary considerably. You should develop your own style using

words as well as symbols, to make your arguments as clear as you can.

1.1 Implication

The notion of implication is fundamental in any mathematical argument. If A and B are state-

ments then "A implies B" (in symbols A B) means that whenever A is true B must also be

true. For example:

x = 2 implies x2 = 4.

Implication may be indicated in a variety of ways, such as:

A implies B, A B, B is implied by A, If A then B, B if A.

It is crucial to realise that "If A then B" and "If B then A" mean very different things. "If x = 2 then x2 = 4" is true, but "If x2 = 4 then x = 2" is false (x might be -2).

However, sometimes two statements A and B are each implied by the other, in which case we say "A and B are equivalent" (in symbols A B). Ways of writing this include:

A is equivalent to B, A B, A implies and is implied by B, A if and only if B, A iff B, A is a necessary and sufficient condition for B.

For example, "x2 = 4 if and only if x = 2 or x = -2". Note that if you are asked to show that A holds if and only if B holds you have to do two things.

1.2 Proof

A proof is a careful argument that establishes a new fact or theorem, given certain assumptions or hypotheses. There are various kinds of proof, some of which we mention here.

Proof by deduction A deductive proof consists of a sequence of statements or sentences each of which is deduced from previous ones or from hypotheses using standard mathematical properties. The final statement may be called a theorem. For example:

Theorem 1.1. If x2 - 3x + 1 < 0 then x > 0.

Deductive proof. Assume that x2 - 3x + 1 < 0. Then 3x > x2 + 1 (rearranging the inequality),

which

implies

that

3x

>

1

(since

x2

0).

It

follows

that

x

>

1 3

(dividing),

so

x

>

0

(by

the

order

property).

[Note that in this argument each step may be deduced from the previous one by a standard mathematical fact. However, the steps are not all reversible.]

2

Proof by contradiction Sometimes it is easier to argue by contradiction, i.e. to assume that the desired conclusion is false and derive a contradiction to some known fact.

Theorem 1.2. If x2 - 3x + 1 < 0 then x > 0.

Proof by contradiction. Assume that x2 - 3x + 1 < 0 and suppose that x 0. Then x2 < 3x - 1 3 ? 0 - 1 (rearranging and using x 0), so x2 < -1, which contradicts that the square of a real number is non-negative. We conclude that x > 0.

Counter-examples To show that a statement is false it is enough to give a single instance for which it does not hold, called a counter-example.

For example, the statement "x2 -4x +1 > 0 for all x > 0" is false. To see this we simply note that 22 - 4 ? 2 + 1 = -3 0, so that x = 2 is a counter-example to the statement. In particular, to demonstrate falsity there is no need to `solve the inequality'.

1.3 Mathematical Induction

Mathematical induction is a more sophisticated method of deductive proof used to derive formulae and facts throughtout mathematics. Induction is a method of proving statements involving the natural numbers 1, 2, 3, . . .. The idea is that (i) we prove the statement when n = 1 and (ii) show that if the statement is true for some integer n then it is true for the integer immediately above. From this we can conclude that the statement is true for all n = 1, 2, 3, . . .. Formally:

The Principle of Mathematical Induction. Let P(n) be a statement depending on an arbitrary positive integer n. Suppose that we can do the following two steps:

(i) Verify that P(1) is true, (ii) for all positive integers n, show that if P(n) is true then P(n + 1) is true. Then the statement P(n) is true for all positive integers n.

The statement P(n) is called the inductive hypothesis, step (i) is called starting the induction or anchor and step (ii) is called the inductive step.

Note that the Principle of Induction is intuitively obvious: if P(1) is true and P(n) P(n + 1), that is the truth of P(n) implies the truth of P(n + 1) for all n = 1, 2, 3, . . ., then

P(1) P(2) P(3) . . . P(n) . . . by applying (ii) with n = 1, 2, 3, . . . in turn, so P(n) is true for all n.

Example 1.3. (Summation of series). For every positive integer n

n(n + 1)

1+2+...+n =

.

2

3

Proof

by

induction.

Let

P(n)

be

the

statement:

1+2+...+n =

n(n+1) 2

.

Then

1=

1(1+1) 2

,

so

P(1) holds, which starts the induction.

Now assume that P(n) is true for some positive integer n. We relate the sum in P(n + 1) to

that in P(n):

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

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

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

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

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

(using P(n))

which is the statement P(n + 1), completing the inductive step. Thus by the Principle of Induction P(n) is true for all positive integers n.

Example 1.4. Use induction to show that 9n - 2n is divisible by 7 for all positive integers n.

There are many variants on the Principle of Induction. For instance we may wish to start at an integer other than 1. Thus if for some integer n0 we can show

(i) that P(n0) is true, and (ii) for all n n0 that if P(n) is true then P(n + 1) is true, the Principle of Induction gives that P(n) is true for all n n0.

Sometimes we need to use that P(k) is true for all k n to deduce P(n + 1). Thus if we can show

(i) that P(1) is true, and (ii) that if P(k) is true for all k n then P(n + 1) is true, then P(n) is true for all n 1., This is called strong or total mathematical induction.

Recall that an integer n 2 is a prime number if is cannot be expressed as a product of integers n = rs with r > 1 and s > 1.

Theorem 1.5 (The Fundamental Theorem of Arithmetic). Every natural number n 2 is a

product of prime numbers, i.e.

n = pk11 pk22 . . . pkmm,

for some distinct primes p1, . . . , pm and natural numbers k1, . . . , km. Moreover, up to the order of the pi, this decomposition is unique.

Proof by induction. Let P(n) be the statement: n may be expressed as a product of primes. Since 2 is prime, P(2) is true, which starts the induction.

Now assume that for some n 2, P(k) is true for all integers 2 k n. Consider the integer n + 1. Either n + 1 is prime (so a product of a single prime factor) or n + 1 = rs where r > 1 and

4

s > 1. In the latter case 2 r, s n, so by P(r) and P(s) both r and s are products of primes, so n + 1 = rs is a product of primes. Thus P(n + 1) is true, completing the inductive step.

To show uniqueness we use the fact that if the integer a divides bc and a and b have no common prime factor, then a divides c; we omit the details here.

Induction is a general method that is used in virtually every area of mathematics. Further examples include complex numbers (e.g. for a proof of de Moivre's theorem), finding powers of matrices, terms of sequences, in number theory, graph theory, group theory, mathematical logic, . . . .

2 Sets, Relations and Functions

2.1 Sets

Today all of Mathematics is expressed in the language of sets ? in a certain sense, the concept of a set is even more fundamental than that of a number.

For the main part of the course, we will simply take a set to be a collection of object which we term the members or elements of the set. Generally we use capital letters to denote sets and small letters to denote elements. We write a A to mean that an element a belongs to a set A and a A to mean it does not belong to A. We sometimes write {? ? ? } for the set containing the elements ? ? ? . Here are some of the standard sets used in mathematics:

Z = {. . . , -3, -2, -1, 0, 1, 2, 3, . . .} the Integers

Q = {p/q such that p, q Z, q = 0} the Rationals

R = the Real Numbers

C = the Complex Numbers N = Z+ = {1, 2, 3, . . .} the Natural Numbers or Positive Integers Q+ = the Positive Rationals, etc.

the Empty Set or Null Set, i.e. the set with no elements.

We write

{x : Property involving x} or {x| Property involving x}

to mean "the set of x such that the Property involving x holds". For a common example:

[a, b] = {x : a x b} and (a, b) = {x : a < x < b}

denote the closed and open intervals of real numbers between a and b. Two sets are said to be equal (A = B) if they consist of precisely the same elements. In other

words A = B if and only if every element of A is also an element of B and every element of B is

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download