Reviews (19)

Absolutely rediculous
WAY TOO MANY TYPOS!!!!!! There were so many typos, it made it extremely difficult to follow this book at times.As a first time student to mathematical logic, I found this to be just too much.People who are veterans with logic and logicians may easily spot typos, but for a first time student of the subject, I was confused as hell at some parts simply because there was a typo.I wasted hours trying to figure out some parts (such as the factorial function in chapter 6) when I finally found out that the reason why I couldn't figure it out was because of a typo. The Errata sheet on the internet IS 35 PAGES LONG!!!! I didn't pay money to correct a horde of typos! God that pisses me off.

Prefer the old edition
I have used the old edition for a class in computability and logic where the students did not have much background in either. Having used the new edition this year, I find I greatly prefer the old one. The new one may be more rigorous, but it is much harder to read and understand for students without the background. The first part is not so bad, but the second half on logic gets too involved in the proofs and the students lose sight of the overall pupose and what these result really mean.

Reviews (2)

Another Dover classic reprint at a bargain price.
Another classic reprintrom Dover at a reasonable price. Martin Davis is a very well-known worker in the area of logical foundations of computing.This book covers muchfascinating material and provides answers to some deep questions relating to the limits of computations. The material can be a little dry but worth the effort. The book is worth the price for the appendix which is a reprint of an article by Davis on the proof of the unsolvability of Hilbert's Tenth Problem.

Mapping the Outer Limits of Computation
The book introduces the theory of computability and non-computability tothe mathematically-comfortable.The theory of recursive functions providesentry to that theoretical territory at the limits of what is computable andwhat is solvable.The theory is relevant to important philosophicalquestions and also in the theory of computing and what is possible (andnever possible) by use of computing machines.

The result for philosophyis establishment of absolutely unsolvable problems and undecidablequestions, even ones that can be completely and precisely formulated usingrigorous logic.The result for computing is problems that are absolutelyunsolvable by use of a computer program.

So what problems aretheoretically solvable by a computer program?First, the Universal TuringMachine (UTM) is presented along with the famous demonstration that alluniversal computers are equivalent in the sense that any one of them can bemade to simulate any of the others, using a suitable representation.

So,if we establish that the computer we have at hand is a universal computer,we can be confident that, in principle, anything that any computer cancompute, this one can also.

The book goes on to address what evenuniversal computers can't do.The most well-known result incomputer-science circles is the unsolvability of the halting problem.Thatis, if the computer is powerful enough to be universal, one of itslimitations is the impossibility of an algorithm that will determinewhether any program for that machine will always terminate for all inputs. It is as if the price of universality is the inevitability of programs thatwon't finish, along with having no absolute way of telling whetherarbitrary given programs will finish or not.

Davis maps the boundarybetween the impossible (the unsolvable) and the merely inhumanly difficult(the computable).With that foundation, one can move on to other work thatintroduces what has been learned about computational complexity and how toapply the analysis of algorithms to finding computational methods that arepractical and no more complex than absolutely necessary.

Reviews (2)

Very good but be aware of omissions
This book is indeed much shorter than Principia, mainly because it is derived for lecture notes for a 1 semester PhD course. It is also a lot clearer than PM. But the notation is largely the same, which makes for hard reading if your are under 50. Quine's proof format doesn't take up much space, but has always eluded me. This book contains the best treatment of truth functional and quantificational logic prior to natural deduction and truth trees.

I like the set theory of this book, but I warn you that it is very nonstandard. Even ardent lovers of Quine's NF theory hate
the ML theory of this book.

The weakness of this book is its treatment of metatheory:
consistency, completeness, decidability, categoricity. The treatment of Godel's incompleteness is detailed and highly original (altho' it owes more to Tarski than to Godel). But it is very difficult, and Smullyan (1991) is much better.
Quine also had no clue re model theory or recursion.

I respect the historical remarks a lot. Just one big omission: Quine, like nearly everyone of his generation, missed that
math logic as we know and love it does not descend from Frege, but from an 1885 article by C S Peirce.

Reviews (5)

Masterpiece
I don't think you get this in a lot of other books. Just look at the Historical Notes; In themselves a guided direction to the most important work on logics. This is truly time saving instead of go wondering what books to read, up to the date of Quine's book of course.

In the end it also contains bibliography, but also a note to a whole other index covering literature up to 1935, this is truly at great value.

I find this book helpful in analysis concerning ideas; Whatever they are, since language usage is the tool for thought, even if not written down.

It's simply a MIND-SPEAKER.

Also more newer books, in for instance computer science, in my personal opinion, skip important questions already asked by scientists which then have been elaborated on.

People who read logic for the first time, like me, ask fundamental questions in order to understand, following Quine's reasoning is surely educational.

