Agler (6.3) Symbolic Logic: Syntax, Semantics, and Proof, "The Syntax of RL", summary

 

by Corry Shores

[Search Blog Here. Index-tags are found on the bottom of the left column.]

 

[Central Entry Directory]

[Logic & Semantics, Entry Directory]

[David Agler, entry directory]

[Agler’s Symbolic Logic, entry directory]

 

[The following is summary. Boldface (except for metavariables) and bracketed commentary are my own. Please forgive my typos, as proofreading is incomplete. I highly recommend Agler’s excellent book. It is one of the best introductions to logic I have come across.]

 

 

 

Summary of

 

David W. Agler

 

Symbolic Logic: Syntax, Semantics, and Proof

 

Ch.6: Predicate Language, Syntax, and Semantics

6.3 The Syntax of RL

 

 

 

Brief summary:

In the language of predicate logic (RL), variables are either bound or free. They are bound if they fall under the scope of a quantifier that is quantifying specifically for that particular variable, and it is a free variable otherwise. An open sentence or an open formula is one with an n-place predicate P followed by n terms, where at least one of those variables is free. However, a closed sentence or a closed formula is one with an n-place predicate P followed by n terms, where none of those terms are free variables. The main operator in a well formed formula (wff) in RL is the one with the greatest scope, which means that the one that falls under no other operator’s scope is the main one. We consider the quantifiers as operators. Thus in (∃x)(Px∧Qx) the main operator is ∃x, because all the rest of the formula falls under the quantifier’s scope, and in ¬(∃x)(Px∧Qx) the main operator is the negation, because the quantifier falls under its scope, and the rest of the formula falls under the quantifier’s scope. And there are five rules that determine a wff in RL:  (i) An n-place predicate ‘P’ followed by n terms (names or variables) is a wff. (ii) If ‘P’ is a wff in RL, then ‘¬P’ is a wff. (iii) If ‘P’ and ‘Q’ are wffs in RL, then ‘P∧Q,’ ‘P∨Q,’ ‘P→Q,’ and ‘P↔Q’ are wffs. (iv) If ‘P’ is a wff in RL containing a name ‘a,’ and if ‘P(x/a)’ is what results from substituting the variable x for every occurrence of ‘a’ in ‘P,’ then ‘(∀x)P(x/a)’ and ‘(∃x)P(x/a)’ are wffs, provided ‘P(x/a)’ is not a wff. (v) Nothing else is a wff in RL except that which can be formed by repeated applications of (i) to (iv).

 

 

 

 

Summary

 

6.3 The Language of RL

 

Agler will now explain the syntax of the language of predicate logic, or RL (for relational logic). To do this, we will look at the difference between free and bound variables, then we learn how to find the main operator of wffs, and lastly we examine the formal syntax of RL (Agler 256).

 

 

6.3.1 Free and Bound Variables

 

[Recall from the prior section 6.2.3 the notion of scope: Quantifiers have a scope in the formulation over which they apply. They operate just over the propositional contents to the immediate right of the quantifier or just over the complex propositional contents to the right of the parentheses.] With regard to the notion of a quantifier’s scope, Agler now clarifies that parentheses are not needed if they do nothing to remove ambiguity in the situation. Consider first the formula:

(1) (∀x)(Fx→Bx)∨Wx

(Agler 256)

[Here the parentheses are needed, because we need to make it clear that Wx does not fall under the scope of the quantifier. Were the parentheses omitted, this would be ambiguous.] Agler then has us consider:

(2) (∃x)Mx∧(∃y)Ry

(Agler 256)

Here each term is just under the scope of the quantifier that immediately precedes it. And he also has us consider:

(3) (∀y)(Mx∧By)

(Agler 256)

Here both Mx and By are under the quantifier’s scope [although I do not know yet what it would mean for Mx to be under the scope of a quantifier for the variable y. In other words, I do not know what makes the above formula different than Mx∧(∀y)By.] Agler now clarifies the distinction between bound and free variables. Variables are bound if they fall under the scope of a quantifier that is quantifying specifically for that particular variable, and it us a free variable otherwise.

Bound variable: When a variable is within the scope of a quantifier that quantifies that specific variable, then the variable is a bound variable.

Free variable: A free variable is a variable that is not a bound variable.

(Agler 256)

So recall

(3) (∀y)(Mx∧By)

We noted that Mx falls under the scope of ∀y. But ∀y does not quantify for x. Therefore, x in Mx is a free variable (Agler 257).

 

If a variable is bound when it falls under the scope of a quantifier that quantifiers for that variable, then we can also define a variable as free if it satisfies at least one of the following conditions:

(1) when it is not contained in the scope of any quantifier,

or

(2) when it is in the scope of a quantifier, but the quantifier does not specifically quantify for that specific variable.

(Agler 257)

Agler illustrates with this example:

(6) [(∀x)(Px→Gy)∧(∃z)(Pxy∧Wz)]∨Rz

(Agler 257)

First consider the part:

(∀x)(Px→Gy)

