8.5.2. Derivations for existentials

To implement the laws we have just been considering, we will again use ideas introduced in connection with universals. In particular, a proof by choice will be marked by a veil of ignorance flagged by a parameter, and it will have a supposition that sets out the example chosen. However, the complications that appeared with the rules for exploiting universals may be left with those rules, since we manage planning for an existential conclusion simply by passing the buck on to universals.

The two basic rules for the unrestricted existential are Proof by Choice (PCh) and Non-constructive Proof (NcP):

│⋯ │∃x θx │⋯ ││⋯ ││ ││ ││ ││ ││ ││ │├─ ││φ │...

│⋯ │∃x θx n │⋯ ││⋯ ││ⓐ │││θa ││├─ │││ ││├─ │││φ n │├─ ││φ n PCh │...

Fig. 8.5.2-1. Developing a derivation at stage n by exploiting an unrestricted existential; the parameter a is new to the derivation.

│⋯ ││⋯ ││ ││ ││ ││ ││ │├─ ││∃x θx │...

│⋯ ││⋯ │││∀x θx ││├─ │││ ││├─ │││⊥ n │├─ ││∃x θx n NcP │...

Fig. 8.5.2-2. Developing a derivation at stage n by planning for an unrestricted existential.

Notice that the existential is rendered inactive in the first rule. Also remember that the parameter that is used in this rule should be new to the derivation; that will insure that the supposition that is introduced represents the only information about this parameter that may be used in closing the gap. The second rule will often be a very indirect way of reaching an existential goal, and the following attachment rule, Existential Generalization (EG), will often simplify derivations considerably:

│⋯ │θτ │⋯ ││⋯ ││ ││ │├─ ││φ │... │⋯ │θτ n │⋯ ││⋯ n EG ││∃x θx X ││ │├─ ││φ │...

Fig. 8.5.2-3. Developing a derivation at stage n by adding an unrestricted existential that has an instance among the active resources.

Although this is an attachment rule and therefore not part of the basic system, you should be as ready to use it as the two above.

Here are two derivations that illustrate these rules. Each shows that a claim of uniformly general exemplification implies the corresponding claim of general exemplification without a claim of uniformity. The derivation on the left uses a non-constructive proof of the existential that is set as the goal in stage 2 while the one on the right uses EG to give a constructive proof of this existential. Both derivations begin by exploiting the existential premise, but derivations for the same entailment could have been developed by planning for the initial conclusion first; and, when NcP is used, it would be possible to postpone the exploitation of the initial premise until after NcP is applied. (It would be a good exercise at this point to write down these other derivations for this argument.)

The savings here in length and complexity by using EG are typical of cases where it can be used. Since it can be used only when an existential is entailed by the resources, it will often be unavailable in derivations that fail, and NcP is required also in some derivations for valid arguments. A derivation showing the obversion principle ¬ ∀x Fx ⇒ ∃x ¬ Fx is simple example of this; EG cannot be applied because the premise does not entail any sentence ¬ Fτ from which we could generalize.

The rules for restricted quantifiers take on the same general forms. The two basic rules are Proof by Restricted Choice (PRCh) and Restricted Non-constructive Proof (RNcP):

│⋯ │(∃x: ρx) θx │⋯ ││⋯ ││ ││ ││ ││ ││ ││ ││ │├─ ││φ │...

│⋯ │(∃x: ρx) θx n │⋯ ││⋯ ││ⓐ │││ρa │││θa ││├─ │││ ││├─ │││φ n │├─ ││φ n PRCh │...

Fig. 8.5.2-4. Developing a derivation at stage n by exploiting a restricted existential; the parameter a is new to the derivation.

│⋯ ││⋯ ││ ││ ││ ││ ││ │├─ ││(∃x: ρx) θx │...

│⋯ ││⋯ │││(∀x: ρx) θx ││├─ │││ ││├─ │││⊥ n │├─ n RNcP ││(∃x: ρx) θx │...

Fig. 8.5.2-5. Developing a derivation at stage n by planning for a restricted existential.

