Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

## Read the Online Textbook for the full content.

## Section 3.5 Mathematical Systems and Proofs

### Subsection 3.5.1 Mathematical Systems

- This section: overview of what a mathematical system is and how logic plays an important role in one.
- The axiomatic method that we will use here will not be duplicated with as much formality anywhere else in the book, but we hope an emphasis on how mathematical facts are developed and organized will help to unify the concepts we will present.
- The system of propositions and logical operators we have developed will serve as a model for our discussion.

#### Definition 3.5.1. Mathematical System.

A mathematical system consists of:

1. A set or universe, \(U\text{.}\)

2. Definitions: sentences that explain the meaning of concepts that relate to the universe. Any term used in describing the universe itself is said to be undefined. All definitions are given in terms of these undefined concepts of objects.

3. Axioms: assertions about the properties of the universe and rules for creating and justifying more assertions. These rules always include the system of logic that we have developed to this point.

4. Theorems: the additional assertions mentioned above.

#### Example 3.5.2. Euclidean Geometry.

- In Euclidean geometry the universe consists of points and lines (two undefined terms).
- Among the definitions is a definition of parallel lines and among the axioms is the axiom that two distinct parallel lines never meet.

#### Example 3.5.3. Propositional Calculus.

- Propositional calculus is a formal name for the logical system that we've been discussing.
- The universe consists of propositions.
- The axioms: truth tables for the logical operators.
- Definitions: are those of equivalence and implication.
- Propositions are used to describe any other mathematical system; therefore, this is the minimum amount of structure that a mathematical system can have.

#### Definition 3.5.4. Theorem.

A true proposition derived from the axioms of a mathematical system is called a theorem.

Theorems are normally expressed in terms of a finite number of propositions, \(p_1, p_2, . . . ,p_n\) , called the premises, and a proposition,\( \: C\text{,}\) called the conclusion. These theorems take the form

\begin{equation*} p_1\land p_2\land \cdots \land p_n\Rightarrow C \end{equation*}

or more informally,

\begin{equation*} p_1, p_2, . . . , \textrm{ and } p_n \textrm{ imply } C \end{equation*}

- For a theorem of this type: the premises imply the conclusion.
- When a theorem is stated, it is assumed that the axioms of the system are true.
- In addition, any previously proven theorem can be considered an extension of the axioms and can be used in demonstrating that the new theorem is true.
- When the proof is complete, the new theorem can be used to prove subsequent theorems.
- A mathematical system can be visualized as an inverted pyramid with the axioms at the base and the theorems expanding out in various directions.

Figure 3.5.5. The body of knowledge in a mathematical system

#### Definition 3.5.6. Proof.

A proof of a theorem is a finite sequence of logically valid steps that demonstrate that the premises of a theorem imply its conclusion.

- Exactly what constitutes a proof is not always clear.
- Proof complexity may depend on the audience.
- Proofs to famous problems (like the Four-Color Theorem, proved in 1976) involved computers checking different graphs for a property, after mathematicians tried in vain for 100 years.
- Automated theorem proving is a branch of formal reasoning and mathematical logic working on computer programs for proving theorems.

### Subsection 3.5.2 Direct Proof

- Theoretically, you can prove anything in propositional calculus with truth tables.
- The laws of logic stated in Section 3.4 are all theorems.
- Propositional calculus is one of the few mathematical systems for which any valid sentence can be determined true or false by mechanical means.
- A program to write truth tables is not too difficult to write; however, what can be done theoretically is not always practical.
- For example,
  \begin{equation*} a, a\to b, b\to c, . . . ,y\to z\Rightarrow z \end{equation*}

  is a theorem in propositional calculus. However, suppose that you wrote such a program and you had it write the truth table for

  \begin{equation*} (a\land (a\to b)\land ( b\to c)\land \cdots \land (y\to z))\to z \end{equation*}
  The truth table will have \(2^{26}\) cases. At one million cases per second, it would take approximately one hour to verify the theorem.
- Now if you decided to check a similar theorem,
  \begin{equation*} p_1,p_1\to p_2,\ldots ,p_{99}\to p_{100}\Rightarrow p_{100} \end{equation*}
  there would be \(2^{100} \approx 1.26765\times 10^{30}\) cases to check in the truth table. At one million cases per second it would take approximately \(1.46719\times 10^{19}\) days to check all cases.
