# User:Prime.mover/Proof Structures

## Contents

- 1 Ordinary proofs
- 2 Definition Equivalences
- 3 Integration by Parts
- 4 Iff Proofs
- 5 Partition Proofs
- 6 Metric Space proofs
- 7 Topology Proofs
- 8 Equivalence Proofs
- 9 Ordering Proofs
- 10 Strict Ordering Proofs
- 11 Group Proofs
- 12 Group Action Proofs
- 13 Ring Proofs
- 14 Proof by Mathematical Induction
- 15 Proof by Complete Induction
- 16 Proof by Finite Induction
- 17 Proof by Complete Finite Induction
- 18 Tableau proofs

## Ordinary proofs

\(\displaystyle \) | \(=\) | \(\displaystyle \) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) |

...etc.

## Definition Equivalences

== Theorem == {{TFAE|def = [definiend] }} === [[Definition:[definiend]/Definition 1|Definition 1]] === {{:Definition:[definiend]/Definition 1}} === [[Definition:[definiend]/Definition 2|Definition 2]] === {{:Definition:[definiend]/Definition 2}} == Proof == === $(1)$ implies $(2)$ === Let $...$ be a [[Definition:[definiend]/Definition 1|[definiend] by definition 1]]. Then by definition: : [Definition 1 of definiend] : : Thus $...$ is a [[Definition:[definiend]/Definition 2|[definiend] by definition 2]]. {{qed|lemma}} === $(2)$ implies $(1)$ === Let $...$ be a [[Definition:[definiend]/Definition 2|[definiend] by definition 2]]. Then by definition: : [Definition 2 of definiend] : : : Thus $...$ is a [[Definition:[definiend]/Definition 1|[definiend] by definition 1]]. {{qed}} [[Category:[definiend]]]

## Integration by Parts

With a view to expressing the primitive in the form:

- $\displaystyle \int u \frac {\d v} {\d x} \rd x = u v - \int v \frac {\d u} {\d x} \rd x$

let:

\(\displaystyle u\) | \(=\) | \(\displaystyle ...\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \frac {\d u} {\d x}\) | \(=\) | \(\displaystyle ...\) | link to rule |

and let:

\(\displaystyle \frac {\d v} {\d x}\) | \(=\) | \(\displaystyle ...\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle v\) | \(=\) | \(\displaystyle ...\) | link to rule |

Then:

\(\displaystyle \int ...\) | \(=\) | \(\displaystyle \int u \rd v\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \paren {u} \paren {v} - \int \paren {v} \paren {\frac {\d u} {\d x} } \rd x + C\) | Integration by Parts | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle ...\) | etc |

$\blacksquare$

## Iff Proofs

### Necessary Condition

### Sufficient Condition

## Partition Proofs

Testing each of the criteria for a partition as follows:

### Each element in no more than one component

Thus each element of ... is in no more than one component of ... .

$\Box$

### Each element in at least one component

Thus each element of ... is in at least one component of ... .

$\Box$

### No component is empty

Thus no component of ... is empty.

$\Box$

Thus ... is a partition by definition.

$\blacksquare$

## Metric Space proofs

It is to be demonstrated that $d$ satisfies all the metric space axioms.

### Proof of $M1$

\(\displaystyle \map d {x, x}\) | \(=\) | \(\displaystyle \) | Definition of $d$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle 0\) | as ... fulfils axiom $M1$ |

So axiom $M1$ holds for $d$.

$\Box$

### Proof of $M2$

\(\displaystyle \map d {x, y} + \map d {y, z}\) | \(=\) | \(\displaystyle \) | Definition of $d$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \) | |||||||||||

\(\displaystyle \) | \(\ge\) | \(\displaystyle \) | as ... fulfils axiom $M2$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \map d {x, z}\) | Definition of $d$ |

So axiom $M2$ holds for $d$.

$\Box$

### Proof of $M3$

\(\displaystyle \map d {x, y}\) | \(=\) | \(\displaystyle \) | Definition of $d$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle k \cdot \map d {y, x}\) | as ... fulfils axiom $M3$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \map d {y, x}\) | Definition of $d$ |

