Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



[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 "Dedekindcompleteness" (or "cutcompleteness"). 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 wellknown 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 "metaaxiom"  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 completeness. (Instead of "syntactic" the adjectives "deductive" and "prooftheoretic" 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. 7879.) 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 Hilbert's strong influence. See also Carnap [8], p. 1734. Note 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 wellknown anomalies involving firstorder systems. Thus, although firstorder 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 literature. (See also an elegant algebraic formulation of this 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 "firstorder" from "higherorder". 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, 198081):
\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 instead is concerned about a shortage of algorithms, I get the uneasy feeling that someone is tinkering with basic traditional concepts. What is the beef? One is that if a mathematician uses traditional concepts in asking a question, the axiomatic set 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 five decades! Five decades of intense activity were not sufficient 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: firstorder, secondorder etc.; (3) what can be and what cannot be made with firstorder logic; (4) that there is no reason why one should restrict all logic to firstorder logic; (5) that firstorder logic has some very useful (although "paradoxical") proprieties that are not shared by higherorder logics (Lindstrom theorem); (6) that a firstorder 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 Dedekindcomplete 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 understood him correctly, the whole point in Bing's mind was this: 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 firstorder 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 noneuclidean geometries without continuity, Monthly, 1979, 757764.
[6] P. S. Novikov  Elements of Mathematical Logic. AddinsonWesley, 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 firstorder logic as the basis for mathematics.
[12] Hermann Weyl, David Hilbert and his mathematical work, Bull. MAS, 1944, 612654.
[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, 260270.
[16] Hilary Putnam  Models and reality, 1977.
[17] Wolfram Schwabh\"auser  On models of elementary elliptic geometry, Symposium on the Theory of Models, NorthHolland, 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



