*Question {9.1}*

1. True. (Each instance is true.)

2. True. (Each instance is true.)

3. False. It has a false instance, *b* for *x* and *a* for *y*, *Tba* ⊃ (*Tab* & ~ *Fb*)) is false.

4. True. It has a true instance (∀ *y*)((*Tby* & *Fy*) ⊃ (*Gb* & *Tby*))

5. False. It has a false instance (*a* for *x* and *b* for *y*) (∃ *z*)(*Taz* & *Tab*) ⊃ (∃ *z*)(*Tbz* & *Tza*)

The antecedent is true as it has a true instance (*b* for *z*). The consequent is false as it has no true instance.

*Question {9.2}*

Formulas 3, 4, 5, 6, 8, 9 and 10 are true. The rest are false.

*Question {9.3}*

2, 3, 4, 6, 7, 8 and 10 are tautologies. They are true in every two-element model (and in *every* model, in fact!)

Number 1 is false in this model:

*D* = {a,b}

I(F) | I(G) | |

a | 1 | 0 |

b | 1 | 1 |

(∀ *x*)(*Fx* ⊃ *Gx*) ∨ (∀ *x*)(*Fx* ⊃ ~ *Gx*) is false, as (∀ *x*)(*Fx* ⊃ *Gx*) is false (it has a false instance: *Fa* ⊃ *Ga*) and (∀ *x*)(*Fx* ⊃ ~ *Gx*) is false (it has a false instance: *Fa* ⊃ ~ *Ga*)

The rest are false in this model:

*D* = {a,b}

I(F) | |

a | 0 |

b | 1 |

5: (∀ *x*)*Fx* ∨ (∀ *x*)~ *Fx* is false, as both (∀ *x*)*Fx* and (∀ *x*)~ *Fx* are false.

9: (∀ *x*)(*Fx* ⊃ (∀ *y*)*Fy*) is false, as it has a false instance *Fb* ⊃ (∀ *y*)*Fy*, as (∀ *y*)*Fy* is false, but *Fb* is true.

*Question {9.4}*

Arguments 3, 5, 6, 7 and 8 are valid. The rest are invalid.

1 has the following counterexample:

*D* = {a,b,c}

I(G) | I(H) | |

a | 1 | 1 |

b | 0 | 1 |

c | 0 | 0 |

(∀ *x*)(*Gx* ⊃ *Hx*) is true as every instance is true. (∀ *x*)(~ *Gx* ⊃ ~ *Hx*) is false as the instance ~ *Gb* ⊃ ~ *Hb* is false.

2 has the following counterexample:

*D* = {a,b,c}

I(G) | I(H) | |

a | 1 | 1 |

b | 1 | 0 |

c | 0 | 0 |

(∀ *x*)*Gx* ⊃ (∀ *x*)*Hx* is true, as (∀ *x*)*Gx* and (∀ *x*)*Hx* are both false. However, (∀ *x*)(*Gx* ⊃ *Hx*) is not true, as it has a false instance: *Gb* ⊃ *Hb*.

4 has the following counterexample:

*D* = {a,b,c}

I(G) | I(H) | |

a | 1 | 1 |

b | 1 | 1 |

c | 1 | 1 |

(∃ *x*)(*Gx* ≡ *Hx*) is true, it has a true instance with *a* for *x*. But ~(∀ *x*)(*Gx* ⊃ *Hx*) is false, as (∀ *x*)(*Gx* ⊃ *Hx*) is true.

9 has the following counterexample:

*D* = {a,b,c}

I(G) | I(H) | |

a | 0 | 0 |

b | 0 | 0 |

c | 0 | 0 |

(∀ *x*)(*Gx* ⊃ ~ *Hx*) is true, as every instance is true. (Every instance of *Gx* is false, so the conditional is always true!). However, no instance of (∃ *x*)(*Gx* & ~ *Hx*) is true (for the same reason: *Gx* is never true).

10 has the following counterexample:

*D* = {a,b,c}

I(G) | I(H) | |

a | 1 | 0 |

b | 0 | 0 |

c | 0 | 0 |

(∃ *x*)(*Gx* & ~ *Hx*) is now true. However ~(∀ *x*)(*Gx* ⊃ ~ *Hx*) is false, as (∀ *x*)(*Gx* ⊃ ~ *Hx*) is true.

*Question {9.5}*

Each of the three names can pick out any of the four objects. So for each name you have four choices. The result is 4 x 4 x 4 = 16 x 4 = 64 different assignments of objects to names. In general, with *n* names and *m* objects, you gave *m* x *m* x … x *m* (*n* times) = *m* to the power of *n*.

