## The Logic CaféReference

### Chapter Nine — Predicate Logic with Identity

It is recommended that you print this reference.

Contents: Section 1: An Introduction to Identity and Symbolization; Section 2: Predicate Logic with Identity: Syntax and Semantics; Section 3: Complex Names and Functions; Section 4: An Example: Very Elementary Abstract Algebra

#### 1. An Introduction to Identity and Symbolization

This chapter makes one main addition to our work in chapters six through eight: We add equality, the relationship standardly represented by the "=" sign. In other words, we take up the logic of identity. This "predicate logic with identity" provides a logic rich enough for much of natural language. For example, it allows one to represent the logical structure of mathematics.

But we begin with a simple example. We often say things like

(1) Sam is the person on the phone.

This is to say that Sam and the person on the phone are one and the same, identical, or just equal. We could also borrow the equal sign from arithmetic and put this as "Sam = the person on the phone".

In PL we use 'I' for identity:

Ixy:   x=y

Then, using 's' for Sam and 't' for the person on the phone, we get

Symbolization of (1):      Ist

This is meant to be easy. But there are some complications to consider:

These four complications are as follows.

The "is" of Identity and the "is" of Predication

The first complication is the ambiguity of the word "is". For example, instead of "Sam is the person on the phone" one might say:

(2) Sam is Australian

Notice the difference in the meaning of "is"! The first statement says that Sam is identical to the person on the phone; the second describes a quality of Sam by attributing a predicate ("is Australian"). On the standard terminology, the first use is the "is" of identity, the second the "is" of predication.

So, (1) is translated with the identity relation 'I' as shown above: 'Ist'. (2) could be symbolized as

Symbolization of (2):     As

using 'A' for "is Australian".

Distinctness and Numerical Quantification

We might say that Sam and the person on the phone are distinct, i.e., they are not the same person. In PL:

"s and t are distinct":     ~Ist

We can put this symbolization of distinctness to work right away. Think about symbolizing

(3) There are at least two people at home.

