Predicate Calculus with Identity: Syntax and Proof Theory

 

*The predicate calculus is more tricky that PC. I strongly urge you to study chapter 3 of Lemmon. None of the proofs or questions below are provided in Lemmon.

 

1. Introduction

The job of logic is to codify valid inference. We have seen that PC is adequate to this task where validity solely turns on the occurrence of coordinate expressions, such as and, not, etc. Clearly, however, not every valid inference turns on such expressions. That is, there is more to validity than PC mandates.

 

Consider the following arguments:

 

(1) Every footballer is blonde.

     Pele is a foootballer.

     Pele is blonde.

 

(2) Pele is a footballer.

     Therefore, someone is a footballer.

 

(3) No footballer is blonde.

     Pele is a footballer.

     Therefore, Pele is not blonde.

 

Transparently, each of these arguments is valid, but PC is unable to represent them as valid. Because each sentence of the arguments is distinct, and none include constants, the best PC can do is to notate each sentence with a distinct propositional variable. Thus:

 

(4) P

    Q

    R

 

(4) is not a valid argument of PC.

 

The essential problem is that PC abstracts away from all structure a given sentence possesses. But some valid inferences depend upon such structure. The predicate calculus (PredC) is designed to represent such structure so as to capture the valid inferences which depend upon such structure.

 

2. Syntax

The syntax of PredC is somewhat more complicated than that of PC. Consider the arguments above. Whereas PC just has propositional variables and constants, to represent the above arguments we appear to require at least names (‘Pele’) and predicates (‘is a footballer’, ‘is blonde’). Do we need more? Yes.

 

First off, note that the validity of the arguments (1)-(3) do not depend on the fact that they are about footballers and Pele, etc. Witness, e.g.,

 

(5) Every A is B

     a is A

     a is B

 

Whatever we uniformly substitute for ‘A’, ‘B’, and ‘a’, the result is a valid argument. But note that we can’t substitute ‘every’ for another similar expression:

 

(6) No A is B

     a is A

     a is B

 

Any uniform substitution of the terms of (6) results in an invalid argument: e.g.,

 

(7) No footballer is blonde.

     Pele is a footballer.

     Pele is blonde.

 

We call expressions such as every, some, no, etc. quantifiers (this will be explained). How, then, are we to treat expressions such as ‘Every/No footballer’? Can we treat them like names? No.

 

(i) As just seen, we can substitute into the positions of names and retain validity. We can’t do that with quantifiers.

(ii) The sentence, ‘Pele is a footballer’ attributes a property - being a footballer - to a thing - Pele. Something else appears to be going on with ‘Every footballer is blonde’. This sentence does not attribute a property to a thing - every footballer is not a thing, and even if we were to think it was, heaven knows what it would be for it to be blonde. ‘Every footballer is blonde’ says ‘Everything which is a footballer is also blonde’. Alternatively, ‘For all things, if it is a footballer, then it is blonde’.

 

It seems that not only do we need something more than names to represent quantifiers, we also require the logical constants of PC. Let us introduce some symbols of the formal language of PredC.

 

Symbols

 

(i) Arbitrary Names

Since PredC abstracts away from what particular names refer to, we may use arbitrary names - a, b, c, d, etc. We call them arbitrary for they stand for any given object, not a particular object. Thus, ‘a’ and ‘b’ do not necessarily ‘refer’ to distinct things.

 

 

(ii) Predicates

 Again, PredC abstracts away from the properties expressed by particular predicates. Our symbolism thus adopts predicate letters - F, G, H, I, etc. So far, then, we can represent ‘Pele is a footballer’ as ‘Fa’ (Note: ‘Ia’ would also do as well as ‘Fd’, etc.).

 

(iii) PC Constants

We adopt wholesale the logical constants of PC. Thus, the sentence ‘Pele is a  footballer and Tony Blair is a politician’ may be represented as ‘Fa & Gb’.

 

(iv) Quantifiers (Constants)