- For most of the remainder of this section, we will discuss an alternate method for proving theorems in propositional calculus.
- It is the same method that we will use in a less formal way for proofs in other systems.
- Formal axiomatic methods would be too unwieldy to actually use in later sections. However, none of the theorems in later chapters would be stated if they couldn't be proven by the axiomatic method.

We will introduce two types of proof here, direct and indirect.

#### Example 3.5.7. A typical direct proof.

This is a theorem: \(p \rightarrow r, q\rightarrow s,p\lor q\Rightarrow s\lor r\text{.}\) A direct proof of this theorem is:

Table 3.5.8. Direct proof of \(p \rightarrow r, q\rightarrow s,p\lor q\Rightarrow s\lor r\)

Step | Proposition | Justification
1. | \(p \lor q\) | Premise
2. | \(\neg p \rightarrow q\) | (1), conditional rule
3. | \(q \rightarrow s\) | Premise
4. | \(\neg p \rightarrow s\) | (2), (3), chain rule
5. | \(\neg s \rightarrow p\) | (4), contrapositive
6. | \(p \rightarrow r\) | Premise
7. | \(\neg s \rightarrow r\) | (5), (6), chain rule
8. | \(s \lor r\) | (7), conditional rule \(\square\)

Note that \(\square\) marks the end of a proof.

Example 3.5.7 illustrates the usual method of formal proof in a formal mathematical system. The rules governing these proofs are:

1. A proof must end in a finite number of steps.

2. Each step must be either a premise or a proposition that is implied from previous steps using any valid equivalence or implication.

3. For a direct proof, the last step must be the conclusion of the theorem. For an indirect proof (see below), the last step must be a contradiction.

4. Justification Column. The column labeled “justification” is analogous to the comments that appear in most good computer programs. They simply make the proof more readable.

#### Example 3.5.9. Two proofs of the same theorem.

Here are two direct proofs of \(\neg p \lor q, s\lor p, \neg q \Rightarrow s\text{:}\)

Table 3.5.10. Direct proof of \(\neg p \lor q, s\lor p, \neg q \Rightarrow s\)

1. | \(\neg p \lor q\) | Premise
2. | \(\neg q\) | Premise
3. | \(\neg p\) | Disjunctive simplification, (1), (2)
4. | \(s\lor p\) | Premise
5. | \(s\) | Disjunctive simplification, (3), (4). \(\square\)

You are invited to justify the steps in this second proof:

Table 3.5.11. Alternate proof of \(\neg p \lor q, s\lor p, \neg q \Rightarrow s\)

1. | \(\neg p \lor q\)
2. | \(\neg q \rightarrow \neg p\)
3. | \(s\lor p\)
4. | \(p \lor s\)
5. | \(\neg p \to s\)
6. | \(\neg q \rightarrow s\)
7. | \(\neg q\)
8. | \(s\) \(\square\)

- The conclusion of a theorem is often a conditional proposition.
- The condition of the conclusion can be included as a premise in the proof of the theorem.
- The object of the proof is then to prove the consequence of the conclusion.
- This rule is justified by the logical law

\begin{equation*} p \rightarrow (h \rightarrow c) \Leftrightarrow (p \land h) \rightarrow c \end{equation*}

#### Example 3.5.12. Example of a proof with a conditional conclusion.

The following proof of \(p \to (q \rightarrow s), \neg r \lor p, q \Rightarrow r \rightarrow s\) includes \(r\) as a fourth premise. Inference of truth of \(s\) completes the proof.

Table 3.5.13. Proof of a theorem with a conditional conclusion.

1. | \(\neg r \lor p\) | Premise
2. | \(r\) | Added premise
3. | \(p\) | (1), (2), disjunction simplification
4. | \(p \rightarrow (q \to s)\) | Premise
5. | \(q\rightarrow s\) | (3), (4), detachment
6. | \(q\) | Premise
7. | \(s\) | (5), (6), detachment. \(\square\)

### Subsection 3.5.3 Indirect Proof

