Agler (7.1) Symbolic Logic: Syntax, Semantics, and Proof, "Four New Decomposition Rules", 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.7: Predicate Logic Trees

7.1 Four New Decomposition Rules

 

 

 

Brief summary:

We can decompose quantified propositions of the language of predicate logic (RL) into logic trees, by using additional rules.

Negated Existential Decomposition (¬∃D)	Negated Universal Decomposition (¬∀D)
¬(∃x)P✔ (∀x)¬P	¬(∀x)P✔ (∃x)¬P

(Agler 285)

[Note that when the negation is moved, if there is a quantifier to the right, the negation is moved to the quantifier rather than jumping over to the proposition further to the right. So ¬(∃x)(∀y)Pxy becomes (∀x)¬(∀y)Pxy and not (∀x)(∀y)¬Pxy.]

 

Existential Decomposition (∃D)	Universal Decomposition (∀D)
(∃x)P✔ P(a/x)   where ‘a’ is an individual constant (name) that does not previously occur in the branch.	(∀x)P P(a/x)   where ‘a’ is any individual constant (name).

(Agler 285)

 

[Note that the universal quantifier is not checked, because for infinite domains, not all possible substitutions can be given in the tree.] The universal decomposition is further specified as:

 

Universal Decomposition (∀D)

(∀x)P P(a . . . v/x) Consistently replace every bound x with any individual constant (name) of your choosing (even if it already occurs in an open branch) under any (not necessarily both) open branch of your choosing.

(Agler 286)

 

 

 

Summary

 

Ch.7: Predicate Logic Trees

 

We will examine a truth-tree method for the language of predicate logic (RL). Unlike the system of the language of propositional logic (PL), the system of RL is undecidable. This means that “there is no decision procedure like truth tables or trees that always produces a yes or no answer about whether a given proposition, set of propositions, or argument has a logical property” (Agler 283). However, the truth-tree method for RL will still give a “partial decision procedure”, because “it will give an answer for a number of propositions, sets of propositions, and arguments” (283).

 

 

 

7.1 Four New Decomposition Rules

 

Agler has us recall from PL the nine decomposable proposition types (Agler 283).

 

 

And we saw how we could conduct the decompositions using the rules for constructing truth trees in PL.

 

(Agler 284)

 

In RL, we add four kinds of decomposable propositions.

 

Four Decomposable Proposition Types

Existential                   (∃x)P

Universal                    (∀x)P

Negated existential      ¬(∃x)P

Negated universal        ¬(∀x)P

(Agler 284)

 

There is a decomposition rule for each one of these proposition types. Agler begins with the rules for the negated types.

 

Negated Existential Decomposition (¬∃D)	Negated Universal Decomposition (¬∀D)
¬(∃x)P✔ (∀x)¬P	¬(∀x)P✔ (∃x)¬P

(Agler 285)

 

To illustrate, Agler has us consider the truth tree for the following propositions.

 

1	¬(∃x)Px	P
2	¬(∀y)Wy	P

 

Next we decompose the first line.

 

1	¬(∃x)Px✔	P
2	¬(∀y)Wy	P
3	(∀x)¬Px	1¬∃D

 

And then we decompose the second line.

 

1	¬(∃x)Px✔	P
2	¬(∀y)Wy✔	P
3	(∀x)¬Px	1¬∃D
4	(∃y)¬Wy	2¬∀D

(Agler 285)

 

In the above example, Agler has us observe that “negated quantified expressions fully decompose” (285). [By this I think he means that they are completely transformed from existential to universal quantification or vice versa, and therefore they are not just partially decomposed into a formula of the same quantification.]

 

Agler gives another example.

 

1	¬(∃x)(∀y)Pxy	P
2	¬(∀y)Wy∧(∃z)Pz	P

 

Let us start by decomposing the first line. [We might be tempted to decompose it like this:

 

1	¬(∃x)(∀y)Pxy✔	P
2	¬(∀y)Wy∧(∃z)Pz	P
3	???(∀x)(∀y)¬Pxy???	1¬∃D

 

] Agler says this is not how it should be decomposed. The negation does not move all the way to the proposition, as we might think. Rather, it goes once to the right to the universal quantifier.

 

1	¬(∃x)(∀y)Pxy✔	P
2	¬(∀y)Wy∧(∃z)Pz	P
3	(∀x)¬(∀y)Pxy	1¬∃D

 

For the next step, to decompose line 2, we might be tempted to decompose each conjunct independently, like:

 