Use 'Hx' for "x is at home" and assume a universe of discourse of people. We cannot symbolize this as '(%x)(%y)(Hx&Hy)'! Why not? Because this PL sentence says that there is something x (perhaps named 'a' in PL) and something y (suppose it's named 'b') which are both H's; i.e., 'Ha&Hb' is true. But x and y could be the same thing, i.e., "Iab" could be true and there be only one thing (with two PL names!) which is at home.

The lesson is simple: To symbolize (3), we need to add that x and y are distinct.

Symbolization of (3):    (%x)(%y)[ ~Ixy & (Hx&Hy) ]

Similar uses of "I" are required to symbolize other "numerical" quantification statements of English. These are discussed at length in tutorial 9.1 and summarized in the chart just below.

The following takes our example of quantifying numbers of people "at home". It charts...

• explicit numerical quantifications (e.g., "the number of people at home is greater than zero" is the first),
• some common and equivalent ways of putting this quantification in English (in the white box),
• and suggested symbolizations (on the right).
The number of people at home...
Symbolizations:
...is greater than 0.
(%x)Hx
• Someone is home.
• At least one person is home.
...is greater than 1.
(%x)(%y)[~Ixy&(Hx&Hy)]
• More than one person is home.
• At least two people are home.

...is greater than 2.
(%x)(%y)(%z)[
((~Ixy&~Ixy )&~Ixy)
& ((Hx&Hy)&Hz) ]
• More than two people are home.
• At least three people are home.

...is greater than n.
Symbolize this as in the example above but use n variables, say they are all distinct and all satisfy 'H'.
• More than n are home.
• At least n+1 people are home.

The number of people at home...
Symbolizations:
...is less than 1.
~(%x)Hx
• No one is home.

...is less than 2.
~(%x)(%y)[~Ixy&(Hx&Hy)]
or
(^x)(^y)[(Hx&Hy)>Ixy]
• No two people are at home.
• There is at most one person home.

...is less than 3.
Like the above: write that there aren't three people ('~(%x)(%y)(%z)...')
or
that for any x,y,z at home, two of the pair are identical.
• No three people are at home.
• There are at most two people home.

...is less than n.
Like the above except you will need to use n variables.
• No n are at home.
• There are at most n-1 people home.

The number of people at home...
Symbolizations:

is exactly 1.
(%x)Hx &
~(%x)(%y)[~Ixy&(Hx&Hy)]
or
(%x)(^y)(Hy=Ixy)
• There is exactly one person at home.

is exactly 2.
(%x)(%y)(^z)[~Ixy
& (Hz=(IxzvIyz))]
• There are exactly two people at home.

is exactly n.
Can be done by conjoining the symbolization for "there are at least n people" and that for "there are less than n+1 people" (an example of this is the first symbolization for "exactly 1" above)
or
use the '=' (as in the case of exactly 2 just above).
• There are exactly n people at home.

Definite Descriptions

A definite description, e.g. "the person at home", may be symbolized as a name. That is how we symbolized in chapter six. But we can do better now that we have identity as a part of our symbolic language.

A definite description indicates that there is exactly one thing satisfying the description in question. And that, "exactly one", is something we have just learned to symbolize. For example,

(4) The person at home is sleeping.

indicates that there is exactly one person at home and that person is sleeping.

Symbolization of (4):  (%x)[(Hx&(^y)(Hy>Ixy))&Sx]

(Here 'Sx' symbolizes "x is sleeping" and we continue to assume a universe of discourse of people. So, our symbolization says that there is someone x who is at home, everyone at home is identical to x, and x is sleeping.)

 In general, "The P is Q" may be symbolized as '(%x)[(Px&(^y)(Py>Ixy))&Qx]'.

Exceptions in Quantification

One last use of identity described in the tutorials considered this example:

(5) All seniors except Chris are female.

Unfortunately, (5) is a bit ambiguous. It could mean

(5a) Chris is a senior non-female but every other senior is female.

or it might be seen to merely say:

(5b) All seniors distinct from Chris are female.

Can you see the difference between (5a) and (5b)? The first entails that Chris isn't female. But (5b) is about the others and so tells us nothing about Chris (Chris might be male or female as far as (5b) is concerned).

Symbolizing may make the difference clearer; use:

Fx: x is female
Sx: x is a senior

Both (5a) and (5b) require universal statements about "every senior other than Chris". To be a senior other than Chris is to be a senior distinct from Chris: 'Sx&~Ixc'. But (5a) says more, that Chris is a senior but not a female: 'Sc&~Fc'. So we get the symbolizations:

To symbolize (5a):
(Sc&~Fc)&(^x)[(Sx&~Ixc)>Fx]

and

To symbolize (5b):
(^x)[(Sx&~Ixc)>Fx]

Notice that only the first of these two says anything about Chris's gender.

Which is the best way to symbolize (5)? (5a) seems a little closer to what most of us would be thinking were we in situation to assert (5). But this may be more a matter of our likely knowledge (in such a situation) which might make it misleading to assert (5) if Chris were female. We'd likely know Chris was female and should state the more informative "All seniors are female".

But would (5) be not only misleading but also false if Chris were female? The reading as (5a) does entail that (5)'s falsity. But consider that in some cases one could state (5) while thinking "All seniors excepting Chris are female but I know nothing about Chris's gender". There's no contradiction in such thinking!

For this reason some argue that (5) itself means only (5b) and should be symbolized without taking sides about Chris's status. Because this latter understanding of meaning is closer to the modern categorical logic described in the last chapter, Café quizzes and exercises will assume the following minimal reading of an exception to a quantifier:

 All P except a are Q may be seen as having hybrid form: (*)   (^x)[(Px&~Ixa)>Qx]

On this view, the English quantifer "all P except a" means "all members of the set of P's which aren't a".

Also, "All P but a are Q" and "All P other than a are Q" can be symbolized with hybrid form (*).

Similarly,

 No P except a are Q may be seen as having hybrid form: (**)   (^x)[(Px&~Ixa)>~Qx]

Again, "No P but a are Q" and "No P other than a are Q" can be symbolized with this hybrid form (**).

#### 2. Predicate Logic with Identity (PLI): Syntax, Semantics, Derivation

Syntax

The syntax for our new predicate logic with identity, PLI, is easy to describe: We just use that of PL. The difference between PLI and PL consists in the conditions we put on the interpretation of identity.

Semantics

We add four principles of identity to the interpretation of 'I':

 (1) The relationship 'I' is reflexive: '(^x)Ixx' true in any interpretation, i.e., it's a logical truth. (2) The relationship 'I' is symmetric: '(^x)(^y)(Ixy>Iyx)' is logially true. (3) The relationship 'I' is transitive: '(^x)(^y)(^z) [(Ixy&Iyz)>Ixz)]' is logically true. (4) The substitution of one name for another name of the same object preserves truth.

In predicate logic with identity, interpretations are constrained to satisfy these four conditions.

Derivations

We add four rules of inference, one each for the four conditions on interpretations.

I1
input:

output:
(none) Iaa
I2
input:

output:
Iab Iba
I3
input:

output:
Iab
Ibc Iac
I4
input:

output:
Pa
Iab Pb

PDI: Call the extended system, PD+ together with these four identity rules, "predicate derivation with identity" or, simply, "PDI".

Here's an example derivation using all four identity rules:

 Premise 1 (Iab&Icb)&Ka Premise 2 (^x)(Ixx>(Kc>Kd)) 1 &E 3 Iab&Icb 3 &E 4 Iab 3 &E 5 Icb 5 I2 6 Ibc 4,6 I3 7 Iac 1 &E 8 Ka 7,8 I4 9 Kc 2 ^E 10 Iaa>(Kc>Kd) I1 11 Iaa 10,11 >E 12 Kc>Kd 9,12 >E 13 Kd

#### 3. Complex Names and Functions

We add a few additional symbols to the lexicon of PL in order to form PLIF; first four function symbols (which we call "functors"):

*,-,+,|