- Consider a theorem \(P\Rightarrow C\text{,}\) where \(P\) represents \(p_1, p_2, . . . , \textrm{ and } p_n\text{,}\) the premises.
- The method of indirect proof is based on the equivalence \(P\rightarrow C\Leftrightarrow \neg (P\land \neg C)\text{.}\)
- This logical law states that if \(P \Rightarrow C\text{,}\) then \(P \land \neg C\) is always false; that is, \(P \land \neg C\) is a contradiction.
- This means that a valid method of proof is to negate the conclusion of a theorem and add this negation to the premises.
- If a contradiction can be implied from this set of propositions, the proof is complete. For the proofs in this section, a contradiction will often take the form \(t \land \neg t\text{.}\)

For proofs involving numbers, a contradiction might be \(1 = 0\) or \(0 < 0\text{.}\) Indirect proofs involving sets might conclude with \(x \in \emptyset\) or (\(x \in A\) and \(x \in A^c\)). Indirect proofs are often more convenient than direct proofs in certain situations. Indirect proofs are often called proofs by contradiction.

#### Example 3.5.14. An Indirect Proof.

Here is an example of an indirect proof of the theorem in Example 3.5.7.

Table 3.5.15. An Indirect proof of \(p \rightarrow r, q\rightarrow s,p\lor q\Rightarrow s\lor r\)

1. | \(\neg (s \lor r)\) | Negated conclusion
2. | \(\neg s \land \neg r\) | DeMorgan's Law, (1)
3. | \(\neg s\) | Conjunctive simplification, (2)
4. | \(q\to s\) | Premise
5. | \(\neg q\) | Indirect reasoning, (3), (4)
6. | \(\neg r\) | Conjunctive simplification, (2)
7. | \(p \rightarrow r\) | Premise
8. | \(\neg p\) | Indirect reasoning, (6), (7)
9. | \((\neg p) \land (\neg q)\) | Conjunctive, (5), (8)
10. | \(\neg (p \lor q)\) | DeMorgan's Law, (9)
11. | \(p \lor q\) | Premise
12. | \(0\) | (10), (11) \(\square\)

#### Note 3.5.16. Proof Style.

The rules allow you to list the premises of a theorem immediately; however, a proof is much easier to follow if the premises are only listed when they are needed.

#### Example 3.5.17. Yet Another Indirect Proof.

Here is an indirect proof of \(a \rightarrow b, \neg (b \lor c ) \Rightarrow \neg a\text{.}\)

Table 3.5.18. Indirect proof of \(a \rightarrow b, \neg (b \lor c ) \Rightarrow \neg a\)

1. | \(a\) | Negation of the conclusion
2. | \(a\to b\) | Premise
3. | \(b\) | (1), (2), detachment
4. | \(b \lor c\) | (3), disjunctive addition
5. | \(\neg (b \lor c)\) | Premise
6. | \(0\) | (4), (5) \(\square\)

### Exercises 3.5.4 Exercises

#### 1.

Prove with truth tables:

1. \(\displaystyle p\lor q, \neg q\Rightarrow p\)

2. \(\displaystyle p \rightarrow q, \neg q \Rightarrow \neg p\)

Answer.

1. \begin{equation*} \begin{array}{cccc} p & q & (p\lor q)\land \neg q & ((p\lor q)\land \neg q)\to p \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ \end{array} \end{equation*}
2. \begin{equation*} \begin{array}{ccccc} p & q & (p\to q)\land \neg q & \neg p & (p\to q)\land (\neg q) \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ \end{array} \end{equation*}

#### 2.

Prove with truth tables:

1. \(\displaystyle q, \neg q\Rightarrow p\)

2. \(\displaystyle p \rightarrow q \Rightarrow \neg p \lor q\)

#### 3.

Give direct and indirect proofs of:

1. \(a \rightarrow b, c \rightarrow b, d\rightarrow (a \lor c), d\Rightarrow b\text{.}\)

2. \((p\to q) \land (r\to s), (q\rightarrow t) \land (s \to u), \neg (t \land u), p \rightarrow r \Rightarrow \neg p\text{.}\)

3. \(p\to (q\to r),\neg s \lor p,q\Rightarrow s\to r\text{.}\)

4. \(p\rightarrow q, q\rightarrow r, \neg (p \land r), p \lor r \Rightarrow r\text{.}\)

