nyuuzyou/wikis huggingface dataset:
Equivalence of Definitions of Topology

== Theorem ==
=== Definition 1 ===
=== Definition 2 ===
== Proof ==
=== Definition 1 implies Definition 2 ===
Let $\tau$ be a topology on $S$ by definition 1.
$\text O 1$ is the same as $\text O 1'$, so $\text O 1'$ holds for $\tau$.
From General Intersection Property of Topological Space:
:if $\text O 2$ holds, then $\text O 2'$ holds.
Thus $\tau$ is a topology on $S$ by definition 2.
=== Definition 2 implies Definition 1 ===
Let $\tau$ be a topology on $S$ by definition 2.
$\text O 1'$ is the same as $\text O 1$, so $\text O 1$ holds for $\tau$.
$\text O 2'$ states that the intersection of any finite subset of $\tau$ is an element of $\tau$.
This applies when the subset of $\tau$ contains exactly $2$ sets.
Thus $\text O 2$ is a direct consequence of $\text O 2'$.
Also as a consequence of $\text O 2$, it follows that the intersection of an empty subset of $\tau$ is an element of $\tau$.
From Intersection of Empty Set it follows that $S \in \tau$.
So $\text O 3$ is a direct consequence of $\text O 2'$.
Thus all the open set axioms hold.
Thus $\tau$ is a topology on $S$ by definition 1.
== Sources ==
* : Notes: Part $\text I$: Basic Definitions: Section $1$. General Introduction: $1$
Category:Topology
Equivalence of Definitions of Topology Generated by Synthetic Basis

== Theorem ==
Let $S$ be a set.
Let $\BB$ be a synthetic basis on $S$.
=== Definition 1 ===
=== Definition 2 ===
=== Definition 3 ===
== Proof ==
=== Definition 1 iff Definition 2 ===
=== Definition 1 iff Definition 3 ===
Category:Topological Bases
Category:Equivalence of Definitions of Topology Generated by Synthetic Basis
Equivalence of Definitions of Topology Generated by Synthetic Basis/Definition 1 iff Definition 2

== Theorem ==
Let $S$ be a set.
Let $\BB$ be a synthetic basis on $S$.
Let $\tau$ be the topology on $S$ generated by the synthetic basis $\BB$:
:$\ds \tau = \set {\bigcup \AA: \AA \subseteq \BB}$
Then:
:$\ds \forall U \subseteq S: U \in \tau \iff U = \bigcup \set {B \in \BB: B \subseteq U}$
== Proof ==
Trivially, the reverse implication holds, as $\set {B \in \BB: B \subseteq U} \subseteq \BB$.
We now show that the forward implication holds.
Suppose $U \in \tau$.
Then, by definition:
:$\ds \exists \AA \subseteq \BB: U = \bigcup \AA$
By Union is Smallest Superset: General Result:
:$\forall B \in \AA: B \subseteq U$
By definition of subset, it follows that:
:$\AA \subseteq \set {B \in \BB: B \subseteq U}$
From Union of Subset of Family is Subset of Union of Family:
:$\ds U = \bigcup \AA \subseteq \bigcup \set {B \in \BB: B \subseteq U}$
By Union is Smallest Superset: General Result:
:$\ds \bigcup \set {B \in \BB: B \subseteq U} \subseteq U$
By definition of set equality:
:$\ds U = \bigcup \set {B \in \BB: B \subseteq U}$
Category:Equivalence of Definitions of Topology Generated by Synthetic Basis
Equivalence of Definitions of Topology Generated by Synthetic Basis/Definition 1 iff Definition 3

== Theorem ==
Let $S$ be a set.
Let $\BB$ be a synthetic basis on $S$.
Let $\tau$ be the topology on $S$ generated by the synthetic basis $\BB$:
:$\ds \tau = \set {\bigcup \AA: \AA \subseteq \BB}$
Then:
:$\forall U \subseteq S: U \in \tau \iff \forall x \in U: \exists B \in \BB: x \in B \subseteq U$
== Proof ==
From Set is Subset of Union: General Result, the forward implication directly follows.
We now show that the reverse implication holds.
By hypothesis, we have that:
:$\ds U \subseteq \bigcup \set {B \in \BB: B \subseteq U}$
By Union is Smallest Superset: General Result:
:$\ds \bigcup \set {B \in \BB: B \subseteq U} \subseteq U$
By definition of set equality:
:$\ds U = \bigcup \set {B \in \BB: B \subseteq U}$
The result follows.
Category:Equivalence of Definitions of Topology Generated by Synthetic Basis
Equivalence of Definitions of Topology Generated by Synthetic Sub-Basis

