7.8.2. The failure of decisiveness

The rules UG+ and ST are designed to uncover finite structures whenever possible. We will not prove that they do this; instead we will see why finite structures are not always there to be uncovered.

For example, consider the following pair of sentences:

The first says that the relation expressed by R obeys a law of transitivity, and the second says that nothing is related to itself by R, which is to say that R is irreflexive.

What must a structure be like to make these sentences true? Thinking in terms of the diagrams of 6.4.2, the claim of irreflexivity tells us that there cannot be any looped arrows. The claim of transitivity tells us that arrows linked head to tail running from object a to object b and from object b to object c can be spanned by an arrow running directly from a to c (see Figure 7.8.2-1).

Fig. 7.8.2-1. The arrow spanning two linked arrows that is implied by transitivity.

Now, if we had a circuit of arrows leading from some object back to itself by way of other objects, transitivity would imply that there was a loop leading from the object directly back to itself. Figure 7.8.2-2 illustrates this in a case where we have Rab, Rbc, Rcd, and Rda. Transitivity made be applied three times, first to show that Rac (because Rab and Rbc), then to show that Rad (because Rac and Rcd), and finally to show that Raa (because Rad and Rda).

Fig. 7.8.2-2. A circuit from a to a reduced to a looped arrow in three steps by spanning linked arrows.

Irreflexivity would rule out the truth of Raa, so irreflexivity can hold along with transitivity only if there are no loops or circuits of arrows like the one illustrated.

Finally, let us add to the statements of transitivity and irreflexivity either of the sentences ∀x ¬ ∀y ¬ Rxy and ∀x Rx(fx) that we considered in 7.8.1. Each of the latter sentences tells us, in its own way, that every object is at the tail of some arrow. A little thought (and attempts at diagrams) will show that there is no way to manage this with a finite number of objects unless there is somewhere a loop or a circuit of arrows. So, although the sentences ∀x ¬ ∀y ¬ Rxy and ∀x Rx(fx) can each be made true in a structure with only one reference value if we consider them by themselves, they cannot be true along with claims of transitivity and irreflexivity in any structure with only a finite number of values.

Nevertheless ∀x ¬ ∀y ¬ Rxy and ∀x Rx(fx) are consistent with claims of transitivity and irreflexivity. For example, let us take the positive integers as our referential range and let R express the relation < of one number being less than another. The relation < is transitive and irreflexive. Moreover, each positive integer is less than some positive integer, so there is no positive integer that has the property of being less than no positive integer—and that is what ∀x ¬ ∀y ¬ Rxy says on this interpretation. And, if we interpret the functor f by any function whose output is always larger than its input, ∀x Rx(fx) will also be true.

So there are sets of sentences that are consistent but whose members cannot all be true with only a finite range of reference values. This means that, even if a revised system of derivations using UG+ and ST always succeeds in locating finite structures, it cannot always provide an answer to our questions about entailment. If the entailment holds, it will say so. If the entailment fails and can be shown to fail using a finite structure, it will say so. But, if the entailment fails and can only be shown to fail only by using an infinite structure, it will give no answer because it will never finish describing a structure of the required sort.

Of course, it is possible to describe an infinite structure in a finite space (as we did informally above), so we might hope that a more substantial modification of our system might lead us to descriptions of infinite structures after finitely many stages. But here we must recall the result of Church mentioned in 7.7.1: although an improved system might provide answers to some further questions about entailment, no system could answer them all correctly. In terms of the present discussion, this implies that no matter what method we choose for describing structures, there are bound to be structures among those we need to describe that our method would not lead us to.