Soundness and Completeness
. Show that the following PML tree rules are sound on the given frames:
(a) the D-rule on SER;
Assume an open branch b is satised by a serial model and that the D rule is applicable to b. When
the rule is applied, for some n mentioned on b and some m not mentioned on b, b is extended to b by
adding n > m. By assumption, there is a serial model M, containing a point f n. Since this model is serial,
theres also some point s in M with R f ns. We then set f m = s. Since m was new to b, theres nothing of
the form A, m on b and hence M satises b .
That branch is TRANS-satisable. (To check: build a model from the branch, making sure its transitive.)
But if you apply the -rule and add 2 > 1, it ceases to become TRANS-satisable, because you can then
add p, 2 followed by p, 1 and the tree closes. (So in fact, the branch becomes unsatisable for any
frame condition.)
Now, you might wonder what kind of alchemy I used to get this branch. The answer is simple: I knew
that (p p) is EUC-unsatisable, so a K-tree starting from p and p (or equivalently:
p) will close, whereas a K-tree from those sentences wont close. So, before applying the -rule,
the branch has a transitive model, whereas after applying the -rule, the branch will close and so wont
have any model.
NB this was a hard question!!
. (a) Show (using a tree) that A KT4 A.
A, 2
0>1
A, 1
1>1
A, 0
(b) the B-rule on SYM;
Assume an open branch b is satised by a symmetrical model and that the B rule is applicable to b. When
the rule is applied, for some line n > m on b, b is extended to b by adding m > n. By assumption, theres
a symmetrical model M with Rf nf m which satises b. Since M is symmetrical, we have Rf mf n and
hence M satises b too.
0>0
2>2
0>2
A, 2
(c) the -rule on EUC.
Assume an open branch b is satised by a euclidian model and that the rule is applicable to b. When the
rule is applied, for some lines n > m and n > l on b, b is extended to b by adding m > l. By assumption,
theres a euclidian model M with points n, m, l such that R f n f m and Rf n f l. Since M is euclidian, we
have Rf m f l and hence M satises b too.
A, 0
A, 0
A, 2
(b) From an open branch on this tree, build a reexive and transitive model M containing a point s
such that AM,s = T but AM,s = F.
1 A
. Show that the -rule is not sound on TRANS. (You need to think rst about what is means for a
tree rule to be sound or unsound. Then work out how youd go about demonstrating this in the
case in question.)
We need to give a counterexample, i.e., a branch thats TRANS-satisable before the -rule is applied,
but not after. Heres such a branch:
p, 0
p
0>1
p, 1
0>2
p, 2
2 A
Here, 0 is the required point.
(c) Explain why this shows that A REF+TRANS A. (REF+TRANS is the reexive and transitive
frame, containing all models that are both reexive and transitive.)
By denition, A REF+TRANS A iff, for every point s in every model M in REF+TRANS, if AM,s =
T then AM,s = T. But point 0 in the model above shows that this isnt so: AM,0 = T but
AM,0 = F. So A REF+TRANS A.
. (a) Give an argument to show that any model built from a nished open branch in a KT tree will be a
reexive and transitive model.
Suppose M is built from such a branch b. Suppose M contains a point s. Then s = f n for some sentence
A, n on b. Since b is nished, n > n must be on b, and hence Rss in M. So M is reexive. Now take any
points s, t, u in M where Rst and Rtu. Then there are numerals n, m, l such that f n = s, f m = t and
f l = u, such that n > m and m > l are on b. Since b is nished, n > l is also on b, and so Rsu. Hence M
is transitive.
(b) Explain why the answer to (a) shows that the KT tree test is complete with respect to REF+TRANS.
We know (from the standard K completeness proof) that models build from nished open branches
satisfy the sentences on those branches. (a) shows that the model built from a nished open KT
branch is reexive and transitive. So, if the KT-tree beginning with G, A nishes open, then theres a
model in REF+TRANS satisfying G and A, and so G REF+TRANS A. Contraposing, if G KT4 A then
G REF+TRANS A. Thats completeness for KT on REF+TRANS.
. Using a tree, construct a model which validates the but not the axiom (i.e., a model for which the
but not the axiom is true at all worlds). Hint: start by showing that the axiom isnt provable
in K.
First, the K tree:
(A A), 0
A, 0
A, 0
A, 0
0>1
A, 1
0>2
A, 2
A, 2
Then the transitive model:
0
1
A
Here, point 0 satises A but not A, hence 0 does not satisfy the axiom, A A. Since the
model is transitive, it will satisfy the axiom, A A.
