Introduction to Logic, MT 2007, Week 5

(Ofra Magidor)

  • Up to now we have been concerned with a branch of logic called propositional calculus.
  • From now on, we will be concerned with an extension of propositional calculus called ‘predicate calculus’.
  • The move from propositional calculus to predicate calculus is motivated by the following observation. Our central motivation for looking at propositional calculus we noticed that some arguments were not only valid but formally valid (roughly: any argument with the same form would be valid or they were valid ‘in virtue’ of their form). But unfortunately, the language of predicate calculus is too coarse-grained to capture the validity of many other arguments that intuitively are also valid ‘in virtue of their form’. For example: the argument ‘All humans are mortal. Socrates is Human. Therefore, Socrates is Mortal’ is valid, and moreover if we uniformly replace ‘Socrates’ by any other name, and ‘human’ by any other predicate we would get an argument that is also valid.
  • We thus introduce a new language L2 (aka ‘Elisabeth’, aka ‘Liz’) which is able to represent propositions in a more fine grained way.

The symbols of L2 are:

Sentences letters: P, Q, S, P1,Q1,…

Individual variables: x, y, z, x1, x2,…

Individual constants: a, b, c, a1, a2,…

Predicate and relation letters: R, F, G, R1, R2. For each predicate letter we also need to specify how many places it has (Note: Hodges sometimes does this by writing the relevant number of variables after the letter: e.g. ‘Rxy’ or ‘Gx’).

Connectives: , , , , 

Quantifiers, 

Brackets [, ]

Note: We will sometimes be sloppy and not specify how many place the predicate letter has. We will try to do this only when it is clear from the context. Also note that some people count sentence letters as 0-placed predicate letters.

The WFFs of L2 are defined as follows:

  1. Any sentence letter is a wff.
  2. Anyn-place predicate letter followed bynsymbols – each of which is either an individual variables or individual constant - is a wff.
  3. If  is a wff,  is a wff

4. If  and ψ are wffs then [ ψ], [ ψ], [ ψ], [ ψ] are wffs.

5. For any variable x, if  is a wff then x, x are wffs.[1]

6. Nothing is a wff unless by virtue of 1 to 4.

  • Note that all formulas of Elle are also formulas of Liz.
  • A sub-formula is any part of a wff which is itself a wff. The scope of an occurrence of a logical constant (i.e. connective or quantifier) is the smallest sub-formula in which it occurs.
  • A variable x is called ‘bound’ if and only if it is it in the scope of ‘x’ or a ‘x’ quantifier. A variable which is not bound is called ‘free’. For example in the wff xRxy, ‘x’ is bound by ‘y’ is free.
  • A wff is called ‘closed’ if and only if all of its variables are bound. Otherwise it is called ‘open’. For example, the wff xRxy is open because one of its variables (namely ‘y’) is free. The wff yxRxy, on the other hand is closed.

1

[1]Some people also require that  have a free occurrence of ‘x’ in it. This won’t matter much for our purposes – so don’t worry about it.