A good start
Like any great book, this one could be a bit, though not too much, better. By far and away the most useful element of Quine's book is his treatment of translating ordinary English into logical schemata. I have never seen such a lucid and effective presentation of the task, and I recommend the book very highly to anybody on that account. His presentation of truth-functional and quantificational schemata are solid are simply excellent. The book, however, is not without its defects of which I should caution prospective buyers about. First, there are many treatments in the book of historical interest, but to a student of first-order logic they may seem to be a bit excessive. His incorporation of Polish notation, while fascinating in its own right, is not in accorance with Quine's drive for efficiency and conciseness. A similar account goes for his treatment of Boolean algebra. It is in that treatment that Quine introduces many ideas indispensible to quantificational logic, yet it is tempting to skip over those chapters when one can sufficiently delve into quantification theory. Secondly, his notation is, as another reviewer points out, unorthodox. It is very effective and in my opinion superior to the conventional formality, but this could be difficult to deal with, and one wonders if Quine should have been more cautious about varying his symbols from the norm. Finally, Quine's treatment of the Completeness Proof and the Lowenheim Theorem, while quite solid in their own right, could be more effective. Quine seems to be keen on applying a constructivist approach to the proof, and spends many pages on definitions and lemmas that can be avoided. One can provide a proof by contradiction in order to sufficiently demonstrate most of his treatment of the matter, as so much of it is spent proving the "law of infinite conjunction," which is really only an 8 step proof. I won't go into the details here, but keep that in mind when studying the chapter. Nevertheless, Quine's work is as entertaining as it is rigorous.

a great introduction to first-order logic ...
Quine is well-known in this century for being one of the premier analytic philosophers in the Anglo-American tradition.He probably used this book for his upper-divisioncourse in logic for philosophy majors.After reading this book, I can see his reputation is well-justified.

This book is more than just a textbook in logic.In his own way, Quine shows in his examples just how difficult it is to break down ordinary language into symbolic logic, and in the process (hopefully), one should learn both rigorous thinking and charity.These are rare commodities today.

Quine has the rather idiosyncratic position that modal logic only confuses matters.However, I would rather read a complete introduction to modal logic, than to receive only a chapter's worth of treatment.Hence, I can deal with his excluding modal logic from this book.

I do wish there was a short chapter or glossary on informal logic, since many other treatments do continue to use thoseterms (e.g. Copi).Knowing the terminology does help one to communicate in prose one's analysis of an argument.It does help to know all those latin distinctions (e.g. ad hominem, ad nominem, ad populii, petitio principii, etc.).

Reviews (3)

It's painted a turn-on red...
Often duplicated, never imitated -- this is the real "Boss Hoss" of mathematical logic textbooks.People complain about the "cathedral-like" architectonic of this (unfinished) book, and there are more symbols than you'd ever need, but that's cool 'cause Church is really having a symbol party in the book (and yes, those crazy lambdas are invited): you can see those symbols gettin' wild right there on the page.And people think it's out of date, but the real story is that this is the most logistic power which is really street legal -- anything more and you're having a conversation with yourself.Is it safe?Hell no; even my second-order logic still doesn't work right.But in the right hands, it'll shut any fool down.

a classic, but mostly useful as a historical reference
I give this book 5 stars out of respect for its enormous contribution to mathematical logic; for no doubt many of the authors of the more modern math-logic texts were greatly influenced by this book. But with that said, all of the material here is a proper subset of other current books which present the material much more clearly and using better notation. Examples include Burris' "Logic for Mathematics and Computer Science", Ebbinhaus' "Intro. To Math Logic", and Gallier's "Logic for Computer Scientists".

One of the classics
This book, which first appeared in print as an issue in Annals of Mathematics in 1944, is now a classic in mathematical logic, and is still worth perusing in spite of the out-dated notation. The author outlines comprehensively the propositional calculus and predicate calculus. Although the book is mostly formal in its style, the author does introduce the reader to some elementary notions in logic, and some brief commentary on what would now be classified as philosophical logic. He defines logic as the analysis of propositions and their proof according to their form and not their content. He notes also that inductive logic and the theory of partial confirmation should also be included as part of mathematical logic. There are exercises throughout the book, and so it could conceivably be used as a textbook, in spite of its publication date. The book could better be used as a historical supplement to a course in mathematical logic or one in the philosophy of logic.

In the introduction to the book the author defines the terms and concepts he will use in the book, with a discussion of proper names, constants and variables, functions, and sentences. He adopts the Fregian point of view that sentences are names of a particular kind. His discussion of this is rather vague however, for he does not give enough clarification of the difference between an "assertive" use of a sentence and its "non-assertive" use. Readers will have to do further reading on Frege in order to understand this distinction more clearly, but essentially what Church is saying here is that sentences are names with truth values. The existential and universal quantifiers are introduced as well. And here the author also introduces the concepts of object language and metalanguage, along with a discussion of the axiomatic method. The author distinguishes between informal and formal axiomatic methods. The modern notions of syntax and semantics are given a nice treatment here, and the di

scussion is more in-depth than one might get in more modern texts on mathematical logic.

Chapter 1 is a detailed overview of propositional logic, being the usual formal system with three symbols, one constant, an infinite number of variables, rules on how to form well-formed formulas, and the rules of inference. The deduction theorem is proved in detail along with a discussion of the decision problem for propositional logic, with the famous truth tables due to W. Quine introduced here. The notions of consistency and completeness are briefly discussed.

