1. Introduction to Informal Proofs

Formal vs. Informal Proofs

We aim to present a formal deductive system which:

• shows how a conclusion follows from a set of premises via a sequence of well-defined proof steps.
• fully agrees with the semantical concept of logical consequence
• is purely syntactical

Informal proofs

The term “informal” here is used in the sense that we may omit some steps and / or use some “accepted” results or statements in the proof: axioms, theorems, etc

Our interim objective is to relate reasoning patterns in the proofs with known tautologies. We will then formalise the notion of proof, to completely forbid any assumptions outside the set of premises or any steps which are not fully defined at the outset.

Common Proof Patterns

Direct proof

A direct proof involves successive application of valid inference steps to demonstrate that a conclusion follows from a set of assumptions.

Link to original

title: Example 1: Prove $n^2$ is odd if $n$ is odd.
**Assume**: $n$ is even iff $n = 2k$ for some integer $k$;
and $n$ is odd iff $n = 2k + 1$ for some integer $k$
 
**Example**: If $n$ is an odd integer, then $n^2$ is odd.
 
**Proof**: Assume that $n$ is any odd integer, and then show that $n^2$ is odd.
If $n$ is odd, then $n = 2k + 1$ for some integer $k$.
Therefore $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$.
If $k$ is an integer, then $2k^2 + 2k$ is also an integer and hence $n^2$ is odd.

Proof by contradiction

A proof by contradiction is where we show $A \land \neg B$ is a contradiction in order to prove that $A \rightarrow B$.

Link to original

title: Example 2: Prove $A \rightarrow B$ by contradiction.
To prove $A \rightarrow B$, construct a proof of $A \land \neg B \rightarrow 0$.
$$
	\begin{aligned}
		A \land \neg B &\equiv \neg(A \land \neg B) \\
		&\equiv (\neg A \lor B) \\
		&\equiv A \rightarrow B
	\end{aligned}
$$
 
**Example**: If $3n+2$ is odd, then $n$ is odd.
 
**Proof**: Suppose $3n+2$ is odd but $n$ is not odd (i.e. even).
Since $n$ is even, we know that $n = 2k$ for some integer $k$.
Thus, we can expand $3n + 2$ as $3(2k) + 2 = 2(3k + 1)$.
Since $3k + 1$ is an integer, $3n + 2$ can be expressed as $2(3k + 1)$, then $3n + 2$ must be even, and this contradicts out original assumption.
 
Therefore, by contradiction, if $3n+2$ is odd, then $n$ is odd.

Proof by contraposition

A proof by contraposition is where we show $\neg B \rightarrow \neg A$ in order to show that $A \rightarrow B$.

Link to original

title: Example 3: Prove $A \rightarrow B$ by contraposition.
We can show that $\neg B \rightarrow \neg A$.
$$
	\neg B \rightarrow \neg A \equiv A \rightarrow B
$$
 
**Example**: If $3n + 2$ is odd, then $n$ is odd.
 
**Proof**: Suppose that $n$ is not odd (i.e. even), we show that $3n + 2$ is also not odd (i.e. it is even).
 
If $n$ is even, then $n = 2k$, for some integer $k$.
Then $3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)$ which is an even number.

Proof by cases

A proof by cases or proof by exhaustion is a method where we split up the argument into different sub-proofs.

Link to original

title: Example 4: Proof by cases.
To prove $(A_1 \lor A_2 \lor ... \lor A_n) \rightarrow B$, you can show that:
$$
	(A_1 \rightarrow B) \land (A_2 \rightarrow B) \land ... \land (A_n \rightarrow B)
$$
 
**Example**: If $n$ is an integer, then $n^2 \ge n$.
 
**Proof**: Let us divide the set of integers into three classes:
- $0$
- positive numbers
- negative numbers
 
And show that in each case that $n^2 \ge n$.
- If $n = 0$, then $n^2 = 0^2 = 0 \ge 0$.
- If $n \ge 1$, then $(n\cdot n) \ge (1\cdot n)$ and therefore $n^2 \ge n$.
- If $n \le 1$, then again we know that $n^2 > 0$, hence $n^2 \ge n$.
 
In all cases, we show that for all of $n$, $n^2 \ge n$.

Fallacies

We want every step in our proof to be correct, we mean that if we apply a step of the form “from $P$ and $P\to Q$, we can conclude $Q$”, or otherwise:

$$\frac{P,P\to Q}{Q}$$

then the formula $(P\wedge (P\to Q))\to Q$ is a tautology.

Fallacy

A fallacy resembles a correct inference, but it is not valid, leading to incorrect reasoning.

Link to original

Fallacy of affirming the conclusion

Suppose the following argument: “If you do every problem in this book ($P$) then you will learn discrete mathematics ($M$). You learned discrete mathematics ($M$). Therefore, you did every problem in this book ($P$).”

$$P\to M,M\models P\text{ is not valid!}$$

Affirming the consequent of the implication $P\to M$ does not guarantee the truth of its antecedent $P$.

Notice when $v(P)=0$ and $v(M)=1$, all the assumptions of the argument are true but the conclusion is false.

This incorrect reasoning pattern is based on the formula

$$((P\to M)\wedge M)\to P$$

which is not a tautology, only a contingency.

Fallacy of denying the hypothesis

Using the same language, consider the argument: “If you do every problem in this book ($P$) then you will learn discrete mathematics ($M$). You did not do every problem in this book ($\neg P$). Therefore, you did not learn discrete mathematics ($\neg M$).”

$$P\to M,\neg P\models \neg M\text{ is not valid!}$$

Denying the antecedent of the implication $P\to M$ does not guarantee the falsity of its consequent $M$.

Notice that $v(P)=0$ and $v(M)=1$ makes all assumptions true but conclusion false.

This incorrect reasoning pattern is based on the formula

$$((P\to M)\wedge \neg P)\to \neg M$$

which is not a tautology, only a contingency.