Transcript Session 8: Formalization

Philosophy of Mathematics
Formalisation
• In the last session we looked at several familiar number
systems: the naturals, integers and rationals.
• We also briefly introduced the idea of the real numbers,
which are designed to represent the points on a
continuous line.
• These are at least the rationals plus all the irrationals we get
by taking square roots, cube roots and so on; maybe others,
too, who knows?
• But the real numbers are a lot stranger than the more
familiar ones. We can easily make mistakes if we rely on
our intuition to guide us.
Quick Recap
• Usually we just use numbers as if they were all given to us in a
lump. But it helps to sort them out and be clear about which
ones we need for different jobs.
• The natural numbers, ℕ, are the basic counting numbers.
• This is fine if you just want to add and multiply.
• The integers, ℤ, are the negative and positive whole numbers,
plus zero.
• This is handy if you want to be able to subtract.
• The rationals, ℚ, are the positive and negative fractions, plus
zero.
• Here we can also divide.
• The reals, ℝ, are the numbers you need to identify the points
in a continuous line. Question: are the reals and the rationals
the same numbers?
Know Your Number System!
PART 1: MOTIVATION
What was wrong with maths around 1800?
• It had been known since the time of the ancient Greeks
that √2 can’t be expressed as a fraction – at least not
exactly.
• In modern terms we say it’s “irrational” – meaning it isn’t
found among the rational numbers.
• The real numbers are supposed to contain “all the
numbers we need” – rational and irrational alike.
Irrationality of √2
• Even worse is the Dirichlet function (1829): f(x) = 1 if x
is rational, 0 otherwise.
• At first blush it’s not clear what’s going on with this
function at all. We can’t even draw a graph of it.
• In fact we can prove (with a suitable theory) that the
Dirichlet function is nowhere continuous. This is indeed a
strange property.
Dirichlet Function
• Early analysts were concerned with finding technical solutions to
practical problems arising from the rapid development of the
calculus:
•
•
•
•
•
•
Augustin Louis Cauchy (1789–1857),
Bernhard Bolzano (1781–1848),
Niels Henrik Abel (1802–1829),
Peter Lejeune Dirichlet (1805-1859)
Karl Weierstrass (1815–1897)
Bernhard Riemann (1826–1866)
• A little later, in response to their work, focus fell on the nature of
number and of the continuum and the project became philosophically
deeper:
•
•
•
•
Leopold Kronecker (1823-1891)
Richard Dedekind (1831-1916)
Georg Cantor (1845-1918)
Giuseppe Peano (1858-1932)
Analysis in the C19
• This idea is associated with Bolzano in the early C19:
• “Every nonempty set bounded above has a least upper bound”
• This is not a property of the rational number system ℚ.
• Consider the set of all numbers whose square is less than 2. This is
clearly bounded above by 2, but given a rational upper bound (an
approximation of 2 that overestimates it) we can always find
another, smaller one (a better approximation that also overestimates).
• As we know, 2 itself isn’t available in the rational number system.
• We can try to define the real number system ℝ with this axiom.
• If you’re interested in this, the thing to search for is “Dedekind cut”.
• In fact it turns out that it really is the only number system that
satisfies it plus a few other criteria (technically, ℝ is a complete
ordered field).
• But this is very indirect and may very well look like a trick – it seems
as if we’ve magicked the irrationals into existence.
Axiom of Completeness
• Cauchy’s Cours d’Analyse of 1821 can be thought of as the
first attempt to write a textbook in rigorous analysis. It was
hugely influential.
• Note the date: this is just the time when Dirichlet is pointing to
problems in the foundations of Fourier’s use of calculus to solve
the heat and wave equations.
• We’ll focus on the idea of a continuum of points, not on
continuity of functions. The ideas are basically the same, but
clearer in the former case.
• Here is a modern definition of continuity of a sequence in the
spirit of Cauchy (notice: no mention of limits!):
Cauchy’s Version of Convergence
• We can define a sequence of rationals that converges to 2
• We can use Cauchy’s definition to show that this sequence
converges… but to what? A missing number! For 2 doesn’t
exist in our number system ℚ.
• A modern definition of the real numbers is that they are the
limits of Cauchy sequences in ℚ. But again, this may seem like
a conjuring trick.
• Here is a way to make it a bit clearer: suppose we have all the
possible Cauchy sequences in ℚ, and suppose we gather them into
classes such that in each class, all the sequences have the same
limit. Then a real number just is one of these classes.
• Note that every real number is then an infinite set!
• But this seems to do quite a bit of violence to what we think a
“number” ought to be…
A Definition of the Reals
A sequence of rational numbers that converge to 2.
• Note that the reals are at least as big as the natural
numbers, because we can make a surjective map ℝ → ℕ
(just “round down” each real number to the natural
number below it).
• This isn’t surprising; after all, ℝ contains a copy of ℕ
(these are the reals with an infinite string of zeroes after the
decimal point).
• Using the definition in terms of Cauchy sequences, it
turns out we can represent a real number as an infinitely
long decimal.
• For simplicity we’ll just try to count the real numbers
between 0 and 1: that is, the number of points on a finite
line segment of unit length.
The Real Numbers
• In ℚ: Between any two rational numbers we can find
another rational number. We say the rationals are dense.
• This is already weird: it suggests that no two points that
make up the continuum are “next to each other”.
• Think of Leibniz’s picture of an abyssal continuum whose
every tiny part contains whole universes.
• In ℝ, something slightly weirder happens:
• Between any two real numbers we can find a rational
number. We say the rationals are dense in the reals.
• Between any two real numbers we can find an irrational
number. We say the irrationals are dense in the reals.
• Store this away for now as it gets much more strange
when we start counting these numbers (next week).
Density
PART 2: FORMALIZATION
The proposed solution to all these problems
• Actual infinities pose a serious problem: they’re difficult
to think about and it’s easy to be led into absurdities (i.e.
contradictions).
• Kant’s antinomies warm us about this: for him, there are
limits beyond which reason can go, but knowledge can’t.
• Yet infinities lurk at the heart of much mathematics,
including the calculus that underpins almost all of modern
physics.
• Can we find a way to think about them that’s robust enough
to save us from both absurdity and ignorance?
• Can questions like the Continuum Hypothesis be decided
ion a principled way, or do they simply lie beyond what
anyone’s capable of knowing?
The Need for Rigour
• In modern terminology, every statement in Euclid’s Elements belongs
to one of the following:
•
•
•
•
An axiom – that is, a definition or something taken to be basic.
A rule of reasoning that allows you to make deductions.
A theorem – that is, something claimed to be true.
A proof – that is, an argument showing that the theorem necessarily
follows from the axioms.
• The axioms are as minimal as possible.
• If you don’t agree with them, nothing in the Elements works for you.
• A valid proof shows why you’re forced to accept the theorem if you
accept the axioms and follow the rules of reasoning.
• The axioms and rules should therefore be “intuitively true” in some
sense.
• A lot of high-powered C18 and C19 mathematics has abandoned this
approach. It sets a very high standard but appears to be too difficult
(or at least too slow) for advanced problems.
The Axiomatic Method
• A formal language isn’t much like
a “natural” language like English
or French.
• Nor does it look like the kind of
mathematics human beings do.
• It looks more like the kind of code
a computer might use.
• It consists of:
• a restricted set of symbols;
• A set of rules for combining them
to make expressions;
• Another set of rules for combining
expressions to make proofs.
Formal Languages
• What we’ve just described is syntax: mere symbol-shuffling.
• We like to think there’s another layer: the meaning of the
symbols. This is their semantics.
• Without this, a formal language is just a kind of abstract game. To
matter to us, it must be about something.
• Still, we can use it to state (purely abstract) axioms and proofs of
theorems.
• Given a set of formally-encoded axioms, the set of all the
theorems we can prove from them is called their theory.
• This is captured more formally by the idea of an interpretation
of the pure symbolic syntax.
• We find a model – something outside the theory that it’s
suppposed to be “about”.
• Then we map the symbols of the language, one by one, onto
features of the model.
Syntax vs Semantics
• A theory is consistent if it doesn’t prove any
contradictions.
• If you can produce a proof of “P” and of “not P”, the theory
is inconsistent.
• Assumption: if a theory is inconsistent, it has no model.
• That is, there are no “real” contradictions.
• It follows that if a theory demonstrably has a model, it’s
consistent.
• Ex falso quodlibet
• It’s a feature of classical logic that if you can prove a
contradiction, you can use that contradiction to prove any
other statement you like, even if the two have nothing to do
with each other.
Contradiction
• Suppose we, who are working in a formalized language, have a
theory that we interpret as being about sea creatures.
• Suppose this theory can prove “Whales are fish” and also, by a
different line of argument, “Whales are not fish”.
• We may now prove “Humans are fish” as follows:
• “Whales are fish” is true, so “Either whales are fish or humans are
fish” is also true.
• This is because “either X or Y” is true if X is true, regardless of
whether Y is true.
• But “Whales are not fish”
• Well, “Either whales are fish or humans are fish” and “Whales are
not fish”. So it must be that humans are fish!
• This is because when “either X or Y” is true and X is false, Y must
be true.
• Nobody thinks this is a good proof that humans are fish. But
it’s not so easy to point to one step that causes the trouble.
• If we’re going to express mathematics formally, that had better
include the basic system of whole-number arithmetic before trying to
do all the fancy bits.
• This already includes non-trivial things like Goldbach’s Conjecture.
• First-Order Peano Arithmetic gives a simple formal theory that
“obviously” has the arithmetic of the natural numbers as a model.
That is, its axioms are explicitly chosen for that purpose.
• Most of it is uncontroversial, but we do need to add some machinery
to do induction, which is how we get to prove a statement like “every
even number is the successor of an odd number”.
• Without induction, we can prove for any particular even number, that
it’s the successor of an odd number; we just can’t prove it for all of
them at once.
• This is a direct consequence of the fact that there are infinitely many
of them, and it’s where the trouble starts.
Peano Arithmetic
• Naïve set theory includes the Principle of Comprehension.
• Anything is a set that can be described by a suitable formal
language that can be interpreted as making consistent
statements about sets and their elements.
• This was, broadly speaking, Frege’s approach in his attempts to
express arithmetic purely in terms of set theory (actually it’s more
complicated than that, but we’re close enough).
• The PoC licenses us to declare:
• “S is the set of all sets that don’t contain themselves”
• S is a contradictory object; any theory that allows this sentence to
be proved is absurd: ex falso quodlibet.
• Yet we don’t need much “machinery” to do it: just the ability to
refer to sets and what they include.
Russell’s Paradox
• Extensionality: Two sets that have exactly the same elements
are the same set.
• Regularity: All sets are well-founded.
• Replacement: This is an axiom schema that allows us to “build
up sets from other sets” by saying things like “X is the set of
all x such that…” without falling into Russell’s Paradox.
• You’ll sometimes see an “Axiom of Separation” as an
alternative.
• Null set: there exists a set of which nothing is an element
• Unordered pairs: given sets x and y, there exists a set {x, y}
• Union: given sets x and y, x union y exists.
• Power set: given x, its power set exists.
• Infinity: A specific infinite set exists.
A Version of the ZF Axioms
• This axiom guarantees the existence of a set that can be
interpreted as “the set of natural numbers”.
• There are various ways to build sets that can be interpreted as
natural numbers – the details aren’t important.
• This axiom plays a similar role to induction in Peano Arithmetic.
• Without it we have finite set theory, which would appear to be a
theory of the potential infinite only.
• It can say “this even number is the successor of an odd number”
for any even number you choose.
• It can say “in this set of even numbers, every one is the successor
of an odd number” for any set of numbers you like, however large.
• But it can’t say “every even number is the successor of an odd
number”.
• The point to note is that we can’t get our first infinite set just
by juggling with finite sets. We must “import” or “assert” it.
The Axiom of Infinity
• “Real” mathematics is given to us in (Kantian) intuition. Facts like
2+2=4 are really facts and we can know and prove that they’re true
from first principles (a priori).
• Is all mathematics “real” in this sense? In particular, what about
calculus (which relies on the continuum) and Cantor’s set theory with
its multiple sizes of infinity?
• Perhaps this lies outside the bounds of knowledge, in the pure play of
reason where antinomies are possible. Hilbert hopes not, though!
• The way to draw this boundary is to reconstruct as much mathematics
as possible formally, with great rigor and care, out of elements like
basic arithmetic that are undoubtedly part of our immediate intuition.
• To proceed rigorously we need axioms for each field of maths.
• But in the more exotic fields, how can we tell our axioms are wellformed, i.e. that they don’t give rise to a contradictory theory?
• We must prove it. Mathematics owes us a proof of its own
consistency.
Hilbert’s Programme
1. Express statements about infinite objects as finite
strings of symbols in a precisely-defined formal
language.
2. Express rules of inference as precisely-defined
operations on symbol strings.
3. Derive theorems from the axiom strings by finitely
many applications of rules of inference.
4. Prove that the rules of inference produce no
contradictory sentence, by purely finite reasoning about
strings of symbols.
Hilbert’s Programme
Hilbert wrote these words in 1922, responding to the
intuitionist programme of Weyl, Brouwer and others.
His aim, then, is to preserve the achievements of the C19
against skepticism and paradox.
• This formal language uses letters to represent propositions, such as
“Whales are fish”.
• The built-in symbols, besides letters, are ¬ (“not”), | (“or”) and &
(“and”), along with parentheses “(“ and “)”.
• The rules for forming expressions are:
•
•
•
•
•
Every letter on its own is an expression
If X is an expression, so is ¬(X)
If X and Y are expressions, so is (X | Y)
If X and Y are expressions, so is (X & Y)
Nothing else is an expression
• We then need a set of rules for combining expressions into proofs. These
are usually pretty short but in the interests of space we won’t set this out
here.
• Here is the proof we just did on the previous slide:
P
(P | Q)
¬(P)
(¬(P) & (P | Q))
Q
Propositional Logic
• Predicate logic allows us to “break apart” propositions a bit.
It’s a bit more complicated as a result.
• To express “Whales are fish”, we might write
∀(𝑥)(𝑤 𝑥 → 𝑓 𝑥 )
• Which we would read aloud as “for every creature, x, if x is a
whale (“w(x)”) then x is a fish (“f(x)”).
• Predicate logic gives us a way to express mathematical
statements. For example, let’s change the model:
• Let the variable, x, range over the natural numbers instead of
animals.
• Let w(x) mean “x is an even number greater than 2”
• Let f(x) mean “x is the sum of two prime numbers”
• Now our symbols express Goldbach’s Conjecture!
Predicate Logic