User:Prime.mover/Proof Structures

From ProofWiki
Jump to: navigation, search

Ordinary proofs

\(\displaystyle \) \(=\) \(\displaystyle \) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(=\) \(\displaystyle \) $\quad$ $\quad$

...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 ...\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \frac {\d u} {\d x}\) \(=\) \(\displaystyle ...\) $\quad$ link to rule $\quad$


and let:

\(\displaystyle \frac {\d v} {\d x}\) \(=\) \(\displaystyle ...\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle v\) \(=\) \(\displaystyle ...\) $\quad$ link to rule $\quad$


Then:

\(\displaystyle \int ...\) \(=\) \(\displaystyle \int u \rd v\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({u}\right) \left({v}\right) - \int \left({v}\right) \left({\frac {\d u} {\d x} }\right) \rd x + C\) $\quad$ Integration by Parts $\quad$
\(\displaystyle \) \(=\) \(\displaystyle ...\) $\quad$ etc $\quad$

$\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 \) $\quad$ Definition of $d$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 0\) $\quad$ as ... fulfils axiom $M1$ $\quad$

So axiom $M1$ holds for $d$.

$\Box$


Proof of $M2$

\(\displaystyle \map d {x, y} + \map d {y, z}\) \(=\) \(\displaystyle \) $\quad$ Definition of $d$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \) $\quad$ $\quad$
\(\displaystyle \) \(\ge\) \(\displaystyle \) $\quad$ as ... fulfils axiom $M2$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \map d {x, z}\) $\quad$ Definition of $d$ $\quad$

So axiom $M2$ holds for $d$.

$\Box$


Proof of $M3$

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

So axiom $M3$ holds for $d$.

$\Box$


Proof of $M4$

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

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 $\left \langle{U_i}\right \rangle_{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 $\left \langle{U_i}\right \rangle_{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 * \left({h * s}\right)\) \(=\) \(\displaystyle ...\) $\quad$ by definition of $*$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({g \circ h}\right) * s\) $\quad$ by definition of $*$ $\quad$

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


Then:

\(\displaystyle e * s\) \(=\) \(\displaystyle ...\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle s\) $\quad$ ... $\quad$

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 \) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(=\) \(\displaystyle \) $\quad$ $\quad$

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


Therefore:

$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 \) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(=\) \(\displaystyle \) $\quad$ $\quad$

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 \) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(=\) \(\displaystyle \) $\quad$ $\quad$

So $k \in S \implies k + 1 \in S$ and the result follows by the Principle of 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.