<<

. 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

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.
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 .)



>>