CHAPTER SIX

Predicate Logic transcribed into Laws of Form Notation

The formulae of first order logic can be transcribed into 'Laws of Form' notation in a straightforward way. Consider first of all the atomic formulae. In the calculus of Circles and Letters (CL-calculus) brackets mean one thing and one thing only. A pair of brackets ( ) is always used as a shorthand sign for a circle. So it would confuse matters to have formulae like G(x,y,z) knocking around. We represent the arguments of a predicate-function (G in this case) by subscripts instead. So

G(x,y,z) becomes Gxyz.

When the intended relationship of the letters G, x, y, z is obvious from the context, we sometimes forget about the subscripting and just write

Gxyz

instead.

We choose to represent the value True by the empty expression, False by the empty mark. So

T becomes , F becomes .

If A is a formula,

¬A becomes .

If A and B are formulae

A ∧ B becomes
A ∨ B becomes
A → B becomes
A ↔ B becomes .

It is easily verified (provided that you know the C-calculus) that all these expressions behave as they ought to when the values _ and O are substituted for A and B. As for the universal quantifier ∀x,

∀x A(x) becomes .

The symbol here is the upper-case Greek letter Pi (equivalent to the Latin P), with subscript x. In ordinary mathematics, the conventional meaning of upper-case Pi is 'take the product of', so, for example, the formula

Πi=1..5 f(xi)

would be taken to mean: take the product of the values f(xi) as i goes from 1 to 5; thus

Πi=1..5 f(xi) = f(x1)×f(x2)×f(x3)×f(x4)×f(x5).

Now, if the universal set U happens to be finite, consisting, for example of the 5-member set {a,b,c,d,e} then ∀x A(x) may be construed as the equivalent formula

A(a)∧A(b)∧A(c)∧A(d)∧A(e) .

Transcribed into Laws of Form notation, in which ∧ is replaced by simple juxtaposition, this last formula becomes simply

Aa Ab Ac Ad Ae ,

an expression which we may well describe as the product of Aa, Ab, Ac, Ad, Ae and symbolize by the formula

Πx∈U Ax .

If we leave out the '∈U' as understood, we arrive at the form given above. Interestingly, the notation Πx actually pre-dates the notation ∀x; the former means of expression was introduced by C.S.Peirce in a paper of 1885, 'The Algebra of Logic', whereas the upside-down A only came in with a paper by Gentzen of 1935. (The backwards E for 'there exists' was brought in earlier by Peano in 1897; Peirce had the symbol Σx for ∃x.)

As for ∃x we use the fact that

∃x A(x) = ¬(∀x ¬A(x))

(in all models); that is, to say 'there is an x for which A(x) is true' is equivalent to saying 'it is not the case that A(x) is False for all x'. So we transcribe

∃x A(x) as

Anatomy of a Wff

Every wff, when transcribed into Laws of Form notation, has a skeleton consisting of nested circles; for example:

To the skeleton, a certain amount of flesh is added, in the form, to start with, of atomic formulae, which may be dotted around anywhere in the spaces between (or outside) the circles. For example:

Finally, to make it into a wff, each variable has to introduced, or announced by a Pi-operator, such as Πx or Πy. Any Pi-operator needs a defined scope, or sub-expression within the whole expression formula to 'act' on. In our original notation, the scope was represented by means of brackets. How is this to be represented in the circle-based form, where brackets are banned? For the moment, let us represent it by a dotted circle, surounding the target formula. The associated Pi-symbol will be drawn just outside or just on the dotted circle, resulting in a form like the following:

For the formula as a whole to be well-formed, the dotted circle associated with a variable (y, for example) must surround at least all the atomic formulae that have y as an argument. It's allowed to include other stuff as well. Naturally it is not allowed to intersect any of the skeletal circles (the 'not'-circles); in other words, it must surround a sub-formula of the whole formula.

Now Lemma 5.1 tells us that, in the context of a suitable model, any wff takes a value, T or F; or, as we now write the two values, _ or O. Let us remind ourselves how this works, using the example just given in the figure. The important thing to grasp is that the process of valuation works inwards and outwards at the same time (in a sense that I hope will become clear as we go along). In the example given, the outermost Pi-operator, with the most inclusive scope, is Πx. Next in is Πy, then Πz. If we wish to evaluate the wff, our first step must be to instantiate x: that is to say, we must choose an element out of the universal set U to be an 'instance' of x. By a slight abuse of notation (in that the instance is only a temporary constant), let's call the instance x. Everywhere within the scope of Πx, we then temporarily replace x by x. Then, moving inwards, we instantiate y, and replace each occurrence of y by y; and instantiate z, replacing each occurrence of z by z. By this point, as there are no more variables in this example, the formula within the scope of Πz has no variables left in it. All the arguments of its atomic formulae must either be constants (each one assigned a U-element by the model) or U-elements (such as x, y, z). Therefore each of these atomic formulae has a value, determined by the model. Hence the formula that is the scope of Πz (what from now on we will refer to as the 'scope-formula' of z) has a value. (This is where the 'working outwards' comes in: the atomic values build up to the value of the formula by working outwards. The working inwards was the instantiation of x, y and z in turn.) This is the value of the formula when z is instantiated as z.

Our next step must be to choose a different instance of z. We then work out a new value for the scope-formula - and so on for all the possible z-instances. All these values contribute (in principle, at least) to the value of ΠzZ (where we use Z to stand for the scope-formula) in the familiar way: ΠzZ takes the value O if any of the contributing values of Z are O, _ otherwise (if the contributing values are all _ ).

