Part II: First Order Logic
11.1 A limitation of the propositional logic
The propositional logic is a perfect language for what it does. It is rigorously precise and easy to use. But it is not the only kind of logic that philosophers developed. The philosopher Aristotle (384-322 BC) wrote several books on logic, and famously, he used the following argument as one of his examples.
All men are mortal.
Socrates is a man.
Socrates is mortal.
Aristotle considered this an example of a valid argument. And it appears to be one. But let us translate it into our propositional logic. We have three atomic sentences. Our translation key would look something like this:
P: All men are mortal.
Q: Socrates is a man.
R: Socrates is mortal.
And the argument, written in propositional logic, would be
This argument is obviously invalid. What went wrong? Somehow, between Aristotle’s argument and our translation, essential information was lost. This information was required in order for the argument to be valid. When we lost it, we ended up with an argument where the conclusion could be false (as far as we can tell from the shape of the argument alone).
It seems quite clear what we lost in the translation. There are parts of the first premise that are shared by the other two: something to do with being a man, and being mortal. There is a part of the second sentence shared with the conclusion: the proper name “Socrates”. And the word “All” seems to be playing an important role here.
Note that all three of these things (those adjective phrases, a proper name, and “all”) are themselves not sentences. To understand this argument of Aristotle’s, we will need to break into the atomic sentences, and begin to understand their parts. Doing this proved to be very challenging—most of all, making sense of that “all” proved challenging. As a result, for nearly two thousand years, we had two logics working in parallel: the propositional logic and Aristotle’s logic. It was not until late in the nineteenth century that we developed a clear and precise understanding of how to combine these two logics into one, which we will call “first order logic” (we will explain later what “first order” means).
Our task will be to make sense of these parts: proper names, adjective phrases, and the “all”. We can begin with names.
11.2 Symbolic terms: proper names
The first thing we want to add to our expanded language are names. We will take proper names (such as, “Abraham Lincoln”) as our model. General names (such as “Americans”) we will handle in a different way, to be discussed later. We will call these proper names of our language, “names”.
Recall that we want our language to have no vagueness, and no ambiguity. A name would be vague if it might or might not pick out an object. So we will require that each name pick out an object. That is, a name may not be added to our language if it refers to nothing, or only refers to something under some conditions. A name would be ambiguous if it pointed at more than one thing. “John Smith” is a name that points at thousands of people. We will not allow this in our language. Each name points at only one thing.
We might decide also that each thing that our language talks about has only one name. Some philosophers have thought that such a rule would be very helpful. However, it turns out it is often very hard to know if two apparent things are the same thing, and so in a natural language we often have several names for the same thing. A favorite example of philosophers, taken from the philosopher and mathematician Gottlob Frege (1848-1925), is “Hesperus” and “Phosphorus.” These are both names for Venus, although some who used these names did not know that. Thus, for a while, some people did not know that Hesperus was Phosphorus. And, of course, we would not have been able to use just one name for both, if we did not know that these names pointed at the same one thing. Thus, if we want to model scientific problems, or other real world problems, using our logic, then a rule that each thing have one and only one name would demand too much: it would require us to solve all our mysteries before we got started. In any case, there is no ambiguity in a thing having several names.
Names refer to things. But when we say a refers to such and such an object, then if someone asked, “What do you mean by ‘refer’?”, we would be hard pressed to do anything more than offer a list of synonyms: a points at the object, a names the object, a indicates the object, a picks out the object. “Refer” is another primitive that we are adding to our language. We cannot in this book explain what reference is; in fact, philosophers vigorously debate this today, and there are several different and (seemingly) incompatible theories about how names work. However, taking “refer” as a primitive will not cause us difficulties, since we all use names and so we all have a working understanding of names and how they refer.
In our language, we will use lower case letters, from the beginning of the alphabet, for names. Thus, the following are names:
In a natural language, there is more meaning to a name than what it points at. Gottlob Frege was intrigued by the following kinds of cases.
Hesperus is Hesperus.
Hesperus is Phosphorus.
What is peculiar in these four sentences is that the first and third are trivial. We know that they must be true. The second and fourth sentences, however, might be surprising, even if true. Frege observed that reference cannot constitute all the meaning of a name, for if it did, and if a is b, then the second sentence above should have the same meaning as the first sentence. And, if Hesperus is Phosphorus, the third and fourth sentences should have the same meaning. But obviously they don’t. The meaning of a name, he concluded, is more than just what it refers to. He called this extra meaning sense (Sinn, in his native German).
We won’t be able to explore these subtleties. We’re going to reduce the meaning of our names down to their referent. This is another case where we see that a natural language like English is very powerful, and contains subtleties that we avoid and simplify away in order to develop our precise language.
Finally, let us repeat that we are using the word “name” in a very specific sense. A name picks out a single object. For this reason, although it may be true that “cat” is a kind of name in English, it cannot be properly translated to a name in our logical language. Thus, when considering whether some element of a natural language is a proper name, just ask yourself: is there a single thing being referred to by this element? If the answer is no, then that part of the natural language is not like a name in our logical language.
Another element of Aristotle’s argument above that we want to capture is phrases like “is a man” and “is mortal”. These adjective phrases are called by philosophers “predicates”. They tell us about properties or relations had by the things our language is about. In our sentence “Socrates is a man”, the predicate (“… is a man”) identifies a property of Socrates. We want to introduce into our logical language a way to express these predicates. But before we do this, we need to clarify how predicates relate to the objects we are talking about, and we want to be sure that we introduce predicates in such a way that their meaning is precise (they are not vague or ambiguous).
Our example of “… is a man” might lead us to think that predicates identify properties of individual objects. But consider the following sentences.
Tom is tall.
Tom is taller than Jack.
7 is odd.
7 is greater than or equal to 5.
The first and third sentence are quite like the ones we’ve seen before. “Tom” and “7” are names. And “…is tall” and “…is odd” are predicates. These are similar (at least in terms of their apparent syntax) to “Socrates” and “… is a man”.
But what about those other two sentences? The predicates in these sentences express relations between two things. And, although in English it is rare that a predicate expresses a relation of more than two things, in our logical language a predicate could identify a relation between any number of things. We need, then, to be aware that each predicate identifies a relation between a specific number of things. This is important, because the predicates in the first and second sentence above are not the same. That is, “…is tall” and “… is taller than…” are not the same predicate.
Logicians have a slang for this; they call it the “arity” of the predicate. This odd word comes from taking the “ary” on words like “binary” and “trinary”, and making it into a noun. So, we can say the following: each predicate has an arity. The arity of a predicate is the minimum number of things that can have the property or relation. The predicate “… is tall” is arity one. One thing alone can be tall. The predicate “… is taller than…” is arity two. You need at least two things for one to be taller than the other.
Thus, consider the following sentence.
Stefano, Margarita, Aletheia, and Lorena are Italian.
There is a predicate here, “… are Italian.” It has been used to describe four things. Is it an arity four predicate? We could treat it as one, but that would make our language deceptive. Our test should be the following principle: what is the minimum number of things that can have that property or relation? In that case, “… are Italian” should be an arity one predicate because one thing alone can be Italian. Thus, the sentence above should be understood as equivalent to:
Stefano is Italian and Margarita is Italian and Aletheia is Italian and Lorena is Italian.
This is formed using conjunctions of atomic sentences, each containing the same arity one predicate. Consider also the following sentence.
Stefano is older than Aletheia and Lorena.
There are three names here. Is the predicate then an arity three predicate? No. The minimum number of things such that one can be older than the other is two. From this fact, we know that “… is older than…” is an arity two predicate. This sentence is thus equivalent to:
Stefano is older than Aletheia and Stefano is older than Lorena.
This is formed using a conjunction of atomic sentences, each containing the same arity two predicate.
Note an important difference we need to make between our logical language and a natural language like English. In a natural language like English, we have a vast range of kinds of names and kinds of predicates. Some of these could be combined to form sentences without any recognizable truth value. Consider:
Jupiter is an odd number.
America is taller than Smith.
7 is older than Jones.
These expressions are semantic nonsense, although they are syntactically well formed. The predicate “…is an odd number” cannot be true or false of a planet. America does not have a height to be compared. Numbers do not have an age. And so on.
We are very clever speakers in our native languages. We naturally avoid these kinds of mistakes (most of the time). But our logic is being built to avoid such mistakes always; it aims to make them impossible. Thus, each first order logical language must have what we will call its “domain of discourse”. The domain of discourse is the set of things that our first order logic is talking about. If we want to talk about numbers, people, and nations, we will want to make three different languages with three different sets of predicates and three different domains of discourse.
We can now state our rule for predicates precisely. A predicate of arity n must be true or false, never both, never neither, of each n objects from our domain of discourse.
This will allow us to avoid predicates that are vague or ambiguous. A vague predicate might include, “…is kind of tall.” It might be obviously false of very short people, but it is not going to have a clear truth value with respect to people who are of height slightly above average. If a predicate were ambiguous, we would again not be able to tell in some cases whether the predicate were true or false of some of the things in our domain of discourse. An example might include, “… is by the pen.” It could mean is by the writing implement, or it could mean is by the children’s playpen. Not knowing which, we would not be able to tell whether a sentence like “Fido is by the pen” were true or false. Our rule for predicates explicitly rules out either possibility.
When we say, “a predicate of arity n is true or false of each n objects from our domain of discourse”, what we mean is that an arity one predicate must be true or false of each thing in the domain of discourse; and an arity two predicate must be true or false of every possible ordered pair of things from the domain of discourse; and an arity three predicate must be true or false of every possible ordered triple of things from our domain of discourse; and so on.
We will use upper case letters from F on to represent predicates of our logical language. Thus,
11.4 First order logic sentences
We can now explain what a sentence is in our first order logic.
We need to decide how names and predicates will be combined. Different methods have been used, but most common is what is called “prefix notation”. This means we put the predicate before names. So, if we had the sentences
Tom is tall.
Tom is taller than Steve.
And we had the following translation key,
Fx: x is tall
Gxy: x is taller than y
Then our translations would be
I did something new in the translation key: I used variables to identify places in a predicate. This is not any part of our language, but just a handy bit of bookkeeping we can use in explaining our predicates. The advantage is that if we write simply:
G: is greater than
there could be ambiguity about which name should come first after the predicate (the greater than name, or the less than name). We avoid this ambiguity by putting variables into the predicate and the English in the translation key. But the variables are doing no other work. Don’t think of a predicate as containing variables.
The sentence above that we had
Stefano is Italian and Margarita is Italian and Aletheia is Italian and Lorena is Italian.
can be translated with the following key:
Ix: x is Italian.
And in our language would look like this:
We have not yet given a formal syntax for atomic sentences of first order logic. We will need a new concept of syntax—the well formed formula that is not a sentence—and for this reason we will put off the specification of the syntax for the next chapter.
- Translate the following sentences into our first order logic. Provide a translation key that identifies the names and predicates.
- Bob is a poriferan.
- Bob is neither a cnidarian nor female.
- Bob is a male poriferan.
- Bob is not a male poriferan.
- Bob is a poriferan if and only if he is not a cnidarian.
- Pat is not both a poriferan and a cnidarian.
- Pat is not a poriferan, though he is male.
- Pat and Bob are male.
- Bob is older than Pat.
- Pat is not older than both Sandi and Bob.
- Identify the predicate of the following sentences, and identify its arity.
- Aletheia and Lorena are tall.
- Aletheia and Lorena are taller than Stefano and Margarita.
- Margarita is younger than Aletheia, Lorena, and Stefano.
- Margarita and Stefano live in Rome and Aletheia and Lorena live in Milan.
- Lorena stands between Stefano and Aletheia.
- Make your own translation key for the following sentences. Use your key to write the English equivalents.
- (Gab ^ Fb).
- ¬(Gab ^ Fb).
- (¬Gab ^ Fb).
- ¬(Gab v Fb).
- (Gab ↔ Gac).
- (Fa ^ Fb).