In English, quantifiers constitute a mixed and complex category of expression. Let us just think about ‘every’ and ‘some’. We said above that we can think of a sentence of the form ‘Every F is G’ as expressing a proposition of the form ‘For every thing, if it is F, then it is G’. Let us replace the conditional here with the constant ‘→’ and substitute the variable x for the pronoun ‘it’ and the dummy generic noun ‘thing’. This gives us

 

(6) For every x, x is F → x is G.

 

We can drop the copula (is) in line with our convention of notating predication (i.e., putting the predicate letter before its subject). This gives us:

 

(7) For every x, Fx → Gx.

 

Finally, let us notate the prefix ‘For every x’. Here we employ a variable binding operator (the universal quantifier):

 

(8) ("x)(Fx → Gx)

      ‘Every x is such that if x is F then x is G’

 

The procedure is analogous for something/someone, with one crucial difference. Consider, ‘Some footballers are blonde’. Could we notate this as (9)?

 

(9) For some x, Fx → Gx.

 

No. (9) doesn’t say that any x at all is F (a footballer). It simply says that there is something such that if that thing is F, then it is G. We get the right reading if we substitute ‘&’ for ‘→’:

 

(10) For some x, Fx & Gx.

 

We fully formalize by introducing the existential quantifier:

 

(11) ($x)(Fx & Gx).

       ‘There is an (at least one) x such that x is F and x is G’.

 

Variables ≠ Names

Variables are not names. Names - a, b, etc. - are read as referring to arbitrary objects. Variables do not refer at all. The difference may be seen in English between proper names and pronouns. Compare:

 

(12)a. Bill is tall.

      b. It/he/she is tall.

 

In a sense, b. doesn’t say anything determinate, for we don’t know what it is. Pronouns can, however, be bound by a preceding quantifier, e.g.,

 

(13) The car skidded, then it hit a lamp-post.

 

Here, ‘it’ is bound by the preceding nominal phrase ‘The car’. We can’t bind names in the same way. Imagine you have a car called Herbie:

 

(14) The car skidded, then Herbie hit a lamp-post.

 

Here, it seems as if there are two cars.

 

Variables substitute names in the formation of PredC formulae. They allow us to generalise over the positions of names. The following procedure gives an example:

 

(15)a. Fab

      b. ($x)(Fxb)

      c. ("y)($x)(Fxy)

 

Let ‘F’ = ‘loves’.

We go from ‘a loves b’ to ‘Someone loves b’ to ‘Everyone is loved by someone’. Note, this is not valid. It is just an example of how variables allow for generalisation.

 

Differences Between the Quantifiers.

 

(16) ¬($x)Fx

       ‘Nothing is F’ (Here we are denying that something is F, which means that nothing at

        all is F.)

(17) ($x) ¬Fx

       ‘Something is not F’ (Here we are saying that there is something or other, but it is not

        F.)

(18) ¬("x)Fx

      ‘Something is not F’ (Here we are saying that F-ness doesn’t hold universally, i.e.,

       there is something which lacks F.)

(19) ("x) ¬Fx

       ‘Nothing is F’ (This is not consistent with something being F. It doesn’t say

       ‘Not every thing is F, but something might be’ - it denies F-ness, as it were, of

        everything.)

 

The differences of interpretation are here to do with the scope of ‘¬’. If another reason were needed, this is why quantifier phrases are not names, for names are insensitive to the scope of ‘¬’: ¬a is F ↔ a is ¬F.

 

It may be noted from above that

 

(20)a. ("x)f ↔df ¬($x)¬f

       b. ($x)f ↔df ¬("x)¬f

       c. Everything is f iff it is not the case that something is not f.

       d. Something is f iff it is not the case that everything is not f.

 

2.1. Recursive Definition

 

As with PC, we want a recursive definition of ‘formula of PredC’.

 

(PredC-Df)

 (i)    x, y, z,… are terms of PredC (variables).

(ii)    a, b, c, …. are terms of PredC (arbitrary names).

(iii)   F, G, H,… are predicates letters of PC.

(iv)   If F is a predicate letter and <a1, …, an> is a sequence of terms (where n ˜1), then

         ‘Fa1, …, an’ is a formula of PredC.

(v)    If ‘Fa1,… v,…an’ is a formula is PredC, with at least every occurrence of v

        unbound, then

        (a) ‘("x)Fa1,… x,…an’  and

        (b) ‘($x)Fa1,… x,…an’  are formulae of PredC.

(vi)   If ’Fa1,… t,…an’  is a formula is PredC, with t as a name, then

       (a) ‘("x)Fa1,… x…an’ and

       (b) ‘($x) Fa1,… x…an’ are formulae of PredC.

(vii)  If X is a formula of PredC, then ¬X,

                                                              X & X,

                                                              X v X,

                                                              X→X,

                                                              and X ↔ X are formulae of PredC.

(viii) These are all the formulae of PredC.

 

Q: From the definition, which of the following are formulae of PredC?

(i)   Fa & ¬Fz

(ii)  ($x)("x)Faxz

(iii) Fx → ("y)(Fx → Gb)

(iv) ("x)Fxx

 

 

 

3. Rules of Inference for PredC

 

We take over all the rules of PC and in addition have four new rules for, respectively, the introduction and elimination of the universal and existential quantifiers.

 

(i) Universal Elimination (UE)

For any formula, either derived or assumed, ‘("x)Fx’, which contains at least one occurrence of ‘x’ bound, one can derive ‘Fa’, which rests on all the assumptions upon which ‘("x)Fx’ rests.

Justification: If everything is F, then any arbitrary object (a) will also be F.

 

(ii) Universal Introduction (UI)

 If one can derive ‘Fa’ resting upon no assumptions which feature ‘a’, then one can derive‘("x)Fx’, which binds every occurrence of ‘x’ substituting ‘a’, and rests upon all assumptions upon which ‘Fa’ rests.

Justification: If  F holds of an arbitrary object (a) resting upon no assumptions about the object, then F holds of everything.

 

(iii) Existential Introduction (EI)

For any formula, either derived or assumed, ‘Fa’, one can derive ‘($x)Fx’, which binds every occurrence of ‘x’ substituting ‘a’, and rests upon all assumptions upon which ‘($x)Fx’ rests.

Justification: If an arbitrary object (a) is F, then something or other is F.

 

(iv) Existential Elimination (EE)

For any formula, ‘($x)Fx’, if, from assumption ‘Fa’, where ‘a’ substitutes every occurrence of x, one can derive C, then one can conclude C, resting upon all assumptions upon which ‘($x)Fx’, ‘Fa’, and C rest, minus any assumptions upon which two or more formulae rest (in effect, this will mean that C follows from ‘($x)Fx’ minus ‘Fa’. 

Justification: if C follows from an arbitrary object (a) being F, then it follows from something or other being F.

 

Examples

We saw above that  ‘¬($x)Fx’ says the same thing as ‘("x) ¬Fx’. We should thus be able to prove one from the other.

 

(i) ¬($x)Fx ┤├ ("x) ¬Fx

 

1   (1)  ¬($x)Fx                   A

2   (2)           Fa                   A

2   (3)    ($x)Fx                   2EI

1,2(4)  ¬($x)Fx & ($x)Fx   1,3&I

1   (5)         ¬Fa                   2,4RAA

1   (6) ("x) ¬Fx                   5UI

 

The second proof is quite complex; its elegance will repay scrutiny:

 

(ii) ("x) ¬Fx ┤├ ¬($x)Fx

 

1   (1)   ("x) ¬Fx                           A

2   (2)       ($x)Fx                           A

3   (3)              Fa                           A

1   (4)            ¬Fa                           1UE

1,3(5)              Fa & ¬Fa                3,4&I

3   (6) ¬("x) ¬Fx                           1,5RAA

2   (7) ¬("x) ¬Fx                            2,3,6EE

1,2(8)   ("x) ¬Fx & ¬("x) ¬Fx      1,7&I

1   (9)    ¬($x)Fx                             2,8RAA

 

We also saw that ‘($x) ¬Fx’ says the same thing as ‘¬("x)Fx’. We should thus be able to prove one from the other.

 

(i) ($x) ¬Fx ┤├ ¬("x)Fx

1   (1) ($x) ¬Fx            A

2   (2)    ("x)Fx            A

3   (3)         ¬Fa            A

2   (4)           Fa            2UE

2,3(5)        ¬Fa & Fa    3,4&I

3   (6) ¬("x)Fx            2,5RAA

1   (7) ¬("x)Fx            1,3,6EE

 

As before, the second proof is quite complex. First, consider this putative proof:

 

*(ii) ¬("x)Fx ┤├ ($x) ¬Fx

1   (1) ¬("x)Fx              A

2   (2)           Fa              A

1   (3)         ¬Fa             1UE

1,2(4)           Fa & ¬Fa  2,3&I

1   (5)         ¬Fa             2,4RAA

1   (6) ($x) ¬Fx             5EI

 

Q: What is wrong with this proof?

 

The correct proof is complex, but exceedingly pretty:

 

 

 

 

(ii) ¬("x)Fx ┤├ ($x) ¬Fx

 

1   (1)     ¬("x) Fx                          A

2   (2)     ¬($x)¬Fx                         A

3   (3)             ¬ Fa                         A

3   (4)       ($x)¬Fx                         3EI

2,3(5)     ¬($x)¬Fx & ($x) ¬Fx      2,4&I

2   (6)            ¬¬Fa                         3,5RAA

2   (7)                 Fa                        6DN

2   (8)         ("x)Fx                        7UI

1,2(9)         ("x)Fx & ¬("x)Fx     1,8&I

1  (10) ¬¬($x) ¬Fx                        2,9RAA

1  (11)     ($x)  ¬Fx                       10DN

 

Q: Prove the following:

 (i) ("x)(Fx → Gx) ┤├ ("x) ¬Gx → ("x) ¬Fx

(ii) ("x)(Fx → Gx) ┤├ ($x) ¬Gx → ($x) ¬Fx

(iii) ("x)(Fx → ¬Gx) ┤├ ¬($x)(Fx & Gx)

 

Examples of relations

So far, we have just established results about monadic predication, i.e., of the form ‘Fa’. The proof theory set out also deals with relations, e.g., ‘Fab’, ‘Fabc’, etc. One basically proceeds in the same way, with a few minor complications. First, one is dealing with distinct variables - not just ‘x’: distinct arbitrary names must substitute distinct variables. It doesn’t follow that one is talking about distinct things - see the section on identity. Second, one has quantifiers in the scope of other quantifiers: always proceed from the widest scope quantifier in - from left to right.  The proof below gives an example:

 

(i) ("x)($y)("z)Fxyz ┤├ ("x)("z)($y)Fxyz

 

1(1)  ("x)($y)("z)Fxyz                A

1(2)         ($y)("z)Fayz                1UE

3(3)               ("z)Fabz                A

3(4)                      Fabc               3UE

3(5)               ($y)Fayc                4EI

3(6)        ("z)($y)Fayz                5UI

1(7)        ("z)($y)Fayz                1,3,6EE

1(8) ("x)("z)($y)Fxyz                7UI

 

 

Q1: We here apply EE at line (7) to eliminate assumption (3). Could we have first derived ‘("x)("z)($y)Fxyz’ at line (7) from line (6), then applied EE?

 

 

Q2: Prove the following:

 

(i) ("x)("y)("z)Fxyz  ┤├ ("z)("y)("x)Fxyz

(ii) ($x)($y)("z)Fxyz ┤├ ("z)($y)($x)Fxyz

 

 

4. Identity and Rules of Inference

 

The concept of identity adds great expressive power to our logic. Let us say that we want to express the proposition that a given equation has a unique solution, a case common in mathematics. How would we represent this in PredC? The best we could do so far would be (21), where ‘F’ = ‘is a solution to equation E’:

 

(21) ($x)Fx

 

But this just says that the equation has some solution, not a unique one. We might try

 

(22) ($x)Fx & ¬($y)Fy

 

But this just says, in effect, that not everything is a solution to the equation.

 

With identity, however, we can express the uniqueness claim:

 

(22) ($x)(Fx & ("y)(Fy → x = y))

 

This says that the equation has a solution and ‘anything else’ which is a solution is (in fact) identical with the given solution.

 

Axioms for Identity

Axioms are logical truths which we take to be definitive of our logical concepts:

 

A1: ("x)x = x

        ‘Everything is identical with itself’.

 

A2: ("x)("y)((x = y & Fx) → Fy)

       ‘Identical things share all their properties’.

 

It follows from the axioms that everything is identical with itself and nothing else. Why? Because identity itself is a property.  One can use an indefinite number of variables to range over a ‘universe of objects’, even if the universe contains just one object.

 

From the axioms, we may introduce two rules of inference.

 

 

 

(i) Identity introduction (=I)

At any stage of a proof, one introduce ‘a = a’ as a logical truth which rests upon no assumptions.

Justification: Everything is identical with itself as a matter of logic, so ‘a = a’ need rest on no assumptions.

 

(ii) Identity elimination (=E)

If, as assumptions or derived formulae, ‘Fa’ and ‘a = b’, then one may derive ‘Fb’, resting upon all assumptions upon which ‘Fa’ and ‘a = b’ rest.

Justification: Since identities share all properties, if a = b, then b has any properties a does.

 

Since these rules simply encode our axioms, we should be able to derive the axioms as theorems:

 

(i) ├ ("x)(x = x)

 

(1)          a = a              =I     

(2) ("x)(x = x)            1UI

 

(Note: Normally, we can apply UI to an arbitrary name formula only if it rests upon no assumptions which include the arbitrary name; thus, we can’t apply it directly to an underived formula. Yet since the formula on line 1 has no assumptions, we have not derived it from any assumptions about a, so the restriction on UI isn’t in play.)

 

(ii) ├ ("x)("y)((x = y & Fx) → Fy)

 

1(1)                   a = b & Fa                    A

1(2)                   a = b                            1&E

1(3)                               Fa                    1&E

1(4)                                          Fb         2,3=E

  (5)                 (a = b & Fa) → Fb        1,4CP

  (6)         ("y)((a = y & Fa) → Fy)       5UI

  (7) ("x)("y)((x = y & Fx) → Fy)       6UI

 

(Note:  Again, we can apply UI without its restriction being applicable.)

 

 

Examples of other proofs

It follows from our axioms that ("x)(x = a → Fx) ↔ Fa. That is, if everything which is a is F, then a is F, and if a is F, then everything which is a is F. Thus, we should be able to establish: ("x)(x = a → Fx) ┤├ Fa

 

 

 

(i) ("x)(x = a → Fx) ┤├ Fa

 

1(1) ("x)(x = a → Fx)      A

1(2)          a = a → Fa       1UI

  (3)          a = a                 =I

1(4)                       Fa       2,3MPP

 

Consider this putative proof of the reverse entailment:

 

*(ii) Fa ┤├ ("x)(x = a → Fx)

 

1   (1) Fa                            A

2   (2) x = a                        A

1,2(3) Fx                            2,2=E

1   (4) x = a →  Fx              2,3CP

1   (5) ("x)(x = a →  Fx)    4UI

 

Q: There are two fundamental errors in this ‘proof’- what are they? (Hint: Think about the difference between names and variables and the restriction on UI.)

 

The correct proof is

 

(ii) Fa d ("x)(x = a →  Fx)

 

1   (1) Fa                             A

2   (2) b = a                         A

1,2(3) Fb                            1,2=E

1   (4) b = a  →   Fb             2,3CP

1   (5) ("x)(x = a →  Fx)     4UI

 

Study the difference between the proofs -most enlightening on the application of UI.

 

Q: Prove the following:

(i) b = c & c = a ┤├  b = c

(ii) a = b ┤├  Fa ↔ Fb

(iii) a = b ┤├  a =a ↔ c = b