5. \(\displaystyle \neg q, p\to q, p\lor t \Rightarrow t\)

Answer.

1. Direct proof:

   1. \(\displaystyle d\to (a\lor c)\)

   2. \(\displaystyle d\)

   3. \(\displaystyle a\lor c\)

   4. \(\displaystyle a\to b\)

   5. \(\displaystyle \neg a \lor b\)

   6. \(\displaystyle c\to b\)

   7. \(\displaystyle \neg c\lor b\)

   8. \(\displaystyle (\neg a\lor b)\land (\neg c\lor b)\)

   9. \(\displaystyle (\neg a\land \neg c) \lor b\)

   10. \(\displaystyle \neg (a\lor c)\lor b\)

   11. \(b\) \(\square\)

   Indirect proof:

   1. \(\neg b\quad \) Negated conclusion

   2. \(a\to b\quad \) Premise

   3. \(\neg a\quad \) Indirect Reasoning (1), (2)

   4. \(c\to b\quad \) Premise

   5. \(\neg c\quad \) Indirect Reasoning (1), (4)

   6. \((\neg a\land \neg c)\quad \) Conjunctive (3), (5)

   7. \(\neg (a\lor c)\quad \) DeMorgan's law (6)

   8. \(d\to (a\lor c)\quad \) Premise

   9. \(\neg d\quad \) Indirect Reasoning (7), (8)

   10. \(d\quad \) Premise

   11. \(\mathbb{0} \quad \) (9), (10) \(\quad \square\)

2. Direct proof:

   1. \(\displaystyle (p\to q)\land (r\to s)\)

   2. \(\displaystyle p\to q\)

   3. \(\displaystyle (p\to t)\land (s\to u)\)

   4. \(\displaystyle q\to t\)

   5. \(\displaystyle p\to t\)

   6. \(\displaystyle r\to s\)

   7. \(\displaystyle s\to u\)

   8. \(\displaystyle r\to u\)

   9. \(\displaystyle p\to r\)

   10. \(\displaystyle p\to u\)

   11. \(p\to (t\land u)\) Use \((x\to y)\land (x\to z)\Leftrightarrow x\to (y\land z)\)

   12. \(\displaystyle \neg (t\land u)\to \neg p\)

   13. \(\displaystyle \neg (t\land u)\)

   14. \(\neg p\) \(\quad \square\)

   Indirect proof:

   1. \(\displaystyle p\)

   2. \(\displaystyle p\to q\)

   3. \(\displaystyle q\)

   4. \(\displaystyle q\to t\)

   5. \(\displaystyle t\)

   6. \(\displaystyle \neg (t\land u)\)

   7. \(\displaystyle \neg t\lor \neg u\)

   8. \(\displaystyle \neg u\)

   9. \(\displaystyle s\to u\)

   10. \(\displaystyle \neg s\)

   11. \(\displaystyle r\to s\)

   12. \(\displaystyle \neg r\)

   13. \(\displaystyle p\to r\)

   14. \(\displaystyle r\)

   15. \(0\) \(\quad \square\)

3. Direct proof:

   1. \(\neg s\lor p\quad \) Premise

   2. \(s\quad \) Added premise (conditional conclusion)

   3. \(\neg (\neg s)\quad \) Involution (2)

   4. \(p \quad \) Disjunctive simplification (1), (3)

   5. \(p\to (q\to r)\quad \) Premise

   6. \(q\to r\quad \) Detachment (4), (5)

   7. \(q \quad\) Premise

   8. \(r\quad \) Detachment (6), (7) \(\square\)

   Indirect proof:

   1. \(\neg (s\to r)\quad \) Negated conclusion

   2. \(\neg (\neg s\lor r)\quad \) Conditional equivalence (I)

   3. \(s\land \neg r\quad \) DeMorgan (2)

   4. \(s\quad\) Conjunctive simplification (3)

   5. \(\neg s\lor p\quad \) Premise

   6. \(s\to p\quad\) Conditional equivalence (5)

   7. \(p \quad\) Detachment (4), (6)

   8. \(p\to (q\to r)\quad\) Premise

   9. \(q\to r \quad\) Detachment (7), (8)

   10. \(q\quad \) Premise

   11. \(r\quad\) Detachment (9), (10)

   12. \(\neg r \quad\) Conjunctive simplification (3)

   13. \(0 \quad\) Conjunction (11), (12) \(\square\)

