4. Proofs

4.1 Logical reasoning

Argument: hypotheses followed by conclusion
Hypotheses: a sequence of propositions
Conclusion: a final proposition
Valid argument: the conclusion is true for every truth assignment to the variables that causes all of the hypotheses to be true ($(h_1\wedge h_2\wedge \cdots \wedge h_n)⟹c$ is a tautology)
Invalid argument: not valid argument

Argument:

$$\begin{array}{c}{h}_1\\ h_2\\ ⋮\\ h_n\\ \therefore c\end{array}$$

4.2 Rules of inference with propositions

Rule of inference	Name
$\begin{array}{c}p\\ p\to q\\ \therefore q\end{array}$	Modus ponens
$\begin{array}{c}\neg q\\ p\to q\\ \therefore \neg p\end{array}$	Modus tollens
$\begin{array}{c}p\\ \therefore p\vee q\end{array}$	Addition
$\begin{array}{c}p\wedge q\\ \therefore p\end{array}$	Simplification
$\begin{array}{c}p\\ q\\ \therefore p\wedge q\end{array}$	Conjunction
$\begin{array}{c}p\to q\\ q\to r\\ \therefore p\to r\end{array}$	Hypothetical syllogism
$\begin{array}{c}p\vee q\\ \neg p\\ \therefore q\end{array}$	Disjunctive syllogism
$\begin{array}{c}p\vee q\\ \neg p\vee r\\ \therefore q\vee r\end{array}$	Resolution
Logical proof of an argument: a sequence of steps, each consisting of a proposition and a justification

4.3 Rules of inference with quantifiers

Element: a value that can be plugged in for variable
An arbitrary element of a domain has no special properties other than those shared by all the elements of the domain
A particular element of the domain may have properties that are not shared by all the elements of the domain

NOTE: both arbitrary and particular elements must belong to the domain

The rules existential instantiation and universal instantiation replace a quantified variable with an element of the domain
The rules existential generalization and universal generalization replace an element of the domain with a quantified variable

Rule of Inference	Name
$c$ is an element (arbitrary or particular) $\frac{\forall xP(x)}{\therefore P(c)}$	Universal instantiation
$c$ is an arbitrary element $\frac{P(c)}{\therefore \forall xP(x)}$	Universal generalization
$\frac{\exists xP(x)}{\therefore (c\text{ is a particular element})\wedge P(c)}$	Existential instantiation
$c$ is an element (arbitrary or particular) $\frac{P(c)}{\therefore \exists xP(x)}$	Existential generalization

NOTE: each use of existential instantiation must define a new element with its own name
NOTE: an element defined in a hypothesis is always a particular element
NOTE: different quantifiers bind variables independently, even when the variables have the same name. Existential quantifiers may refer to different elements, while universal quantifiers apply to every element in the domain

4.4 Mathematical definitions

Even: $x=2k$
Odd: $x=2k+1$
where $k\in \mathbb{Z}$
Every integer is either even or odd, but never both

Same parity: both even or both odd
Opposite parity: one even, one odd
The choice of $x$ and $y$ is not unique

Rational: $r=\frac{x}{y}$, where $x,y\in \mathbb{Z}$ and $y\ne 0$.

$x\mid y$: $x$ divides $y$ if and only if $x\ne 0$ and $y=kx$ for some $k\in \mathbb{Z}$
$x\nmid y$: $x$ does not divide $y$
If $x\mid y$, then $y$ is a multiple of $x$, and $x$ is a factor (divisor) of $y$

Prime: $n>1$, with only two positive divisors: $1$ and $n$.
Composite: $n>1$, with some integer divisor $m$ such that $1<m<n$.
Note: $1$ is neither prime nor composite.

Exactly one holds: $x<c$, $x=c$, or $x>c$.
Positive: $x>0$; Negative: $x<0$.
Nonnegative: $x\ge 0$; Nonpositive: $x\le 0$.

4.5 Introduction to proofs

Theorem: a statement can be proven to be true
Proof: a series of steps that follow logically from assumptions or from previously proven statements, with a final step that results in the statement of the theorem being proven
Axiom: a statement assumed to be true

Consecutive integers: if one of the numbers is equal to 1 plus the other number

