This junior/senior level text is devoted to a study of first-order logic and its role in the foundations of mathematics: What is a proof? How can a proof be justified? To what extent can a proof be made a purely mechanical procedure? How much faith can we have in a proof that is so complex that no one can follow it through in a lifetime? The first substantial answers to these questions have only been obtained in this century. The most (...) striking results are contained in Goedel's work: First, it is possible to give a simple set of rules that suffice to carry out all mathematical proofs; but, second, these rules are necessarily incomplete - it is impossible, for example, to prove all true statements of arithmetic. The book begins with an introduction to first-order logic, Goedel's theorem, and model theory. A second part covers extensions of first-order logic and limitations of the formal methods. The book covers several advanced topics, not commonly treated in introductory texts, such as Trachtenbrot's undecidability theorem. Fraissé's elementary equivalence, and Lindstroem's theorem on the maximality of first-order logic. (shrink)

Psychology has a long past, yet its real history is short. For thousands of years it has existed and has been growing older; but in the earlier part of this period it cannot boast of any continuous progress toward a riper and richer development. In the fourth century before our era that giant thinker, Aristotle, built it up into an edifice comparing very favorably with any other science of that time. But this edifice stood without undergoing any noteworthy changes or (...) extensions, well into the eighteenth or even the nineteenth century. Only in recent times do we find an advance, at first slow but later increasing in rapidity, in the development of psychology. The general causes which checked the progress of this science and thus made it fall behind the others can readily be stated:— "The boundaries of the Soul you cannot find, though you pace off all its streets, so deep a foundation has it," runs a sentence of Heraclitus, and it hits the truth more fully than its author could ever have expected. The structures and functions of our mental life present the greatest difficulties to scientific investigation, greater even than those presented by the phenomena, in many respects{4} similar, of the bodily life of the higher organisms. These structures and processes change so unceasingly, are so fleeting, so enormously complex, and dependent on so many factors hidden yet undoubtedly influential, that it is difficult even to seize upon them and describe their true substance, still more difficult to gain an insight into their causal connections and to understand their significance. We are just now beginning to recognize the full force of these difficulties. (shrink)

On October 4, 1937, Zermelo composed a small note entitled “Der Relativismus in der Mengenlehre und der sogenannte Skolemsche Satz” in which he gives a refutation of “Skolem's paradox”, i.e., the fact that Zermelo-Fraenkel set theory—guaranteeing the existence of uncountably many sets—has a countable model. Compared with what he wished to disprove, the argument fails. However, at a second glance, it strongly documents his view of mathematics as based on a world of objects that could only be grasped adequately by (...) infinitary means. So the refutation might serve as a final clue to his epistemological credo.Whereas the Skolem paradox was to raise a lot of concern in the twenties and the early thirties, it seemed to have been settled by the time Zermelo wrote his paper, namely in favour of Skolem's approach, thus also accepting the noncategoricity and incompleteness of the first-order axiom systems. So the paper might be considered a late-comer in a community of logicians and set theorists who mainly followed finitary conceptions, in particular emphasizing the role of first-order logic. However, Zermelo never shared this viewpoint: In his first letter to Gödel of September 21, 1931, he had written that the Skolem paradox rested on the erroneous assumption that every mathematically definable notion should be expressible by a finite combination of signs, whereas a reasonable metamathematics would only be possible after this “finitistic prejudice” would have been overcome, “a task I have made my particular duty”. (shrink)

Using hitherto unpublished manuscripts from the Zermelo Nachlass, I describe the development of the notion of definiteness and the discussion about it, giving a conclusive picture of Zermelo's thoughts up to the late thirties. As it turns out, Zermelo's considerations about definiteness are intimately related to his concept of a Cantorian universe of categorically definable sets that may be considered an inner model of set theory in an ideationally given universe of classes.

On October 4, 1937, Zermelo composed a small note entitled “Der Relativismus in der Mengenlehre und der sogenannte Skolemsche Satz”(“Relativism in Set Theory and the So-Called Theorem of Skolem”) in which he gives a refutation of “Skolem's paradox”, i.e., the fact that Zermelo-Fraenkel set theory—guaranteeing the existence of uncountably many sets—has a countable model. Compared with what he wished to disprove, the argument fails. However, at a second glance, it strongly documents his view of mathematics as based on a world (...) of objects that could only be grasped adequately by infinitary means. So the refutation might serve as a final clue to his epistemological credo.Whereas the Skolem paradox was to raise a lot of concern in the twenties and the early thirties, it seemed to have been settled by the time Zermelo wrote his paper, namely in favour of Skolem's approach, thus also accepting the noncategoricity and incompleteness of the first-order axiom systems. So the paper might be considered a late-comer in a community of logicians and set theorists who mainly followed finitary conceptions, in particular emphasizing the role of first-order logic (cf. [8]). However, Zermelo never shared this viewpoint: In his first letter to Gödel of September 21, 1931, (cf. [1]) he had written that the Skolem paradox rested on the erroneous assumption that every mathematically definable notion should be expressible by a finite combination of signs, whereas a reasonable metamathematics would only be possible after this “finitistic prejudice” would have been overcome, “a task I have made my particular duty”. (shrink)

The paper gives an introduction to the problem whether there is a logic ℒ that captures PTIME in the sense that, via some natural encoding, the classes of finite structures axiomatizable in ℒ correspond to the languages in PTIME. It discusses several notions of capturing, thereby giving a picture of the general theory. The question for the most important version is still open. The paper surveys positive answers for certain classes of graphs that are based on the method of canonization.

Towards the end of his 1930 paper on boundary numbers and domains of sets Zermelo briefly discusses the questions of consistency and of the existence of an unbounded sequence of strongly inaccessible cardinals, deferring a detailed discussion to a later paper which never appeared. In a report to the Emergency Community of German Science from December 1930 about investigations in progress he mentions that some of the intended extensions of these topics had been worked out and were nearly ready for (...) publication. Using manuscripts from his Nachlass, we exhibit essential features of these extensions. (shrink)