Topics include the place of problems in the development of theories of logic and logic's relation to computer science. Specific attention is given to Gödel's incompleteness theorems, predicate logic and its decision and reduction problems, constructibility and Cantor's continuum hypothesis, proof theory and Hilbert's program, hierarchies and unification, proof of the four-color problem, the Diophantine problem, the tautology problem, and many other subjects. Three helpful Appendixes conclude the text.
Topics include the place of problems in the development of theories of logic and logic's relation to computer science. Specific attention is given to Gödel's incompleteness theorems, predicate logic and its decision and reduction problems, constructibility and Cantor's continuum hypothesis, proof theory and Hilbert's program, hierarchies and unification, proof of the four-color problem, the Diophantine problem, the tautology problem, and many other subjects. Three helpful Appendixes conclude the text.
eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
Topics include the place of problems in the development of theories of logic and logic's relation to computer science. Specific attention is given to Gödel's incompleteness theorems, predicate logic and its decision and reduction problems, constructibility and Cantor's continuum hypothesis, proof theory and Hilbert's program, hierarchies and unification, proof of the four-color problem, the Diophantine problem, the tautology problem, and many other subjects. Three helpful Appendixes conclude the text.
Product Details
| ISBN-13: | 9780486171043 |
|---|---|
| Publisher: | Dover Publications |
| Publication date: | 08/18/2014 |
| Series: | Dover Books on Mathematics |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 292 |
| File size: | 21 MB |
| Note: | This product may take a few minutes to download. |
About the Author
Hao Wang (1921–95) was a Chinese-American mathematician, logician, and philosopher. He taught at Harvard, Oxford, and Rockefeller University.
Read an Excerpt
Popular Lectures on Mathematical Logic
By Hao Wang
Dover Publications, Inc.
Copyright © 1981 Litton Educational Publishing, Inc.All rights reserved.
ISBN: 978-0-486-17104-3
CHAPTER 1
ONE HUNDRED YEARS OF MATHEMATICAL LOGIC
We begin by stating some of the central concepts and theorems in a historical and developmental context. Relations to other disciplines will also be briefly outlined. A number of the issues sketched in this chapter will be considered more closely in the other chapters and the appendices.
It is customary to trace back to Leibniz (1646—1716) for conceptual and fragmentary anticipations of modern logic. His notion of a theory of arrangements includes a calculus of identity and inclusion that is in the direction of Boolean algebra. He strove for an exact universal language of science, and looked for a calculus of reasoning so that arguments and disagreements can be settled by calculation.
In 1847, George Boole (1815—1864) published his Mathematicalanalysis of logic in which an algebra of logic is developed, now commonly known as Boolean algebra in mathematics. As logic, it corresponds to the propositional calculus, and has been extended to forms corresponding to the predicate calculus by C. S. Peirce and O. H. Mitchell in 1883; notable contributions along this tradition have been made by E. Schröder, L. Löwenheim, and Skolem.
It is convenient to date the beginning of mathematical logic back to shortly before 1880 when the predicate calculus (first order logic) and set theory were introduced). Two directions of mathematics played an important role in the background : the interest in the axiomatic method; and the concern with the foundations of analysis (in particular, real numbers and arbitrary functions of them). One main trend since about 1880 has been the interplay of the predicate calculus with set theory.
Another important trend was the study of the axiomatic method, both in getting and studying axiom systems for number theory, geometry, analysis, and set theory; and in a general study of the concept of formal systems as a sharpening of the concept of axiom systems with strong results on the limitations of formalization).
One achievement is an exact concept of theoretical computability which yields the discipline of recursion theory and gives a framework for introducing a theory of computation. This last aspect has so far produced little that is immediately useful for real computation, as the major results deal only with theoretical decidability and un-decidability. The development of a theory of feasible computation remains at a rather primitive stage. What is most relevant to the advances in computers is rather the concern common to both areas for explicit formalization which makes mathematical logic a helpful discipline toward training experts in programming and especially in the design of programming languages). A more obvious application is to the design of logical circuits for computers since these circuits correspond naturally to Boolean expressions or expressions in the propositional calculus. By the way, Boolean algebra and a number of simple algorithms are rather simple and can be taught in middle schools.
In recent years mathematical logic has found applications in number theory (e.g., the problem of deciding whether a Diophantine equation is solvable), algebra (e.g., the Word problem for groups, and a proof of Artin's conjecture on p-adic fields), topology (notably proofs of consistency and independence), and an exact theory of infinitesimals. This last application uses a technique first introduced in giving a nonstandard model for the positive integers and touches on a broad philosophical question of intuitive reasoning and its rigid codification. To many, the current formulation of nonstandard analysis appears artificial and there is a natural question whether it is necessary to justify the intuitive use of infinitesimals by way of such a detour.
A similar question exists with regard to the identification of axiom systems with formal systems. There is an inclination to construe the axiomatic method more broadly so that not everything is required to be entirely explicit as in a formal system. On the other hand, we do not possess an exact notion of axiom systems in such a broader sense.
Mathematical logic has for many years been intricately connected with academic philosophy. In the earlier development of mathematical logic, concern with traditional philosophical problems had stimulated advances. But the effect of mathematical logic on academic philosophy seems to have mainly been the provision of an additional excuse for moving away from real and complex questions having to do with man and nature.
The drive toward more reliable and intuitively more transparent reasoning in mathematics has yielded intuitionism with its concept of constructivity and proof theory with its goal of proving by constructive methods the consistency of formal systems which codify nonconstructive reasoning. The possibility of finding constructive interpretations of nonconstructive propositions has tended to tie proof theory to intuitionism rather closely. But this whole area of study has not been particularly fruitful in terms of positive results of reducing nonconstructive methods to or justifying them by constructive ones.
Apart from specific results to be mentioned below, the interaction of the predicate calculus with set theory has also brought about the discipline of model theory which uses the intuitive concept of set to study interpretations of theories formulated in the framework of the predicate calculus.
Nowadays it is common to speak of mathematical logic as consisting of four domains): (1) set theory; (2) model theory; (3) recursion theory; (4) constructivism and proof theory. In addition, there are two less well-defined areas which may be called: (a) logic and computers; (b) "foundations of mathematics".
Another way of characterizing logic is to take it as the study of the syntax (relations between expressions) and the semantics (relations between expressions and their meanings or interpretations) of formal languages and formal systems (chiefly those of logic and mathematics). Roughly then recursion theory and proof theory are concerned primarily with syntax; set theory and model theory with semantics.
Cantor began to study the problem of representing a function by a trigonometric series in 1869 and introduced the concept of derived set (the set of limit points) of a point set (a set of real numbers) in 1872. In 1880, Cantor introduced for the first time infinite ordinal numbers in connection with iterating infinitely many times the process of forming derived sets of a point set. By using the concept of one-one correspondence, Cantor proved in 1874 that real numbers are not countable. In 1883 he published a long article (also as a separate monograph) in which his theory of transfinite numbers was developed systematically for the first time.
In a different direction, Frege published his Begriffsschrift in 1879 in which the predicate calculus was formalized for the first time. A theory of sequences was also introduced which led later to the definition of integers in terms of set-theoretical (or what Frege took to be logical) notions.
The Peano axioms were first published in 1889 using also Dedekind's monograph of the preceding year. An instructive motivation of these axioms is contained in a letter of Dedekind written in 1890 but first published only in 1957).
The continuum hypothesis was first put forth as a conjecture by Cantor in 1878. It says that there are as many reals (points on the line) as there are countable ordinal numbers, or that the cardinal number of the continuum is the first uncountable cardinal number. This was Hilbert's first open problem in his list of 1900 and remains unsettled today.
During the decade of 1900, several basic ideas were introduced. Zermelo explicitly formulated the axiom of choice and offered an axiomatization of set theory. Hilbert for the first time spoke of getting consistency results by examining possible methods of proof in number theory. Brouwer introduced his form of intuitionism. Basing on suggestions of Richard and Poincaré on a "vicious circle principle," Russell arrived at a formulation of ramified type theory which may be thought of as bringing the predicate calculus explicitly into the study of the foundations of set theory.
Over the next two decades Zermelo's axioms for set theory were improved by Mirimanoff, Skolem, Fraenkel, and von Neumann. In particular, Skolem identified the somewhat vague concept of "definite properties" with those definable in the predicate calculus. Löwenheim and Skolem did interesting work on the predicate calculus. The particularly striking result is the "paradoxical" theorem that if axiomatic set theory has any model, then it has a countable model. Since we intend to have many uncountable sets, this reveals a limitation of formal systems.
Over this period, Hilbert, while obtaining no significant definite results himself, exerted great influence by putting forth bold projects from his exalted position as an eminent mathematician. Under his influence Ackermann and von Neumann obtained partial results on proving the consistency of number theory. Limited results were obtained on the decision problem for the predicate calculus (known as the Entscheidungsproblem tout court). Hilbert himself outlined an approach toward proving the continuum hypothesis. The completeness of formal systems of the predicate calculus was defined and posed as an open question.
Beginning from 1930, Gödel published strong results which clarified greatly all these problems and opened up a new era in mathematical logic). In 1930, Gödel published his dissertation in which the completeness of familiar systems of the predicate calculus was established. It turns out that much of the technical part of Gödel's proof had been obtained in a paper of Skolem from 1922, unknown to Gödel at the time. In 1931 the famous incompleteness results were published which establish definitely that formal systems for number theory or analysis or set theory are incomplete and incompletable. Moreover, a corollary is that consistency proofs of a given formal system call for methods of proof which go beyond the system. These theorems dealt a fatal blow to Hilbert's program, which is reductionist and positivistic in spirit, aiming at reducing the rich intuition and experience in mathematics to simple combinational concepts by ways of consistency proofs of the former with the latter. Results were also included in the same paper which suggested negative solutions to the Entscheidungs problem and to deciding the solvability of Diophantine equations.
The incompleteness results were not given in their full general form because the general concept of mechanical procedures and formal systems was not yet available in 1931. Shortly afterwards, building on a suggestion of Herbrand, Gödel introduced the concept of general recursive functions on which Church and Kleene have since done significant work. It was Turing's introduction of a convincing concept of general machines in 1936 which consolidated the by now generally accepted concept of theoretical computability and therewith that of mechanical procedures and formal systems. Once the general concept was available, it was relatively easy to extend Gödel's related result to establish other undecidability results on number theory and on the predicate calculus. (It is interesting to note that Gödel also established the decidability of the richest decidable natural subcase of the Entscheidungs problem.)
In the summer of 1930, Gödel began to study the relative consistency of analysis to number theory, representing real numbers by properties or sentences (propositional functions) of integers. He quickly ran into the Liar and Richard's paradoxes connected with truth and definability. He realized that truth in number theory cannot be defined in number theory and his plan of relative consistency proof did net work. He went on to draw the conclusion that in suitably strong formal systems there are undecidable propositions. Hence, the influence of Hibert's program is clear.
It must have been in 1930 when Gödel began to think about the continuum hypothesis and first heard about Hilbert's proposed outline of a proof of it. He felt that one should not build up the hierarchy in a constructive way and it is not necessary to do so for a proof of (relative) consistency. The ramified hierarchy came to his mind. By 1935 Gödel had obtained the concept of constructible sets, proved that the axioms of set theory (including the axiom of choice) hold for it, and conjectured that the continuum hypothesis also would hold. In the summer of 1938, Gödel extended his results to the extent familiar today: that the generalized continuum hypothesis cannot be disproved by the axioms of set theory, the first major result on the continuum problem since Cantor proposed it in 1878.
It follows from Gödel's incompleteness result that there are nonstandard models for any given formal system of number theory. For an extended period, Skolem had attempted to find nonstandard models of number theory. In 1933 he produced such a model by a new method which to a great extent anticipated the use of ultra-products about twenty years later.
In the area of proof theory and intuitionism, beyond the central incompleteness theorems of Gödel, Gentzen produced a consistency proof for number theory in 1936 which has since undergone various refinements and extensions. In 1932, Gödel put forth an interpretation (or translation) of classical number theory in intuitionistic number theory. In 1942, he found also an interpretation of intuitionistic number theory by means of primitive recursive functionals, which was published only in 1958. A good deal of work has been done since to extend Gödel's interpretation to deal with classical analysis. There has also been extensive study of inductive definitions and predicative (or construetivistic) analysis. Troelstra and others have tidied up somewhat formal studies of intuitionism.
Model theory has gradually emerged since about 1950. At first, results appeared to be elegant reformulation of familiar facts. But then interesting theorems and applications began to appear. In particular, it was also used in the study of large cardinals so that around 1960 Hanf numbers appeared and Scott proved that measurable cardinals yield nonconstructible sets. Results often mentioned as being impressive are Morley's theorem on categoricity in power, and applications to algebraic problems by Ax and Kochen.
The strongest impact on the further development of set theory, including its interaction with model theory, came from Cohen's independence proof of the continuum hypothesis in 1963. Apart from the importance of the result, the method used turned out to have a wide range of applicability). For example, Solovay soon proved the consistency with dependent choice of the proposition that every set of reals is Lebesgue measurable. (He has to assume that there are inaccessible cardinals; it remains an open problem whether this stronger assumption can be avoided).) Apart from using Cohen's method to get various independence results, there has been a general upsurge of interest in other aspects of set theory. For example, there has been much work on the axiom of determinancy including its relation to large cardinals and their relation to descriptive set theory, by D. A. Martin, Solovay, H. Friedman, and others). Jensen and others have examined more closely the structure of constructible sets. Partition properties and indiscernables (tracing back to Ramsey's theorem of 1929 first introduced to deal with a simple case of the Entscheidungsproblem) have been extensively studied by Rowbottom, Silver and others. At present, the continuum problem remains the most challenging special problem ; toward general progress, efforts are made to clarify the nature of large cardinals (especially those which require nonconstructible sets).
The concept of general recursive functions and Turing's computable functions have led to recursion theory and a number of mechanically unsolvable problems which are of particular interest in one way or another. In terms of the general theory, studies have been made of degrees of unsolvability, the arithmetical hierarchy, the hyperarithmetical hierarchy, and generalizations to admissible ordinals and admissible sets, which interact with set theory and model theory. Of the results on particular problems, the most famous are probably the unsolvability of the problem on the existence of solution to Diophantine equation (Hilbert's tenth problem) established in 1970 and that of the word problem for groups established in 1955.
(Continues...)
Excerpted from Popular Lectures on Mathematical Logic by Hao Wang. Copyright © 1981 Litton Educational Publishing, Inc.. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
A noted logician and philosopher addresses various forms of mathematical logic, discussing both theoretical underpinnings and practical applications. Author Hao Wang surveys the central concepts and theories of the discipline in a historical and developmental context, and then focuses on the four principal domains of contemporary mathematical logic: set theory, model theory, recursion theory and constructivism, and proof theory.
Topics include the place of problems in the development of theories of logic and logic's relation to computer science. Specific attention is given to Gödel's incompleteness theorems, predicate logic and its decision and reduction problems, constructibility and Cantor's continuum hypothesis, proof theory and Hilbert's program, hierarchies and unification, proof of the four-color problem, the Diophantine problem, the tautology problem, and many other subjects. Three helpful Appendixes conclude the text.
Dover (2014) republication of the edition published by Van Nostrand Reinhold, New York, in 1981, and reissued by Dover in 1993 with a new Postscript by the author.
See every Dover book in print at
www.doverpublications.com