== Theorem ==
=== Definition 1 ===
=== Definition 2 ===
== Proof ==
Let $X$ be a set.
Let $\SS \subseteq \powerset X$ be a synthetic sub-basis on $X$.
Let $\BB$ be the synthetic basis on $X$ generated by the synthetic sub-basis $\SS$.
Let $\map \tau \SS$ be the topology on $X$ generated by the synthetic basis $\BB$.
We now show that:
:$(1): \quad$ $\SS \subseteq \map \tau \SS$
:$(2): \quad$ For any topology $\TT$ on $X$, the implication $\SS \subseteq \TT \implies \map \tau \SS \subseteq \TT$ holds.
We have that:
:$\SS \subseteq \BB \subseteq \map \tau \SS$
Hence by transitivity of $\subseteq$:
:$\SS \subseteq \map \tau \SS$
Suppose that $\TT$ is a topology on $X$ such that $\SS \subseteq \TT$.
From General Intersection Property of Topological Space:
:$\BB \subseteq \TT$
By :
:$\map \tau \SS \subseteq \TT$
It follows that $\map \tau \SS$ is the unique topology on $X$ satisfying conditions $(1)$ and $(2)$.
Category:Sub-Bases
Equivalence of Definitions of Topology Induced by Metric

== Theorem ==
=== Definition 1 ===
=== Definition 2 ===
== Proof ==
Let $M = \struct {A, d}$ be a metric space whose metric is $d$.
=== $(1)$ implies $(2)$ ===
Let $T = \struct {A, \tau_d}$ be the topological space of which $\tau_d$ is the topology induced on $M$ by $d$ by definition 1.
Then by definition:
:$\tau_d$ is the set of all open sets of $M$.
Let $U \in \tau_d$.
From definition:
:$\forall y \in U: \exists \epsilon_y \in \R_{>0}: \map {B_{\epsilon_y} } y \subseteq U$
where $\map {B_{\epsilon_y}} y$ is the open $\epsilon$-ball of $y$.
We find these $\epsilon$ for every $y \in U$.
Consider the set $\ds \bigcup_{y \mathop \in U} \map {B_{\epsilon_y} } y$.
From $y \in \map {B_{\epsilon_y} } y \subseteq U$ for each $y$:
:$\ds \bigcup_{y \mathop \in U} \map {B_{\epsilon_y} } y = U$
This shows that any $U \in \tau_d$ is a union of open $\epsilon$-balls in $M$.
So open $\epsilon$-balls in $M$ form a basis for $\tau_d$.
Thus $\tau_d$ is the topology induced on $M$ by $d$ by definition 2.
=== $(2)$ implies $(1)$ ===
Let $T = \struct {A, \tau_d}$ be the topological space of which $\tau_d$ is the topology induced on $M$ by $d$ by definition 2.
Then by definition:
:$\tau$ is the topology generated by the basis consisting of the set of all open $\epsilon$-balls in $M$.
Let $U \in \tau_d$.
Since open $\epsilon$-balls in $M$ form a basis for $\tau_d$, $U$ is a union of open $\epsilon$-balls in $M$.
Hence for each $x \in U$:
:$\exists y \in U: \exists \epsilon \in \R_0: x \in \map {B_\epsilon} y$
By Open Ball is Subset of Open Ball:
:$x \in \map {B_{\epsilon - \map d {x, y} } } x \subseteq \map {B_\epsilon} y \subseteq U$
Therefore $U$ is an open set of $M$.
Thus $\tau_d$ is the topology induced on $M$ by $d$ by definition 1.
Category:Metric Spaces
Equivalence of Definitions of Torus of Arbitrary Dimension

