Interpretations
Extensions can be listed or described ("{u : u is odd}"), and can be empty. A one-place predicate's extension is a set of 1-tuples, which the book writes as plain members.
Variable assignments and satisfaction
Open formulas like Gxy aren't true or false. Instead, a variable assignment d gives each variable a member of the UD, and d either satisfies a formula or doesn't. d[u/x] is the assignment that agrees with d except that it gives x the value u.
- d satisfies (∀x)Q when d[u/x] satisfies Q for every u in the UD.
- d satisfies (∃x)Q when d[u/x] satisfies Q for at least one u.
- A sentence is true on I when every variable assignment satisfies it, and false when none does. (For sentences those are the only possibilities.)
This is called satisfaction semantics.
Reading quantifiers on a small UD
With UD {1, 2, 3}, (∀x)Fx asks whether 1, 2 and 3 are all in F's extension. (∃x)(∀y)Lxy asks whether some x stands in L to every y, including itself.
The UD is never empty, so (∀x)Fx ⊃ (∃x)Fx is quantificationally true.
Quantificational properties
The definitions copy Chapter 3's, with "interpretation" in place of "truth-value assignment".
- Quantificationally true / false / indeterminate: true on every interpretation / false on every one / neither.
- Equivalent: no interpretation gives them different truth-values.
- Consistent: some interpretation makes every member true.
- Γ entails P, and valid: no interpretation makes Γ (the premises) true and P (the conclusion) false.
Showing that something exists takes one interpretation: a model of a set, or a counterexample to an argument. Showing that nothing exists means reasoning about all interpretations, and there are infinitely many. That reasoning has to be general; Chapters 9 and 10 give methods for it.
Two theoretical points
Löwenheim's theorem. A sentence of PL without identity that is true on some interpretation is true on one whose UD is the positive integers. Some sentences are true only on infinite UDs, so small finite models aren't always enough.
Church's theorem. Unlike SL, PL has no decision procedure that settles quantificational truth for every sentence. Sentences with only one-place predicates are the exception (Bernays and Schönfinkel).
Truth-functional expansions
If every member of a finite UD is named by one of a chosen set of constants, a universal sentence says the same as the conjunction of its substitution instances, and an existential sentence the same as their disjunction. Replacing every quantifier this way gives a truth-functional expansion, which can be studied with truth-tables.
The chosen set must include every constant already in the sentence. Expanding with two constants covers all interpretations with UDs of one or two members.
Expansion tool
Semantics for PLE
The identity predicate always has the same extension: every pair <u, u> for u in the UD. So a = b is true exactly when a and b name the same member.
An n-place functor is assigned an n-place function defined on the whole UD, with values in the UD. A complex term like f(a) denotes the value of f's function at a's referent.
Why identity is "logical"
Because its interpretation is fixed, sentences like (∀x)x = x and (a = b & Fa) ⊃ Fb are quantificationally true, which no ordinary two-place predicate could make them.
Interpretation builder
Type sentences of PL or PLE, one per line. Choose a UD size and set each extension; the truth-value of every sentence updates as you go.
Truth-values on this interpretation
Model and counterexample finder
Searches every interpretation with a UD of 1, 2 or 3 members. Finding one settles the question. Finding none doesn't prove the opposite: a model might need a bigger or infinite UD, so use a tree or a derivation for that.
Practice sets for Chapter 8
Discussion questions
- Why does the book require a nonempty UD? Which sentences would change status if the UD could be empty?
- Why do open formulas need satisfaction rather than truth?
- Find a sentence that is true on every interpretation with a UD of one or two members but isn't quantificationally true.
- Church proved there's no decision procedure for PL. What does that mean for the model finder above?
- When does a truth-functional expansion with two constants tell you something about all interpretations?
Questions for our session
Saved in this browser only.