Here, the x of Px is bound, because it falls under the scope of ∀x. But since ∀x does not quantify for y, that means the y of Gy is free. Now what about the part:

(∃z)(Pxy∧Wz)

Here, only the z of Wz is bound. And what about the z in Rz? It falls within the scope of no quantifier, and thus is free (Agler 257)

 

 

6.3.2 Main Operator in Predicate Wffs

 

The main operator in a wff in RL is the one with the greatest scope [and that means the operator that falls under the scope of no other operator would be the main operator]. [Recall the discussion of main operators in section 2.2.3.] Agler then gives four example wffs in RL, each having a different main operator, despite their structural similarities.

(1) (∃x)(Px∧Qx)

You might think the main operator is the conjunction. However, it does not have the greatest scope. The existential quantifier does. So the main operator is actually ∃x. What about

(2) (∃x)(Px)∧(∃x)(Qx)

Given what we just said about sentence 1, we might here propose that there are two equally main operators, namely, the two instances of ∃x. However, what about the conjunction operator? Does it fall under the scope of any other operator? It does not. Rather, it operates on its two conjuncts. Thus it is the main operator in sentence 2. Now what about:

(3) ¬(∃x)(Px∧Qx)

(Agler 257)

Can the main operator be the conjunction operator? No, because it falls under the scope of ∃x. But then would the main operator be the existential quantifier? No, because it falls under the negation operator. Thus the negation operator is the main operator in sentence 3 (Agler 258). Now consider the last example:

(4) (∀y)(∃x)(Rx→Py)

(Agler 257)

[We know it is probably not the conditional operator, because it falls under the scope of the existential quantifier. We might think that in a series of quantifiers, like in sentence 4, all of the quantifiers should be taken as independent of one another. But for some reason, the quantifiers on the left quantify over the ones to the right. I do not know yet what that means, however, as I do not know how inverting the order of the quantifiers would change its meaning or logical properties. We perhaps learn later about this.]

 

Agler then provides a table with a variety of other examples to help us understand how to find main operators.

Wff ........................................... Its Main Operator

(∀x)Px ..................................... ∀x
(∀x)(Px) ................................... ∀x
¬(∀x)(Px) ................................. ¬
¬(∃y)(Py) .................................. ¬
(∀x)(Px→Qx) ............................ ∀x
¬(∀x)(Px→Qx) .......................... ¬
(∀x)(Px→¬Qx) .......................... ∀x
(∀x)(Px)→(∃x)(Qx) ................... →
¬(∀x)(Px)→(∃x)(Qx) ................. →
¬[(∀x)(Px)→(∃x)(Qx)] ............... ¬
(∃x)(Px∧Qx)∧¬(∀y)(Py→Qy) .... ∧
(∃x)¬(Px∧Qx) ............................ ∃x
(∃x)(∀y)[(Px∧Qx)→Dy] ............. ∃x
(∀x)¬(∀y)(Px→Qy) ................... ∀x
¬(∀x)(∀y)(Px→Qy) .................... ¬

(Agler 285)

 

 

6.3.3 The Formal Syntax of RL: Formation Rules

 

If a proposition in RL is well formed, then it is syntactically correct. The formation rules determining all grammatical ways to formulate propositions in RL is the following:

(i) An n-place predicate ‘P’ followed by n terms (names or variables) is a wff.

(ii) If ‘P’ is a wff in RL, then ‘¬P’ is a wff.

(iii) If ‘P’ and ‘Q’ are wffs in RL, then ‘P∧Q,’ ‘P∨Q,’ ‘P→Q,’ and ‘P↔Q’ are wffs.

(iv) If ‘P’ is a wff in RL containing a name ‘a,’ and if ‘P(x/a)’ is what results from substituting the variable x for every occurrence of ‘a’ in ‘P,’ then ‘(∀x)P(x/a)’ and ‘(∃x)P(x/a)’ are wffs, provided ‘P(x/a)’ is not a wff.

(v) Nothing else is a wff in RL except that which can be formed by repeated applications of (i) to (iv).

(Agler 258)

 

Agler will look at each rule individually. We begin with the first:

(i) An n-place predicate ‘P’ followed by n terms (names or variables) is a wff.

This means that if P is a three-place predicate, then either Pabc (which uses names) and Pxyz (which uses variables) are both wffs. But if P is a three-place predicate, then Pab and Pxy would not be wffs (Agler 259). Agler next will distinguish formulas that have at least one free variables and ones containing only names in the following way. An open sentence or an open formula is one with an n-place predicate P followed by n terms, where at least one of those variables is free. However, a closed sentence or a closed formula is one with an n-place predicate P followed by n terms, where none of those terms are free variables (Agler 259).

Open formula: An open formula is a wff consisting of an n-place predicate ‘P’ followed by n terms, where one of those terms is a free variable.

Closed formula: A closed formula is a wff consisting of an n-place predicate ‘P’ followed by n terms, where every term is either a name or a bound variable.

(259)

 

Now let us look again at ii.

(ii) If ‘P’ is a wff in RL, then ‘¬P’ is a wff.