== Theorem ==
=== Definition $1$ ===
=== Definition $2$ ===
== Proof ==
=== Definition $(1)$ implies Definition $(2)$ ===
Let $...$ be a torus of arbitrary dimension by definition $1$.
:
:
Thus $...$ is a torus of arbitrary dimension by definition $2$.
=== Definition $(2)$ implies Definition $(1)$ ===
Let $...$ be a torus of arbitrary dimension by definition $2$.
:
:
:
Thus $...$ is a torus of arbitrary dimension by definition $1$.
Category:Torus of Arbitrary Dimension
Equivalence of Definitions of Total Ordering

== Theorem ==
=== Definition 1 ===
=== Definition 2 ===
== Proof ==
=== Definition 1 implies Definition 2 ===
Let $\RR$ be an ordering which is also connected.
By definition 2 of ordering:
:$\RR \circ \RR = \RR$
:$\RR \cap \RR^{-1} = \Delta_S$
and hence by definition of set equality:
:$(1): \quad \RR \circ \RR \subseteq \RR$
:$(2): \quad \RR \cap \RR^{-1} \subseteq \Delta_S$
By Relation is Connected and Reflexive iff Total, $\RR$ is a total relation.
Thus by Relation is Total iff Union with Inverse is Trivial Relation:
:$(3): \quad \RR \cup \RR^{-1} = S \times S$
Hence $\RR$ is a total ordering by definition 2.
=== Definition 2 implies Definition 1 ===
Let $\RR$ be a relation which fulfils the conditions:
:$(1): \quad \RR \circ \RR \subseteq \RR$
:$(2): \quad \RR \cap \RR^{-1} \subseteq \Delta_S$
:$(3): \quad \RR \cup \RR^{-1} = S \times S$
By definition of transitive relation, we have from $(1)$ that $\RR$ is transitive.
From Relation is Antisymmetric iff Intersection with Inverse is Coreflexive, it follows from $(2)$ that $\RR$ is an antisymmetric relation.
By Relation is Total iff Union with Inverse is Trivial Relation it follows from $(3)$ that $\RR$ is a total relation.
From Relation is Connected and Reflexive iff Total, $\RR$ is both connected and reflexive.
Hence we have that $\RR$ is:
:an ordering by definition 1
and hence:
:a total ordering by definition 1.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.27 \ \text {(b)}$
Category:Total Orderings
Equivalence of Definitions of Total Variation of Real Function on Closed Bounded Interval

== Theorem ==
=== Definition 1 ===
=== Definition 2 ===
== Proof ==
We aim to prove that: 
:$\ds \sup_{P \mathop \in \map X {\closedint a b} } \paren {\map {V_f} {P ; \closedint a b} } = \sup_{\SS \mathop \in \map {\PP_F} {\closedint a b} } \paren {\map {V_f^\ast} {\SS ; \closedint a b} }$
We will prove that: 
:$\ds \sup_{P \mathop \in \map X {\closedint a b} } \paren {\map {V_f} {P ; \closedint a b} } \le \sup_{\SS \mathop \in \map {\PP_F} {\closedint a b} } \paren {\map {V_f^\ast} {\SS ; \closedint a b} }$
and:
:$\ds \sup_{\SS \mathop \in \map {\PP_F} {\closedint a b} } \paren {\map {V_f^\ast} {\SS ; \closedint a b} } \le \sup_{P \mathop \in \map X {\closedint a b} } \paren {\map {V_f} {P ; \closedint a b} }$
Note that:
:$\map X {\closedint a b} \subseteq \map {\PP_F} {\closedint a b}$
Note also that if $\SS$ is a finite subdivision of $\closedint a b$, we have: 
:$\map {V_f} {\SS ; \closedint a b} = \map {V_f^\ast} {\SS ; \closedint a b}$
So, we have: 
:$\set {\map {V_f} {P ; \closedint a b} : P \in \map X {\closedint a b} } \subseteq \set {\map {V_f^\ast} {\SS ; \closedint a b} : \SS \in \map {\PP_F} {\closedint a b} }$
So, from Supremum of Subset we obtain: 
:$\ds \sup_{P \mathop \in \map X {\closedint a b} } \paren {\map {V_f} {P ; \closedint a b} } \le \sup_{\SS \mathop \in \map {\PP_F} {\closedint a b} } \paren {\map {V_f^\ast} {\SS ; \closedint a b} }$
In Equivalence of Definitions of Bounded Variation for Real Function on Closed Bounded Interval, it is shown that for each $\SS \in \map {\PP_F} {\closedint a b}$, there exists a finite subdivision $\SS^\ast \in \map X {\closedint a b}$ such that $\SS \subseteq \SS^\ast$ and: 
:$\map {V_f^\ast} {\SS ; \closedint a b} \le \map {V_f} {\SS^\ast ; \closedint a b}$
which establishes: 
:$\ds \sup_{\SS \mathop \in \map {\PP_F} {\closedint a b} } \paren {\map {V_f^\ast} {\SS ; \closedint a b} } \le \sup_{P \mathop \in \map X {\closedint a b} } \paren {\map {V_f} {P ; \closedint a b} }$
Category:Total Variation of Real Function
Equivalence of Definitions of Totally Bounded Metric Space

