Updated 09 November 2000

$xFx

Is that true ?

To answer -

interpretation

domain

meaning of predicates

$x[Sx Ù Rx]

Interpretation

Domain : residents Oxford

Sx : x is a student

Rx : x is rich

Interpretation

Domain: dons Oxford

Sx : x is smart

Rx : x is rich

Predicates

intension (meaning)

extension

Determining whether something is true or false is a matter of going through the intension to the extension

$xFx

Fx : x is funny

can you find ?

what is the extension ?

$x[Fx Ù Gx]

Interpretation

Domain {a, b, c}

Fx : {a, b}

Gx : {a}

so the wff is true

$x[Fx Ù Gx]

Domain {a, b, c, d}

Fx: {a, b}

Gx: {c, d}

The wff is false

$ " F x P

Propositional Logic

consistency

P1, P2, P3 |- C

(via tableau)

then

P1, P2, P3 |= C

(via truth tables)

Completeness

P1, P2, P3 |= C

(via truth tables)

then

P1, P2, P3 |- C

(via tableau)

Consistency

If P1, P2, P3 |- C

then P1, P2, P3 |= C

Completeness

If P1, P2, P3 |= C

then P1, P2, P3 |- C

P1, P2, P3 |- C

just in case

P1, P2, P3 |= C

10.

Theorems

|- P Ú ØP

Can be established by tableau without premises

11.

Tautologies |= P Ú ØP

P | P Ú ØP

----------------

T | T F

F | F T

|- f just in case |= f

12.

Predicate logic

no truth tables

true in an interpretation

|= f just in case f is true in every interpretation

every interpretation !?!?

13.

Domains:

students,

counting numbers 1,2,3,…,

clever and honest politicians,

ballroom dancers,

fundamental particles,

copies of yesterdays’ Independent,…

14.

Predicates:

x is a student;

x is a Zemindar,

x is twice as large as y and z together,

x is made of silver, …

15.

P1, P2, P3 |= C

Every interpretation which makes P1, P2 and P3 true also makes C true.

P1, P2, P3 |- C

Tableau closes

Completeness

16.

P1, P2, P3 |- C

then

P1, P2, P3 |= C

Consistency 17.

Completeness

Proved by Godel.

Warming up exercise for Gödel’s Theorem

See Gödel, Escher, Bach.

18.

n : Dobaci

Lxy : x loves y

$x"yLxy |- Lnn

CES

