In this lecture we are going to learn the basics of predicate logic. For this we are going to be building on the previous lectures about Propositional Logic and Set Theory. We will need to make use of the notation we have introduced for each of these topics, and we will also see some new notation. However, after this topic you will ave seen all the notation for logic that we will need in this module.

If you are not comfortable with at least the basics of both Propositional Logic and Set Theory, I recommend you go back and revise those before reading ahead to this lecture. If you see notation you do not recognise, you may need to check back to those lectures as it may have been introduced there.

In this lecture, we are going to pursue the goal of formalising and proving statements of natural language using formal logic. Previously, when we attempted this while learning propositional logic, we were very limited in the kinds of statements we could formalise. This was because we could only relate propositions to one another. We did not have the logical tools to 'look inside' the proposition itself and construct it of smaller parts. Subsequently we have seen Set Theory which allows us to construct propositions about entities and sets. We also saw that set theory lets us define functions as sets. Pulling this together, we can develop a more powerful logic, called Predicate Logic, which will let us formalise much more interesting claims.

Humans have a remarkable capacity to reason about the world. Philosophers have used this for thousands of years to try and understand the nature of the universe, and have used their capacity for reasoning to do so. However, for most of this time, the reasoning was done in natural, human language. One trouble that philosophers discovered was that language itself is ambiguous. Philosophers in the Vienna Circle, excited by advances in science and mathematics were among the first to attempt to formalise philosphy using modern formal logic.

Of course, it's not just philosphers who want to reason unambiguously about the world. When as computer scientists we wish to define algoritihms and software for interpreting and controlling the world around us, we need to be able to formalise logical reasoning so it can be performed by a machine. Furthermore, mathematics is reducable to logic, so logic gives is powerful tools for reasoning in mathematics. Predicate logic is also crucial for understanding languages: both formal languages and natural languages.

We have already encountered propositional logic. This logic, also known as Zero-Order Logic lets us reason about the relationships between propositions. Predicate logic, also known as First-Order Logic, significantly extends propositional logic by allowing us to quantify over sets. There are also so-called higher-order logics that extend predicate logic with the ability to quantify over predicates, however we will not cover those in this module.

So far the proposition has been the smallest unit of our logic. However, we have been unable to say what a proposition consists of. This limits what we can reason about using formal logic. To get past this, we need to understand the predicate.

We are going to start off by understanding the predicate and how we can use them to create propositions. For example, we will come to understand how to make claims such as "the cat is red". To do this, we will have to understand the nature of first order logic and what its symbols represent.

After this we will move on to formalising more complex natural language sentences in first order logic, including the use of quantifiers, such as "All cats are red".

We will apply this to the intensional definition of sets. Set comprehensions will allow us to define complex sets by giving rules of what they include.

We saw in set theory that we can define sets and entities. We don't need to just talk about things that exist in the real world. Indeed, it's often easier to imagine a simpler universe or model that contains a smaller, well defined number of entities. A Universe is the set of all entities that exist within a model. When we define a universe, we are saying what the entities are that we will be concerning ourselves with in our logic.

Imagine a universe that contains two entities, John and Mary. Suppose that John and Mary may or may not be cold or sleepy. As it happens, John is both cold and sleepy, and Mary is just cold but not sleepy, as indicated by the table below. There propositions that are true in this universe - claims that we could make that, given the entities are properties defined above, we can decide are true or false. For example "John is cold" is a true proposition. Similarly, there are propositions that are false, such as "Mary is sleepy". Consider the following true propositions:

1. Mary is cold
2. John is sleepy
3. Everyone is cold
4. Someone is sleepy

These propositions are not random; there is a pattern to them. We have named entities John and Mary. We have named properties: cold and sleepy. Each of our entities may or may not have any given property. That is, that a property holds of a given entity is either true or false -- it is a proposition. These properties we will call predicates.

Predicates allow us to make assertions - truth claims or propositions - about entities. A predicate is a function from one or more entities onto a truth value. So far we have seen one-place predicates, which are functions from a single entity onto a truth value. For example, in our universe we have an entity called John and it is true that John is cold. In other words, we asset that the 'cold' predicate is true of John, which we will write:

'Cold' is a one-place predicate as it takes a single argument. Because we passed this predicate a specific entity, and we have defined the properties that are true of this entity, we can treat the above statement as a proposition. We could construct a similar proposition for "John is sleepy". We can then use the operators of propositional logic for instance to construct the following compound proposition:

This proposition, which roughly translates as "if John is cold then John is sleepy", is true if John is both cold and sleepy. If John is not cold, this proposition is also true (if this is not obvious, look back at the definition of implication). It is only false when John is cold but he is not sleepy.

Set theory has given us tools to talk about sets of entities. Consider the set of entities we discussed above, but now lets assume that there are more than two people in the universe.

Using predicates, we can create propositions about the individual entities in our sets. However, we need to have a label to refer to them. We can only evaluate cold(\( x \)) if we know what $x$ is. However, it is very common to want to talk about any or all entities in a set. For instance, it should be true that "All members of \( P \) are cold". However, assuming $P$ is more than trivial in size, it would not be feasible to name each entity:

We want to generalise this conjunction of propositions to apply to every element of $P$; to say $cold(x)$ is true for all elements of P. To say this in predicate logic, we need to use a quantifier.

You will be introduced to quantifiers later in this lecture so don't worry if this doesn't make sense just yet. For now, just note that this lets us formalise much more interesting claims. Here we formalise the claim "All people who are cold are sleepy", or "For people, being cold implies being sleepy".

Note that in the universe described above, this claim is false.

You may or may not have noticed that above I have performed a trick of misdirection or slight-of-hand. Above we see a variety of different symbols arranged in strings. Each symbol must have a meaningRecall in propositional logic we had propositions \( p \), \( q \), $r$, etc., which stood in for some proposition. We had operators, such as \( \wedge \) and \( \implies \), which we defined completely by using truth tables.

So you might be wondering: what do "John", "Mary", "cold", and "sleepy" mean? These terms are not logical symbols. Indeed, they are non logical symbols.

Non-logical symbols only have meaning when given one by an interpretation. An interpretation is the assignment of meaning to symbols in a formal language. Consider the propositional logic statement \( p \vee q \). By itself it is true or false under an interpretation. An interpretation might be

• p is the proposition "1+1=2"
• q is the proposition "1+1=3"

Under this interpretation, the statement \( p \vee q \) is true.

Similarly, the statement \( \text{cold(John)}\implies \text{sleepy(John)} \) is true or false under an interpretation. The interpretation was provided by the table above, repeated here, makes this statement true:

There are two types of non-logical symbol in predicate logic: constants and predicates. "John" and "Mary" are constants, the only constants in the interpretation provided by this table. "Cold and sleepy" are the two predicates in this interpretation.

Understood in terms of set theory, constants are elements. Here we have the set of people. Our constants are elements

A predicate can be understood in multiple compatible ways.

A predicate is a function that takes a certain number of arguments and returns a truth value (i.e. true or false). For now, we will consider a predicate that takes one argument: \( \text{sleepy}(x) \). The function \( \text{sleepy}(x) \) returns either true or false, as defined by our interpretation. In any reasonable interpretation, this function would return true if x sleepy (whatever that means). For example, in the interpretation given by the table above:

A predicate also defines a set of elements for which the predicate is true. For instance, the predicate \( cold(x) \), in the interpretation given above, is the set \( \{John, Mary\} \). This is the set of all people in that interpretation who are cold. Checking whether a predicate holds of an entity (whether \( \text{cold}(x) \) is true) is the same as checking whether \( x \) is in the set \( cold \).

Both of these interpretations are correct. To use a fancy term, the predicate \( \text{cold}(x) \) is the indicator function of the set \( cold \). An indicator function of a set is a function that returns \( true \) if an element is in the set and \( false \) if it is not.

The number of arguments that a predicate takes is called its arity.

A predicate that takes one argument is called a one-place predicate. We have seen examples of one-place predicates already. These are properties of a single object, like "cold" and "sleepy". These are also called intransitive verbs. The set \( cold \) is defined by the set of elements (people) that are cold, in our interpretation, for example:

Two-place predicates are relations between objects that include all transitive verbs like "loves" and "equals". These are functions that take two arguments, for instance \( \text{loves}(x, y) \) is a two-place predicate. It is defined by a set of tuples \( (x, y) \), where \( x \) "loves" \( y \) (whatever that means in our interpretation). Let's extend our above interpretation to include the predicate "loves":

So under this interpretation, it is true that John loves Mary:

Three-place predicates take three arguments. They include ditransitive verbs such as "prefers" and "gave".