The discussion of the propositional calculus is continued in the next chapter where a new system of propositional calculus is obtained by dropping the constants from the first one and adding another symbol (negation). The two systems are shown to be equivalent to each other using a particular well-formed formula in the second one to replace the constant in the first. Other systems of propositional calculus are also introduced here, using the idea of primitive connectives such as disjunction, along with various rules of inference. Church also outlines an interesting propositional calculus due to J.G.P.Nicod, which assumes only one primitive connective, one axiom, and only one rule of inference (besides substitution). The author also introduces partial systems of propositional calculus, with the goal of showing just what must be added to these systems to obtain the full propositional calculus. He discusses the highly interesting and thought-provoking intuitionistic propositional calculus, due to A. Heyting, which is a formalization of the famous mathematical intuitionism of L.E.J. Brouwer. The system he discusses is a variant of Heyting's and he gives references to the positive solution of the decision problem for this system. The author ends the chapter with a brief discussion of how to construct a propositional calculus by employing axiom schemata.

The author then moves on to what he has termed functional calculi of first order beginning in the next chapter. Called predicate calculi in today's parlance, the author first defines the pure functional calculus of first order, and shows that the theorems of the propositional calculus also follow when considered as part of this system. Free and bound variables are defined, and Church proves explicitly the consistency of this system, and the deduction theorem. The important construction of a prenex normal form of a well-formed formula is discussed, and the author shows that every well-formed formula of the functional calculus is equivalent to some well-formed formula in prenex normal form.

In chapter 4, the author gives an alternative formulation of pure functional calculus of first order, wherein rules of substitution are used and axiom schemata are replaced by instances, making the number of axioms finite. The Skolem normal form of a well-formed formula is defined, which sets up a discussion of satisfiability and validity. The author then proves the Godel completeness theorem, which states that every valid well-formed formula is a theorem. This is followed by a very well written discussion of the Skolem-Lowenheim theorem, and an overview of the decision problem in functional (predicate) calculus.

Editorial Review

Could it be true that Whitehead and Russell's Principia Mathematica is the most influential book written in the 20th century?Ask any mathematician or philosopher--or anyone who understands the impact these fields have had on modern thinking--and you'll get a short answer: yes. Their goal, to set mathematics on a firm logical foundation, was revolutionary, and their tools and rigor continue to influence modern professionals. Using Peano's symbolic logic, they formalized axioms and produced theorems (including the famous "1 + 1 = 2") in orderings, continuous functions, and other areas of mathematics.

Reviews (2)

Finally -- Straight Talk About Incompleteness!
Well. This is the book. Read this instead of, or before you read Goedel�s paper. Within 20 pages you will know the �trick� that Goedel used. It�s a beauty, but it is far easier to see it under Smullyan�s tutelage than by coming to the classic paper cold, since Goedel uses a more difficult scheme to achieve his ends. Much work has been done since 1931, and we get the benefit of the stripping-down to essentials that such as Tarski (and Smullyan himself) have contributed.

The book has much of interest to those who wish to pursue the subject of the incompleteness and/or consistency of mathematics, or to come at Goedel from a number of angles. For me, though, the first 3 chapters were enough. I just wanted to find out how K.G. did what he did. Now I know, and I know where to go if I need even more.

The exercises are helpful to keep you on track and test your understanding. They also contribute materially to the exposition. A stumbling-block for many readers will be the extremely abstract nature of the discussion, and the new notations and definitions that constantly come at one. Viewing numbers as strings and strings as numbers (and knowing when to switch from one view to another) will be confusing at first. This is the hard part: what Goedel did, in essence, is demonstrate that one can view proofs in two ways � as numbers, and as strings of characters. As in viewing an optical illusion, it is sometimes tough to hold the proper picture in mind.

Smullyan�s book �First-Order Logic� is enough preparation for this work. One must here, even more than there, keep straight the difference between the �proofs� that are part of the subject matter (and so are strings of characters), and the proofs we go through that verify facts about these strings. Before we started reading this book, of course, we had some informal sense that we were going to prove something about proofs. What we are REALLY doing, though, is proving something about �proofs�. You get the picture. Goedel must have been a lot of fun at parties.

Mainline Incompleteness with this Book!
I highly recommend this title because it supplys all the necessary proofs for a nuts and bolts understanding of incompleteness, including incompleteness proofs for Peano arithmetic and the unprovability ofconsistency.

This title is a difficult read but the only prerequisite isa familiarity of first-order logic equivalent to a one semester collegecourse.

A lot of the proofs are based on new material and are easier tounderstand than the original work by KG.

An added benefit is theexercises.They are not impossible and aid in one's understanding.

Reviews (10)

For the history buff
There are at many academic pathways to Godel's Incompleteness theorems: philosophy, computer science, and mathematics, to name a few. What does this presentation of the results - among the many others available - have to offer the wide readership it is likely to attract?

