CMSC 27100 — Lecture 3

Predicates and first-order logic

One problem that we run into very quickly is that propositional logic is not quite powerful enough for our needs. For instance, if I wanted to say something like

$x$ is odd and $x$ is less than $y$

then I can define propositions for them. For instance, $p$ can be “$x$ is odd” and $q$ can be “$x$ is less than $y$”. This would give us the statement $p \wedge q$.

But this is not very satisfying or helpful. We see that there’s no way to express the fact that the two different propositions are really talking about the same $x$. Why is that? The problem lies in the fact that propositional logic is about propositions but what we really care about are not the propositions themselves but what we can say about things: numbers, vectors, functions, cars, dogs, and so on.

So if we want a language to talk about things, we need to expand our language a bit further. We will be discussing predicate or first-order logic.

First, we need to determine a domain of discourse: what are the things that we want to talk about? This can be something like the natural numbers $\mathbb N$ or the integers $\mathbb Z$ or matrices or functions or graphs and so on. There’s also nothing stopping us from making our domain the set of all dogs, if what we really wanted to do was express statements about dogs, or other “real-world” types of objects. (This occurs less in math but more in places like database theory.)

Then, we want to express properties and relationships about the objects in our domain. For this, we need to define predicates. Predicates are written $P(x_1, x_2, \dots, x_k)$ and can be thought of as statements about things $x_1$ through $x_k$.

Suppose our domain is the natural numbers. Let’s try to express $x$ is odd and $x$ is less than $y$ as a sentence in predicate logic. We will define the following predicates.

This is enough to get us something like $P(x) \wedge Q(x,y)$ for the example statement from above. Notice that we are able to say that $x$ is the same among the two statements and that we’re able to relate $x$ and $y$. Observe also that what we typically call “relations”, like “less than”, are really predicates. For instance, $=$ (equality) is another example of a predicate.

But what are $x$ and $y$? At this point, they are both not anything at all and at the same time can be anything. This is because they are variables to which we have not given any meaning. They are still quite useful at this point because they give us a way to name things. But one way we can use them is to set them (using other predicates), say like $x$ is 3 and $y$ is 5.

However, we often want to say more general things than that. Since we have a domain of discourse, we often want to make claims about various objects in the domain. We want to say that all of the things have some particular property or that there are objects that have various properties. Such statements quantify over our domain, so we define quantifiers to talk about them.

The symbol $\forall$ is called the universal quantifier and is read “for all”. The statement $\forall x P(x)$ is true if and only if $P(x)$ is true for every element $x$ in the domain.

The symbol $\exists$ is called the existential quantifier and is read “there exists”. The statement $\exists x P(x)$ is true if and only if $P(x)$ is true for at least one element $x$ in the domain.

Basically, we use $\forall$ when we want to make a statement about all objects in our domain (“every dog is a good boy”) and we use $\exists$ when we want to say that there is some object out there in our domain that has a particular property (“there is a dog that can play Jenga”).

Suppose our domain is the integers $E(x)$ is the statement “$x$ is an even number”. We can use predicates and quantifiers together with the logical connectives we introduced with propositional logic to say things like $\forall x (E(x) \rightarrow \neg E(x+1))$, which says that “for every integer $x$, if $x$ is even, then $x+1$ is not even”.

We can define statements that relate more than one object. Suppose our domain is the natural numbers and $L(x,y)$ is the statement “$x$ is less than $y$”. We can consider the following proposition: $$\forall x \exists y L(x,y).$$ This reads “for every natural number $x$, there exists a natural number $y$ such that $x \lt y$”. This statement turns out to be true: every natural number does have some other natural number that it’s less than. Now, let’s consider the following similar statement, where the order of the quantifiers is reversed: $$\exists y \forall x L(x,y).$$ Here, we’re saying that there is a natural number $y$ for which every natural number $x$ is less than it. In other words, this says that there is a “biggest” natural number, which is obviously not true. As we can see, the order of the quantifiers matters.

A point about notation here. Notice that we write $\forall x P(x)$, which leaves the domain implicit. This is technically the correct way to write this—in mathematical logic, the domain of discourse is typically fixed beforehand. However, you may sometimes see such statements written as $\forall x \in \mathbb R, P(x)$, if the writer wanted to use $\mathbb R$ as the domain. This is not really necessary if the domain is $\mathbb R$, but what if the domain was something like $\mathbb C$ instead? Technically speaking, $\forall x \in \mathbb R$ is really shorthand for something like $\forall x (R(x) \rightarrow P(x))$, where $R(x)$ would be a predicate for “$x$ is a real number”. Pretty much everyone outside of logicians will abuse notation like this.

Let’s try formalizing a more substantial statement. We’ll switch to the domain of the integers and discuss the notion of divisibility. Division on integers is an interesting operation even though we’ve likely been dividing numbers since childhood without thinking about it too much. However, where it does come back to trip us up again is when we start to learn how to program. This usually comes in the form of trying to divide two numbers and then remembering that dividing two integers doesn’t always give you an integer.

Let $a$ and $b$ be integers. We say that $a$ divides $b$, written $a \mid b$, if and only if there exists an integer $n$ such that $a \cdot n = b$. We also say that $b$ is a multiple of $a$.

