Lecture Notes: Section 3.1

Section 3.1: A Formal Language for Predicate Logic

Comment: The language of predicate logic greatly increases our ability to capture the logic of intuitively valid arguments. Consider, for example, the following:

All logicians are fastidious.
Willard is a logician.
Therefore, Willard is fastidious.

Every horse is an animal.
Therefore, every horse's head is the head of some animal.

The best we can do to represent these intuitively valid arguments in sentential logic is to translate them as, say, the sequents $\mathrm{L},\, \mathrm{W}\vdash \mathrm{F}$ and $\mathrm{A}\vdash \mathrm{H}$ .
Both of which are invalid. What's wrong?

The problem: the logically relevant expressions that determine the validity of these arguments are ``invisible'' to the language of sentential logic -- they are parts of sentences that, from the perspective of sentential logic, are logically simple (i.e., they contain no connectives).

Comment: There are three new types of logically relevant classes of expressions we will study in predicate logic: names , like `Willard', predicates, like `is a logician', and the quantifiers `every' (or, equivalently, `all') and `some'. To capture these, we define the vocabulary of predicate logic to include categories of expressions corresponding to the new elements. Specifically:

Definition: The vocabulary of predicate logic consists of:

Sentence letters (as in sentential logic)
Connectives (as in sentential logic)
Names
Variables
Predicate letters
Quantifiers
Parentheses

Definition: A name is a symbol from the following list: $\mathrm{a},\, \mathrm{b},\, \mathrm{c},\, \mathrm{d},\, \mathrm{a}_{1},\, \ma... ...,\, }\mathrm{a}_{2},\, \mathrm{b}_{2},\, \mathrm{c}_{2},\mathrm{d}_{2,\, }...$ Definition: A variable is a symbol from the following list: $\mathrm{u},\, \mathrm{v},\, \mathrm{w},\, \mathrm{x},\, \mathrm{y},\, \mathrm... ...},\, \mathrm{y}_{1},\, \mathrm{z}_{1},\, \mathrm{u}_{2},\, \mathrm{v}_{2},...$ Definition: Names and variables collectively are known as terms .

Comment: The Greek letters $\alpha$ , $\beta$ ,and $\gamma$ will be used as metavariables for terms.

Definition: A 1-place predicate letter is a symbol from the following list:

