Predicate Logic: Syntax and Symbolization

Atomic sentences of SL are independent of one another, so SL can't see that "Sarah supports Breitlow" and "Breitlow is a Republican" together mean Sarah supports a Republican. Nor can it show that "Each citizen will vote or will not vote" is a logical truth about each citizen.

Singular terms

A singular term designates, or purports to designate, one thing: a proper name ("Marie Curie"), a definite description ("the discoverer of radium"), or a pronoun standing in for one of those.

Predicates

Remove the singular terms from a sentence and you're left with a predicate. "Sarah supports Breitlow" yields the two-place predicate "x supports y". The number of gaps is the predicate's number of places.

Quantity expressions

"All", "some", "none", "each" don't name anything. They say how many things satisfy a predicate, and PL's quantifiers capture them.

Officially an n-place predicate carries n primes (F′, B″); informally they're dropped when the terms make the number of places clear. An atomic formula is a sentence letter, or an n-place predicate followed by n individual terms.

Recursive definition of "formula of PL"

1. Every atomic formula is a formula.
2. If P is a formula, so is ~ P.
3. If P and Q are formulas, so are (P & Q), (P ∨ Q), (P ⊃ Q), (P ≡ Q).
4. If P contains at least one occurrence of x and no x-quantifier, then (∀x)P and (∃x)P are formulas.
5. Nothing else is a formula.

Scope, free and bound

The scope of a quantifier is the quantifier plus the subformula right after it. An occurrence of x is bound if it lies in the scope of an x-quantifier, otherwise free. A sentence of PL is a formula with no free variables.

Careful with dropped outer brackets: (∀x)(Fx ⊃ Ga) is quantified, but (∀x)Fx ⊃ Ga is a conditional whose antecedent is quantified.

Substitution instances

P(a/x) is P with a in place of x. If P is (∀x)Q or (∃x)Q, then Q(a/x) is a substitution instance of P, and a is the instantiating constant: Fab is an instance of (∃z)Fzb.

A symbolization key fixes a universe of discourse (UD), what each predicate means, and what each constant names. The UD matters: with UD the set of people, "everyone is happy" is just (∀x)Hx; with a wider UD you need (∀x)(Px ⊃ Hx).

Variables range over the whole UD. The existential quantifier means "at least one". Translate in stages: first a quasi-English paraphrase with variables ("each x is such that if x is a dog then x barks"), then the formula.

The pairing rule

Universal claims pair with ⊃; existential claims pair with &. (∀x)(Dx & Bx) says everything is a barking dog. (∃x)(Dx ⊃ Bx) is true as soon as anything in the UD isn't a dog.

Overlapping quantifiers

With two-place predicates, quantifier order changes the meaning. "Everyone loves someone" is (∀x)(∃y)Lxy; "someone is loved by everyone" is (∃y)(∀x)Lxy. The second entails the first, not the other way round.

Tricky English

• "Only Fs are G": (∀x)(Gx ⊃ Fx), the arrow pointing the other way.
• "Any" often works like "every", but "if anything is broken, Sam will fix it" is (∀x)(Bx ⊃ Fsx) while "if everything is broken, Sam will quit" is (∀x)Bx ⊃ Qs.
• Relative clauses become conjunctions inside the scope: "every gorilla that likes a rhinoceros…" puts Gx & (∃y)(Ry & Lxy) in the antecedent.
• Pronouns that cross-refer to a quantified phrase become the same bound variable.

PLE adds two things to PL. The identity predicate, always interpreted as identity and written informally a = b (negated: ~ a = b). And functors, which name functions: if f(x) is "the successor of x", then f(a) is a complex term, and (∀x)(Ex ⊃ Of(x)) says the successor of an even number is odd.

Identity lets PLE count. Different variables don't mean different things, so "at least two" needs an explicit ~ x = y. It also handles "everyone else", "only", superlatives, and definite descriptions ("the F is G": exactly one thing is F, and it is G).