We could add more. But four will be more than sufficient for our purposes. (If we wanted an unending supply of functors, we could add subscripts as we do for predicates.)

Also, we add symbols for grouping. But instead of using '(' and ')' as we do in arithmatic, we'll avoid confusion with our regular use of parentheses by adding set brackets instead:

{,}

That's it for the additions to the lexicon.

We will use these new symbols to form complex names and variables. We'll call them "terms". The following are examples:

*a
{*a+b}
{{*a+b}+c}
-{{*a+b}+c}
{-{{*a+b}+c}|*c}

Now we need to give a more formal definition of a complex term (to generalize the names and variables we've used previously). But you now have the idea. We build them up as we once built up atomic sentences in sentence logic. (One exception: In SL we only had one and two place constructions. That limitation is not made on terms.)

An atomic term is just what we've been calling a term all along: a lower case letter (not including 'v').

We define terms in general inductively:

Any atomic term is a term.

If t,u,v,... are any terms, then so are '*t', '+t', '-t', '|t', (the one place functions), and '{t*u}', '{t+u}', '{t-u}', '{t|u}' (the two place functions) and '{t*u*v}', ...

We may now finish the definition of the syntax for PLIF, predicate logic with identity and functions: It is exactly the same as for PL (and PLI) except that we allow the complex terms as just defined.

The atomic formulas of PLIF are defined to include any uppercase letter 'A','B',...'Z' (except 'V') followed by any number of terms (now assumed to include the complex terms defined on the previous page).

The definitions of "formula", "free variable", "sentence", etc. remain unchanged from chapter six.

The semantics is a straigtforward extension of the semantics for PLI: we need to assign a function to each use of a functor. (As PLIF is defined, a sentence could "use" a functor as both a one place and two function symbol, for example. (Indeed terms like '{+a|{c+b}}' are well formed.) Then both uses would need to be assigned a distinct function by an interpretation.)

#### 4. An Example: Very Elementary Abstract Algebra

This section applies PLIF with identity to the simple case of group theory.

Group theory is a set of axioms true of a number of different collections of objects. You may first think of numbers when considering these axioms. But, as the tutorial describes, groups can be of many sorts.

The axioms in standard mathematician's language:

Group Theory

1. (^x)(^y)(^z) x+(y+z) = (x+y)+z (The order of applying the '+' operation is immaterial)
2. (%x)(^y) (x+y) = (y+x) = y (We may call the object x an identity element becuase it doesn't change y when '+' is applied to the two. We will prove that there is only one identity element for any group. Let's call it e.)
3. (^x)(%y) (x+y) = (y+x) = e (y is the inverse of x: we will prove that there is only one such inverse for any x and call it -x.)

In this section, we think about how to reformulate the axioms in PLIF and then do derivations. Thus, we try to make the mathematical reasoning very explicit.

First, here is the list of axioms reformulated slightly for PLIF:

Group Theory in PLIF

1. (^x)(^y)(^z) I{x+{y+z}}{{x+y}+z}
2. (%x)(^y)( I{x+y}y& I{y+x}y )
3. (^x)(%y) I{x+y}e & I{y+x}e

You should notice that these say exactly the same thing as the original set so long as 'I' is identity.

Finally, theorems can be proven in group theory. We take as premises any of the axioms of group theory together with any definitions we may give or previous (already proven) theorems. The resulting theorems are propositions that hold for any group, i.e., anything statisfying the axioms.

To reherse our example from the tutorial, first take the definition of a predicate true of identity elements:

Definition of 'E':   (^x)[ Ex = (^y)( I{x+y}y & I{y+x}y ) ]

With this definition, we can use PLIF to state that there is no more than one identity element:

Theorem 1: (^x)(^y)[(Ex&Ey)>Ixy]

We call this a theorem because it can be proven. We did so informally and in PDI in the tutorial. Here's the result:

 Premise 1 (^x)[Ex=(^y)(I{x+y}y&I{y+x}y)] Assumption 2 what if .............................. Ee&Ef 1 ^E 3 then ................................. Ee=(^y)(I{e+y}y&I{y+e}y) 2 &E 4 then ................................. Ee 3,4 >E 5 then ................................. (^y)(I{e+y}y&I{y+e}y) 1 ^E 6 then ................................. Ef=(^y)(I{f+y}y&I{y+f}y) 2 &E 7 then ................................. Ef 6,7 >E 8 then ................................. (^y)(I{f+y}y&I{y+f}y) 5 ^E 9 then ................................. I{e+f}f & I{f+e}f 8 ^E 10 then ................................. I{f+e}e & I{e+f}e 10 &E 11 then ................................. I{f+e}e 11 I2 12 then ................................. Ie{f+e} 9 &E 13 then ................................. I{f+e}f 12,13 I3 14 then ................................. Ief 2-14 >I 15 (Ee&Ef)>Ief 15 ^I 16 (^y)[(Ee&Ey)>Iey] 16 ^I 17 (^x)(^y)[(Ex&Ey)>Ixy]