Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: [HM] Categorical systems
Replies: 1   Last Post: Oct 11, 1999 9:51 AM

 Messages: [ Previous | Next ]
 Carlos Cesar Araujo Posts: 9 Registered: 12/3/04
[HM] Categorical systems
Posted: Oct 10, 1999 6:58 PM

As Zach [1] recently pointed out (p.353), "The history of the
concept(s) of completeness of an axiomatic system has yet to be
written". Be that as it may, there is no doubt that one starting
point here is Hilbert's "axiom of completeness". Note that
"completeness" is first used by him to name just an axiom and not
a PROPERTY OF an axiom system. "Completeness" in this latter sense
(and in many forms) would be very much investigated by Hilbert
himself and his collaborators in the 1920s. Zach [1] is right when
he remarks (p.353) that "one of the roots of completeness as a
property of axiom systems is the completeness axiom that Hilbert
introduced in" [2].

On the other hand, it seems very likely that Hilbert took the
term "complete" (in this context) from Dedekind [3]. In many
passages of this work Dedekind uses the term "completeness" to
refer to the continuity of the straight line. He then finds the
"essence of continuity" in a condition that "is nothing else than
an axiom" and which is today justifiably called
"Dedekind-completeness" (or "cut-completeness"). It might be
good to recall at this point what Hilbert said in his famous 1900
lecture on mathematical problems (see [4]):

\begin{quote}
The axioms of arithmetic [i.e for the real numbers] are
essentially nothing else than the known rules of calculation, with
the addition of the axiom of continuity. I recently collected them
and in so doing replaced the axiom of continuity by two simpler
[sic] axioms, namely, the well-known axiom of Archimedes, and a
new axiom essentially as follows: that numbers form a system of
things which is capable of no further extension, as long as all
other axioms hold (axiom of completeness).
\end{quote}

I cannot discuss now what was (probably) his motivation behind
this replacement (a little hint is given in Greenberg [5]), but a
significant technical fact here is that this new axiom stands in
the same relation to ARCHIMEDEAN ordered fields as does Dedekind's
axiom to ordered fields: both yield one and the same CATEGORICAL
axiom system --- namely, the system most (standard) analysts
employ today. This system is categorical in the sense that it
possess AT MOST one model up to isomorphism. For Hilbert (as for
Dedekind), categoricity, alongside with (semantic) consistency
(existence of AT LEAST one model), is all that really matters. In
fact, in his 1900 lecture (see [4]) he also wrote:

\begin{quote}
Indeed, when the proof for the compatibility of the axioms shall
be fully accomplished, the doubts which have been expressed
occasionally as to the existence of the complete system of real
numbers will become totally groundless. The totality of real
numbers, i.e., the continuum ..., is not the totality of all
possible series in decimal fractions, or of all possible laws
according to which the elements of a fundamental [Cauchy] sequence
may proceed. It is rather a system of things whose mutual
relations are governed by the axioms set up and for which all
propositions, and only those, are true which can be derived from
the axioms by a finite number of logical processes. In my opinion,
the concept of the continuum is strictly logically tenable in this
sense only.
\end{quote}

There is, of course, a difference in that Hilbert's axiom, as it
stands, is not immediately "simpler" than Dedekind's, being a
sort of "external" condition, a kind of "meta-axiom" --- a
feature which led to many critical objections by mathematicians
and logicians of that period. However, I think that such a feature
should not appear so strange for us today, since it is not
difficult to give a precise formulation of Hilbert's axiom in
terms of a maximality condition on a suitable poset. (Some care is
needed when defining the relevant underlying order relation via
field embeddings.) After all, there is by now a huge body of
concepts and methods in model theory, universal algebra and
category theory that cover far more general structures.

Now, it was Hilbert and his school who POPULARIZED the axiomatic
method and, in particular, the very term "completeness" as a
property of axiom systems. After some tentative attacks, at least
three distinct notions had emerged in the 20s: (what we now call)
Post completeness, syntactic completeness and semantic
"deductive" and "proof-theoretic" are also common.) The great
Russian mathematician (and field medalist) P. S. Novikov used to
refer to the first and third notions by the terms "complete[ness]
in the narrow sense" and "complete[ness] in the wide
sense".(See [6], pp. 78-79.) Novikov [6] also mentions another
possibility (p. 105):

\begin{quote}
Every system of axioms for which all interpretations are
isomorphic is called a complete system.
\end{quote}