To begin with, it is a reprint of the first English translation of Godel's original published Incompleteness proofs. It's slim and it's cheap, and includes a good detailed and clear "introduction" which is really a less formal paraphrase of the results with some additional information and clarification provided. The real value, though, is in the details of the proofs. Godel's original proofs - unlike many of the easier, more modern equivalents - are constructive. It was Godel's intention to formulate a universally acceptable proof of the inadequacy of Hilbert's program (which sought to defend mathematics as science of consistent formal systems) and of Russell's and Whitehead's logistic philosophy in Principia Mathematica (which sought to reduce all of mathematics to a theory within Russell's formal logic). With his constructive proofs, Godel produced a document of historical relevance to each of the major early 20th century philosophies of math: Formalism, Logicism, and Intuitionism; criticising the first two positions with an argument compatible with the third. Within the same proofs, he also provides the basic definition of the (primitive) recursive functions. In this sense - in containing the first published results of recursive function theory - Godel's original proofs have significance in the history of computer science and mathematics proper. These original arguments, then, have a clear place history of mathematical logic beyond the simple statement of their results, and are well worth reading for their historical significance.

As has been mentioned by other reviewers, there is a lot of typos in the text, some of which aren't good for the integrity of the argument. But, to be honest, this is hardly a text to learn from - it's simply contains too many fine details. Rather, it would make a valuable addition to the library of anyone with sufficient interest in the history of formal logic to want a copy of the original argument, and who is mathematically competent enough to correct the numerous errors as they read through it. 5 stars for the combination of price and content - though an errata sheet from Dover would certainly be an improvement.

In addition to this publication, there are numerous good accounts of the Incompleteness theorems:

An excellent informal account can be found in "Godel's Proof" by Nagel and Newman. This is about right for the reader who wants to know the argument without having to worry about all of the formal technicalities. As technical accounts go, Smullyan's "Godel's Incompleteness theorem's" isn't bad, and it proves a slightly more comprehensive version of the results. Smullyan was an extraordinary expositor of mathematical logic: his account is both conceptually clear and insightful, and the theorems are approached in a unique stepwise fashion, building up to the main theorems. An interesting (though *difficult*) account of Incompleteness can be found in the "Syntax" chapter of Quine's "Mathematical Logic". This is remarkable for proceeding by simple syntactic considerations, without the use of any basic number theory. Lastly, there are countless good proofs of the Incompleteness theorems to be found in the numerous good introductions to recursive function theory (Rogers or Cutland are O.K.). For the mathematically inclined this approach is good, as it offers immediate access into some of the more interesting undecidability results that followed Godel's results.

Unbelievable theorem
Reading through the reviews of self-proclaimed math geniuses (see some of the below unhelpful reviews for examples) is hardly edifying, so I feel compelled to lend a hand. Here are a few comments about this publication:

First, the introduction does a poor job in explicating the theory. I suppose it gives you the basic idea, but this is hardly the first account of the theory one should read. Brathwaite does not connect all of the dots, and it will take a long time to figure out how the proof works from his intro, if you can do it all. (And that's not a challenge or insult; it simply isn't that well written.)

Second, forget about wading through Godel's proof on your own. The reviewer who claimed to do so with two years of algebra and a really good dictionary is simply lying. You do not wade through difficult theorems in mathematical logic without the appropriate tools. And the appropriate tools include having done similar but simpler proofs on your own and having a solid background in mathematical logic. Without this background, it doesn't matter whether you have the ability to be a mathematics professor at Princeton or place top five in the Putnam - you simply will not understand the proof in a rigorous manner. By all means, take a look at it to get a general feel for what's going on, but if you want a semi-technical account read Smullyan's "Godel's Incompleteness Theorems."

Third, as one reviewer pointed out, there are multiple errors in this printing of the proof. This makes what was a tall task virtually impossible.

So what did Godel do that was so interesting?
He proved that there were certain arithmetical statements about whole numbers that were not provable but true. (This was important because it shattered the widely held belief that if you stated a problem in mathematics clearly enough you would be able to determine whether it was true or false. Godel showed this isn't always the case. As an aside, simpler mathematical systems have been shown complete; that is to say, they can answer any well formed question.)
So, how can something be true but unprovable?
The sentence Godel constructed said this, more or less: I am not provable. This statement, if true, is not provable. If it is provable it's false, and correct systems (systems that do not prove false statements) cannot prove false statements. Therefore, it must not be provable. But then it's saying something true, and thus it's true but unprovable. Now, I'm simplifying and being sloppy, and you need to know about the difference between mathematical statements and metamathematical statements, but in a nutshell that's the thrust of his first theorem.

The other interesting aspect of his proof is that he constructed a statement that referred to itself indirectly. Russell, in Principia Mathematica - the work that contains the arithmetical system that served as the model for the arithmetical system in Godel's proof - created a "Theory of Types" which did not allow statements to mention themselves. But the sentence "I am not provable" references itself so it would seem that I've erred. But in fact I haven't; I just didn't fully explain how that sentence worked. (I know you were worried, if for just an instant.) Where was I . . . Godel created a sentence which referred to itself indirectly. The sentenced said, "Sentences with such and such characteristics are unprovable." It so happened that a sentence with such characteristics was itself. Thus, it referred to itself, but only indirectly and not in violation of the "Theory of Types."

All of my blathering, I hope, has impressed on you . . .
1) That this proof is worth understanding.
2) That you shouldn't believe anyone who tells you they worked through and understood the proof without having a signficant background in mathematical logic and the history of the proof. If you don't understand certain basic features of Principia Mathematica you're not going to grasp fully his proof.
3) That you should get an introductory account. Nagle's "Godel's Proof" is excellent and easy to understand. Smullyan's "Godel's Incompleteness Theorems" is more difficult, but not impossible and amounts to what would serve as the textbook of a solid mathematical logic course or two at an elite university.
4) That you shouldn't buy this work if you're hoping to work through his proof, unless of course you have the requisite training. Brain power is not enough.