1	¬(∃x)(∀y)Pxy✔	P
2	¬(∀y)Wy∧(∃z)Pz✔	P
3	(∀x)¬(∀y)Pxy	1¬∃D
4	???(∃y)¬Wy∧(∃z)Pz???	??2¬∀D??
5	???(∃y)¬Wy???	??4∧D??
6	???(∃z)Pz???	??4∧D??

 

[I am not sure why yet, but] this is the wrong way to do it. Instead, we need to do the conjunction decomposition before the quantification decompositions: “notice that since line 2 is a conjunction, (∧D) is applied to line 2, and then (¬∀D) is applied to ‘¬(∀y)Wy’ ” (Agler 285). [I wonder if it is because the original conjunction of line 2 is to be considered one whole unit that needs to be broken into simple formulas before quantification decomposition.  But I am just guessing.] So instead the decomposition should look like this:

 

1	¬(∃x)(∀y)Pxy✔	P
2	¬(∀y)Wy∧(∃z)Pz✔	P
3	(∀x)¬(∀y)Pxy	1¬∃D
4	¬(∀y)Wy✔	2∧D
5	(∃z)Pz	2∧D
6	(∃y)¬Wy	4¬∀D

(Agler 285)

 

[Also at this point I am not sure yet why for line 3 we do not use

(¬∀D) on line 3 to get (∀x)(∃y)¬Pxy]

 

Agler then gives the two rules for the decomposition of [unnegated] quantified expressions:

 

Existential Decomposition (∃D)	Universal Decomposition (∀D)
(∃x)P✔ P(a/x)   where ‘a’ is an individual constant (name) that does not previously occur in the branch.	(∀x)P P(a/x)   where ‘a’ is any individual constant (name).

(Agler 285)

 

[Recall from section 6.3.1 the distinction between bound and free variables. A variable is bound if it falls under the scope of a quantifier that is quantifying specifically for that particular variable, and it is a free variable otherwise.] [As we see in the above formulations, the decomposition results in: P(a/x). We do not actually write this or something like. Rather it indicates a procedure. We substitute some constant in the domain in for the variable. The basic reasoning for why this works for universal quantification seems obvious. If the predicate holds for every object in the domain, than we can select any arbitrary object and note that the predicate holds for it. It is less obvious to me how this works for existential quantification. Of course it would not make sense that we can pick any arbitrary constant, because we are not saying that that property holds for any given one. It holds for one or some, and not (necessarily) to all. There is the stipulation, “where ‘a’ is an individual constant (name) that does not previously occur in the branch.” I am still not sure how this stipulation protects us from selecting an object to which the predicate does not apply, but perhaps that later will become apparent.]

According to (∃D) and (∀D), an individual constant (name) is substituted for a bound variable in a quantified expression. This procedure is symbolized as ‘P(a/x)’ (i.e., replace x with ‘a’). Thus, if there is a quantified expression of the form ‘(∀x)P’ or ‘(∃x)P,’ a substitution instance of ‘P(a/x)’ replaces x’s bound by the quantifier with ‘a.’

(Agler 286)

 

To further elaborate on these decomposition rules, Agler begins by stating ∀D more explicitly.

 

Universal Decomposition (∀D)

(∀x)P P(a . . . v/x) Consistently replace every bound x with any individual constant (name) of your choosing (even if it already occurs in an open branch) under any (not necessarily both) open branch of your choosing.

(Agler 286)

 

[Previously the formulation only had P(a/x) but now has P(a . . . v/x). The emphasis now seems to be on the fact that any and every constant in the domain can be substituted.]

The motivation behind this formulation of universal decomposition is that if ‘(∀x)P’ is true, then every substitution instance for ‘P(a/x)’ is true. That is, if Everything is a monkey, then every substitution instance ‘P(a/x),’ ‘P(b/x),’ ‘P(c/x)’ in the domain is true.

(Agler 286)

Agler explains that in finite domains, we can conceivably “go through every object in the domain” to check if “it has the property ‘P’” when decomposing universally quantified propositions (286). However, in infinite domains, however, we cannot decompose a universally quantified proposition ‘(∀x)P’ in a finite number of steps by writing out various substitution instances—that is, ‘P(a/x),’ ‘P(b/x),’‘P(c/x),’and so on. It thus never receives a checkmark (✔) to indicate that it has been fully decomposed (see above)” (286). [One part of this explanation that confuses me a little is the idea that in finite domains, we can go through the domain to check if the objects have the property P. I would think that this would be for when we have conditional statements, all zombies are hungry. Here we would need to check if any members of the domain are in fact zombies. But for simple statements like (∀x)Px, I wonder if you need to do any checking, because I would think in this case any members would already have that property. But perhaps I misunderstand.]

 