4. Direct proof:

   1. \(\displaystyle p\to q\)

   2. \(\displaystyle q\to r\)

   3. \(\displaystyle p\to r\)

   4. \(\displaystyle p\lor r\)

   5. \(\displaystyle \neg p\lor r\)

   6. \(\displaystyle (p\lor r)\land (\neg p\lor r)\)

   7. \(\displaystyle (p\land \neg p)\lor r\)

   8. \(\displaystyle 0\lor r\)

   9. \(r\)\(\square\)

   Indirect proof:

   1. \(\neg rv\) Negated conclusion

   2. \(p\lor r\quad\) Premise

   3. \(p\quad\) (1), (2)

   4. \(p\to q\quad\) Premise

   5. \(q \quad \) Detachment (3), (4)

   6. \(q\to r\quad\) Premise

   7. \(r \quad \)Detachment (5), (6)

   8. \(0 \quad\) (1), (7) \(\square\)

#### 4.

Give direct and indirect proofs of:

1. \(p\rightarrow q, \neg r\rightarrow \neg q, \neg r \Rightarrow \neg p\text{.}\)

2. \(p\rightarrow \neg q, \neg r\rightarrow q, p \Rightarrow r\text{.}\)

3. \(a \lor b, c \land d, a \rightarrow \neg c \Rightarrow b\text{.}\)

#### 5.

Are the following arguments valid? If they are valid, construct formal proofs; if they aren't valid, explain why not.

1. If wages increase, then there will be inflation. The cost of living will not increase if there is no inflation. Wages will increase. Therefore, the cost of living will increase.

2. If the races are fixed or the casinos are crooked, then the tourist trade will decline. If the tourist trade decreases, then the police will be happy. The police force is never happy. Therefore, the races are not fixed.

Answer.

1. Let \(W\) stand for “Wages will increase,” \(I\) stand for “there will be inflation,” and \(C\) stand for “cost of living will increase.” Therefore the argument is: \(W\to I,\text{ }\neg I\to \neg C,\text{ }W\Rightarrow C\text{.}\) The argument is invalid. The easiest way to see this is through a truth table, which has one case, the seventh, that this false. Let \(x\) be the conjunction of all premises. \(\begin{array}{ccccccccc} W & I & C & \neg I & \neg C & W\to I & \neg I\to \neg C & x & x\to C \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{array}\)

2. Let \(r\) stand for “the races are fixed,” \(c\) stand for “casinos are crooked,” \(t\) stand for “the tourist trade will decline,” and \(p\) stand for “the police will be happy.” Therefore, the argument is:

   \begin{equation*} (r\lor c)\to t, t\to p, \neg p\to \neg r\text{.} \end{equation*}

   The argument is valid. Proof:

   1. \(t\to p\quad \) Premise

   2. \(\neg p\quad \) Premise

   3. \(\neg t\quad \) Indirect Reasoning (1), (2)

   4. \((r\lor c)\to t\quad \) Premise

   5. \(\neg (r\lor c)\quad \) Indirect Reasoning (3), (4)

   6. \((\neg r)\land (\neg c)\quad \) DeMorgan (5)

   7. \(\neg r\quad \) Conjunction simplification \((6)\text{ }\square\)

#### 6.

Determine the validity of the following argument: For students to do well in a discrete mathematics course, it is necessary that they study hard. Students who do well in courses do not skip classes. Students who study hard do well in courses. Therefore students who do well in a discrete mathematics course do not skip class.

#### 7.

Describe how \(p_1,p_1\to p_2,\ldots ,p_{99}\to p_{100}\Rightarrow p_{100}\) could be proved in 199 steps.

Answer.

\(p_1\to p_k\) and \(p_k\to p_{k+1}\) implies \(p_1\to p_{k+1}\text{.}\) It takes two steps to get to \(p_1\to p_{k+1}\) from \(p_1\to p_k\) This means it takes \(2(100-1)\) steps to get to \(p_1\to p_{100}\) (subtract 1 because \(p_1\to p_2\) is stated as a premise). A final step is needed to apply detachment to imply \(p_{100}\)