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?)