# Predicate Logic

**Predicate logic**, **first-order logic** or **quantified logic** is a formal language in which propositions are expressed in terms of predicates, variables and quantifiers. It is different from propositional logic which lacks quantifiers.

It should be viewed as an extension to propositional logic, in which the notions of truth values, logical connectives, etc still apply but propositional letters(which used to be atomic elements), will be replaced by a newer notion of proposition involving predicates and quantifiers.

#### Contents

## Why propositional logic was not enough?

Predicate logic is superior to propositional logic in the sense that it is able to capture the structure of several arguments in a formal sense which propositional logic cannot.

We'll illustrate this with an example.

Consider the following famous argument:

- All men are mortal.
- Aristotle is a man.
- Therefore, Aristotle is mortal.
Let us try to symbolize this in propositional logic:

\[\begin{align} A: &\text{ All men are mortal.} \\ B: &\text{ Aristotle is a man.} \\ C: &\text{ Aristotle is mortal.} \end{align}\]

The argument becomes

\[\frac{A, \; B}{\therefore C}. \]

This is a completely invalid argument in propositional logic since A, B and C have no relations to each other.

Note that the problem isn't with the symbolization of the argument. In fact, this is the best symbolization propositional logic can offer for these statements.

We do not show how predicate logic accomplishes to show the validity of the argument yet, but will be clearer to the reader in subsequent sections.

## Predicates

Predicates are a fundamental concept in mathematical logic. Predicates express similar kinds of propositions involving it's arguments.

Simplest predicates are the ones expressing properties of things.

\[Ax \text{: } x \text{ is tall} \]

Or it could have two places like

\[Bxy \text{: }x \text{ owes money to } y\]

Or several places like

\[Cxyz \text{: }x \text{ borrowed } y \text{ from } z\]

The predicates with one argument, two arguments, or in general \(n\) arguments are referred to as *monoadic*, *dyadic* or *n-adic* respectively. You might realize that predicates are a generalization of Relations

As with the convention followed above, it is usually customary to denote the predicates with capital letters, the variable arguments with \(x, y, z, \cdots\) and constants with \(a,b,c, \cdots\). The notion of variables and constants will be clearer in the subsequent discussions.

An important comment I should make about using propositions is that the arguments of the propositions are meant to be *singular terms*, i.e, a specific object as opposed to a class or its representative.

The following is not a valid way to form propositions in predicate logic

Symbolization key

- \(Ax: x \text{ bark(s)}\)
- \(d: \text{ dogs}\)
\(\)

\(Ad\)

That is because \(d\) refers to "dogs" which is not just one particular object, but the entire set of dogs. The correct way to express these propositions is through

quantifiers, which we will explore next.

The set of objects in the Universe of Discourse (see below) which satisfy a predicate is called the **extension** of the predicate. A predicate whose extension is the empty set is called an **empty predicate**.

## Quantifiers

The other most important notion in predicate logic is the notion of *quantifiers*, which is why we also call it the *quantified logic*. The quantifiers give us the power to express propositions involving entire sets of objects, some of them, enumerate them, etc.

Before we discuss quantifiers in more detail, we must talk introduce the notion of the **Universe of Discourse**. The universe of discourse(UD) is a set of all the things which we plan to talk about when we make formal propositions. Usually the universe of discourse is obvious, but when we need to, we'll make it explicit in the symbolization key.

#### The Universal Quantifier \( ( \forall ) \)

The universal quantifier let's us apply a predicate to *all* members of the universe of discourse. Essentially it let's us say things like *Everyone is happy*, or *all numbers are divisible by 1*.

It is denoted by the symbol \(\forall\), read *for all*

Symbolization Key

- UD: All people
- \(Hx\) : \(x\) is happy
We could say \[\forall x H x\] to mean that everyone is happy

Symbolization Key

- UD: \(\mathbb{N}\)
- \(Dxy\) : \(x \mid y\)
We could say \[\forall n D1n\] to mean that all natural numbers are divisible by 1.

A clever reader might notice that the usual convention is to say \(\forall n \in \mathbb{N}, 1 \mid n\). While this is also structurally equivalent to predicate logic, we'll stick to our own formalism for this wiki instead of the shorthands.

#### The Existential Quantifier \( ( \exists ) \)

The existential quantifier guarantees that the quantified predicate applies to *at least one* of the members of the UD. We could use it to say things like *Somebody in this room can dance*, or *some day Agnishom will die*

It is denoted by the symbol \(\exists\), and is usually read *there exists*

Symbolization Key

- UD: People in this room
- \(Dx\) : \(x\) can Dance
We could say \[\exists x D x\] to mean that there exists someone (at least one), who can dance.

Symbolization Key

- UD: All the days
- \(Dx\) : \(x\) is day when Agnishom dies
We could say \[\exists x D x\] to mean that Agnishom will die some day.

## Combining Quantifiers

Quantifiers can be combined together to form propositions.

A common example is the *for all, there exists* clause.

Let the UD be \(\mathbb{R}\) and let \(Lxy\) mean \(x\) is less than \(y\)

