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.

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:

1. All men are mortal.
2. Aristotle is a man.
3. Therefore, Aristotle is mortal.

Let us try to symbolize this in propositional logic:

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

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 yet show how predicate logic succeeds in demonstrating the validity of the argument; this will be made clearer to the reader in subsequent sections.

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.

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.

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.

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:

1. Every atomic formula is a well formed formula.
2. If $\mathscr{A}$ is a well formed formula, then $\neg \mathscr{A}$ is also a well formed formula.
3. If $\mathscr{A}$ and $\mathscr{B}$ are well formed formulae, then $(\mathscr{A} \wedge \mathscr{B})$ is also a well formed formula.
4. If $\mathscr{A}$ and $\mathscr{B}$ are well formed formulae, then $(\mathscr{A} \vee \mathscr{B})$ is also a well formed formula.
5. If $\mathscr{A}$ and $\mathscr{B}$ are well formed formulae, then $(\mathscr{A} \to \mathscr{B})$ is also a well formed formula.
6. If $\mathscr{A}$ and $\mathscr{B}$ are well formed formulae, then $(\mathscr{A} \leftrightarrow \mathscr{B})$ is also a well formed formula.
7. 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.
8. 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 proposition if it has no free 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.

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 spy using 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:

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

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 least n, at most n, or exactly n things satisfying the predicate.

	one	two
at 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.

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:

1. $\exists x K x$ There is a king of France
2. $\forall x \forall y ((Kx \wedge Ky) \to (x = y))$ There is at most one king of France
3. $\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.

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$: