<< Ļšåäūäółą’ ńņš. 9(čē 11 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>

63
64 3. HINTS
CHAPTER 4

Hints

4.1. Use induction on the length of the deduction and Proposition
3.2.
4.2. Assume, by way of contradiction, that the given set of formulas
is inconsistent. Use the Soundness Theorem to show that it canā™t be
satisļ¬able.
4.3. First show that {Ā¬(Ī± ā’ Ī±)} Ļ.
4.4. Note that deductions are ļ¬nite sequences of formulas.
4.5. Use Proposition 4.4.
4.6. Use Proposition 4.2, the deļ¬nition of Ī£, and Proposition 2.4.
4.7. Assume, by way of contradiction, that Ļ• ā Ī£. Use Deļ¬nition
/
4.2 and the Deduction Theorem to show that Ī£ must be inconsistent.
4.8. Use Deļ¬nition 4.2 and Problem 3.9.
4.9. Use Deļ¬nition 4.2 and Proposition 4.8.
4.10. Use Proposition 1.7 and induction on a list of all the formulas
of LP .
4.11. One direction is just Proposition 4.2. For the other, expand
the set of formulas in question to a maximally consistent set of formulas
Ī£ using Theorem 4.10, and deļ¬ne a truth assignment v by setting
v(An) = T if and only if An ā Ī£. Now use induction on the length of
Ļ• to show that Ļ• ā Ī£ if and only if v satisļ¬es Ļ•.
4.12. Prove the contrapositive using Theorem 4.11.
4.13. Put Corollary 4.5 together with Theorem 4.11.

65
66 4. HINTS
CHAPTER 5

Hints

5.1. Try to disassemble each string using Deļ¬nition 5.2. Note that
some might be valid terms of more than one of the given languages.
5.2. This is similar to Problem 1.5.
5.3. This is similar to Proposition 1.7.
5.4. Try to disassemble each string using Deļ¬nitions 5.2 and 5.3.
Note that some might be valid formulas of more than one of the given
languages.
5.5. This is just like Problem 1.2.
5.6. This is similar to Problem 1.5. You may wish to use your
solution to Problem 5.2.
5.7. This is similar to Proposition 1.7.
5.8. You might want to rephrase some of the given statements to
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 deļ¬nitions 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 ļ¬eld, which you need to be
able to tell apart.
5.10. Use Deļ¬nition 5.3 in the same way that Deļ¬nition 1.2 was
used in Deļ¬nition 1.3.
5.11. The scope of a quantiļ¬er ought to be a certain subformula of
the formula in which the quantiļ¬er occurs.
67
68 5. HINTS

5.12. Check to see whether they satisfy Deļ¬nition 5.4.
5.13. Check to see which pairs satisfy Deļ¬nition 5.5.
5.14. Proceed by induction on the length of Ļ• using Deļ¬nition 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 Deļ¬nition 6.1.
1. This should be easy.
2. Ditto.
3. Invent objects which are completely diļ¬erent 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 Deļ¬nition
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 Deļ¬nition 6.4 to get informal state-
ments whose truth you can determine.
6.5. Unwind the abbreviation ā and use Deļ¬nition 6.4.
6.6. Unwind each of the formulas using Deļ¬nitions 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 Deļ¬-
nition 6.4 and Lemma 6.7.
6.9. How many free variables does a sentence have?
6.10. Use Deļ¬nition 6.4.
6.12. Unwind the sentences in question using Deļ¬nition 6.4.
6.11. Use Deļ¬nitions 6.4 and 6.5; the proof is similar in form to
the proof of Proposition 2.9.
6.14. Use Deļ¬nitions 6.4 and 6.5; the proof is similar in form to
the proof for Problem 2.10.
6.15. Use Deļ¬nitions 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 satisļ¬ed.
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

1. Use Deļ¬nition 7.1.
7.1.
2. Ditto.
3. Ditto.
4. Proceed by induction on the length of the formula Ļ•.
7.2. Use the deļ¬nitions and facts about |= from Chapter 6.
7.3. Check each case against the schema in Deļ¬nition 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 deļ¬nitions 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

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.
Deļ¬ne an equivalence relation ā¼ on C by setting c ā¼ d if and only if
c = d ā Ī£, and let [c] = { a ā C | a ā¼ c } be the equivalence class of
c ā C. The universe of M will be M = { [c] | c ā C }. For each k-place
function symbol f deļ¬ne f M by setting f M ([a1], . . . , [ak ]) = [b] if and
only if fa1 . . . ak = b is in Ī£. Deļ¬ne the interpretations of constant
73
74 8. HINTS

symbols and relation symbols in a similar way. You need to show that
all these things are well-deļ¬ned, and then show that M |= Ī£.
8.15. Expand Ī“ to a maximally consistent set of sentences with a
set of witnesses in a suitable extension of L, apply Theorem 8.14, and
then cut down the resulting structure to one for L.
8.16. One direction is just Proposition 8.2. For the other, use
Corollary 8.15.
8.17. This follows from Theorem 8.16 in the same way that the
Completeness Theorem for propositional logic followed from Theorem
4.11.
8.18. This follows from Theorem 8.16 in the same way that the
Compactness Theorem for propositional logic followed from Theorem
4.11.
CHAPTER 9

Hints

9.1. In each case, apply the trick used in Example 9.1. For deļ¬-
nitions and the concrete examples, consult texts on combinatorics and
abstract algebra.
9.2. Suppose Ramseyā™s Theorem fails for some n. Use the Com-
pactness Theorem to get a contradiction to Lemma 9.3 by showing
there must be an infnite graph with no clique or independent set of
size n.
9.3. Inductively deļ¬ne a sequence a0, a1 , . . . , of vertices so that for
every n, either it is the case that for all k ā„ n there is an edge joining
an to ak or it is the case that for all k ā„ n there is no edge joining an
to ak . There will then be a subsequence of the sequence which is an
inļ¬nite clique or a subsequence which is an inļ¬nite independent set.
9.4. The key is to ļ¬gure out how, given an assignment for one
structure, one should deļ¬ne the corresponding assignment in the other
structure. After that, proceed by induction using the deļ¬nition of
satisfaction.
9.5. When are two ļ¬nite structures for L= elementarily equivalent?
9.6. In a suitable expanded language, consider Th(N) together with
the sentences āx 0 + x = c, āx S0 + x = c, āx SS0 + x = c, . . .
9.7. Suppose M |= Th(N) but is not isomorphic to N.
1. Consider the subset of |M| given by 0M , S M (0M ), S M (S M (0M )),
...
2. If it didnā™t have one, it would be a copy of N.
3. Start with a inļ¬nite number and work down.
9.8. Expand LF by throwing in a constant symbol for every real
number, plus an extra one, and take it from there.

75
76 9. HINTS
Appendices
APPENDIX A

A Little Set Theory

This apppendix is meant to provide an informal summary of the
notation, deļ¬nitions, and facts about sets needed in Chapters 1ā“9. For
a proper introduction to elementary set theory, try [5] or [6].
Definition A.1. Suppose X and Y are sets. Then
1. a ā X means that a is an element of (i.e. a thing in) the set X.
2. X is a subset of Y , written as X ā Y , if a ā Y for every a ā X.
3. The union of X and Y is X āŖ Y = { a | a ā X or a ā Y }.
4. The intersection of X and Y is X ā©Y = { a | a ā X and a ā Y }.
5. The complement of Y relative to X is X \ Y = { a | a ā
X and a ā Y }.
/
6. The cross product of X and Y is X Ć—Y = { (a, b) | a ā X and b ā
Y }.
7. The power set of X is P(X) = { Z | Z ā X }.
8. [X]k = { Z | Z ā X and |Z| = k } is the set of subsets of X of
 << Ļšåäūäółą’ ńņš. 9(čē 11 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>