Note that this is exactly the condition of categoricity! In order
to distinguish this sense of "completeness" from the other two,
Novikov calls it "completeness to within isomorphism" or
"formal completeness". Here we see an example (and I have seen
many others which I do not have handy now) of how categoricity was
(and can be) considered as a kind of completeness. What is more,
in many (antiquated) geometry books we learn that "if all
realizations of the system of axioms T are isomorphic, then this
system of axioms is complete" (Pogorelov [7], p.57), where
"completeness" of $T$ here means that "it is impossible to
adjoin new axioms to it which do not follow from the axioms of T
and do not contradict them" ([7], p.57). In other words,
categoricity implies (semantic) Post completeness.

This said, it is not unreasonable to conjecture that the use of
"completeness" for "categoricity" appeared as a consequence of
that Huntington's definition of completeness (as quoted by Julio)
splits in these three requirements: (I) (semantical) consistency,
(II) categoricity and (III) independence. (Note also that every
inconsistent system is vacuously categorical. To avoid
trivialities, Carnap restricts "categorical" to mean existence
and uniqueness of a model up to isomorphism.)

Finally, there are the well-known anomalies involving first-order
systems. Thus, although first-order logic is not Post complete
(Ackermann) and not categorical (Skolem), it is semantically
complete (Goedel). This last result is the famously known Goedel's
"completeness theorem" for the predicate calculus. However,
Lyndon [9] (p. 43) preferred to use another term:

\begin{quote}
since we have used the word completeness in a different sense, we
shall call this the Adequacy Theorem.
\end{quote}

Unfortunately, the term "adequacy" has not been much used in the
completeness theorem in Halmos [10].)

In regard to the loss of categoricity and the resulting
"confusion" among mathematicians (which I mentioned elsewhere),
I think the root of the problem lies in the correct separation of
"first-order" from "higher-order". This is not an easy
distinction! (See [11].) To illustrate it, I would like to take
this opportunity to mention the (apparently not well known)
personal "drama" experienced by a distinct topologist. In 1967
H. B. Bing published an article entitled "Challenging
Conjectures" (Amer. Math. Monthly) where he wrote:

\begin{quote}
There have been some very interesting theorems by Paul Cohen and
others showing that these questions [the continuum hypothesis]
cannot be answered in certain restricted logical systems. (...)
However, these logical systems (...) have countable models and
axiomatic systems based on these logical systems do not purport to
describe adequately the working model of the real number system as
I and many other mathematicians envision it. (...) I would regard
the "integers" as a well defined set (...), rather than things
satisfying certain noncategorical systems. Similarly, I regard the
"reals" as fixed, invariant, agreed upon sets. (...) It would be
interesting to know if one steps outside these abstract "reals"
with countable models and into the real reals, whether or not the
continuum hypothesis is true.
\end{quote}

Thirteen years later we find Bing still complaining (Metrizations
Problems, in the book General Topology and Modern Analysis,
1980-81):

\begin{quotation}
This suggests the underlying assumption that there is only one set
of reals. (...) However, we are told that in axiomatic set theory
there are many sets of reals. (...) I asked the innocent question
as to whether there was always a homeomorphism between any two
sets of axiomatic reals, but it was suggested that this was not a
proper question. (...) However, when I am told that the
cardinality of a set is not an intrinsic property of the set but
uneasy feeling that someone is tinkering with basic traditional
concepts. What is the beef? One is that if a mathematician uses
theorist may ignore the concepts intended by the questioner,
replace them with related concepts, answer the changed questions,
and then announce results with verbage that makes it appear that
the original question has been answered. (...) Axiomatic set
theory (...) tends to mislead general topologists by shifting the
meaning of terms. (...)
\end{quotation}

By that same year, Morris Kline was still examining the subject by
himself and decided to publish "The Loss of Certainty", where
one can read (footnote to p. 271):

\begin{quote}
Older texts did "prove" that the basic systems were categorical;
(...) But the "proofs" were loose in that logical principles
were used that are not allowed in Hilbert's metamathematics and
the axiomatic bases were not as carefully formulated then as now.
No set of axioms is categorical, despite "proofs" by Hilbert and
others.
\end{quote}

More recently, in a critique to an article that appeared in the
Summer 1991 Mathematical Intelligencer, Peter Nyikos wrote:

