1Proofs and logic

IA Numbers and Sets

1.1 Proofs

As the first course in pure mathematics, we will have an (informal) look at proofs

and logic.

In mathematics, we often want to prove things. This is different from most

other disciplines. For example, in science, we perform experiments to convince

ourselves that our theory is correct. However, no matter how many experiments

we do, we still cannot be absolutely sure that our theory is correct. For example,

Newtonian mechanics was believed to be correct for a long time, but is nowadays

only considered to be an approximation of reality.

On the other hand, when we prove a theorem in mathematics, we are

completely sure that the theorem is true. Also, when we actually prove a

theorem, (hopefully) we can also understand why it is true, and gain further

insight.

Definition

(Proof)

.

A proof is a sequence of true statements, without logical

gaps, that is a logical argument establishing some conclusion.

To prove things, we need to start from some assumptions. These assumptions

are known as axioms. When we call something an axiom, it does not mean that

we take these statements to be true without questioning. Instead, we are saying

“if we assume these axioms, then these results hold”. Two people can disagree on

what the axioms are and still be friends.

We also tend to define concepts as unambiguously as possible. Of course, just

like a dictionary cannot define all words without being circular, we do not define

everything in mathematics. To prove things, we have to start somewhere, with

some agreed assumptions (axioms). We also don’t define everything rigorously

(or else how could one start speaking?).

In mathematics, we are often concerned about truth. Often, we only care

about statements that can take some truth value.

Definition

(Statement)

.

A statement is a sentence that can have a true value.

Example. The following are statements:

(i) There are infinitely many primes of the form n

2

+ 1

(ii) There is always a prime number between n and 2n

(iii)

There is no computer program that can factorize an

n

-digit number in

n

3

steps

(iv)

For every polynomial

p

(

x

) =

a

n

x

n

+

a

n−1

x

n−1

+

···

+

a

0

, where

a

i

are

complex numbers,

n ≥

1,

a

n

6

= 0, there exists (possibly complex)

z

such

that p(z) = 0

(v) m × n = n ×m for all natural numbers n, m

(vi) 2 + 2 = 4

The current status (as of 2015) of these statements are:

(i) No one has a proof but it is probably true

(ii) This is known to be true

(iii) No one knows (related to P = NP problem)

(iv) This is known to be true (Fundamental Theorem of Algebra)

(v) This is known to be true

(vi) This is known to be true (obviously — does this need to be proved?)