Universal statements:
Proof by exhaustion: proving the statement by checking each element individually
Counterexample: an assignment of values to variables that shows that a universal statement is false
Counterexamples for conditional statements: hypotheseses are true and conclusion is false

Existential statements:
Existence proof: a proof that shows that an existential statement is true
Constructive proof of existence: a specific example of an element in the domian or a set of directions to construct an element in the domain that has the required proerties
Nonconsecutive proof of existence: proves that an element with the required properties exists without giving a specific example

4.6 Best practices and common errors in proofs

The rules of algebra:
For example, if $x$, $y$, and $z$ are real numbers and $x=y$, then $x+z=y+z$.
The set of integers is closed under addition, multiplication, and subtraction:
In other words, sums, products, and differences of integers are also integers.
Every integer is either even or odd:
This fact is proven elsewhere in the material.
If $x$ is an integer, there is no integer between $x$ and $x+1$:
In particular, there is no integer between $0$ and $1$.
The relative order of any two real numbers:
For example, $\frac{1}{2}<1$ or $4.2\ge 3.7$.
The square of any real number is greater than or equal to $0$:
This fact is proven in a later exercise.
Every real number is positive, negative, or equal to $0$:
That is, for every real number $x$, exactly one of the following expressions is true: $x>0$, $x<0$, or $x=0$.
Algebraic facts about inequalities:
For any real numbers $a$, $b$, and $c$, if $a>b$, then $a+c>b+c$.
For any real numbers $a$, $b$, and $c$, if $a>b$ and $c>0$, then $ac>bc$.
For any real numbers $a$, $b$, and $c$, if $a>b$ and $c<0$, then $ac<bc$.

Thus and therefore:
A statement that follows from the previous statement or previous few statements can be started with “Thus” or “Therefore.”

• $n$ and $m$ are integers. Therefore, $n+m$ is also an integer.
• $n$ is a positive integer. Thus, $n\ge 1$.
  Other words that serve the same purpose are “it follows that,” “then,” “hence”.
  Let:
  New variable names are often introduced with the word “let”. For example, “Let $x$ be a positive integer.”
  Suppose:
  The word “suppose” can also be used to introduce a new variable. For example: “Suppose that $x$ is a positive integer.” Suppose is also used to introduce a new assumption, as in: “Suppose that $x$ is odd,” assuming that $x$ has already been introduced as an integer earlier in the proof.
  Since:
  If a statement depends on a fact that appeared earlier in the proof or in the assumptions of the theorem, remind the reader of that fact before the statement. The phrase “because we know that” serves the same purpose. For example, assuming that the facts $x>0$ and $y>z$ have been established earlier, a proof could say:
• “Since $x>0$ and $y>z$, then $xy>xz$.”
• “Because we know that $x>0$ and $y>z$, then $xy>xz$.”

We will prove … and We will show …:
It is important in mathematical proofs to give readers an indication of where the proof is leading, by saying what will be proven in the upcoming steps of the proof. In the context of a mathematical proof, “showing” a mathematical fact means the same thing as “proving” a mathematical fact.
By definition:
A fact that is known because of a definition can be started with the phrase “By definition”. For example: “The integer $m$ is even. By definition, $m=2k$ for some integer $k$.”
By assumption:
A fact that is known because of an assumption can be started with the phrase “By assumption”. For example: “By assumption, $x$ is positive. Therefore, $x>0$.”
In other words:
Sometimes rephrasing a statement in a more specific way is useful. The phrase “in other words” is useful in this context. For example: “We must show that the average of $x$ and $y$ is positive. In other words, we must show that $\frac{x+y}{2}>0$.”
gives and yields:
Sometimes a proof is clearer if even an algebraic step is justified. The words “gives” and “yields” say that one equation or inequality follows from another.

• Multiplying both sides of the inequality $x>y$ by $2$ gives $2x>2y$.
• Substituting $m=2k$ into $m^2$ yields $(2k{)}^2$.
• Since $z>0$, we can multiply both sides of the inequality $x>y$ by $z$ to get $xz>yz$.