We say that $4$ divides $8$, since there is an integer, $2$, such that $4 \times 2 = 8$. Similarly, $3$ divides $15$, since $3 \times 5 = 15$.

Divisibility is often confused with division. Notice that from above, we have $4 \mid 8$ and $3 \mid 15$. It would be incorrect to say “4 divided by 8”.

We can try to express this formally. Our domain is the integers and we assume that we know basic properties or axioms about integers, like how we know they’re equal and how we can multiply them.

We have two integers, $a$ and $b$. These integers are arbitrary, so the entire statement will be universally quantified. Then notice that $a \mid b$ is really a predicate: it’s a statement about $a$ and $b$. We would like to relate this predicate to more basic operations—in particular, that there’s an integer $n$ for which we have $a \cdot n = b$. Equality is also a predicate, which is comparing two things, $a \cdot n$ and $b$. Since this is an existential statement, we can write this as \[\exists n (a \cdot n = b).\]

Now, we want to define the predicate $a \mid b$ so that it is true if and only if there is an integer $n$ for which $a \cdot n = b$.

The connective “if and only if” is not one of the connectives we introduced, but we can construct it using what we’ve already seen. We say that $p$ if and only if $q$ whenever $p \rightarrow q \wedge q \rightarrow p$. Sometimes this is also written $p \leftrightarrow q$. This means our definition can be rendered formally in the following way: \[\forall a,b (a \mid b \leftrightarrow \exists n (a\cdot n = b)).\]

In order to explore more about proof and logic, we’ll soon be working more with definitions like this. Our focus will be on the field of elementary number theory, which is the study of the integers.

Proof

So far, we have covered how to say things, but ultimately, what we want to do is verify whether a statement is true or not. This is done by means of proof. Informally, a proof is really just an argument that a statement is valid based on some premises.

In mathematics, the premises are a set of facts, like “For all natural numbers $m$ and $n$, $m+n = n+m$” (that is, addition on the natural numbers is commutative). In very formal settings, we are extra careful to specify exactly which facts we “know” already—these are called axioms. Then, if we apply those facts in certain ways which are described by some rules, we can arrive at some statement, which we know must be true because we followed the rules.

For example, consider the following proposition.

For all integers $a$, $b$, and $c$, if $a \mid b$, then $a \mid bc$.

What is this statement trying to say? First, we take any three integers $a, b, c$. If it so happens that $a \mid b$, then we are guaranteed that $a \mid bc$.

Let’s try this. Take $a = 10, b = 7, c = 23$. Well, $10 \nmid 7$, so the statement is still true.

Now, what about $a = 5, b = 10, c = 7$? Here, we have $5 \mid 10$, since $5 \times 2 = 10$. Does $5 \mid 10 \times 7$? We have that $10 \times 7 = 70$ and with some work, we can figure out that $5 \times 14 = 70$, so we do have that $5 \mid 10 \times 7$ as promised.

So we have at least one example that works, but how do we prove that the statement is always true?

First of all, notice that within this statement, there are some facts that we need to know already in order to work with if we want to “prove” this statement. We must know facts about integers and the predicate for divisibility, $\mid$.

Here is a list of facts that we take to be true about integers.

Name Property
Closure under addition For all integers $a,b$, $a+b$ is an integer.
Associativity of addition For all integers $a,b,c$, $(a+b)+c = a+(b+c)$.
Commutativity of addition For all integers $a,b$, $a+b = b+a$.
Additive identity There exists an integer 0 such that for all integers $a$, $a+0 = a$.
Additive inverse For all integers $a$, there exists an integer $-a$ such that $a+(-a) = 0$.
Closure under multiplication For all integers $a,b$, $a \times b$ is an integer.
Associativity of multiplication For all integers $a,b,c$, $(a \times b) \times c = a \times (b \times c)$.
Commutativity of multiplication For all integers $a,b$, $a \times b = b \times a$.
Multiplicative identity There exists an integer 1 such that for all integers $a$, $a \times 1 = a$.
Distributivity of multiplication over addition For all integers $a,b,c$, $a \times (b+c) = (a \times b) + (a \times c)$.

You don’t need to memorize these—all these facts really say is that addition and multiplication on integers works the way that you’ve known all along. But it is interesting to note and useful to be aware that we can list these facts and that we rely on them, even if we weren’t aware of it.

As an aside, these rules define an algebraic structure known as a ring.

What then is a formal proof in this context? This is something that the mathematcians of the late 19th century tried to nail down using logic. We might render the above statement as something like \[\forall a,b,c(a \mid b \rightarrow a \mid bc).\] What constitutes a proof of this? Well, we need a way to “prove” a statement that’s universally quantified and how to deal with an implication. In other words, the form of the statement determines the rules that we apply to come up with our argument, or proof.

Notice that if we have everything set up, we don’t actually need to “know” what our predicates “mean”, since the validity of the proof is determined totally by the form of the sentence. What this means is that in the most formal versions of this process, we get to the level of manipulation of symbols, akin to string rewriting. It’s not hard to see that when we get to this level, a proof really becomes something like a program, with strict rules that can be checked and validated.

We want to approach less formally, so what we are trying to do is begin with a set of statements that represent facts that we already know and try to apply rules to these facts so that we can construct a “true” statement by the end of the process. Any statement that we can arrive at by following these rules is considered “valid” and the steps that we take constitute the proof.