Transcript LOGIC, NUMBER THEORY AND THE LIMITS OF HUMAN REASON

LOGIC,
NUMBER THEORY
AND
THE LIMITS OF
REASON
M. Ram Murty
Queen’s Research Chair
Queen’s University, Canada
What is a number?
 Counting is basic to all civilizations.
 From the Babylonians onwards, there are
many notations for the natural numbers.
 The place value number systems were
discovered by only four cultures.
 They are the Babylonians, Mayans,
Chinese and the Indians.
ZERO
 The Babylonians, the Mayans and the Indians
were the only ancient civilizations with a symbol
for zero.
 However, it was only in the Indian civilization
that zero was treated as a number and rules
were given about how to work with it.
 In his work Brahmasphutasiddhanta, written in
600 A.D., Brahmagupta gave the first modern
treatment of the algebraic rules for zero.
Aryabhata
 Aryabhata was the first to
use the decimal system
for calculations.
 He was also the first to
introduce algebraic
notation.
 He also was the first to
propose a heliocentric
model for the solar
system.
Aryabhata (476-550 A.D.)
Aryabhatiya written in 499 A.D.
Diophantine Equations
 Arybhata studied ax + by = c for given a,b and c.
He was interested in finding integer solutions x
and y for this equation.
 His successor Brahmagupta considered the
equation ax² + by²=c and discovered a
remarkable algorithm to generate integer
solutions.
 This work was expanded later by Jayadeva and
Bhaskaracharya.
 Such equations are called Diophantine
equations after Diophantus who first studied
them.
A page from the Brahmasphutasiddhanta
A page from the Lilavati
Can we always solve a Diophantine
equation?
 This is a question we will discuss later.
 The early Indian mathematicians have
shown that for small degree equations, it is
possible to solve them.
 But what happens for higher degrees?
 It is remarkable that these questions were
raised in antiquity in ancient India.
The discovery of numbers
``The astonishing progress that the
Indians made is now well known and
it is recognized that the foundations
of modern arithmetic and algebra
were laid long ago in India. The
clumsy method of using a counting
frame, and the use of Roman and
such numerals had long retarded
progress when the ten Indian
numerals including the zero sign
liberated the human mind from these
restrictions and threw a flood of light
on the behavior of numbers. …They
are common enough today and we
take them for granted, yet they
contained the germs of revolutionary
progress in them. It took many
centuries for them to travel from
India, via Baghdad, to the western
world.’’ –The Discovery of India.
Jawaharlal Nehru (1889-1964)
Fibonacci
 Fibonacci introduced
the decimal system
into Europe in 1200.
 It took another four
centuries for the
system to be
commonplace in the
Western world.
Fibonacci (1170-1250)
 ``It is India that gave us
the ingenious method of
expressing all numbers
by means of ten symbols
… a profound and
important idea which
appears so simple now
… but its very simplicity
… puts our arithmetic in
the first rank of useful
inventions and we shall
appreciate the grandeur
of this achievement
when we remember that
it escaped the genius of
Archimedes and
Apolonius, two of the
greatest men produced
by antiquity.’’ -Laplace
Pierre Simon de Laplace (1749-1827)
 Plato believed that
numbers are ideal
entities existing
independently of the
human mind.
 Einstein wrote that
numbers are a
creation of the human
mind that simplify the
ordering of sensory
experience.
Pythagoras
 Pythagoras saw a
deep connection
between the
natural world and
the world of natural
numbers.
Pythagoras (569-475 BC)
Baudhayana Sulva Sutras
 The theorem
usually
attributed to
Pythagoras is
found in these
sutras written
around 800
B.C.
Mathematical laws
 Since antiquity, many mathematical laws have




been discovered suggesting that somehow
mathematics has been woven into the fabric of
the universe and one cannot separate it.
This feeling led Pythagoras to say “everything is
number.”
Music and numbers are closely related too.
The geometry of the universe was linked to
numbers.
This led Plato to say “God is a geometer.”
 “The enormous
usefulness of
mathematics in the
natural sciences is
something bordering on
the mysterious and there
is no rational explanation
of it.” in “The unreasonable
effectiveness of mathematics in the
natural sciences’’
Eugene Wigner (1902-1995)
 ``How is it possible
that mathematics, a
product of human
thought that is
independent of
experience, fits so
excellently the
objects of physical
reality.’’ in Sidelights on
Relativity.
Albert Einstein (1879-1955)
Leibniz’s Dream
 Leibniz dreamed of a
universal language and
some sort of “calculus
of reason” which would
reduce all problems to
numerical computation.
Leibniz (1646-1716)
George Boole
 In 1848, Boole wrote a
paper entitled “The
calculus of logic” in
which he begins “I
have exhibited the
application of a new
form of mathematics to
the expression of the
operations of the mind
in reasoning.”
George Boole (1815-1864)
The Ladder of Infinity
 The numbers 1, 2, 3, … are countable.
 They are in one-to-one correspondence
with 1, 1/2, 1/3, …
 Both sets are infinite.
 How many numbers are there between 0
and 1?
Cantor and Infinity
 Discovered different
orders of infinity
 The natural numbers
are countable
 The real numbers
are uncountable
 The continuum
hypothesis
Georg Cantor (1845-1918)
The continuum hypothesis
 Given any infinite set of numbers between
0 and 1, it is either countable, that is, can
be put in one-to-one correspondence with
the natural numbers or it can be put in
one-to-one correspondence with all the
numbers between 0 and 1.
 That is, there are only two orders of infinity