The exploitation rule introduces two suppositions; they stipulate of the example chosen not only that it have the attribute of the claim of exemplification but also that it be in the domain of this claim. An analogous move in an English proof would be to say, Let r be a real number, and suppose it is between 0 and 1 as a way of exploiting the fact Some real number is between 0 and 1.

The analogue of EG for restricted existentials is the rule Restricted Existential Generalization (REG):

│⋯ │ρτ │⋯ │θτ │⋯ ││⋯ ││ ││ │├─ ││φ │...

│⋯ │ρτ │⋯ │θτ │⋯ ││⋯ n REG ││(∃x: ρx) θx X ││ │├─ ││φ │...

Fig. 8.5.2-6. Developing a derivation at stage n by adding a restricted existential whose domain and attribute predicates are found among the active resources applying to the same term.

As an example of REG, let us construct a derivation to show that Every horse is a mammal implies Any head of a horse is a head of a mammal (an entailment mentioned in 7.1.1 as being beyond the scope of Aristotle’s syllogistic logic).

Existential generalization is used at stage 4 and saves us having to enter (∀z: Mz) ¬ Daz as a supposition to be reduced to absurdity. That is a small simplification in this case; but REG can provide a more substantial simplification when it is used to provide an auxiliary resource for a detachment rule, as in the following derivation of an alternative analysis of Any head of a horse is a head of a mammal that treats a horse as marking a generalization with wide scope.

Here the alternative to REG is a use of MCR to exploit the premise for b after planning for (∃z: Mz) Dxz by NcP, and each of the two gaps opened by MCR would require some work to complete. Here is what a completed derivation along those lines would look like:

Although this is not a very natural argument for the entailment, it provides a good illustration of the basic rules for both restricted universals and restricted existentials; and this sort of approach could be unavoidable in the case of an argument that was not valid.

As was the case with universals, it is possible to capture the logical properties of restricted existentials by way of their restatement using unrestricted quantifiers. The rules for doing this are Restricted Existential Premise (REP) and Restricted Existential Conclusion (REC). The latter takes two forms since it needs to be applied to resources as well as goals in order to use EG in place of REG. The second form of REC is counted as an attachment rule since it and REP could not both be counted as progressive.

│⋯ │(∃x: ρx) θx │⋯ ││⋯ ││ ││ │├─ ││φ │⋯

│⋯ │(∃x: ρx) θx n │⋯ ││⋯ n REP ││∃x (ρx ∧ θx) ││ │├─ ││φ │⋯

Fig. 8.5.2-7. Developing a derivation at stage n by restating a restricted existential resource.

│⋯ ││⋯ ││ ││ ││ ││ │├─ ││(∃x: ρx) θx │⋯

│⋯ ││⋯ │││ │││ ││├─ │││∃x (ρx ∧ θx) n │├─ n REC ││(∃x: ρx) θx │⋯

│⋯ │∃x (ρx ∧ θx) │⋯ ││⋯ ││ ││ │├─ ││φ │⋯

│⋯ │∃x (ρx ∧ θx) n │⋯ ││⋯ n REC ││(∃x: ρx) θx X ││ │├─ ││φ │⋯

Fig. 8.5.2-8. Developing a derivation at stage n by restating a restricted existential goal or restating a resource as a restricted existential.

Each of PRCh, RNcP, and REG could be replaced by a use of one of these along with other rules—PCh followed by Ext, NcP followed by uses of UI together with MPT or CR, and EG preceded by Adj, respectively.

Arguments for the soundness and completeness of this system carry over from 7.7 without any new wrinkles. We solved all the key problems there, and a number are not even repeated here.

However, we cannot avoid the consequences of the failure of decisiveness. To find finite counterexamples whenever they exist, we would need to modify the rules for exploiting existential resources in the way the rule for planning for a universal goal was modified in 7.8.1. Without such rules, we will not reach dead-end open gap in any derivation whose resources contain a weak, though unrestricted, claim of general exemplification (e.g., the sentence of the form ∀x ∃y Rxy). We will label the modified rules Supplemented Proof by Choice (PCh+) and Supplemented Proof by Restricted Choice (PRCh+).

│⋯ │∃x θx │⋯ ││⋯ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ │├─ ││φ │...

