Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
The Book of
Foundational Mathematics
1 Propositional Logic
2 Arguments and Proof
- The Structure of Basic Arguments
- Rules of Inference
- Using the Rules of Inference
- Logically Equivalent Arguments
- Invalid Arguments
- Universal Specification
- Universal Generalization
- Axioms, Definitions, Theorems, and Proofs
- Proof Technique: Direct Proofs
- Proof Technique: Indirect Proofs
- Proof Technique: Contradiction
- Mistakes in Proofs
- Proof Technique: Equivalence
4 Relations and Functions
Appendix
Propositions
Often when dealing with problems in mathematics, we make use of certain facts. For example, when dealing with geometry problems in the plane, we often make use of the Pythagorean Theorem and the Angle Bisector Theorem. When dealing with quadratic equations, we can use the Quadratic Formula to calculate the roots. The Fundamental Theorem of Calculus gives us a way to relate integrals to derivatives, and gives us a way to evaluate definite integrals.
But how do we know that the Pythagorean Theorem or the Angle Bisector Theorem are true? How do we know that the Quadratic Formula gives us the roots of the associated quadratic equation, and not some unrelated pair of numbers? We could of course ask the same thing of the Fundamental Theorem of Calculus.
The answer is that, starting from some underlying collection of assumptions, mathematicians use a system of logic to arrive at these conclusions. These assumptions and resulting conclusions are stated in the form of sentences that are either true or false. We can develop a system to work with these kinds of sentences in a way that allows these sentences to be strung together in a valid argument. These valid arguments are the reason why we are able to use various facts when solving problems.
Primitive Statements
The types of sentences described previously (those sentences that state something that is true or false, but not both) are called declarative and they form the building blocks of mathematical logic.
Proposition
A proposition is a declarative sentence; that is, a proposition is a sentence that is either true or false, but not both.
Sometimes, the word statement is used.
Often, just as in algebra, we can identify a proposition using a symbol. Typically, this symbol will be a lowercase letter from the alphabet.
Example 1.1.1
Consider the following propositions:
| h: | Hank helps manage a propane store. |
| t: | Mr. T was a mathematics major. |
| p: | Thomas Jefferson was the second president of the United States. |
| x: | 2 + 2 = 4 and 2 + 3 = 6. |
These are all sentences that are either true or false (but not both.) Here, propositions h and t are both true, while propositions p and x are false. Notice that we could break proposition x up into two simpler propositions.
| x1: | 2 + 2 = 4. |
| x2: | 2 + 3 = 6. |
Here, x1 is a true proposition, but x2 is a false proposition. Next, consider the following sentences.
| What time is it? |
| Are you hungry? |
| Make sure to file your taxes before April 15. |
| What a beautiful painting! |
These sentences can’t be described as either true or false, so they are not propositions. The second sentence could easily be re-worded to become a proposition though. For example, the sentence “You are hungry.” can be described as either true or false.
Compound Propositions
Looking back at Example 1.1.1, we see that proposition x is made up of two propositions connected together using the connective word and. When a sentence is made up of propositions joined together by connective words, the truth value of the entire sentence will depend on the truth value of its constituent parts.
Common connective words and phrases include the following:
- and
- or
- if
- if…then
- only if
- if and only if
- necessary
- sufficient
Figure 1.1.1: The words and phrases listed above are very commonly used to denote logical connectives between propositions in text.
Compound Proposition, Primitive Proposition
A compound proposition is a proposition made up of other propositions that are joined together with connectives such as and, or, and if then.
A primitive proposition is a proposition that is not made up of other propositions; in other words, it can’t be broken up into smaller constituent propositions.
Compound propositions are sometimes called non-primitive.
Example 1.1.2
Consider the compound proposition
Al sells women’s shoes, and Peggy is a housewife.
This proposition is made up of the two primitive propositions
Al sells women’s shoes,
and
Peggy is a housewife.
These two propositions are joined together by the connective word and.
Logical Connectives
Compound propositions are formed by joining primitive propositions together with connective words. This allows us to express more complicated and intricate ideas. We start with a very simple transformation.
Negation
Let p be any proposition (primitive or non-primitive.)
The negation of p, denoted ¬p, is the proposition “Not p” or “It is not the case that p.”
The proposition ¬p is true whenever the proposition p is false.
Negations of primitive statements are not themselves considered primitive statements. Negation can be applied to primitive and non-primitive propositions alike.
Conjunction, Disjunction
Let p and q be any two propositions (primitive or non-primitive.)
The conjunction of propositions p and q, denoted p ∧ q, is the proposition “p and q.” The proposition p ∧ q is true only when both p and q are true. p ∧ q is false otherwise.
The disjunction of propositions p and q, denoted p ∨ q, is the proposition “p or q, or both.” The proposition p ∨ q is true when p is true, q is true, or both p and q are true.
Notice that when we talk about the disjunction, we are using the inclusive or. This is the commonly used form of the word or in mathematics, so unless otherwise stated, assume or is being used in the inclusive sense.
Exclusive-or
Let p and q be any two propositions (primitive or non-primitive.)
The exclusive-or of the statements p and q, denoted p ⊻ q, is the proposition “p or q, but not both.” The proposition p ⊻ q is true when p is true and q is false, or when p is false and q is true. p ⊻ q is false when both p and q are false, or when both p and q are true.
Example 1.1.3
Consider the following propositions:
| p: | Angus practices musical scales on the guitar |
| q: | Angus becomes the lead guitarist of a rock’n’roll band |
We can translate p ∧ q as
Angus practices musical scales on the guitar, and Angus becomes the lead guitarist of a rock’n’roll band.
(¬p) ∨ q can be translated to
Angus does not practice musical scales on the guitar, or Angus becomes the lead guitarist of a rock’n’roll band.
¬(p ∧ q) can be translated to
It is not the case that Angus practices musical scales on the guitar and he becomes lead guitarist for a rock’n’roll band.
¬(p) ∧ ¬(q) can be translated to
Angus does not become the lead guitarist for a rock’n’roll band, and Angus does not practice musical scales on the guitar.
p ⊻ ¬q can be translated to
Either Angus practices musical scales on the guitar, or he does not become the lead guitarist of a rock’n’roll band, but not both.
The last important types of compound statements we’ll talk about are those that describe the way theorems are stated: conditional statements.
Implication, Hypothesis, Conclusion
Let p and q be any two propositions (primitive or non-primitive.)
The implication, or conditional statement, denoted p → q, is the proposition “if p, then q.” The proposition p → q is false when p is true and q is false. It is true otherwise.
Here, p is called the hypothesis and q is called the conclusion of the implication.
There are alternate ways to describe an implication of the form p → q, and they are given here:
- “If p, then q.”
- “p only if q.”
- “p is a sufficient condition for q.”
- “p is sufficient for q.”
- “q is a necessary condition for p.”
- “q is necessary for p.”
The “necessary” and “sufficient” parts can be a little confusing to understand at first. Just remember what information we’re trying to convey. When we say p → q, this means that the occurrence of p implies the occurrence of q. This is why we say p is sufficient for q: if we know p occurred, then we know that q occurred as well because we are asserting that p → q.
Additionally, when we say p → q, this means that if we don’t have q (in other words, we have ¬q,) then we know p could not have happened (otherwise, we would have q and not ¬q.) This is why p → q can be restated as “q is necessary for p.” Notice though that just saying q is necessary for p is not enough to imply the occurrence of p if we know that q occurred. Knowing q occurred is necessary to knowing that p occurred, but it is not enough to say with certainty that p occurred.
Biconditional
Let p and q be any two propositions (primitive or non-primitive.)
The biconditional of statements p and q, denoted p ↔ q, is the proposition “p if and only if q.” The proposition is true when both p and q are false, or when both p and q are true. It is false otherwise.
From here, we are able to construct more elaborate and intricate propositions as the next example shows.
Consider the propositions p and q:
| Negation: | ¬p |
| Conjunction: | p ∧ q |
| Disjunction: | p ∨ q |
| Exclusive-or: | p ⊻ q |
| Implication: | p → q |
| Biconditional: | p ↔ q |
Figure 1.1.2: We use the symbols above to concisely denote special combinations of proposition. Note that p and q do not need to be primitive.
Example 1.1.5
Consider the following primitive propositions.
| d: | Dennis takes his R.C. boat out to the lake. |
| s: | Today is bright and sunny. |
| w: | Mr. Wilson is fishing at the lake. |
The proposition ¬w ∧ s represents the sentence
Mr. Wilson is not fishing at the lake, and today is bright and sunny.
The proposition (¬w ∧ s) → d represents the sentence
If Mr. Wilson is not fishing at the lake, and today is bright and sunny, then Dennis will take his R.C. boat out to the lake.
We can come up with slightly different alterations, such as s → (¬w → d) which represents the sentence
If today is bright and sunny, then if Mr. Wilson is not fishing at the lake, then Dennis will take his R.C. boat out to the lake.
We also have the proposition ¬(d ↔ (s ∧ w)) which represents the sentence
It is not the case that Dennis will take his R.C. boat out to the lake if and only if today is bright and sunny, and Mr. Wilson is fishing at the lake.
Notice that in the definition for implication, the proposition is false when p is true and q is false; in other words, we have that “true → false” is a false proposition. It is true otherwise. This requires special emphasis:
“false → false” is a true proposition
“false → true” is a true proposition
“true → false” is a false proposition
“true → true” is a true proposition
When constructing any mathematical argument, we must use implications that reduce to the form “true → true.” We want to start with true statements, and those true statements should yield more true statements.
The reason why “true → false” is a false proposition is because we don’t want true statements implying false statements in a logical system. True statements should only imply true statements.
Curiously enough, we do consider the implication of a false statement by another false statement to be a true proposition. This is because if we start with a false statement, then the truth of the conclusion is irrelevant.
Trivially True
Implications of the form
false → false
false → true
are called trivially true.
Example 1.1.6
Suppose Angelica wants to buy a new computer. She decides that the easiest way to buy a new computer is to save enough money by working a summer job. The computer she wants to buy costs $2000.
Consider the following propositions.
| a: | Angelica earned $2000 working a summer job. |
| b: | Angelica buys a new computer. |
We want to examine the implication a → b.
Case 1: false → false
Here, Angelica did not earn $2000 working a summer job, and she did not buy a new computer. Because Angelica did not earn $2000 in the first place, Angelica did not go back on her word. So, as far as we can tell, the proposition a → b was still true. This is a trivially true case.
Case 2: false → true
Here, Angelica did not earn $2000 working a summer job, but was still able to purchase the computer she wanted. Perhaps she won the lottery, or got a lot of birthday money. In this case she did not go back on her word because she did not earn the money working a summer job. This is another trivially true case.
Case 3: true → false
In this case, Angelica did earn $2000 working a summer job, but did not buy the computer she wanted. Here, Angelica did go back on her word, because even though she fulfilled the premise, she did not follow through with the conclusion. Thus, the implication a → b was false.
Case 4: true → true
Here, Angelica saved $2000 by working a summer job, and bought the computer she wanted. She kept her word, and fulfilled the goal of buying the computer. This is a true case, but not a trivially true case.
Example 1.1.7
Consider the following propositions:
| a: | George stuffs too much stuff into his wallet |
| b: | George’s wallet will explode |
The sentence “If George stuffs too much stuff into his wallet, then his wallet will explode.” can be symbolically represented as
a → b.
The sentence “If George’s wallet did not explode, then he did not stuff too much stuff into his wallet.” can be symbolically turned into
¬b → ¬a.
The proposition “George will not stuff too much into his wallet if and only if his wallet does not explode.” can be symbolically translated to
¬a ↔ ¬b.