first order logic

how can we split up contents of a sentence

names

predicates

quantifiers

names

a b c / 𝑎1, 𝑎2, 𝑎3

all names are unique

predicates

F G H / 𝐹1, 𝐹2, 𝐹3

• eg ‘is an elephant’, ‘is a mammal’, ‘is an even number’ and ‘tells lies’

• attaches before the name - Fa

variables

gaps created by removing names , placeholders for nothing

x y z / 𝑥1, 𝑥2, 𝑥3

These allow us to write open sentences:

• Fx: x is a fox

• Lxy: x loves y

logical connectives

¬ , ∧ , ∨ , → , ↔

quantifiers

• ∀x : “for all x”, “every x”

• ∃x : “there exists an x”, “some x”

the universal quantifier

• Pa – Adam is physical

• ∀𝑥𝑃 𝑥 – Everything is physical

• (𝐸𝑑 → 𝑀𝑑) If Dumbo is an elephant, then Dumbo is a mammal

• ∀𝑥(𝐸𝑥 → 𝑀𝑥) - All elephants are mammals

existential quantifier

• Pa – Adam is physical

• ∃𝑥𝑃 𝑥 – some things are physical

• (𝐸𝑑 → 𝑀𝑑) - If Dumbo is an elephant, then Dumbo is a mammal

• ∃𝑥(𝐸𝑥 ∧ 𝑀𝑥) - Some elephants are mammals

domains

we implicitly use domains so we dont refer to everyone, everywhere, from all times

In FOL, we make domains explicit:

• the set of currently living people

• The set of all people who have ever lived

• The set of all natural numbers

• The set {Prince William, Bonny Prince Charlie, Prince}

quantifiers and scope

A quantifier applies to the matching variables within its scope.

• (∀𝑥𝐴𝑥 ∧ ∃𝑥𝑇 𝑥): everyone is alive and someone is talented

• ∀𝑥(𝐴𝑥 → 𝑇 𝑦): for anyone who is alive, y is talented (but what is y referring to?)

quantifiers and negation

the placement of a negation can seriously affect a quantifier:

(∀𝑥 ¬𝐴𝑥) = (¬ ∃𝑥𝐴𝑥)

(¬ ∀𝑥𝐴𝑥) = (∃𝑥 ¬𝐴𝑥)

translating cheat sheet

• “All Fs are Gs” = ∀𝑥(𝐹𝑥 → 𝐺𝑥)

• “Some Fs are Gs” = ∃𝑥(𝐹𝑥 ∧ 𝐺𝑥)

• “No Fs are Gs” = ¬ ∃𝑥(𝐹𝑥 ∧ 𝐺𝑥)

• “Not all Fs are Gs” = ¬ ∀𝑥(𝐹𝑥 → 𝐺𝑥)

2 place predicates

relationship between 2 variables

• Lxy: x loves y

• Rxy: x is to the right of y

• Sxy: x is shorter than y

(∀𝑥𝐿𝑥𝑥 → ∃𝑦𝐿𝑦𝑡): If everyone loves themselves, then someone loves Tom Hardy

multiple generality

two quantifiers affect one another, one within the scope of another:

∀𝑥 ∃𝑦𝐿𝑥𝑦 = “For each person, there is someone who they love”

∃𝑦 ∀𝑥𝐿𝑥𝑦 = “There is at least one person such that everybody loves them”

• These are not equivalent!

• order of construction matters because 1 quantifier is in the others scope

keeping track of variables

• Different variables may pick out different objects (though they don’t need to!)

• If you have the same variable within the quantifier’s scope, it must pick out the same object or objects:

Basic check: if you have a variable in your sentence, there should be a quantifier featuring it which has the variable within its scope

equivalence

(∀𝑥 ¬𝐴𝑥) = (¬ ∃𝑥𝐴𝑥)

(¬ ∀𝑥𝐴𝑥) = (∃𝑥 ¬𝐴𝑥)

surface vs logical order