Agler says that this means that “if ‘Pa,’ ‘¬Qab,’ and ‘(∀x)Px’ are all wffs, then ‘¬Pa,’ ‘¬¬Qab,’ and ‘¬(∀x)Px’ are also wffs” (Agler 259). Recall iii.

(iii) If ‘P’ and ‘Q’ are wffs in RL, then ‘P∧Q,’ ‘P∨Q,’ ‘P→Q,’ and ‘P↔Q’ are wffs.

Agler explans that “if ‘Pa,’ ‘¬Qab,’ and ‘(∀x)Px’ are all wffs, then ‘Pa∧¬Qab,’ ‘¬Qab∨(∀x)Px,’ ‘Pa→(∀x) Px,’ and ‘¬Qab↔Pa’ are wffs (as are many others)” (Agler 259).

 

Agler says that iv is the most complicated of the rules. He begins first by examining its antecedent [I will call it ‘a’ and the second part ‘b’]:

(iv.a) If ‘P’ is a wff in RL containing a name ‘a,’ and if ‘P(x/a)’ is what results from substituting the variable x for every occurrence of ‘a’ in ‘P’ ...

(Agler 259)

To help us understand the symbolization here, Agler will give us an example. So consider this wff:

(1) Pb

(Agler 259)

Now we will think of substituting the variable x for every instance of b in Pb [in this case there is just one instance of b]. We would write that substitution situation as

P(x/b)

It means that we turn Pb into Px. So consider

(2) Pbb

And suppose we turn that into Pzz. This means we have the substitution situation that can be written as P(z/b).

 

But, Agler adds, making such a substitution is so far not enough to create a wff. Let us not forget the consequent clause of iv:

(iv.b) ... then ‘(∀x)P(x/a)’ and ‘(∃x)P(x/a)’ are wffs, provided ‘P(x/a)’ is not a wff.

(Agler 260)

[At this point, I am not sure why, in our example, Px or Pzz would not be wffs. For, according to rule i, they would seem to be, as they are n-place predicates with n variables coming after them. It seems that because a variable was substituted, that thereby necessitates a quantifier, but I am not sure why. I might guess that by substituting, we are somehow treating the variable that replaces the name as being bound and thus needing a quantifier that would bind it. I wonder if it makes sense to think about the situation as if we began from the other direction. So suppose we were to substitute a name in for a variable. Perhaps this can only be done if the variable is bound. But why might it be impossible to substitute a name in for an unbound variable? Recall the example from before: (∀y)(Mx∧By). Is there some reason why we cannot substitute a name in for the x of Mx? I do not know. Does it have something to do with the fact that by not quantifying the variable, we have not determined what can be substituted in for it? At any rate, the main idea is that (for some reason) we need to add a quantifier to the variable-substituted predicate to make it a wff. Let me quote.]

The consequent of (iv) says that by putting a universal quantifier or existential quantifier in front of the formula that is the result of substituting a variable x for every name ‘a,’ the resulting formula is a wff. For example, using (1) from above, note that ‘Pb’ is a wff and contains a name ‘b.’ Second, take ‘P(x/b),’ which is the formula that results from substituting the variable x for every occurrence of ‘b’ in ‘Pb.’ This gives us ‘Px.’ The consequent clause of (iv) says that both of the following will be wffs:

(∀x)Px

(∃x)Px

(Agler 260)

 

Finally, recall v:

(v) Nothing else is a wff in RL except that which can be formed by repeated applications of (i) to (iv).

The purpose of this rule is to ensure “that the only wffs allowed into RL are those that are the result of using (i) to (iv)” (Agler 260).

 

Agler then illustrates the rules with some examples where he will state the specific rules that qualify the example formulas as wffs. So consider:

(3) Pab∧Ra
(260)

We first suppose that all the predicates in these examples are one-place, except for Pxy, which is two place. So rule i tells us that Pab and Ra [the two conjuncts above] are wffs. Then we note rule iii which says their conjunction makes them a wff too (260).

Now, why is

(4) ¬Qa→(∀x)Rx

a wff? Rule i tells us that ¬Qa is a wff. [I am not sure why we are not invoking rule ii, which is for negations.] Now look at Rx. [Agler will say that we use rule iv to establish this as a wff. I am not exactly sure why we do not use rule 1, which also holds for predicates taking a variable. For some reason we need to suppose that we begin with Ra, but I am not sure why. It might be because formula 3 has Ra.] Rule iv tells us that if Ra is a wff and furthermore if R(x/a) results when we substitute x for any occurrence of a, then (∀x)Rx is a wff. We can establish that Ra is a wff on the basis of rule i. Thus we can infer that (∀x)Rx is a wff. We can then bring the two parts together using rule iii. Here is how Agler works it out:

Agler then uses a similar procedure to show that

(5) (∀x)Pxx→¬(∃y)Gy

is a wff (for the details, see Agler, page 261).

 

 

Agler, David. Symbolic Logic: Syntax, Semantics, and Proof. New York: Rowman & Littlefield, 2013.