« Section 3.3: Problem 2 Solution

Section 3.3: Problem 4 Solution »

Section 3.3: Problem 3 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
A theory (in a language with and ) is called -complete iff for any formula and variable , if belongs to for every natural number , then belongs to . Show that if is a consistent -complete theory in the language of and if , then .
Let be a sentence (in the language of ) in the prenex normal form (Section 2.6). We use induction on the number of quantifiers in to show that iff is true in . We already know by the preceding exercise that for every quantifier-free sentence , if is true in , then , hence, , and if is false in , then , hence, . If is true in , where is the only free variable in , then for all , , and, by hypothesis, , but then, since is -complete, . If is true in , then for some , , and, by hypothesis, , but then . Now, if or is false in , then (which is logically equivalent to or , respectively) is true in , and, hence, . Therefore, by induction, we conclude that ( ) iff is true in ( ) (here, we use the fact the is consistent).
Note. is not -complete. For example, if , then for every , however, , which is axiom S3 of .