John gave Growltiger (the cat) to Mary

For instance, if in our interpretation, John gave Growltiger to Mary, the predicate \( gave(x) \) would be defined by the set:

What if instead of saying "John gave Growltiger to Mary" we wanted to say "John gave a cat to Mary"? This small change makes a surprising difference, yet being able to express this is necessary for our logic to be able to formalise human reasoning.

Why such a big difference? Growltiger is an entity, a non-logical constant that we define with an interpretation. This is not true of "a cat". We do not mean a particular cat, thus "cat" is not a constant like "Growltiger" is. Instead, we mean "a thing that is a cat". Written this way "cat" is a clearly a predicate: \( cat(x) \) would be true of things that are cats, just like \( blue(x) \) is true of things that are blue.

Yet while we could easily write "Growltiger is a cat" (\( \text{cat}(\text{Growltiger}) \)), we are still talking whether this particular thing is a cat. How do we express the idea of "a thing", or "something" separate from being a particular thing?

If the above does not make sense to you, do not worry. The key thing to recognise is that we need to use a variable. Let $x$ be a variable that stands for an entity in the universe of our interpretation (our domain of discourse). We will to say something like the following, but there is a crucial thing missing here:

We do not know what $x$ is. It is not a particular thing defined by our interpretation. Instead it is a logical symbol, a variable, that quantifies over a particular domain.

In the above $x$ is a free variable. As such there is nothing to give it meaning. We need to bind it, turning it into a bound variable, with the use of a quantifier.

There are two quantifiers in propositional logic, called the existential \( \exists \) and universal \( \forall \). They roughly translate to "there exists", and "for all". Their symbols are:

We will see them both below.

Quantifiers in propositional logic bind a variable. For example, we might bind the variable \( x \) with the existential quantifier as shown below. Then, whenever $x$ appears in the quantified proposition (which is here \( \text{cat}(x) \)), it would take whatever values given to it by the quantifier:

Here, by using the existential quantifier, we claim that there is at least one possible assignment to \( x \) that satisfies the proposition \( \text{cat}(x) \). In other words, it is the proposition there exists at least one cat (in the domain that \( x \) is drawn from).

Let's make this domain explicit with the following interpretation. John, Mary, and Growltiger are entities in our domain of discourse and \( \text{cat}(x) \) is a predicate that is true only of Growltiger:

We can visualise this as a table:

It is true that that at least one of the entities in $A$ is a cat (the notation will be explained in detail later on):

Note that this is equivalent to the following disjunction:

That is, if there exists a cat in our set \( A \), then it must be true that one of the elements of set $A$, being either John, or Mary, or Growltiger, is a cat. From our knowledge of disjunction, we know that so long as the claim \( \text{cat}(x) \) is true for at least one of these entities, the disjunction of the statements will be true.

Thus the existential quantifier is a way of expressing a disjunction over all the elements of a set.

The universal quantifier is the second of the two quantifiers of predicate logic. It is written with the symbol \( \forall \) which should be read "for all".

Let us consider for a moment the claim that all entities in our domain of discourse are cats: "Everything is a cat". In other words, the predicate \( \text{cat} \) is true for every element of \( A \). For this we need to use the universal quantifier:

The universal quantifier means that for all possible assignments of $x$, given the domain specified, the quantified proposition is always true. It is the same as the conjunction.

From our knowledge of conjunction, we know that all of these conjoined propositions must be true for the overall proposition to be true. Thus the universal quantifier is a way of expressing a conjunction over all elements of a set.

As you have seen, a quantified statement of logic has the following form, where \( Q \) is a quantifier, \( x \) is a variable, and $P$ is a proposition. We usually specify the domain of quantification by writing $\\in S$, where \( S \) is a particular set that has been defined. This clarifies that \( x \) will only take values from $S$. However, this is sometimes omitted if the domain is obvious.

Such quantified statements are themselves propositions, thus there is nothing stopping us nesting a quantified statement of logic inside another quantified statement of logic. For instance, imagine \( P \) is a set of customers at a cafe, and \( F \) is a set of foods on the menu. We might assert that for every customer, there is at least one food that they eat. Here we have two variables $x$ and \( y \), bound by different quantifiers. (Note that eats\( (x, y) \) is a two-place predicate, because it takes two arguments.)

