nyuuzyou/wikis huggingface dataset:
Transitive Closure of Reflexive Relation is Reflexive

== Theorem ==
Let $S$ be a set.
Let $\RR$ be a reflexive relation on $S$.
Let $\RR^+$ be the transitive closure of $\RR$.
Then $\RR^+$ is reflexive.
== Proof ==
Let $a \in S$.
Since $\RR$ is reflexive:
:$\tuple {a, a} \in \RR$
By the definition of transitive closure:
:$\RR \subseteq \RR^+$
Thus by the definition of subset:
:$\tuple {a, a} \in \RR^+$
Since this holds for all $a \in S$, it follows that $\RR^+$ is reflexive.
== Also see ==
* Reflexive Closure of Transitive Relation is Transitive
Category:Reflexive Relations
Category:Transitive Closures
Transitive Closure of Reflexive Symmetric Relation is Equivalence

== Theorem ==
Let $S$ be a set.
Let $\RR$ be a symmetric and reflexive relation on $S$.
Then the transitive closure of $\RR$ is an equivalence relation.
== Proof ==
Let $\sim$ be the transitive closure of $\RR$.
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
By Transitive Closure of Reflexive Relation is Reflexive:
:$\sim$ is reflexive.
=== Symmetry ===
By Transitive Closure of Symmetric Relation is Symmetric:
:$\sim$ is symmetric.
=== Transitivity ===
By the definition of transitive closure:
:$\sim$ is transitive.
$\sim$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
Category:Transitive Closures
Category:Equivalence Relations
Transitive Closure of Relation/Examples/Arbitrary Example 1

== Example of Transitive Closure ==
Let $S = \set {1, 2, 3}$ be a set.
Let $\RR$ be the relation on $S$ defined as:
:$\RR = \set {\tuple {1, 2}, \tuple {2, 2}, \tuple {2, 3} }$
The transitive closure $\RR^+$ of $\RR$ is given by:
:$\RR^+ = \set {\tuple {1, 2}, \tuple {2, 2}, \tuple {2, 3}, \tuple {1, 3} }$
== Sources ==
* : Chapter $1$: Preliminaries: $1.5$ Relations: Closures of Relations
Category:Examples of Transitive Closures
Transitive Closure of Relation/Examples/Arbitrary Example 2

== Example of Transitive Closure ==
Let $S = \set {1, 2, 3, 4, 5}$ be a set.
Let $\RR$ be the relation on $S$ defined as:
:$\RR = \set {\tuple {1, 2}, \tuple {2, 3}, \tuple {3, 4}, \tuple {5, 4} }$
The transitive closure $\RR^+$ of $\RR$ is given by:
:$\RR^+ = \set {\tuple {1, 2}, \tuple {1, 3}, \tuple {1, 4}, \tuple {2, 3}, \tuple {2, 4}, \tuple {3, 4}, \tuple {5, 4} }$
== Proof ==
By Construction of Transitive Closure of Relation:
That completes the phase of the construction which uses Rule $(1)$.
Then:
There are no further elements of $\RR$ for which there are corresponding elements of $\RR^*$ that satisfy Rule $(2)$.
Hence the result.
== Sources ==
* : Chapter $1$: Preliminaries: Exercises: $1.7$
Category:Examples of Transitive Closures
Transitive Closure of Relation Always Exists/Outline

== Theorem ==
== Outline of Proof ==
First, note that there exists at least one transitive relation containing $\RR$.
That is, the trivial relation $S \times S$, which is an equivalence and therefore transitive by definition.
Next, note that the Intersection of Transitive Relations is Transitive.
Hence the transitive closure of $\RR$ is the intersection of all transitive relations containing $\RR$.
Category:Transitive Closure of Relation Always Exists
Transitive Closure of Relation Always Exists/Proof

