Chapter 2 Notes
An argument is a set of statements consisting of zero or more premises and a conclusion, where the premises are intended to give reason to think that the conclusion is true.
We will be interested exclusively in deductive arguments. A successful deductive argument is said to be logically valid. An argument is valid if and only if it is not possible for all the premises to be true and the conclusion false. Equivalently, an argument is valid if and only if, if the premises are true, then the conclusion must be true as well.
The conclusion of a logically valid argument is a logical consequence of the premises.
Notice that the premises of a valid argument are not necessarily true. What makes it valid is just that, if the premises are true, then so is the conclusion. Whether the premises actually are true is another matter!
If an argument is valid and, in addition, all of its premises are true, then the argument is said to be sound.
A proof is a way of showing that a conclusion is a logical consequence of a set of premises.
A proof breaks a chain of reasoning up into very small steps which can easily be seen to be valid. In a formal proof, the steps can be checked mechanically.
1. Reflexivity. For any object x, x = x.
2. Transitivity. For any objects x, y, and z, if x = y and y = z, then x = z.
3. Symmetry. For any objects x and y, if x = y, then y = x.
Informal Name Formal Name Description Reflexivity =Intro At any point in a proof, if n is any constant, you can write the sentence n = n Indiscernibility of Identicals;
=Elim If n and m are any constants, and you already have the sentence n = m (either as a premise or as something you have already proved), then in any other sentence you already have, you may replace any occurrence of n by an occurrence of m
=Intro corresponds directly to the reflexive property of identity.
=Elim does not directly correspond to any of the properties listed above. Sometimes it is referred to as a substitution rule, because it basically allows you, if you have the sentence 'a = b', to replace an occurrence of 'a' by an occurrence of 'b' anywhere you want to. (Note on English usage: "substitute 'b' for 'a'" means the same thing as "replace 'a' by 'b'". I've noticed in recent years that some students have a tendency to use the word "substitute" in the wrong direction, which can get very confusing!)
Note that the rule does not tell us that we can replace any occurrence of 'b' with 'a'! The rule only says you can replace the name on the left-hand side of the identity sentence with the name on the right-hand side. It doesn't follow without argument that you can replace the name on the right-hand side with the one on the left-hand side! That only works if identity is symmetric, as defined above, that is, if for any names n and m, if n = m then m = n. This is true, but it's not OK to use this principle without first proving that it's true. (Notice that there are many two-place relations that are not symmetric, such as Larger(x,y) or FrontOf(x,y).)
This is why the text, in the "You Try It" exercise, makes us go through the steps of proving, from n = m, that m = n. However, once we've seen how to do this, B&E allow us to be a little sloppier. (Notice that Fitch will let you apply =Elim in either direction.)
USING THE RULES TO PROVE TRANSITIVITY AND SYMMETRY
Using =Intro and =Elim, we can prove the other two properties of identity.
We begin with an informal proof: a paragraph of English prose. Informal proofs are still rigorous and follow a very precise format. You need to think of an informal proof as proceeding one step at a time, and every step needs to be justified either as a premise of the argument, or as following from earlier steps in accordance with specified rules.
You cannot write anything in an informal proof that is not either a premise, or something that can be written on the basis of earlier steps by applying one of the rules. You cannot appeal to your intuitive understanding of the concepts involved, only to the explicitly stated rules.
So, suppose that we are given that a = b, and we want to prove that b = a. But that's obvious! It may be obvious, but "it's obvious" does not count as a proof. We are only allowed to use substitutivity (also known as indiscernibility) and reflexivity.
So, our proof might look like this:
We are given that a = b. By reflexivity, we also know that a = a. Since a = b, by indiscernibility we can replace the first occurrence of 'a' in 'a = a' by 'b'. This gives us b = a, as desired.
Our first step, a = b, is a premise. Our second step, a = a, is justified by reflexivity. Then the third step, b = a, follows from the first two by using the indiscernibility of identicals. Note that when we use indiscernibility, we need to state explicitly which sentence we are making a substitution in, and which occurrence of the constant we are making a substitution for. (There are two occurrences of 'a' in the sentence 'a = a', so we need to explain that we are replacing the first occurrence by 'b'.
Converting this informal reasoning into a formal proof, we get the following:
1. a = b
2. a = a =Intro
3. b = a =Elim: 1, 2
Step three is worth looking at a little. We are thinking of a = a as the sentence we want to make a substitution into. Because we have the identity in 1, we know we can take any occurrence of 'a' and replace it with a 'b'.
So, we pick the first occurrence of a in line 2, and replace it with a b. That's something =Elim allows us to do, so this is an acceptable deductive step. Since the same pattern of proof will work no matter what names we use instead of 'a' and 'b', we've essentially shown that identity is symmetric.
Similarly, we can show that identity is transitive using only =Intro and =Elim. Giving an informal proof of transitivity is one of the homework problems. Here is a formal version:
1. a = b
2. b = c
3. a = c =Elim: 1, 2
This is a one-step proof! In this case we are thinking of line 1 as the sentence we will substitute into. Then line 2 tells us that, in line 1, we can take any occurrence of 'b' and replace it with 'c'. When we do that, we get line 3.
Chapter 2 also introduces something that's kind of like a rule, but is not a part of our formal deductive system. This is the "ANA CON" mechanism. Ana Con is short for "analytic consequence." Ana Con is incredibly powerful. It is more powerful than the real rules in two different ways.
First, it looks for a proof using the other rules, and an application of Ana Con to derive a new line on the basis of earlier lines will be successful as long as there is some way to get the new line from the earlier ones, no matter how many steps it takes. So it can essentially pack what should require many steps in a formal proof into a single step.
Second, Ana Con uses more than the rules of the formal deductive system. It also makes use of relations in meaning between the predicates of our language. For instance, you can use Ana Con to derive 'Smaller(a,b)' from 'Larger(b,a)' even though there is no rule in the deductive system that would let you do this. (Why not add rules for all this stuff? Because there would be far too many, and because they are too closely tied to very specific subject matters. Logic is supposed to be general, to concern reasoning about any subject matter whatsoever, so it shouldn't include special-purpose rules that apply only to size relations, or shapes, or whatever.)
(Our text is different in some respects from most texts in this area. Most texts ignore analytic relations between predicates. In fact, most texts at this stage do not even have notations for predicates and constants, but simply use upper-case letters such as 'P' and 'Q' to represent atomic sentences. Our text pays more attention to natural language. The advantage is added realism and usefulness; the disadvantage is added complexity.)
Later in the course we will see that we can capture these relationships of meaning by constructing axioms and then using the formal system to see what follows from a set of premises together with the relevant axioms.
When to Use Ana Con
Since Ana Con is so powerful, you could use it to essentially turn any proof into a one-liner. Just select all the premises of the argument, write down the conclusion, and justify it using Ana Con. Done!
Obviously, this is not how the homework assignments should be done. DON'T USE ANA CON UNLESS THE DIRECTIONS EXPLICITLY TELL YOU IT'S OK! And even then, only use it in the way the directions indicate -- basically, you should only use it for very small steps that cannot be derived using the official system.
You shouldn't have to worry about this rule yet. It just tells you that you can take any line you already have in a proof and write it down again (this will have to be qualified a little when we get to subproofs, but never mind that for now). At the moment this probably seems like a pretty useless rule, but it will come in handy later on.
Examples of proofs.
Notice that you'll need to use a new piece of software this time, namely the Fitch program for constructing proofs. This is a really remarkable and delightful program. It has a few quirks that take a little getting used to, but it has the potential to be incredibly helpful as you're learning to do proofs, because you can check any step whenever you want. You can also check the whole proof when you're done to make sure it is successful.
I would suggest checking each individual step as you construct a proof, at least when you're starting out; it can save you from writing a 20-line proof only to find out that you made a mistake at line 2 and need to redo the whole thing.
citing earlier lines by selecting them
showing line numbers on which steps rest
moving around from line to line
How do you prove that a conclusion does not follow from (i.e. is not a logical consequence of) a set of premises? Well, to say that it is a logical consequence is to say that it's not possible for all the premises to be true and the conclusion false. So you can show that a conclusion is not a logical consequence of some premises by showing that it is possible for the premises to be true and the conclusion false. Tarski's World gives us a very vivid way of accomplishing this: if we can build a Tarski's World in which all the premises are true and the conclusion is false, then the argument can't be valid (since we have just done something that would be impossible if the argument were valid). Such a world is a counterexample to the argument.