So now that we are fairly comfortable with propositional logic, it is time to consider its limitations. Many of you will remember running up against this with the Gordon Ramsay question from the first assignment. It would be very nice if there were a way to talk about things and how they are related.
Let's consider the following statements.
These are propositions, just like we're used to and we know that If Gordon Ramsay took CS 245 and Gordon Ramsay did not pass CS 245, then Gordon Ramsay failed CS 245 and we can express it as a formula $((p \wedge (\neg q)) \rightarrow r)$. This is a perfectly fine proposition of the kind that we've been dealing with.
However, Gordon Ramsay is not the only person who took CS 245. For example, I took CS 245 many, many years ago and luckily I passed it. And you are all taking CS 245 right now and so we could express the same kinds of statements for all of us. So what if we want to do that? Then we would have to define a set of propositional variables for each of us:
and we would be able to condlude $((p_1 \wedge (\neg q_1)) \rightarrow r_1)$. And we can repeat this process for all 101 of you currently enrolled in this section.
Just like back when Gordon Ramsay whipped up a hundred dishes for us (back when he wasn't taking CS 245 and busy with studying for the midterm) and we didn't have one of them, we need to cook up a ton of propositional variables to express this not-very-complicated relationship between taking, passing, and failing CS 245. Now, the nice thing about Gordon Ramsay cooking a hundred dishes is that he stopped at a hundred. How many students will take CS 245? We have a pretty good idea that it is probably going to only be finitely many, but at this point we can't really be sure.
To express all of the things we want to express, we need to extend propositional logic. What this means is that we are going to need to define some new concepts and go through the whole syntax and semantics dance that we did for propositional logic.
The extension of propositional logic to include concepts like objects, quantification, and relationships is called predicate logic or first-order logic. First-order logic was developed independently by Gottlob Frege, whom you may remember from our discussion about the semantics of first order logic, and Charles S. Peirce in the late 1800s.
While so far we have been talking about the mechanics of taking CS 245, it's helpful to remember that the motivation for all of this ultimately to construct a language for expressing mathematics. For computer scientists, we tend to emphasize the modelling part of logic, which involves translating natural language to precise logical statements. Of course, this sort of abstraction is ultimately turned into mathematics, but we're very clever about not thinking about math more than we need to.
However, we can see how propositional logic doesn't quite cut it if we wanted to express something like a theorem from MATH 135. If we had a proposition like
If $n$ is a natural number and $n$ is even, then $n$ is not odd.we run into the same problems as when talking about Gordon Ramsay's status in CS 245. In particular, we can certainly transform this sentence into a formula with atomic propositions, but this doesn't let us talk about numbers per se.
One observation you may have made is that the structure of this claim is actually the same as $((p \wedge (\neg q)) \rightarrow r)$. What this means is that if we want to start talking about objects, first, we need fix which objects it is that we really want to talk about.
The domain is the set of objects that we want to work with and a constant refers to an object in the domain. For our example, our domain is the set of students and one such constant would be Gordon Ramsay. In the context of mathematics, we may want to use the set of natural numbers $\mathbb N$ as our domain and 0 would be a constant in this domain. Or perhaps, we would rather work with $\mathbb R^2$ as our domain, in which case $(2,\sqrt 2)$ is a constant in $\mathbb R^2$. Our choice of domain will dictate the kinds of things we want to say and about which objects we want to talk about.
Next, we want to describe relationships among the objects in our domain. Going back to our example, we can turn our propositions into the following.
We call these predicates, or relations, and we can treat them in the obvious way: $P(\text{Gordon Ramsay})$ denotes the statement "Gordon Ramsay took CS 245". And we can make use of these predicates in the same way we would with propositional variables. That means, we can come up with formulas like $$((P(\text{Gordon Ramsay}) \wedge (\neg Q(\text{Gordon Ramsay}))) \rightarrow R(\text{Gordon Ramsay})).$$
Predicates have an arity associated with them. A $k$-ary predicate is a predicate with $k$ arguments. For instance, a unary, or 1-ary, predicate would express that an object has a particular property. From above, $P(\text{Gordon Ramsay})$ would mean that Gordon Ramsay has the property that he took CS 245. However, if we wanted to be more general, we could say $P(x)$, using $x$ as a variable. A variable is a placeholder for (possibly unknown) concrete values. In a more mathematical setting, we may wish to define a unary predicate $E(\cdot)$ for the property of being even and $E(n)$ would be the statement "$n$ is even".
Similarly, binary predicates express a relationship between two objects. For instance, in the domain of the natural numbers, we may wish to express the "greater than" relation. We could denote this by $G(x,y)$ for "$x$ is greater than "$y$". Or back in our students and CS 245 world, we could define a binary predicate like $L(x,y)$ to express "the student $x$ loves the course $y$".
However, note that simply saying $G(2,600)$ or $L(\text{Gordon Ramsay},\text{CS 245})$ doesn't necessarily mean that 2 is greater than 600 or that Gordon Ramsay is a big fan of CS 245. Rather, just like the relationship between propositional variables in formulas, such statements can be assigned a truth value, which we can consider and evaluate.
And as you may be familiar with already, we can use $k$-ary predicate symbols to express $k$-ary relations. But here's a fun question to ponder: What is a 0-ary (or nullary) predicate?
So informally, predicate symbols are used to denote properties of and relationships between objects and we use variables as placeholders for objects. If we go back to the example we started out with, we can now express the following $$((P(x) \wedge (\neg Q(x))) \rightarrow R(x))$$ and this will be true for any student $x$ that we want to plug in. However, if we want to say that this is true for every student, the best we can currently do is something like $$((((P(x_1) \wedge (\neg Q(x_1))) \rightarrow R(x_1)) \wedge ((P(x_2) \wedge (\neg Q(x_2))) \rightarrow R(x_2))) \wedge \cdots )$$ To capture the kind of statement we want to express, we need a bit more notation, and so we introduce the notion of quantifiers.
Definition 11.1. The symbol $\forall$ is called the universal quantifier is read "for all". The symbol $\exists$ is called the existential quantifier and is read "there exists". These symbols are collectively called quantifiers.
Quantifier symbols are defined to let us capture the ideas of quantification. To say that "If $x$ took CS 245 and did not pass it, then $x$ failed CS 245 is true for every student $x$, we can write $$(\forall x ((P(x) \wedge (\neg Q(x))) \rightarrow R(x))).$$ In other words, $((P(x) \wedge (\neg Q(x))) \rightarrow R(x))$ holds for every choice of $x$. Similarly, if we want to say that some student $x$ failed CS 245, we can write $(\exists x R(x))$ for "there is a student $x$ such that $x$ failed CS 245". With these quantifiers, we can express notions like "some", "every", "none", and so on.
We can then construct more elaborate expressions. If $S$ is a predicate for "is a student" and $c$ is CS 245, then we can write "All students love CS 245" as $(\forall x(S(x) \rightarrow L(x,c)))$. Or if, for some reason, it isn't the case that every student loves CS 245, then we can say that "Some students love CS 245" and write $(\exists x (S(x) \wedge L(x,c)))$. Even here, we can notice a few subtleties about what these quantifiers and predicates mean. For instance, we didn't write $(\exists x (S(x) \rightarrow L(x,c)))$ to mirror the statement about all students. Similarly, how would we say that "No students love CS 245"? Should it be $(\neg (\exists x (S(x) \wedge L(x,c))))$ or $(\forall x (S(x) \rightarrow (\neg L(x,c))))$?
Our final notion that we need is the concept of functions. While predicates tell us about the relationship between objects, functions tell us about objects in relation to other objects. For instance, we can define a predicate $D(x,y)$ for "$x$ is $y$'s dog". Now, if we learn that, say, Gordon Ramsay's dog really liked CS 245, then we might try to say something like $(\exists x(D(x,g) \wedge L(x,c)))$, where $c$ is CS 245 and $g$ is Gordon Ramsay. But in fact, this is not what we want to say, since this says that there exists someone who is Gordon's Ramsay's dog and loves CS 245. If we assume that in our universe, everyone owns exactly one dog, then we can define a function $d$ to denote a "dog-of" function. Using this, our expression can be formulated as $L(d(g),c)$.
Of course, most of our intuitive understanding of how functions work also applies here. For instance, if we wanted to talk about Gordon Ramsay's dog's own pet dog, then we could use nested function applications to denote said dog by $d(d(g))$ (this is kind of like how Hello Kitty has a pet cat). And just like how functions operate in our usual understanding, functions in predicate logic may also have arity like predicates.
Example 11.2. Let's look at some examples that we may be familiar with from mathematics. If we wanted to talk about number theory, then our domain would be the set of integers $\mathbb Z = \{\dots, -2, -1, 0, 1, 2, \dots\}$. We would define operations such as addition ($+$), subtraction ($-$), and multiplication ($\times$) and we could have an equality predicate $=$ and a less-than predicate $<$.
Strictly speaking, we could package all of these symbols up into a neat structure and denote it as something like $\mathfrak Z$ (this is a very fancy Z written in a calligraphic style called blackletter and is used when mathematicians exhaust all the other ways they try to write the same letter differently). Doing this allows us to distinguish the structure $\mathfrak Z$ and the domain $\mathbb Z$. Now, this is overkill even for most mathematicians, so generally we're fine with referring to the structure by its domain/universe.
Example 11.3. For the purposes of this course, even something like number theory with the domain restricted to $\mathbb Z$ (as opposed to say, trying to express things in $\mathbb R$) is too much for us to work with. In past offerings of the course (but not this one), we might have you work with Peano arithmetic, a basic formalization of arithmetic over the natural numbers defined by Giuseppe Peano in the late 19th century. The symbols defined for Peano arithmetic are:
Note that although the domain of Peano arithmetic is the natural numbers $\mathbb N$, the only constant symbol is 0. In other words, every element of $\mathbb N$ can be expressed as a series of applications of the functions $S,+,\times$ and the constant symbol 0.