ńņš. 9 |

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 |