FIRST ORDER LOGIC

PHIL 210

What are the three ideas which allow us to ‘split the atom’ in FOL?

Names: Indicated with lowercase italic letters: “b” for Bernie. In FOL names are lowercase letters a-r

Predicates: Expressions like ‘———’ is a dog. We indicate predicates with uppercase letters. D = ——- is a dog. Predicates express properties of individuals. Predicates are capital letters A-Z

We can therefore symbolize this FOL sentence as D(b)

Quantifiers: ∃ - The existential quantifier ‘there is at least one’

‘∀: “the universal quantifier”

• Quantifiers must always be followed by a variable. Variables are lowercase italic letters s-z

• The order of Quantifiers used MATTERS

The problem of non-referring terms?

Each name of FOL must refer to something in the domain in order to avoid this problem of referencing things that do not ‘exist’ and therefore cannot be true or false (which also violates law of excluded middle)

For sentences with one quantifier which symbolizations are used?

With the universal quantifier, the conditional is used.

With the existential quantifier, the conjunction is used.

So ‘only Fs are Gs’ (ex. Only dimes are on the table) is symbolized as ¬∃x (G(x) ∧ ¬F(x)) and also as ∀x (G(x) → F(x)).

What are empty predicates?

A predicate that applies to nothing in the domain. Things can be vacuously true if an empty predicate is in the domain.

What is scope in FOL?

To be defined when using conditionals

What are Ambiguous predicates?

What are atomic sentences?

• An atomic formula with no variables (x,y)

What are the 6 kinds of symbols in FOL?

• Predicates

• Names

• Variables

• Connectives

• Brackets

• Quantifiers

What is an atomic formula?

• Any sentence letter

• R(n)

• n=n

• Nothing else

When are variables free vs. bound?

• Variable x is bound iff it falls within the scope of the quantifier (Ex)

• Variable is free when it is not bound

What is a sentence in FOL?

Any formula that contains no free variables

• ∃x H(x) = sentence

• H(x) = not a sentence (x is free)

What is the scope of a formula?

• The quantifier and its variable, together with A

  • Also known as the subformula it begins with

What is the use of interpretations?

• Used to evaluate TRUTH

  • Requires we supply

    • A domain

    • Assignments of constants (objects in the domain)

    • Assignments of predicates (properties/relations on the domain)

      • ex

        • Domain: {students in the class}

        • Constant m → Mandy

        • Predicate H(x) → "x likes hiking"

Truth does not come from a table, it comes from interpretation

How do we assign truth to formulas with Free Variables?

• To evaluate H(x), we need to know who x refers t

  • We need an interpretation with a variable assignment such as: I[d/x]

    • Ex: H(x) under I[m/x] = H(m).

    • This gives us an idea of satisfaction

      • An object d satisfies A(x) in I iff A(x) is true under I[d/x].

What are truth conditions for the quantifiers?

• Universal Quantifier: ∀xA(x)

  • is true in I iff every object in the domain satisfies A(x).

• Existential Quantifier: ∃xA(x)

  • is true in I iff at least one object satisfies A(x)

How do i define truth for different sentences?

• Atomic sentence truth → from interpretation

• Connectives → truth tables

• Quantifiers → satisfaction

• Sentences (no free vars) → true or false in a full interpretation

What does it mean for an object d to satisfy A(x)?

A(x) is true under I[d/x]

Is ∀x H(x) a sentence?

Yes (no free variables)

Is H(x) ∨ ∃x K(x) a sentence?

No, because H(x) has a free x.

Why are truth tables not enough in FOL?

Because predicates do not have fixed meanings - we must interpret them using domains, constants, and extensions

What is first-order validity?

An argument is first-order valid if there is no interpretation in which all premises are true and the conclusion is false; instead of checking valuations (like in TFL), we check interpretations (domains, constants, predicate extensions)

What is a predicates extension

A set of domain objects that make it true

• ex. H(x) = {things smaller than Earth}

How do I show an argument is not FOL valid?

You must provide an interpretation where all premises are true and the conclusion is false

Notation for variable assignment

σ

ex.

• σ(x) = d (means σ assigns object d to x)

• Purpose: allows us to talk about truth of formulas with free variables

What is the truth for formulas**

Formula ‘A’ is true in an interpretation ‘I’ if for every variable assignment σ, A is true in I under σ

• To count as “true in the interpretation”, ‘A’ must come out true no matter which object is assigned to its free variables

  • A formula is a first-order truth if it is true in every interpretation under every variable assignment

What is first order equivalence?

• Two formulas A and B are first-order equivalent if: For every interpretation I and every variable assignment σ,
  

  A and B have the same truth value under I and σ.