We say, \(\forall x \exists y L x y\), to mean that for every real number there is some real number less than the number itself.

It might be tempting to think that the \(\forall\) and \(\exists\) can always be switched in such a construct, but this is not necessarily so.

Let \(Lxy\) mean \(x\) likes \(y\)

\(\exists x \forall y Lyx\) means that there is somebody who everyone likes.

However, \(\forall x \exists y Lyx\) means that for everybody, there is someone who likes them.

Another common combination of quantifiers is to queue together existential or universal quantifiers like \(\exists x \exists y \exists z \cdots\) and \(\forall x \forall y \forall z \cdots\) respectively, to mean *for all x,y,z..* or *there exists x,y,z,...*. This is often written as a shorthand as \(\exists x,y,z\) or \(\forall x,y,z\)

Let \(Dx\) mean \(x\) is a dog. Let \(Oxy\) mean that \(x\) owns \(y\)

Then \(\exists x \exists y ( Dx \wedge Oyx) \) means somebody owns a dog

The **scope** of a quantifier is the part of the sentence to which the quantifier applies. If necessary, we modify the scope using parantheses We'll make this clearer through an example.

Consider the following symbolization:

UD:People- \(Gx\): \(x\) can play the guitar
- \(l\): Lemmy
In the expression \(\exists x G x \to Gl\), the scope of the quantifier \(\exists\) is the expression \(Gx\). This translates to

If there is a guitarist, Lemmy is a guitarist.However, if we say \(\exists x (G x \to Gl ) \), we have changed the scope of the quanitifier to the entire expression. The sentence now means,

There is a person \(x\) such that if \(x\) is a guitarist, Lemmy is a guitarist.

You might notice that this sentence is true because non-Guitarists exist. For example, let \(p\) be Agnishom. \(Gp \to Gl\) is true since the conditional in which the antecedent is false is always true. (Agnishom does not play the guitar). Since someone, namely \(p\), satisfies the sentence, \(\exists x (G x \to Gl ) \) is true.

A variable which is not bound to the scope of any quantifier is called a **free variable**. An expression can only be a proposition if none of it's variables are free, as we'll see in the next section.

## Formal Definitions

In this section, we'll develop a rigorous recursive definition of propositions or sentences in predicate logic by going through an organizational hierarchy.

- Predicates, constants, variables, logical connectives, parentheses and the quantifiers are referred to as
**symbols**. - An
**expression**is a string of*symbols*. - A
**term**is either a constant or a variable. - An
*n-adic predicate*followed by \(n\)*terms*is called an**atomic formula**. - An atomic formula is an
**well formed formula**(wff) if and only if it satisfies the following definition:

- Every atomic formula is a well formed formula.
- If \(\mathscr{A}\) is a well formed formula, then \(\neg \mathscr{A}\) is also a well formed formula.
- If \(\mathscr{A}\) and \(\mathscr{B}\) are well formed formulae, then \((\mathscr{A} \wedge \mathscr{B})\) is also a well formed formula.
- If \(\mathscr{A}\) and \(\mathscr{B}\) are well formed formulae, then \((\mathscr{A} \vee \mathscr{B})\) is also a well formed formula.
- If \(\mathscr{A}\) and \(\mathscr{B}\) are well formed formulae, then \((\mathscr{A} \to \mathscr{B})\) is also a well formed formula.
- If \(\mathscr{A}\) and \(\mathscr{B}\) are well formed formulae, then \((\mathscr{A} \leftrightarrow \mathscr{B})\) is also a well formed formula.
- If \(\mathscr{A}\) is an well formed formula, and \(\mathscr{x}\) is a variable, \(\mathscr{A}\) contains at least one occurence of \(\mathscr{x}\), and \(\mathscr{A}\) contains no \(\mathscr{x}\) quantifiers, then \(\forall \mathscr{x}\mathscr{A}\) is also a well formed formula.
- If \(\mathscr{A}\) is an well formed formula, and \(\mathscr{x}\) is a variable, \(\mathscr{A}\) contains at least one occurence of \(\mathscr{x}\), and \(\mathscr{A}\) contains no \(\mathscr{x}\) quantifiers, then \(\exists \mathscr{x}\mathscr{A}\) is also a well formed formula.

- Finally, we are ready to define a proposition as follows:

A well formed formula is a

propositionif it has nofree variables

- Just to be more rigorous, we formally define
**scope**again: The scope of the quantifier is the subformula for which the quantifier is the main logical operator.

## Identity

We could extend predicate logic by talking about identity, something we are all familiar with. The identity \( = \) is actually a two place predicate which tells us that a given term can always be replaced by the other. Because identity is an equivalence relation, it is symmetric, transitive and reflexive,

It lets us express some propositions which we otherwise would not have been able to

Express

Liz is the tallest spyusing a suitable formulation in Predicate Logic

Let the UD be all people. Let \(Sx\) mean that \(x\) is a spy and \(Txy\) mean that \(x\) is taller than \(y\). Let the constant \(l\) refer to Liz.