\begin{quote}
(...) I disagree with what he calls the formalist thesis:
"...rather like Church's thesis, [it] is simply that all of pure
mathematics can be imbedded in formal systems." Unlike Church's
thesis, I believe this to be false. As a counterexample, I propose
the thesis that there is no way to formalize in a satisfactory way
the distinction between "finite" and "infinite". (...) however
one formalizes the concept of "the integers", there are
nonstandard models in which there are integers that are infinite
(...) any formalism of the concept "standard integer" must
itself allow for models with infinite standard integers. (...) the
present ZFC axioms (...) are inadequate for deciding the truth or
falsehood of the [Twin Primes] conjecture for finite integers
(...) The thesis that it is impossible to unambiguously state this
conjecture in any formal system makes it all the more fascinating.
\end{quote}

As you all can see, confusion reigns over basic concepts and
methodologies that have been studied and correctly understood
(except for philosophic disagreements) by specialists for at least
to make people understand:

(1) that in order to talk about the proprieties of a "formal
system" today we must specify the underling logic, just as we must
specify the notion of "convergence" before discussing whether the
Fourier series of a function converges or not to the function; (2)
that there is a hierarchy of finitary logics: first-order,
second-order etc.; (3) what can be and what cannot be made with
first-order logic; (4) that there is no reason why one should
restrict all logic to first-order logic; (5) that first-order
logic has some very useful (although "paradoxical") proprieties
that are not shared by higher-order logics (Lindstrom theorem);
(6) that a first-order set theory like ZF can be viewed simply as
a tool to derive results concerning what can be proved about sets
in the "real world", without any philosophical commitment with any
sort of ontology; (8) many models of the continuum are possible,
IR is one of them and IR, as a Dedekind-complete field, is
characterized by axioms of first and second order;

Etc., etc.

If I am not wrong, Bing (and even some experts in set theory)
failed to understand (or accept) point (6), while Kline and the
others failed to comprehend, in the main, point (4) and (8). If I
there must exist a REAL WORLD (RW) containing, among other things,
the REAL REALS and it is not fair to derive conclusions about RW
by means of fictitious reals that are countable in number.
Apparently, he did not understand the following. ZF is strange
because of its very first-order character. But in using ZF we do
not have to commit ourselves with any decision concerning the
ontological status of RW. All that we have to know is that if CH
is provable in RW, then its axiomatic translation CH* is provable
in ZF. We "reduce" RW to a more tractable thing called ZF, which
is in fact artificial, but in which we can show that CH* is
unprovable - thus showing that CH is unprovable in the real world
(whatever this might mean).

REFERENCES (and some suggestions for further reading)

[1] Richard Zach --- Completeness before Post: Bernays, Hilbert,
and the development of propositional logic. The Bulletin of
Symbolic Logic, Volume 5, Number 3, Sept. 1999.

[2] D. Hilbert --- \"Uber den Zahlbegriff, 1900.

[3] R. Dedekind --- Continuity and irrational numbers (Dover).

[4] Mathematical developments arising from Hilbert problems, AMS
1976 (edited by Felix Browder)

[5] Marvin Jay Greenberg --- Euclidean and non-euclidean
geometries without continuity, Monthly, 1979, 757-764.

[6] P. S. Novikov --- Elements of Mathematical Logic.
Addinson-Wesley, 1964. Translation of the first (1959) Russian
edition.

[7] A. V. Pogorelov --- Lectures on the foundations of geometry,
1966 (translated from the second Russian edition by Leo F. Boron).

[8] R. Carnap --- Introduction to symbolic logic (Dover, 1958).

[9] Roger C. Lyndon --- Notes on logic (Van Nostrand, 1966)

[10] Paul Halmos --- Algebraic logic (Chelsea, 1962).

[11] Gregory H. Moore --- A house divided against itself: the
emergence of first-order logic as the basis for mathematics.

[12] Hermann Weyl, David Hilbert and his mathematical work, Bull.
MAS, 1944, 612-654.

[13] Kosta Dosen --- Deductive completeness, Bull. Symb. Logic,
Vol.2, Number 3, Sept. 1996.

[14] Emil Leon Post --- Introduction to a general theory of
elementary propositions (1921).

[15] J. C. Fisher --- Geometry according to Euclid, Amer. Math.
Monthly, 1979, 260-270.

[16] Hilary Putnam --- Models and reality, 1977.

[17] Wolfram Schwabh\"auser --- On models of elementary elliptic
geometry, Symposium on the Theory of Models, North-Holland, 1965.

[18] Alfred Tarski and Steven Givant --- Tarski's system of
geometry, Bull. Symb. Logic, Volume 5, Number 2, June 1999.

Carlos Cesar de Araujo

Date Subject Author
10/10/99 Carlos Cesar Araujo
10/11/99 Alexander Zenkin