== Theorem ==
=== Definition 1 ===
=== Definition 2 ===
== Proof ==
=== Definition 1 implies Definition 2 ===
Let $M$ be totally bounded by definition 1.
That is:
:$\forall \epsilon \in \R_{>0}: \struct {A, d}$ has a finite $\epsilon$-net.
So, let $\epsilon \in \R_{>0}$.
Let $A' = \set {x_0, x_1, \ldots, x_n}$ be such a finite $\epsilon$-net of $A$.
By definition:
:$\ds A \subseteq \bigcup_{x_i \mathop \in A'} \map {B_\epsilon} {x_i}$
Now let $x \in A$, and so:
:$\ds x \in \bigcup_{x_i \mathop \in A'} \map {B_\epsilon} {x_i}$
Thus:
:$\exists i: 0 \le i \le n: x \in \map {B_\epsilon} {x_i}$
and so:
:$\map d {x_i, x} < \epsilon$
But:
:$\ds \inf_{0 \mathop \le i \mathop \le n} \map d {x_i, x} \le \map d {x_i, x}$
Thus it follows that there exist finitely many points $x_0, \dots, x_n \in x$ such that:
:$\ds \inf_{0 \mathop \le i \mathop \le n} \map d {x_i, x} \le \epsilon$
for all $x \in A$.
Thus $M$ is totally bounded by definition 2.
=== Definition 2 implies Definition 1 ===
Let $M$ be totally bounded by definition 2.
That is:
:for every $\epsilon > 0$ there exist finitely many points $x_0, \dots, x_n \in A$ such that $\ds \inf_{0 \mathop \le i \mathop \le n} \map d {x_i, x} \le \epsilon$ for all $x \in A$.
So, let $x \in A$.
Let $\epsilon' = \dfrac \epsilon 2$.
Then by definition $\exists n \in \N: A' = \set {x_0, x_1, \ldots, x_n}$ such that $\forall x \in A: \exists x_i \in A': \map d {x_i, x} \le \epsilon'$.
Hence:
:$x \in \map {B_{\epsilon'} } {x_i}$
where $\map {B_{\epsilon'} } {x_i}$ is the open $\epsilon'$-ball of $x_i$.
So:
:$\ds x \in \bigcup_{x_i \mathop \in A'} \map {B_{\epsilon'} } {x_i}$
and hence:
:$\ds A \subseteq \bigcup_{x_i \mathop \in A'} \map {B_{\epsilon'} } {x_i}$
Thus by definition, $A'$ is a finite $\epsilon'$-net of $A$.
Thus $M$ is totally bounded by definition 1.
Category:Totally Bounded Metric Spaces
Equivalence of Definitions of Totally Pathwise Disconnected Space

== Theorem ==
=== Definition 1 ===
=== Definition 2 ===
== Proof ==
Let $T = \struct {S, \tau}$ be a totally pathwise disconnected space by definition 1.
That is:
:all path components of $T$ are singletons.
By definition of path component, this means there are no two points $x, y \in S$ such that there exists a path between $x$ and $y$.
By definition of path, this means the only paths in $T$ are from a single point to that single point.
That is, that the paths in $T$ are constant mappings.
By definition of path:
:the only continuous mappings from the closed unit interval $\closedint 0 1$ to $T$ are constant mappings.
That is the definition of a totally pathwise disconnected space by definition 2.
Let $T = \struct {S, \tau}$ be a totally pathwise disconnected space by definition 2.
That is:
:the only continuous mappings from the closed unit interval $\closedint 0 1$ to $T$ are constant mappings.
That is, that the paths in $T$ are constant mappings.
That is, the path components are singletons.
That is the definition of a totally pathwise disconnected space by definition 1.
== Sources ==
* : Part $\text I$: Basic Definitions: Section $4$: Connectedness: Disconnectedness
Category:Totally Pathwise Disconnected Spaces
Equivalence of Definitions of Totally Separated Space

== Theorem ==
=== Definition 1 ===
=== Definition 2 ===
== Proof ==
Let $T = \struct {S, \tau}$ be totally separated by definition 1:
:For every $x, y \in S: x \ne y$ there exists a separation $U \mid V$ of $T$ such that $x \in U, y \in V$.
 there exist $x, y \in S$ such that $x \ne y$ such that $x$ and $y$ are in the same quasicomponent of $T$.
Then, by definition of quasicomponent, every separation of $T$ includes a single open set $U \in \tau$ which contains both $x$ and $y$.
But this contradicts our stipulation that there exists a separation $U \mid V$ of $T$ such that $x \in U, y \in V$.
So there exists no quasicomponent of $T$ with more than one element.
That is, $T = \struct {S, \tau}$ is totally separated by definition 2.
Let $T = \struct {S, \tau}$ be totally separated by definition 2:
:Each of its quasicomponents is a singleton set.
 there exist $x, y$ such that there exists no separation $U \mid V$ of $T$ such that $x \in U, y \in V$.
That is, each separation of $T$ contains an open set $U \in \tau$ which contains both $x$ and $y$.
That is, there exists a quasicomponent which contains both $x$ and $y$.
But this contradicts our stipulation that every quasicomponent of $T$ is a singleton.
So for every $x, y \in S: x \ne y$ there exists a separation $U \mid V$ of $T$ such that $x \in U, y \in V$.
That is, $T = \struct {S, \tau}$ is totally separated by definition 1.
== Sources ==
* : Part $\text I$: Basic Definitions: Section $4$: Connectedness: Disconnectedness
Category:Totally Separated Spaces
Equivalence of Definitions of Transitive Closure of Relation

== Theorem ==
=== Smallest Transitive Superset ===
=== Intersection of Transitive Supersets ===
=== Finite Chain ===
=== Union of Compositions ===
== Proof ==
Let $\RR$ be a relation on a set $S$.
First note that by Smallest Element is Unique, once it has been shown that some relation, $\QQ$, is the smallest transitive superset of $\RR$, it is the only such.
Thus we need only prove that each of the other definitions lead to relations with this property.
First we have:
=== Intersection of Transitive Supersets is Smallest Transitive Superset ===
=== The Finite Chain Definition is Equivalent to the Union of Compositions Definition ===
=== Union of Compositions is Smallest Transitive Superset ===
=== Finite Chain Definition gives Smallest Transitive Superset ===
== Also see ==
* Recursive Construction of Transitive Closure
Category:Transitive Closures
Category:Equivalence of Definitions of Transitive Closure of Relation
Equivalence of Definitions of Transitive Closure of Relation/Finite Chain is Smallest

== Theorem ==
Let $S$ be a set or class.
Let $\RR$ be a relation on $S$.
Let $\RR^+$ be the transitive closure of $\RR$ by the finite chain definition.
That is, for $x, y \in S$ let $x \mathrel {\RR^+} y$ for some natural number $n > 0$ there exist $s_0, s_1, \dots, s_n \in S$ such that $s_0 = x$, $s_n = y$, and:
:$\forall k \in \N_n: s_k \mathrel \RR s_{k + 1}$
Then $\RR^+$ is transitive and if $\QQ$ is a transitive relation on $S$ such that $\RR \subseteq \QQ$ then $\RR \subseteq \QQ$.
== Proof ==
==== $\RR^+$ is transitive ====
Let $x, y, z \in S$.
Let $x \mathrel {\RR^+} y$ and $y \mathrel {\RR^+} z$.
Then for some $m, n \in \N_{>0}$ there are $s_0, s_1, \dots, s_m$ and $t_0, t_1, \dots, t_n$ such that $s_0 = x$, $s_m = y$, $t_0 = y$, $t_n = z$, and the following hold:
:$\forall k \in \N_m: s_k \mathrel {\RR^+} s_{k + 1}$
:$\forall k \in \N_n: t_k \mathrel {\RR^+} t_{k + 1}$
Let $\sequence {u_k}_{k \mathop \in \N_{m + n} }$ be defined thus:
:$u_k = \cases {s_k & \text {if $k \le m$} \\ t_{k - m} & \text {if $k > m$} }$
Then clearly $u_k \mathrel {\RR^+} u_{k + 1}$ whenever $k < m$ and whenever $k > m$.
But $u_m = s_m = y = t_0 \mathrel {\RR^+} t_1 = u_{m + 1}$, so this holds also for $k = m$.
Furthermore, $u_0 = s_0 = x$ and $u_{m + n} = t_n = z$.
Therefore $x \mathrel {\RR^+} z$.
As this holds for all such $x$ and $z$, $\RR^+$ is transitive.
==== $\RR^+$ is smallest ====
Let $\QQ$ be any transitive relation on $S$ such that $\RR \subseteq \QQ$.
For any $x, y \in S$ such that $x \mathrel {\RR^+} y$, let $\map d {x, y}$ be the smallest natural number $n > 0$ such that there exist $s_0, s_1, \dots, s_n \in S$ such that $s_0 = x$, $s_n = y$, and:
:$\forall k \in \N_n: s_k \mathrel \RR s_{k + 1}$
Such an $n$ always exists by the definition of $\RR^+$ and the fact that $\N$ is well-ordered by $\le$.
We will show by induction on $n$ that for every $x, y$ such that $x \mathrel {\RR^+} y$ and $\map d {x, y} = n$, $x \mathrel \QQ y$.
This will show that $\RR^+ \subseteq \QQ$.
If $\map d {x, y} = 1$ then $x \mathrel \RR y$, so $x \mathrel \QQ y$.
Suppose that the result holds for $n$.
Let $\map d {x, y} = n + 1$.
Then there exist $s_0, s_1, \dots, s_{n + 1}$ such that $s_0 = x$, $s_{n + 1} = y$, and:
:$\forall k \in \N_{n + 1}: s_k \mathrel \RR s_{k + 1}$
Then dropping the last term:
:$\forall k \in \N_n: s_k \mathrel \RR s_{k + 1}$
so $x \mathrel {\RR^+} s_n$.
It should be clear, then, that $\map d {x, s_n} = n$.
Thus by the inductive hypothesis, $x \mathrel \QQ s_n$.
Since $\RR \subseteq \QQ$, $s_n \mathrel \QQ s_{n + 1} = y$.
Since $x \mathrel \QQ s_n$, $s_n \mathrel \QQ y$, and $\QQ$ is transitive:
:$x \mathrel \QQ y$
As this holds for all such $x$ and $y$:
:$\RR^+ \subseteq \QQ$
Category:Equivalence of Definitions of Transitive Closure of Relation
Equivalence of Definitions of Transitive Closure of Relation/Intersection is Smallest

== Theorem ==
Let $\RR$ be a relation on a set $S$.
Then the intersection of all transitive relations on $S$ that contain $\RR$ is the smallest transitive relation on $S$ that contains $\RR$.
== Proof ==
Category:Equivalence of Definitions of Transitive Closure of Relation
Equivalence of Definitions of Transitive Closure of Relation/Intersection is Smallest/Proof

== Theorem ==
== Proof ==
Note that the trivial relation $\TT = S \times S$ on $S$ contains $\RR$, by the definition of a relation on $S$.
Further, $\TT$ is transitive by Trivial Relation is Equivalence.
Thus there is at least one transitive relation on $S$ that contains $\RR$.
Now define $\RR^+$ as the intersection of all transitive relations on $S$ that contain $\RR$:
:$\ds \RR^+ := \bigcap \set {\RR': \text {$\RR'$ is transitive and $\RR \subseteq \RR'$} }$
By Intersection of Transitive Relations is Transitive, $\RR^+$ is also a transitive relation on $S$.
By Set Intersection Preserves Subsets, it also holds that $\RR \subseteq \RR^+$.
Lastly, by Intersection is Subset, for any transitive relation $\RR'$ containing $\RR$, it must be that $\RR^+ \subseteq \RR'$.
Thus $\RR^+$ is indeed the smallest transitive relation on $S$ containing $\RR$.
Category:Equivalence of Definitions of Transitive Closure of Relation
Equivalence of Definitions of Transitive Closure of Relation/Union of Compositions is Smallest

== Theorem ==
Let $\RR$ be a relation on a set $S$.
Let:
:$\RR^n := \begin {cases} \RR & : n = 0 \\ \RR^{n - 1} \circ \RR & : n > 0 \end {cases}$
where $\circ$ denotes composition of relations.
Finally, let:
:$\ds \RR^+ = \bigcup_{i \mathop \in \N} \RR^i$
Then $\RR^+$ is the smallest transitive relation on $S$ that contains $\RR$.
== Proof ==
==== $\RR^+$ is Transitive ====
By Relation contains Composite with Self iff Transitive, we can prove that $\RR^+$ is transitive by proving the following:
:$\RR^+ \circ \RR^+ \subseteq \RR^+$
Let $\tuple {a, c} \in \RR^+ \circ \RR^+$.
Then:
:$\exists b \in S: \tuple {a, b} \in \RR^+, \tuple {b, c} \in \RR^+$
Thus:
:$\exists n \in \N: \tuple {a, b} \in \RR^n$
:$\exists m \in \N: \tuple {b, c} \in \RR^m$
From Composition of Relations is Associative:
:$\RR^{n + m} = \RR^n \circ \RR^m$
so:
:$\tuple {a, c} \in \RR^{n + m} \subseteq \RR^+$
Since this holds for all $\tuple {a, c} \in \RR^+ \circ \RR^+$:
:$\RR^+ \circ \RR^+ \subseteq \RR^+$
Thus $\RR^+$ is transitive.
==== $\RR^+$ contains $\RR$ ====
$\RR \subseteq \RR^+$ by Set is Subset of Union of Family.
==== $\RR^+$ is Smallest ====
Let $\RR'$ be a transitive relation on $S$ such that $\RR \subseteq \RR'$.
We must show that $\RR^+ \subseteq \RR'$.
Let $\tuple {a, b} \in \RR^+$.
That is:
:$a \mathrel \RR b$
Then:
:$\exists n \in \N: \tuple {a, b} \in \RR^n$
Thus by the definition of composition of relations, there exists $x_{n - 1} \in S$ such that:
:$a \mathrel {\RR^{n - 1} } x_{n - 1} \land x_{n - 1} \mathrel \RR b$
Likewise there exists $x_{n - 2} \in S$ such that:
:$a \mathrel {\RR^{n - 2} } x_{n - 2} \land x_{n - 2} \mathrel \RR x_{n - 1}$
 
And so forth there exist elements $x_0, \dots, x_n \in S$ such that:
:$x_0 = a$
:$x_n = b$
:$\forall k \in \N_n: x_k \mathrel \RR x_{k + 1}$
Since $\RR \subseteq \RR'$:
:$\forall k \in \N_n: x_k \mathrel {\RR'} x_{k + 1}$
Since $\RR'$ is transitive:
:$a \mathrel {\RR'} b$
That is:
:$\tuple {a, b} \in \RR'$
Since this holds for all $\tuple {a, b} \in \RR^+$:
:$\RR^+ \subseteq \RR'$
Since this holds for all transitive relations $\RR'$ that contain $\RR$:
:$\RR^+$ is the smallest transitive relation containing $\RR$.
Category:Equivalence of Definitions of Transitive Closure of Relation