Editorial Review

Gödel's incompleteness theorem--which showed that any robust mathematical system contains statements that are true yet unprovable within the system--is an anomaly in 20th-century mathematics. Its conclusions are as strange as they are profound, but, unlike other recent theorems of comparable importance, grasping the main steps of the proof requires little more than high school algebra and a bit of patience. Ernest Nagel and James Newman's original text was one of the first (and best) to bring Gödel's ideas to a mass audience. With brevity and clarity, the volume described the historical context that made Gödel's theorem so paradigm-shattering. Where the first edition fell down, however, was in the guts of the proof itself; the brevity that served so well in defining the problem made their rendering of Gödel's solution so dense as to be nearly indigestible.

Reviews (1)

Still an interesting read....
Those interested in mathematical logic will appreciate this book written by one of the main contributors to the field in the twentieth century. The technique of "currying" in higher order logic is named after the author, wherein unary functions can be used to emulate functions with many parameters. The book was first published in 1963, reprinted in 1977, and so is not a up-to-date treatment of mathematical logic, but it could still be used as an historical supplement to a course in this subject. The reader should be aware though the terminology employed by the author is very idiosyncratic and therefore it may not reflect what is currently used in the literature.

The first chapter of the book could be considered an introduction to the philosophy of logic and mathematics. The author though views "philosophical logic" as the study of the principles of valid reasoning, and this is to be distinguished from "mathematical logic", wherein mathematical systems are constructed to study (formally) the principles of valid reasoning. One can also according to the author view logic as a theory in itself, and many "models" of it can be studied, in much the same way as many different models of geometry can be considered. The author also discusses very succinctly the logical paradoxes, and the different schools of thought in mathematics, such as Platonism, intuitionism, and formalism. The author clearly advocates the formalist school of thought in this book.

In chapter 2, the author gets more into the details of formal reasoning, the field of semiotics is outlined, and the author first begins defining the grammar and symbols for the upcoming discussion. A theory is defined as a class of statements, and consistency and decidability of theories is defined. The idea of a deductive theory is also defined, and the author defines the notion of such a theory being complete. The notions of consistency, decidability, and completeness are the familiar ones now entrenched in current textbooks on mathematical logic. A formal system, according to the author, is a theory in which the parameters of the statements of the theory are introduced as unspecified objects, and the statements of the theory make assertions on the properties of the parameters and their relations. The author considers syntactical systems, wherein the formal objects are taken from some object language, and what he calls Ob systems, which are essentially the systems considered in modern mathematical logic.The author employs the familiar Godel numbering scheme to numerically represent formal objects. The notion of algorithm is brought in here as an effective procedure to manipulate the formal objects of a system.

The next chapter is basically an introduction to the analysis of what would now be called the metalanguage of a formal system. This analysis is done in terms of what the author calls epistatements and epitheorems. Examples of these epitheorems include the Godel incompleteness theorem and the Skolem-Lowenheim theorem. The author introduces and classifies variables, and defines free and bound variables. A brief introduction to the lambda calculus and combinatory logic is given.

Then in chapter 4, the author discusses logical systems which are relational but with no bound variables. These are called logical algebras by the author, and the reader will encounter the famous truth tables and lattices in this chapter. A discussion of the Heyting algebra is given in the notes to the chapter. The reader interested in the more exotic types of algebraic logic, such as quantum logic, could benefit greatly from the reading of this chapter.

The logic of propositional calculus in terms of algebraic logic is discussed in chapter 5. Called propositional algebras by the author, the author proves the deduction theorem for such systems in this chapter. Interestingly, the L systems introduced by Gentzen are also discussed in this chapter. Although there are much better overviews of Gentzen's work in the current literature, a reader may still profit from a perusing of this chapter. L-systems where negation is added is then the subject of the next chapter.

Quantification in formal systems is taken up in chapter 7, considered both in the usual predicate calculus and in L systems. Prenex normal forms, the Herbrand-Gentzen theorem, and the completeness theorem are discussed in fairly good detail, albeit with old-fashioned notation.

Reviews (8)

Great stuff.
First, this isn't one of Smullyan's popular puzzle books- its a serious mathematics text. Second, don't use this as your first exposure to first-order logic (note the title doesnt say "Introduction to ...")- although logically self-contained, it requires some experience to appreciate what a neat little book this is.

It's not a general mathematical logic text- there is no model theory (beyond basic Skolem-Lowenheim), incompleteness, recursion theory, or set theory. It covers tableaux (this alone is worth the price of the book), Hilbert-style axiomatic systems (briefly), sequent systems, Gentzen's Hauptsatz and Extended Hauptsatz, Craig's and Beth's theorems, and more. But the heart of the book is completeness theorems, their proofs, and closely related material such as compactness and Herbrand-like theorems. Smullyan shows there are two main approaches to completeness (analytic vs. synthetic), breaks each into stages, provides nice abstracted formulations, and usually gives several different proofs of each result. The centerpiece is his "Fundamental Theorem of Quantification Theory", a theorem associating a truth-table tautology with every valid first-order sentence (check out the amazingly slick proof of completeness for the the Hilbert-style system that this provides). Similar constructions such as magic sets are also discussed. All this forms a much more extensive and illuminating look at completeness proofs than I've seen elsewhere.

