[ Pobierz całość w formacie PDF ]
make them easier to formalize.
1. Look up associativity if you need to.
2. There is an object such that every object is not in it.
3. This should be easy.
4. Ditto.
5. Any two things must be the same thing.
5.9. If necessary, don t hesitate to look up the definitions of the
given structures.
1. Read the discussion at the beginning of the chapter.
2. You really need only one non-logical symbol.
3. There are two sorts of objects in a vector space, the vectors
themselves and the scalars of the field, which you need to be
able to tell apart.
5.10. Use Definition 5.3 in the same way that Definition 1.2 was
used in Definition 1.3.
5.11. The scope of a quantifier ought to be a certain subformula of
the formula in which the quantifier occurs.
67
68 5. HINTS
5.12. Check to see whether they satisfy Definition 5.4.
5.13. Check to see which pairs satisfy Definition 5.5.
5.14. Proceed by induction on the length of Õ using Definition 5.3.
5.15. This is similar to Theorem 1.12.
5.16. This is similar to Theorem 1.12 and uses Theorem 5.15.
CHAPTER 6
Hints
6.1. In each case, apply Definition 6.1.
1. This should be easy.
2. Ditto.
3. Invent objects which are completely different except that they
happen to have the right number of the right kind of components.
6.2. Figure out the relevant values of s(vn) and apply Definition
6.3.
6.3. Suppose s and r both extend the assignment s. Show that
s(t) =r(t) by induction on the length of the term t.
6.4. Unwind the formulas using Definition 6.4 to get informal state-
ments whose truth you can determine.
6.5. Unwind the abbreviation " and use Definition 6.4.
6.6. Unwind each of the formulas using Definitions 6.4 and 6.5 to
get informal statements whose truth you can determine.
6.7. This is much like Proposition 6.3.
6.8. Proceed by induction on the length of the formula using Defi-
nition 6.4 and Lemma 6.7.
6.9. How many free variables does a sentence have?
6.10. Use Definition 6.4.
6.12. Unwind the sentences in question using Definition 6.4.
6.11. Use Definitions 6.4 and 6.5; the proof is similar in form to
the proof of Proposition 2.9.
6.14. Use Definitions 6.4 and 6.5; the proof is similar in form to
the proof for Problem 2.10.
6.15. Use Definitions 6.4 and 6.5 in each case, plus the meanings
of our abbreviations.
69
70 6. HINTS
6.17. In one direction, you need to add appropriate objects to a
structure; in the other, delete them. In both cases, you still have to
verify that “ is still satisfied.
6.18. Here are some appropriate languages.
1. L=
2. Modify your language for graph theory from Problem 5.9 by
adding a 1-place relation symbol.
3. Use your language for group theory from Problem 5.9.
4. LF
CHAPTER 7
Hints
7.1. 1. Use Definition 7.1.
2. Ditto.
3. Ditto.
4. Proceed by induction on the length of the formula Õ.
7.2. Use the definitions and facts about |= from Chapter 6.
7.3. Check each case against the schema in Definition 7.4. Don t
forget that any generalization of a logical axiom is also a logical axiom.
7.4. You need to show that any instance of the schemas A1 A8 is
a tautology and then apply Lemma 7.2. That each instance of schemas
A1 A3 is a tautology follows from Proposition 6.15. For A4 A8 you ll
have to use the definitions and facts about |= from Chapter 6.
7.5. You may wish to appeal to the deductions that you made or
were given in Chapter 3.
1. Try using A4 and A6.
2. You don t need A4 A8 here.
3. Try using A4 and A8.
4. A8 is the key; you may need it more than once.
5. This is just A6 in disguise.
7.6. This is just like its counterpart for propositional logic.
7.7. Ditto.
7.8. Ditto.
7.9. Ditto.
7.10. Ditto.
7.11. Proceed by induction on the length of the shortest proof of
Õ from “.
7.12. Ditto.
7.13. As usual, don t take the following suggestions as gospel.
1. Try using A8.
71
72 7. HINTS
2. Start with Example 7.1.
3. Start with part of Problem 7.5.
CHAPTER 8
Hints
8.1. This is similar to the proof of the Soundness Theorem for
propositional logic, using Proposition 6.10 in place of Proposition 3.2.
8.2. This is similar to its counterpart for prpositional logic, Propo-
sition 4.2. Use Proposition 6.10 instead of Proposition 3.2.
8.3. This is just like its counterpart for propositional logic.
8.4. Ditto.
8.5. Ditto.
8.6. This is a counterpart to Problem 4.6; use Proposition 8.2 in-
stead of Proposition 4.2 and Proposition 6.15 instead of Proposition
2.4.
8.7. This is just like its counterpart for propositional logic.
8.8. Ditto
8.9. Ditto.
8.10. This is much like its counterpart for propositional logic, The-
orem 4.10.
8.11. Use Proposition 7.8.
8.12. Use the Generalization Theorem for the hard direction.
8.13. This is essentially a souped-up version of Theorem 8.10. To
ensure that C is a set of witnesses of the maximally consistent set of
sentences, enumerate all the formulas Õ of L with one free variable
and take care of one at each step in the inductive construction.
8.14. To construct the required structure, M, proceed as follows.
Define an equivalence relation
c = d " £, and let [c] ={ a " C | a
[ Pobierz całość w formacie PDF ]