This is the value of ΠzZ when x and y are instantiated as x and y, respectively; and in combination with other values will help to determine (working outwards, again) the value of Y (the scope-formula of Πy) - when x and y are instantiated in this particular way. But then we have to choose a different instance of y, and calculate the value of Y all over again - and again, as many times as is necessary to determine the value of ΠyY.

This will help to determine the value of X (the scope-formula of Πx) - but again, only for one particular instantiation of x - and then we must repeat the whole thing for all the different instantiations of x. (It would be no exaggeration to say that the labour of the calculation increases exponentially with the number of nested Pi-operators.) Once we've got all those different values of X can we proceed, finally, to the valuation of ΠxX and to the valuation of the whole wff.

At last we are in a position to state and prove the following

Lemma 6.1

If the sub-formula

appears anywhere in a wff W, it can be replaced by the sub-formula

without making any difference to the value of W in any model. In other words, the scope of Πx can be extended from A to include any other formulae in the same space as A. Conversely, it can be contracted so long as no formula involving the variable x is excluded.

Note: for simplicity we have suppressed indices; but we certainly expect A to depend on x, if not other variables as well. The fact that the original sub-formula is part of a wff implies that the expression B contains no occurrence of x.

Proof

To start with let us suppose that the context of the sub-formula within W is such that it is not within the scope of any Pi-operator occurring further out in W. Then B, Πx{A} and Πx{AB} are all themselves wffs and have values as soon as a model is given. (Here the curly brackets {...} represent the scope of the quantifier, i.e. the dotted circle in the full two-dimensional diagram.) Suppose the value of B is _ ; then the two expressions that are the subject of the lemma become identical and of equal value. If, on the other hand, the value of B is O, then AB has the value O, whatever the instantiation of x, therefore Πx{AB} has the value O. But so does BΠx{A}. Thus the value of W will be unchanged if one expression is exchanged for the other. If the sub-formula is situated within the scope of some further-out Pi-operators, it will still be the case that the two expressions have the same value when the further-out variables are instantiated in any particular way; the expressions can therefore be exchanged without having any effect on the value of W ◊


In our statement of Lemma 6.1 we said 'The scope of Πx can be extended from A to include any other formulae in the same space as A'. We stand by the claim; however, we must pay attention to the qualification 'in the same space as A'. For at this stage in our argument, the spaces inside our well-formed formula are defined by two sorts of boundary, the authentic 'not-circles' of the CL-calculus, and the dotted scope-defining circles - which will prove to be no more than temporary scaffolding.

We need to examine the situation when the space occupied by A and the other formulae in the same space is defined by the scope-boundary of another, further out Pi-operator, Πv, say. Then, after the application of Lemma 6.1, we end up with a sub-formula of W surrrounded by two scope-boundaries, belonging to the variables v and x.

Lemma 6.2

When a sub-formula of a wff is surrounded by two scope-boundaries, belonging to two variables, it makes no difference to the value of W which scope-boundary is exterior to the other.

Proof

The value of Πvx{A}} is _ if all instantiations of the variables v and x cause A to take the value _ ; O if there is an instantiation that causes A to take the value O. This statement is independent of the order in which the variables are instantiated, therefore

Πvx{A}} = Πxv{A}}

(the formulae take the same values in all models). If W has more variables, exterior to v and x, all the above statements need to be qualified by the clause 'in any given instantiation of the exterior variables' ◊

Corollary 6.3

Similar considerations apply if three or more scope-boundaries are nested within the space defined by a 'not-circle' (or the outer space of W as a whole). Therefore the dotted circles may be done away with. If operators Πx, Πy, ..., Πz are written in a space, we may assume that their scope is the whole of the interior of the not-circle surrounding them; or the whole of W in case there is no bounding circle ◊

Having abolished scope-boundaries, we need to modify our criterion for a formula to be well-formed. From now on, we say that each variable occurring as an argument of a predicate-function must be 'announced' by a Π-operator either in the same space as the predicate-function, or in an 'outer' space within which the predicate-function is contained at some depth or other. ('Spaces' are now once more bounded by not-circles as in the CL-calculus; except for the outermost, unbounded space.)

Lemma 6.4: Migration of Pi-operators

Suppose that an expression having the form of the left-hand expression in the following figure occurs as a sub-expression of a wff. We assume that no Pi-operator is present (as part of the expression B) in the space between the nested circles. Then the expression is interchangeable with one that is the same except that the Pi-operator has moved up from the inner space to the outer, as indicated:

Thus a Pi-operator can migrate outwards in a wff, going up by two levels, provided that no other Pi-operators stand in its way (in the intervening level).

Proof

In case B has the value _ , the two sides become equal by virtue of unwrap i.e. ((E)) = E. In case B has the value O, both sides of the equation have the value _ ◊

Pitfall 6.5

If formula A involves the variables x and y,

The formula on the left says 'there exists a y such that A takes the value _ for all x'; that on the right says 'for all x there exists a y such that A = _ '. These are not the same.

For example, for the universe of discourse take the natural numbers {1,2,3,...}, and let Axy stand for the two-place predicate 'y is the next number after x'. It is quite true that every number has a next number after it, but untrue that there is a number which is the next number after every other number. Remember, just one counterexample (i.e. one model in which Val[B]≠Val[C]) is enough to disprove the equivalence of two formulae (to disprove B = C).

Thus, to some extent, all the Pi-operators in a wff can float up to the top level, but a Pi-operator that gets stuck at the penultimate level (one level down from the top) may well cause a blockage, preventing other Pi's lower down in its part of the wff from bubbling up. Fortunately, there is a way of undoing the blockage, due to the Norwegian mathematician Thoralf Skolem. That is the subject of the next chapter.