The first-order logic used in the book has no equality and no function signs. There are few exercises, most of them simple. Smullyan writes clearly and with an appropriate amount of rigor (but its not as polished as his later books). Makes a great supplement to more general-purpose introductory mathematical logic books. If you haven't seen the tableau method yet buy this book immediately. Experienced readers will appreciate the sophisticated coverage of completeness proofs.

An Oddity But a Good-ity. Wait, that's terrible.
The reviewer from Illinois gave a very good characterization of Smullyan's style here:
"Smullyan has divorced logic from its roots: logics are simply recursively-defined sets of sentences and mappings, and that is that. No discussions, ala WvO Quine, on the history or linguistic difficulties of a concept, just definition and proof."
Readers familiar with Smullyan's enormous talent for popular exposition may be expecting the same herein: not so. This is very much for people who have attained what medical professionals call "mathematical maturity" (which is about as difficult to attain as zen, yet perhaps amounts to little more than the ability to read VCR instruction manuals). For example, the very first section is a wiz-bang treatment of trees (not the usual graph-theoretic ones), defined in the abstract/axiomatic fashion.
Of course, people who spend perhaps way too much of their time steeped in math are attracted to treatments of just this sort.
A structural characterization in terms of sets and mappings is much more meaningful, interesting, and aesthetically pleasing to those with these unusual inclinations (compulsions?) than a characterization framed significantly by historical motivation (please understand that I'm speaking roughly here). This is why I gave a positive review. A star was witheld for the selfish reason that I'm not sure I'll find much use for such an odd treatment of model theory, the topic for which I was seeking a more mainstream treatment when I purchased this. Regrets are nonetheless few: time spent reading Smullyan is never a waste.

Reviews (1)

Reviews (6)

The essential essence of set theory in 100 pages
This book is an excellent primer on the basics of set theory that all graduate students need, but are not necessarily obtained in the general undergraduate curriculum. Halmos writes in an abbreviated, yet effective style that imparts the necessary details without an excess of words. Theorems and exercises are very few, so it really cannot be used as a textbook. If you need a great deal of explanations, then it is not for you. However, if your need is for a book that distills the essence of set theory down to the shortest possible size, then this book should be yours, either in your college or personal library.

Mercy Sought
My previous review of Halmos' book stands.Exceptional book, but ... As an example of a question in the book to whet some appetites and in seeking someone's kind mercy in actually answering it for me and putting me out of my misery, consider p.59 on the Axiom of Choice. Quote: if {X (sub)i} is a finite sequence of sets, for i in n say, then a necessary and sufficient condition that their Cartesian product be empty is that at least one of them be empty ... (The case n=0 leads to a slippery argument about the empty function; the uninterested reader may start his induction at 1 instead of 0). Unquote.Induction from 1 is no problem.The slippery argument stuff (and other similar pearls thoughout the book) sends me wild.What is the slippery argument.Please.Anyone.With thanks to Paul Halmos for making my life 'miserably interesting' (sic)!!

Reviews (4)

A real bargain by a true master
Rudolf Carnap was one of the greatest philosophers of the 20th century, and the only student of Frege's worth thinking about. But what a student!

This is his intro text, a doubtful first text, but full of insight for those who already know some logic. Carnap trained as a mathematician; surprisingly, his text is of value mainly for philosophers. For instance, this is the ONLY undergrad logic text I know that grapples with the intension-extension dichotomy, with the Carnap-Morris syntax-semantics-pragmatics trichotomy. Metatheory is nonexistent, and Carnap's notion of proof is emphatically too casual for my taste.
The book is dated. In its treatment of first order logic, Carnap is a bit too loyal to Principia Mathematica. His axioms are a bit pedantic, a bit inelegant for my taste. (I should admit here that I have devised a radically simpler axiom for the truth functors, and am working on a simplification of quantification theory. Even if my theory doesn't pan out, I still believe that UG and UI suffice for quantifiers.) You won't learn any natural deduction, truth trees, or Gentzen sequents here. You most definitely won't learn anything about recursion. But the exposition incorporates thoughout Carnap's greatest discovery: his formal theory of semantics. You will also learn more about the logic of relations than you will in any other undergrad text. You will be given an idea of the mathematical power of logic (infinity, continuity, numbers). You will even be introduced to the lambda calculus, Alonzo Church's greatest discovery. Carnap was comfortable with the notion of predicate like few logicians since.

Part II of the book is without parallel anywhere: an introduction to a very wide range of axiomatic theories, presented as interesting applications of modern formal logic. This is a wonderful reference for ZF set theory, Peano axioms, Tarski's axioms for the reals, the Hausdorff- Bohnenblust axioms for topology, axioms for geometry, space-time, and mirabile dictu, even mereology. Other texts present at most the first 2 items on this list.

good books
It ismy experience as a reader that good books are always books thathave lots of examples because they make our understanding easier.Therefore, if this math book has examples in it,then it must mean it isvery good.So I recommend that whenever you have a chance to see it that youbuy it.

Reviews (5)

A classic exposition of ZFC
Mathematics is a first order theory whose primitive formulae
all take the form 'a is a member of b'. 'a' can be a set or atom; 'b' must be a set. If you do not object to the preceding sentence, then read on.

Axiomatic Set Theory (AST) lays down the axioms of the now-canonical set theory due to Zermelo, Fraenkel (and Skolem), called ZFC. Building on ZFC, Suppes then derives the theory of cardinal and ordinal numbers, the integers, rationals, and reals, and the transfinite--Cantor's paradise. Suppes accomplishes in 250 well laid out pages what required 800 crabbed pages in Principia Mathematica.

This book evolved out of a class Suppes taught at Stanford in the long ago 1950s. It has since remained the best book of its kind. The reason is that subsequent presentations of set theory are too difficult, too contrived, too clever by half. They disdain the basics as old hat.

AST has several valuable pedagogical features.

1. The introduction to relations and functions is the best I know of. I am disappointed at how little attention has been devoted to relations and relational algebra in recent decades.

2. Suppes has a nice way of introducing a simple axiom, then showing that that axiom is a theorem when a more complicated axiom is later introduced. In particular, he develops the theory of cardinals by means of a temporary axiom to the effect that equipollent sets have identical cardinalities. This axiom becomes a theorem when the axiom of Choice is introduced in the final chapter.

The axiom schema of Replacement is introduced as late as possible, to enable transfinite arithmetic. He then turns around and shows that Replacement makes Subsets and Pairing redundant.

In my opinion, the greatest flaw of ZFC is that defining a cardinal number requires either the axiom of Choice, or Infinity plus the subtle notion of set rank. Frege and Russell had an appealing definition: a cardinal number is an equivalence class of sets under equipollence. That definition does not work in ZFC. It does work in Quinian set theory. Suppes does a yeoman's job of battling this flaw.

3. Suppes defines a finite set in the interesting way Tarski proposed in 1924.


AST contains hundreds and hundreds of theorems, man of them useful classics. In many cases, the proof is an exercise. Suppes's proof are of the informal sort typical of mathematics. What AST does can be done more rigorously: type 'Metamath' into Google and see for yourself.

Even though Suppes is a philosopher, this book is almost entirely a mathematical exercise. The reader will not get a good feel for how set theory is part of analytic philosophy, and how it has been a contentious subject. The writings ofFraenkel and Bar Hillel are better in these respects. Suppes does highlight the reservations re the axiom of Choice, but Cohen's proof that Choice is independent of ZF has largely laid those reservations to rest, except for those of us with constructive sympathies. AST gives no hint that Replacement and Power Set give us far more set theory than is needed in practice. Thanks to the work of Aczel and Barwise, published around 1990, we have a better idea of what it means to dispense with Regularity. Shortly after the 1960 publication of AST, Lawvere and others began to lay down the category theoretic foundation of mathematics knowns as topos theory. That theory puts ZFC in a new light. Personally, I am astonished that an axiomatization of finite sets simpler than ZF has yet to emerge.

Still interesting...and still important.
One does not hear about set theory too much these days, no doubt due to the de-emphasis of foundational discussions in mathematics. Foundational questions of course were the focus of much attention in mathematics in the early twentieth century, this taking place because of the many paradoxes in set theory and due to the influence of the philosophers. Set theory, the theory of types, and mathematical logic are still very important though in computer science and in artificial intelligence, due to the needs in these fields for knowledge representation, computational models of intelligence, and automated reasoning. This book could serve to introduce these topics or as an historical reference to the issues as they were hotly debated in the last century.

The first chapter gives an informal introduction to the notion of a set, first-order predicate logic (notions of bound and free variables and quantification), and the Zermelo-Fraenkel axioms of set theory. The author describes the difficulties in the "axiom of abstraction" in the writings of Frege as pointed out by Bertrand Russell. It is pointed out that the axiom of abstraction is in fact an infinite collection of axioms, thus motivating the concept of an "axiom schema". The axiom schema that is used explicitly in the book is the "axiom schema of separation" due to Ernst Zermelo, which he formulated in order to make precise the notion of a statement as being "definite". More of the set-theoretic paradoxes are discussed, along with their classification due to F.P. Ramsey into "linguistic" and "semantical" ones.

The advantage of an older book on set theory is that more of the underlying details are explained, instead of just being formally developed. The author gives a thorough discussion of the concepts throughout the book, beginning with an organized development in chapter 2. He begins immediately with discussing the distinction between the object language and metalanguage, and the symbols to be used in the object language: constants, variables, logical connectives, quantifiers, and grouping symbols. These symbols are used to construct formulas, a subclass of which, the primitive formulas, are defined recursively, and which all formulas in the object language can be expressed in terms of. Throughout the book though the author uses additional notation that allows formulas not to be written in terms of primitive formulas. This is done to make the text more readable, but he requires that the added notion satisfy the criterion of eliminability and non-creativity. The notion of a set is defined formally, and then the axiom of extensionality, which gives a criterion for two sets being equal, and the axiom schema schema of separation. The pairing axiom, which gives the existence of a non-empty set; the sum axiom, which gives the existence of the union of a family of sets; the power set axiom, which gives the notion of the set of all subsets of a set; and the axiom of regularity, which prohibits infinite descending sequences of sets, are all discussed in detail.

Chapter 3 treats relations and functions, so important not only in mathematics but in computer science, especially in the theory of relational databases. Then in chapter 4, the author begins a study of cardinality and the cardinal numbers, proving that the finite cardinal numbers have the properties of the natural numbers, as one would expect. The author is careful to point out the need for the axiom of cardinal numbers in this study. Chapter 5 then goes into the theory of ordinal numbers, wherein it is emphasized that no special axioms are needed for the development of this theory. The author is also careful to note the special problems that arise in defining the arithmetic of natural numbers, such as defining addition recursively without using set theory. But including the apparatus of set theory does allow the replacement of the recursive definition by a proper definition. The axiom of infinity is brought in to permit the construction of arithmetical operations as certain sets. The theory of denumerable sets is then discussed, followed by one of the most fascinating concepts in all of mathematics: the theory of transfinite and infinite cardinals.

The author then shows that set theory can allow the construction of the real numbers, which takes place after the construction of the rational numbers.The famous "Dedekind cut" is discussed, along with the method of Cantor, which defines real numbers as equivalence classes of Cauchy sequences of rational numbers. The author uses the Cantor approach in the rest of the book. He also proves the famous Cantor theorem on the non-denumerability of the real numbers, and gives a brief discussion of the Continuum Hypothesis.

Chapter 8 then gives an overview of the fascinating topics of transfinite induction and ordinal number theory. Recursion theory makes its appearance again in the transfinite recursion for ordinal numbers, using the axiom schema of replacement. The non-commutativity of ordinal addition and multiplication is brought out, and the falsity of Fermat's Last Theorem and Goldbach's Hypothesis in ordinal number theory is shown. The author then shows to what extent cardinal number theory can be done without using special axioms by defining cardinal numbers as initial ordinals. The axiom of choice however is needed to show that every set has a cardinal number. The author then restates the Zermelo-Fraenkel axioms in their final form at the end of the chapter.

The final chapter gives an overview of the most controversial topic in all of set theory, if not in all of mathematics: the axiom of choice. The author shows that the use of this axiom allows one to prove that an infinite set has a denumerable subset, and he shows the equivalence of the axiom of choice with the numeration theorem, the well-ordering theorem, Zorn's lemma, and the law of trichotomy. The counterintuitive Banach-Tarski paradox is discussed, and the author shows the existence of axioms which imply the axiom of choice.

Reviews (4)

There are better introductory choices
I found this one disapointing.For example, they do a nice job very carefully and clearly distinguishing "decidable" and "acceptable" languages.Then they talk about languages Turing machines "recognize" without saying if these are acceptable or decidable or what.This kind of thing is frustrating.That said, I did learn things from this book.Many things are well covered.But if you buy one book, buy Sipser instead.

What a textbook shouldn't be
It's rather disappointing that many universities use this textbook in courses on the subject matter.While it does cover some inseresting and important things, in general the book is terribly written.The back cover states that this text assumes no prerequisites - nothing could be further from the truth.The first chapter purports to provides all prerequisites needed, but it is poorly done and insufficient.Both the first chapter and all subsequent chapters make use of mathematical and computational symbols and terminology that are not explained.Even if you're generally familiar with them, you'll still have to look up the exact definitions in another book.Most of the text in the book is written in a terribly confusing manner that requires it to be re-read multiple times.The proofs are the same way (I have seen some of these proofs written in a very clear manner elsewhere).The authors even omit some proofs because they're "obvious" (although I have been confronted with having to come up with these proofs on graduate-level exams).Possibly the most frustrating thing about this book is the fact that frequently (usually when introducting a new topic) it will give a tiny bit of background and then throw out a few homework problems.Instead of explaining what's going on, the authors decide to let these homework problems take the place of a few pages of definitions, explanations, and examples (note that there are no solutions to the hw problems in the book).Not only will you struggle with the rest of the material if you can't get those problems, but it makes it nearly impossible to merely read the book.

Isbn: 3540674195
Sales Rank: 518741
Subjects:  1. Algorithms (Computer Programming)    2. Computational complexity    3. Computer Bks - General Information    4. Computer Books: General    5. Computer Science    6. Computers    7. General    8. Programming - General    9. System Theory    10. Theory Of Computing    11. Algorithms    12. Complexity Theory    13. Computers / Computer Science    14. Foundations    15. Theoretical Computer Science    16. Theory of Computation   

Editorial Review

Reviews (1)

Nice coverage of Wolframs published work
This is a nice collection of wolframs work on cellular automata (whichfirst appeared as a number of papers in various physics journals).It is anice coverage of cellular automata, but it would have been nice to givemore credit to von Neuman for his pioneering work in cellular automatatheory.

There is also an annoying habit for all of his work toconcentrate on deterministic cellular automata, and the mathematics isconstrained to this.Recent work has indicated that the origin ofcomplexity in our universe is from random sources that are preserved.. notthat the complexity all came from the initial conditions.

It isespecially interesting to note in his book how the different rules ofcellular automata play out to create varying degrees of complexity.Ittakes a very specific rule set indeed to allow for interesting complexbehaviors to show up, as evinced by the long search Conway undertook todiscover "life".