*Question {9.6}*

Given a three place predicate in a domain of 2 objects, you have a 2 x 2 x 2 table (think of a cube) to fill with values of either 0 or 1. That is, you have 8 slots to fill in with either 0 or 1, and there are 2 to the power of 8, namely 256, different ways of doing this. In general, for an *n* place predicate in a domain of *m* objects, you have a staggering 2 to the power of (*m* to the power of *n*) ways of doing this. That’s a **lot** of different combinations!

*Question {9.7}*

This is a hard one.

*n*names can be done*k*^*n*times (I write ``*k*to the*n*’’ as ``*k*^*n*’’.)*m*monadic predicates can be done (2^*k*)^*m*times.*j*dyadic predicates can be done (2^(*k*^2))^*j*times.

This gives you *k*^*n* x (2^*k*)^*m* x (2^(*k*^2))^*j* different models all up. That’s a lot!

*Question {9.8}*

Here is a formula which is satisfied only in a model with an infinite domain

(∀ *x*)~ *Sxx* & (∀ *x*)(∀ *y*)(∀ *z*)((*Sxy* & *Syz*) ⊃ *Sxz*) & (∀ *x*)(∃ *y*)*Sxy*

Why? Well, first show that it has a model with an infinite domain. In particular, it has a model with the domain *D* = {0,1,2,3,4,…} of all the numbers. Interpret *S* like this: *Sxy* holds when *x* is smaller than *y*. So, it has a table like this

I(S) | 0 | 1 | 2 | 3 | 4 | … |

0 | 0 | 1 | 1 | 1 | 1 | … |

1 | 0 | 0 | 1 | 1 | 1 | … |

2 | 0 | 0 | 0 | 1 | 1 | … |

3 | 0 | 0 | 0 | 0 | 1 | … |

… | … | … | … | … | … | … |

And the formula is true in this interpretation, as (1) no number is smaller than itself (2) If one number is smaller than another, and that number is smaller than a third, then the first is smaller than the third. (3) For any number, there’s a bigger number.

So, the whole formula is true in this model with an infinite domain.

Now we’ll show that in any finite model, this whole formula is false. In particular, we’ll show that if the second and third conjuncts are true, then the first conjunct (∀ *x*)~ *Sxx* is false.

Suppose you’ve got a finite domain and you want to make (∀ *x*)(∃ *y*)*Sxy* true in it. This means that every object in the domain is “smaller than” some object in the domain. Now suppose that (∀ *x*)(∀ *y*)(∀ *z*)((*Sxy* & *Syz*) ⊃ *Sxz*) is true. This means that if *x* is “smaller than” *y* and *y* is “smaller than” *z* then *x* is “smaller than” *z*.

Now look at what happens if these hold in a finite domain. Start with one object. It must be “smaller than” some object. If it is “smaller than” itself, we’re done: we’ve made (∀ *x*)~ *Sxx* false. So, suppose it’s “smaller than” something else. So, we’ve got a picture like this:

a | —S→ | b |

Now b is “smaller than” some object too. If we have *Sba*, then since *Sab* and *Sba*, we must have *Saa*, which conflicts with (∀ *x*)~ *Sxx*. If we have *Sbb*, this is bad too, so we must have a new object c, such that *Sbc*. So, we’ve got a picture like this:

a | —S→ | b | —S→ | c |

Now we have *Sac* too (since *Sab* and *Sbc*) so the picture is actually like this:

a | —S→ | b | —S→ | c |

| | | | |||

— | -S- | → |

Now, there must be some object *y* where *Scy*: what could it be? If it were *a*, then we’d have *Sac* and *Sca*, and so, *Saa*, which is bad. If it were *b*, we’d have *Sbc* and *Scb*, which gives *Sbb*, which is bad. If it were *c*, we’d have *Scc*, which is bad too. So, we need a new object *d* where *Scd*.

This goes on forever. Every object requires a *new* object to be related to by *S*, because (∀ *x*)~ *Sxx* requires that we can’t have *S* “looping back” to anywhere it’s already been. So, our formula can only be true in an infinite domain. No finite list of objects will be enough.

So, we can answer our original question:

The formula

~[ (∀ *x*)~ *Sxx* & (∀ *x*)(∀ *y*)(∀ *z*)((*Sxy* & *Syz*) ⊃ *Sxz*) & (∀ *x*)(∃ *y*)*Sxy* ]

is true in every finite model, and it is false in some infinite models.