Simply Gödel

The World of Logic

Gödel’s studies in the late 1920s led him deeper into the world of mathematical logic. A few preliminaries are needed to understand his work in logic and mathematics, including some facts about axiom systems, formalization, formal proof, and the notion of logical truth. These are involved in most of Gödel’s work, even to some extent in his later formal “proof” for the existence of God. Although this chapter discusses his completeness theorem, it will not include its mathematical proof. Gödel makes some very interesting claims about how a certain philosophical viewpoint led him to his completeness proof at a time when opposing philosophical viewpoints were preventing other very good logicians from seeing it. He wrote that having the right philosophical outlook—a type of Platonic rationalism or “objectivism”—was an important heuristic in developing his technical work.

Axiom Systems

First, we should consider some key ideas about axiom systems in mathematics and logic. The axiomatic method has been with us for a long time. More than 2,000 years ago, Euclid applied it to the geometry of his day. Since then, axiomatization has been viewed as an ideal way to systematically organize and unify mathematics and logic. Euclid’s work has been celebrated, not only in these two fields, but also as an inspiration in literature and poetry, as in Edna St. Vincent Millay’s poem, “Euclid alone has looked on beauty bare.”

To prove his theorems, Euclid’s geometry employed undefined terms, definitions, axioms, rules of inference, and diagrammatic constructions. Beyond geometry, of course, many different areas of mathematics and logic can be axiomatized. The idea, traditionally, has been to start with a specific area or domain such as geometry, the theory of natural numbers, the theory of real numbers, or the theory of sets. Then one lays out as “given” a small number of basic truths that characterize the domain. These are the axioms. Some of the terms used might be primitive, in the sense that no attempt is made to define them. They are taken as intuitively understood. Other terms might then be defined from those primitive expressions. From the small kernel of truths about the domain that the axioms express, the idea is to derive, using valid principles of reasoning, the domain’s other truths. The principles of reasoning applied to prove the other truths are the axiom system’s primitive rules of inference. The sentences or truths obtained are called the system’s theorems. This approach also requires a few basic rules of inference. Little will be gained from an axiom system that contains a large and unwieldy set of axioms and rules of inference. Theorems are derived or proved from the axioms using only the rules of inference. One cannot step outside the rules and start using any old pattern of reasoning. Ideally, then, a derivation or proof will show the step-by-step process of obtaining a theorem from the axioms. Once a theorem has been proved, it can be used in proofs of further theorems. Also, as various patterns of reasoning emerge in unfolding the axioms, it is common to formulate new rules of inference derived from the process.

Formal Logic

Logic has a long history in Western philosophy, going back to the ancient Greek philosopher Aristotle, who lived from 384 to 322 B.C.E. Aristotle’s work on logic held sway for centuries without significant modifications or extensions. Though logic really started to blossom in the 19th century, one earlier figure is especially important to Gödel’s study of logic: this is Gottfried Wilhelm Leibniz, who lived from 1646 to 1716. Leibniz is famous not only as a philosopher. He also, along with Isaac Newton, was one of the inventors of calculus. He had a grand vision for the future of logic. Leibniz wanted to create what he called a “universal characteristic” and a “calculus ratiocinator.” By that, he meant an exact universal language, modeled on mathematics, that would express and solve any kinds of problems about which we could reason.

Leibniz himself did not make much headway in actually carrying out this project. It would fall to others to create the universal characteristic and the calculus ratiocinator. The great logician Gottlob Frege (1848-1925), deserves most of the credit for bringing at least part of Leibniz’s dream to fruition. Frege devised what he called a “concept notation.” His plan was to use it in a formal, axiomatic system of logic from which he hoped to derive significant portions of mathematics, starting with arithmetic. He sought to be very rigorous about how axiom systems would work, insisting that proofs contain no gaps, that they not require the use of pictures, diagrams, or intuition as Euclid had, and that all the rules of inference would be laid out in advance so as to circumscribe the reasoning process. This approach would make proofs secure. It would also ensure clarity and avoid the possibility of errors in reasoning. Since Frege thought most of mathematics, except for geometry, could be derived from logical principles alone, his position in the foundations of mathematics is referred to as “logicism.” His conception of logic’s scope, however, included much more than what today would be regarded as basic logic. Although Frege made tremendous advances, his system of axioms for mathematics has some problems, as we will see below.

Frege’s innovations in logical theory were unparalleled. Ironically, however, his own specific notation system was cumbersome and never enjoyed any popularity. His near-contemporary, the mathematician Giuseppe Peano (1858-1932), found a better notation for expressing Frege’s innovations in pure formal logic. Without the language of modern logic, it is difficult to understand anything in the field. I will present a few simple examples of some standard formulas and arguments in what is called “predicate logic” or “quantificational logic.” This is the logic for which Gödel proved his completeness theorem.

The language of mathematical logic is an artificial language. It is possible to symbolize English sentences or sentences from other natural languages in the language of formal logic. The resulting symbolizations will contain no expressions at all from natural language. The language of logic picks out the form or structure of our thinking and expression, leaving behind the original content. Nowadays this is comparable to how problems are represented in programming languages, which are also artificial. At the time of Frege and other pioneers in mathematical logic, programming languages did not yet exist, of course. In fact, these early logicians were the ones who laid the foundations for what we now think of as computer science. There are even “descriptive,” as distinct from “imperative,” programming languages that are based directly on the language of predicate logic. Frege’s idea was that the language of logic was to be universal, in the sense that it would pick out the underlying logical structure of expression and thinking, whether in English, Spanish, German, Hindi, Chinese, or other natural languages. Thus, using the language of logic, it is like writing programs in in C++ or learning and solving problems in calculus. C++ or calculus is the same worldwide, but users of these artificial languages will start from their own natural languages.

Predicate Logic

Learning predicate logic is like learning a new language. We have to get acquainted with the alphabet, the grammar—also called syntax—and the meanings of its expressions. A basic distinction is drawn in modern logic between syntax and semantics. Syntax concerns the forms of the strings of signs that make up the sentences of logic. Those forms are independent of their meanings, or of the sentences’ truth or falsity. Semantics, on the other hand, is concerned with precisely these meanings or truth values. In basic logic, semantics addresses the sentences’ truth conditions. In Frege’s system, the semantics remained informal and not precisely specified. Formal semantics, with its exact definition of truth, did not come into its own until 1935, thanks to the work of Alfred Tarski (1901-1983). Some important semantic concepts will be explored in the section on logical truth in the next chapter.

Consider an expression such as, “If mathematics is fun then mathematics is interesting.” Logically speaking, this is a “conditional” sentence. It asserts the idea that mathematics is fun as a condition for its being interesting. In the language of the logic for which Gödel proved his completeness theorem, we can represent the logical “if . . . then . . . .” function by the symbol “→.” We can choose an upper-case Roman letter to stand for the declarative sentence that follows the sentence’s “if” part and another upper-case Roman letter to stand for the different sentence that follows the “then” part. For example:

So the symbolization of the English sentence will be “F → I.” Note that it would be incorrect to symbolize the sentence as “I → F,” because this reverses the dependence relation. Symbolizing sentences in the language of logic is like coding information in a programming language. All the natural language will disappear in favor of the artificial language, just as Leibniz and Frege had wished. We can symbolize declarative sentences in this way whether they are true or false, or even if we do not know...