Discrete Mathematics: An Open Introduction, 4th edition (preview)

In order to do mathematics, we must be able to talk and write about mathematics. Perhaps your experience with mathematics so far has mostly involved finding numerical answers to problems. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process.

In fact, the primary goal of mathematics, as an academic discipline in its own right, is to establish general mathematical truths. How can we know whether these facts, perhaps called theorems or propositions, are true? We construct valid arguments, called proofs, which establish the truth of the statements. Here, an argument is not the sort of thing you have with your Mom when you disagree about what to have for dinner. Rather, we have a technical definition of the term.

So to determine whether we have a proof of a statement, we must decide both whether the sequence of premises are each true, and whether the argument is valid: whether the conclusion follows from the premises. How can we do this?

Since arguments are built up of statements, we should try to understand what a statement is.

Notice that if the sentences in an argument were not able to be true or false, there would be no way to determine whether the argument was valid, since that describes a relationship between the truth values of the premises and conclusions.

The goal of this section is to explore the different “shapes” a statement can take. We will see that more complicated statements can be built up from simpler ones, entirely in ways that determine their truth value based on the truth values of their parts.

A statement is any declarative sentence which is either true or false. A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular.

The reason the sentence “\(3 + x = 12\)” is not a statement is that it contains a variable. Depending on what \(x\) is, the sentence is either true or false, but right now it is neither. One way to make the sentence into a statement is to specify the value of the variable in some way. This could be done by specifying a specific substitution, for example, “\(3+x = 12\) where \(x = 9\text{,}\)” which is a true statement. Or you could capture the free variable by quantifying over it, as in, “for all values of \(x\text{,}\) \(3+x = 12\text{,}\)” which is false. We will discuss quantifiers in more detail in Section 1.3.

You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives. For example, this is a molecular statement:

Note that we can break this down into two smaller statements. The two shorter statements are connected by an “and.” We will consider 5 connectives: “and” (Sam is a man and Chris is a woman), “or” (Sam is a man or Chris is a woman), “if…, then…” (if Sam is a man, then Chris is a woman), “if and only if” (Sam is a man if and only if Chris is a woman), and “not” (Sam is not a man). The first four are called binary connectives (because they connect two statements) while “not” is an example of a unary connective (since it applies to a single statement).

These molecular statements are of course still statements, so they must be either true or false. The absolutely key observation here is that which truth value the molecular statement achieves is completely determined by the type of connective and the truth values of the parts. We do not need to know what the parts actually say, only whether those parts are true or false. So to analyze logical connectives, it is enough to consider propositional variables (sometimes called sentential variables), usually capital letters in the middle of the alphabet: \(P, Q, R, S, \ldots\text{.}\) We think of these as standing in for (usually atomic) statements, but there are only two values the variables can achieve: true or false.¹ We also have symbols for the logical connectives: \(\wedge\text{,}\) \(\vee\text{,}\) \(\imp\text{,}\) \(\iff\text{,}\) \(\neg\text{.}\)

The truth value of a statement is determined by the truth value(s) of its part(s), depending on the connectives:

Note that for us, or is the inclusive or (and not the sometimes used exclusive or) meaning that \(P \vee Q\) is in fact true when both \(P\) and \(Q\) are true. As for the other connectives, “and” behaves as you would expect, as does negation. The biconditional (if and only if) might seem a little strange, but you should think of this as saying the two parts of the statements are equivalent in that they have the same truth value. This leaves only the conditional \(P \imp Q\) which has a slightly different meaning in mathematics than it does in ordinary usage. However, implications are so common and useful in mathematics, that we must develop fluency with their use, and as such, they deserve their own subsection.

Easily the most common type of statement in mathematics is the implication. Even statements that do not at first look like they have this form conceal an implication at their heart. Consider the Pythagorean Theorem. Many a college freshman would quote this theorem as “\(a^2 + b^2 = c^2\text{.}\)” This is absolutely not correct. For one thing, that is not a statement since it has three variables in it. Perhaps they imply that this should be true for any values of the variables? So \(1^2 + 5^2 = 2^2\text{???}\) How can we fix this? Well, the equation is true as long as \(a\) and \(b\) are the legs of a right triangle and \(c\) is the hypotenuse. In other words:

This is a reasonable way to think about implications: our claim is that the conclusion (“then” part) is true, but on the assumption that the hypothesis (“if” part) is true. We make no claim about the conclusion in situations when the hypothesis is false.²

Still, it is important to remember that an implication is a statement, and therefore is either true or false. The truth value of the implication is determined by the truth values of its two parts. To agree with the usage above, we say that an implication is true either when the hypothesis is false, or when the conclusion is true. This leaves only one way for an implication to be false: when the hypothesis is true and the conclusion is false.

Just to be clear, although we sometimes read \(P \imp Q\) as “\(P\) implies \(Q\)”, we are not insisting that there is some causal relationship between the statements \(P\) and \(Q\text{.}\) In particular, if you claim that \(P \imp Q\) is false, you are not saying that \(P\) does not imply \(Q\text{,}\) but rather that \(P\) is true and \(Q\) is false.

It is important to understand the conditions under which an implication is true not only to decide whether a mathematical statement is true, but in order to prove that it is. Proofs might seem scary (especially if you have had a bad high school geometry experience) but all we are really doing is explaining (very carefully) why a statement is true. If you understand the truth conditions for an implication, you already have the outline for a proof.

Perhaps a better way to say this is that to prove a statement of the form \(P \imp Q\) directly, you must explain why \(Q\) is true, but you get to assume \(P\) is true first. After all, you only care about whether \(Q\) is true in the case that \(P\) is as well.

There are other techniques to prove statements (implications and others) that we will encounter throughout our studies, and new proof techniques are discovered all the time. Direct proof is the easiest and most elegant style of proof and has the advantage that such a proof often does a great job of explaining why the statement is true.

This sort of argument shows up outside of math as well. If you ever found yourself starting an argument with “hypothetically, let’s assume …,” then you have attempted a direct proof of your desired conclusion.

An implication is a way of expressing a relationship between two statements. It is often interesting to ask whether there are other relationships between the statements. Here we introduce some common language to address this question.

Mathematics is overflowing with examples of true implications which have a false converse. If a number greater than 2 is prime, then that number is odd. However, just because a number is odd does not mean it is prime. If a shape is a square, then it is a rectangle. But it is false that if a shape is a rectangle, then it is a square.

However, sometimes the converse of a true statement is also true. For example, the Pythagorean theorem has a true converse: if \(a^2 + b^2 = c^2\text{,}\) then the triangle with sides \(a\text{,}\) \(b\text{,}\) and \(c\) is a right triangle. Whenever you encounter an implication in mathematics, it is always reasonable to ask whether the converse is true.

The contrapositive, on the other hand, always has the same truth value as its original implication. This can be very helpful in deciding whether an implication is true: often it is easier to analyze the contrapositive.

Understanding converses and contrapositives can help understand implications and their truth values:

As we said above, an implication is not logically equivalent to its converse, but it is possible that both the implication and its converse are true. In this case, when both \(P \imp Q\) and \(Q \imp P\) are true, we say that \(P\) and \(Q\) are equivalent and write \(P \iff Q\text{.}\) This is the biconditional we mentioned earlier.

You can think of “if and only if” statements as having two parts: an implication and its converse. We might say one is the “if” part, and the other is the “only if” part. We also sometimes say that “if and only if” statements have two directions: a forward direction \((P \imp Q)\) and a backwards direction (\(P \leftarrow Q\text{,}\) which is really just sloppy notation for \(Q \imp P\)).

Let’s think a little about which part is which. Is \(P \imp Q\) the “if” part or the “only if” part? Consider an example.

It is not terribly important to know which part is the “if” or “only if” part, but this does illustrate something very, very important: there are many ways to state an implication!

Hopefully you agree with the above example. We include the “necessary and sufficient” versions because those are common when discussing mathematics. In fact, let’s agree once and for all what they mean.

To be honest, I have trouble with these if I’m not very careful. I find it helps to keep a standard example for reference.

Thinking about the necessity and sufficiency of conditions can also help when writing proofs and justifying conclusions. If you want to establish some mathematical fact, it is helpful to think what other facts would be enough (be sufficient) to prove your fact. If you have an assumption, think about what must also be necessary if that hypothesis is true.