So axiom $M3$ holds for $d$.

$\Box$

### Proof of $M4$

\(\displaystyle x\) | \(\ne\) | \(\displaystyle y\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle ... \map d {x, y}\) | \(>\) | \(\displaystyle 0\) | as ... fulfils axiom $M4$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(>\) | \(\displaystyle 0\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \map d {x, y}\) | \(>\) | \(\displaystyle 0\) | Definition of $d$ |

So axiom $M4$ holds for $d$.

$\Box$

Thus $d$ satisfies all the metric space axioms and so is a metric.

$\blacksquare$

## Topology Proofs

Each of the open set axioms is examined in turn:

### $O1$: Union of Open Sets

Let $\family {U_i}_{i \mathop \in I}$ be an indexed family of open sets of $T$.

Let $\displaystyle V = \bigcup_{i \mathop \in I} U_i$ be the union of $\family {U_i}_{i \mathop \in I}$.

Hence $V$ is open by definition.

$\Box$

### $O2$: Intersection of Open Sets

Let $U$ and $V$ be open sets of $T$.

Hence $U \cap V$ is open by definition.

$\Box$

### $O3$: Underlying Set

$\Box$

All the open set axioms are fulfilled, and the result follows.

$\blacksquare$

## Equivalence Proofs

Checking in turn each of the criteria for equivalence:

### Reflexivity

Thus ... is seen to be reflexive.

$\Box$

### Symmetry

Thus ... is seen to be symmetric.

$\Box$

### Transitivity

Thus ... is seen to be transitive.

$\Box$

... has been shown to be reflexive, symmetric and transitive.

Hence by definition it is an equivalence relation.

$\blacksquare$

## Ordering Proofs

Checking in turn each of the criteria for an ordering:

### Reflexivity

So ... has been shown to be reflexive.

$\Box$

### Transitivity

So ... has been shown to be transitive.

$\Box$

### Antisymmetry

So ... has been shown to be antisymmetric.

$\Box$

... has been shown to be reflexive, transitive and antisymmetric.

Hence by definition it is an ordering.

$\blacksquare$

## Strict Ordering Proofs

Checking in turn each of the criteria for a strict ordering:

### Antireflexivity

So ... has been shown to be antireflexive.

$\Box$

### Transitivity

So ... has been shown to be transitive.

$\Box$

### Asymmetry

So ... has been shown to be asymmetric.

$\Box$

... has been shown to be antireflexive, transitive and asymmetric.

Hence by definition it is a strict ordering.

$\blacksquare$

## Group Proofs

Taking the group axioms in turn:

### $G \, 0$: Closure

Thus $...$ and so $...$ is closed.

$\Box$

### $G \, 1$: Associativity

Thus $...$ is associative.

$\Box$

### $G \, 2$: Identity

Thus $...$ is the identity element of $...$.

$\Box$

### $G \, 3$: Inverses

We have that $...$ is the identity element of $\struct {\R, \circ}$.

Thus every element of $...$ has an inverse $...$.

$\Box$

All the group axioms are thus seen to be fulfilled, and so $...$ is a group.

$\blacksquare$

## Group Action Proofs

The group action axioms are investigated in turn.

Let $g, h \in G$ and $s \in S$.

Thus:

\(\displaystyle g * \paren {h * s}\) | \(=\) | \(\displaystyle ...\) | by definition of $*$ |
| |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \paren {g \circ h} * s\) | by definition of $*$ |

demonstrating that group action axiom $GA\,1$ holds.

Then:

\(\displaystyle e * s\) | \(=\) | \(\displaystyle ...\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle s\) | ... |

demonstrating that group action axiom $GA\,2$ holds.

The group action axioms are thus seen to be fulfilled, and so $*$ is a group action.

$\blacksquare$

## Ring Proofs

Taking the ring axioms in turn:

### A: Addition forms a Group

### M0: Closure of Ring Product

### M1: Associativity of Ring Product

### D: Distributivity of Ring Product over Addition

