Transcript The history presentation.

A Brief History of Logic
Some Background
Copyright © 2003-2015 Curt Hill
Greece and the beginnings
• The Greek legal system had some
similarities to ours with juries and
lawyers
– Juries were much larger
– Less screening
• There was much more dependence
on what was reasonable
• Less on codified laws
Copyright © 2003-2015 Curt Hill
How to win
• The arguments of the lawyer are
much more important
• Rhetoric becomes an important
science
– Citizens who were not particularly
wealthy could be their own lawyers
• Philosophy was also quite important
and depended on rhetoric
– Socrates and Plato among others
Copyright © 2003-2015 Curt Hill
The Sophist as Lawyer
• The sophist could argue that right
was wrong
– A lawyer is not looking for justice, but
for the client to win
• So how do we tell if the speech is
good but the argument flawed?
Copyright © 2003-2015 Curt Hill
Mathematical progress
• Some important names we will
consider
• Thales of Miletus (640-546 BC)
• Pythagoras (570-500 BC)
• Zeno of Elea(early fifth century)
• Aristotle (384-322 BC)
Copyright © 2003-2015 Curt Hill
Thales of Miletus (640-546 BC)
• Wealthy merchant
– Became rich by cornering the olive oil
market
• Prior to Thales geometry was mostly
concerned with surveying
– Techniques on how to accomplish a
practical thing
• He chose several statements on
geometry
– These were well known as practical
facts
Copyright © 2003-2015 Curt Hill
Statements
• Statements
– A circle is bisected by any of its diameters
– When two lines intersect the opposite angles
are equal
– The sides of similar triangles are proportional
– The angles at the base of an isosceles triangle
are equal
– An angle inscribed within a semcircle is a
right angle
• However, Thales showed that they could
be derived from previous statements
• This is the precursor of the idea of a proof
– He founded the Ionian school of thought
Copyright © 2003-2015 Curt Hill
Pythagoras (570-500 BC)
• The most famous of the Ionian school
• A lot of myth has grown up about him
because of his impact on mathematics
• His followers formed a secret society with
mysticism, worshipping the idea of
number and the hoarding of knowledge
• He was the first to assert that proofs were
based upon assumptions, axioms or
postulates – things that were given and in
their own right not provable
• He also was the first to offer a proof about
sizes of sides of right triangles
Copyright © 2003-2015 Curt Hill
Pythagorean Society
• The society made contributions to
many areas:
–
–
–
–
Music theory
Number theory
Astronomy
Geometry
• However, they proved themselves to
be a contradiction
Copyright © 2003-2015 Curt Hill
The Contradiction
• One of their fundamental assumptions
that the integer was the basis of all truth
• One of their members proved the
existence of irrational numbers
– Numbers that are not the ratio of two integers
• They took him in a boat out to sea and
drowned him
• They suppressed the knowledge for some
time, but ultimately he had disproved one
of their fundamental principles
Copyright © 2003-2015 Curt Hill
Zeno of Elea (early fifth century)
• Student of Parmenides
• They believed:
– Motion and change are only apparent
– Everything is one – no multiplicity
• He produced several paradoxes that
nobody could resolve
• This was an affront to the whole
notion of a proof and opposed to
Pythagorean reality
Copyright © 2003-2015 Curt Hill
Line Segment
• If we assume that a line segment is
composed of a multiplicity of points
• We can always bisect the line
• Each of the resulting segments can
itself be bisected
• We can do this ad infinitum
• We never come to a stopping point
so lines must not be composed of
points
Copyright © 2003-2015 Curt Hill
Achilles and the Tortoise
• Achilles and a tortoise are in a race
where the tortoise is given a head
start
• Whenever Achilles catches up to
where the tortoise was, the tortoise
has advanced
• Thus Achilles can never catch the
tortoise
Copyright © 2003-2015 Curt Hill
The arrow
• Assume that the instant is indivisible
• An arrow is either at rest or moving in any
instant
• An arrow cannot change its state in an
instant
• Therefore an arrow at rest cannot move
• It turns out that neither of these
paradoxes can be handled until the
calculus is introduced with its notion of
limits
Copyright © 2003-2015 Curt Hill
Aristotle (384-322 BC)
• Tutor of Alexander the Great
• Greatest mathematician and
scientist of the day
• Wrote a number of works in
philosophy and science
• His science works were not usually
superseded until the Renaissance
– About 17 centuries of pre-eminence
Copyright © 2003-2015 Curt Hill
Logic Contributions
• Four types of statements, each denoted
by a letter
– Universal affirmative
• All S is P
• A
– Universal negative
• No S is P
• E
– Particular affirmative
• Some S is P
• I
– Particular negative
• Some S is not P
• O
Copyright © 2003-2015 Curt Hill
Four types (continued)
• In each of these statements:
– S which is the subject
– P is the predicate
• All or no have obvious meanings
• Some means one or more
Copyright © 2003-2015 Curt Hill
Syllogism
• Aristotle's main form was a
syllogism
• Each syllogism consisted of two
premises (a major and minor) and
one conclusion
• The premises and conclusion are of
one of previous four statement types
Copyright © 2003-2015 Curt Hill
Syllogism
• Example
– All cats eat mice
– Felix is a cat
– Therefore Felix eats mice
• Statement types
– First is universal affirmative
– Second is a particular affirmative
– Third is a particular affirmative
Copyright © 2003-2015 Curt Hill
Example continued
• Subjects
– Cats (all) for major premise and Felix for minor
• Predicates
– The set of items that eat mice for major and
conclusion
– Is a cat for minor
• The form:
– S1  P1
S2  P2
S2  P1
Copyright © 2003-2015 Curt Hill
Discussion
• Subjects identify an item or group of
items
• Predicates state a property
• The conclusion
– Has a subject and predicate that are each
only used once in the premises
– However there is a middle term used in the
premises that is not used in the conclusion
– The major premise contains the conclusions
predicate
– The minor premise contains the conclusions
subject
Copyright © 2003-2015 Curt Hill
More discussion
• There should be three items in these
two premises
• The conclusions subject, the
conclusions predicate and a middle
term
• The major premise should contain
the conclusions predicate
• The minor premise should contain
the conclusions subject
Copyright © 2003-2015 Curt Hill
Combinatorics
• There are four different ways to arrange
the S, P and M into a syllogism
• There are four different statements that
can be plugged into the three statement
• This give 4^4 = 256 syllogisms
• However, not all of these are valid
• What Aristotle did is identify (some of) the
valid syllogisms and some of the invalid
syllogisms
• Some of these received names, which will
be mentioned as we re-encounter them
Copyright © 2003-2015 Curt Hill
Archimedes
• 250 BC
• Seems to have figured out the
paradoxes of Zeno
• Very close to inventing both
Calculus and the underpinning idea
of limits
• The work did not get out and was
lost for centuries
• Killed in Roman siege of Syracuse
• Ranked as one of top
mathematicians along with Newton
and Gauss Copyright © 2003-2015 Curt Hill
Gottfried Liebniz
• Invented calculus
• Postulated the concept of balance of
power
• Postulated that there was a
universal characteristic
– A language in which errors of thought
would appear as computational errors
– This part of his work was ignored
– However this is a long standing goal of
logic
Copyright © 2003-2015 Curt Hill
George Boole (1815-1864)
• Almost single handedly moved logic
from philosophy to mathematics
• What we now know as a Boolean
algebra stems from his work
• Separated the logical statements
from their underlying facts
• Once this occurred the gates
opened and a number of people
joined in
Copyright © 2003-2015 Curt Hill
Boole’s Successors
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
Jevons
DeMorgan
Peirce
Venn
Lewis Carroll
Ernst Schröder
Löwenheim
Skolem
Peano
Frege
Bertrand Russell
Alfred North Whitehead
Hilbert
Ackermann
Gödel
• The early ones corrected Boole's work and the later ones
extended it
Copyright © 2003-2015 Curt Hill
Two of note
• Many of this above list will be
considered in the course of this
class but the following two bear
more comment now
• David Hilbert
• Kurt Gödel
Copyright © 2003-2015 Curt Hill
David Hilbert
• An extraordinary leader in the
mathematical community
– The dominant mathematician from
about 1885 to 1940
• List of career accomplishments
could be a course itself
– Geometry
– Number theory
– Physics
• In 1900 he published a list of 23
problems that needed to be solved
in the 20th century
Copyright © 2003-2015 Curt Hill
The 23 problems
•
•
•
•
Some have been solved
Some are too vague to solve
Many are still in process
The second is relevant today
– Prove that the axioms of arithmetic are
consistent
• Seems like a good goal
Copyright © 2003-2015 Curt Hill
Kurt Gödel
• Proved the first and second
incompleteness theorems
– 1931 or so
• There is considerable belief that this
is the death knell of problem 2
– The second states that a proof of the
consistency of arithmetic cannot be
from within arithmetic itself
Copyright © 2003-2015 Curt Hill
First
• Any effectively generated theory
capable of expressing elementary
arithmetic cannot be both consistent
and complete.
• In particular, for any consistent,
effectively generated formal theory
that proves certain basic arithmetic
truths, there is an arithmetical
statement that is true, but not
provable in the theory
Copyright © 2003-2015 Curt Hill
Second
• For any formal effectively generated
theory T including basic arithmetical
truths and also certain truths about
formal provability, if T includes a
statement of its own consistency
then T is inconsistent
Copyright © 2003-2015 Curt Hill
So?
• Among other things these two state
that no formal system of axioms can
prove the validity of itself
• If this were a three hour course of
logic we would be compelled to
study these two theorems
• As it is, this is as close as we will
come
• However, these theorems do not
disprove the usefulness of axiomatic
systems
Copyright © 2003-2015 Curt Hill