PROFESSOR: In this final segment on predicate logic,
there are two issues that I'm going to talk about.
The first is some problems with translating A E quantifiers
and E A quantifiers into English-- or rather
from English into logic.
We've seen examples in class that English is ambiguous.
And I want to show you two that are I think
interesting and provocative.
Just as a warning that the translation is not
always routine.
And then the second topic is an optional one,
just to kind of make some comments
about the amazing results in metamathematics,
the mathematics of mathematics, or more
precisely, the mathematics of mathematical logic.
And two fundamental theorems about properties
of predicate calculus, which go beyond this class
and are optional, I would suggest
it's worth listening to the A E in English example.
And if you want to skip the short discussion of the meta
theorems, that's fine, because it's never going
to come up again in this class.
So let's look at this phrase in English, where the poet says,
"all that glitters is not gold."
Well, a literal translation of that
would be that, if we let G be glitters,
and I can't use G again, so we'll say Au is gold,
then this translated literally would say for every x,
G of x, if x is gold implies that not gold of x.
So is that a sensible translation?
Well, it's clearly false, because gold
glitters like gold.
And you can't say that gold is not gold.
So this is not what's meant.
It's not a good translation.
It doesn't make sense.
Well, what is meant, well, when the poet says,
"all that glitters is not gold," he's
really leaving out a key word to be understood from context.
All that glitters is not necessarily gold.
He was using poetic license.
You're supposed to fill in and understand its meaning.
And the proper translation would be
that it is not true that everything that glitters
is gold.
It is not the case that for all x, if x glitters,
then x is gold.
So it's just an example where a literal translation
without thinking about what the sentence means
and what the poet who articulated this sentence
intended will get you something that's nonsense.
It's one of the problems with machine translation
from natural language into precise formal language.
Let's look at another example of the same kind.
The poet says this time, "there is a season
to every purpose under heaven."
This is a variant of a biblical phrase.
So what does it mean?
Well, the literal translation would
be, there exists an s that's a season,
such that for every p that's a purpose, s is for p.
Well, that from the way the quantifiers work
means that there's some season, say summer, that's supposed
to be good for all purposes.
Well, that's not right, because summer is not
good for snow shoveling.
And if your purpose is to shovel snow, then summer
will not do for you as a season.
So even though it's phrased, there
is a season to every purpose under heaven,
it's not the case that the intended translation is there
is a season for every purpose.
In fact, the poet really means to flip the quantifiers, which
is what's shown here.
We're going to switch them around so that we are really
saying, for every purpose, there is a season,
such that s is for p.
For snow shoveling, winter is good.
For planting, spring is good.
For leaf watching, fall is good.
And that is, in fact, the intended translation
here, although I remind you that there's
a famous historical man, Sir Thomas More, who was described
as a man for all seasons.
That would be a case where there was one man who
was good for all seasons.
He was a polymath-- a writer, a cleric,
and the chancellor of England for many years
until he had a falling out with Henry VIII, which
served him ill.
That's the end of those two examples, whose point is just
to warn you that translation from English into math
is not something that can be done
in a mindless mechanical way.
Sometimes, the quantifiers really
are meant to go the other way from the way
that they literally appear.
Now, we're going to shift to another topic, which is just
two profound theorems from mathematical logic
about the properties of predicate calculus
that are worth knowing about and that
describes sort of the power and limits of logic.
So these are called meta-theorems,
because they're theorems about theorems.
They're theorems about systems for proving theorems.
And that phrase, meta, means going up above a level.
So the first theorem is a good news theorem.
It says that, if you want to be able to prove
every valid assertion of predicate calculus,
there really is only a few axioms and rules
that will do the job.
As a matter of fact, the rules that you need
are just rules that we've seen already,
namely modus ponens and universal generalization
and a few valid axioms which we've seen already.
So let's go back a little bit.
So there's a remark here that says that, in practice,
if you're really going to try to do automatic theorem proving,
you need much more than this minimal system.
But it's intellectually interesting and satisfying
that a fairly economical set of axioms and inference rules
are in theory sufficient to prove
every logically valid sentence.
And this is known as Godel's completeness theorem.
Godel was the great mathematician,
German mathematician, who spent the latter part of his life
at the Institute for Advanced Study in Princeton
as an emigre.
And he has two major theorems, at least,
that are results of his.
One is the completeness theorem-- this one.
Then there's an incompleteness theorem, which maybe we'll
talk about in a few lectures.
But for now, the good news is you can prove everything that's
valid using a few simple rules.
Now, the bad news is that there's
no way to tell whether you're attempt
to find a proof for something that you think
is valid is going to succeed.
There's no way to test whether or not
a quantified formula is valid.
This is in contrast to the case of propositional formulas,
where you can do it with a truth table.
A truth table may blow up, so it becomes
pragmatically infeasible.
But at least, theoretically, there's
an exhaustive search that will enable
you to figure out whether a propositional formula is valid.
That's not the case with predicate calculus.
Predicate calculus is undecidable,
meaning that it's logically impossible to write a computer
program that will take an arbitrary predicate calculus
formula in and print out true or false depending on
whether or not it's valid.
Can't be done.
Now, as I said, we're not going to go further
into these theorems.
These are the kind of basic results
that would be proved in an introductory course in logic.
Usually, they take about a half a term to do,
maybe a little less.
And it goes beyond our course.
You can look over in the math department
for introductory courses in logic.
And you will learn about these two profound meta-theorems
about logic and math.