## Proof by Mathematical Induction

The proof proceeds by induction.

For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:

- $proposition_n$

$\map P 0$ is the case:

- $proposition_0$

Thus $\map P 0$ is seen to hold.

### Basis for the Induction

$\map P 1$ is the case:

- $proposition_1$

Thus $\map P 1$ is seen to hold.

This is the basis for the induction.

### Induction Hypothesis

Now it needs to be shown that if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.

So this is the induction hypothesis:

- $proposition_k$

from which it is to be shown that:

- $proposition_{k + 1}$

### Induction Step

This is the induction step:

\(\displaystyle \) | \(=\) | \(\displaystyle \) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) |

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

- $\forall n \in \Z_{\ge 0}: proposition_n$

## Proof by Complete Induction

The proof proceeds by complete induction.

For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:

- $proposition_n$

$\map P 0$ is the case:

- $proposition_0$

Thus $\map P 0$ is seen to hold.

### Basis for the Induction

$\map P 1$ is the case:

- $proposition_1$

Thus $\map P 1$ is seen to hold.

This is the basis for the induction.

### Induction Hypothesis

Now it needs to be shown that if $\map P j$ is true, for all $j$ such that $0 \le j \le k$, then it logically follows that $\map P {k + 1}$ is true.

This is the induction hypothesis:

- $proposition_k$

from which it is to be shown that:

- $proposition_{k + 1}$

### Induction Step

This is the induction step:

\(\displaystyle \) | \(=\) | \(\displaystyle \) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) |

So $\map P k \implies \map P {k + 1}$ and the result follows by the Second Principle of Mathematical Induction.

Therefore:

- $proposition_n$

## Proof by Finite Induction

The proof will proceed by the Principle of Finite Induction on $\Z_{>0}$.

Let $S$ be the set defined as:

- $S := \set {n \in \Z_{>0}: ...}$

That is, $S$ is to be the set of all $n$ such that:

- $...$

### Basis for the Induction

We have that:

(proof that $1 \in S$)

So $1 \in S$.

This is the basis for the induction.

### Induction Hypothesis

It is to be shown that if $k \in S$ where $k \ge 1$, then it follows that $k + 1 \in S$.

This is the induction hypothesis:

- $\text {expression for $k$}$

It is to be demonstrated that it follows that:

- $\text {expression for $k + 1$}$

### Induction Step

This is the induction step:

\(\displaystyle \) | \(=\) | \(\displaystyle \) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) |

So $k \in S \implies k + 1 \in S$ and the result follows by the Principle of Finite Induction:

- $\forall n \in \Z_{>0}: ...$

## Proof by Complete Finite Induction

The proof will proceed by the Principle of Complete Finite Induction on $\Z_{>0}$.

Let $S$ be the set defined as:

- $S := \set {n \in \Z_{>0}: ...}$

That is, $S$ is to be the set of all $n$ such that:

- $...$

### Basis for the Induction

We have that:

(proof that $1 \in S$)

So $1 \in S$.

This is the basis for the induction.

### Induction Hypothesis

It is to be shown that if $j \in S$ for all $j$ such that $0 \le j \le k$, then it follows that $k + 1 \in S$.

This is the induction hypothesis:

- $\forall j \in \Z_{>0}: 1 \le j \le k: \text {expression for $j$}$

It is to be demonstrated that it follows that:

- $\text {expression for $k + 1$}$

### Induction Step

This is the induction step:

\(\displaystyle \) | \(=\) | \(\displaystyle \) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) |

So $\forall j \in S: 0 \le j \le k: j \in S \implies k + 1 \in S$ and the result follows by the Principle of Complete Finite Induction:

- $\forall n \in \Z_{>0}: ...$

## Tableau proofs

Line | Pool | Formula | Rule | Depends upon | Notes | |
---|---|---|---|---|---|---|

<line number> | <line numbers> | $\ldots{}$ | link to ProofWiki entry | <line numbers> | ||

<line number> | <line numbers> | $\ldots{}$ | link to ProofWiki entry | <line numbers> |

...etc.