The proof depends upon the fact that, if v and vN agree on the free

Spring, 2004
Phi 432/532: Completeness & Decidability
SEMANTICS (contd.)
Example: Let LE be the first order language whose extralogical vocabulary E comprises three 1-place
predicate symbols F, G and H, and let A = <A, vA > be the LE-structure such that A = {1, 2, 3}, vA(F) =
{1, 3}, vA(G) = i and vA(F) = A. Interpret the following LE- sentences in A (i.e. determine their respective
truth values):
a) xFx
e) x-(Hx 6 Fx)
i) (xFx w yHy)
b) x(Hx 6 Gx)
f) (xFx 6 xGx)
j) x(Fx w yHy)
c) x(Gx 6 Hx)
g) x(Fx 6 Gx)
k) (xFx v yGy)
d) -x(Hx 6 Fx)
h) -xGx
l) x(Fx v yGy)
Some Semantic Lemmas
1) If for all x 0 t V v(x) = vN(x), then denA(t) [v] = denA(t) [vN]
Proof By induction on terms.
2) If for all x 0 FvN v(x) = vN(x), then <A(N) [v] = <A(N) [vN]
Proof By induction on formulas.1
Base Step: N is atomic. Then, there are two subcases to consider.
Subcase i N is of the form P(t1,...
, tn), then
<A(N) [v] = T iff <denA(t1),... denA(tn)> [v] 0 vA(P)
iff <denA(t1),... denA(tn)> [vN] 0 vA(P)
iff <A(N) [vN] = T
Subcase ii N is of the form t . u, then
<A(N) [v] = T iff denA(t) [v] = denA(u) [v]
iff denA(t) [vN] = denA(u) [vN]
iff <A(N) [vN] = T
[by def. of <A]
[by 1) above]
[by def. of <A]
[by def. of <A]
[by 1) above]
[by def. of <A]
Induction Step: We assume as our induction hypothesis that the result holds for the immediate
subformulas of N and set out to prove that it holds for N.2 There are six subcases to consider.
The proof depends upon the fact that, if v and vN agree on the free variables of N then, if N is
atomic, they agree on the variables of every term occurring in N and, unless N is a universal or an
existential formula, they will also agree on the free variables of the immediate subformula(s) of N.
1
2
Notice that the induction hypothesis assumes that the result holds for any variable
interpretations which agree on the free variables of the immediate subformulas of N, not for some
specific v and vN. This matters for subcases v and vi below.
1
Subcase i N is of the form ¬2, then
<A(N) = T [v] iff <A(2) = F [v]
[by def. of <A]
iff <A(2) = F [vN]
[by the induction hyp.]
iff <A(N) = T [vN]
[by def. of <A]
Subcase ii N is of the form (2 v R) Exercise
Subcase iii N is of the form (2 w R) Exercise
Subcase iv N is of the form (2 6 R) Exercise
Subcase v N is of the form x2
Exercise
Subcase vi N is of the form x2.
By definition, FvN = Fv2 ! {x}. It follows that, if v and vN agree on the free variables of N, then, for any
a 0 A, [v(x/a)] and [vN(x/a)] agree on the free variable of 2. So,
<A(N) = T [v] iff <A(2) [v(x/a)] = T, for some a 0 A
[by def. of <A]
iff <A(2) [vN(x/a)] = T, for some a 0 A
[by the induction hyp.]
iff <A(N) = T [vN]
[by def. of <A]
3) If N is a sentence, then either <A(N) [v] = T for every variable assignment v, or <A(N) [v] = F for every
variable assignment v.
Proof Trivial corollary of 2) above.
So, if N is a sentence of LE, the preceding becomes a definition of the truth of N in A , without reference
to variable assignments.
LOGICAL CONSEQUENCE
We define the basic logical properties of, and relations between, formulas of LE in much the same way
as we did for PL. The difference is only that LE structures play the role of admissible truth assignments.
Definitions: Let N be a formula of LE, then:
1) N is said to be satisfiable if there is some LE-structure, A and variable interpretation v such
that <A(N) [v] = T. (In this case, we say that v satisfies N in A .)
A set ' of formulas of Lv is satisfiable if there is some LE-structure, A and variable interpretation
v such that <A(() [v] = T, for every ( , '.
2) If every LE-structure, A and variable interpretation v which satisfies ' satisfies N, then N is
said to be a logical consequence of ', and we write ' Ö N. (If N is not a logical consequence of ', we
write ' | N.
3) N is said to be logically equivalent to R (in symbols, N X R) if, for every LE-structure, A and
variable interpretation v, <A(N) [v] = <A(R) [v].
2
4) N is said to be logically true (in symbols, Ö N) if, for every LE-structure, A and variable
interpretation v, <A(N) [v] = T.
Example: (Exercise 3.25 on page 104 of Zalabardo) We show that {(xN 6 xR)} Ö x(N 6 R).
Let A be a structure and v a variable interpretation in A such that <A((xN 6 xR)) [v] = T.
We have to show that <A(x(N 6 R)) [v] = T.
<A((xN 6 xR)) [v] = T iff <A(xN) [v] = F or <A(xR) [v] = T
[by def. of <A]
3
iff <A(N) [v(x/a)] = F, for some a 0 A or <A(R) [v(x/a)] = T, for every a 0 A
[by def. of <A]
So, there are two cases to consider:
Case 1: <A(N) [v(x/a)] = F, for some a 0 A. In this case, <A(xN) [v] = F.3
Case 2: <A(R) [v(x/a)] = T, for every a 0 A. In this case, <A(xR) [v] = T.
In either case, it follows that <A(xN) [v] = F or <A(xR) [v] = T and, thus, <A(x(N 6 R)) [v] = T.
Notice that, because <A(xN) [v] = T iff <A(N) [v(x/a)] = T, for every a 0 A, it follows that
<A (xN) [v] T iff it’s not the case that. for every a 0 A, <A(N) [v(x/a)] = T; i.e. iff, for some a 0 A,
<A(N) [v(x/a)] = F.
3
3

Download Report