Agler then notes two important features of (∀D). {1} “a universally quantified proposition ‘(∀x)P’ is partially decomposed by writing any substitution instance ‘P(a/x)’ on one or more open branches that ‘(∀x)P’ contains” (286). He has us consider these formulas.

 

1	(∀x)(Px→Rx)	P
2	Pa∨Ra	P

 

The first thing we do is decompose line 2 using disjunction decomposition.

 

1	(∀x)(Px→Rx)	P
2	Pa∨Ra✔	P
3	/               \ Pa              Ra	2∨D

(Agler 286)

 

We then partially decompose line 1 by substituting in it all instances of x with the constant ‘a’, but we can do so just under one branch. [I am not sure yet, but the point here seems to be that there may not be an absolutely thorough way to decompose the universal quantifications. Perhaps this is because there might be too many, and decomposing all of them may not make any difference in making determinations about the propositions.]

 

1	(∀x)(Px→Rx)	P
2	Pa∨Ra✔	P
3	/               \ Pa              Ra	2∨D
4	Pa→Ra	1∀D

(Agler 287)

 

Or instead, just the right branch can take the decomposition.

 

1	(∀x)(Px→Rx)	P
2	Pa∨Ra✔	P
3	/               \ Pa              Ra	2∨D
4	Pa→Ra	1∀D

(Agler 287)

 

Or, alternately, it can be decomposed under both branches.

 

 

1	(∀x)(Px→Rx)	P
2	Pa∨Ra✔	P
3	/               \ Pa              Ra	2∨D
4	Pa→Ra         Pa→Ra	1∀D

(Agler 287)

 

[Agler’s next point seems to be that instead of ‘a’, we can choose any other object in the domain, and in fact, we can choose a different one for each branch, so long, it seems, that we consistently make the same substitution for each branch.]

In addition, it is important to keep in mind that when we decompose ‘(∀x) (Px→Rx),’ we can write any substitution instance ‘P(a/x)’ under any branch that ‘(∀x)(Px→Rx)’ contains (provided the substitution is done consistently). In other words, rather than making use of the variable replacement ‘P(a/x),’ we could have used ‘P(b/x),’ ‘P(c/x),’ and so on.

(Agler 287)

Agler gives the following example.

 

1	(∀x)(Px→Rx)	P
2	Pa∨Ra✔	P
3	/               \ Pa              Ra	2∨D
4	Pb→Rb         Pc→Rc	1∀D

(Agler 287)

 

“In the left branch on line 4, ‘(∀x)(Px→Rx)’ is decomposed using ‘P(b/x),’ while on the right branch ‘(∀x)(Px→Rx)’ is decomposed using ‘P(c/x)’ (Agler 288). We also note that line one is not checked off, because when our domain is infinite, we can never fully decompose universally quantified propositions. Thus our example sentences could be endlessly decomposed.

 

1	(∀x)(Px→Rx)	P
2	Pa∨Ra✔	P
3	/               \ Pa              Ra	2∨D
4	Pa→Ra	1∀D
5	Pb→Rb	1∀D
6	Pc→Rc	1∀D
7	Pd→Rd	1∀D
8	.	1∀D
	.	1∀D
	.	1∀D

(Agler 288)

 

Agler then takes a closer look at existential decomposition, which was formulated:

Existential Decomposition (∃D)

(∃x)P✔ P(a/x)   where ‘a’ is an individual constant (name) that does not previously occur in the branch.

(Agler 289)

 

Agler explains:

The decomposition of an existential proposition ‘(∃x)P’ involves removing the quantifier and then replacing the bound variable with an individual constant that does not previously occur in the branch. The motivation behind this formulation is that if ‘(∃x)P’ is true, then there is at least one thing in the domain of discourse that has the property picked out by ‘P.’

(Agler 289)

Agler further explains the motivation for this rule. If at least one thing in the domain takes the predicate P, then we should be able to specify it. However, we do not know which object takes that predicate. This is why we can only pick one that has not appeared on that branch yet. The reasoning for this might not be clear, but Agler says he will return to the issue later (289).

 

He illustrates existential decomposition with these propositions:

(∃x)Px, Pa

(Agler 289).

 

So let us first set up the tree.

 

1	(∃x)Px	P
2	Pa	P

 