“All Fs are G” and “Some Fs are G” have:

• The same form in English (surface form) - same language form

• A different form in FOL (logical form) - ∀x(Fx→Gx) vs ∃x(Fx∧Gx)

“Some politicians are liars, and some politicians are not liars”

(∃x(Px∧Lx)∧∃y(Py∧¬Ly))

sometimes logic is strict and ordinary language is loose

• “Or” can be inclusive/exclusive – “∨” is always inclusive

• “And” sometimes implies temporal order – “∧” never does

• “If/then” seems to commit to less than “→” does

• “Some frogs are green”

• “Some frog is green”

“∃x(Fx∧Gx)” is used for both - no distinction

empty predicates

contraries vs contradictories

Hk = Karl is happy

¬Hk does NOT mean Karl is unhappy, it means he is not happy

• can be not happy without being unhappy

• happy and not happy = contradictories (cannot both be true or both be false)

• happy and unhappy = contrary (cannot both be true, but they can both be false

syncategorematic terms

too many predicates

• “Vladimir Putin is a Russian politician” = (Rv∧Pv)

• “Vladimir Putin is a good politician” = (Gv∧Pv) – problem!

“good” is not an independent predicate, it modifies the other predicate, “politician”

When an English sentence reads “a is an [adjective 1] [adjective 2]”: If it can be paraphrased as “a is an [adjective 1] and a is an [adjective 2]”, you may represent it as (Fa∧Ga)

• Otherwise, you must create a single predicate and write Ha

only

“Only animals have intelligence” = “The only things that have intelligence are animals” = “Anything that has intelligence is an animal”, so:

∀x(Ix→Ax)

all and only

• “All Fs are Gs”: ∀x(Fx→Gx)

• “Only Fs are Gs”: ∀x(Gx→Fx)

• “All and only Fs are Gs”: (∀x(Fx→Gx)∧∀y(Gy→Fy))

We can represent this more simply, since we have a conditional that goes both ways:

“All and only Fs areGs”: ∀x(Fx↔Gx)

2 place predicates / binary relations

relations between more than 1 variable

‘Rishi Sunak knows Boris Johnson’

• Bx: ‘x knows Boris Johnson’ (or ‘___ knows Boris Johnson’)

• Rx: ‘Rishi Sunak knows x’ (or ‘Rishi Sunak knows x’)

• Kxy: ‘x knows y’ (or ‘___₁ knows ___₂’) (2 place predicates)

combining quantifiers and relations

• “Anisha respects Bethany” = Rab

• “Anisha respects someone” = ∃xRax

• “Everyone respects Bethany” = ∀xRxb

• “No one respects Carlos” = ¬∃xRxc

• “If everyone respects Bethany, Anisha respects Bethany = (∀xRxb→Rab)

• “If Carlos respects himself, then someone respects Carlos = (Rcc→∃xRxc)

• “Someone respects Bethany and Carlos” = ∃y(Ryb∧Ryc)

• “Anisha respects anyone who respects her” = ∀x(Rxa→Rax)

multiple quantifiers

In all the below cases, we can either repeat the same variable or use a new one

• “Either no one respects Carlos, or someone respects Carlos” = (¬∃xRxc∨∃yRyc)

• “If everyone respects Anisha, then everyone respects Bethany” = (∀xRxa→∀xRxb)

• “There’s someone Bethany respects, and someone she doesn’t = (∃yRby∧∃z¬Rbz)

Things get interesting where two uses of a quantifier depend on each other

• “Someone respects someone else” = ∃x∃yRxy

• “There is someone who respects everyone” = ∃x∀yRxy

quantifier shift fallacy

many sentences with multiple quantifiers are ambiguous

• confusing 2 ambiguous readings is the quantifier shift fallacy

Everything aims at some good (or other). Therefore: there is some (one) good at which everything aims.

• Translation: ∀x∃y(Axy∧Gy). Therefore: ∃y∀x(Axy∧Gy)

• invalid