\[\forall x ( (Sx \wedge \neg (x = l)) \to Tlx ) \]

This actually says, someone is a spy, but not Liz, Liz must be taller than her. We needed to use the identity predicate because Liz is not taller than herself.

Use suitable symbolization to translate the following to Predicate Logic:

- Every logician loves someone other than himself.
- The only one who respects Richard is Sue.

## Enumeration using Identity and Quantifiers

If you had tried the last exercise, you probably can do this yourself.

Let \(Px\) be some predicate. We'll see how one could express several ideas of quantity involving natural numbers using predicate logic, namely we will express that there are

at leastn,at mostn, orexactlyn things satisfying the predicate.

onetwoat least\( \exists x P x \) \( \exists x \exists y (Px \wedge Py \wedge \neg (x = y) ) \) exactly\( \exists x ( Px \wedge \forall y (Py \to (y = x) ) ) \) \( \exists x \exists y (\neg (x = y) \wedge Px \wedge Py \wedge \forall z (Pz \to (z = x) \vee (z = y))) \) at most\( \forall x \forall y ((Px \wedge Py) \to (x = y)) \) \( \forall x \forall y \forall z((Px \wedge Py \wedge Pz) \to ((x = y) \vee (x = z) \vee (y = z))) \)

The reader could try exploring why these propositions have the claimed translation in English and try out the same for three or more.

## Definite Descriptions

Descriptions which are not suitable for representing a constant in predicate logic are **indefinite descriptions.** For example, in the sentence *some dog is annoying*, *some dog* is an indefinite description.

All other descriptions are *definite*. If there is something that actually fits the description of the term, the fitting object is called the **referent** of the term. However, it is possible to construct sentences with terms that do not refer to anything, in which case the term itself is called a **non-referring** term.

Consider the sentence

The king of France is bald.We could symbolise this as follows:

- \(Bx\): x is Bald
- \(k\): king of France
\[Bk\]

The problem with \(k\) is that it is a non-referring, since there is no king of France

The problem arises when we try to evaluate the truth value of the sentence. If we consider the extension of the *being bald* predicate, the *king of France* is not in them, since there is no such person. Considering the negation of the statement, *The king of France is not bald*, does not seem to be true either, since the *king of France* is not in the extension of *not bald* either, using the same logic. That seems to be a violation of the law of excluded middle.

One proposed solution is to interpret the sentence in three valued logic, where non referring terms yield a third kind of logical value.

Bartend Russel's *Theory of Descriptions* formalises the negation of the statement in the following way:

Let \(Kx\) mean \(x\) is the king of france.

Then, the original statement is the conjunction of the three following statements:

- \(\exists x K x\) There is a king of France
- \(\forall x \forall y ((Kx \wedge Ky) \to (x = y))\) There is at most one king of France
- \( \forall x (Kx \to Bx) \) Anyone who is a king of France is bald

In essence, \[ \exists x ( Kx \wedge Bx \wedge \forall y (Ky \to (x=y)))\]

The negation of the statement could either mean, \[ \neg \exists x ( Kx \wedge Bx \wedge \forall y (Ky \to (x=y)))\], in which case the negation is true, since there really isn't such a King.

Or, it could mean \[ \exists x ( Kx \wedge \neg Bx \wedge \forall y (Ky \to (x=y)))\], in which case the negation is False, by the same reasoning.

## Proofs in Predicate Logic

This section is incomplete. You can help by completing it and adding more examples.

To prove a conclusion from a set of premises, is a transformation of the propositions using certain inference rules. This abstraction of the formulation of arguments is one of the central themes in formal logic.

In addition to the proof rules already etablished for propositional logic, we add the following rules:

**Universal Elimination \(\forall E\):**If \(\mathscr{A}\) is a formula containing \(\mathscr{x}\), \(\forall x \mathscr{A}\) can be replaced by \(\mathscr{A} \boxed{\mathscr{x} \implies \mathscr{c}}\), i.e, all instances of \(\mathscr{x}\) replaced with \(\mathscr{c}\)**Existential Introduction \(\exists I\):**If \(\mathscr{A}\) is a formula containing \(\mathscr{c}\), \(\mathscr{A}\) can be replaced by \(\exists \mathscr{x} \mathscr{A} \boxed{\boxed{\mathscr{c} \implies \mathscr{x}}}\), i.e, one or more instances of \(\mathscr{c}\) replaced with \(\mathscr{x}\)**Existential Elimination \(\exists E\):****Universal Introduction \(\forall I\):****Quantifier Negation \(QN\):**If \(\mathscr{A}\) is a formula containing \(\mathscr{x}\), \(\forall \mathscr{xA}\) can be replaced by \(\neg \exists \mathscr{x} \neg \mathscr{A}\) and, \(\exists \mathscr{xA}\) can be replaced by \(\neg \forall \mathscr{x} \neg \mathscr{A}\)**Identity Introduction \(=I\):**One can always add the premise \(\mathscr{c} = \mathscr{c}\)**Identity Elimination \(=E\):**