│⋯ │∃x θx n │⋯ ││⋯ │││θσ ││├─ │││ │││ ││├─ │││φ n ││ ││⋮ ││ │││θτ ││├─ │││ │││ ││├─ │││φ n ││ ││ⓐ │││θa ││├─ │││ │││ ││├─ │││φ n │├─ n PCh+ ││φ │...

│⋯ │(∃x: ρx) θx │⋯ ││⋯ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ ││ │├─ ││φ │...

│⋯ │(∃x: ρx) θx n │⋯ ││⋯ │││ρσ │││θσ ││├─ │││ ││├─ │││φ n ││ ││⋮ ││ │││ρτ │││θτ ││├─ │││ ││├─ │││φ n ││ ││ⓐ │││ρa │││θa ││├─ │││ ││├─ │││φ n │├─ n PRCh+ ││φ │...

Fig. 8.5.2-9. Developing a derivation at stage n by exploiting an unrestricted or a restricted existential; the parameter a is new to the derivation and the terms σ, ..., τ include at least one from each current alias set for the gap

The following derivation illustrates these rules. It shows that a claim of general exemplification need not imply uniformity by finding a counterexample to the entailment ∀x ∃y Rxy ⇒ ∃y ∀x Rxy.

│∀x ∃y Rxy a:2, c:9 ├─ ││∀y ¬ ∀x Rxy a:3, c:10 │├─ 2 UI ││∃y Ray 5 3 UI ││¬ ∀x Rxa 4 ││ ││││Raa (7) │││├─ │││││● ││││├─ 7 QED │││││Raa 6 ││││ ││││ⓒ ││││││¬ Rca │││││├─ 9 UI ││││││∃y Rcy 12 10 UI ││││││¬ ∀x Rxc 11 ││││││ ││││││││Rca │││││││├─ ││││││││(unfinished but will close) │││││││├─ ││││││││∀x Rxc 12 │││││││ ││││││││Rcc │││││││├─ ││││││││││¬ Rac │││││││││├─ ││││││││││○ Raa, ¬ Rca, Rcc, ¬ Rac ⇏ ⊥ │││││││││├─ ││││││││││⊥ 14 ││││││││├─ 14 IP │││││││││Rac 13 ││││││││ │││││││││● 15 ││││││││├─ 15 QED │││││││││Rcc 13 ││││││││ ││││││││ⓔ │││││││││(unfinished) ││││││││├─ │││││││││Rec 13 │││││││├─ 13 UG+ ││││││││∀x Rxc 12 │││││││ │││││││ⓓ ││││││││Rcd │││││││├─ ││││││││(unfinished) │││││││├─ ││││││││∀x Rxc 12 ││││││├─ 12 PCh+ │││││││∀x Rxc 11 │││││├─ 11 CR ││││││⊥ 8 ││││├─ 8 IP │││││Rca 6 │││├─ 6 UG+ ││││∀x Rxa 5 │││ │││ⓑ ││││Rab │││├─ ││││(unfinished) │││├─ ││││∀x Rxa 5 ││├─ 5 PCh+ │││∀x Rxa 4 │├─ 4 CR ││⊥ 1 ├─ 1 NcP │∃y ∀x Rxy

Although this is long and cumbersome, the development of the dead-end gap goes through precisely the steps you would need to go through in your own thinking to arrive the same counterexample:

The premise says that everything stands in relation R to something or other. So let’s suppose we have an object a such that Raa. But we if we stop there, everything will stand in R to a and the conclusion will be true. So let’s suppose we have a second object c that doesn’t stand in R to a. Now c must stand in R to something if the premise is to be true and it can’t stand in R to a, so let’s suppose it stands in R to itself. Now, to make the conclusion false we must be sure that not everything stands in R to c, so we better suppose that a does not. So we’ve described a possible world containing objects a and c where Raa, ¬ Rca, Rcc, ¬ Rac; and that’s enough to make the premise true and the conclusion false.

Developing the unfinished gaps would lead to other counterexamples. For example, the last open gap in this derivation explores the possibility of making the premise true by having a stand in R to another object b and it would, among other things, lead us to a counterexample in which each of a and b is stands in R to the other but neither stands in R to itself.