What time is it?
Open the window.
Damn you!
I promise to pay you back.
It rained in Central Park on June 26, 2015.
We could multiply such examples. Sentences in English can be used to ask questions, give commands, curse or insult, form contracts, and express emotions. But, the last example above is of special interest because it aims to describe the world. Such sentences, which are sometimes called “declarative sentences”, will be our model sentences for our logical language. We know a declarative sentence when we encounter it because it can be either true or false.Tom is kind of tall.
When Karen had a baby, her mother gave her a pen.
This sentence is false.
We have already observed that an important feature of our declarative sentences is that they can be true or false. We call this the “truth value” of the sentence. These three sentences are perplexing because their truth values are unclear. The first sentence is vague, it is not clear under what conditions it would be true, and under what conditions it would be false. If Tom is six feet tall, is he kind of tall? There is no clear answer. The second sentence is ambiguous. If “pen” means writing implement, and Karen’s mother bought a playpen for the baby, then the sentence is false. But until we know what “pen” means in this sentence, we cannot tell if the sentence is true. The third sentence is strange. Many logicians have spent many years studying this sentence, which is traditionally called “the Liar”. It is related to an old paradox about a Cretan who said, “All Cretans are liars”. The strange thing about the Liar is that its truth value seems to explode. If it is true, then it is false. If it is false, then it is true. Some philosophers think this sentence is, therefore, neither true nor false; some philosophers think it is both true and false. In either case, it is confusing. How could a sentence that looks like a declarative sentence have both or no truth value? Since ancient times, philosophers have believed that we will deceive ourselves, and come to believe untruths, if we do not accept a principle sometimes called “bivalence”, or a related principle called “the principle of non-contradiction”. Bivalence is the view that there are only two truth values (true and false) and that they exclude each other. The principle of non-contradiction states that you have made a mistake if you both assert and deny a claim. One or the other of these principles seems to be violated by the Liar. We can take these observations for our guide: we want our language to have no vagueness and no ambiguity. In our propositional logic, this means we want it to be the case that each sentence is either true or false. It will not be kind of true, or partially true, or true from one perspective and not true from another. We also want to avoid things like the Liar. We do not need to agree on whether the Liar is both true and false, or neither true nor false. Either would be unfortunate. So, we will specify that our sentences have neither vice. We can formulate our own revised version of the principle of bivalence, which states that:Principle of Bivalence: Each sentence of our language must be either true or false, not both, not neither.
This requirement may sound trivial, but in fact it constrains what we do from now on in interesting and even surprising ways. Even as we build more complex logical languages later, this principle will be fundamental. Some readers may be thinking: what if I reject bivalence, or the principle of non-contradiction? There is a long line of philosophers who would like to argue with you, and propose that either move would be a mistake, and perhaps even incoherent. Set those arguments aside. If you have doubts about bivalence, or the principle of non-contradiction, stick with logic. That is because we could develop a logic in which there were more than two truth values. Logics have been created and studied in which we allow for three truth values, or continuous truth values, or stranger possibilities. The issue for us is that we must start somewhere, and the principle of bivalence is an intuitive way and—it would seem—the simplest way to start with respect to truth values. Learn basic logic first, and then you can explore these alternatives. This points us to an important feature, and perhaps a mystery, of logic. In part, what a logical language shows us is the consequences of our assumptions. That might sound trivial, but, in fact, it is anything but. From very simple assumptions, we will discover new, and ultimately shocking, facts. So, if someone wants to study a logical language where we reject the principle of bivalence, they can do so. The difference between what they are doing, and what we will do in the following chapters, is that they will discover the consequences of rejecting the principle of bivalence, whereas we will discover the consequences of adhering to it. In either case, it would be wise to learn traditional logic first, before attempting to study or develop an alternative logic. We should note at this point that we are not going to try to explain what “true” and “false” mean, other than saying that “false” means not true. When we add something to our language without explaining its meaning, we call it a “primitive”. Philosophers have done much to try to understand what truth is, but it remains quite difficult to define truth in any way that is not controversial. Fortunately, taking true as a primitive will not get us into trouble, and it appears unlikely to make logic mysterious. We all have some grasp of what “true” means, and this grasp will be sufficient for our development of the propositional logic.2+2=4.
Malcolm Little is tall.
If Lincoln wins the election, then Lincoln will be President.
The Earth is not the center of the universe.
These are all declarative sentences. These all appear to satisfy our principle of bivalence. But they differ in important ways. The first two sentences do not have sentences as parts. For example, try to break up the first sentence. “2+2” is a function. “4” is a name. “=4” is a meaningless fragment, as is “2+”. Only the whole expression, “2+2=4”, is a sentence with a truth value. The second sentence is similar in this regard. “Malcolm Little” is a name. “is tall” is an adjective phrase (we will discover later that logicians call this a “predicate”). “Malcolm Little is” or “is tall” are fragments, they have no truth value.^{[2] }Only “Malcolm Little is tall” is a complete sentence. The first two example sentences above are of a kind we call “atomic sentences”. The word “atom” comes from the ancient Greek word “atomos”, meaning cannot be cut. When the ancient Greeks reasoned about matter, for example, some of them believed that if you took some substance, say a rock, and cut it into pieces, then cut the pieces into pieces, and so on, eventually you would get to something that could not be cut. This would be the smallest possible thing. (The fact that we now talk of having “split the atom” just goes to show that we changed the meaning of the word “atom”. We came to use it as a name for a particular kind of thing, which then turned out to have parts, such as electrons, protons, and neutrons.) In logic, the idea of an atomic sentence is of a sentence that can have no parts that are sentences. In reasoning about these atomic sentences, we could continue to use English. But for reasons that become clear as we proceed, there are many advantages to coming up with our own way of writing our sentences. It is traditional in logic to use upper case letters from P on (P, Q, R, S….) to stand for atomic sentences. Thus, instead of writingMalcolm Little is tall.
We could writeP
If we want to know how to translate P to English, we can provide a translation key. Similarly, instead of writingMalcolm Little is a great orator.
We could writeQ
And so on. Of course, written in this way, all we can see about such a sentence is that it is a sentence, and that perhaps P and Q are different sentences. But for now, these will be sufficient. Note that not all sentences are atomic. The third sentence in our four examples above contains parts that are sentences. It contains the atomic sentence, “Lincoln wins the election” and also the atomic sentence, “Lincoln will be President”. We could represent this whole sentence with a single letter. That is, we could letIf Lincoln wins the election, Lincoln will be president.
be represented in our logical language byS
However, this would have the disadvantage that it would hide some of the sentences that are inside this sentence, and also it would hide their relationship. Our language would tell us more if we could capture the relation between the parts of this sentence, instead of hiding them. We will do this in chapter 2.Colorless green ideas sleep furiously.
In other words, in English, this sentence is syntactically correct, although it may express some kind of meaning error. An expression made with the parts of our language must have correct syntax in order for it to be a sentence. Sometimes, we also call an expression with the right syntactic form a “well-formed formula”. We contrast syntax with semantics. “Semantics” refers to the meaning of an expression of our language. Semantics depends upon the relation of that element of the language to something else. For example, the truth value of the sentence, “The Earth has one moon” depends not upon the English language, but upon something exterior to the language. Since the self-standing elements of our propositional logic are sentences, and the most important property of these is their truth value, the only semantic feature of sentences that will concern us in our propositional logic is their truth value. Whenever we introduce a new element into the propositional logic, we will specify its syntax and its semantics. In the propositional logic, the syntax is generally trivial, but the semantics is less so. We have so far introduced atomic sentences. The syntax for an atomic sentence is trivial. If P is an atomic sentence, then it is syntactically correct to write downP
By saying that this is syntactically correct, we are not saying that P is true. Rather, we are saying that P is a sentence. If semantics in the propositional logic concerns only truth value, then we know that there are only two possible semantic values for P; it can be either true or false. We have a way of writing this that will later prove helpful. It is called a “truth table”. For an atomic sentence, the truth table is trivial, but when we look at other kinds of sentences their truth tables will be more complex. The idea of a truth table is to describe the conditions in which a sentence is true or false. We do this by identifying all the atomic sentences that compose that sentence. Then, on the left side, we stipulate all the possible truth values of these atomic sentences and write these out. On the right side, we then identify under what conditions the sentence (that is composed of the other atomic sentences) is true or false. The idea is that the sentence on the right is dependent on the sentence(s) on the left. So the truth table is filled in like this:Atomic sentence(s) that compose the dependent sentence on the right | Dependent sentence composed of the atomic sentences on the left |
All possible combinations of truth values of the composing atomic sentences |
Resulting truth values for each possible combination of truth values of the composing atomic sentences |
P | |
T | |
F |
P | P |
T | T |
F | F |
Φ
is a sentence. This tells us that simply writing Φ down (whatever atomic sentence it may be), as we have just done, is to write down something that is syntactically correct. To specify now the semantics of atomic sentences (that is, of all atomic sentences) we can say: If Φ is an atomic sentence, then the semantics of Φ is given byΦ | Φ |
T | T |
F | F |
Force is equal to mass times acceleration.
Igneous rocks formed under pressure.
Germany inflated its currency in 1923 in order to reduce its reparations debt.
Logic cannot tell us whether these are true or false. We will turn to physicists, and use their methods, to evaluate the first claim. We will turn to geologists, and use their methods, to evaluate the second claim. We will turn to historians, and use their methods, to evaluate the third claim. But the logician can tell the physicist, geologist, and historian what follows from their claims.If Lincoln wins the election, then Lincoln will be President.
The Earth is not the center of the universe.
We could treat these like atomic sentences, but then we would lose a great deal of important information. For example, the first sentence tells us something about the relationship between the atomic sentences “Lincoln wins the election” and “Lincoln will be President”. And the second sentence above will, one supposes, have an interesting relationship to the sentence, “The Earth is the center of the universe”. To make these relations explicit, we will have to understand what “if…then…” and “not” mean. Thus, it would be useful if our logical language was able to express these kinds of sentences in a way that made these elements explicit. Let us start with the first one. The sentence, “If Lincoln wins the election, then Lincoln will be President” contains two atomic sentences, “Lincoln wins the election” and “Lincoln will be President”. We could thus represent this sentence by lettingLincoln wins the election
be represented in our logical language byP
And by lettingLincoln will be president
be represented byQ
Then, the whole expression could be represented by writingIf P then Q
It will be useful, however, to replace the English phrase “if…then...” by a single symbol in our language. The most commonly used such symbol is “→”. Thus, we would writeP→Q
One last thing needs to be observed, however. We might want to combine this complex sentence with other sentences. In that case, we need a way to identify that this is a single sentence when it is combined with other sentences. There are several ways to do this, but the most familiar (although not the most elegant) is to use parentheses. Thus, we will write our expression(P→Q)
This kind of sentence is called a “conditional”. It is also sometimes called a “material conditional”. The first constituent sentence (the one before the arrow, which in this example is “P”) is called the “antecedent”. The second sentence (the one after the arrow, which in this example is “Q”) is called the “consequent”. We know how to write the conditional, but what does it mean? As before, we will take the meaning to be given by the truth conditions—that is, a description of when the sentence is either true or false. We do this with a truth table. But now, our sentence has two parts that are atomic sentences, P and Q. Note that either atomic sentence could be true or false. That means, we have to consider four possible kinds of situations. We must consider when P is true and when it is false, but then we need to consider those two kinds of situations twice: once for when Q is true and once for when Q is false. Thus, the left hand side of our truth table will look like this:P | Q | |
T | T | |
T | F | |
F | T | |
F | F |
P | Q | (P→Q) |
---|---|---|
T | T | T |
T | F | F |
F | T | |
F | F |
You give me $50
be represented in our logic byR
and letI will buy you a ticket to the concert tonight.
be represented byS
Our sentence then is(R→S)
And its truth table—as far as we understand right now—is:R | S | (R→S) |
---|---|---|
T | T | T |
T | F | F |
F | T | |
F | F |
R | S | (R→S) |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
If a is evenly divisible by 4, then a is evenly divisible by 2.
(By “evenly divisible,” I mean divisible without remainder.) The first thing to ask yourself is: is this sentence true? I hope we can all agree that it is—even though we do not know what a is. Leta is evenly divisible by 4
be represented in our logic byU
and leta is evenly divisible by 2
be represented byV
Our sentence then is(U→V)
And its truth table—as far as we understand right now—is:U | V | (U→V) |
---|---|---|
T | T | T |
T | F | F |
F | T | |
F | F |
U | V | (U→V) |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
P | Q | (P→Q) |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
(Φ→Ψ)
is a sentence. The semantics of the conditional are given by a truth table. For any sentences Φ and Ψ:Φ | Ψ | (Φ→Ψ) |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
If P, then Q.
Q, if P.
On the condition that P, Q.
Q, on the condition that P.
Given that P, Q.
Q, given that P.
Provided that P, Q.
Q, provided that P.
When P, then Q.
Q, when P.
P implies Q.
Q is implied by P.
P is sufficient for Q.
Q is necessary for P.
An oddity of English is that the word “only” changes the meaning of “if”. You can see this if you consider the following two sentences.Fifi is a cat, if Fifi is a mammal.
Fifi is a cat only if Fifi is a mammal.
Suppose we know Fifi is an organism, but, we don’t know what kind of organism Fifi is. Fifi could be a dog, a cat, a gray whale, a ladybug, a sponge. It seems clear that the first sentence is not necessarily true. If Fifi is a gray whale, for example, then it is true that Fifi is a mammal, but false that Fifi is a cat; and so, the first sentence would be false. But the second sentence looks like it must be true (given what you and I know about cats and mammals). We should thus be careful to recognize that “only if” does not mean the same thing as “if”. (If it did, these two sentences would have the same truth value in all situations.) In fact, it seems that “only if” can best be expressed by a conditional where the “only if” appears before the consequent (remember, the consequent is the second part of the conditional—the part that the arrows points at). Thus, sentences of this form:P only if Q.
Only if Q, P.
are best expressed by the formula(P→Q)
For each of these four cards, if the card has a Q on the letter side of the card, then it has a square on the shape side of the card.
Here is our puzzle: what is the minimum number of cards that we must turn over to test whether this claim is true of all four cards; and which cards are they that we must turn over? Of course we could turn them all over, but the puzzle asks you to identify all and only the cards that will test the claim. Stop reading now, and see if you can decide on the answer. Be warned, people generally perform poorly on this puzzle. Think about it for a while. The answer is given below in problem 1.(P⊃Q)
The Earth is not the center of the universe.
At first glance, such a sentence might appear to be fundamentally unlike a conditional. It does not contain two sentences, but only one. There is a “not” in the sentence, but it is not connecting two sentences. However, we can still think of this sentence as being constructed with a truth functional connective, if we are willing to accept that this sentence is equivalent to the following sentence.It is not the case that the Earth is the center of the universe.
If this sentence is equivalent to the one above, then we can treat “It is not the case” as a truth functional connective. It is traditional to replace this cumbersome English phrase with a single symbol, “¬”. Then, mixing our propositional logic with English, we would have¬The Earth is the center of the universe.
And if we let W be a sentence in our language that has the meaning The Earth is the center of the universe, we would write¬W
This connective is called “negation”. Its syntax is: if Φ is a sentence, then¬Φ
is a sentence. We call such a sentence a “negation sentence”. The semantics of a negation sentence is also obvious, and is given by the following truth table.Φ | ¬Φ |
---|---|
T | F |
F | T |
~P
Q | S | (Q→S) |
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Translation Key | |
---|---|
Logic | English |
P | Abe is able. |
Q | Abe is honest. |
Argument: an ordered list of sentences; we call one of these sentences the “conclusion”, and we call the other sentences “premises”.
This is obviously very weak. (There is a famous Monty Python skit where one of the comedians ridicules the very idea that such a thing could be called an argument.) But for our purposes, this is a useful notion because it is very clearly defined, and we can now ask, what makes an argument good? The everyday notion of an argument is that it is used to convince us to believe something. The thing that we are being encouraged to believe is the conclusion. Following our definition of “argument”, the reasons that the person gives will be what we are calling “premises”. But belief is a psychological notion. We instead are interested only in truth. So, we can reformulate this intuitive notion of what an argument should do, and think of an argument as being used to show that something is true. The premises of the argument are meant to show us that the conclusion is true. What then should be this relation between the premises and the conclusion? Intuitive notions include that the premises should support the conclusion, or corroborate the conclusion, or make the conclusion true. But “support” and “corroborate” sound rather weak, and “make” is not very clear. What we can use in their place is a stronger standard: let us say as a first approximation that if the premises are true, the conclusion is true. But even this seems weak, on reflection. For, the conclusion could be true by accident, for reasons unrelated to our premises. Remember that we define the conditional as true if the antecedent and consequent are true. But this could happen by accident. For example, suppose I say, “If Tom wears blue then he will get an A on the exam”. Suppose also that Tom both wears blue and Tom gets an A on the exam. This makes the conditional true, but (we hope) the color of his clothes really had nothing to do with his performance on the exam. Just so, we want our definition of “good argument” to be such that it cannot be an accident that the premises and conclusion are both true. A better and stronger standard would be that, necessarily, given true premises, the conclusion is true. This points us to our definition of a good argument. It is traditional to call a good argument “valid.”Valid argument: an argument for which, necessarily, if the premises are true, then the conclusion is true.
This is the single most important principle in this book. Memorize it. A bad argument is an argument that is not valid. Our name for this will be an “invalid argument”. Sometimes, a dictionary or other book will define or describe a “valid argument” as an argument that follows the rules of logic. This is a hopeless way to define “valid”, because it is circular in a pernicious way: we are going to create the rules of our logic in order to ensure that they construct valid arguments. We cannot make rules of logical reasoning until we know what we want those rules to do, and what we want them to do is to create valid arguments. So “valid” must be defined before we can make our reasoning system. Experience shows that if a student is to err in understanding this definition of “valid argument”, he or she will typically make the error of assuming that a valid argument has all true premises. This is not required. There are valid arguments with false premises and a false conclusion. Here’s one:If Miami is the capital of Kansas, then Miami is in Canada. Miami is the capital of Kansas. Therefore, Miami is in Canada.
This argument has at least one false premise: Miami is not the capital of Kansas. And the conclusion is false: Miami is not in Canada. But the argument is valid: if the premises were both true, the conclusion would have to be true. (If that bothers you, hold on a while and we will convince you that this argument is valid because of its form alone. Also, keep in mind always that “if…then…” is interpreted as meaning the conditional.) Similarly, there are invalid arguments with true premises, and with a true conclusion. Here’s one:If Miami is the capital of Ontario, then Miami is in Canada. Miami is not the capital of Ontario. Therefore, Miami is not in Canada.
(If you find it confusing that this argument is invalid, look at it again after you finish reading this chapter.) Validity is about the relationship between the sentences in the argument. It is not a claim that those sentences are true. Another variation of this confusion seems to arise when we forgot to think carefully about the conditional. The definition of valid is not “All the premises are true, so the conclusion is true.” If you don’t see the difference, consider the following two sentences. “If your house is on fire, then you should call the fire department.” In this sentence, there is no claim that your house is on fire. It is rather advice about what you should do if your house is on fire. In the same way, the definition of valid argument does not tell you that the premises are true. It tells you what follows if they are true. Contrast now, “Your house is on fire, so you should call the fire department”. This sentence delivers very bad news. It is not a conditional at all. What it really means is, “Your house is on fire and you should call the fire department”. Our definition of valid is not, “All the premises are true and the conclusion is true”. Finally, another common mistake is to confuse true and valid. In the sense that we are using these terms in this book, only sentences can be true or false, and only arguments can be valid and invalid. When discussing and using our logical language, it is nonsense to say, “a true argument”, and it is nonsense to say, “a valid sentence”. Someone new to logic might wonder, why would we want a definition of “good argument” that does not guarantee that our conclusion is true? The answer is that logic is an enormously powerful tool for checking arguments, and we want to be able to identify what the good arguments are, independently of the particular premises that we use in the argument. For example, there are infinitely many particular arguments that have the same form as the valid argument given above. There are infinitely many particular arguments that have the same form as the invalid argument given above. Logic lets us embrace all the former arguments at once, and reject all those bad ones at once. Furthermore, our propositional logic will not be able to tell us whether an atomic sentence is true. If our argument is about rocks, we must ask the geologist if the premises are true. If our argument is about history, we must ask the historian if the premises are true. If our argument is about music, we must ask the music theorist if the premises are true. But the logician can tell the geologist, the historian, and the musicologist whether her arguments are good or bad, independent of the particular premises. We do have a common term for a good argument that has true premises. This is called “sound”. It is a useful notion when we are applying our logic. Here is our definition:Sound argument: a valid argument with true premises.
A sound argument must have a true conclusion, given the definition of “valid”.If Jupiter is more massive than Earth, then Jupiter has a stronger gravitational field than Earth. Jupiter is more massive than Earth. In conclusion, Jupiter has a stronger gravitational field than Earth.
This looks like it has the form of a valid argument, and it looks like an astrophysicist would tell us it is sound. Let’s translate it to our logical language using the following translation key. (We’ve used up our letters, so I’m going to start over. We’ll do that often: assume we are starting a new language each time we translate a new set of problems or each time we consider a new example.)P: Jupiter is more massive than Earth
Q: Jupiter has a stronger gravitational field than Earth.
This way of writing out sentences of logic and sentences of English we can call a “translation key”. We can use this format whenever we want to explain what our sentences mean in English. Using this key, our argument would be formulated(P→Q)
P
______
Q
That short line is not part of our language, but rather is a handy tradition. When quickly writing down arguments, we write the premises, and then write the conclusion last, and draw a short line above the conclusion. This is an argument: it is an ordered list of sentences, the first two of which are premises and the last of which is the conclusion. To make a truth table, we identify all the atomic sentences that constitute these sentences. These are P and Q. There are four possible kinds of ways the world could be that matter to us then:P | Q | |||
---|---|---|---|---|
T | T | |||
T | F | |||
F | T | |||
F | F |
premise | premise | conclusion | ||
P | Q | (P→Q) | P | Q |
T | T | |||
T | F | |||
F | T | |||
F | F |
premise | premise | conclusion | ||
P | Q | (P→Q) | P | Q |
T | T | T | T | T |
T | F | F | T | F |
F | T | T | F | T |
F | F | T | F | F |
premise | premise | conclusion | ||
P | Q | (P→Q) | P | Q |
T | T | T | T | T |
T | F | F | T | F |
F | T | T | F | T |
F | F | T | F | F |
R: Miami is the capital of Ontario
S: Miami is in Canada
And our argument is thus(R→S)
¬R
_____
¬S
Here is the truth table.premise | premise | conclusion | ||
R | S | (R→S) | ¬R | ¬S |
T | T | T | F | F |
T | F | F | F | T |
F | T | T | T | F |
F | F | T | T | T |
premise | premise | conclusion | ||
R | S | (R→S) | ¬R | ¬S |
T | T | T | F | F |
T | F | F | F | T |
F | T | T | T | F |
F | F | T | T | T |
T: Childbed fever is caused by cosmic-atmospheric-terrestrial influences.
U: The mortality rate is similar in the First and Second Clinics.
This would mean the argument is:(T→U)
¬U
_____
¬T
Is this argument valid? We can check using a truth table.premise | premise | conclusion | ||
T | U | (T→U) | ¬U | ¬T |
T | T | T | F | F |
T | F | F | T | F |
F | T | T | F | T |
F | F | T | T | T |
V: the higher rate of childbed fever is caused by fear of death resulting from the priest’s approach.
W: the rate of childbed fever will decline if people cannot discern when the priest is coming to the Clinic.
But when Semmelweis had the priest silence his bell, and take a different route, so that patients could not discern that he was coming to the First Clinic, he found no difference in the mortality rate; the First Clinic remained far worse than the second clinic. He concluded that the higher rate of childbed fever was not caused by fear of death resulting from the priest’s approach.(V→W)
¬W
_____
¬V
Is this argument valid? We can check using a truth table.premise | premise | conclusion | ||
V | W | (V→W) | ¬W | ¬V |
T | T | T | F | F |
T | F | F | T | F |
F | T | T | F | T |
F | F | T | T | T |
P: The fever is caused by cadaveric matter on the hands of the doctors.
Q: The mortality rate will drop when doctors wash their hands with chlorinated water before delivering babies.
And the argument appears to be something like this (as we will see, this isn’t quite the right way to put it, but for now…):(P→Q)
Q
_____
P
Is this argument valid? We can check using a truth table.premise | premise | conclusion | ||
P | Q | (P→Q) | Q | P |
T | T | T | T | T |
T | F | F | F | T |
F | T | T | T | F |
F | F | T | F | F |
Alison will go to the party.
If Alison will go to the party, then Beatrice will.
If Beatrice will go to the party, then Cathy will.
If Cathy will go to the party, then Diane will.
If Diane will go to the party, then Elizabeth will.
If Elizabeth will go to the party, then Fran will.
If Fran will go to the party, then Giada will.
If Giada will go to the party, then Hilary will.
If Hillary will go to the party, then Io will.
If Io will go to the party, then Julie will.
_____
Julie will go to the party.
Most of us will agree that this argument is valid. It has a rather simple form, in which one sentence is related to the previous sentence, so that we can see the conclusion follows from the premises. Without bothering to make a translation key, we can see the argument has the following form.P
(P→Q)
(Q→R)
(R→S)
(S→T)
(T→U)
(U→V)
(V→W)
(W→X)
(X→Y)
_____
Y
However, if we are going to check this argument, then the truth table will require 1024 rows! This follows directly from our observation that for arguments or sentences composed of n atomic sentences, the truth table will require 2n rows. This argument contains 10 atomic sentences. A truth table checking its validity must have 210 rows, and 210=1024. Furthermore, it would be trivial to extend the argument for another, say, ten steps, but then the truth table that we make would require more than a million rows! For this reason, and for several others (which become evident later, when we consider more advanced logic), it is very valuable to develop a syntactic proof method. That is, a way to check proofs not using a truth table, but rather using rules of syntax. Here is the idea that we will pursue. A valid argument is an argument such that, necessarily, if the premises are true, then the conclusion is true. We will start just with our premises. We will set aside the conclusion, only to remember it as a goal. Then, we will aim to find a reliable way to introduce another sentence into the argument, with the special property that, if the premises are true, then this single additional sentence to the argument must also be true. If we could find a method to do that, and if after repeated applications of this method we were able to write down our conclusion, then we would know that, necessarily, if our premises are true then the conclusion is true. The idea is more clear when we demonstrate it. The method for introducing new sentences will be called “inference rules”. We introduce our first inference rules for the conditional. Remember the truth table for the conditional:Φ | Ψ | (Φ→Ψ) |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
premise | premise | |||
P | Q | (P→Q) | P | Q |
T | T | T | T | T |
T | F | F | T | F |
F | T | T | F | T |
F | F | T | F | F |
premise | premise | |||
Φ | Ψ | (Φ→Ψ) | Φ | Ψ |
T | T | T | T | T |
T | F | F | T | F |
F | T | T | F | T |
F | F | T | F | F |
(Φ→Ψ)
Φ
_____
Ψ
This is a syntactic rule. It is saying that whenever we have written down a formula in our language that has the shape of the first row (that is, whenever we have a conditional), and whenever we also have written down a formula that has the shape in the second row (that is, whenever we also have written down the antecedent of the conditional), then go ahead, whenever you like, and write down a formula like that in the third row (the consequent of the conditional). The rule talks about the shape of the formulas, not their meaning. But of course we justified the rule by looking at the meanings. We describe this by saying that the third line is “derived” from the earlier two lines using the inference rule. This inference rule is old. We are, therefore, stuck with its well-established, but not very enlightening, name: “modus ponens”. Thus, we say, for the above example, that the third line is derived from the earlier two lines using modus ponens.premise | premise | |||
Φ | Ψ | (Φ→Ψ) | ¬Ψ | ¬Φ |
T | T | T | F | F |
T | F | F | T | F |
F | T | T | F | T |
F | F | T | T | T |
(Φ→Ψ)
¬Ψ
_____
¬Φ
What about negation? If we know a sentence is false, then this fact alone does not tell us about any other sentence. But what if we consider a negated negation sentence? Such a sentence has the following truth table.Φ | ¬¬Φ |
---|---|
T | T |
F | F |
Φ
_____
¬¬Φ
¬¬Φ
_____
Φ
Finally, it is sometimes helpful to be able to repeat a line. Technically, this is an unnecessary rule, but if a proof gets long, we often find it easier to understand the proof if we write a line over again later when we find we need it again. So we introduce the rule “repeat”.Φ
_____
Φ
(Q→P)
(¬Q→R)
¬R
_____
P
We want to check this argument to see if it is valid. To do a direct proof, we number the premises so that we can refer to them when using inference rules. \[ \fitchprf{\pline[1.] {(Q \lif P)} [premise]\\ \pline[2.]{(\lnot Q \lif R)} [premise]\\ \pline[3.]{\lnot R} [premise]\\ } { } \] And, now, we apply our inference rules. Sometimes, it can be hard to see how to complete a proof. In the worst case, where you are uncertain of how to proceed, you can apply all the rules that you see are applicable and then, assess if you have gotten closer to the conclusion; and repeat this process. Here in any case is a direct proof of the sought conclusion. \[ \fitchprf{\pline[1.] {(Q \lif P)} [premise]\\ \pline[2.]{(\lnot Q \lif R)} [premise]\\ \pline[3.]{\lnot R} [premise]\\ } { \pline[4.]{\lnot \lnot Q}[modus tollens, 2, 3]\\ \pline[5.]{Q}[double negation, 4]\\ \pline[6.]{P}[modus ponens, 1, 5]\\ } \] Developing skill at completing proofs merely requires practice. You should strive to do as many problems as you can.Inspector Tarski told his assistant, Mr. Carroll, “If Wittgenstein had mud on his boots, then he was in the field. Furthermore, if Wittgenstein was in the field, then he is the prime suspect for the murder of Dodgson. Wittgenstein did have mud on his boots. We conclude, Wittgenstein is the prime suspect for the murder of Dodgson.”
]]>Tom will go to Berlin and Paris.
The number a is evenly divisible by 2 and 3.
Steve is from Texas but not from Dallas.
We could translate each of these using an atomic sentence. But then we would have lost—or rather we would have hidden—information that is clearly there in the English sentences. We can capture this information by introducing a new connective; one that corresponds to our “and”. To see this, consider whether you will agree that these sentences above are equivalent to the following sentences.Tom will go to Berlin and Tom will go to Paris.
The number a is evenly divisible by 2 and the number a is evenly divisible by 3.
Steve is from Texas and it is not the case that Steve is from Dallas.
Once we grant that these sentences are equivalent to those above, we see that we can treat the “and” in each sentence as a truth functional connective. Suppose we assume the following key.P: Tom will go to Berlin.
Q: Tom will go to Paris.
R: a is evenly divisible by 2.
S: a is evenly divisible by 3.
T: Steve is from Texas
U: Steve is from Dallas.
A partial translation of these sentences would then be:P and Q
R and S
T and ¬U
Our third sentence above might generate some controversy. How should we understand “but”? Consider that in terms of the truth value of the connected sentences, “but” is the same as “and”. That is, if you say “P but Q” you are asserting that both P and Q are true. However, in English there is extra meaning; the English “but” seems to indicate that the additional sentence is unexpected or counter-intuitive. “P but Q” seems to say, “P is true, and you will find it surprising or unexpected that Q is true also.” That extra meaning is lost in our logic. We will not be representing surprise or expectations. So, we can treat “but” as being the same as “and”. This captures the truth value of the sentence formed using “but”, which is all that we require of our logic. Following our method up until now, we want a symbol to stand for “and”. In recent years the most commonly used symbol has been “^”. The syntax for “^” is simple. If Φ and Ψ are sentences, then(Φ^Ψ)
is a sentence. Our translations of our three example sentences should thus look like this:(P^Q)
(R^S)
(T^¬U)
Each of these is called a “conjunction”. The two parts of a conjunction are called “conjuncts”. The semantics of the conjunction are given by its truth table. Most people find the conjunction’s semantics obvious. If I claim that both Φ and Ψ are true, normal usage requires that if Φ is false or Ψ is false, or both are false, then I spoke falsely also. Consider an example. Suppose your employer says, “After one year of employment you will get a raise and two weeks vacation”. A year passes. Suppose now that this employer gives you a raise but no vacation, or a vacation but no raise, or neither a raise nor a vacation. In each case, the employer has broken his promise. The sentence forming the promise turned out to be false. Thus, the semantics for the conjunction are given with the following truth table. For any sentences Φ and Ψ:Φ | Ψ | (Φ^Ψ) |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
Even though they lost the battle, they won the war.
Here “even though” seems to do the same work as “but”. The implication is that it is surprising—that one might expect that if they lost the battle then they lost the war. But, as we already noted, we will not capture expectations with our logic. So, we would take this sentence to be sufficiently equivalent to:They lost the battle and they won the war.
With the exception of “but”, it seems in English there is no other single word that is an alternative to “and” that means the same thing. However, there are many ways that one can imply a conjunction. To see this, consider the following sentences.Tom, who won the race, also won the championship.
The star Phosphorous, that we see in the morning, is the Evening Star.
The Evening Star, which is called “Hesperus”, is also the Morning Star.
While Steve is tall, Tom is not.
Dogs are vertebrate terrestrial mammals.
Depending on what elements we take as basic in our language, these sentences all include implied conjunctions. They are equivalent to the following sentences, for example:Tom won the race and Tom won the championship.
Phosphorous is the star that we see in the morning and Phosphorous is the Evening Star.
The Evening Star is called “Hesperus” and the Evening Star is the Morning Star.
Steve is tall and it is not the case that Tom is tall.
Dogs are vertebrates and dogs are terrestrial and dogs are mammals.
Thus, we need to be sensitive to complex sentences that are conjunctions but that do not use “and” or “but” or phrases like “even though”. Unfortunately, in English there are some uses of “and” that are not conjunctions. The same is true for equivalent terms in some other natural languages. Here is an example.Rochester is between Buffalo and Albany.
The “and” in this sentence is not a conjunction. To see this, note that this sentence is not equivalent to the following:Rochester is between Buffalo and Rochester is between Albany.
That sentence is not even semantically correct. What is happening in the original sentence? The issue here is that “is between” is what we call a “predicate”. We will learn about predicates in chapter 11, but what we can say here is that some predicates take several names in order to form a sentence. In English, if a predicate takes more than two names, then we typically use the “and” to combine names that are being described by that predicate. In contrast, the conjunction in our propositional logic only combines sentences. So, we must say that there are some uses of the English “and” that are not equivalent to our conjunction. This could be confusing because sometimes in English we put “and” between names and there is an implied conjunction. Consider:Steve is older than Joe and Karen.
Superficially, this looks to have the same structure as “Rochester is between Buffalo and Albany”. But this sentence really is equivalent to:Steve is older than Joe and Steve is older than Karen.
The difference, however, is that there must be three things in order for one to be between the other two. There need only be two things for one to be older than the other. So, in the sentence “Rochester is between Buffalo and Albany”, we need all three names (“Rochester”, “Buffalo”, and “Albany) to make a single proper atomic sentence with “between”. This tells us that the “and” is just being used to combine these names, and not to combine implied sentences (since there can be no implied sentence about what is “between”, using just two or just one of these names). That sounds complex. Do not despair, however. The use of “and” to identify names being used by predicates is less common than “and” being used for a conjunction. Also, after we discuss predicates in chapter 11, and after you have practiced translating different kinds of sentences, the distinction between these uses of “and” will become easy to identify in almost all cases. In the meantime, we shall pick examples that do not invite this confusion.(Φ^Ψ)
_____
Φ
And:(Φ^Ψ)
_____
Ψ
In other words, if (Φ^Ψ) is true, then Φ must be true; and if (Φ^Ψ) is true, then Ψ must be true. We can also introduce a rule to show a conjunction, based on what we see from the truth table. That is, it is clear that there is only one kind of condition in which (Φ^Ψ) is true, and that is when Φ is true and when Ψ is true. This suggests the following rule:Φ
Ψ
_____
(Φ^Ψ)
We might call this rule “conjunction”, but to avoid confusion with the name of the sentences, we will call this rule “adjunction”.Tom and Steve will go to London. If Steve goes to London, then he will ride the Eye. Tom will ride the Eye too, provided that he goes to London. So, both Steve and Tom will ride the Eye.
We need a translation key.T: Tom will go to London.
S: Steve will go to London.
U: Tom will ride the Eye.
V: Steve will ride the Eye.
Thus our argument is:(T^S)
(S→U)
(T→V)
_____
(V^U)
Our direct proof will look like this. \[ \fitchprf{\pline[1.] {(T \land S)} [premise]\\ \pline[2.]{(S \lif U)} [premise]\\ \pline[3.]{(T \lif V)} [premise]\\ } { \pline[4.]{T}[simplification, 1]\\ \pline[5.]{V}[modus ponens, 3, 4]\\ \pline[6.]{S}[simplification, 1]\\ \pline[7.]{U}[modus ponens, 2, 6]\\ \pline[8.]{(V \land U)}[adjunction, 5, 7] } \] Now an example using just our logical language. Consider the following argument.(Q→¬S)
(P→(Q^R))
(T→¬R)
P
_____
(¬S^¬T)
Here is one possible proof. \[ \fitchprf{\pline[1.] {(Q \lif \lnot S)} [premise]\\ \pline[2.]{(P \lif (Q \land R))} [premise]\\ \pline[3.]{(T \lif \lnot R)} [premise]\\ \pline[4.]{P}[premise] } { \pline[5.]{(Q \land R)}[modus ponens, 2, 4]\\ \pline[6.]{Q}[simplification, 5]\\ \pline[7.]{\lnot S}[modus ponens, 1, 6]\\ \pline[8.]{R}[simplification, 5]\\ \pline[9.]{\lnot \lnot R}[double negation, 8]\\ \pline[10.]{\lnot T}[modus tollens, 3, 9]\\ \pline[11.]{(\lnot S \land \lnot T)}[adjunction, 7, 10] } \](P&Q)
(P∙Q)
¬(P→Q)
(¬P→Q)
(¬P→¬Q)
We want to understand what kinds of sentences these are, and also when they are true and when they are false. (Sometimes people wrongly assume that there is some simple distribution law for negation and conditionals, so there is some additional value to reviewing these particular examples.) The first task is to determine what kinds of sentences these are. If the first symbol of your expression is a negation, then you know the sentence is a negation. The first sentence above is a negation. If the first symbol of your expression is a parenthesis, then for our logical language we know that we are dealing with a connective that combines two sentences. The way to proceed is to match parentheses. Generally people are able to do this by eye, but if you are not, you can use the following rule. Moving left to right, the last “(” that you encounter always matches the first “)” that you encounter. These form a sentence that must have two parts combined with a connective. You can identify the two parts because each will be an atomic sentence, a negation sentence, or a more complex sentence bound with parentheses on each side of the connective. In our propositional logic, each set of paired parentheses forms a sentence of its own. So, when we encounter a sentence that begins with a parenthesis, we find that if we match the other parentheses, we will ultimately end up with two sentences as constituents, one on each side of a single connective. The connective that combines these two parts is called the “main connective”, and it tells us what kind of sentence this is. Thus, above we have examples of a negation, a conditional, and a conditional. How should we understand the meaning of these sentences? Here we can use truth tables in a new, third way (along with defining a connective and checking arguments). Our method will be this. First, write out the sentence on the right, leaving plenty of room. Identify what kind of sentence this is. If it is a negation sentence, you should add just to the left a column for the non-negated sentence. This is because the truth table defining negation tells us what a negated sentence means in relation to the non-negated sentence that forms the sentence. If the sentence is a conditional, make two columns to the left, one for the antecedent and one for the consequent. If the sentence is a conjunction, make two columns to the left, one for each conjunct. Here again, we do this because the semantic definitions of these connectives tell us what the truth value of the sentence is, as a function of the truth value of its two parts. Continue this process until the parts would be atomic sentences. Then, we stipulate all possible truth values for the atomic sentences. Once we have done this, we can fill out the truth table, working left to right. Let’s try it for ¬(P→Q). We write it to the right.¬(P→Q) |
---|
(P→Q) | ¬(P→Q) |
---|---|
P | Q | (P→Q) | ¬(P→Q) |
---|---|---|---|
T | T | ||
T | F | ||
F | T | ||
F | F |
P | Q | (P→Q) | ¬(P→Q) |
---|---|---|---|
T | T | T | |
T | F | F | |
F | T | T | |
F | F | T |
P | Q | (P→Q) | ¬(P→Q) |
---|---|---|---|
T | T | T | F |
T | F | F | T |
F | T | T | F |
F | F | T | F |
P | Q | ¬P | (¬P→Q) |
---|---|---|---|
T | T | F | T |
T | F | F | T |
F | T | T | T |
F | F | T | F |
P | Q | ¬P | ¬Q | (¬P→¬Q) |
---|---|---|---|---|
T | T | F | F | T |
T | F | F | T | T |
F | T | T | F | F |
F | F | T | T | T |
U | V | (U^V) | ¬(U^V) | ¬U | ¬V | (¬U^¬V) |
---|---|---|---|---|---|---|
T | T | T | F | F | F | F |
T | F | F | T | F | T | F |
F | T | F | T | T | F | F |
F | F | F | T | T | T | T |
P | Q | ¬Q | (P→Q) | (P^¬Q) | ¬(P→Q) | ((P^¬Q)→¬(P→Q)) |
---|---|---|---|---|---|---|
T | T | F | T | F | F | T |
T | F | T | F | T | T | T |
F | T | F | T | F | F | T |
F | F | T | T | F | F | T |
If whales are mammals, then they have vestigial limbs. If whales are mammals, then they have a quadrupedal ancestor. Therefore, if whales are mammals then they have a quadrupedal ancestor and they have vestigial limbs.
We need a translation key.P: Whales are mammals.
Q: Whales have have vestigial limbs.
R: Whales have a quadrupedal ancestor.
The argument will then be symbolized as:(P→Q)
(P→R)
____
(P→(R^Q))
premise | premise | conclusion | ||||
P | Q | R | (P→Q) | (P→R) | (R^Q) | (P→(R^Q)) |
T | T | T | T | T | T | T |
T | T | F | T | F | F | F |
T | F | T | F | T | F | F |
T | F | F | F | F | F | F |
F | T | T | T | T | T | T |
F | T | F | T | T | F | T |
F | F | T | T | T | F | T |
F | F | F | T | T | F | T |
“I suspect Dr. Kronecker of the crime of stealing Cantor’s book,” Inspector Tarski said. His assistant, Mr. Carroll, waited patiently for his reasoning. “For,” Tarski said, “The thief left cigarette ashes on the table. The thief also did not wear shoes, but slipped silently into the room. Thus, If Dr. Kronecker smokes and is in his stocking feet, then he most likely stole Cantor’s book.” At this point, Tarski pointed at Kronecker’s feet. “Dr. Kronecker is in his stocking feet.” Tarski reached forward and pulled from Kronecker’s pocket a gold cigarette case. “And Kronecker smokes.” Mr. Carroll nodded sagely, “Your conclusion is obvious: Dr. Kronecker most likely stole Cantor’s book.”
]]>Hereby it is manifest that during the time men live without a common power to keep them all in awe, they are in that condition which is called war; and such a war as is of every man against every man…. In such condition there is no place for industry, because the fruit thereof is uncertain: and consequently no culture of the earth; no navigation, nor use of the commodities that may be imported by sea; no commodious building; no instruments of moving and removing such things as require much force; no knowledge of the face of the earth; no account of time; no arts; no letters; no society; and which is worst of all, continual fear, and danger of violent death; and the life of man, solitary, poor, nasty, brutish, and short.^{[8]}Hobbes developed what is sometimes called “contract theory”. This is a view of government in which one views the state as the product of a rational contract. Although we inherit our government, the idea is that in some sense we would find it rational to choose the government, were we ever in the position to do so. So, in the passage above, Hobbes claims that in this state of nature, we have absolute freedom, but this leads to universal struggle between all people. There can be no property, for example, if there is no power to enforce property rights. You are free to take other people’s things, but they are also free to take yours. Only violence can discourage such theft. But, a common power, like a king, can enforce rules, such as property rights. To have this common power, we must give up some freedoms. You are (or should be, if it were ever up to you) willing to give up those freedoms because of the benefits that you get from this. For example, you are willing to give up the freedom to just seize people’s goods, because you like even more that other people cannot seize your goods. We can reconstruct Hobbes’s defense of government, greatly simplified, as being something like this:
If we want to be safe, then we should have a state that can protect us.
If we should have a state that can protect us, then we should give up some freedoms.
Therefore, if we want to be safe, then we should give up some freedoms.
Let us use the following translation key.P: We want to be safe.
Q: We should have a state that can protect us.
R: We should give up some freedoms.
The argument in our logical language would then be:(P→Q)
(Q→R)
_____
(P→R)
This is a valid argument. Let’s take the time to show this with a truth table.premise | premise | conclusion | |||
P | Q | R | (P→Q) | (Q→R) | (P→R) |
T | T | T | T | T | T |
T | T | F | T | F | F |
T | F | T | F | T | T |
T | F | F | F | T | F |
F | T | T | T | T | T |
F | T | F | T | F | T |
F | F | T | T | T | T |
F | F | F | T | T | T |
If you are Pope, then you have a home in the Vatican.
If you have a home in the Vatican, then you hear church bells often.
_____
If you are Pope, then you hear church bells often.
That is a valid argument, with the same form as the argument we adopted from Hobbes. However, if we broke our rule about conditional derivations, we could prove that you are Pope. Let’s use this key:S: You are Pope.
T: You have a home in the Vatican.
U: You hear church bells often.
Now consider this “proof”: \[ \fitchprf{\pline[1.]{(S \lif T)} [premise]\\ \pline[2.]{(T \lif U))} [premise]\\ } { \subproof{\pline[3.]{S}[assumption for conditional derivation]}{ \pline[4]{T}[modus ponens, 1, 3]\\ \pline[5.]{U}[modus ponens, 2, 4] } \pline[6.]{(S \lif U)}[conditional derivation, 3-5]\\ \pline[7.]{S}[repeat, 3] } \] And, thus, we have proven that you are Pope. But, of course, you are not the Pope. From true premises, we ended up with a false conclusion, so the argument is obviously invalid. What went wrong? The problem was that after we completed the conditional derivation that occurs in lines 3 through 5, and used that conditional derivation to assert line 6, we can no longer use those lines 3 through 5. But on line 7 we made use of line 3. Line 3 is not something we know to be true; our reasoning from lines 3 through line 5 was to ask, if S were true, what else would be true? When we are done with that conditional derivation, we can use only the conditional that we derived, and not the steps used in the conditional derivation.(P→Q)
(R→S)
_____
((P^R)→(Q^S))
We always begin by constructing a direct proof, using the Fitch bar to identify the premises of our argument, if any. \[ \fitchprf{\pline[1.]{(P \lif Q)} [premise]\\ \pline[2.]{(R \lif S)} [premise]\\ } { } \] Because the conclusion is a conditional, we assume the antecedent and show the consequent. \[ \fitchprf{\pline[1.]{(P \lif Q)} [premise]\\ \pline[2.]{(R \lif S)} [premise]\\ } { \subproof{\pline[3.]{(P \land R)}[assumption for conditional derivation]}{ \pline[4]{P}[simplification, 3]\\ \pline[5.]{Q}[modus ponens, 1, 4]\\ \pline[6.]{R}[simplification, 3]\\ \pline[7.]{S}[modus ponens, 2, 6]\\ \pline[8.]{(Q \land S)}[adjunction, 5, 7] } \pline[9.]{((P \land R) \lif (Q \land S))}[conditional derivation, 3-8] } \] Here’s another example. Note that the following argument is valid.(P→(S→R))
(P→(Q→S))
_____
(P→(Q→R))
The proof will require several embedded subproofs. \[ \fitchprf{\pline[1.]{(P \lif (S \lif R))} [premise]\\ \pline[2.]{(P \lif (Q \lif S))} [premise]\\ } { \subproof{\pline[3.]{P}[assumption for conditional derivation]}{ \subproof{\pline[4.]{Q} [assumption for conditional derivation]}{ \pline[5.]{(Q \lif S)}[modus ponens, 2, 3]\\ \pline[6.]{S}[modus ponens, 5, 4]\\ \pline[7.]{(S \lif R)}[modus ponens, 1, 3]\\ \pline[8.]{R}[modus ponens, 7, 6] } \pline[9.]{(Q \lif R)}[conditional derivation, 4-8] } \pline[10.]{(P \lif (Q \lif R))}[conditional derivation, 3-9] } \]((P→Q) →(¬Q→¬P))
This sentence is a tautology. To check this, we can make its truth table.P | Q | ¬Q | ¬P | (P→Q) | (¬Q→¬P) | ((P→Q) → (¬Q→¬P)) |
---|---|---|---|---|---|---|
T | T | F | F | T | T | T |
T | F | T | F | F | F | T |
F | T | F | T | T | T | T |
F | F | T | T | T | T | T |
Theorem: a sentence that can be proved without premises.
Tautology: a sentence of the propositional logic that must be true.
Piety is that which is loved by the gods and impiety is that which is not loved by them.
Socrates observes that this is ambiguous. It could mean, an act is good because the gods love that act. Or it could mean, the gods love an act because it is good. We have, then, an “or” statement, which logicians call a “disjunction”:Either an act is good because the gods love that act, or the gods love an act because it is good.
Might the former be true? This view—that an act is good because the gods love it—is now called “divine command theory”, and theists have disagreed since Socrates’s time about whether it is true. But, Socrates finds it absurd. For, if tomorrow the gods love, say, murder, then, tomorrow murder would be good. Euthyphro comes to agree that it cannot be that an act is good because the gods love that act. Our argument so far has this form:Either an act is good because the gods love that act, or the gods love an act because it is good.
It is not the case that an act is good because the gods love it.
Socrates concludes that the gods love an act because it is good.Either an act is good because the gods love that act, or the gods love an act because it is good.
It is not the case that an act is good because the gods love it.
_____
The gods love an act because it is good.
This argument is one of the most important arguments in philosophy. Most philosophers consider some version of this argument both valid and sound. Some who disagree with it bite the bullet and claim that if tomorrow God (most theistic philosophers alive today are monotheists) loved puppy torture, adultery, random acts of cruelty, pollution, and lying, these would all be good things. (If you are inclined to say, “That is not fair, God would never love those things”, then you have already agreed with Socrates. For, the reason you believe that God would never love these kinds of acts is because these kinds of acts are bad. But then, being bad or good is something independent of the love of God.) But most philosophers agree with Socrates: they find it absurd to believe that random acts of cruelty and other such acts could be good. There is something inherently bad to these acts, they believe. The importance of the Euthyphro argument is not that it helps illustrate that divine command theory is an enormously strange and costly position to hold (though that is an important outcome), but rather that the argument shows ethics can be studied independently of theology. For, if there is something about acts that makes them good or bad independently of a god’s will, then we do not have to study a god’s will to study what makes those acts good or bad. Of course, many philosophers are atheists so they already believed this, but for most of philosophy’s history, one was obliged to be a theist. Even today, lay people tend to think of ethics as an extension of religion. Philosophers believe instead that ethics is its own field of study. The Euthyphro argument explains why, even if you are a theist, you can study ethics independently of studying theology. But is Socrates’s argument valid? Is it sound?Tom will go to Berlin or Paris.
We have coffee or tea.
This web page contains the phrase “Mark Twain” or “Samuel Clemens.”
Logicians call these kinds of sentences “disjunctions”. Each of the two parts of a disjunction is called a “disjunct”. The idea is that these are really equivalent to the following sentences:Tom will go to Berlin or Tom will go to Paris.
We have coffee or we have tea.
This web page contains the phrase “Mark Twain” or this web page contains the phrase “Samuel Clemens.”
We can, therefore, see that (at least in many sentences) the “or” operates as a connective between two sentences. It is traditional to use the symbol “v” for “or”. This comes from the Latin “vel,” meaning (in some contexts) or. The syntax for the disjunction is very basic. If Φ and Ψ are sentences, then(Φ v Ψ)
is a sentence. The semantics is a little more controversial. This much of the defining truth table, most people find obvious:Φ | Ψ | (ΦvΨ) |
---|---|---|
T | T | |
T | F | T |
F | T | T |
F | F | F |
Φ | Ψ | (ΦvΨ) |
---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Φ | Ψ | (Φ ^ Ψ) | (Φ v Ψ) | ¬(Φ ^ Ψ) | ((Φ v Ψ) ^ ¬(Φ ^ Ψ)) |
---|---|---|---|---|---|
T | T | T | T | F | F |
T | F | F | T | T | T |
F | T | F | T | T | T |
F | F | F | F | T | F |
P or Q
Either P or Q
These are both expressed in our logic with (P v Q). One expression that does arise in English is “neither…nor…”. This expression seems best captured by simply making it into “not either… or…”. Let’s test this proposal. Consider the sentenceNeither Smith nor Jones will go to London.
This sentence expresses the idea that Smith will not go to London, and that Jones will not go to London. So, it would surely be a mistake to express it asEither Smith will not go to London or Jones will not go to London.
Why? Because this latter sentence would be true if one of them went to London and one of them did not. Consider the truth table for this expression to see this. Use the following translation key.P: Smith will go to London.
Q: Jones will go to London.
Then suppose we did (wrongly) translate “Neither Smith nor Jones will go to London” with(¬P v ¬Q)
Here is the truth table for this expression.P | Q | ¬Q | ¬P | (¬Pv¬Q) |
---|---|---|---|---|
T | T | F | F | F |
T | F | T | F | T |
F | T | F | T | T |
F | F | T | T | T |
P | Q | (PvQ) | ¬(PvQ) |
---|---|---|---|
T | T | T | F |
T | F | T | F |
F | T | T | F |
F | F | F | T |
(Φ v Ψ)
¬Φ
_____
Ψ
and(Φ v Ψ)
¬Ψ
_____
Φ
This rule is traditionally called “modus tollendo ponens”. What if we are required to show a disjunction? One insight we can use is that if some sentence is true, then any disjunction that contains it is true. This is so whether the sentence makes up the first or second disjunct. Again, then, we would have two rules, which we can group together under one name:Φ
_____
(Φ v Ψ)
andΨ
_____
(Φ v Ψ)
P: An act is good because the gods love that act.
Q: The gods love an act because it is good.
Euthyphro had argued \[ \fitchprf{\pline[1.]{(P \lor Q)}[premise]} { } \] Socrates had got Euthryphro to admit that \[ \fitchprf{ \pline[1.]{(P \lor Q)}[premise]\\ \pline[2.]{\lnot P}[premise] } { } \] And so we have a simple direct derivation: \[ \fitchprf{ \pline[1.]{(P \lor Q)}[premise]\\ \pline[2.]{\lnot P}[premise] } { \pline[3.]{Q}[modus tollendo ponens, 1, 2] } \] Socrates’s argument is valid. I will leave it up to you to determine whether Socrates’s argument is sound. Another example might be helpful. Here is an argument in our logical language.(P v Q)
¬P
(¬P → (Q → R))
_____
(R v S)
This will make use of the addition rule, and so is useful to illustrating that rule’s application. Here is one possible proof. \[ \fitchprf{ \pline[1.]{(P \lor Q)}[premise]\\ \pline[2.]{\lnot P}[premise]\\ \pline[3.]{(\lnot P \lif (Q \lif R))}[premise] } { \pline[4.]{Q}[modus tollendo ponens, 1, 2]\\ \pline[5.]{(Q \lif R)}[modus ponens, 3, 2]\\ \pline[6.]{R}[modus ponens, 5, 4]\\ \pline[7.]{(R \lor S)}[addition, 6] } \](P || Q)
Either Dr. Kronecker or Bishop Berkeley killed Colonel Cardinality. If Dr. Kronecker killed Colonel Cardinality, then Dr. Kronecker was in the kitchen. If Bishop Berkeley killed Colonel Cardinality, then he was in the drawing room. If Bishop Berkeley was in the drawing room, then he was wearing boots. But Bishop Berkeley was not wearing boots. So, Dr. Kronecker killed the Colonel.
Either Wittgenstein or Meinong stole the diamonds. If Meinong stole the diamonds, then he was in the billiards room. But if Meinong was in the library, then he was not in the billiards room. Therefore, if Meinong was in the library, Wittgenstein stole the diamonds.
{1, 2, 3, 4, 5, 6, 7, ….}
He also proposes that we take as a premise that there is an actual infinity of the squares of the natural numbers.{1, 4, 9, 16, 25, 36, 49, ….}
Now, Galileo reasons, note that these two groups (today we would call them “sets”) have the same size. We can see this because we can see that there is a one-to-one correspondence between the two groups.{1, | 2, | 3, | 4, | 5, | 6, | 7, ….} |
{1, | 4, | 9, | 16, | 25, | 36, | 49, ...} |
{2, 3, 5, 6, 7, 8, 10, ….}
So, Galileo reasons, if there are many numbers in the group of natural numbers that are not in the group of the square numbers, and if there are no numbers in the group of the square numbers that are not in the naturals numbers, then the natural numbers is bigger than the square numbers. And if the group of the natural numbers is bigger than the group of the square numbers, then the natural numbers and the square numbers are not the same size. We have reached two conclusions: the set of the natural numbers and the set of the square numbers are the same size; and, the set of the natural numbers and the set of the square numbers are not the same size. That’s contradictory. Galileo argues that the reason we reached a contradiction is because we assumed that there are actual infinities. He concludes, therefore, that there are no actual infinities.(P→(QvR))
¬Q
¬R
_____
¬P
This argument looks valid. By the first premise we know: if P were true, then so would (Q v R) be true. But then either Q or R or both would be true. And by the second and third premises we know: Q is false and R is false. So it cannot be that (Q v R) is true, and so it cannot be that P is true. We can check the argument using a truth table. Our table will be complex because one of our premise is complex.premise | premise | premise | conclusion | ||||
P | Q | R | (QvR) | (P→(QvR)) | ¬Q | ¬R | ¬P |
T | T | T | T | T | F | F | F |
T | T | F | T | T | F | T | F |
T | F | T | T | T | T | F | F |
T | F | F | F | F | T | T | F |
F | T | T | T | T | F | F | T |
F | T | F | T | T | F | T | T |
F | F | T | T | T | T | F | T |
F | F | F | F | T | T | T | T |
P | ¬P | (P ^ ¬P) |
---|---|---|
T | F | F |
F | T | F |
P: There are actual infinities (including the natural numbers and the square numbers).
Q: There is a one-to-one correspondence between the natural numbers and the square numbers.
R: The size of the set of the natural numbers and the size of the set of the square numbers are the same.
S: All the square numbers are natural numbers.
T: Some of the natural numbers are not square numbers.
U: There are more natural numbers than square numbers.
With this key, the argument will be translated:(P→Q)
(Q→R)
(P→(S^T))
((S^T)→U)
(U→¬R)
______
¬P
And we can prove this is a valid argument by using indirect derivation: \[ \fitchprf{\pline[1.]{(P \lif Q)} [premise]\\ \pline[2.]{(Q \lif R)} [premise]\\ \pline[3.]{(P \lif (S \land T))} [premise]\\ \pline[4.]{((S \land T) \lif U)}[premise]\\ \pline[5.]{(U \lif \lnot R)} [premise] } { \subproof{\pline[6.]{\lnot \lnot P}[assumption for indirect derivation]}{ \pline[7.]{P}[double negation, 6]\\ \pline[8.]{Q}[modus ponens, 1, 7]\\ \pline[9.]{R}[modus ponens, 2, 8]\\ \pline[10.]{(S \land T)}[modus ponens, 3, 7]\\ \pline[11.]{U}[modus ponens, 4, 10]\\ \pline[12.]{\lnot R}[modus ponens, 5, 11]\\ \pline[13.]{R}[repeat, 9] } \pline[14.]{\lnot P}[indirect derivation, 6-13] } \] On line 6, we assumed ¬¬P because Galileo believed that ¬P and aimed to prove that ¬P. That is, he believed that there are no actual infinities, and so assumed that it was false to believe that it is not the case that there are no actual infinities. This falsehood will lead to other falsehoods, exposing itself. For those who are interested: Galileo concluded that there are no actual infinities but there are potential infinities. Thus, he reasoned, it is not the case that all the natural numbers exist (in some sense of “exist”), but it is true that you could count natural numbers forever. Many philosophers before and after Galileo held this view; it is similar to a view held by Aristotle, who was an important logician and philosopher writing nearly two thousand years before Galileo. Note that in an argument like this, you could reason that not the assumption for indirect derivation, but rather one of the premises was the source of the contradiction. Today, most mathematicians believe this about Galileo’s argument. A logician and mathematician named Georg Cantor (1845-1918), the inventor of set theory, argued that infinite sets can have proper subsets of the same size. That is, Cantor denied premise 4 above: even though all the square numbers are natural numbers, and not all natural numbers are square numbers, it is not the case that these two sets are of different size. Cantor accepted however premise 2 above, and, therefore, believed that the size of the set of natural numbers and the size of the set of square numbers is the same. Today, using Cantor’s reasoning, mathematicians and logicians study infinity, and have developed a large body of knowledge about the nature of infinity. If this interests you, see section 17.5. Let us consider another example to illustrate indirect derivation. A very useful set of theorems are today called “De Morgan’s Theorems”, after the logician Augustus De Morgan (1806–1871). We cannot state these fully until chapter 9, but we can state their equivalent in English: DeMorgan observed that ¬(PvQ) and (¬P^¬Q) are equivalent, and also that ¬(P^Q) and (¬Pv¬Q) are equivalent. Given this, it should be a theorem of our language that (¬(PvQ)→(¬P^¬Q)). Let’s prove this. The whole formula is a conditional, so we will use a conditional derivation. Our proof must thus begin: \[ \fitchprf{} { \subproof{\pline[1.]{\lnot (P \lor Q)}[assumption for conditional derivation]}{ } } \] To complete the conditional derivation, we must prove (¬P^¬Q). This is a conjunction, and our rule for showing conjunctions is adjunction. Since using this rule might be our best way to show (¬P^¬Q), we can aim to show ¬P and then show ¬Q, and then perform adjunction. But, we obviously have very little to work with—just line 1, which is a negation. In such a case, it is typically wise to attempt an indirect proof. Start with an indirect proof of ¬P. \[ \fitchprf{} { \subproof{\pline[1.]{\lnot (P \lor Q)}[assumption for conditional derivation]}{ \subproof{\pline[2.]{\lnot \lnot P}[assumption for indirect derivation]}{ \pline[3.]{P}[double negation, 2]\\ } } } \] We now need to find a contradiction—any contradiction. But there is an obvious one already. Line 1 says that neither P nor Q is true. But line 3 says that P is true. We must make this contradiction explicit by finding a formula and its denial. We can do this using addition. \[ \fitchprf{} { \subproof{\pline[1.]{\lnot (P \lor Q)}[assumption for conditional derivation]}{ \subproof{\pline[2.]{\lnot \lnot P}[assumption for indirect derivation]}{ \pline[3.]{P}[double negation, 2]\\ \pline[4.]{(P \lor Q)}[addition, 3]\\ \pline[5.]{\lnot (P \lor Q)}[repeat, 1] } \pline[6.]{\lnot P}[indirect derivation 2-5] } } \] To complete the proof, we will use this strategy again. \[ \fitchprf{} { \subproof{\pline[1.]{\lnot (P \lor Q)}[assumption for conditional derivation]}{ \subproof{\pline[2.]{\lnot \lnot P}[assumption for indirect derivation]}{ \pline[3.]{P}[double negation, 2]\\ \pline[4.]{(P \lor Q)}[addition, 3]\\ \pline[5.]{\lnot (P \lor Q)}[repeat, 1] } \pline[6.]{\lnot P}[indirect derivation 2-5]\\ \subproof{\pline[7.]{\lnot \lnot Q}[assumption for indirect derivation]}{ \pline[8.]{Q}[double negation, 7]\\ \pline[9.]{(P \lor Q)}[addition, 8]\\ \pline[10.]{\lnot (P \lor Q)}[repeat, 1] } \pline[11.]{\lnot Q}[indirect derivation 7-10]\\ \pline[12.]{(\lnot P \land \lnot Q)}[adjunction, 6, 11] } \pline[13.]{(\lnot (P \lor Q) \lif (\lnot P \land \lnot Q))}[conditional derivation 1-12] } \] We will prove De Morgan’s theorems as problems for chapter 9. Here is a general rule of thumb for doing proofs: When proving a conditional, always do conditional derivation; otherwise, try direct derivation; if that fails, then, try indirect derivation.Blassingame, J. W. (1985) (ed.), The Frederick Douglass Papers. Series One: Speeches, Debates, and Interviews. Volume 3: 1855-63 (New Haven: Yale University Press).
Carnap, R. (1956), Meaning and Necessity: A Study in Semantics and Modal Logic (Chicago: University of Chicago, Phoenix Books).
Carter, K. C. (ed., tr.) (1983), The Etiology, Concept, and Prophylaxis of Childbed Fever, by Ignaz Semmelweis (Madison: University of Wisconsin Press).
—— and Carter, B. R. (2008), Childbed Fever: A Scientific Biography of Ignaz Semmelweis (New Brunswick, NJ: Transaction Publishers).
Chalmers, D. (1996), The Conscious Mind (New York: Oxford University Press).
Cooper, J. M. and Hutchinson. D. S. (1997) (eds.), Plato: Complete Works (Indianapolis: Hackett Publishing).
Drake, S. (1974) (ed. and translator) Galileo: The Two New Sciences (Madison: University of Wisconsin Press).
Duhem, P. (1991), The Aim and Structure of Physical Theory (Princeton: Princeton University Press).
Grice, P. (1975), “Logic and conversation” in P. Cole and J. Morgan (eds.), Syntax and Semantics, 3: Speech Acts. (New York: Academic Press), 41–58.
Hobbes, T. (1886), Leviathan, with an introduction by Henry Morley (London: Routledge and Sons).
Mendelson, E. (2010), Introduction to Mathematical Logic. (5th edn., New York: Taylor & Francis Group, CRC Press).
Russell, B. (1905), “On Denoting.” Mind, 14: 479-493.
Selby-Bigge, L. A. and Nidditch, P. H. (1995) (eds.), An Enquiry Concerning Human Understanding and Concerning the Principles of Morals, by David Hume (Oxford: Oxford University Press).
Tarski, A. (1956), Logic, Semantics, Metamathematics (Oxford: Oxford University Press).
Wason, P. C. (1966), “Reasoning,” In Foss, B. M. New Horizons in Psychology 1. (Harmondsworth, England: Penguin).
]]>We can add to Frederick Douglass’s words that: find out just how much a person can be deceived, and that is just how far she will be deceived. The limits of tyrants are also prescribed by the reasoning abilities of those they aim to oppress. And what logic teaches you is how to demand and recognize good reasoning, and so how to avoid deceit. You are only as free as your powers of reasoning enable.Power concedes nothing without a demand. It never did and it never will. Find out just what any people will quietly submit to and you have found out the exact measure of injustice and wrong which will be imposed upon them, and these will continue till they are resisted with either words or blows, or with both. The limits of tyrants are prescribed by the endurance of those whom they oppress.^{[1]}
When we run over libraries, persuaded of these principles, what havoc must we make? If we take in our hand any volume of divinity or school metaphysics, for instance, let us ask, Does it contain any abstract reasoning concerning quantity or number? No. Does it contain any experimental reasoning concerning matter of fact and existence? No. Commit it then to the flames, for it can contain nothing but sophistry and illusion.^{[11]}Hume felt that the only sources of knowledge were logical or mathematical reasoning (which he calls above “abstract reasoning concerning quantity or number”) or sense experience (“experimental reasoning concerning matter of fact and existence”). Hume is led to argue that any claims not based upon one or the other method is worthless. We can reconstruct Hume’s argument in the following way. Suppose t is some topic about which we claim to have knowledge. Suppose that we did not get this knowledge from experience or logic. Written in English, we can reconstruct his argument in the following way:
We have knowledge about t if and only if our claims about t are learned from experimental reasoning or from logic or mathematics.
Our claims about t are not learned from experimental reasoning.
Our claims about t are not learned from logic or mathematics.
_____
We do not have knowledge about t.
What does that phrase “if and only if” mean? Philosophers think that it, and several synonymous phrases, are used often in reasoning. Leaving “if and only” unexplained for now, we can use the following translation key to write up the argument in a mix of our propositional logic and English.P: We have knowledge about t.
Q: Our claims about t are learned from experimental reasoning.
R: Our claims about t are learned from logic or mathematics.
And so we have:P if and only if (QvR)
¬Q
¬R
_____
¬P
Our task is to add to our logical language an equivalent to “if and only if”. Then we can evaluate this reformulation of Hume’s argument.P | Q | (Q → P) | (P → Q) | ((Q→P)^(P→Q)) |
T | T | T | T | T |
T | F | T | F | F |
F | T | F | T | F |
F | F | T | T | T |
(Φ↔Ψ)
is a sentence. This kind of sentence is typically called a “biconditional”. The semantics is given by the following truth table.Φ | Ψ | (Φ↔Ψ) |
T | T | T |
T | F | F |
F | T | F |
F | F | T |
P if and only if Q.
P just in case Q.
P is necessary and sufficient for Q.
P is equivalent to Q.
(Φ↔Ψ)
Φ
_____
Ψ
(Φ↔Ψ)
Ψ
_____
Φ
(Φ↔Ψ)
¬Φ
_____
¬Ψ
(Φ↔Ψ)
¬Ψ
_____
¬Φ
(Φ→Ψ)
(Ψ→Φ)
_____
(Φ↔Ψ)
This means that often when we aim to prove a biconditional, we will undertake two conditional derivations to derive two conditionals, and then use the bicondition rule. That is, many proofs of biconditionals have the following form: \[ \fitchctx{ \subproof{\pline{\phi}}{ \ellipsesline\\ \pline{\psi} } \fpline{(\phi \lif \psi)}\\ \subproof{\pline{\psi}}{ \ellipsesline\\ \pline{\phi} } \fpline{(\psi \lif \phi)}\\ \pline{(\phi \liff \psi)} } \](¬(PvQ)↔(¬P^¬Q))
(¬(P^Q)↔(¬Pv¬Q))
We will prove the second of these theorems. This is perhaps the most difficult proof we have seen; it requires nested indirect proofs, and a fair amount of cleverness in finding what the relevant contradiction will be. \[ \fitchprf{} { \subproof{\pline[1.]{\lnot (P \land Q)}[assumption for conditional derivation]}{ \subproof{\pline[2.]{\lnot(\lnot P \lor \lnot Q)}[assumption for indirect derivation]}{ \subproof{\pline[3.]{\lnot P}[assumption for indirect derivation]}{ \pline[4.]{(\lnot P \lor \lnot Q)}[addition, 3]\\ \pline[5.]{\lnot(\lnot P \lor \lnot Q)}[repeat, 2]\\ } \pline[6.]{P}[indirect derivation, 3-5]\\ \subproof{\pline[7.]{\lnot Q}[assumption for indirect derivation]}{ \pline[8.]{(\lnot P \lor \lnot Q)}[addition, 7]\\ \pline[9.]{\lnot(\lnot P \lor \lnot Q)}[repeat, 2]\\ } \pline[10.]{Q}[indirect derivation, 6-9]\\ \pline[11.]{(P \land Q)}[adjunction, 6, 10]\\ \pline[12.]{\lnot (P \land Q)}[repeat, 1]\\ } \pline[13.]{(\lnot P \lor \lnot Q)}[indirect derivation, 2-12]\\ } \pline[14.]{(\lnot (P \land Q) \lif (\lnot P \lor \lnot Q))}[conditional derivation, 1-13]\\ \subproof{\pline[15.]{(\lnot P \lor \lnot Q)}[assumption for conditional derivation]}{ \subproof{\pline[16.]{\lnot \lnot (P \land Q)}[assumption for indirect derivation]}{ \pline[17.]{(P \land Q)}[double negation 16]\\ \pline[18.]{P}[simplification, 17]\\ \pline[19.]{\lnot \lnot P}[double negation, 18]\\ \pline[20.]{\lnot Q}[modus tollendo ponens, 15, 19]\\ \pline[21.]{Q}[simplification, 17]\\ } \pline[22.]{\lnot (P \land Q)}[indirect derivation 16-21]\\ } \pline[23.]{((\lnot P \lor \lnot Q) \lif \lnot (P \land Q))}[conditional derivation, 15-22]\\ \pline[24.]{(\lnot (P \land Q)\liff (\not P \lor \lnot Q) )}[bicondition,14, 23]\\ } \](Pv¬P)
(P↔¬P)
P
The first is a tautology, the second is a contradictory sentence, and the third is contingent. We can see this with a truth table.P | ¬P | (Pv¬P) | (P↔¬P) | P |
T | F | T | F | T |
F | T | T | F | F |
¬(Pv¬P)
¬(P↔¬P)
¬P
P | ¬P | (Pv¬P) | ¬(Pv¬P) | (P↔¬P) | ¬(P↔¬P) |
T | F | T | F | F | T |
F | T | T | F | F | T |
P: Smith will go to London.
Q: Jones will go to London.
And we have the following argument: \[ \fitchprf{\pline[1.] {\lnot (P \lor Q)} [premise]\\ }{ \pline[2.]{(\lnot (P \lor Q) \liff ( \lnot P \land \lnot Q))}[theorem]\\ \pline[3.]{( \lnot P \land \lnot Q)} [equivalence, 2, 1]\\ \pline[4.]{ \lnot Q}[simplification, 3]\\ } \] This proof was made very easy by our use of the theorem at line 2. There are two things to note about this. First, we should allow ourselves to do this, because if we know that a sentence is a theorem, then we know that we could prove that theorem in a subproof. That is, we could replace line 2 above with a long subproof that proves (¬(P v Q)↔(¬P ^ ¬Q)), which we could then use. But if we are certain that (¬(P v Q)↔(¬P ^ ¬Q)) is a theorem, we should not need to do this proof again and again, each time that we want to make use of the theorem. The second issue that we should recognize is more subtle. There are infinitely many sentences of the form of our theorem, and we should be able to use those also. For example, the following sentences would each have a proof identical to our proof of the theorem (¬(P v Q)↔(¬P ^ ¬Q)), except that the letters would be different:(¬(R v S) ↔ (¬R ^ ¬S))
(¬(T v U) ↔ (¬T ^ ¬U))
(¬(V v W) ↔ (¬V ^ ¬W))
This is hopefully obvious. Take the proof of (¬(P v Q)↔(¬P ^ ¬Q)), and in that proof replace each instance of P with R and each instance of Q with S, and you would have a proof of (¬(R v S)↔(¬R ^ ¬S)). But here is something that perhaps is less obvious. Each of the following can be thought of as similar to the theorem (¬(P v Q)↔(¬P ^ ¬Q)).(¬((P^Q) v (R^S))↔(¬(P^Q) ^ ¬(R^S)))
(¬(T v (Q v V))↔(¬T ^ ¬(Q v V))
(¬((Q↔P) v (¬R→¬Q))↔(¬(Q↔P) ^ ¬(¬R→¬Q)))
For example, if one took a proof of (¬(P v Q)↔(¬P ^ ¬Q)) and replaced each initial instance of P with (Q↔P) and each initial instance of Q with (¬R→¬Q), then one would have a proof of the theorem (¬((Q↔P) v (¬R→¬Q))↔(¬(Q↔P) ^ ¬(¬R→¬Q))). We could capture this insight in two ways. We could state theorems of our metalanguage and allow that these have instances. Thus, we could take (¬(Φ v Ψ) ↔ (¬Φ ^ ¬Ψ)) as a metalanguage theorem, in which we could replace each Φ with a sentence and each Ψ with a sentence and get a particular instance of a theorem. An alternative is to allow that from a theorem we can produce other theorems through substitution. For ease, we will take this second strategy. Our rule will be this. Once we prove a theorem, we can cite it in a proof at any time. Our justification is that the claim is a theorem. We allow substitution of any atomic sentence in the theorem with any other sentence if and only if we replace each initial instance of that atomic sentence in the theorem with the same sentence. Before we consider an example, it is beneficial to list some useful theorems. There are infinitely many theorems of our language, but these ten are often very helpful. A few we have proved. The others can be proved as an exercise.T1 (P v ¬P)
T2 (¬(P→Q) ↔ (P^¬Q))
T3 (¬(P v Q) ↔ (¬P ^ ¬Q))
T4 ((¬P v ¬Q) ↔ ¬(P ^ Q))
T5 (¬(P ↔ Q) ↔ (P ↔ ¬Q))
T6 (¬P → (P → Q))
T7 (P → (Q → P))
T8 ((P→(Q→R)) → ((P→Q) → (P→R)))
T9 ((¬P→¬Q) → ((¬P→Q) →P))
T10 ((P→Q) → (¬Q→¬P))
Some examples will make the advantage of using theorems clear. Consider a different argument, building on the one above. We know that neither is it the case that if Smith goes to London, he will go to Berlin, nor is it the case that if Jones goes to London he will go to Berlin. We want to prove that it is not the case that Jones will go to Berlin. We add the following to our key:R: Smith will go to Berlin.
S: Jones will go to Berlin.
And we have the following argument: \[ \fitchprf{\pline[1.] {\lnot ((P \lif R) \lor (Q \lif S))} [premise]\\ }{ \pline[2.]{\brokenform{(\lnot ((P \lif R) \lor (Q \lif S)) \liff}{ \formula{( \lnot (P \lif R) \land \lnot (Q \lif S)))}}}[theorem T3]\\ \pline[3.]{( \lnot (P \lif R) \land \lnot (Q \lif S))} [equivalence, 2, 1]\\ \pline[4.]{ \lnot (Q \lif S)}[simplification, 3]\\ \pline[5.]{( \lnot (Q \lif S) \liff (Q \land \lnot S))} [theorem T2]\\ \pline[6.]{(Q \land \lnot S)}[equivalence, 5, 4]\\ \pline[7.]{\lnot S}[simplification, 6] } \] Using theorems made this proof much shorter than it might otherwise be. Also, theorems often make a proof easier to follow, since we recognize the theorems as tautologies—as sentences that must be true.Φ | ¬Φ |
T | F |
F | T |
Φ | Ψ | (Φ→Ψ) |
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Φ | Ψ | (Φ ^ Ψ) |
T | T | T |
T | F | F |
F | T | F |
F | F | F |
Φ | Ψ | (Φ v Ψ) |
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Φ | Ψ | (Φ↔Ψ) |
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Modus ponens | Modus tollens | Double negation | Double negation |
(Φ→Ψ) Φ _____ Ψ | (Φ→Ψ) ¬Ψ _____ ¬Φ | Φ _____ ¬¬Φ | ¬¬Φ _____ Φ |
Addition | Addition | Modus tollendo ponens | Modus tollendo ponens |
Φ _____ (Φ v Ψ) | Ψ _____ (Φ v Ψ) | (Φ v Ψ) ¬Φ _____ Ψ | (Φ v Ψ) ¬Ψ _____ Φ |
Adjunction | Simplification | Simplification | Bicondition |
Φ Ψ _____ (Φ ^ Ψ) | (Φ ^ Ψ) _____ Φ | (Φ ^ Ψ) _____ Ψ | (Φ→Ψ) (Ψ→Φ) _____ (Φ↔Ψ) |
Equivalence | Equivalence | Equivalence | Equivalence |
(Φ↔Ψ) Φ _____ Ψ | (Φ↔Ψ) Ψ _____ Φ | (Φ↔Ψ) ¬Φ _____ ¬Ψ | (Φ↔Ψ) ¬Ψ _____ ¬Φ |
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 beP
Q
_____
R
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.a
b
c
…
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.a=a
a=b
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.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,F
G
H
I
J
K
…
are predicates.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
a: Tom
b: Steve
Then our translations would beFa
Gab
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 hadStefano 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.
c: Stefano
d: Margarita
e: Aletheia
f: Lorena
And in our language would look like this:((Ic^Id)^(Ie^If))
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.All men are mortal.
What does this “all” mean? Let’s start with a simpler example. Suppose for a moment we consider the sentenceAll is mortal.
Or, equivalently,Everything is mortal.
How should we understand this “all” or “everything”? This is a puzzle that stumped many generations of logicians. The reason is that, at first, it seems obvious how to handle this case. “All”, one might conclude, is a special name. It is a name for everything in my domain of discourse. We could then introduce a special name for this, with the following translation key.ε: all (or everything)
Mx: x is mortal
And, so we translate the sentenceMε
So far, so good. But now, what about our first sentence? Let’s add to our translation keyHx: x is human
Now how shall we translate “all men are mortal”? Most philosophers think this should be captured with a conditional (we will see why below), but look at this sentence:(Hε→Mε)
That does not at all capture what we meant to say. That sentence says: if everything is a human, then everything is mortal. We want to say just that all the humans are mortal. Using a different connective will not help.(Hε ^ Mε)
(Hε v Mε)
(Hε ↔ Mε)
All of these fail to say what we want to say. The first says everything is human and everything is mortal. The second, that everything is human or everything is mortal. The third that everything is human if and only if everything is mortal. The problem is even worse for another word that seems quite similar in its use to “all”: the word “some”. This sentence is surely true:Some men are mortal.
Suppose we treat “some” as a name, since it also appears to act like one. We might have a key like this:σ : some
And suppose, for a moment, that this meant, at least one thing in our domain of discourse. And then translate our example sentence, at least as a first attempt, as(Hσ ^ Mσ)
This says that some things are human, and some things are mortal. It might seem at first to work. But now consider a different sentence.Some things are human and some things are crabs.
That’s true. Let us introduce the predicate Kx for x is a crab. Then, it would seem we should translate this(Hσ ^ Kσ)
But that does not work. For σ, if it is a name, must refer to the same thing. But, then something is both a human and a crab, which is false. “All” and “some” are actually subtle. They look and (in some ways) act like names, but they are different than names. So, we should not treat them as names.ε: all (or everything)
σ : some
This perplexed many philosophers and mathematicians, but finally a very deep thinker whom we have already mentioned—Gottlob Frege—got clear about what is happening here, and developed what we today call the “quantifier”. The insight needed for the quantifier is that we need to treat “all” and “some” as special operators that can “bind” or “reach into” potentially several of the arity places in one or more predicates. To see the idea, consider first the simplest case. We introduce the symbol ∀ for all. However, we also introduce a variable—in this case we will use x—to be a special kind of place holder. (Or: you could think of ∀ as meaning every and x as meaning thing, and then ∀x means everything.) Now, to say “everything is human”, we would write∀xHx
Think of this sentence as saying, you can take any object from our domain of discourse, and that thing has property H. In other words, if ∀xHx is true, then Ha is true, and Hb is true, and Hc is true, and so on, for all the objects of our domain of discourse. So far, this is not much different than using a single name to mean “everything”. But there is a very significant difference when we consider a more complex formula. Consider “All men are mortal”. Most logicians believe this means that “Everything is such that, if it is human, then it is mortal”. We can write∀x(Hx→Mx)
So, if ∀x(Hx→Mx) is true, then (Ha→Ma) and (Hb→Mb) and (Hc→Mc) and so on are true. This captures exactly what we want. We did not want to say if everything is human, then everything is mortal. We wanted to say, for each thing, if it is human, then it is mortal. A similar approach will work for “some”. Let “∃” be our symbol for “some”. Then we can translateSome men are mortal
With∃x(Hx^Mx)
(We will discuss in section 13.3 below why we do not use a conditional here; at this point, we just want to focus on the meaning of the “∃”.) Read this as saying, for this example, there is at least one thing from our domain of discourse that has properties H and M. In other words, either (Ha ^ Ma) is true or (Hb ^ Mb) is true or (Hc ^ Mc) is true or etc. These new elements to our language are called “quantifiers”. The symbol “∀” is called the “universal quantifier”. The symbol “∃” is called the “existential quantifier” (to remember this, think of it as saying, “there exists at least one thing such that…”). We say that they “quantify over” the things that our language is about (that is, the things in our domain of discourse). We are now ready to provide the syntax for terms, predicates, and quantifiers.¬Φ
(Φ → Ψ)
(Φ ^ Ψ)
(Φ v Ψ)
(Φ↔Ψ)
∀αΦ
∃αΦ
If the expression Φ(α) contains no quantifiers, and α is a variable, then we say that α is a “free variable” in Φ(α). If the expression Φ(α) contains no quantifiers, and α is a variable, then we say that α is “bound” in ∀αΦ(α) and α is “bound” in ∃αΦ(α). A variable that is bound is not free. If Φ is a well-formed formula with no free variables, then it is a sentence. If Φ and Ψ are sentences, then the following are sentences:¬Φ
(Φ→Ψ)
(Φ ^ Ψ)
(Φ v Ψ)
(Φ↔Ψ)
This way of expressing ourselves is precise; but, for some of us, when seeing it for the first time, it is hard to follow. Let’s take it a step at a time. Let’s suppose that F is a predicate of arity one, that G is a predicate of arity two, and that H is a predicate of arity three. Then the following are all well-formed formulas.Fx
Fy
Fa
Gxy
Gyx
Gab
Gax
Hxyz
Haxc
Hczy
And, if we combine these with connectives, they form well-formed formulas. All of these are well-formed formulas:¬Fx
(Fx→Fy)
(Fa^Gxy)
(Gyx v Gab)
(Gax↔Hxyz)
∀xHaxc
∃zHczy
For these formulas, we say that x is a free variable in each of the first five well-formed formulas. The variable x is bound in the sixth well-formed formula. The variable z is bound in the last well-formed formula, but y is free in that formula. For the following formulae, there are no free variables.∀xFx
∃zGza
Fa
Gbc
Each of these four well-formed formulas is, therefore, a sentence. If combined using our connectives, these would make additional sentences. For example, these are all sentences:¬∀xFx
(∀xFx→∃zGza)
(Fa ^ Gbc)
(Gbc ↔ ∃zGza)
(Gbc v ∃zGza)
The basic idea is that in addition to sentences, we recognize formulae that have the right shape to be a sentence, if only they had names instead of variables in certain places in the formula. These then become sentences when combined with a quantifier binding that variable, because now the variable is no longer a meaningless placeholder, and instead stands for any or some object in our language. What about the semantics for the quantifiers? This will, unfortunately, have to remain intuitive during our development of first order logic. We need set theory to develop a semantics for the quantifiers; truth tables will not work. In chapter 17, you can read a little about how to construct a proper semantics for the quantifiers. Here, let us simply understand the universal quantifier, “∀”, as meaning every object in our domain of discourse; and understand the existential quantifier, “∃”, as meaning at least one object in our domain of discourse. A note about the existential quantifier. “Some” in English does not often mean at least one. If you ask your friend for some of her french fries, and she gives you exactly one, you will feel cheated. However, we will likely agree that there is no clear norm for the number of french fries that she must give you, in order to satisfy your request. In short, the word “some” is vague in English. This is a useful vagueness—we don’t want to have to say things like, “Give me 11 french fries, please”. But, our logical language must be precise, and so, it must have no vagueness. For this reason, we interpret the existential quantifier to mean at least one.Everything is human.
Something is human.
Something is not human.
Nothing is human.
All humans are mortal.
Some humans are mortal.
Some humans are not mortal.
No humans are mortal.
Our goal is to decide how best to translate each of these. Then, we will generalize. Let us use our key above, in which “Hx” means x is human, and “Mx” means x is mortal. The first two sentences are straightforward. The following are translations.∀xHx
∃xHx
What about the third sentence? It is saying there is something, and that thing is not human. A best translation of that would be to start with the “something”.∃x¬Hx
That captures what we want. At least one thing is not human. Contrast this with the next sentence. We can understand it as saying, It is not the case that something is human. That is translated:¬∃xHx
(It turns out that “∃x¬Hx” and “¬∀xHx” are equivalent and “¬∃xHx” and “∀x¬Hx” are equivalent; so we could also translate “Something is not human” with “¬∀xHx”, and “Nothing is human” with “∀x¬Hx”. However, this author finds these less close to the English in syntactic form.) The next four are more subtle. “All humans are mortal” seems to be saying, if anything is human, then that thing is mortal. That tells us directly how to translate the expression:∀x(Hx→Mx)
What about “some humans are mortal”? This is properly translated with:∃x(Hx^Mx)
Many students suspect there is some deep similarity between “all humans are mortal” and “some humans are mortal”, and so want to translate “some humans are mortal” as ∃x(Hx→Mx). This would be a mistake. Remember the truth table for the conditional; if the antecedent is false, then the conditional is true. Thus, the formula ∃x(Hx→Mx) would be true if there were no humans, and it would be true if there were no humans and no mortals. That might seem a bit abstract, so let’s leave off our language about humans and mortality, and consider a different first order logic language, this one about numbers. Our domain of discourse, let us suppose, is the natural numbers (1, 2, 3, …). Let “Fx” mean “x is even” and “Gx” mean “x is odd”. Now consider the following formula:Some even number is odd.
We can agree that, for the usual interpretation of “odd” and “even”, this sentence is false. But now suppose we translated it as∃x(Fx→Gx)
This sentence is true. That’s because there is at least one object in our domain of discourse for which it is true. For example, consider the number 3 (or any odd number). Suppose that in our logical language, a means 3. Then, the following sentence is true:(Fa→Ga)
This sentence is true because the antecedent is false, and the consequent is true. That makes the whole conditional true. Clearly, “∃x(Fx→Gx)” cannot be a good translation of “Some even number is odd”, because whereas “Some even number is odd” is false, “∃x(Fx→Gx)” is true. The better translation is∃x(Fx^Gx)
This says, some number is both even and odd. That’s clearly false, matching the truth value of the English expression. To return to our language about humans and mortality. The sentence “some human is mortal” should be translated∃x(Hx^Mx)
And this makes clear how we can translate, “some human is not mortal”:∃x(Hx ^ ¬Mx)
The last sentence, “No humans are mortal” is similar to “Nothing is human”. We can read it as meaning It is not the case that some humans are mortal, which we can translate:¬∃x(Hx^Mx)
(It turns out that this sentence is equivalent to, “all humans are not mortal”. Thus, we could also translate the sentence with:∀x(Hx→¬Mx).)
We need to generalize these eight forms. Let Φ and Ψ be expressions (these can be complex). Let α be any variable. Then, we can give the eight forms schematically in the following way.Everything is Φ
∀αΦ(α)
Something is Φ
∃αΦ(α)
Something is not Φ
∃α¬Φ(α)
Nothing is Φ
¬∃αΦ(α)
All Φ are Ψ
∀α(Φ(α)→Ψ(α))
Some Φ are Ψ
∃α (Φ(α) ^ Ψ(α))
Some Φ are not Ψ
∃α (Φ(α) ^ ¬Ψ(α))
No Φ are Ψ
¬∃α (Φ(α)^ Ψ(α))
These eight forms include the most common forms of sentences that we encounter in English that use quantifiers. This may not, at first, seem plausible, but, when we recognize that these generalized forms allow that the expression Φ or Ψ can be complex, then, we see that the following are examples of the eight forms, given in the same order:Everything is a female human from Texas.
Something is a male human from Texas.
Something is not a female human computer scientist from Texas.
Nothing is a male computer scientist from Texas.
All male humans are mortal mammals.
Some female humans are computer scientists who live in Texas.
Some female humans are not computer scientists who live in Texas.
No male human is a computer scientist who lives in Texas.
The task in translating such sentences is to see, when we refer back to our schemas, that Φ and Ψ can be complex. Thus, if we add to our key the following predicates:Fx: x is female
Gx: x is male
Tx: x is from Texas
Sx: x is a computer scientist
Lx: x is a mammal
Then, we can see that the following are translations of the eight English sentences, and they utilize the eight forms.∀x((Fx^Hx) ^ Tx)
∃x((Gx^Hx)^Tx)
∃x ¬((Fx^Hx)^(Sx^Tx))
¬∃x((Gx^Sx)^Tx)
∀x((Gx^Hx) → (Mx^Lx))
∃x((Fx^Hx) ^ (Sx^Tx))
∃x((Fx^Hx) ^ ¬(Sx^Tx))
¬∃x((Gx^Hx)^(Sx^Tx))
Another important issue to be aware of when translating expressions with quantifiers is that “only” plays a special role in some English expressions. Consider the following sentences.All sharks are fish.
Only sharks are fish.
The first of these is true; the second is false. We will start a new logical language and key. Let Fx mean that x is a fish, and Sx mean that x is a shark. We know how to translate the first sentence.∀x(Sx → Fx)
However, how shall we translate “Only sharks are fish”? This sentence tells us that the only things that are fish are the sharks. But then, all fish are sharks. That is, the translation is:∀x(Fx → Sx)
It would also be possible to combine these claims:All and only sharks are fish.
Which should be translated:∀x(Sx ↔ Fx)
This indicates two additional schemas for translation that may be useful. First, sentences of the form “Only Φ are Ψ” should be translated:∀α(Ψ(α) → Φ(α))
Second, sentences of the form “all and only Φ are Ψ” should be translated in the following way:∀α(Φ(α) ↔ Ψ(α))
All men are mortal.
Socrates is a man.
_____
Socrates is mortal.
We now have the tools to represent this argument.∀x(Hx→Mx)
Ha
_____
Ma
But, how can we show that this argument is valid? The important insight here concerns the universal quantifier. We understand the first sentence as meaning, for any object in my domain of discourse, if that object is human, then that object is mortal. That means we could remove the quantifier, put any name in our language into the free x slots in the resulting formula, and we would have a true sentence: (Ha→Ma) and (Hb→Mb) and (Hc→Mc) and (Hd→Md) and so on would all be true. We need only make this semantic concept into a rule. We will call this, “universal instantiation”. To remember this rule, just remember that it is taking us from a general and universal claim, to a specific instance. That’s what we mean by “instantiation”. We write the rule, using our metalanguage, in the following way. Let α be any variable, and let β be any symbolic term._____
Φ(β)
All men are mortal.
Socrates is a man.
_____
Something is mortal.
This looks to be an obviously valid argument, a slight variation on Aristotle’s original syllogism. Consider: if the original argument, with the same two premises, was valid, then the conclusion that Socrates is mortal must be true if the premises are true. But, if it must be true that Socrates is mortal, then it must be true that something is mortal. Namely, at least Socrates is mortal (recall that we interpret the existential quantifier to mean at least one). We can capture this reasoning with a rule. If a particular object has a property, then, something has that property. Written in our meta-language, where β is some symbolic term and α is a variable:Φ(β)
_____
∃αΦ(α)
This rule is called “existential generalization”. It takes an instance and then generalizes to a general claim. We can now show that the variation on Aristotle’s argument is valid. \[ \fitchprf{\pline[1.]{ \lall \textit{x}(H\textit{x} \lif M\textit{x})} [premise]\\ \pline[2.]{H\textit{a}} [premise] } { \pline[3.]{(H\textit{a} \lif M\textit{a})}[universal instantiation, 1]\\ \pline[4.]{M\textit{a}}[modus ponens, 3, 2]\\ \pline[5.]{\lis \textit{x}M\textit{x}}[existential generalization, 4] } \]All men are mortal.
Something is a man.
_____
Something is mortal.
This, too, looks like it must be a valid argument. If the first premise is true, then any human being you could find would be mortal. And, the second premise tells us that something is a human being. So, this something must be mortal. But, this argument confronts us with a special problem. The argument does not tell us which thing is a human being. This might seem trivial, but it really is only trivial in our example (because you know that there are many human beings). In mathematics, for example, there are many very surprising and important proofs that some number with some strange property exists, but no one has been able to show specifically which number. So, it can happen that we know that there is something with a property, but, not know what thing. Logicians have a solution to this problem. We will introduce a special kind of name, which refers to something, but we know not what. Call this an “indefinite name”. We will use p, q, r… as these special names (we know these are not atomic sentences because they are lowercase). Then, where χ is some indefinite name and α is a variable, our rule is:∃αΦ(α)
_____
Φ(χ)
where χ is an indefinite name that does not appear above in an open proof
This rule is called “existential instantiation”. By “open proof” we mean a subproof that is not yet complete. The last clause is important. It requires us to introduce indefinite names that are new. If an indefinite name is already being used in your proof, then you must use a new indefinite name if you do existential instantiation. This rule is a little bit stronger than is required in all cases, but it is by far the easiest way to avoid a kind of mistake that would produce invalid arguments. To see why this is so, let us drop the clause for the sake of an example. In this example, we will prove that the Pope is the President of the United States. We need only the following key.Hx: x is the President of the United States.
Jx: x is the Pope.
Here are two very plausible premises, which I believe that you will grant: there is a President of the United States, and there is a Pope. So, here is our proof: \[ \fitchprf{\pline[1.]{ \lis \textit{x}H\textit{x}} [premise]\\ \pline[2.]{\lis \textit{x}J\textit{x}} [premise] } { \pline[3.]{H\textit{p}}[existential instantiation, 1]\\ \pline[4.]{J\textit{p}}[existential instantiation, 2]\\ \pline[5.]{(H\textit{p} \land J\textit{p})}[adjunction, 3, 4]\\ \pline[6.]{\lis \textit{x}(H\textit{x} \land J\textit{x})}[existential generalization, 5] } \] Thus, we have just proved that there is a President of the United States who is Pope. But that’s false. We got a false conclusion from true premises—that is, we constructed an invalid argument. What went wrong? We ignored the clause on our existential instantiation rule that requires that the indefinite name used when we apply the existential instantiation rule cannot already be in use in the proof. In line 4, we used the indefinite name “p” when it was already in use in line 3. Instead, if we had followed the rule, we would have a very different proof: \[ \fitchprf{\pline[1.]{ \lis \textit{x}H\textit{x}} [premise]\\ \pline[2.]{\lis \textit{x}J\textit{x}} [premise] } { \pline[3.]{H\textit{p}}[existential instantiation, 1]\\ \pline[4.]{J\textit{q}}[existential instantiation, 2]\\ \pline[5.]{(H\textit{p} \land J\textit{q})}[adjunction, 3, 4]\\ } \] Because we cannot assume that the two unknowns are the same thing, we give them each a temporary name that is different. Since existential generalization replaces only one symbolic term, from line five you can only generalize to ∃x(Hx ^ Jq) or to ∃x(Hp ^ Jx)—or, if we performed existential generalization twice, to something like ∃x∃y(Hx ^ Jy). Each of these three sentences would be true if the Pope and the President were different things, which in fact they are. We can now prove that the variation on Aristotle’s argument, given above, is valid. \[ \fitchprf{\pline[1.]{ \lall \textit{x} (H\textit{x} \lif M\textit{x})} [premise]\\ \pline[2.]{\lis \textit{x}H\textit{x}} [premise] } { \pline[3.]{H\textit{p}}[existential instantiation, 2]\\ \pline[4.]{(H\textit{p} \lif M\textit{p})}[universal instantiation, 1]\\ \pline[5.]{M\textit{p}}[modus ponens, 4, 3]\\ \pline[6.]{\lis \textit{x}M\textit{x}}[existential generalization, 5] } \] A few features of this proof are noteworthy. We did existential instantiation first, in order to obey the rule that our temporary name is new: “p” does not appear in any line in the proof before line 3. But, then, we are permitted to do universal instantiation to “p”, as we did on line 4. A universal claim is true of every object in our domain of discourse, including the I-know-not-what. We can consider an example that uses all three of these rules for quantifiers. Consider the following argument.All whales are mammals. Some whales are carnivorous. All carnivorous organisms eat other animals. Therefore, some mammals eat other animals.
We could use the following key.Fx: x is a whale.
Gx: x is a mammal.
Hx: x is carnivorous.
Ix: x eats other animals.
Which would give us:∀x(Fx→Gx)
∃x(Fx^Hx)
∀x(Hx→Ix)
_____
∃x(Gx^Ix)
Here is one proof that the argument is valid. \[ \fitchprf{\pline[1.]{ \lall \textit{x} (F\textit{x} \lif G\textit{x})} [premise]\\ \pline[2.]{\lis \textit{x}(F\textit{x} \land H\textit{x})} [premise]\\ \pline[3.]{\lall \textit{x}(H\textit{x} \lif I\textit{x})}[premise] } { \pline[4.]{(F\textit{p} \land H\textit{p})}[existential instantiation, 2]\\ \pline[5.]{F\textit{p}}[simplification, 4]\\ \pline[6.]{(F\textit{p} \lif G\textit{p})}[universal instantiation, 1]\\ \pline[7.]{G\textit{p}}[modus ponens, 6, 5]\\ \pline[8.]{H\textit{p}}[simplification, 4]\\ \pline[9.]{(H\textit{p} \lif I\textit{p})}[universal instantiation, 3]\\ \pline[10.]{I\textit{p}}[modus ponens, 9, 8]\\ \pline[11.]{(H\textit{p} \land I\textit{p})}[adjunction, 8, 10]\\ \pline[12.]{\lis \textit{x} (G\textit{x} \land I\textit{x})}[existential generalization, 11] } \]Anything with complex independently interrelated parts was designed. If something is designed, then there is an intelligent designer. All living organisms have complex independently interrelated parts. There are living organisms. Therefore, there is an intelligent designer.Symbolize this argument, and prove that it is valid. (The second sentence is perhaps best symbolized not using one of the eight forms, but rather using a conditional, where both the antecedent and the consequent are existential sentences.) Do you believe this argument is sound? Why do you think Darwin’s work was considered a significant challenge to the claim that the argument is sound?
Socrates: Tell me, boy, is not this a square of four feet that I have drawn? Boy: Yes. Socrates: And now I add another square equal to the former one? Boy: Yes. Socrates: And a third, which is equal to either of them? Boy: Yes. Socrates: Suppose that we fill up the vacant corner? Boy: Very good. Socrates: Here, then, there are four equal spaces? Boy: Yes.^{[12]}
So what Socrates has drawn at this point looks like:Suppose each square is a foot on a side. Socrates will now ask the boy how to make a square that is of eight square feet, or twice the size of their initial 2x2 square. Socrates has a goal and method in drawing the square four times the size of the original.
Socrates: And how many times larger is this space than the other? Boy: Four times. Socrates: But it ought to have been twice only, as you will remember. Boy: True. Socrates: And does not this line, reaching from corner to corner, bisect each of these spaces?
By “spaces”, Socrates means each of the 2x2 squares. Socrates has now drawn the following:Boy: Yes. Socrates: And are there not here four equal lines that contain this new square? Boy: There are. Socrates: Look and see how much this new square is. Boy: I do not understand.
After some discussion, Socrates gets the boy to see that where the new line cuts a small square, it cuts it in half. So, adding the whole small squares inside this new square, and adding the half small squares inside this new square, the boy is able to answer.Socrates: The new square is of how many feet? Boy: Of eight feet. Socrates: And from what line do you get this new square? Boy: From this. [The boy presumably points at the dark line in our diagram.] Socrates: That is, from the line which extends from corner to corner of the each of the spaces of four feet? Boy: Yes. Socrates: And that is the line that the educated call the “diagonal”. And if this is the proper name, then you, Meno’s slave, are prepared to affirm that the double space is the square of the diagonal? Boy: Certainly, Socrates.
For the original square that was 2x2 feet, by drawing a diagonal of the square we were able to draw one side of a square that is twice the area. Socrates has demonstrated how to make a square twice the area of any given square: make the new square’s sides each as large as the diagonal of the given square. It is curious that merely by questioning the slave (who would have been a child of a Greek family defeated in battle, and would have been deprived of any education), Socrates is able to get him to complete a proof. Plato takes this as a demonstration of a strange metaphysical doctrine that each of us once knew everything and have forgotten it, and now we just need to be helped to remember the truth. But we should note a different and interesting fact. Neither Socrates nor the slave boy ever doubts that Socrates’s demonstration is true of all squares. That is, while Socrates draws squares in the dirt, the slave boy never says, “Well, Socrates, you’ve proved that to make a square twice as big as this square that you have drawn, I need to take the diagonal of this square as a side of my new square. But what about a square that’s much smaller or larger than the one you drew here?” That is in fact a very perplexing question. Why is Socrates’s demonstration good for all, for any, squares?All numbers evenly divisible by eight are evenly divisible by four.
All numbers evenly divisible by four are evenly divisible by two.
_____
All numbers evenly divisible by eight are evenly divisible by two.
Let us assume an implicit translation key, and then we can say that the following is a translation of this argument.∀x(Fx→Gx)
∀x(Gx→Hx)
_____
∀x(Fx→Hx)
This looks like a valid argument. Indeed, it may seem obvious that it is valid. But to prove it, we need some way to be able to prove a universal statement. But how could we do such a thing? There are infinitely many numbers, so surely we cannot check them all. How do we prove that something is true of all numbers, without taking an infinite amount of time and creating an infinitely long proof? The odds are that you already know how to do this, although you have never reflected on your ability. You most likely saw a proof of a universal claim far back in grade school, and without reflection concluded it was good and proper. For example, when you were first taught that the sum of the interior angles of a triangle is equivalent to two right angles, you might have seen a proof that used a single triangle as an illustration. It might have gone something like this: assume lines AB and CD are parallel, and that two other line segments EF and EG cross those parallel lines, and meet on AB at E. Assume also that the alternate angles for any line crossing parallel lines are equal. Assume that a line is equivalent to two right angles, or 180 degrees. Then, in the following picture, b’=b, c’=c, and b’+c’+a=180 degrees. Thus, a+b+c=180 degrees. Most of us think about such a proof, see the reasoning, and agree with it. But if we reflect for a moment, we should see that it is quite mysterious why such a proof works. That’s because, it aims to show us that the sum of the interior angles of any triangle is the same as two right angles. But there are infinitely many triangles (in fact, logicians have proved that there are more triangles than there are natural numbers!). So how can it be that this argument proves something about all of the triangles? Furthermore, in the diagram above, there are infinitely many different sets of two parallel lines we could have used. And so on. This also touches on the case that we saw in the Meno. Socrates proves that the area of a square A twice as big as square B does not simply have sides twice as long as the sides of B; rather, each side of A must be the length of the diagonal of B. But he and the boy drew just one square in the dirt. And it won’t even be properly square. How can they conclude something about every square based on their reasoning and a crude drawing? In all such cases, there is an important feature of the relevant proof. Squares come in many sizes, triangles come in many sizes and shapes. But what interests us in such proofs is all and only the properties that all triangles have, or all and only properties that all squares have. We refer to a triangle, or a square, that is abstract in a strange way: we draw inferences about, and only refer to, its properties that are shared with all the things of its kind. We are really considering a special, generalized instance. We can call this special instance the “arbitrary instance”. If we prove something is true of the arbitrary triangle, then we conclude it is true of all triangles. If we prove something is true of the arbitrary square, then we conclude it is true of all squares. If we prove something is true of an arbitrary natural number, then we conclude it is true of all natural numbers. And so on.Where α′ does not appear in any open proof above the beginning of the universal derivation.
Remember that an open proof is a subproof that is not completed. We will call any symbolic term of this form (x′, y′, z′…) an “arbitrary term”, and it is often convenient to describe it as referring to the arbitrary object or arbitrary instance. But there is not any one object in our domain of discourse that such a term refers to. Rather, it stands in for an abstraction: what all the things in the domain of discourse have in common. The semantics of an arbitrary instance is perhaps less mysterious when we consider the actual syntactic constraints on a universal derivation. One should not be able to say anything about an arbitrary instance α′ unless one has done universal instantiation of a universal claim. No other sentence should allow claims about α′. For example, you cannot perform existential instantiation to an arbitrary instance, since we required that existential instantiation be done to special indefinite names that have not appeared yet in the proof. But if we can only makes claims about α′ using universal instantiation, then we will be asserting something about α′ that we could have asserted about anything in our domain of discourse. Seen in this way, from the perspective of the syntax of our proof, the universal derivation hopefully seems very intuitive. This schematic proof has a line where we indicate that we are going to use α′ as the arbitrary object, by putting α′ in a box. This is not necessary, and is not part of our proof. Rather, like the explanations we write on the side, it is there to help someone understand our proof. It says, this is the beginning of a universal derivation, and α′ stands for the arbitrary object. Since this is not actually a line in the proof, we need not number it. We can now prove our example above is valid. \[ \fitchprf{\pline[1.]{ \lall \textit{x} (F\textit{x} \lif G\textit{x})} [premise]\\ \pline[2.]{ \lall \textit{x} (G\textit{x} \lif H\textit{x})} [premise]\\ } { \boxedsubproof []{\textit{x}'}{}{ \subproof{\pline[3.]{F\textit{x}'}[assumption for conditional derivation]}{ \pline[4.]{(F\textit{x}' \lif G\textit{x}')}[universal instantiation, 1]\\ \pline[5.]{G\textit{x}'}[modus ponens, 4, 3]\\ \pline[6.]{(G\textit{x}' \lif H\textit{x}')}[universal instantiation, 2]\\ \pline[7.]{H\textit{x}'}[modus ponens, 6, 5] } \pline[8.]{(F\textit{x}' \lif H\textit{x}')}[conditional derivation, 3-7] } \pline[9.]{\lall \textit{x}(F\textit{x} \lif H\textit{x})}[universal derivation, 3-8] } \] Remember that our specification of the proof method has a special condition, that α′ must not appear earlier in an open proof (a proof that is still being completed). This helps us avoid confusing two or more arbitrary instances. Here, there is no x′ appearing above our universal derivation in an open proof (in fact, there is no other arbitrary instance appearing in the proof above x′), so we have followed the rule.∀x(Fx v ¬Fx)
This sentence must be true. But we cannot show this with a truth table. Instead, we need the concept of a model (introduced briefly in section 17.6) to describe this property precisely. But even with our intuitive semantics, we can see that this sentence must be true. For, we require (in our restriction on predicates) that everything in our domain of discourse either is, or is not, an F. We call a sentence of the first order logic that must be true, “logically true”. Just as it was a virtue of the propositional logic that all the theorems are tautologies, and all the tautologies are theorems; it is a virtue of our first order logic that all the theorems are logically true, and all the logically true sentences are theorems. Proving this is beyond the scope of this book, but is something done in most advanced logic courses and texts. Here is a proof that ∀x(Fx v ¬Fx). \[ \fitchprf{ } { \boxedsubproof []{\textit{x}'}{}{ \subproof{\pline[1.]{\lnot (F\textit{x}' \lor \lnot F\textit{x}')}[assumption for indirect derivation]}{ \subproof{\pline[2.]{\lnot F\textit{x}'}[assumption for indirect derivation]}{ \pline[3.]{(F\textit{x}' \lor \lnot F\textit{x}')} [addition, 2]\\ \pline[4.]{\lnot (F\textit{x}' \lor \lnot F\textit{x}')}[repeat, 1]\\ } \pline[5.]{F\textit{x}'}[indirect derivation, 2-4]\\ \pline[6.]{(F\textit{x}' \lor \lnot F\textit{x}')}[addition, 5]\\ \pline[7.]{\lnot (F\textit{x}' \lor \lnot F\textit{x}')}[repeat, 1]\\ } \pline[8.]{(F\textit{x}' \lor \lnot F\textit{x}')}[indirect derivation, 1-7] } \pline[9.]{\lall \textit{x}(F\textit{x} \lor \lnot F\textit{x})}[universal derivation, 1-8] } \] Let us consider another example of a logically true sentence that we can prove, and thus, practice universal derivation. The following sentence is logically true.((∀x (Fx → Gx) ^ ∀x (Fx → Hx))→ ∀x (Fx → (Gx ^Hx))
Here is a proof. The formula is a conditional, so we will use conditional derivation. However, the consequence is a universal sentence, so we will need a universal derivation as a subproof. \[ \fitchprf{}{ \subproof{\pline[1.]{ (\lall \textit{x} (F\textit{x} \lif G\textit{x}) \land \lall \textit{x} (F\textit{x} \lif H\textit{x}))}[assumption for conditional derivation]}{ \boxedsubproof []{\textit{x}'}{}{ \subproof{\pline[2.]{F\textit{x}'}[assumption for conditional derivation]}{ \pline[3.]{\lall \textit{x} (F\textit{x} \lif G\textit{x}) }[simplification, 1]\\ \pline[4.]{(F\textit{x}' \lif G\textit{x}')}[universal instantiation, 3]\\ \pline[5.]{G\textit{x}'}[modus ponens, 4, 2]\\ \pline[6.]{\lall \textit{x} (F\textit{x} \lif H\textit{x}) }[simplification, 1]\\ \pline[7.]{(F\textit{x}' \lif H\textit{x}')}[universal instantiation, 6]\\ \pline[8.]{H\textit{x}'}[modus ponens, 7, 2]\\ \pline[9.]{(G\textit{x}' \land H\textit{x}')}[adjunction, 5, 8]\\ } \pline[10.]{(F\textit{x}' \lif (G\textit{x}' \land H\textit{x}')) }[conditional derivation, 2-9]\\ } \pline[11.]{\lall \textit{x}(F\textit{x} \lif (G\textit{x} \land H\textit{x}))}[universal derivation, 2-10]\\ } \pline[12.]{\brokenform{((\lall \textit{x} (F\textit{x} \lif G\textit{x}) \land \lall \textit{x} (F\textit{x} \lif H\textit{x})) \lif}{\lall \textit{x}(F\textit{x} \lif (G\textit{x} \land H\textit{x}))}} [conditional derivation, 1-11] } \] Just as there were useful theorems of the propositional logic, there are many useful theorems of the first order logic. Two very useful theorems concern the relation between existential and universal claims.(∃xFx ↔ ¬∀x¬Fx)
(∀xFx ↔ ¬∃x¬Fx)
Something is F just in case not everything is not F. And, everything is F if and only if not even one thing is not F. We can prove the second of these, and leave the first as an exercise. \[ \fitchprf{}{ \subproof{\pline[1.]{\lall \textit{x} F\textit{x}}[assumption for conditional derivation]}{ \subproof{\pline[2.]{\lis \textit{x} \lnot F\textit{x}}[assumption for indirect derivation]}{ \pline[3.]{\lnot F\textit{p}}[existential instantiation, 2]\\ \pline[4.]{F\textit{p}}[universal instantiation, 1] } \pline[5.]{\lnot \lis \textit{x} \lnot F\textit{x}}[indirect derivation, 2-4]\\ } \pline[6.]{(\lall \textit{x} F\textit{x} \lif \lnot \lis \textit{x} \lnot F\textit{x})}[conditional derivation 1-5]\\ \subproof{\pline[7.]{\lnot \lis \textit{x} \lnot F\textit{x}}[assumption for conditional derivation]}{ \boxedsubproof []{\textit{x'}}{}{ \subproof{\pline[8.]{\lnot F\textit{x'}}[assumption for indirect derivation]}{ \pline[9.]{\lis \textit{x} \lnot F\textit{x}}[existential generalization, 8]\\ \pline[10.]{\lnot \lis \textit{x} \lnot F\textit{x}}[repeat, 7] } \pline[11.]{F\textit{x'}}[indirect derivation, 8-10] } \pline[12.]{\lall \textit{x}F\textit{x}}[universal derivation, 8-11] } \pline[13.]{(\lnot \lis \textit{x} \lnot F\textit{x} \lif \lall x F\textit{x} )}[conditional derivation 7-12]\\ \pline[14.]{(\lall \textit{x} F\textit{x} \liff \lnot \lis \textit{x} \lnot F\textit{x}))}[bicondition, 6, 13] } \]∀x(Hx→Gx)
¬Hd
_____
¬Gd
This is an invalid argument. It is possible that the conclusion is false but the premises are true. Because we cannot use truth tables to describe the semantics of quantifiers, we have kept the semantics of the quantifiers intuitive. A complete semantics for first order logic is called a “model”, and requires some set theory. This presents a difficulty: we cannot demonstrate that an argument using quantifiers is invalid without a semantics. Fortunately, there is a heuristic method that we can use that does not require developing a full model. We will develop an intuitive and partial model. The idea is that we will come up with an interpretation of the argument, where we ascribe a meaning to each predicate, and a referent for each term, and where this interpretation makes the premises obviously true and the conclusion obviously false. This is not a perfect method, since it will depend upon our understanding of our interpretation, and because it requires us to demonstrate some creativity. But this method does illustrate important features of the semantics of the first order logic, and used carefully it can help us see why a particular argument is invalid. It is often best to create an interpretation using numbers, since there is less vagueness of the meaning of the predicates. So suppose our domain of discourse is the natural numbers. Then, we need to find an interpretation of the predicates that makes the first two lines true and the conclusion false. Here is one:Hx: x is evenly divisible by 2
Gx: x is evenly divisible by 1
d: 3
The argument would then have as premises: All numbers evenly divisible by 2 are evenly divisible by 1; and, 3 is not evenly divisible by 2. These are both true. But the conclusion would be: 3 is not evenly divisible by 1. This is false. This illustrates that the argument form is invalid. Let us consider another example. Here is an invalid argument:∀x(Fx→Gx)
Fa
_____
Gb
We can illustrate that it is invalid by finding an interpretation that shows the premises true and the conclusion false. Our domain of discourse will be the natural numbers. We interpret the predicates and names in the following way:Fx: x is greater than 10
Gx: x is greater than 5
a: 15
b: 2
Given this interpretation, the argument translates to: Any number greater than 10 is greater than 5; 15 is greater than 10; therefore, 2 is greater than 5. The conclusion is obviously false, whereas the premises are obviously true. In this exercise, it may seem strange that we would just make up meanings for our predicates and names. However, as long as our interpretations of the predicates and names follow our rules, our interpretation will be acceptable. Recall the rules for predicates are that they have an arity, and that each predicate of arity n is true or false (never both, never neither) of each n things in the domain of discourse. The rule for names is that they refer to only one object. This illustrates an important point. Consider a valid argument, and try to come up with some interpretation that makes it invalid. You will find that you cannot do it, if you respect the constraints on predicates and names. Make sure that you understand this. It will clarify much about the generality of the first order logic. Take a valid argument like:∀x(Fx→Gx)
Fa
_____
Ga
Come up with various interpretations for a and for F and G. You will find that you cannot make an invalid argument. In summary, an informal model used to illustrate invalidity must have three things:Every event is caused by prior events by way of natural physical laws. Any event caused by prior events by way of natural physical laws could not have happened otherwise. But, if all events could not have happened otherwise, then there is no freely willed event. We conclude, therefore, that there are no freely willed events.
Symbolize this argument and prove it is valid. You might consider using the following predicates:
Fx: x is an event.
Gx: x is caused by prior events by way of natural physical laws.
Hx: x could have happened otherwise.
Ix: x is a freely willed event.
(Hint: this argument will require universal derivation. The conclusion can be had using modus ponens, if you can prove: all events could not have happened otherwise.) Do you believe that this argument is sound?
∀xΦ(xx)
Examples of reflexive relations in English include “…is as old as…”. Each person is as old as herself. A relation that is not reflexive is, “…is older than …”. No person is older than herself. For any relation Φ, the relation is symmetric if and only if:∀x∀y(Φ(x y) → Φ(y x))
Examples of symmetric relations in English include “…is married to…”. In our legal system at least, if Pat is married to Chris, then Chris is married to Pat. Finally, call a relation “transitive” if and only if∀x∀y∀z((Φ(x y)^Φ(y z)) → Φ(x z))
Examples of transitive relations in English include “…is older than…”. If Tom is older than Steve, and Steve is older than Pat, then Tom is older than Pat. Return now to our example of blood types. We introduce the following translation key:Gxy: x can give blood to y without causing an immune reaction
It is the case that∀xGxx
And so we know that the relation G is reflexive. A person with type O blood can give blood to himself, a person with type AB blood can give blood to herself, and so on. (People do this when they store blood before a surgery.) Is the relation symmetric? Consider whether the following is true:∀x∀y(Gxy → Gyx)
A moment’s reflection reveals this isn’t true. A person of type O can give blood to a person of type AB, but the person with type AB blood cannot give blood to the person with type O, without potentially causing a reaction. So G is not symmetric. Finally, to determine if G is transitive, consider whether the following is true.∀x∀y∀z((Gxy ^ Gyz) → Gxz)
A person with type O blood can give blood to a person with type A blood, and that person can give blood to someone of type AB. Does it follow that the person with type O can give blood to the person with AB? It does. And similarly this is so for all other possible cases. G is a transitive relation.the mother of…
the father of…
Think of how you could use something like this in our logical language. You could say, “The father of Tom is Canadian”. But now, who is Canadian? Not Tom. Tom’s father is. In this sentence, “the father of…” acts as a function. It relates a person to another person. And, in our predicate, “the father of Tom” acts like a name, in that it refers to one thing. Functions have an arity. Addition is an arity two function; it takes two objects in order to form a symbolic term. But in order to be a function, the resulting symbolic term must always refer to only one object. (This rule gets broken a lot in mathematics, where some relations are called “functions” but can have more than one output. This arises because in circumscribed domains of discourse, those operations are functions, and then they get applied in new domains but are still called “functions”. Thus, the square root function is a function when we are studying the natural numbers, but once we introduce negative numbers it no longer is a function. But mathematicians call it a “function” because it is in limited domains a function, and because the diverse output is predictable in various ways. Logic is the only field where one earns the right to call mathematicians sloppy.) Functions are surprisingly useful. Computers, for example, can be understood as function machines, and programming can be usefully described as the writing of functions for the computer. Much of mathematics is concerned with studying functions, and they often prove useful for studying other things in mathematics that are not themselves functions. We can add functions to our logical language. We will let f, g, h, … be functions. Each function, as noted, has an arity. A function of arity n combined with n symbolic terms is a symbolic term. Thus, to make a key to translate the sentence above, we can have:Kx: x is Canadian.
fx: the father of x.
a: Tom
b: Steve
(Obviously, we are assuming that each person has only one father. Arguably that is only one use of the word “father,” but our goal here is to create a familiar example, not to take sides in any issue about family relations. So we will allow the assumption just to make our point.) Using that key, the following would mean “Tom is Canadian”:Ka
And the following would mean “The father of Tom is Canadian”:Kfa
We can also say something like, “Tom’s paternal grandfather is Canadian”:Kffa
Or even, “Tom’s paternal great-grandfather is Canadian”:Kfffa
That works because the father of the father of Tom is the paternal grandfather of Tom, which then is a symbolic term, and we can apply the function to it. Recall that, when a rule can be applied repeatedly to its product, we call this “recursion”.Malcolm X is a great orator.
Malcolm X is Malcolm Little.
Malcolm X is.
The last example is not very common in English usage, but it is grammatical. Here we see the “is” of existence. The sentence asserts that Malcolm X exists. In the first sentence, we would treat “…is a great orator” as an arity one predicate. The “is” is part of the predicate, and in our logic, cannot be distinguished from the predicate. But the second case uses the “is” of identity. It asserts that Malcolm X and Malcolm Little are the same thing. Because it is so common to use the symbol “=” for identity, we will use it, also. Strictly speaking, our syntax requires prefix notation. But for any language we create, we could introduce an arity two predicateIxy: x is identical to y
And then we could say, whenever we write “α=β” we really mean “Iαβ”. Note identity describes a relation that is reflexive, symmetric, and transitive. Everything is identical to itself. If a=b then b=a. And if a=b and b=c then a=c. One special feature of identity is that we know that if two things are identical, then anything true of one is true of the other. In fact, the philosopher Leibniz defined identity with a principle that we call Leibniz’s Law: a and b are identical if and only if they have all and only the same properties. Our logic must take identity as a primitive, however, because we have no way in our logic of saying “all properties” (this is what “first order” in “first order logic” means: our quantifiers have only particular objects in their domain). Leibniz’s insight, however, suggests an inference rule. If α and β are symbolic terms, and Φ(α) means that Φ is a formula in which α appears, we can sayΦ(α)
α=β
_____
Φ(β)
Where we replace one or more occurrences of α in Φ with β. We can call this rule, “indiscernibility of identicals”. We sometimes also call this, “substitution of identicals”. This is an interesting kind of rule. Some logicians would call this a “non-logical rule”. The reason is, we know it is proper because we know the meaning of “=”. Unlike, for example, modus ponens, which identifies a logical relation between two kinds of sentences, this rule relies not on the semantics of a connective, but rather on the meaning of a predicate. This notion of “non-logical” is a term of art, but it does seem profound. Adding such rules to our language can strengthen it considerably. Adding identity to our language will allow us to translate some expressions that we would be unable to translate otherwise. Consider our example above, for functions. How would we translate the expression, “Steve is the father of Tom”? We could add to our language a predicate, “… is the father of …”. However, it is interesting that in this expression (“Steve is the father of Tom”), the “is” is identity. A better translation (using the key above) would be:b=fa
We can also say things like, “The father of Steve is the paternal grandfather of Tom”:fb=ffa
Consider now a sentence like this: someone is the father of Tom. Again, if we had a predicate for “… is the father of …”, we could just say, there is something that is the father of Tom. But given that we have a function for “the father of x” we could also translate this phrase as:∃x x=fa
We can see from these examples that there are interesting parallels between relations (including functions) and predicates. To represent some kind of function, we can introduce a function into our language, which acts as a special kind of symbolic term, but it is also possible to identify a predicate that is true of all and only those things that the function relates. Nonetheless, we must be careful to distinguish between predicates, which when combined with the appropriate number of names form a sentence; and functions, which when combined with the appropriate number of other terms are symbolic terms. In our logic, treating predicates like functions (that is, taking them as symbolic terms for other predicates) will create nonsense. Finally, we had as an example above, the sentence “Malcolm X is”. This is equivalent to “Malcolm X exists”. Let c mean Malcolm X. Identity allows us to express this sentence. We say that there is at least one thing that is Malcolm X:∃x x=c
Every number is greater than or equal to some number.
Some number is greater than or equal to every number.
Every number is less than or equal to some number.
Some number is less than or equal to every number.
Depending upon our domain of discourse, some of these sentences are true, and some of them are false. Can we represent them in our logical language? Suppose that we introduce an arity two predicate for “greater than or equal to”:Gxy: x is greater than or equal to y
We can follow tradition, and use “≥”. Thus, when we write “α≥β” we understand that this is “Gαβ”. Let us also assume that our domain of discourse is the natural numbers. That is, we are talking only about 1, 2, 3, 4…. We can see now how to take a first step toward expressing these sentences. If we write:x≥y
We have said that x is greater than or equal to y. We have used quantifiers to say “all”, and we can write∀x x≥y
Which says that every number is greater than or equal to y. But how will we capture the sentences above? We will need to use multiple quantifiers. To say that “every number is greater than some number”, we will write∀x∃y x≥y
This raises important questions about how to interpret multiple quantifiers. Using multiple quantifiers expands the power of our language enormously. However, we must be very careful to understand their meaning. Consider the following two sentences, which will use our key above.∀x∃y x≥y
∃y∀x x≥y
Do they have the same meaning? As we understand the semantics of quantifiers, we will say that they do not. The basic idea is that we read the quantifiers from left to right. Thus, the first sentence above should be translated to English as “Every number is greater than or equal to some number”. The second sentence should be translated, “Some number is less than or equal to every number”. They have very different meanings. Depending upon our domain of discourse, they could have different truth values. For example, if we use the natural numbers as our domain of discourse, the first sentence is true and the second sentence is true. However, if we used the integers for our domain of discourse, so that we included negative numbers, then the first sentence is true but the second sentence is false. It may be helpful to think of multiple quantifiers in the following way. If we were to instantiate the quantifiers, then, we would work from left to right. Thus, the first sentence says something like, pick any number in our domain of discourse, then there will be at least one number in our domain of discourse that is less than or equal to that first number that you already picked. The second sentence says something quite different: there is at least one number in our domain of discourse such that, if you pick that number, then any number in our domain of discourse is greater than or equal to it. With this in mind, we are now able to translate the four phrases above. We include the English with the translation to avoid any confusion.Every number is greater than or equal to some number.
∀x∃y x≥y
Some number is greater than or equal to every number.
∃x∀y x≥y
Every number is less than or equal to some number.
∀x∃y y≥x
Some number is less than or equal to every number.
∃x∀y y≥x
As we noted above, the truth value of these sentences can change if we change our domain of discourse. If our domain of discourse is the natural numbers, then only the second sentence is false; this is because for the natural numbers there is a least number (1), but there is no greatest number. But if our domain of discourse is the integers, then the second and fourth sentences are false. This is because with the negative numbers, there is no least number: you can always find a lesser negative number. Hopefully it becomes very clear now why we need the possibility of a number of variables for our quantifiers. We could not write the expressions above if we did not have discernibly distinct variables to allow different quantifiers to bind different locations in the predicate.It is not the case that Sam is bald.
Now suppose that anyone who is not bald has hair. Then, we could reason that:Sam has hair.
That seems correct, if we grant the premise that all those who are not bald have hair. But now consider the following sentence.It is not the case that the present King of France is bald.
By the same reasoning, this would seem to entail that:The present King of France has hair.
But that’s not right. There is no present King of France! It gets worse. Let us assert thatThe present King of France does not exist.
This seems to pick out a thing, the present King of France, and ascribe to it a property, not existing. After all, in our logical language, each name must refer to something. But if we can pick out that thing in order to describe it as not existing, does it not exist? That is, is there not a thing to which the term refers? Some philosophers indeed argued that every term, even in a natural language, must have a thing that it refers to. The philosopher Alexius Meinong (1853-1920), for example, proposed that every name has a referent that has being, but that existence was reserved for particular actual objects. This is very strange, when you consider it: it means that “the round square” refers to something, a something that has being, but that lacks existence. Russell thought this a terrible solution, and wanted to find another. Russell uses a different example to illustrate a third problem. Suppose thatGeorge IV wished to know whether Scott was the author of Waverley.
Here Russell raises a problem related to one that the mathematician Gottlob Frege had already observed. Namely, if Scott=the author of Waverley, then one might suppose that we could substitute “Scott” where we see “the author of Waverley” and get a sentence that has the same truth value. That is, we introduced above a rule—indiscernibility of identicals—that, if applied here, should allow us to replace “the author of Waverley” with “Scott” if Scott=the author of Waverley. But that fails: it is not the case thatGeorge IV wished to know whether Scott was Scott.
George IV already knows that Scott is Scott. Russell put forward a brilliant solution to these puzzles. He developed an analysis of some English phrases into a logical form that is rather different than we might expect. For example, he argues the proper form to translate “It is not the case that the present King of France is bald” is something like this. Let “Gx” mean “x is the present king of France” and “Hx” mean “x is bald”, then this sentence is translated:∃x((Gx ^ Hx) ^ ∀y(Gy → x=y))
This says there is something—call it x for now—that is the present king of France, and that thing is bald, and if anything is the present king of France it is identical to x. This second clause is a way of saying that there is only one king of France, which is how Russell captures the meaning of “the” in “the present king of France”. This sentence is false, because there is no present king of France. But to deny that the present king of France is bald is to assert rather that∃x((Gx ^ ¬Hx) ^ ∀y(Gy → x=y))
This sentence is false also. It cannot be used to conclude that there is a present king of France who is hirsute. Similar quick work can be done with the puzzle about existence. “The present king of France does not exist” is equivalent to “It is not the case that the present king of France exists” and this we translate as:¬∃x(Gx ^ ∀y(Gy → x=y))
Note that there is no need in this formula for a name that refers to nothing. There is no name in this formula. Finally, when George IV wished to know whether Scott was the author of Waverley, we can let “a” stand for “Scott”, and “Wx” mean “x authored Waverley”, and now assert that what the king wanted to know was whether the following is true:∃x((Wx ^ ∀y(Wy → x=y)) ^ x=a)
In this, the part of the formula that captures the meaning of “the author of Waverley” requires no name, and so there is no issue of applying the indiscernibility of identicals rule. (Remember that the indiscernibility of identicals rule allows the replacement of a symbolic term with an identical symbolic term. In this formula, there is no symbolic term for “the author of Waverley”, and so even if Scott is the author of Waverley, the indiscernibility of identicals rule cannot be applied here.) Russell has done something very clever. He found a way to interpret a phrase like “the present king of France” as a complex logical formula; such a formula can be constructed so that it uses no names to capture the meaning of the phrase. It is an interesting question whether Russell’s analysis should be interpreted as describing, in some sense, what is really inside our minds when we use a phrase like “The present king of France.” That’s perhaps an issue for cognitive scientists to settle. Our interest is that Russell inspires a new and flexible way to use first order logic to understand possible interpretations of these kinds of utterances. Russell’s translations also suggest a surprising possibility: perhaps many names, or even all names, are actually phrases like these that are uniquely true of one and only one thing. That was of interest to philosophers who wanted to explain the nature of reference; it suggests that reference could be explained using the notion of a complex predicate expression being true of one thing. That is a radical suggestion, and one that Russell developed and defended. He proposed that the only names were the very basic primitive “this” and “that”. All other natural language names could then be analyzed into complex phrases like those above. This is an issue for the philosophy of language, and we will not consider it further here. Another benefit of Russell’s translation is that it illustrates how to count with the quantifier. This is of great interest to our logic. Any sentence of the form “there is only one thing that is Φ” can be translated:∃x(Φ(x)^∀y(Φ(y) → x=y))
Russell’s insight is that if only one thing is Φ, then anything that turns out to be Φ must be the same one thing. A little ingenuity shows that we can use his insight to say, there are exactly two things that are Φ. It might be helpful at first to separate out “there are at least two” and “there are at most two”. These are:∃x∃y ((Φ(x)^Φ(y)) ^ ¬x =y)
∀x∀y∀z (((Φ(x)^Φ(y))^Φ(z)) → ((x=y v x=z) v y=z))
The first sentence says, there exists a thing x and a thing y such that x has property Φ and y has property Φ and x and y are not the same thing. This asserts there are at least two things that have property Φ. The second sentence says for any x, y, z, if each has the property Φ, that at least one of them is the same as the other. This asserts that there are at most two things that have property Φ. Combine those with a conjunction, and you have the assertion at least two things are Φ, and at most two things are Φ. That is, there are exactly two things that are Φ.(∃x∃y ((Φ(x)^Φ(y)) ^ ¬x =y) ^ ∀x∀y∀z (((Φ(x)^Φ(y))^Φ(z)) → ((x=y v x=z) v y=z)))
That’s awkward, but it shows that we can express any particular quantity using our existing logical language. We will be able to say, for example, that there are exactly 17 things that are Φ. It is quite surprising to think that we do not need numbers to be able to express particular finite quantities, and that our logic is strong enough to do this.Φ | ¬Φ |
T | F |
F | T |
Φ | Ψ | (Φ → Ψ) |
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Φ | Ψ | (Φ ^ Ψ) |
T | T | T |
T | F | F |
F | T | F |
F | F | F |
Φ | Ψ | (Φ v Ψ) |
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Φ | Ψ | (Φ ↔ Ψ) |
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Modus ponens | Modus tollens | Double negation | Double negation |
(Φ → Ψ) Φ _____ Ψ | (Φ → Ψ) ¬Ψ _____ ¬Φ | Φ _____ ¬¬Φ | ¬¬Φ _____ Φ |
Addition | Addition | Modus tollendo ponens | Modus tollendo ponens |
Φ _____ (Φ v Ψ) | Ψ _____ (Φ v Ψ) | (Φ v Ψ) ¬Φ _____ Ψ | (Φ v Ψ) ¬Ψ _____ Φ |
Adjunction | Simplification | Simplification | Bicondition |
Φ Ψ _____ (Φ ^ Ψ) | (Φ ^ Ψ) _____ Φ | (Φ ^ Ψ) _____ Ψ | (Φ → Ψ) (Ψ → Φ) _____ (Φ ↔ Ψ) |
Equivalence | Equivalence | Equivalence | Equivalence |
(Φ ↔ Ψ) Φ _____ Ψ | (Φ ↔ Ψ) Ψ _____ Φ | (Φ ↔ Ψ) ¬Φ _____ ¬Ψ | (Φ ↔ Ψ)¬Ψ _____ ¬Φ |
Repeat | Universal instantiation | Existential generalization | Existential instantiation |
Φ _____ Φ | ∀αΦ(α) _____ Φ(β) where β is any symbolic term | Φ(β) _____ ∃αΦ(α) where β is any symbolic term | ∃αΦ(α) _____ Φ(χ) where χ is an indefinite name that does not appear above in any open proof |
Everything is Φ ∀xΦ(x) | Something is Φ ∃xΦ(x) |
Nothing is Φ ¬∃xΦ(x) | Something is not Φ ∃x¬Φ(x) |
All Φ are Ψ ∀x(Φ(x) → Ψ(x)) | Some Φ are Ψ ∃x(Φ(x) ^ Ψ(x)) |
No Φ are Ψ ¬∃x(Φ(x) ^ Ψ(x)) | Some Φ are not Ψ ∃x(Φ(x) ^ ¬Ψ(x)) |
Only Φ are Ψ ∀x(Ψ(x) → Φ(x)) | All and only Φ are Ψ ∀x(Φ(x) ↔ Ψ(x)) |
17.2 Axiomatic propositional logic
17.3 Mathematical induction
17.4 The deduction theorem for propositional logic
17.5 Set theory
17.6 Axiomatic first order logic
17.7 Modal logic
17.8 Peano arithmetic
(L1): (Φ → (Ψ → Φ))
(L2): ((Φ → (Ψ→χ)) → ((Φ → Ψ) → (Φ → χ)))
(L3): ((¬Φ→¬Ψ)→((¬Φ→Ψ)→Φ))
We suppose that we have some number of atomic sentences, P1, P2, P3 and so on (it is useful, at this point, to use a single letter, with subscripts, so we do not find ourselves running out of letters). We have one rule: modus ponens. We have one proof method: direct derivation. However, we have now a new principle in doing proofs: we can at any time assert any instance of an axiom. Thus, each line of our direct derivation will be either a premise, an instance of an axiom, or derived from earlier lines using modus ponens. Later, we will loosen these restrictions on direct derivations in two ways. First, we will allow ourselves to assert theorems, just as we have done in the natural deduction system. Second, we will allow ourselves to apply principles that we have proven and that are general. These are metatheorems: theorems proved about our logic. The semantics for this system are like those for the propositional logic: we assign to every atomic formula a truth value, and then the truth value of the sentences built using conditionals and negation are determined by the truth tables for those connectives. Amazingly, this system can do everything that our propositional logic can do. Furthermore, because it is so small, we can prove things about this logic much more easily. What about conjunction, disjunction, and the biconditional? We introduce these using definitions. Namely, we say, whenever we write “(Φ^Ψ)” we mean “¬(Φ→¬Ψ)”. Whenever we write “(ΦvΨ)” we mean “(¬Φ→Ψ)”. Whenever we write “(Φ ↔ Ψ)” we mean “((Φ→Ψ)^(Ψ→Φ))”; or, in full, we mean “¬((Φ→Ψ)→¬(Ψ→Φ))”. We will introduce a useful bit of metalanguage at this point, called the “turnstile” and written “|―”. We will write “{Ψi, Ψj, …}|― Φ” as a way of saying that Φ is provable given the assumptions or premises {Ψi, Ψj, …}. (Here the lower case letter i and j are variables or indefinite names, depending on context—so “Ψi” means, depending on the context, either any sentence or some specific but unidentified sentence. This is handy in our metalanguage so that we do not have to keep introducing new Greek letters for metalanguage variables; it is useful in our object language if we want to specify arbitrary or unknown atomic sentences, Pi, Pj….) The brackets “{” and “}” are used to indicate a set; we will discuss sets in section 17.5, but for now just think of this is a collection of things (in this case, sentences). If there is nothing on the left of the turnstile—which we can write like this, “{}|― Φ” —then we know that Φ is a theorem. Proving theorems using an axiomatic system is often more challenging than proving the same theorem in the natural deduction system. This is because you have fewer resources, and so it often seems to require some cleverness to prove a theorem. For this reason, we tend to continue to use the methods and rules of a natural deduction system when we aim to apply our logic; the primary benefit of an axiom system is to allow us to study our logic. This logical study of logic is sometimes called “metalogic”. An example can be illustrative. It would be trivial in our natural deduction system to prove (P→P). One proof would be: \[ \fitchprf{} { \subproof{\pline[1.]{P}[assumption for conditional derivation]}{ \pline[2.]{p}[repeat, 1] } \pline[3.]{(P \lif P)}[conditional derivation, 1-2] } \] To prove the equivalent in the axiom system is more difficult. We will prove (P1→P1). That is, we will prove {}|―(P1→P1). What we must do in this system is find instances of our axioms that we can use to show, via modus ponens, our conclusion. We will not be using the Fitch bars. The proof will begin with:1. ((P1→((P1→ P1) →P1)) → ((P1→(P1→P1)) →(P1→P1))) instance of (L2)
To see how why we are permitted to assert this sentence, remember that we are allowed in this system to assert at any time either a premise or an axiom. We are trying to prove a theorem, and so we have no premises. Thus, each line will be either an instance of an axiom, or will be derived from earlier lines using modus ponens. How then is line 1 an instance of an axiom? Recall that axiom (L2) is: ((Φ → (Ψ→χ)) → ((Φ → Ψ) → (Φ → χ)). We replace Φ with P1, and we get ((P1 → (Ψ→χ)) → ((P1 → Ψ) → (P1 → χ)). We replace Ψ with (P1→ P1) and we have ((P1 → ((P1→ P1) →χ)) → ((P1 → (P1→ P1)) → (P1 → χ)). Finally, we replace χ with P1, and we end up with the instance that is line 1. Continuing the proof, we have:1. ((P1→((P1→ P1) →P1)) →((P1→(P1→P1)) →(P1→P1))) | instance of (L2) |
2. (P1→((P1→ P1) →P1)) | instance of (L1) |
3. ((P1→(P1→P1)) →(P1→P1)) | modus ponens 1, 2 |
4. (P1→(P1→P1)) | instance of (L1) |
5. (P1→P1) | modus ponens 3, 4 |
((n2+n)/2) + (n+1) = ((n2+n)/2) + (2n+2)/2)
and((n2+n)/2) + (2n+2)/2) = ((n2+n) + (2n+2))/2
and((n2+n) + (2n+2))/2 = (n2 + 3n + 2)/2
Consider now the right side. Here, we are applying the equation. We are hoping it will come out the same as our independent reasoning above. We see:((n+1)2+ n+1) /2 = ((n2 + 2n + 1) + n + 1)/2
and((n2 + 2n + 1) + n + 1)/2 = (n2 + 3n + 2) /2
So, since the two are identical (that is, our reasoning based on induction and basic observations matched what the equation provides), we have proven the equation applies in the n+1th case, and so we have proven the induction step. Using mathematical induction we now conclude that the sum of numbers up to the nth number, for any n, is always (n2+n)/2.1. (P1→P2) | assumption |
2. (P2→P3) | assumption |
3. P1 | assumption |
4. P2 | modus ponens 1, 3 |
5. P3 | modus ponens 2, 4 |
{1, 2, 3}
A set is determined by its members (also sometimes called “elements”), but it is not the same thing as its members: 1 is not the same thing as {1}. And, we assume there is an empty set, the set of nothing. We can write this as {} or as ⌀. Sets can contain other sets: the following is a set containing three different members.{{}, {{}}, {{{}}}}
This is also an example of a pure set: it contains nothing but sets. If we develop our set theory with sets alone (if our domain of discourse is only sets) and without any other kinds of elements, we call it “pure set theory”. The members of sets are not ordered. Thus{1, 2, 3} = {3, 2, 1}
But an ordered set is a set in which the order does matter. We can indicate an ordered set using angle brackets, instead of curly brackets. Thus:<1, 2, 3> = <1, 2, 3>
but<1, 2, 3> ≠ <3, 2, 1>
We will write {...} for a set when we want to show its contents, and A, B, ... for sets when we are dealing with them more generally. We write x∈A to mean that x is a member of the set A. As noted, sets can be members of sets. Sets are defined by their contents, so two sets are the same set if they have the same contents.A = B if and only if ∀x(x∈A ↔ x∈B)
This is interesting because it can be a definition of identity in set theory. In the natural deduction system first order logic, we needed to take identity as a primitive. Here, we have instead defined it using membership and our first order logic. If all the contents of a set A are in another set B, we say A is a subset of B.A ⊆ B if and only if ∀x(x∈A → x∈B)
A proper subset is a subset that is not identical (that means B has something not in A, in the following case):A ⊂ B if and only if (A ⊆ B ^ A≠B)
The empty set is a subset of every set. The power set operation gives us the set of all subsets of a set.℘(A) = B if and only if ∀x(x ⊆ A → x∈B)
There are always 2n members in the power set of a set with n members. That is, if A has n members, then ℘(A) has 2n members. The cardinal size of a set is determined by finding a one-to-one correspondence with the members of the set. Two sets have the same cardinal size (we say, they have the same cardinality) if there is some way to show there exists a one-to-one correspondence between all the members of one set and all the members of the other. For the cardinality of some set A, we can write|A|
There is a one-to-one correspondence to be found between all the members of A and all the members of B, if and only if|A| = |B|
If A ⊆ B then |A| ≤ |B|. The union of two sets is a set that contains every member of either set.A ∪ B is defined as satisfying ∀x((x∈A v x∈B) → x ∈ A ∪ B)
The intersection of two sets is a set that contains every member that is in both the sets.A ∩ B is defined as satisfying ∀x((x∈A ^ x∈B) → x ∈ A ∩ B)
A shorthand way to describe a set is to write the following:{ x | Φ(x)}
This is the set of all those things x such that x has property Φ. So for example if our domain of discourse were natural numbers, then the set of all numbers greater than 100 could be written: { x | x > 100 }. A relation is a set of ordered sets of more than one element. For example, a binary relation meant to represent squaring might include {… <9, 81>, <10, 100> …}; a trinary relation meant to represent factors might include {… <9, 3, 3>, <10, 2, 5> …}; and so on. One useful kind of relation is a product. The product of two sets is a set of all the ordered pairs taking a member from the first set and a member from the second.A × B is defined as satisfying ∀x∀y((x∈A ^ y∈B) ↔ <x, y> ∈ A × B)
Many of us are familiar with the either of the Cartesian product, which forms the Cartesian plane. The x axis is the set of real numbers R, and the y axis is the set of real numbers R. The Cartesian product is the set of ordered pairs R × R. Each such pair we write in the form <x, y>. These form a plane, and we can identify any point in this plane using these “Cartesian coordinates”. Another useful kind of relation is a function. A function f is a set that is a relation between the members of two sets. One set is called the “domain”, and the other is called the “range”. Suppose A is the domain and B is the range of a function, then (if we let a be a member of A and b and c be members of B, so by writing fab I mean that function f relates a from its domain to b in its range):If f is a function from A into B, then if fab and fac then b=c
This captures the idea that for each “input” (item in its domain) the function has one “output” (a single corresponding item in its range). We also say a function f isIf fab and fcb then a=c
then f is a 1-to-1 function from A and into B. The idea of being 1-to-1 is that f is a function that if reversed would be a function also. As we noted above, if there is a 1-to-1 function that is on A and onto B, then |A| = |B|. If a function f is 1-to-1 on A and is into B, then we know that |B| ≥ |A|. (Such a function has every member of A in its domain, and for each such member picks out exactly one member of B; but because we only know that the function is into B, we do not know whether there are members of B that are not in the range of the function, and we cannot be sure that there is some other 1-to-1 function on A and onto B.) A common notation also is to write f(a) for the function f with a from its domain. So, when we write this, we identify the expression with the element from the range that the function relates to a. That is, f(a) = b. We can prove many interesting things using this natural set theory. For example, Cantor was able to offer us the following proof that for any set S, |℘(S)| > |S|. That is, the cardinality of the power set of a set is always greater than the cardinality of that set. We prove the claim by indirect proof. We aim to show that |℘(S)| > |S|, so we assume for reductio that |℘(S)| ≤ |S|. We note that there is a function on S and into ℘(S); this is the function that takes each member of S as its domain, and assigns to that member the set of just that element in ℘(S). So, for example, if a∈S then {a}∈℘(S); and there is function on S and into ℘(S) that assigns a to {a}, b to {b}, and so on. Since there is such a function, |℘(S)| ≥ |S|. But if |℘(S)| ≤ |S| and |℘(S)| ≥ |S|, then |℘(S)| = |S|. Therefore, there is a one-to-one function on S and onto ℘(S). Let f be one such function. Consider that each object in S will be in the domain of f, and be related by f to a set in ℘(S). It follows that each element of S must be related to a set that either does, or does not, contain that element. In other words, for each s∈S, f(s) is some set A∈℘(S), and either s∈A or ¬s∈A. Consider now the set of all the objects in the domain of f (that is, all those objects in S) that f relates to a set in ℘(S) that does not contain that element. More formally, this means: consider the set C (for crazy) where C={ s | s∈S ^ ¬s ∈ f(s)}. This set must be in ℘(S), because every possible combination of the elements of S is in ℘(S)—including the empty set and including S. But now, what object in the domain of f is related to this set? We suppose that f is a 1-to-1 function on S and onto ℘(S), so some element of S must be related by f to C, if f exists. Call this element c; that is, suppose f(c)=C. Is c∈C? If the answer is yes, then it cannot be that f(c)=C, since by definition C is all those elements of S that f relates to sets not containing those elements. So ¬c ∈C. But then, C should contain c, because C contains all those elements of S that are related by f to sets that do not contain that element. So c∈C and ¬c ∈C. We have a contradiction. We conclude that the source of the contradiction was the assumption for reductio, |℘(S)| ≤ |S|. Thus, for any set S, |℘(S)| > |S|. This result is sometimes called “Cantor’s theorem”. It has interesting consequences, including that there cannot be a largest set: every set has a powerset that is larger than it. This includes even infinite sets; Cantor’s theorem shows us that there are different sized infinities, some larger than others; and, there is no largest infinity.(L4) (∀xiΦ(xi) → Φ(α))
(L5) (∀xi(Φ → Ψ) → (Φ →∀xiΨ)) if xi is not free in Φ.
Where α is any symbolic term. The additional rule is generalization. From |― Φ we can conclude |― ∀xiΦ(xi). This plays the role of universal derivation in our natural deduction system for the first order logic. This compact system, only slightly larger than the axiomatic propositional logic, is as powerful as our natural deduction system first order logic. This is a convenient place to describe, in a preliminary and general way, how we can conceive of a formal semantics for the first order logic. When we introduced the first order logic, we kept the semantics intuitive. We can now describe how we could start to develop a formal semantics for the language. The approach here is one first developed by Alfred Tarski (1901-1981).^{[14]} Tarski introduces a separate concept of satisfaction, which he then uses to define truth, but we will cover over those details just to illustrate the concept underlying a model. The approach is to assign elements of our language to particular kinds of formal objects. We group these all together into a model. Thus, a model M is an ordered set that contains a number of things. First, it contains a set D of the things that our language is about—our domain of discourse. Second, the model includes our interpretation, I, which contains functions for the elements of our language. For each name, there is a function that relates the name to one object in our domain of discourse. For example, suppose our domain of discourse is natural numbers. Then a name a1 in our language might refer to 1. We say then that the “interpretation” of a1 is 1. The object in our interpretation that captures this idea is a function that includes < a1, 1>. The interpretation of each predicate relates each predicate to a set of ordered sets of objects from our domain. Each predicate of arity n is related to a set of ordered sets of n things. We can write Dn for all the ordered sets of n elements from our domain. Then, each predicate of arity n has as an interpretation some (not necessarily all) of the relations in Dn. For example, an arity two predicate F1 might be meant to capture the sense of “… is less than or equal to…”. Then the interpretation of F1 is a function from F1 to a set of ordered pairs from our domain of discourse, including such examples as {… <1, 2>, <1, 1000>, <8, 10>, …} and so on. We then say that a sentence like F1a2a3 is true if the interpretation for a2 and the interpretation for a3 are in the interpretation for F1. So, if a2 is 2, and a3 is 3, then F1a2a3 would be true because <2, 3> will be in the interpretation for F1. We will need an interpretation for the quantifiers. Without going into the details of how we can describe this rigorously (Tarski uses a set of objects called “sequences”), the idea will be that if we could put any name into the bound variable’s position, and get a sentence that is true, the universally quantified statement is true. To return to our example: assuming again that our domain of discourse is natural numbers, so there is a least number 1, then the sentence ∀xjFa1xj would be true if F1a1xj would be true for any number we put in for xj. Suppose that the interpretation of a1 is 1. Then F1a1xj would be true no matter what element from our domain of discourse we took xj to be referring to, because 1 is less than or equal to every number is our domain of discourse. Therefore, ∀xjFa1xj would be true. We need only add the usual interpretation for negation and the conditional and we have a semantics for the first order logic. This is all very brief, but it explains the spirit of the semantics that is standard for contemporary logic. Much more can be said about formal semantics, and hopefully you will feel encouraged to study further.For there is nothing to prevent someone’s having said ten thousand years beforehand that this would be the case, and another’s having denied it; so that whichever the two was true to say then, will be the case of necessity. (18b35)^{[15]}Here is Aristotle’s worry. Suppose tomorrow is June 16, 2014. Necessarily there either will or will not be a sea battle tomorrow (let us assume that we can define “sea battle” and “tomorrow” well enough that they are without vagueness or ambiguity). If there is a sea battle tomorrow, is the person who said today, or even ten thousand years ago, “There will be a sea battle on June 16, 2014” necessarily right? That is, if there is a sea battle tomorrow, is it necessary that there is a sea battle tomorrow? Aristotle concludes that, if there is a sea battle tomorrow, it is not necessary now.
What is, necessarily is, when it is; and what is not, necessarily is not, when it is not. But not everything that is, necessarily is; and not everything that is not, necessarily is not…. It is necessary for there to be or not to be a sea-battle tomorrow; but it is not necessary for a sea-battle to take place tomorrow, nor for one not to take place—though it is necessary for one to take place or not to take place. (19b30)Aristotle’s reasoning seems to be, from “necessarily (P v ¬P)”, we should not conclude: “necessarily P or necessarily ¬P”. Philosophers would like to be able to get clear about these matters, so that we can study and ultimately understand necessity, possibility, and time. For this purpose, philosophers and logicians have developed modal logic. In this logic, we have most often distinguished possibility from time, and treated them as—at least potentially—independent. But that does not mean that we might not ultimately discover that they are essentially related. In this section, we will describe propositional modal logic; it is also possible to combine modal logic with first order logic, to create what is sometimes called “quantified modal logic”. Our goal however is to reveal the highlights and basic ideas of modal logic, and that is easiest with the propositional logic as our starting point. Thus, we assume our axiomatic propositional logic—so we have axioms (L1), (L2), (L3); modus ponens; and direct derivation. We also introduce a new element to the language, alone with atomic sentences, the conditional, and negation: “necessary”, which we write as “□”. The syntax of this operator is much like the syntax of negation: if Φ is a sentence, then
□Φ
is a sentence. We read this as saying, “necessarily Φ” or “it is necessary that Φ”. The semantics for necessity are a bit too complex to be treated fairly in this overview. However, one intuitive way to read “necessarily Φ” is to understand it as saying, in every possible world Φ is true. Or: in every possible way the world could be, Φ is true. It is useful to introduce the concept of possibility. Fortunately, it appears reasonable to define possibility using necessity. We define “possible” to mean, not necessarily not. We use the symbol “◊” for possible. Thus, if Φ is a sentence, we understand◊Φ
to be a sentence. Namely, this is the sentence,¬□¬Φ
We read “◊Φ” as saying, it is possible that Φ. One intuitive semantics is that it means in at least one possible world, Φ is true; or: in at least one possible way the world could be, Φ is true. The difficult and interesting task before us is to ask, what axioms best capture the nature of necessity and possibility? This may seem an odd way to begin, but in fact the benefit to us will come from seeing the consequence of various assumptions that we can embody in different axioms. That is, our choice of axioms results in a commitment to understand necessity in a particular way, and we can discover then the consequences of those commitments. Hopefully, as we learn more about the nature of necessity and possibility, we will be able to commit to one of these axiomatizations; or we will be able to improve upon them. All the standard axiomatizations of modal logic include the following additional rule, which we will call “necessitation”.⌀ |― Φ
_____
⌀ |― □Φ
This adds an element of our metalanguage to our rule, so let’s be clear about what it is saying. Remember that “⌀ |― Φ” says that one can prove Φ in this system, without premises (there is only an empty set of premises listed to the left of the turnstile). In other words, “⌀ |― Φ” asserts that Φ is a theorem. The necessitation rule thus says, if Φ is a theorem, then □Φ. The motivation for the rule is hopefully obvious: the theorems of our propositional logic are tautologies. Tautologies are sentences that must be true. And “must” in this description hopefully means at least as much as does “necessarily”. So, for our propositional logic, the theorems are all necessarily true. Different axiomatizations of modal propositional logic have been proposed. We will review four here, and discuss the ideas that underlie them. The most basic is known variously as “M” or “T”. It includes the following additional axioms:(M1) (□Φ → Φ)
(M2) (□(Φ → Ψ) → (□Φ → □Ψ))
Both are intuitive. Axiom (M1) says that if Φ is necessary, then Φ. From a necessary claim we can derive that the claim is true. Consider an example: if necessarily 5 > 2, then 5 > 2. Axiom (M2) says that if it is necessary that Φ implies Ψ, then if Φ is necessary, Ψ is necessary. An extension of this system is to retain its two axioms, and add the following axiom:(M3) (Φ → □◊Φ)
The resulting system is often called “Brouwer,” after the mathematician Luitzen Brouwer (1881-1966). Axiom (M3) is more interesting, and perhaps you will find it controversial. It says that if Φ is true, then it is necessary that Φ is possible. What people often find peculiar is the idea that a possibility could be necessary. On the other hand, consider Aristotle’s example. Suppose that there is a sea battle today. Given that it actually is happening, it is possible that it is happening. And, furthermore, given that it is happening, is it not the case that it must be possible that it is happening? Such, at least, is one possible motive for axiom (M3). More commonly adopted by philosophers are modal systems S4 or S5. These systems assume (M1) and (M2) (but not (M3)), and add one additional axiom. S4 adds the following axiom:(M4) (□Φ → □□Φ)
This tells us that if Φ is necessary, then it is necessary that Φ is necessary. In S4, it is possible to prove the following theorems (that is, these are consequences of (M1), (M2), and (M4)):(□Φ ↔ □□Φ)
(◊Φ ↔ ◊◊Φ)
The modal system S5 instead adds to M the following axiom:(M5) (◊Φ → □◊Φ)
This axiom states that if something is possible, then it is necessary that it is possible. This is often referred to as the “S5 axiom”. It is perhaps the most controversial axiom of the standard modal logic systems. Note these interesting corollary theorems of S5:(□Φ ↔ ◊□Φ)
(◊Φ ↔ □◊Φ)
These modal logics are helpful in clarifying a number of matters. Let’s consider several examples, starting with questions about meaning in a natural language. Many philosophers pursued modal logic in the hopes that it would help us understand and represent some features of meaning in a natural language. These include attempting to better capture the meaning of some forms of “if…then…” expressions in a natural language, and also the meaning of predicates and other elements of a natural language. A problem with some “if…then…” expressions concerns that sometimes what appears to be a conditional is not well captured by the conditional in our propositional logic. In chapter 3, we had an example that included the sentence “If Miami is the capital of Kansas, then Miami is in Canada”. This sentence is troubling. Interpreting the conditional as we have done, this sentence is true. It is false that Miami is the capital of Kansas, and it is false that Miami is in Canada. A conditional with a false antecedent and a false consequent is true. However, some of us find that unsatisfactory. We have recognized from the beginning of our study of logic that we were losing some, if not much, of the meaning of a natural language sentence in our translations. But we might want to capture the meaning that is being lost here, especially if it affects the truth value of the sentence. Some people want to say something like this: Kansas is in the United States, so if it were true that Miami were the capital of Kansas, then Miami would be in the United States, not in Canada. By this reasoning, this sentence should be false. It seems that what we need is a modal notion to capture what is missing here. We want to say, if Miami were in Kansas, then it would be in the United States. Some philosophers thought we could do this by reading such sentences as implicitly including a claim about necessity. Let us fix the claim that Kansas is in the United States, and fix the claim that anything in the United States is not in Canada, but allow that Miami could be the capital of other states. In other words, let us suppose that it is necessary that Kansas is in the United States, and it is necessary that anything in the United States is not in Canada, but possible that Miami is the capital of Kansas. Then it appears we could understand the troubling sentence as saying,Necessarily, if Miami is the capital of Kansas, then Miami is in Canada.
Assuming an implicit key, we will say,□(P1→P2)
This seems to make some progress toward what we were after. We take the sentence "if Miami is the capital of Kansas, then Miami is in Canada" to mean: in any world where Miami is in Kansas, then in that world Miami is in Canada. But, given the assumptions we have made above, this sentence would be false. There would be worlds where Miami is the capital of Kansas, and Miami is not in Canada. This at least seems to capture our intuition that the sentence is (on one reading) false. There are further subtleties concerning some uses of “if… then….” in English, and it is not clear that the analysis we just gave is sufficient, but one can see how we appear to need modal operators to better capture the meaning of some utterances of natural languages, even for some utterances that do not appear (at first reading) to include modal notions. Another problem concerning meaning has to do with attempts to better capture the meaning of more fundamental elements of our language, such as our predicates. Our first order logics have what philosophers call an “extensional semantics”. This means that the meaning of terms is merely their referent, and the meaning of predicates is the sum of things that they are true of (see section 17.6). However, upon reflection, this seems inadequate to describe the meaning of terms and predicates in a natural language. Consider predicates. The philosopher Rudolf Carnap (1891-1970) used the following example; suppose that human beings are the only rational animals (“rational” is rather hard to define, but if we have a strong enough definition—language using, capable of some mathematics, can reason about the future—this seems that it could be true, assuming by “animal” we mean Terrestrial metazoans).^{[16]} Then the following predicates would be true of all and only the same objects:… is a rational animal.
… is a human.
That means the extension of these predicates would be the same. That is, if we corralled all and only the rational animals, we would find that we had corralled all and only the humans. If the meaning of these predicates were determined by their extensions, then they would have the same meaning. So the sentence:All and only humans are rational animals.
would be sufficient, in an extensional semantics, to show that these predicates mean the same thing. But obviously these predicates do not mean the same thing. How can we improve our logic to better capture the meaning of such natural language phrases? The philosopher Rudolf Carnap proposed that we use modal logic for this purpose. The idea is that we capture the difference using the necessity operator. Two sentences have the same meaning, for example, if necessarily they have the same truth value. That is, “… is a human” and “… is a rational animal” would have the same meaning if and only if they necessarily were true of all and only the same things. We have not introduced a semantics for modal logic combined with our first order logic. However, the semantics we have discussed are sufficient to make sense of these ideas. Let us use the following key:F1x: x is a rational animal.
F2x: x is a human.
Then we can translate “All and only rational animals are human” as:∀x(F1x ↔ F2x)
And if the meaning of a predicate were merely its extension (or were fully determined by its extension) then these two predicates F1 and F_{2} would mean the same thing. The proposal is that in order to describe the meanings of predicates in a natural language, we must look at possible extensions. We could then say that F1 and F2 have the same meaning if and only if the following is true:□∀x(F1x ↔ F2x)
Much is going to turn on our semantics for these predicates and for the necessity operator, but the idea is clear. We see the difference in the meaning between “… is a human” and “… is a rational animal” by identifying possible differences in extensions. It is possible, for example, that some other kind of animal could be rational also. But then it would not be the case that necessarily these two predicates are true of the same things. In a world where, say, descendants of chimpanzees were also rational, there would be rational things that are not human. The meaning of a predicate that is distinct from its extension is called its “intension”. We have just described one possible “intensional semantics” for predicates: the intension of the two predicates would be the same if and only if the predicates have the same extension in every world (or: in every way the world could be). This seems to get us much closer to the natural language meaning. It also seems to get to something deep about the nature of meaning: to understand a meaning, one must be able to apply it correctly in new and different kinds of situations. One does not know beforehand the extension of a predicate, we might argue; rather, one knows how to recognize things that satisfy that predicate—including things we may not know exist, or may even believe do not exist. Many philosophers and others who are studying semantics now use modal logic as a standard tool to try to model linguistic meanings. Modal logics have important uses outside of semantics. Here are two problems in metaphysics that it can help clarify. Metaphysics is that branch of philosophy that studies fundamental problems about the nature of reality, such as the nature of time, mind, or existence. Consider Aristotle’s problem: is it the case that if there necessarily is or is not a sea battle tomorrow, then it is the case that necessarily there is, or necessarily there is not, a sea battle tomorrow? In each of the systems that we have described, the answer is no. No sentence of the following form is a theorem of any of the systems we have described:(□(Φ v ¬Φ) → (□Φ v □¬Φ))
It would be a problem if we could derive instances of this claim. To see this, suppose there were a sea battle. Call this claim S. In each of our systems we can prove as a theorem that (S → ◊S), which by definition means that (S → ¬□¬S). (Surely it is a good thing that we can derive this; it would be absurd to say that what is, is not possible.) It is a theorem of propositional logic that (S v ¬S), and so by necessitation we would have □(S v ¬S). Then, with few applications of modus ponens and modal logic, we would have □S.1. (□(Sv¬S) → (□Sv□¬S)) | the problematic premise |
2. S | premise |
3. (S v ¬S) | theorem |
4. □(S v ¬S) | necessitation, 3 |
5. (□S v □¬S) | modus ponens, 1, 4 |
6. (S → ¬□¬S) | theorem |
7. ¬□¬S | modus ponens 6, 2 |
8. □S | modus tollendo ponens, 5, 7 |
1. We can conceive of beings that are physically identical to us but that lack conscious experiences.
2. If we can conceive of beings that are physically identical to us and that lack conscious experiences, then it is possible that there are beings that are physically identical to us but that lack conscious experiences.
3. If it is possible that there are beings that are physically identical to us and that lack conscious experiences, then physical sciences alone cannot explain conscious experience.
4. The physical sciences alone cannot explain conscious experience.
This argument is obviously valid; it requires only two applications of modus ponens to show line 4. But is the argument sound? This is very important. Many people study the human mind, and many more people would benefit if we better understood the mind. Understanding consciousness would seem to be an important part of that. So, psychologists, psychiatrists, philosophers, artificial intelligence researchers, and many others should care. But, if this argument is sound, we should start spending grant money and time and other resources on radical new methods and approaches, if we want to understand consciousness. Many philosophers have denied premise 1 of this argument. Those philosophers argue that, although it is easy to just say, “I can conceive of beings that are physically identical to us but that lack conscious experiences”, if I really thought hard about what this means, I would find it absurd and no longer consider it conceivable. After all, imagine that the people weeping next to you at a funeral feel nothing, or that a person who has a severe wound and screams in pain feels nothing. This is what this argument claims is possible: people could exist who act at all times, without exception, as if they feel pain and sadness and joy and so on, but who never do. Perhaps, if we think that through, we’ll say it is not really conceivable. Premise 2 is very controversial, since it seems that we might fool ourselves into thinking we can conceive of something that is not possible. It seems to mix human capabilities, and thus subjective judgments, with claims about what is objectively possible. Premise 3 turns on technical notions about what it means for a physical science to explain a phenomenon; suffice it to say most philosophers agree with premise 3. But what is interesting is that something appears to be wrong with the argument if we adopt the S5 axiom, (M5). In particular, it is a theorem of modal logic system S5 that (□Φ ↔ ◊□Φ). With this in mind, consider the following argument, which makes use of key claims in Chalmers’s argument.1. We can conceive of it being true that necessarily a being physically identical to us will have the same conscious experience as us.
2. If we can conceive of it being true that necessarily a being physically identical to us will have the same conscious experience as us, then it is possible that necessarily a being physically identical to us will have the same conscious experience as us.
3. It is possible that necessarily a being physically identical to us will have the same conscious experience as us.
4. If it is possible that necessarily a being physically identical to us will have the same conscious experience as us, then necessarily a being physically identical to us will have the same conscious experience as us.
5. Necessarily a being physically identical to us will have the same conscious experience as us.
Premise 1 of this argument seems plausible; surely it is at least as plausible as the claim that we can conceive of a being physically identical to us that does not have phenomenal experience. If we can imagine those weird people who act like they feel, but do not feel, then we can also imagine that whenever people act and operate like us, they feel as we do. Premise 2 uses the same reasoning as premise 2 of Chalmers’ argument: what is conceivable is possible. Line 3 is introduced just to clarify the argument; it follows from modus ponens of premises 2 and 1. Line 4 uses (◊□Φ → □Φ), which we can derive in S5. The conclusion, line 5, follows by modus ponens from 4 and 3. The conclusion is what those in this debate agree would be sufficient to show that the physical sciences can explain the phenomenon (via the same reasoning that went into line 3 of Chalmers’s argument). If we accept modal system S5, then it seems that there is something wrong with Chalmers’s argument, since the kind of reasoning used by the argument can lead us to contradictory conclusions. Defenders of Chalmers’s argument must either reject axiom (M5), or deny line 1 of this new argument. As I noted above, this matters because we would like to know how best to proceed in understanding the mind; whether either of these arguments is sound would help determine how best we can proceed.(A1) | (x1 = x2 → x1′ = x2′) |
(A2) | (x1′ = x2′ → x1 = x2) |
(A3) | (x1 = x2 → (x1 = x3 → x2 = x3)) |
(A4) | ¬ x1′ = 0 |
(A5) | x1 + 0 = x1 |
(A6) | x1 + x2′ = (x1 + x2)′ |
(A7) | x1 ∙ 0 = 0 |
(A8) | x1 ∙ x2′ = (x1 ∙ x2) + x1 |
(A9) (Φ(0) → (∀xi(Φ(xi) →Φ(xi′)) →∀xiΦ(xi)))
These axioms are sufficient to do everything that we expect of arithmetic. This is quite remarkable, because arithmetic is very powerful and flexible, and these axioms are few and seemingly simple and obvious. Since these explicitly formulate our notions of addition, multiplication, and numbers, they do not achieve what Frege dreamed; he hoped that the axioms would be more general, and from them one would derive things like addition and multiplication. But this is still a powerful demonstration of how we can reduce great disciplines of reasoning to compact fundamental principles. Axiomatizations like this one have allowed us to study and discover shocking things about arithmetic, the most notable being the discovery by the logician Kurt Godel (1906-1978) that arithmetic is either incomplete or inconsistent. In closing our discussion of axiomatic systems, we can use this system to prove that 1+1=2. We will use the indiscernibility of identicals rule introduced in 15.3. We start by letting x1 be 0′ and x2 be 0 to get the instance of axiom (A6) on line 1, and the instance of (A5) on line 2.1. | 0′ + 0′ = (0′ + 0)′ | axiom (A6) |
2. | 0′ + 0 = 0′ | axiom (A5) |
3. | 0′ + 0′ = 0′′ | indiscernibility of indenticals, 1, 2 |