completeness of predicate calculus
falcon
and Paradox of Kurt Godel). I was surprised to read that Godel's PhD
dissertation had been on the completeness of predicate calculus (which
she called limpid calculus). What exactly does it mean for predicate
calculus to be complete? The only reason I even know predicate
calculus is because of references to it when I studied relational
databases back in undergrad.
Rupert
It means that every statement which is true in all models is provable.
It doesn't mean that for every statement A, either A or ~A is provable
- that's a different sort of completeness.
mark...@yahoo.com
> What exactly does it mean for predicate calculus to be complete?
It means that when the predicate calculus, itself, is viewed as a
mathematical theory, it may be fully characterized by a finite set of
axioms. It is, as a mathematical theory, finitely axiomatizable.
In contrast, the 2nd order theory of arithmetic is not finitely
axiomatizable in the 1st order predicate calculus.
> The only reason I even know predicate calculus is because of references
> to it when I studied relational databases back in undergrad.
Prolog is traditionally regarded as the grandaddy of relational
database theory. Or, more accurately, it is grandfathered into that
designation.
It makes you wonder, then: why was there ever all the bother of
reinventing the wheel by coming up with SQL (which, now, has assumed
monstrous proportions), instead of just basing the theory on Prolog or
a dialect, like Datalog? The language SQL has the same
hyper-unorthogonal feel as FORTRAN, JCL or even assembly language, and
definitely shows the imprint of baby-boomer 1960's-think all over it. I
thought we were supposed to be evolved past that language-flavor and
way of thinking long ago.
And to add insult to injury, you have to *pay* for that monstrosity of
a SQL Standard, now 4000 pages long, if you want to be clued in to the
precise details of the language?! I don't think so! It looks about as
bad as the (400-page) European Constitution, that got shot down a few
months ago, did -- only 10 times worse. Makes you wonder if they were
*both* written in Geneva.
Rupert
mark...@yahoo.com wrote:
> falcon wrote:
> > What exactly does it mean for predicate calculus to be complete?
>
> It means that when the predicate calculus, itself, is viewed as a
> mathematical theory, it may be fully characterized by a finite set of
> axioms. It is, as a mathematical theory, finitely axiomatizable.
>
Well, it's trivial that the predicate calculus is finitely
axiomatizable. The interesting fact is that it is complete.
> In contrast, the 2nd order theory of arithmetic is not finitely
> axiomatizable in the 1st order predicate calculus.
>
Second-order theory of arithmetic? Not even the first-order theory of
arithmetic is finitely axiomatizable. Did you perhaps mean the set of
valid second-order statements is not finitely axiomatizable?
Paul Holbach
> I am currently reading Rebecca Goldstein's "Incompleteness" (The Proof
> and Paradox of Kurt Godel). I was surprised to read that Godel's PhD
> dissertation had been on the completeness of predicate calculus (which
> she called limpid calculus). What exactly does it mean for predicate
> calculus to be complete?
See: http://plato.stanford.edu/entries/logic-classical/#5
Regards
PH
Barb Knox
mark...@yahoo.com wrote:
[snip]
>The language SQL has the same
>hyper-unorthogonal feel as FORTRAN, JCL or even assembly language, and
>definitely shows the imprint of baby-boomer 1960's-think all over it.
As a card-carrying Boomer, I'm curious what you mean by "baby-boomer
1960's-think". In particular, how does that differ from your personal
favourite <whatever>-think?
[snip]
--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------
george
Rupert wrote:
> It means that every statement which is true in all models is provable.
> It doesn't mean that for every statement A, either A or ~A is provable
> - that's a different sort of completeness.
In a recent argument I wound up confused by yet a third
kind of "completeness". It wasn't just "complete" by itself;
it was <x>-completeness where x could denote some syntactically-
characterized class of sentences (classified according to their
quantifier-prefix, usually), and a theory got to be <x>-complete
by proving all the "true" sentences in class <x>. This kind
is a lot closer to the first of the two kinds mentioned above,
except that, in order to get into the "denominator" of the relevant
ratio (if you will), the sentence had to be true NOT in ALL models,
but rather, just true simpliciter, i.e., true in the standard model.
I simply must believe that there is an article somewhere that
discusses not just two, but all three of, these kinds of completeness,
or somebody reading this who knows what their usual names are.
Aatu Koskensilta
> I simply must believe that there is an article somewhere that
> discusses not just two, but all three of, these kinds of completeness,
> or somebody reading this who knows what their usual names are.
The first two kinds of completeness are usually both known as
completeness, or if there is a danger of confusion sometimes the terms
semantical completeness and negation completeness are used. Given a
class of sentences Gamma in some interpreted language, a theory T is
Gamma-complete iff every true sentence in Gamma is provable in T. A
theory T is provably Gamma-complete, if T's Gamma-completeness is
provable in T itself. Thus in logical literature one will encounter e.g.
the assertion that PA is provably Sigma_1-complete. The terms
Gamma-complete and provably Gamma-complete are, unlike the first two,
almost universal. Related to the notion of Gamma-completeness there is
also Gamma-soundness or Gamma-consistency; a theory T is Gamma-sound if
it does not prove false sentences in Gamma. Thus we have such assertions
as "PA is Sigma_1 - sound" which is sometimes also expressed in the form
"PA is 1-consistent".
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
falcon
original post. My understanding was that the *incompleteness* theorem
showed that any logical system based on a set of axioms can not be
complete, yet predicate calculus is complete...did I miss something
obvious?
Secondly, and more practically, does completeness of predicate calculus
mean that "any *fact* can be stated using predicate logic?"
I ask that because if that is true, then I start to understand why
Relational DBMS purists are so adamant about staying true to the
relational model....as I understand it, all the "information" in
wikipedia (or any other source) could be stated as 'facts' which can be
manipulated and queried through predicated logic. Exaclty how those
facts are expressed for humans to read (using english sentence
structures, tables of numbers, charts/graphs) are not part of any logic
system, they are mere ornaments around basic facts as far as logic is
concerned...true?
I am trying to understand the true importance of the relational model
by reading about logic rather than expecting database books to explain
the the 'deeper meaning.'
Again, thanks for your replies, they are very educational.
Chris Menzel
> Thanks for your replies, I should have added another point to my
> original post. My understanding was that the *incompleteness* theorem
> showed that any logical system based on a set of axioms can not be
> complete, yet predicate calculus is complete...did I miss something
> obvious?
You missed something, though it's not terribly obvious at first sight.
There are two quite different notions of completeness in mathematical
logic, one that applies to logical systems -- often called "semantic
completeness" -- and another that applies to theories -- often called
"negation completeness". A logical system S is semantically complete
iff every valid sentence in the language of S is a theorem of S. (A
sentence in the language of S is valid iff it is true in every
interepretation of the language.) A theory T is negation complete iff,
for every sentence A in the language of T, either A or its negation ~A
is a theorem of T.
Predicate logic is semantically complete but (obviously) not negation
complete. There are theories of arithmetic (among others) with only
addition that are negation complete (google "Presburger arithmetic").
Gödel's (first) incompleteness theorem is that any consistent, decidable
extension of a certain weak theory of arithmetic (one containing both
addition and multiplication) is (negation) incomplete.
george
Chris Menzel wrote:
> Gödel's (first) incompleteness theorem is that any consistent, decidable
> extension of a certain weak theory of arithmetic (one containing both
> addition and multiplication) is (negation) incomplete.
That is presumably the CORRECT statement of it, but it is
NOT the popular one; the popular one stresses not that
some statement is undecided, but rather that some "true"
statement is not proved. That is closer to the spirit of
"semantic" incompleteness in that there is a pre-existing
class of sentences that the theorems of the theory don't
exhaustively cover. In "semantic completeness", that
class would be the validities; in terms of the original quest,
it would be the truths of the standard model. You can
(from Godel's thesis, as opposed to his theorem) completely
cover the former (semantic completeness); you cannot (completely)
cover the latter (with a recursive axiom-set and classical
FOL). But both semantic and negation completeness (or the
lack thereof) are NOT the same thing as this "original" kind
of incompleteness. AK gave an answer implying that you
need a different <x> (in <x>-completeness) for every underlying
class, but there was no particular <x> specfied in the original;
it just DEFAULTED to "truth".
mark...@yahoo.com
> Well, it's trivial that the predicate calculus is finitely
> axiomatizable. The interesting fact is that it is complete.
It is not trivial to be finitely axiomatizable; since finite
axiomatizability characterizes completeness.
> > In contrast, the 2nd order theory of arithmetic is not finitely
> > axiomatizable in the 1st order predicate calculus.
>
> Second-order theory of arithmetic? Not even the first-order theory of
> arithmetic is finitely axiomatizable.
You mean: "not even the 2nd order theory of arithmetic is finitely
axiomatizable in 1st order predicate calculus.", which is certainly
true. In particular, the 2nd order induction axiom cannot be rendered
equivalently by any finite number of axioms in 1st order predicate
calculus. That's what the Goedel theorem shows.
Aatu Koskensilta
> It is not trivial to be finitely axiomatizable; since finite
> axiomatizability characterizes completeness.
Do you think the finitely axiomatizable theory with the following axiom
Ax(P(x) \/ Q(x))
is complete? If so, you're certainly using the word in a non-standard sense.
Daryl McCullough
>Well, it's trivial that the predicate calculus is finitely
>axiomatizable. The interesting fact is that it is complete.
Everybody seems to agree that the predicate calculus is
finitely axiomatizable, but I don't see why that's true.
I suppose it is a matter of taste what is considered an
axiom and what is considered a rule of inference, but the
way that I learned logic was in terms of a collection of
axiom *schemas*, each of which corresponds to an infinite
number of axioms. For example:
A -> (B -> A)
(A -> (B -> C)) -> ((A -> B) -> (A -> C))
(forall x Phi(x)) -> Phi(t)
Phi(t) -> (exists x Phi(x))
etc.
In these axiom schemas, A, B, C, and Phi represent arbitrary
formulas, and so each schema corresponds to an infinite number
of axioms.
Of course, you can instead have a finite number of axioms
(or even no axioms at all) at the cost of enlarging your
set of rules of inference.
--
Daryl McCullough
Ithaca, NY
Chris Menzel
Typically, finite axiomatizability is defined relative to a background
of predicate logic: T is finitely axiomatizable if it is the set of
consequences of some finite set. So predicate logic itself is finitely
axiomatized by the empty set. I think that's all Rupert had in mind.
Chris Menzel
said:
> ..
> Typically, finite axiomatizability is defined relative to a background
> of predicate logic: T is finitely axiomatizable if it is the set of
Meaning thereby the theory consisting of the set of valid sentences of
predicate logic, of course.
> ... itself is finitely axiomatized by the empty set. I think that's
george
> > finitely axiomatizable, but I don't see why that's true.
It depends on viewpoint, on what semantic level you
are TRYING to operate on. If you want to talk about both
of them at once, then an axiom is an axiom and a rule
of inference is a rule of inference, and NEVER the twain
shall meet: the rules are one semantic level "higher than"
(or "meta-") the axioms, and that's just all there is to it;
the gulf is unbridgeable.
BUT
The reason why the meta-theory is called the meta-THEORY
is that you may ALSO CHOOSE to use FOL *at* the meta-level.
In particular, you can use FOL *as* your language for stating
rules of inference, with an "intended domain" consisting
FOL FORMULAE THEMSELVES.
Of course, this requires you to keep clear a distinction in
your own mind AND your own NOTATION between wffs
of the meta-theory and wffs of the object theory. But as long
as you yourself can avoid confusing yourself, there is nothing
"wrong" in principle with using a first-order axiomatic treatment
to describe FOL.
> > I suppose it is a matter of taste what is considered an
> > axiom and what is considered a rule of inference,
No, really, it isn't.
> > but the
> > way that I learned logic was in terms of a collection of
> > axiom *schemas*,
Exactly, and and it is NOT a matter of taste whether something
is an axiom, an axiom schema, or a rule of inference. SOME concepts
can be expressed in more than one of these ways, and perhaps it is
a matter of taste WHICH way you PICK: but HAVING picked a way, you
really do have to STICK with it. Iti is no LONGER a matter of choice
or taste
AFTER you have defined your framework; you thereafter NEED to operate
within it according to its conventions and its decisions about these
issues.
> each of which corresponds to an infinite
> > number of axioms. For example:
> >
> > A -> (B -> A)
> > (A -> (B -> C)) -> ((A -> B) -> (A -> C))
> > (forall x Phi(x)) -> Phi(t)
> > Phi(t) -> (exists x Phi(x))
> > etc.
> >
> > In these axiom schemas, A, B, C, and Phi represent arbitrary
> > formulas, and so each schema corresponds to an infinite number
> > of axioms.
Right, but the point is, you could view these as
first order SENTENCES that are universally QUANTIFIED OVER
all these variables-representing-arbitrary-first-order-wffs.
These-here sentences had best NOT be in the SAME domain
that they are quantifying over; these would be sentences in the
meta-language, or axioms of a meta-theory. But this meta-theory
could still be a first-order theory.
> > Of course, you can instead have a finite number of axioms
> > (or even no axioms at all) at the cost of enlarging your
> > set of rules of inference.
Of course.
> Typically, finite axiomatizability is defined relative to a background
> of predicate logic: T is finitely axiomatizable if it is the set of
> consequences of some finite set. So predicate logic itself is finitely
> axiomatized by the empty set. I think that's all Rupert had in mind.
Possible, but I doubt it. That trivializes the question.
Every ZEROth-order tautology is, whether you like it or not,
a rule of FIRST-order inference. Being meta- to something first-order,
it is thus 0th-order AND 2nd-order at the SAME time.
You can translate propositions (0th-order wffs) into two connectives
(unary negation and binary conditional). If the original wff was a
tautology
then the translated one will be as well, and just changing its main
connective
from -> to => is guaranteed to get you a sound rule of inference.
The question of how many more rules of inference you "need" (in
addition
to the ones you get for free, as here, just from subsuming 0th-order
logic)
is what here occurs. Do you, or do you not, for example, need a rule
of inference for equality, or failing that, an axiom for it?
Rupert
mark...@yahoo.com wrote:
> Rupert wrote:
> > Well, it's trivial that the predicate calculus is finitely
> > axiomatizable. The interesting fact is that it is complete.
>
> It is not trivial to be finitely axiomatizable; since finite
> axiomatizability characterizes completeness.
>
No, it doesn't.
It does trivially follow from the definition of the predicate calculus
that it is finitely axiomatizable.
Rupert
Actually, I was confused and Daryl had a legitimate complaint against
me (although you very kindly provide me with a nice way of pretending I
wasn't confused).
Jack Campin - bogus address
> mean that "any *fact* can be stated using predicate logic?"
No.
> I ask that because if that is true, then I start to understand why
> Relational DBMS purists are so adamant about staying true to the
> relational model....as I understand it, all the "information" in
> wikipedia (or any other source) could be stated as 'facts' which can be
> manipulated and queried through predicated logic.
The basis of relational databases is relational algebra, which is
a *lot* weaker than predicate calculus. This is essential to
practical use of the system - database queries can be optimized,
whereas general expressions in predicate calculus are so complicated
that no optimization algorithm is possible.
Prolog is in between.
> I am trying to understand the true importance of the relational model
> by reading about logic rather than expecting database books to explain
> the the 'deeper meaning.'
There are a few database books that explain what's going on in
mathematical terms, but you wan't make much progress unless you
know quite a lot of logic first.
============== j-c ====== @ ====== purr . demon . co . uk ==============
Jack Campin: 11 Third St, Newtongrange EH22 4PU, Scotland | tel 0131 660 4760
<http://www.purr.demon.co.uk/jack/> for CD-ROMs and free | fax 0870 0554 975
stuff: Scottish music, food intolerance, & Mac logic fonts | mob 07800 739 557