# User:Prime.mover/Proof Structures

## 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$

## 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:

## 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.