# Solutions to Assignment 7

• 9.3.16. UD:={1,2} Rxx:= {(1,1), (2,2), (1,2), (2,1)} It is obvious that the first sentence is satisfied in this model. Also, the second sentence is satisfied: whenever you have x and y such that Rxy is true (for example x=1, y=2), then you can find z different from x (in this example z=2) such that Ryz is true. You should verify this for all possible values of x and y.

• 9.4.1.(h) False. For example, let \alpha= A, \beta = ¬A.

• 9.4.1.(j) True. Prove first that {(Ax)Fx v (Ax)Gx} |- (Ax)( Fx v Gx ). Then, by the soundness theorem: {(Ax)Fx v (Ax)Gx} |= (Ax)( Fx v Gx ). To prove the first statement construct the derivation.

Premise       1  (Ax)Fx v (Ax)Gx

Assumption    2  | (Ax)Fx
3  | Fa
4  | Fa v Ga
5  | (Ax)( Fx v Gx )

Assumption    6  | (Ax)Gx
7  | Ga
8  | Fa v Ga
9  | (Ax)( Fx v Gx )

vE 1,2-5,6-9  10  (Ax)( Fx v Gx )


• 9.4.4.(d)

UD1 := {1,2}
Lxy := {(1,1),(1,2)}
This model satisfies the sentence.

UD2 := {1,2}
Lxy := {(1,2)}
This model does not satisfy the sentence.


• 9.5.1.(b)

UD := {1,2}
Fx := {1}
Gx := {1}
a := 1
b := 1

Note that to satisfy the last sentence you have to define Gy to be true only when y is b. The second sentence says: if Fx is true then Gx must be true. So, by the previous remark, Fx is true only when x is b. By the first sentence, Fa is true. Hence a=b.
• 9.5.6 (d)

 UD: = {0,1}
Lxy: = {(0,0)}
Gx : = {0}
a:=0
b:=1


It is easy to see that in the above structure, Lab and Ga are true. So it is the model for both Lab and (Lab -> Ga). However, since Gx:={0}, it is not a model of (Ax )Gx. So, the above structure satisfies all the premises but not the conclusion. Therefore, the argument is NOT valid.

• Consider the three sentences:

1. (Ax)[ Fx -> Gx ] ;
2. (Ax) Fx -> (Ax) Gx ;
3. (Ex)[ Fx -> Gx ] .
Consider the six possible arguments: {\alpha } |- \beta; where \alpha and \beta are distinct sentences from the list above.
For each such argument, if valid, give a derivation in PD+; if invalid, give a model that demonstrates this.

Solutions: In the solutions below, "(1)|-(2)" will temparily mean an argument with the sentence in (1) as the only premise and the setence in (2) as the conclusion. The same convention will apply to other arguments.

• (1)|-(2): Valid. Here is a derivation.

Premise  	1	(Ax)(Fx->Gx)
Assume		2  +----(Ax)Fx
AEa/x2		3  +     Fa
AEax1		4  +     Fa->Ga
->E3,4	        5  +     Ga
AIx/a 5         6  +----(Ax)Gx
->I2-3		7       (Ax)Fx -> (Ax)Gx


• (2)|-(1): invalid. Model:

UD:={a,b}
Fx:={a}
Gx:={b}


The above model obviously does not satisfy (Ax)Fx. Hence, it satisfies the sentence (Ax) Fx -> (Ax) Gx. However, when x is a, the model satisfies Fx but not Gx.
• (1)|-(3): Valid. This is just too obvious.

• (3)|-(1): Invalid. Model


UD:= {a,b}
Fx:={a}
Gx:={b}

In the above model, b shows that (Ex)(Fx -> Gx) is satisfied. while a shows that (Ax)(Fx->Gx) is not satisfied
• (2)|-(3): Valid.


Premise		1      (Ax)Fx->(Ax)Gx
Assume		2 +----¬(Ex)(Fx->Gx)
IM2		3 +    ¬(Ex)(¬Fx v Gx)
QN3     	4 +    (Ax)¬(¬Fx v Gx)
DM4		5 +    (Ax)(¬¬Fx & ¬Gx)
DN5		6 +    (Ax)(Fx & ¬Gx)
AEa/x6		7 +    Fa & ¬Ga
&EL7		8 +    Fa
AIa/x8		9 +    (Ax)Fx
->E1,9		10+    (Ax)Gx
AEa/x10		11+     Ga
&ER7            12+---- ¬Ga
¬E2-11,2-12     13 (Ex)(Fx->Gx)


• (3)|- (2): Invalid. Model

UD:={a,b}
Fx:={a,b}
Gx:={a}

Obviously, a shows that (Ex)(Fx->Gx) is satisfied. The model satisfies (Ax)Fx because Fx:={a,b} is the whole universe. The model does not satisfy (Ax)Gx because b is not in Gx. Hence the model does not satisfy
(Ax)Fx->(Ax)Gx.