$\mathrm{A}^{1},\, \mathrm{B}^{1},\, ...,\, \mathrm{Z}^{1},\, \mathrm{A}_{1}^{... ...,\, \mathrm{A}^{1}_{2},\, \mathrm{B}^{1}_{2},\, ...,\, \mathrm{Z}^{1}_{2},...$

Definition: A 2-place predicate letter is a symbol from the following list:

$\mathrm{A}^{2},\, \mathrm{B}^{2},\, ...,\, \mathrm{Z}^{2},\, \mathrm{A}_{1}^{... ...,\, \mathrm{A}^{2}_{2},\, \mathrm{B}^{2}_{2},\, ...,\, \mathrm{Z}^{2}_{2},...$ In general:

Definition: An n-place predicate letter is a symbol from the following list:

$\mathrm{A}^{n},\, \mathrm{B}^{n},\, ...,\, \mathrm{Z}^{n},\, \mathrm{A}_{1}^{... ...,\, \mathrm{A}^{n}_{2},\, \mathrm{B}^{n}_{2},\, ...,\, \mathrm{Z}^{n}_{2},...$ Comment: Predicate letters with more than one place are referred to as many-place predicate letters.

Comment: Predicate letters will sometimes be referred to as `predicates' for short. The Greek letter $\pi$ will be used as a metavariable for predicates.

Comment: In practice, superscripts and subscripts can be omitted. Any of the capital letters may appear as sentence letters or predicate letters.

Definition: A universal quantifier is any symbol of the form $\forall \alpha$ , where $\alpha$ is a variable.

Comment: Universal quantifiers are used to represent the English word `every' and its synonyms (`all', `each', etc.).

Definition: An existential quantifier is any symbol of the form $\exists \alpha$ , where $\alpha$ is a variable.

Comment: Existential quantifiers are used to represent the English word `some', in the sense of `at least one'.

Definition: An expression of predicate logic is any sequence of items from the vocabulary of predicate logic.

Examples

$)(\exists \! \rightarrow \! \mathrm{A}_{3}^{17}\&\mathrm{xxx}\forall$

$\exists \mathrm{x}\forall \mathrm{y}(\mathrm{P}^{2}\mathrm{xy}\, \&\, \sim \! \exists \mathrm{zQ}^{3}\mathrm{xzy})$

Comment: It is always possible to tell how a letter is being used in a wff by looking at the number of terms immediately following it. A capital letter with no terms following it is a sentence letter, one followed by one term is a 1-place predicate; in general, a capital letter with n terms following it is an n-place predicate.

Recursive Definition of `Well Formed Formula (wff) of Predicate Logic':

1.: Every sentence letter is a wff (of predicate logic).
2.: If $\pi$ is an n-place predicate and $\alpha _{1}$ ,..., $\alpha _{n}$ are n terms, then $\pi \alpha _{1}...\alpha _{n}$ is a wff.
3.: If $\varphi$ and $\psi$ are wffs, so are $\sim \! \! \! \varphi$ , $(\varphi \, \&\, \psi )$ , $(\varphi \vee \psi )$ , $(\varphi \rightarrow \psi )$ , and $(\varphi \leftrightarrow \psi )$ .
4.: If $\varphi$ is a wff, then $\varphi$ * is the result of replacing at least one occurrence of a name in $\varphi$ by a variable $\alpha$ not occurring in $\varphi$ , then $\forall \alpha \varphi$ * is a wff.
5.: If $\varphi$ is a wff, then $\varphi$ * is the result of replacing at least one occurrence of a name in $\varphi$ by a variable $\alpha$ not occurring in $\varphi$ , then $\exists \alpha \varphi$ * is a wff.
6.: Nothing else is a wff.

Definition: Wffs of the form $\pi \alpha _{1}...\alpha _{n}$ are known as atomic sentences of predicate logic.

Definition: Wffs of the form $\forall \alpha \varphi$ are known as universally quantified , or universal , wffs.

Definition: Wffs of the form $\exists \alpha \varphi$ are known as existentially quantified , or existential , wffs.

Comment: We will continue to use the parenthesis dropping conventions of sentential logic.

Examples (subscripts and superscripts are dropped after the first example)

$\exists \mathrm{x}\forall \mathrm{y}(\mathrm{P}^{2}\mathrm{xy}\, \&\, \sim \! \exists \mathrm{zQ}^{3}\mathrm{xzy})$
$((\mathrm{Fa}\vee \mathrm{Fb})\rightarrow \mathrm{Gab})$
$\exists \mathrm{yFy}$
$\forall \mathrm{x}(\mathrm{Fx}\rightarrow \mathrm{Gx})$
$\forall \mathrm{x}\forall \mathrm{y}(\mathrm{Rxy}\rightarrow \mathrm{Ryx})$
$(\exists \mathrm{xFx}\leftrightarrow \forall \mathrm{xGx})$
$(\exists \mathrm{xFx}\rightarrow \mathrm{P})$
$\forall \mathrm{x}\exists \mathrm{yFyxb}$

Comment: It is often convenient to omit repetitions of $\exists$ and $\forall$ .

Examples

You may abbreviate

$\forall \mathrm{x}\forall \mathrm{y}\forall \mathrm{z}(\mathrm{Fxy}\, \&\, \mathrm{Gyz}\leftrightarrow \mathrm{Hzx})$ as $\forall \mathrm{xyz}(\mathrm{Fxy}\, \&\, \mathrm{Gyz}\leftrightarrow \mathrm{Hzx})$ .

You may abbreviate

$\exists \mathrm{x}\exists \mathrm{y}\forall \mathrm{z}\forall \mathrm{w}(\mathrm{Fxyz}\, \&\, \mathrm{Gwx}\rightarrow \, \sim \! \mathrm{Hzx})$ as $\exists \mathrm{xy}\forall \mathrm{zw}(\mathrm{Fxyz}\, \&\, \mathrm{Gwx}\rightarrow \, \sim \! \mathrm{Hzx})$ .

Definition: An open formula is the result of replacing at least one occurrence of a name in a wff by a new variable (one not already occurring in the wff). Wffs of the form $\exists \alpha \varphi$ are known as existentially quantified , or existential , wffs.

Comment: Open formulas are not wffs, and hence never appear in any line of a proof. Rather, the notion will be used when the rules of proof for predicate logic are defined.

Examples of open formulas

$\mathrm{Fx},\, \mathrm{Gxy},\, \forall \mathrm{xGxy}$

Definition: The scope of a quantifier in a formula $\varphi$ is the shortest open formula occurring to the right of the quantifier.

Examples

In the wff

$\forall \mathrm{xFx}\, \&\, \mathrm{Pa}$

the scope of the quantifier $\forall \mathrm{x}$ is $\mathrm{Fx}$ .

In the wff

$\forall \mathrm{x}(\exists \mathrm{yFxy}\, \&\, \exists \mathrm{z}(\mathrm{Gyz}\leftrightarrow \mathrm{Hzx}))$ the scope of the quantifier $\forall \mathrm{x}$ is $(\exists \mathrm{yFxy}\, \&\, \exists \mathrm{z}(\mathrm{Gyz}\leftrightarrow \mathrm{Hzx}))$ ,that of $\exists \mathrm{y}$ is $\mathrm{Fxy}$ , and that of $\exists \mathrm{z}$ is $(\mathrm{Gyz}\leftrightarrow \mathrm{Hzx})$ .

Definition: An occurrence of a variable $\alpha$ that is in the scope of a quantifier for that variable (i.e., a quantifier of the form $\forall \alpha$ or $\exists \alpha$ ) is said to be bound . An occurrence of a variable $\alpha$ that is not bound is said to be free .

Comment: In a wff, every occurrence of a variable $\alpha$ is bound. In an open formula, at least one occurrence of a variable is free.

Definition: A quantifier whose scope in a wff or open formula $\varphi$ contains another quantifier is said to have wider scope in $\varphi$ than the second quantifier. The second quantifier is said to have narrower scope in $\varphi$ .

Examples

In the wff

$\forall \mathrm{x}(\exists \mathrm{yFxy}\, \&\, \exists \mathrm{z}(\mathrm{Gyz}\leftrightarrow \mathrm{Hzx}))$ the quantifier $\forall \mathrm{x}$ has wider scope in the wff than both $\exists \mathrm{y}$ and $\exists \mathrm{z}$ . Since neither of the existential quantifiers occurs in the scope of the other in this wff, neither has wider (or narrower) scope than the other in the wff.

Definition: A universalization of a sentence with respect to a given name occurring in the sentence is any sentence obtained by the following two steps:

1.: Replace all occurrences of the name in the sentence by a variable $\alpha$ , where $\alpha$ does not already occur in the sentence.
2.: Prefix the quantifier $\forall \alpha$ to the open formula resulting from Step 1.

Examples

Universalisations of the form

$\mathrm{Faa}$ with respect to the name ` $\mathrm{a}$ ' include
$\forall \mathrm{xFxx}$ , $\forall \mathrm{zFzz}$ , and $\forall \mathrm{wFww}$ . Universalisations of the formula
$\mathrm{Pb}\rightarrow \sim \! \exists \mathrm{yQaby}$ with respect to the name ` $\mathrm{b}$ ' include
$\forall \mathrm{x}(\mathrm{Px}\rightarrow \! \sim \! \exists \mathrm{yQaxy})$ and $\forall \mathrm{z}(\mathrm{Pz}\rightarrow \! \sim \! \exists \mathrm{yQazy})$ . Comment: $\forall \mathrm{xFxa}$ and $\forall \mathrm{x}\forall \mathrm{yFxy}$ are not universalizations of $\mathrm{Faa}$ . Why? (See Step 1 in the definition of universalization.)

Exercise: Give an example of a sentence $\varphi$ and a name $\alpha$ such that $\forall \mathrm{xFxa}$ is a universalization of $\varphi$ with respect to $\alpha$ . Do the same for $\forall \mathrm{x}\forall \mathrm{yFxy}$ .

Definition: An existentialization of a sentence with respect to a given name occurring in the sentence is any sentence obtained by the following two steps:

1.: Replace at least one occurrence of the name in the sentence by a variable $\alpha$ , where $\alpha$ does not already occur in the sentence.
2.: Prefix the quantifier $\exists \alpha$ to the open formula resulting from Step 1.

Comment: Note that universalization requires replacing all occurrences of the name in question with the variable $\alpha$ , whereas existentialization only requires replacing at least one occurrence of the name in question with $\alpha$ .

Examples

Existentializations of the formula

$\mathrm{Faa}$ with respect to the name ` $\mathrm{a}$ ' include
$\exists \mathrm{xFxx}$ , $\exists \mathrm{xFxa}$ , and $\exists \mathrm{wFaw}$ . Existentializations of the formula
$\mathrm{Pb}\rightarrow \! \sim \! \exists \mathrm{yQaby}$ with respect to the name ` $\mathrm{b}$ ' include
$\exists \mathrm{x}(\mathrm{Px}\rightarrow \! \sim \! \exists \mathrm{yQaxy})$ , $\exists \mathrm{w}(\mathrm{Pb}\rightarrow \! \sim \! \exists \mathrm{yQawy})$ , and $\exists \mathrm{z}(\mathrm{Pz}\rightarrow \! \sim \! \exists \mathrm{yQaby})$ .

Definition: An instance of a universally or existentially quantified sentence is any sentence obtained by the following two steps:

1.: Remove the initial quantifier.
2.: In the open formula resulting from Step 1, uniformly replace all occurrences of the unbound variable by occurrences of a name.

Comment: This process is called instantiating the sentence. The name that is used is called the instantial name .

Examples

The sentences

$\forall \mathrm{x}(\mathrm{Fx}\rightarrow \mathrm{Gx})$ and $\exists \mathrm{x}(\mathrm{Fx}\rightarrow \mathrm{Gx})$ have instances $\mathrm{Fa}\rightarrow \mathrm{Ga}$ , $\mathrm{Fb}\rightarrow \mathrm{Gb}$ , $\mathrm{Fc}\rightarrow \mathrm{Gc}$ , etc. The sentences $\forall \mathrm{x}\forall \mathrm{y}(\mathrm{Px}\, \&\! \sim \! \exists \mathrm{zQxyz})$ and $\exists \mathrm{x}\forall \mathrm{y}(\mathrm{Px}\, \&\! \sim \! \exists \mathrm{zQxyz})$ has instances $\forall \mathrm{y}(\mathrm{Pa}\, \&\! \sim \! \exists \mathrm{zQayz})$ , $\forall \mathrm{y}(\mathrm{Pb}\, \&\! \sim \! \exists \mathrm{zQbyz})$ ,etc.

About this document ...

http://philebus.tamu.edu/~cmenzel/240/LectureNotes/Sec3.1
Last updated Tue 31 Mar 1998