Logic Text Chapter 9 Solutions

Chapter 9: Models for Predicate Logic

Basic

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}

(∀ 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}

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}

(∀ 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}

(∀ 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}

(∃ 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}

(∀ 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}

(∃ 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

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:

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:

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

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.