There is a common shorthand that exists for when we are nesting the same quantifier. If we wished to claim that every customer eats every food on the menu - that eats\( (x,y) \) is true for every assignment of \( x \) and $y$, where \( x \in P \) and \( y \in F \) - we could write:

All of the variables within the proposition need to be bound by a quantifier. Unbound variables are called $1. In eats(John, y) there is one free variable, $y$. This is not a proposition as we cannot resolve it to a truth value. By binding this variable with a quantifier, it becomes a proposition: $(\exists y) (eats(John, y))$.

We have already seen how to define a set extensionally, e.g. \( A = \{a, b, c\} \). However, this can be verbose for large sets. It also prevents us defining sets whose elements we are not in a position to list. Indeed, we might want to reason about sets where we cannot list all the elements.

For such a set we must give an intensional definition. To do this, we define a rule that distinguishes between those that should be contained in the set and those that should not. For instance, if I say $B$ is the set of odd numbers, you could identify what belongs in that set and what does not. By enumerating and testing all possible numbers against this rule, you could in principle list everything the set should contain.

The syntax for (that is, way of writing) intensional definitions is called a set comprehension. It is constructed from three parts.

In the declaration, we list a variable (or combination of variables) to enumerate. These variables may be specified with a type. Then there is a vertical bar or pipe character (\( \mid \)), generally read "such that". Then we give a proposition. In practice, this proposition describes one or more properties that our variables must satisfy to be included in the set we are defining. Finally, in the term we specify what goes into the set we are defining.

For example, to define a set containing the natural numbers (denoted by \( \mathbb{N} = \{1, 2, 3, \dots \} \)) greater than 3, we could write:

This could be read "The set of all \( x \)s, where \( x \) is an natural number, such that \( x \) is greater than 3." Here we:

1. enumerate all of the integers;
2. give a proposition that is true only when the current integer is greater than 3; and
3. add the integer to the set.

If we chose to, we could define a different term. For instance, we could include in the set the sum of $x$ and $y$.

Or we could include a tuple:

Or we could include a set:

Using a term is one way in which we can decide what ends up in the set we are defining.

We often do not need to specify a term. If we do not specify a term, by default we assume the characteristic tuple is added to the set. For instance, above we could have written \( \{ x : \mathbb{N} \mid x > 3 \} \) as here the characteristic tuple is $x$.

1. If we have a single variable (e.g. $x$), the characteristic tuple is that variable (e.g. $x$).
2. If we have multiple variables, (e.g. $x; y$), the characteristic tuple is the tuple of those variables (in the order they appear) (e.g. $(x, y)$).

All of the following define the same set, being the set of tuples $(a, b)$, where $a$ and $b$ are natural numbers, i.e. \( \{(1, 1), (1, 2), (2, 1), (2,2) ,\dots \} \). They can be understood to do this in different ways. The former enumerates the integers twice (for the variables $x$ and $y$) and specifies a term. The next is the same but returns the characteristic tuple. The latter enumerates pairs of integers, and returns each pair.

When we choose variables in our declaration, we give their type. A type is, more or less, the set that limits that values a given variable can take. You may be familiar with the concept of a type in programming languages: a variable with the type number can only take values that are numbers. Types are written using a colon. The following should be read "variable $a$ of type \( \mathbb{N} \)"

Here we have said that $a$ can only take values that are natural numbers (\( \mathbb{N} \) means the set of natural numbers). In other words, $a$ must always be an element of \( \mathbb{N} (a \in \mathbb{N} \)). If we wished $a$ to only take values in \( \mathbb{P}(\mathbb{N}) \) (i.e. we wanted $a$ to be a set of natural numbers), we could write:

A variable's type can also be the cartesian product of multiple types. If a variable's type is a cartesian product, the values that variable can take will be tuples. In the expression below, the variable $a$ could take values including \( \{ (0,0), (0, 1), (1, 1), (0, -1), ... \} \).

When writing set comprehensions for variable types that are cartesian products, it is sometimes necessary to reference particular positions within a tuple (e.g. the first, second or third item it contains). Should we want identify a particular position within a tuple we can use the notation $a.n$, where $n$ is the position (with the first element of the tuple being position 1).

In the above example, we enumerate pairs of natural numbers \( \{(2,1), (3, 1), (3, 2), (4, 1), \dots \} \). We check that the first item of the pair (tuple) is greater than the second, if so the pair is natural numbers in our set; if not, we do not include it in our set.