[There is no ‘b’ yet along this singular branch, so we can use it in our decomposition.]

 

1	(∃x)Px✔	P
2	Pa	P
3	Pb	1∃D

 

Agler next has us consider this set of propositions:

{(∃y)(Py→Ry), (∃x)Px∨(∃z)(Qz),Pa}

(Agler 289)

 

We begin by setting them up.

 

 

1	(∃y)(Py→Ry)	P
2	(∃x)Px∨(∃z)Qz	P
3	Pa	P

 

Let us first decompose the line 1. We cannot use ‘a’ since it was already used in line 3.

 

1	(∃y)(Py→Ry)✔	P
2	(∃x)Px∨(∃z)Qz	P
3	Pa	P
4	Pb→Rb	1∃D

(Agler 289)

 

Now we should continue to decompose line 4.

 

1	(∃y)(Py→Ry)✔	P
2	(∃x)Px∨(∃z)Qz	P
3	Pa	P
4	Pb→Rb✔ /                    \ /                          \	1∃D
5	¬Pb                                 Rb	4→D

(Agler 289)

 

Next we can decompose each branch. All that is left is line 2, which is a disjunction. So before we deal with the quantifications, we should first decompose the larger structure.

 

1	(∃y)(Py→Ry)✔	P
2	(∃x)Px∨(∃z)Qz✔	P
3	Pa	P
4	Pb→Rb✔ /                    \ /                        \	1∃D
5	¬Pb                              Rb /       \                          /      \	4→D
6	(∃x)Px    (∃z)Qz    (∃x)Px   (∃z)Qz	2∨D

 

Next we decompose each of these in line 6.

 

1	(∃y)(Py→Ry)✔	P
2	(∃x)Px∨(∃z)Qz✔	P
3	Pa	P
4	Pb→Rb✔ /                    \ /                        \	1∃D
5	¬Pb                              Rb /       \                          /      \	4→D
6	(∃x)Px✔ (∃z)Qz✔ (∃x)Px✔ (∃z)Qz✔	2∨D
7	Pc               Qd               Pd               Qm        0                 0                  0                   0	6∃D

(Agler 290)

 

Since we used existential decomposition, we note the branches as closed. Also, we could have used the same constant for all four cases in line 7.

 

Agler will now explain why with existential decomposition, we must always use a constant that is not found on that same branch. He has us consider the following propositions and the following incorrect way to decompose their tree.

 

{(∃x)(Px), (∃x)(Qx)}

 

1	(∃x)Px	P
2	(∃x)Qx	P
3	Pa	P
4	Qa	2∃D—NO!

(Agler 290)

 

We cannot do this, because the two propositions were given separately. So they are not implying that the same object necessarily takes both predicates.

These two propositions do not say that some one object is both ‘P’ and ‘Q.’ That is, the condition under which ‘(∃x)Px’ and ‘(∃x)Qx’ are true is not the same as the condition under which ‘(∃x)(Px∧Qx)’ is true. The truth conditions of ‘(∃x)Px’ are represented by selecting some unique and arbitrary individual ‘a’ in the universe of discourse, and the truth conditions of ‘(∃x)Qx’ are represented by selecting some unique and arbitrary individual ‘b’ in the universe of discourse.

(Agler 290)

 

Below is one correct way to decompose the formulas.

 

1	(∃x)Px	P
2	(∃x)Qx	P
3	Pa	P
4	Qb	2∃D

(Agler 290-291

 

So we can see then why we must follow this rule that for existential decomposition, we cannot use an object that is already found in the branch. “In order to protect against the unwarranted assumption that each proposition is referring to the same object, the use of (∃D) is restricted by only allowing for substitution instances of individual constants (names) that do not previously occur in the branch” (291). [I am still a little confused by this procedure, even with this restriction. I would think that it is still possible that we assign an object to a predicate when that object should not get that predicate. So how do we know that ‘b’ is Q? Is it Q because ‘b’ was not assigned to any other predicate?  I do not see the connection yet. (Could it not for example be that ‘b’ is a tortoise, and Q is quick?) Perhaps the idea is that for the purposes of the decomposition, it will not matter if we wrongly assign the constants, since for example we are looking for other structural problems not related to the correctness of the attributions.]

 

 

 

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

 

 

Some changes to the book quotations may have been made, as based on: http://markdfisher.com/wp-content/uploads/2014/02/PHIL_012_ONLINE_SYLLABUS_SP14-3-1.pdf .

 

.