for subsets of [0,1].
Hilbert’s Problems
 The Continuum
hypothesis
 Axioms for arithmetic.
 Algorithm for solving
Diophantine equations
David Hilbert (1862-1943)
Peano axioms
 0 is a number.
 Every number has a
successor.
 0 is not the successor of any
number.
 Distinct numbers have
distinct successors.
 (Induction) If a property
holds for 0 and it holds for
the successor of every
natural number, then it holds
for all numbers.
Giuseppe Peano (1858-1932)
Can we derive all “truths” about
numbers from these five axioms?
 In 1977, Jeff Paris and Leo Harrington found a “natural”








truth which cannot be derived from these axioms.
A “simple” example is given by Goodstein’s theorem.
Take any number; write it in base 2.
Write the exponents in base 2 until everything on the
page is in base 2.
Replace all the 2’s by 3’s thereby increasing the number.
Subtract 1 from this number.
Write this number in base 3 and all the exponents in
base 3 as before.
Subtract 1 from this number. Continue in this way.
After a finite number of steps, you get zero!!!
Principia Mathematica
 The Principia
published in 1910
was an attempt to
derive all
mathematical
truths from a welldefined set of
axioms and
inferential rules of
symbolic logic.
Godel’s theorem
 No axiom system
can prove all the
truths about the
natural numbers.
 Godel’s
incompleteness
theorems.
Extending Peano’s axioms
 Zermelo and
Fraenkel
enlarged the
axioms to
include the
“axiom of
choice” which
enables one to
prove
Goodstein’s
theorem.
E. Zermelo(1871-1953)
A. Fraenkel (1891-1965)
The continuum hypothesis is
undecidable
 In 1963, Paul
Cohen showed that
the continuum
hypothesis is not
provable in ZFC.
Paul Cohen
What are Diophantine equations?
 In the simplest case, these are equations
with integer coefficients.
 For example, 3x² + 5y³ = 1 is a
Diophantine equation.
 This equation has no integer solutions,
which is easily seen modulo 5.
 What about 3x² + 5y³ = 2? Does this have
integer solutions?
Let’s look at 3x²+5y³=2
 If this equation has an integer solution, then







multiplying by 3, we get that
(3x)² + 15y³=6 also has an integer solution.
Multiplying by 15², we see that
(45x)² + (15y)³ = 1350 also has an integer
solution.
This leads to integer solutions of the elliptic
curve y² = x³ + 1350.
This curve has only two integer solutions:
(-5,35) and (-5, -35).
This means 3x²+5y³=2 has NO integer solutions.
What about 3x²+ 5y³=3?
 There are the obvious solutions x=1, y=0
and x=-1, y=0.
 Are there any more?
 Yes, there is one more: x=19, y=-6.
 We need the theory of elliptic curves to
prove that there are no further solutions!
General Diophantine Equations
 Any equation of the form
 f(x1, x2, …, xn) = 0 where f is a polynomial with integer




coefficients is called a Diophantine equation.
xn + yn = zn is a famous example of a Diophantine
equation.
Fermat asked if this equation has any non-trivial
solutions and conjectured that there were none.
This was proved by Andrew Wiles following the work of
Ken Ribet in 1995.
Hilbert’s 10th problem asks if there is a universal
algorithm for determining whether a given Diophantine
equation has an integer solution.
Hilbert’s 10th problem
 In 1970, Yuri
Matiyesevich showed
in his PhD thesis that
Hilbert’s 10th problem is
unsolvable.
 That is, there is no
universal algorithm that
works for all
Diophantine equations.
 He was building on
earlier work of Martin
Davis and Julia
Robinson.
Yuri Matiyasevich
Hilbert’s problems revisited
 Three of Hilbert’s
problems had a “negative”
solution in the following
sense.
 Problem1 is undecidable.
 Problem 2 led to Godel’s
incompleteness theorems.
 Problem 10 is unsolvable.
Computability
 Polynomial time algorithms (P)
 Conjectural answer can be verified in
polynomial time (NP)
 X is NP complete: if every problem in NP
can be reduced in polynomial time to X
and X is also in NP.
Is there a polynomial time algorithm
for testing if a given number is
prime?
 Given a number n, can we determine if n is
prime in (log n)² steps?
 Until 2002 this was a major unsolved problem.
 This question is related to cryptography and
internet security, as is well-known.
 More importantly, factoring a number in
polynomial time is an open question.
Agrawal, Kayal and Saxena won the Fulkerson prize this year.
Primality Testing is in P
Nitin Saxena
Neeraj Kayal
Manindra Agrawal
Hamiltonian cycles
 Given a graph on n vertices, is there an
algorithm to find a Hamiltonian cycle in
polynomial time?
 Answer: Not known.
 This problem is NP complete.
 If the answer is “yes” then P=NP.
Mathematical questions lead to the
discovery of fundamental concepts
 For example, 0 is a fundamental concept.
 Mathematics is not something fixed but
rather something that can be enlarged as
we enlarge the axioms.
 These axioms are dictated by
observations and experience.
 We want to minimize the number of
axioms at any given stage.
What are the implications of
Godel’s theorem?
 Does it imply that human reason is
limited?
 On the contrary, it shows that the human
mind cannot be axiomatized.
 Computability is only one aspect of the
mind.
 Understanding lies deeper than
computability.