Indicate when the proof starts and ends:
In this material, every proof begins with the word Proof: and ends with the symbol $\square$.
Write proofs in complete sentences:
A proof should read like English text. In mathematical proofs, English sentences often contain mathematical expressions but those should read naturally as part of the sentence. For example: “If $x$ is an integer that is greater than $0$, then $x\ge 1$.”
Give the reader a roadmap of what has been shown, what is assumed, and where the proof is going:
The beginning of a proof should always state what facts are assumed and ideally inform the reader what will be proven in the proof. If a proof is long, it is helpful to indicate at one or more points in the middle what has been proven and what has yet to be proven. For example: “We have shown that $n$ is a positive integer. Now we must establish that $n$ is composite.”
Introduce each variable when the variable is used for the first time:
Here are some examples of the introduction of a new variable:

• “Let $x$ be a positive integer.”
• “Since we know that $m$ divides $n$, there is an integer $k$ such that $n=km$.” This sentence introduces the variable $k$. Variables $m$ and $n$ should already have been introduced.
• “Let $s$ be the average of $x$ and $y$: $s=\frac{x+y}{2}$.” This sentence introduces the variable $s$. Variables $x$ and $y$ should already have been introduced.
  A block of equations should be introduced with English text and each step that does not follow from algebra should be justified:
  In the example below, the facts that $n=k+1$ and $m\ge 0$ should be previously stated assumptions in the proof or previously proven facts:
  Plugging in $n=k+1$ into $n^2$:

$$\begin{array}{rl}{n}^2& =(k+1{)}^2\\ & =k^2+2k+1\\ & \le k^2+2k+1+m,\text{because }m\ge 0.\end{array}$$

If the justification for a step does not fit easily on the line of the equation, the justification can be provided right after the block of equations.

NOTE: each use of existential instantiation must introduce a fresh variable name, but the elements represented by different names are not necessarily distinct

Common mistakes:
Generalizing from examples
Skipping steps
Circular reasoning
Assuming facts that have not yet been proven

4.7 Writing direct proofs

Direct proof of a conditional statement: the hypothesis $p$ is assumed to be true and the conclusion $c$ is proven as da direct result of the assumption

4.8 Proof by contrapositive

1. Original Statement: $(H_1\wedge H_2)\to C$
2. Contrapositive: $\neg C\to \neg (H_1\wedge H_2)$
3. De Morgan’s Law: $\neg C\to (\neg H_1\vee \neg H_2)$
4. Implication Law: $C\vee \neg H_1\vee \neg H_2$
5. De Morgan’s Law: $\neg (\neg C\wedge H_1)\vee \neg H_2$
6. Implication Law: $(\neg C\wedge H_1)\to \neg H_2$

4.9 Proof by contradiction

Proof by contradiction: indirect proof

Proof Pattern	Description
Direct Proof	Assume $p$. Follow a series of steps to conclude $q$.
Proof by Contrapositive	Assume $\neg q$. Follow a series of steps to conclude $\neg p$.
Proof by Contradiction	Assume $p\wedge \neg q$. Follow a series of logical steps to conclude $r\wedge \neg r$ for some proposition $r$.

NOTE: $\neg (P\to Q)\equiv P\wedge \neg Q$

QUESTIONS: definition of rational numbers includes common factor/coprime?
https://learn.zybooks.com/zybook/WISCCOMPSCI240MATH240Fall2026/chapter/4/section/9

Original	Negation
At least one	None
At least two	At most one
More than one	At most one
All	At least one is not

4.10 Proof by cases

Proof by cases of a universal set ($P(x)$): breaks the domain for the variable $x$ into different classes and gives a different proof for each class
Case: the proof fore each class
Every value in the domain must be included in at least one class

Without loss of generality (WLOG): used in mathematical proofs to narrow the scope of a proof to one special case in situations when the proof can be easily adapted to apply to the general case

---

TEMPLATE:
THEOREM:

PROOF.
We proceed by mathematical induction on n. State the assumptions and what will be proven. Use the definition to express the assumption. Substitute, argue, and use definition to make the final proof.
Complete sentences.
Roadmap.
Introduct variables.

BASE CASE:
We first show that P(n₀) holds.
Thus, the base case holds.

INDUCTIVE HYPOTHESIS:
Assume that P(k) holds for some arbitrary integer k ≥ n₀.

INDUCTIVE STEP:
We want to show that P(k+1) holds.
Therefore, P(k+1) holds.

CONCLUSION:
By PMI, P(n) holds for all integers n ≥ n₀. ∎