Discrete Mathematics: An Open Introduction, 3rd edition

Subsection Atomic and Molecular Statements

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 at the end of this section.

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

Telephone numbers in the USA have 10 digits and 42 is a perfect square.

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.¹In computer programing, we should call such variables Boolean variables. 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.

Subsection Implications

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 or a right triangle and \(c\) is the hypotenuse. In other words:

If \(a\) and \(b\) are the legs of a right triangle with hypotenuse \(c\text{,}\) then \(a^2 + b^2 = c^2\text{.}\)

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.²However, note that in the case of the Pythagorean Theorem, it is also the case that if \(a^2 + b^2 = c^2\text{,}\) then \(a\) and \(b\) are the legs of a right triangle with hypotenuse \(c\text{.}\) So we could have also expressed this theorem as a biconditional: “\(a\) and \(b\) are the legs of a right triangle with hypotenuse \(c\) if and only if \(a^2 + b^2 = c^2\text{.}\)”

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.

Subsection Predicates and Quantifiers

It would be nice to use variables in our mathematical sentences. For example, suppose we wanted to claim that if \(n\) is prime, then \(n+7\) is not prime. This looks like an implication. I would like to write something like

where \(P(n)\) means “\(n\) is prime.” But this is not quite right. For one thing, because this sentence has a free variable (that is, a variable that we have not specified anything about), it is not a statement. A sentence that contains variables is called a predicate.

Now, if we plug in a specific value for \(n\text{,}\) we do get a statement. In fact, it turns out that no matter what value we plug in for \(n\text{,}\) we get a true implication in this case. What we really want to say is that for all values of \(n\text{,}\) if \(n\) is prime, then \(n+7\) is not. We need to quantify the variable.

Although there are many types of quantifiers in English (e.g., many, few, most, etc.) in mathematics we, for the most part, stick to two: existential and universal.

As with all mathematical statements, we would like to decide whether quantified statements are true or false. Consider the statement

You would read this, “for every \(x\) there is some \(y\) such that \(y\) is less than \(x\text{.}\)” Is this true? The answer depends on what our domain of discourse is: when we say “for all” \(x\text{,}\) do we mean all positive integers or all real numbers or all elements of some other set? Usually this information is implied. In discrete mathematics, we almost always quantify over the natural numbers, 0, 1, 2, …, so let's take that for our domain of discourse here.

For the statement to be true, we need it to be the case that no matter what natural number we select, there is always some natural number that is strictly smaller. Perhaps we could let \(y\) be \(x-1\text{?}\) But here is the problem: what if \(x = 0\text{?}\) Then \(y = -1\) and that is not a number! (in our domain of discourse). Thus we see that the statement is false because there is a number which is less than or equal to all other numbers. In symbols,

To show that the original statement is false, we proved that the negation was true. Notice how the negation and original statement compare. This is typical.

Essentially, we can pass the negation symbol over a quantifier, but that causes the quantifier to switch type. This should not be surprising: if not everything has a property, then something doesn't have that property. And if there is not something with a property, then everything doesn't have that property.