{ $x"yLxy, ØLnn }

19.

$x"yLxy |- Lnn

$x"yLxy

ØLnn

"yLay

Laa

Lan

"yLby

Lba

Lbn

Lbb

"yLcy

Lcb

Lcn

Lca

Lcc

20.

$x"yLxy |- Lnn

Interpretation

Domain : this audience

+ God + Dobaci

Lxy : x loves y

n : Dobaci

Dobaci hates himself, God loves everyone one. So premise true, conclusion false.

\ not valid

21.

$x"yLxy |- Lnn

Interpretation

Domain : { a, b }

“n” Þ b

“Lxy” Þ {<a, a> , <a, b>}

22.

Referring

Names : n, m, ...

(non-vacuous)

Pronouns

“ He is a spy”

Let “n” be the name of the person picked out by use of “He”.

Not equivalent in meaning but good enough.

23.

Definite Descriptions

The lecturer is happy.

Hx : x is happy.

n : The lecturer

The lecturer is happy. \ There is a lecturer.

Hn |- $xLx

tableau won’t close !

24.

Hn : The lecturer is happy.

First Problem: we lost information.

Second Problem: designators must be non-vacuous.

25.

Something exists

$x [x=x]

The King does not exist.

n : The King

Ø$x[x=n]

26.

But $x[x=n] is a theorem.

CES {Ø$x[x = n] }

tableau

Ø$x[x = n]

"xØ[x=n]

Ø[n=n]

So it is true come what may that $x[x=n]. But the king does not exist !!!

Don’t treat definite descriptions as names.

27.

Russell’s Theory of Definite Descriptions.

The lecturer is bored.

1. There is a lecturer.

$xLx

2. There is at most one lecturer

"x"y[[Lx Ù Ly] ® x=y]

3. He is bored. "x[Lx ® Bx]

28.

Better

$x[[ Lx Ù "y[Ly ® x=y]] Ù Bx]

Hodges (bless him]

$x"y[ x=y « Lx] Ù "x[Lx ® Bx]

Domains need particular care.

29.

The train is late.

Tx : x is a train

Lx : x is late

$x[[Tx Ù "y[Ty ® x=y]] ÙLx]

One and only one train !!!

Soon but not yet.

30.

1. Make the domain small

Domain : trains expected at Oxford from London in the next hour.

2. Take a larger domain but use an extra predicate.

Domain : trains in the UK

Nx : train with engine no. 7374

$x[[[Tx Ù Nx] Ù "y[[Ty Ù Ny] ® x=y]] Ù Lx]

31.

Do not apply Russell’s theory mechanically.

The whale is a mammal.

$x[[Wx Ù "y[Wy ® x=y]] Ù Mx]

"x[ Wx ® Mx]

32.

The lecturer is mad. \ There is a lecturer.

Mn |- $xLx

$x[[Lx Ù "y[Ly ® x=y]] Ù Mx ]

|- $xLx

CES

{$x[[Lx Ù "y[Ly ® x=y]] ÙMx], Ø$xLx }

33.

$x[[LxÙ"y[Ly®x=y]]ÙMx]

Ø$xLx

"xØLx

[[LaÙ"y[Ly®a=y]]ÙMa]

[La Ù "y[Ly ® a=y]

"y[Ly ® a=y]

ØLa

34.

Our second problem

The King does not exist.

domain : residents of UK

n : the King

Ø$x[x=n]

Won’t do because $x[x=n] is a theorem.

The King exists

$x[Kx Ù "y[Ky ® x=y]]

The King does not exist

Ø$x[Kx Ù "y[Ky®x=y]

35.

Icabod does not sing.

Domain : all humans

Sx : x sings

n : Icabod

ØSn

The Truth Revealed !

Icabod does not exist.

Ex : x exists

ØEn

36.

ØEn

Absurd. There is Icabod lacking the property of existence !

Icabod lacks singing abilility and also existence.

Existence is not a predicate

Existence is expressed by the existential quantifier.

37.

So we cannot write : ØEn.

But still this Icabod does not exist.

Who is Icabod ?

Icabod is the Balliol student who is clever and who is over 10 feet tall.

Drop names in favour of definite descriptions.

Cerberus exists.

Who is Cerberus ?

Gx : x is a dog who guards the gates of Hell.

$x[[Gx Ù "y[Gy®x=y]]

Cerberus does not exist.

Ø$x[[GxÙ"y[Gy®x=y]]

Translation ?

Device ?

39.

How many heads has Cerberus ?

Domain : animals

Tx : x has three heads.

$x[[Gx Ù "y[Gy®x=y]] Ù Tx].

Domain : fictional animals

True in the domain of fictional animals. False in the domain of real animals.

40.

Cerberus has three heads but Cerberus does not exist !

1. Cerberus does not exist but people imagine that he does exist and that he has three heads.

2. Domain of real and fictional animals.

Fx : x is fictional.

$x[[GxÙ"y[Gy®x=y]] Ù Fx]

Fido : the dog of Billy Hague

Fido is not fictional.

$x[[Mx Ù "y[My ® x=y]] Ù ØFx]

41.

There is at least one student.

$xSx

There are at least two students.

$x$y[[Sx Ù Sy] Ù Ø[x=y]]

There are at least three students.

$x$y$z[[[SxÙSy]ÙSz]] Ù [[[Ø[x=y] ÙØ[x=z]] Ù Ø[y=z]]].

42.

There is at most one student.

"x"y[[Sx Ù Sy] ® [x=y]]

There are at most two students.

"x"y"z[[[Sx Ù Sy] Ù Sz] ® [[x=y] Ú [x=z]]

43.

There is exactly one student.

$x[Sx Ù "y[Sy ® x=y]]

There are exactly two students.

$x$y[[Sx Ù Sy] Ù "z[Sz ® [z=x] Ú [z=y]]].

And so on and so forth without limit.

Can we get rid of the numerals in this way?

44.