Validity of inferences?

Inferences: all interpretations & all variable assignments

• An inference is valid if: For every interpretation I and every assignment σ,
  

  if all premises are true in I under σ,
  

  then the conclusion is true in I under σ.

Why is semantic reasoning alone not enough to decide validity in FOL?

• Interpretations are infinite in number

• Domains can be infinitely large

• Predicate extensions can be infinite

• Assignments can vary over infinite objects

What are the limits of interpretations?

No number of interpretations can show

• That a sentence is a validity

• that two sentences are equivalent

• that sentences are unsatisfiable

• that an argument is valid

Why are there limits to interpretations?

• There are infinitely many domains

• There are infinitely many possible predicate extensions

• Infinitely many variable assignments

What can you show with a single interpretation?

The negatives

• A sentence is not a first-order truth

• Two formulas are not equivalent

• Some formulas are satisfiable

• An argument is not valid

Why?

• Because each of these requires just one interpretation (a counterexample), like how in TFL an argument is invalid using one valuation

What does a counter interpretation consist of?

1. A domain

2. An interpretation (extensions of predicates & relations, constants)

3. A variable assignment

How to produce a counterinterpretation?

1. Start with a small domain

2. Universal premises don’t force more objects

3. Existential premises may require adding objects

What is a counterinterpretation?

• An interpretation where all premises are true and the conclusion is false.

How to symbolize “At least two people”

To do this, we must symbolize that the two people are NOT the same person. Just because we use different variables, does not mean they are different: thus \~(x=y), says that person x and person y are NOT the same.

What does every hero wears a cape mean?

If hero x that exists (Ax), then hero x also wears a cape.

Which semantic notions require us to check all rows of truth tables?

Tautology & Validity

Which rules require citing one or more subproofs?

Disjunction elimination, negation introduction, implication introduction

“Only Pavel owes money to Hikaru”

MEANS: 1) Pavel owes money to Hikaru. 2)No one who is not Pavel owes money to Hikaru.

1) O(p,h)

2)Ax(O(x,h)←> x = p)

Therefore: O(p,h) & Ax(O(x,h)←> x = p)

“There are at least two apples”

There are at least two apples AND they are not the same apple.

ExEy((E(x)&A(y)&\~x=y)

“There are at least three apples”

∃x∃y∃z[( (A(x) ∧A(y)) ∧A(z)) ∧ ( (¬x = y ∧ ¬ y = z) ∧ ¬x = z)]

There is at most one apple

Means “It is not the case that there are at least two apples”

¬∃x∃y[(A(x) ∧ A(y)) ∧ ¬x = y]

OR

∀x∀y [ (A(x) ∧ A(y)) → x = y ]

There are at most two apples

Means “It is not the case that there are three or more distinct apples”

¬∃x∃y∃z [ ( (A(x) ∧A(y)) ∧A(z)) ∧ ( (¬x = y ∧¬x = z) ∧¬ y = z)

OR

∀x∀y∀z [ ( (A(x) ∧ A(y)) ∧ A(z)) → ( (x = y ∨ x = z) ∨ y = z) ]

There is exactly one apple

Means: there is at least one apple and there is at most one apple

∃xA(x) ∧ ∀x∀y [ (A(x) ∧ A(y)) → x = y ]

OR

∃x [ A(x) ∧ ∀y(A(y) → x = y) ]

There are exactly three apples

∃x∃y [ ( (A(x) ∧ A(y)) ∧ ¬x = y) ∧ ∀z(A(z) → (x = z ∨ y = z))]

There are exactly two things//there are exactly two objects

∃x∃y ¬x = y ∧ ¬∃x∃y∃z( (¬x = y ∧ ¬ y = z) ∧ ¬x = z) ∃x∃y [ ¬x = y ∧ ∀z(x = z ∨ y = z) ]

How do we symbolize ‘Else’

We must differentiate between objects.

“For all x, for all y, if x is different from y, then O(x,y)”

AxAy(~(x=y)→O(x,y))

Someone observes everyone else

Ex(P(x)&Ay((P(y)&~x=y)→O(x,y))

No one other than x is a hero

Ex(H(x)&Vy(H(y)→x=y))

There are exactly two hero’s

ExEy((H(x)&H(y)&~x=y))&Az(H(z)→(z=x&z=y)))

“The”

Ex((A(x)&Ay(A(y)→x=y))&B(x))

Definition of an argument that is valid in FOL?

All interpretations make either the conclusion true or at least one premise false (it is impossible for all premises to be true while the conclusion is false) → regards conclusion and premises NOT the truth of argument

What is the definition of joint satisfiability in FOL?

Not every interpretation makes either (or both) of the two FOL sentences false