# User:Lord Farin/Proof Structures

## Contents

# Induction

## Proof by Mathematical Induction (type 1 - 'Normal' Induction)

The proof proceeds by induction on $n$, the *describe the integer $n$*.

### Basis for the Induction

The case $n = n_0$ is verified as follows:

*Reasoning for $n_0$*

This is the basis for the induction.

### Induction Hypothesis

Fix $n \in \N$ with $n \ge n_0$.

Assume *to-be-proved property* holds for $n$.

This is our induction hypothesis.

### Induction Step

This is our induction step:

*Insert reasoning. Whenever the induction hypothesis is used, write down explicitly that this is done.*

*When desired, use the reference* induction hypothesis.

We conclude *to-be-proved property* holds for $n+1$.

The result follows by the Principle of Mathematical Induction.

$\blacksquare$

## Proof by Mathematical Induction (type 2 - Complete Induction)

The proof proceeds by induction on $n$, the *describe the integer $n$*.

### Basis for the Induction

The case $n = n_0$ is verified as follows:

*Reasoning for $n_0$*

This is the basis for the induction.

### Induction Hypothesis

Fix $n \in \N$ with $n \ge n_0$.

Assume *to-be-proved property* holds for all $k$ such that $n_0 \le k \le n$.

This is our induction hypothesis.

### Induction Step

This is our induction step:

*Insert reasoning. Whenever the induction hypothesis is used, write down explicitly that this is done.*

*When desired, use the reference* induction hypothesis.

We conclude *to-be-proved property* holds for $n+1$.

The result follows by the Second Principle of Mathematical Induction.

$\blacksquare$

## Notes to Induction Proofs

The above are only guidelines. In most cases, a different formulation is natural. Just use this as a template, so as to structure all induction proofs uniformly. Some proofs require induction to multiple variables. I haven't encountered such proofs on PW; when I do, I will put up a proof template.

# Set Equality

Let $A$ be *describe the set $A$*.

Let $B$ be *describe the set $B$*.

Then $A = B$.

## Proof of Set Equality (type 1 - Direct)

By definition of set equality, it suffices to prove $A \subseteq B$ and $B \subseteq A$.

### $A$ is contained in $B$

Suppose that $x \in A$.

*Insert reasoning*

Hence $x \in B$. It follows that $A \subseteq B$.

$\Box$

### $B$ is contained in $A$

Suppose now that $x \in B$.

*Insert reasoning*

Hence $x \in A$. It follows that $B \subseteq A$.

$\Box$

Therefore, we have established that $x \in B \iff x \in A$.

From the definition of set equality, it follows that $A = B$.

$\blacksquare$

## Proof of Set Equality (type 2 - Indirect)

By [definition of set equality, it suffices to prove $A \subseteq B$ and $B \subseteq A$.

From Set Complement inverts Subsets, have:

- $\complement \left({A}\right) \subseteq \complement \left({B}\right) \iff B \subseteq A$

Therefore, it suffices to prove $A \subseteq B$ and $\complement \left({A}\right) \subseteq \complement \left({B}\right)$.

### $A$ is contained in $B$

Suppose that $x \in A$.

*Insert reasoning*

Hence $x \in B$. It follows that $A \subseteq B$.

$\Box$

### $\complement \left({A}\right)$ is contained in $\complement \left({B}\right)$

Suppose now that $x \notin A$.

*Insert reasoning*

Hence $x \notin B$. It follows that $\complement \left({A}\right) \subseteq \complement \left({B}\right)$.

$\Box$

Therefore, we have established that $x \in B \iff x \in A$.

From the definition of set equality, we conclude that $A = B$.

$\blacksquare$

## Notes to Set Equality Proofs

I am pretty sure no convention on this type of proof exists. Encountering some of these scattered around, I figured I'd give it a shot.

# Iff

*statement 1* $\iff$/iff *statement 2*

## Iff Proof (type 1 - direct)

### Necessary Condition

Suppose *statement 1*.

*Insert reasoning*

Hence *statement 2*.

$\Box$

### Sufficient Condition

Suppose *statement 2*.

*Insert reasoning*

Hence *statement 1*.

$\blacksquare$

## Iff Proof (type 2 - indirect)

From Rule of Transposition, we may replace the *if / $\impliedby$* statement by its contrapositive.

Therefore, the following suffices:

### Implication

Suppose *statement 1*.

*Insert reasoning*

Hence *statement 2*.

$\Box$

### Contrapositive Implication

Suppose *negation statement 1*.

*Insert reasoning*

Hence *negation statement 2*.

$\blacksquare$

## Notes to Iff Proofs

A third (also indirect) type is obtained by exchanging *statement 1* and *statement 2*.

Be advised that I mixed up necessary and sufficient conditions in type 1. This has now been fixed. Lord_Farin 07:09, 7 November 2011 (CST)

# General Notes

For further proof templates, cf. User:Prime.mover/Proof Structures.