by Brian Bosse, Copyright March 29, 2008, all rights reserved. 45 views
This series is simply to help me clarify my thinking and understanding of Gödel's Theorems. To begin, I am going to consider a very simple formal system found in David Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid. What is a formal system? In the context of Gödel's Theorem (GT), a formal system can be thought of as a game made up of rules on how to manipulate symbols. We begin with the pq-system.
The Language
All formal systems have a language. A key component about a formal language is that the language does not need to mean anything. Initially, we are not going to worry at all about meaning, but we will mainly concern ourselves with how the language is developed, i.e., the symbols are manipulated. There will be only three symbols that make up the pq-system: '-', 'p' and 'q'. Any combination of these symbols represents a formula of the system. For example, '- - -p' and 'qpqpq' and '-' all represent formulas in our formal system. However, not all formulas are well-formed. For instance, 'lkqw' is a series of letters in the English alphabet, but it is not considered an actual word according to the rules of the language - there is no vowel. In other words, 'lkqw' is not well-formed. As such, for our formal language we need to define what is a well-formed formula.
Definition: A formula is well-formed in the pq-system if and ony if it begins with at least one '-' followed by one and only one 'p' followed by at least one '-' followed by one and only one 'q' followed by at least one '-'.
Another way to say this is that all well-formed formulas look like xpyqz when 'x' 'y' and 'z' stand for some number of hyphens. Here is a list of well-formed formulas: '-p-q-' and '- - -p-q-' and '-p- - - -q- -'. On the other hand, '- - -p' and 'qpqpq' and '-' are all formulas, but they are not well-formed. Be very careful here. 'x' 'y' and 'z' are not part of the pq-system. They are just place holders that we use for our convenience. In other words, they assist us in talking about the pq-system, but they are not part of the pq-system itself.
Axioms
At this point, we need to further define our language by listing the starting point(s). That is to say, we are going to decide which well-formed formulas are going to be part of our system. We call this starting point (or staring points) the axioms of the system.
Definition: A formula is an axiom of the pq-system if and only if it has the form xp-qx- whenever 'x' is composed of a number of hyphens.
As such, we have allowed ourselves an infinite number of axioms. The following are all axioms of the pq-system: '-p-q- -' and '- -p-q- - -' and '- - - - -p-q- - - - - -'. None of the well-formed formulas above are axioms. Again, note that the 'x' in the above definition is not part of the pq-system. The only symbols in the pq-system are '-', 'p' and 'q'.
Rule of Production
We now need to add to our language a way to take an axiom and create another well-formed formula in our system. These formulas created from the axioms are called theorems of the system.
Rule: Given that 'x' 'y' and 'z' each stand for some number of hyphens, and given that xpyqz is either an axiom of the system or a theorem of the system, then xpy-qz- is a theorem of the system.
For example, '-p-q- -' is an axiom of the system. Let 'x' stand for '-', 'y' stand for '-' and 'z' stand for '- -'. According to our rule of production, then '-p- -q- - -' is a theorem of our system. This concludes our formal system.
As an exercise, which of the following are theorems or axioms of the pq-system?
1. - - - - -p-q- - - - - -
2. -xpy- -qz- - -
3. - - -p- - -q- - - - - -
4. - -p- - - -q- - - - -
For those examples above that are theorems of the system explain how the theorem was derived.
-----No comments yet.