Vanessa Stanfill and Dr. Dennis Packard, Philosophy

In the 1930s, a 24-year-old mathematician named Kurt Gödel developed a theorem showing that certain mathematical and logical systems, those capable of defining numbers, arithmetic, and multiplication, must be incomplete. These systems are incomplete, he showed, because they can generate certain true, but unprovable, statements. Gödel’s theorem has since become a common concept taught in advanced undergraduate logic courses. Undergraduate philosophy students attempting to understand incompleteness are usually well-grounded in basic Aristotelian and first-order predicate logic, as well as set theory. When they try to tackle Gödel’s proof, however, they are thrown into a dizzyingly unfamiliar new world of notation and number coding. The purpose of this project was to develop a new method of proving incompleteness in finite set theory, a language that is familiar to students who have completed an average intermediate logic course. By leading students through the incompleteness theorem using finite set theory as both the object language and metalanguage, this method helps students more quickly and thoroughly grasp the concept of incompleteness.

The kinds of paradoxical statements that give us incompleteness are somewhat analogous to paradoxes found in informal English. One such analogy is the ancient “Liar’s Paradox,” which presents us with the contradictory statement, “This sentence is not true.” The sentence eludes our ability to determine its truth or falsity. Along the same lines, this project’s purpose was to show that finite set theory can generate statements that state of themselves, “This sentence is not provable.” If that statement were false, then finite set theory would prove a false statement, which cannot be. So, the statement must be true, and hence, unprovable. Once we have shown that finite set theory is incomplete, we can show that any language that is consistent, meaning one that doesn’t lead to contradictions, and can define its axioms in finite set theory must be capable of generating such unprovable statements.

Showing incompleteness in finite set theory is, so far as our research has shown, an entirely new approach among metalogic courses. Finite set theory is much like the familiar infinite set theory, but excludes the use of infinite objects or sets. Proving incompleteness in finite set theory is easier than in number theory for the philosophy student, because it uses familiar logic operations instead of arithmetic and multiplication. Also, when we prove incompleteness in finite set theory our final conclusion, showing that any language that can define its axioms in finite set theory must be incomplete, is made more significant by the elimination of infinite sets.

Developing this course required, first, developing a method for defining finite set theory. Students with some intermediate logic background are generally familiar with defining and proving basic theorems about the numbers in infinite set theory. Our system begins by reviewing this concept, but this time in finite set theory. Instead of using the familiar descendent set, or successor set, to define the numbers, we use a new concept, the “ancestor set.” A descendant set for numbers is an infinite collection of the number n and all of its descendants, or succeeding numbers. An ancestor set for numbers, by contrast, is a finite collection of n and all of its ancestors, or preceding numbers, back to zero. Using ancestor sets, we can define “x is a number,” in a finite way. Following the pattern set by the numbers, we can then define the terms and formulas, the basic components of finite set theory. We focus on definitions early in the course to make sure the student fully understands that both our object language and our metalanguage will be finite set theory, and thus must always exclude infinite objects or sets.

The next step towards out goal was defining provability within finite set theory. Defining provability in a finite way required an entirely original look at provability and proofs. A formula is provable when a proof can be constructed that has that formula as its final line, we realized, and such a proof must always be finite because it has a set of assumptions and a final conclusion. Provability, then, can be defined as any formula that is the final step in a proof.

Unfortunately, defining provability requires us to accommodate for the instantiation and generalization of formulas. To allow for this, we had to define a method of “replacement” that allows us to take any quantified formula and replace its free variables with a term. Defining replacement requires the use of recursive definitions, definitions that define a complex entity in terms of its parts, and each of those parts in terms of its own parts. Recursive definitions, unfortunately, are problematic and using them in our definition of replacement required an elaborate set of proofs justifying our use of recursion. During the difficult process of justifying recursion, we discovered that our system had to be “freely generated,” or well-ordered, if the recursion proofs were to work. Proving free generation over the formulas is an inelegant, but essential, step towards showing our final goal.

Having defined finite set theory and shown that we can define a provability predicate within the theory, we turned to proving incompleteness. First, we proved a generalized theorem showing the two necessary criteria that any consistent set of assumptions must meet in order to be shown incomplete. Our final step was to show that finite set theory itself met those criteria. First, we had to show that if something is proven from finite set theory, then that thing itself must be provable. This follows given that we have already used finite set theory as a metalanguage to define provability in finite set theory as an object language. Second, we had to show that self-referential statements, such as “This sentence is unprovable” can be constructed in the theory. Constructing such a sentence is possible thanks to our definition of replacement. Having shown these two criteria, we can then conclude that finite set theory must be incomplete, and further that any consistent set of formulas that meets the two criteria must also be incomplete.

The final step in this project was teaching a class using the theorems and proofs we had developed in Prof. Dennis Packard’s Fall 2005 Metalogic Phil 405 class. Teaching the class gave us an opportunity to both carefully re-examine our own work and share it with advanced logic students within the department. The refined results of our work proved to be very useful in helping students comprehend a difficult concept in an original and singularly unique way.