== Theorem ==
== Proof ==
=== Outline ===
By definition, the trivial relation $\TT = S \times S$ on $S$ contains $\RR$ as a subset.
Further, $\TT$ is transitive by Trivial Relation is Equivalence.
Thus there exists at least one transitive relation on $S$ that contains $\RR$.
Let $\RR^\cap$ be defined as the intersection of all transitive relations on $S$ that contain $\RR$:
:$\ds \RR^\cap := \bigcap \set {\RR': \RR' \text{ is transitive and } \RR \subseteq \RR'}$
By Intersection of Transitive Relations is Transitive, $\RR^\cap$ is also a transitive relation on $S$.
By Set Intersection Preserves Subsets, it also holds that $\RR \subseteq \RR^\cap$.
Lastly, by Intersection is Subset, for any transitive relation $\RR'$ containing $\RR$, it must be that $\RR^\cap \subseteq \RR'$.
Thus $\RR^\cap$ is indeed the minimal transitive relation on $S$ containing $\RR$.
That is, $\RR^+ = \RR^\cap$, and thence the transitive closure of $\RR$ exists.
Category:Transitive Closure of Relation Always Exists
Transitive Closure of Set-Like Relation is Set-Like

== Theorem ==
Let $A$ be a class.
Let $\RR$ be a set-like endorelation on $A$.
Let $\RR^+$ be the transitive closure of $\RR$.
Then $\RR^+$ is also a set-like relation.
== Proof ==
Let $x \in A$.
Let $A'$ be the class of all subsets of $A$.
For each $s \in A'$, $\RR^{-1}$ is a subset of $A$.
Hence by Inverse Image of Set under Set-Like Relation is Set and the definition of endorelation:
:$\RR^{-1} \in A'$
Define a mapping $G: A' \to A'$ as:
:$\forall s \in A': \map G s = \map {\RR^{-1} } s$
Recursively define a mapping $f: \N \to A'$ as follows:
:$\map f n = \begin {cases} \set x & : n = 0 \\ \map G {\map f {n - 1} } & : n > 0 \end {cases}$
By the and the :
:$\map f \N$ is a set.
Thus by the :
:$\ds \bigcup \map f \N$ is a set.
Let $y \in \map {\paren {\RR^+}^{-1} } x$.
By the definition of transitive closure:
:for some $n \in \N_{>0}$ there are $a_0, a_1, \dots, a_n$ such that $y = a_0 \mathrel \RR a_1 \mathrel \RR \cdots \mathrel \RR a_n = x$.
Then by induction (working from $n$ to $0$), $\ds a_n, a_{n - 1}, \dots, a_0 \in \bigcup \map f \N$.
As this holds for all such $y$:
:$\ds \map {\paren {\RR^+}^{-1} } x \subseteq \bigcup \map f \N$
By the :
:$\map {\paren {\RR^+}^{-1} } x$ is a set.
As this holds for all $x \in A$:
:$\RR^+$ is a set-like relation.
Category:Set Theory
Category:Transitive Closures
Transitive Closure of Set Always Exists

== Theorem ==
Let $S$ be a set.
Let $G$ be a mapping such that $\map G x = x \cup \bigcup x$.
Let $F$ be defined using the Principle of Recursive Definition:
:$\map F 0 = S$
:$\map F {n^+} = \map G {\map F n}$
Let $\ds T = \bigcup_{n \mathop \in \omega} \map F n$.
Then:
:$T$ is a set and is transitive
:$S \subseteq T$
:If $R$ is transitive and $S \subseteq R$, then $T \subseteq R$.
That is, given any set $S$, there is an explicit construction for its transitive closure.
== Proof ==
$\omega$ is a set by the .
Thus by the , the image of $\omega$ under $F$ is also a set.
Since $T$ is the union of $\map F \omega$, it is thus a set by the .
Furthermore:
By the above equations:
:$x \in T \land y \in x \implies y \in T$
Thus by definition $T$ is transitive.
We have that:
:$S = \map F 0$
By Set is Subset of Union of Family:
:$\ds S \subseteq \bigcup_{n \mathop \in \omega} \map F n$
So $S \subseteq T$.
Finally, suppose that $S \subseteq R$ and $R$ is transitive.
$T \subseteq R$ follows by finite induction:
For all $n \in \omega$, let $\map P n$ be the proposition:
:$\map F n \subseteq R$
=== Basis for the Induction ===
$\map P 0$ is the case:
:$\map F 0 \subseteq R$
which has been proved above.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 0$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\map F k \subseteq R$
Then we need to show:
:$\map F {k + 1} \subseteq R$
=== Induction Step ===
This is our induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\map F n \subseteq R$ for all $n \in \omega$
:$T \subseteq R$
== Sources ==
* : $\S 9.1$
Category:Relational Closures
Transitive Closure of Symmetric Relation is Symmetric

== Theorem ==
Let $S$ be a set.
Let $\RR$ be a symmetric relation on $S$.
Let $\TT$ be the transitive closure of $\RR$.
The $\TT$ is symmetric.
== Proof ==
Let $a, b \in S$ with $a \mathrel \TT b$.
By the definition of transitive closure, there is an $n \in \N$ such that $a \mathrel {\RR^n} b $.
Thus there are $x_0, x_1, \dots x_n \in S$ such that:
:$x_0 = a$
:$x_n = b$
:For $k = 0, \dots, n-1$: $x_k \mathrel \RR x_{k + 1}$
For $k = 0, \dots, n$, let $y_k = x_{n - k}$.
Then:
:$y_0 = x_n = b$
:$y_n = x_0 = a$
For $k = 0, \dots, n - 1$:
:$x_{n - k - 1} \mathrel \RR x_{n - k}$
Thus:
:$y_{k + 1} \mathrel \RR y_k$
Since $\RR$ is symmetric:
:For $k = 0, \dots, n - 1$: $y_k \mathrel \RR y_{k + 1}$
Thus $b \mathrel {\RR^n} a$, so $b \mathrel \TT a$.
Category:Symmetric Relations
Category:Transitive Closures
Transitive Law

== Theorem ==
The transitive law is the statement that the usual ordering on the real numbers is a transitive relation.
Let $a, b, c \in \R$ such that $a > b$ and $b > c$.
Then:
:$a > c$
== Proof ==
From Real Numbers form Ordered Integral Domain, $\struct {\R, +, \times, \le}$ forms an ordered integral domain.
From Ordered Integral Domain is Totally Ordered Ring, the usual ordering $\le$ is a total ordering.
From Relation Induced by Strict Positivity Property is Transitive it follows that $<$ is transitive.
== Sources ==
* : Introduction: Review of Algebra, Geometry, and Trigonometry: $\text{0-2}$: Inequalities
* : $\S 1$: Real Numbers: $\S 1.4$: Inequalities: $\text{(I)}$
* 
* : $(2)$ Transitive law
* 
* 
* : $(2)$ Transitive law
* 
Category:Transitive Law
Category:Real Numbers
Category:Inequalities
Category:Named Theorems
Transitive Relation/Examples/Is an Ancestor of

== Example of Transitive Relation ==
Let $P$ be the set of people.
Let $\sim$ be the relation on $P$ defined as:
:$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text { $x$ is an ancestor of $y$}$
Then $\sim$ is a transitive relation.
== Sources ==
* : Chapter $\text{I}$: Sets and Functions: Relations
* : Chapter $1$: Sets and mappings: $\S 1.4$: Equivalence relations
Category:Examples of Transitive Relations
Transitive Relation/Examples/Less Than on Real Numbers

== Example of Transitive Relation ==
Let $<$ be the usual ordering on the set of real numbers $\R$.
Then $<$ is a transitive relation, but neither reflexive nor symmetric.
== Sources ==
* : Chapter $1$: Preliminaries: $1.5$ Relations: Example $1.3$
* : Chapter $1$: Theory of Sets: $\S 7$: Relations
Category:Examples of Transitive Relations
Transitive Relation Compatible with Semigroup Operation Relates Powers of Related Elements

== Theorem ==
Let $\struct {S, \circ}$ be a semigroup.
Let $\RR$ be a transitive relation on $S$ which is compatible with $\circ$.
Let $x, y \in S$ such that $x \mathrel \RR y$.
Let $n \in \N_{>0}$ be a strictly positive integer.
Then:
:$x^n \mathrel \RR y^n$
where $x^n$ is the $n$th power of $x$.
== Proof ==
We proceed by mathematical induction.
By definition of power:
:$x^1 = x$
:$y^1 = y$
Hence, by assumption:
:$x^1 \mathrel \RR y^1$
Suppose now that for $n \ge 1$:
:$x^n \mathrel \RR y^n$
Recall the assumption that $x \mathrel \RR y$.
Applying Operating on Transitive Relationships Compatible with Operation to these relations yields:
:$x^n \circ x \mathrel \RR y^n \circ y$
By definition of power:
:$x^{n + 1} = x^n \circ x$
and:
:$y^{n + 1} = y^n \circ y$
The result follows by the Principle of Mathematical Induction.
Category:Compatible Relations
Category:Semigroups
Transitive Relation is Antireflexive iff Asymmetric

== Theorem ==
Let $\RR \subseteq S \times S$ be a relation which is not null.
Let $\RR$ be transitive.
Then $\RR$ is antireflexive $\RR$ is asymmetric.
== Proof ==
=== Necessary Condition ===
Let $\RR \subseteq S \times S$ be antireflexive.
Then by Antireflexive and Transitive Relation is Asymmetric it follows that $\RR$ is asymmetric.
=== Sufficient Condition ===
Let $\RR$ be asymmetric.
Then from Asymmetric Relation is Antireflexive it follows directly that $\RR$ is antireflexive.
== Also see ==
* Null Relation is Antireflexive, Symmetric and Transitive for the case where $\RR = \O$.
== Sources ==
* : Chapter $4$: The Predicate Calculus $2$: $5$ Properties of Relations: Exercise $3$
Category:Antireflexive Relations
Category:Asymmetric Relations
Category:Transitive Relations
Transitive Relation whose Symmetric Closure is not Transitive

== Theorem ==
Let $S = \set {p, q}$, where $p$ and $q$ are distinct elements.
Let $\RR = \set {\tuple {p, q} }$.
Then $\RR$ is transitive but its symmetric closure is not.
== Proof ==
$\RR$ is vacuously transitive because there are no elements $a, b, c \in S$ such that $a \mathrel \RR b$ and $b \mathrel \RR c$.
Let $\RR^\leftrightarrow$ be the symmetric closure of $\RR$.
Then $\RR^\leftrightarrow = \RR \cup \RR^{-1} = \set {\tuple {p, q}, \tuple {q, p} }$.
Then:
:$p \mathrel {\RR^\leftrightarrow} q$ and $q \mathrel {\RR^\leftrightarrow} p$
but:
:$p \not \mathrel {\RR^\leftrightarrow} p$
Therefore $\RR^\leftrightarrow$ is not transitive.
Category:Transitive Relations
Category:Symmetric Closures
Transitive Set Contained in Von Neumann Hierarchy Level

== Theorem ==
Let $G$ be a transitive set.
Then for some ordinal $i$, $G \subseteq V_i$.
== Proof ==
 for each ordinal $i$ the set $G \setminus V_i$ is non-empty. 
Let $i$ be any ordinal.
Then by the axiom of foundation:
$\exists x: x \in G\setminus V_i \text{ and } x \cap \paren {G \setminus V_i} = \O$
Since $G$ is transitive, $x \subseteq G$.
Since $x \subseteq G$ and $x \cap \paren {G \setminus V_i} = \O$:
:$x \subseteq V_i$
By the definition of $V$, $x \in V_{i + 1}$, so:
:$x \notin G \setminus V_{i + 1}$
Thus $G \setminus V_{i + 1} \subsetneqq G \setminus V_i$ for each ordinal $i$.
Let $H: \On \to \powerset G$ be defined by:
:$\map H i = G \setminus V_i$ for each ordinal $i$
Since the class of ordinals is well-ordered, applying Strictly Increasing Mapping on Well-Ordered Class proves that for any ordinals $p$ and $q$,
:$p < q$ implies $\map H q \subsetneq \map H p$.
Since the class of ordinals is totally ordered, for any two distinct ordinals $i$ and $j$:
: $\map H i \ne \map H j$
so $H$ is injective.
But that contradicts the fact that $\powerset G$ is a set.
Category:Von Neumann Hierarchy
Transitive Set is Proper Subset of Ordinal iff Element of Ordinal

== Theorem ==
Let $A$ be an ordinal.
Let $B$ be a transitive set.
Then:
:$B \subsetneq A \iff B \in A$
=== Corollary ===
== Proof ==
=== Necessary Condition ===
Suppose that $B \in A$.
From Ordinal is Transitive, it follows that $B \subseteq A$.
Also, $B \ne A$ by Ordinal is not Element of Itself.
Therefore, $B \subsetneq A$, as desired.
=== Sufficient Condition ===
Suppose that $B \subsetneq A$.
By the definition of set equality, the set difference $A \setminus B$ is non-empty.
By the definition of a strict well-ordering, there exists a minimal element $x$ of $A \setminus B$.
As $x \in A$, it follows from Ordinal is Transitive that $x \subseteq A$.
Next, since the strict well-ordering on $A$ is given by the epsilon restriction $\Epsilon \! \restriction_A$, it follows by the definition of a minimal element that:
:$\forall y \in A \setminus B: y \notin x$
Therefore:
Suppose that $z \in B$.
Since $B \subset A$, it follows that $z \in A$.
Recall that the strict well-ordering on $A$ is given by the epsilon restriction $\Epsilon \! \restriction_A$.
From the Trichotomy Law (Ordering), it follows that $z \in x$ or $x = z$ or $x \in z$.
If $x = z$ or $x \in z$, then it follows by the transitivity of $B$ that $x \in B$.
This contradicts the definition of $x$.
Hence, $z \in x$.
That is, $B \subseteq x$.
We have shown that $x \subseteq B$ and $B \subseteq x$.
By definition of set equality:
:$B = x \in A$
== Also see ==
* Ordering on Ordinal is Subset Relation
* Initial Segment of Ordinal is Ordinal
== Sources ==
* : $\S 7.7$
Category:Ordinals
Category:Transitive Classes
Transitive Set is Proper Subset of Ordinal iff Element of Ordinal/Corollary

== Corollary to Transitive Set is Proper Subset of Ordinal iff Element of Ordinal ==
Let $A$ and $B$ be ordinals.
Then:
:$A \subsetneq B \iff A \in B$
== Proof ==
We have that an ordinal is transitive.
The result follows directly from Transitive Set is Proper Subset of Ordinal iff Element of Ordinal.
== Sources ==
* : $\S 7.8$
Category:Ordinals
Transitive Set of Ordinals is Ordinal

== Theorem ==
Let $x$ be a transitive set of ordinals.
Then $x$ is itself an ordinal.
== Proof ==
Let $x$ be a transitive set of ordinals according to the statement of the theorem.
We have from Class of All Ordinals is Well-Ordered by Subset Relation that $\On$ is well-ordered by $\subseteq$.
By Exists Ordinal Greater than Set of Ordinals there exists $\alpha$ such that $\alpha \notin x$.
Hence let $\alpha$ be the smallest ordinal not in $x$.
So all ordinals smaller than $\alpha$ are in $x$.
Hence from Ordinal equals its Initial Segment:
:$\alpha \subseteq x$
From Transitive Class of Ordinals is Subset of Ordinal not in it:
:$x \subseteq \alpha$
Hence by set equality:
:$x = \alpha$
Thus $x$ is an ordinal.
== Sources ==
* : Chapter $5$: Ordinal Numbers: $\S 2$ Ordinals and transitivity: Theorem $2.2 \ (1)$
Category:Ordinals
Category:Transitive Classes
Transitive Subgroup/Examples/n-Cycle

== Example of Transitive Subgroup ==
Let $S_n$ denote the symmetric group on $n$ letters for $n \in \N$.
Consider the subgroup $H$ of $S_n$ generated by the cyclic permutation $\tuple {1, 2, \ldots, n}$.
Then $H$ is a transitive subgroup .
== Sources ==
* : Chapter $2$: The Symmetric Groups: $\S 86$
Category:Transitive Subgroups
Transitive Subgroup of Prime containing Transposition

== Theorem ==
Let $p$ be a prime number.
Let $S_p$ denote the symmetric group on $p$ letters.
Let $H$ be a transitive subgroup of $S_p$.
If $H$ contains a transposition, then $H = S_p$.
== Proof ==
, let $\tuple {1, 2}$ be the transposition contained by $H$.
Let us define an equivalence relation $\sim$ on the set $\N_p = \set {1, 2, \ldots, p}$ as:
:$i \sim j \iff \tuple {i, j} \in H$
Because $H$ is a transitive subgroup it follows that each $\sim$-equivalence class has the same number of elements.
In fact, if $\phi \in H$ and $\phi_1 := \map \phi 1 = i$, then $\phi$ yields a bijection from the $\sim$-equivalence class of $1$ to that of $i$, because:
:$\tuple {1, k} \in H \iff \tuple {i, \phi_k} = \tuple {\phi_1, \phi_k} = \phi \circ \tuple {1, k} \circ \phi^{-1} \in H$
The number $s$ of elements of any given $\sim$-equivalence class must be a divisor of $p$.
Thus $s = 1$ or $s = p$.
However, the $\sim$-equivalence class of $1$ contains at least both $1$ and $2$.
So there can be only one $\sim$-equivalence class which then contains $p$ elements.
In other words, $H$ contains all the transpositions of $S_p$.
From Existence and Uniqueness of Cycle Decomposition, every permutation is a composition of transpositions.
Hence:
:$H = S_p$
== Sources ==
* : Chapter $2$: The Symmetric Groups: $\S 86$
Category:Transitive Subgroups
Transitive and Antitransitive Relation is Asymmetric

== Theorem ==
Let $S$ be a set.
Let $\RR \subseteq S \times S$ be a relation in $S$.
Let $\RR$ be both transitive and antitransitive.
Then $\RR$ is asymmetric.
== Proof ==
Let $\tuple {x, y} \in \RR$ for some $x, y \in S$.
Then as $\RR$ is antitransitive:
:$\tuple {x, x} \notin \RR$
and so as $\RR$ is transitive and $\tuple {x, x} \notin \RR$:
:$\tuple {y, x} \notin \RR$
That is, $\RR$ is asymmetric.
== Sources ==
* : Chapter $4$: The Predicate Calculus $2$: $5$ Properties of Relations: Exercise $7 \ \text{(b)}$
Category:Asymmetric Relations
Category:Transitive Relations
Category:Antitransitive Relations
Transitivity of Algebraic Extensions

== Theorem ==
Let $E / F / K$ be a tower of field extensions.
Let $E$ be algebraic over $F$.
Let $F$ be algebraic over $K$.
Then $E$ is algebraic over $K$.
== Proof ==
Let $x \in E$.
There are $a_0, \ldots, a_n \in F$ such that $a_0 + \cdots + a_n x^n = 0$.
Let $L = \map K {a_0, \ldots, a_n}$.
We have that $L / K$ is finitely generated and algebraic.
Therefore by Finitely Generated Algebraic Extension is Finite this extension is finite.
We have that $\map L x / L$ is simple and algebraic.
So by Structure of Simple Algebraic Field Extension, this extension is also finite.
Therefore, by the Tower Law:
:$\map L x / K$ is finite.
That is, $x$ is contained in a finite extension of $K$.
Therefore because a Finite Field Extension is Algebraic, it follows that $x$ is algebraic over $K$, as was to be proved.
== Also see ==
* Transitivity of Separable Field Extensions
Category:Field Extensions
Transitivity of Big-O Estimates/General

== Theorem ==
Let $X$ be a topological space.
Let $V$ be a normed vector space over $\R$ or $\C$ with norm $\norm {\,\cdot\,}$.
Let $f, g, h: X \to V$ be functions.
Let $x_0 \in X$.
Let $f = \map \OO g$ and $g = \map \OO h$ as $x \to x_0$, where $\OO$ denotes big-$\OO$ notation.
Then $f = \map \OO h$ as $x \to x_0$.
== Proof ==
Because $f = \map \OO g$ and $g = \map \OO h$, there exist neighborhoods $U$ and $V$ of $x_0$ and real numbers $c, d \ge 0$ such that:
:$\norm {\map f x} \le c \cdot \norm {\map g x}$ for all $x \in U$
:$\norm {\map g x} \le d \cdot \norm {\map h x}$ for all $x \in V$.
By Intersection of Neighborhoods in Topological Space is Neighborhood, $U\cap V$ is a neighborhood of $x_0$.
For $x \in U \cap V$, we have:
:$\norm {\map f x} \le c \cdot \norm {\map g x} \le c d \cdot \norm {\map h x}$
Thus $f = \map \OO h$ for $x \to x_0$.
Category:Big-O Notation
Transitivity of Big-O Estimates/Sequences

== Theorem ==
Let $\sequence {a_n}$, $\sequence {b_n}$ and $\sequence {c_n}$ be sequences of real or complex numbers.
Let $a_n = \map \OO {\sequence {b_n} }$ and $b_n = \map \OO {\sequence {c_n} }$, where $\OO$ denotes big-$\OO$ notation.
Then $a_n = \map \OO {\sequence {c_n} }$.
== Proof ==
Because $a_n = \map \OO {\sequence {b_n} }$, there exists $K \ge 0$ and $n_0 \in \N$ such that $\size {a_n} \le K \cdot \size {b_n}$ for $n \ge n_0$.
Because $b_n = \map \OO {\sequence {c_n} }$, there exists $L \ge 0$ and $n_1 \in \N$ such that $\size {b_n} \le L \cdot \size {c_n}$ for $n \ge n_1$.
Then $\size {a_n} \le K L \cdot \size {c_n}$ for $n \ge \max \set {n_0, n_1}$.
Thus $a_n = \map \OO {\sequence {c_n} }$.
Category:Big-O Notation
Transitivity of Finite Generation

== Theorem ==
Let $\struct { C, +_C, \circ_C}$ be a ring with unity, where $1_C$ denotes the unity of $C$.
Let $\struct { B, +_B, \circ_B}$ be a subring of $C$, such that $1_C \in B$.
Let $\struct { A, +_A, \circ_A}$ be a subring of $B$, such that $1_C \in A$.
Let $B' = \struct { B, +_B, \circ_B}_A$ be a finitely generated $A$-module, where the scalar multiplication $\circ_B$ is defined as the ring product $\circ_B$ in $B$.
Let $C' = \struct { C, +_C, \circ_C}_B$ be a finitely generated $B$-module, where the scalar multiplication $\circ_C$ is defined as the ring product $\circ_C$ in $C$.
Then $C' ' = \struct { C, +_C, \circ_C}_A$ is a finitely generated $A$-module.
== Proof ==
As $1_C \in B$, and $1_C \in A$, it follows that $A$ and $B$ are rings with unity.
Let $b_1, \ldots, b_n \in B$ generate $B'$ over $A$.
Let $c_1, \ldots, c_m \in C$ generate $C'$ over $B$.
Then for any $x \in C$, there exist $\beta_k \in B$, $k = 1, \ldots, m$ such that:
:$\ds x = \sum_{k \mathop = 1}^m \beta_k \circ_C c_k$
For any $k \in \set {1, \ldots, m}$, there exist $\alpha_{k j} \in A$, $j = 1, \ldots, n$ such that:
:$\ds \beta_k = \sum_{j \mathop = 1}^n \alpha_{k j} \circ_B b_j$
Then:
which shows that $x$ is a linear combination of $\set {b_j \circ_C c_k : j = 1, \ldots, n, k = 1, \ldots, m}$, with scalars $\alpha_{k j} \in A$ for all $k \in \set {1, \ldots, m}, j \in \set{1, \ldots, n}$.
Therefore, $\set {b_j \circ_C c_k : j = 1, \ldots, n, k = 1, \ldots, m}$ generates $C' '$ over $A$.
Category:Commutative Algebra
Category:Algebraic Number Theory