Notes on Lecture 9 (full-time)

Slide 21:

"Evaluation in first-order logic"

First we write out all the possible Q predicates. Because Q={(x,y)|x=y} and x,y in {M,T,H} we get:

Q= {(Mark, Mark), (Harry, Harry), (Tom, Tom)} (1)

In our theory we are given P(a,y) (2)

and in the structure we are given a=Tom (3).

We see from the possible P pairs {(Tom, Mark), (Tom, Harry), (Mark, Harry) } (4)

that the only possible values for y from (2), (3) and (4) are:

y in {Mark,Harry} (5)

so from (4),(5) we have that:

P={(Tom,Mark),(Tom, Harry)} (6)


We need now to check whether there exists an x in {T,M,H} such that for all y in {T,M,H} Q(f(y),x) is true (our theory)

We check one by one all the allowed values of y:

For y=Mark:

Q(f(Mark), x) = Q(Harry,x)

in order for this predicate to be true, it needs to be one of the allowed predicates in (1).
The only value of x that satisfies this is x=Harry

For y=Harry

Q(f(Harry),x)=Q(Harry,x)

similarly, in order for this predicate to be true, it it needs to be one of the allowed predicates in (1).
The only value of x that satisfies this is x=Harry

Therefore, our theory, given the specific structure becomes true for x=Harry.
We say that the structure is a model for our theory.

Structure:
X={T,M,H}
a=T
P={(Tom, Mark), (Tom, Harry), (Mark, Harry) }
Q=Q={(x,y)|x=y}
f(T)=m,f(M)=f(H)=H