nyuuzyou/wikis huggingface dataset:
Increasing Martingale Theorem

== Theorem ==
Let $\struct {X, \Sigma, \mu}$ be a probability space.
Let $f$ be a $\mu$-integrable function.
Given sub-$\sigma$-algebra $\CC \subseteq \Sigma$, let $\expect {f \mid \CC}$ denote the conditional expectation of $f$ on $\CC$.
Let $\sequence {\FF_n}_{n \mathop \in \N}$ be a filtration of $\Sigma$. 
Let $\FF_\infty$ be the limit of $\sequence {\FF_n}_{n \mathop \in \N}$.
Then:
:$\ds \lim_{n \mathop \to \infty} \expect {f \mid \FF_n} = \expect {f \mid \FF_\infty}$
holds in $L^1$ norm, and $\mu$-almost surely.
 
== Proof ==
By Tower Property of Conditional Expectation:
:$\expect {f \mid \FF_n} = \expect {\expect {f \mid \FF_\infty} \mid \FF_n}$
Let $\tilde f := \expect {f \mid \FF_\infty}$.
Then we need to show that:
:$\ds \lim_{n \mathop \to \infty} \expect {\tilde f \mid \FF_n} = \tilde f$
holds in $L^1$ norm, and $\mu$-almost surely.
To this end, let $\epsilon > 0$.
By Filtration's Lp Spaces are Dense in Limit Filtration's Lp Space, there exist:
:$N \in \N$
:$g \in \map {L^1} {X, \FF_N, \mu}$
such that:
:$(1):\quad \norm {\tilde f - g}_1 \le \epsilon$
Then, for all $n \ge N$:
Thus:
:$\ds \lim_{n \mathop \to \infty} \norm {\expect {\tilde f \mid \FF_n} - \tilde f}_1 = 0$
On the other hand:
Observe:
From $(2)$ and $(3)$:
Therefore:
== Sources ==
* $5.2:$ Martingales
Category:Filtrations of Sigma-Algebras
Category:Martingales
Increasing Real Function has Countably Many Discontinuities

== Theorem ==
Let $f: \R \to \R$ be an increasing real function.
Then $f$ has at most countably many discontinuities.
=== Corollary ===
== Proof ==
Let $D \subseteq \R$ be the set of discontinuities of $f$. 
From Limit of Monotone Real Function: Increasing: Corollary, we have that:
:$\ds \lim_{x \mathop \to b^-} \map f x = l_x$ and $\ds \lim_{x \mathop \to b^+} \map f x = r_x$
both exist for each $x \in \R$.
Further:
:$l_x \le r_x$ 
Let $x \in D$. 
Then since:
:$f$ is discontinuous at $x$
:both the left and right limit exist at $x$
we have:
:$l_x \ne r_x$
Hence:
:$l_x < r_x$.
We argue that the open intervals $\openint {l_x} {r_x}$ are disjoint.
Let $x, y \in D$ be such that $x < y$. 
Let $\xi \in \R$ be such that $x < \xi < y$.
Then by , we have:
:$r_x \le \map f \xi \le l_y$ 
Hence if $x < y$, we have:
:$\openint {l_x} {r_x} \cap \openint {l_y} {r_y} = \O$
By swapping $x$ and $y$, we have:
:$\openint {l_x} {r_x} \cap \openint {l_y} {r_y} = \O$
for $x \ne y$ with $x, y \in D$. 
Hence $\DD = \set {\openint {l_x} {r_x} : x \in D}$ is a set of disjoint open intervals.
From:
:Real Number Line is Separable
:Separable Space satisfies Countable Chain Condition
$\DD$ is countable.
Since the map $g : D \to \DD$ defined by:
:$\map g x = \openint {l_x} {r_x}$
for each $x \in D$ is a bijection, it follows that $D$ is countable.
== Sources ==
* : $13.12$
Category:Monotone Real Functions
Category:Real Analysis
Increasing Real Function has Countably Many Discontinuities/Corollary

== Corollary ==
Let $f: \R \to \R$ be an increasing real function.
Let $D$ be the set of discontinuities of $f$. 
Then $\R \setminus D$ is everywhere dense in $\R$. 
== Proof ==
From Increasing Real Function has Countably Many Discontinuities, $D$ is countable.
From Complement of Countable Set in Topological Space where Open Neighborhood is Uncountable is Everywhere Dense: Corollary, $\R \setminus D$ is everywhere dense in $\R$. 
Category:Increasing Real Function has Countably Many Discontinuities
Increasing Second Argument of Ackermann-Péter Function is Not Greater than Increasing First Argument

== Theorem ==
For all $x, y \in \N$:
:$\map A {x + 1, y} \ge \map A {x, y + 1}$
where $A$ is the Ackermann-Péter function.
== Proof ==
Proceed by induction on $y$.
=== Basis for the Induction ===
Suppose $y = 0$.
Then:
Therefore:
:$\map A {x + 1, 0} \ge \map A {x, 1}$
which is the basis for the induction.
=== Induction Hypothesis ===
This is the induction hypothesis:
:$\map A {x + 1, y} \ge \map A {x, y + 1}$
We want to show that:
:$\map A {x + 1, y + 1} \ge \map A {x, y + 2}$
=== Induction Step ===
First, observe:
Thus, we have shown:
:$\paren 1 \quad \map A {x + 1, y} \ge y + 2$
Now, we have:
This completes the induction step.
Thus, by the Principle of Mathematical Induction, the result holds for all $x, y \in \N$.
Category:Ackermann-Péter Function
Increasing Sequence in Ordered Set Terminates iff Maximal Element

== Theorem ==
Let $\struct {P, \le}$ be an ordered set.
:$(1): \quad$ Every increasing sequence $x_1 \le x_2 \le x_3 \le \cdots$ with $x_i \in P$ eventually terminates: there is $n \in \N$ such that $x_n = x_{n + 1} = \cdots$.
:$(2): \quad$ Every non-empty subset of $P$ has a maximal element.
== Proof ==
=== $(1)$ implies $(2)$ ===
Suppose $(1)$ holds.
Pick $\O \ne S \subseteq P$.
Let $x_1 \in S$ be arbitrary.
Given $x_k \in S$, pick $x_{k + 1} \in S$ strictly bigger than $x_k$.
By hypothesis the process must eventually terminate, say $x_n$ is the last element.
Then by construction there are no larger elements than $x_n$, that is, $x_n$ is a maximal element of $S$.
=== $(2)$ implies $(1)$ ===
Suppose $(2)$ holds.
Let $\sequence {x_k}_{k \mathop \in \N}$ be an increasing sequence of elements of $P$.
By hypothesis, the set $\set {x_k: k \in \N}$ has a maximal element, say $x_n$.
Then since $x_m \ge x_n$ for all $m \ge n$, we must have $x_n = x_{n + 1} = \cdots$.
Category:Increasing Sequences
Increasing Sequence of Sets forms Nest

== Theorem ==
Let $\sequence {a_n}$ be an increasing sequence of sets:
:$\forall k \in \N: S_k \subseteq S_{k + 1}$
Let $c = \set {a_1, a_1, \ldots, a_n, a_{n + 1}, \ldots}$ be the class of all terms of $\sequence {a_n}$.
Then $c$ is a nest.
== Proof ==
Recall the definition of nest:
$c$ is a nest :
:$\forall x, y \in c: x \subseteq y$ or $y \subseteq x$
Let $a_i$ and $a_j$ be arbitrary elements of $c$.
From Ordering on Natural Numbers is Trichotomy, either $i < j$ or $i = j$ or $i > j$.
;Case $(1)$
Let $i = j$.
Then we have $a_i = a_j$ and so both $a_i \subseteq a_j$ and $a_j \subseteq a_i$.
;Case $(2)$
Let $i \ne j$.
, suppose $i < j$.
Then as Subset Relation is Transitive:
:$a_i \subseteq a_j$
== Sources ==
* : Chapter $3$: The Natural Numbers: $\S 8$ Definition by finite recursion: Exercise $8.5$
Category:Nests
Category:Increasing Sequences
Increasing Sequence of Sets induces Partition on Limit

== Theorem ==
Let $\sequence {S_n}_{n \mathop \in \N} \uparrow S$ be an increasing sequence of sets with limit $S$.
Define $T_1 = S_1$, and, for $n \in \N$, $T_{n + 1} = S_{n + 1} \setminus S_n$, where $\setminus$ denotes set difference.
Then $\sequence {T_n}_{n \mathop \in \N}$ is a countable partition of $S$.
== Proof ==
That $\sequence {T_n}_{n \mathop \in \N}$ partitions $S$, means precisely that:
:$(1): \quad$ The $T_n$ are pairwise disjoint
:$(2): \quad \ds \bigcup_{n \mathop \in \N} T_n = S$
It is more convenient to prove $(1)$ and $(2)$ separately:
=== Proof of $(1)$ ===
Let $l, m \in \N$ be such that $l < m$.
Then by Set Difference is Subset, $T_l \subseteq S_l$.
As the $S_n$ form an increasing sequence of sets, it follows that also $T_l \subseteq S_{m - 1}$ because $m - 1 \ge l$.
Now compute as follows:
Hence $T_m \cap T_l = \O$.
Reversing the roles of $m$ and $l$ leads to the same conclusion if $l > m$.
Hence, by definition, the $T_n$ are pairwise disjoint.
=== Proof of $(2)$ ===
By Set Union Preserves Subsets and Set Difference is Subset, have that:
:$\ds \bigcup_{n \mathop \in \N} T_n \subseteq \bigcup_{n \mathop \in \N} S_n = S$
To establish $(2)$, by definition of set equality, it is now only required to show that $\ds S \subseteq \bigcup_{n \mathop \in \N} T_n$.
So let $s \in S$.
Then by definition of union, the set:
:$N_s := \set {n \in \N: s \in S_n}$
is nonempty.
By Well-Ordering Principle, $N_s$ contains a minimal element, $n$, say.
If $n = 1$, then $s \in S_1 = T_1$.
If $n > 1$, then, by minimality of $n$, $s \notin S_{n - 1}$.
Hence, by definition of set difference, $s \in T_n = S_n \setminus S_{n - 1}$.
By definition of set union, it follows that:
:$\ds s \in \bigcup_{n \mathop \in \N} T_n$
That is, by definition of subset:
:$\ds S \subseteq \bigcup_{n \mathop \in \N} T_n$
Category:Set Theory
Category:Increasing Sequences of Sets
Increasing Sum of Binomial Coefficients

== Theorem ==
Let $n \in \Z$ be an integer.
Then:
:$\ds \sum_{j \mathop = 0}^n j \binom n j = n 2^{n - 1}$
where $\dbinom n k$ denotes a binomial coefficient.
That is:
:$1 \dbinom n 1 + 2 \dbinom n 2 + 3 \dbinom n 3 + \dotsb + n \dbinom n n = n 2^{n - 1}$
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 3$: The Binomial Formula and Binomial Coefficients: Properties of Binomial Coefficients: $3.14$
* : Chapter $1$: Some Preliminary Considerations: $1.2$ The Binomial Theorem: Problems $1.2$: $3 \ \text{(c)}$
* : $\S 3$: The Binomial Formula and Binomial Coefficients: Properties of Binomial Coefficients: $3.14.$
Category:Increasing Sum of Binomial Coefficients
Category:Binomial Coefficients
Increasing Sum of Binomial Coefficients/Proof 2

== Theorem ==
== Proof ==
From the Binomial Theorem:
:$(1): \quad \paren {1 + x}^n = \ds \sum_{j \mathop = 0}^n \dbinom n j x^n$
Differentiating $(1)$ $x$:
Hence the result.
== Sources ==
* : $\text I$. Algebra: The Binomial Theorem
Category:Increasing Sum of Binomial Coefficients
Category:Binomial Coefficients
Increasing Union of Ideals is Ideal/Chain

== Theorem ==
Let $R$ be a ring.
Let $\struct {P, \subseteq}$ be the ordered set consisting of all ideals of $R$, ordered by inclusion.
Let $\set {I_\alpha}_{\alpha \mathop \in A}$ be a non-empty chain of ideals in $P$.
Let $\ds I = \bigcup_{\alpha \mathop \in A} I_\alpha$ be their union.
Then $I$ is an ideal of $R$.
== Proof ==
=== Property 1: $0 \in I$ ===
Since $\set {I_\alpha}_{\alpha \mathop \in A}$ is non-empty chain, it must contain some ideal $I_\beta$
Since $I_\beta$ is an ideal, $0 \in I_\beta$. 
Thus $0 \in I$.
=== Property 2: $x \in I \implies -x \in I$ ===
If $x \in I$, then $x \in I_\beta$ for some $\beta\in A$.
Since $I_\beta$ is an ideal, $-x \in I_\beta$. 
Thus $-x \in I$.
=== Property 3: $x, y \in I \implies x + y \in I$ ===
If $x,y \in I$, then $x \in I_\beta$ for some $\beta\in A$, and $y \in I_\gamma$ for some $\gamma \in A$. 
Since $\set {I_\alpha}_{\alpha \mathop \in A}$ is totally ordered, $I_\beta \subseteq I_\gamma$ or $I_\gamma \subseteq I_\beta$.
, we can assume $I_\beta \subseteq I_\gamma$, which gives us $x, y \in I_\gamma$.
Since $I_\gamma$ is an ideal, $x + y \in I_\gamma$.
Thus $x + y \in I$.
=== Property 4: $x \in I \land r \in R \implies r x, x r \in I$ ===
If $x \in I$, then $x \in I_\beta$ for some $\beta\in A$. 
If $r \in R$, then since $I_\beta$ is an ideal, $r x, x r \in I_\beta$.
Thus $r x, x r \in I$.
Since $I$ satisfies these $4$ properties, it is a ideal of $R$.
== Also see ==
* Union of Chain of Proper Ideals is Proper Ideal
Category:Ring Theory
Category:Ideal Theory
Increasing Union of Ideals is Ideal/Sequence

== Theorem ==
Let $R$ be a ring.
Let $S_0 \subseteq S_1 \subseteq S_2 \subseteq \dotsb \subseteq S_i \subseteq \dotsb$ be ideals of $R$.
Then the increasing union $S$:
:$\ds S = \bigcup_{i \mathop \in \N} S_i$
is an ideal of $R$.
== Proof ==
Let $\ds S = \bigcup_{i \mathop \in \N} S_i$.
From Increasing Union of Subrings is Subring, we have that $S$ is a subring of $R$.
Now we need to show that it is an ideal of $R$.
Let $a \in S$.
Then $\exists i \in \N: a \in S_i$.
Let $b \in R$.
Then $a b \in S_i$ and $b a \in S_i$, as $S_i$ is an ideal of $R$.
Thus $a b \in S$ and $b a \in S$.
So $S$ is an ideal of $R$.
== Sources ==
* : $\S 2.3$: Some properties of subrings and ideals: Lemma $2.13 \ \text{(ii)}$
* : Chapter $9$: Rings: Exercise $17$
Category:Set Union
Category:Ideal Theory
Increasing Union of Subrings is Subring

== Theorem ==
Let $R$ be a ring.
Let $S_0 \subseteq S_1 \subseteq S_2 \subseteq \ldots \subseteq S_i \subseteq \ldots$ be subrings of $R$.
Then the increasing union $S$:
:$\ds S = \bigcup_{i \mathop \in \N} S_i$
is a subring of $R$.
== Proof ==
Let $\ds S = \bigcup_{i \mathop \in \N} S_i$.
Clearly $0_R \in S$.
Let $a, b \in S$.
Then $\exists i, j \in \N: a \in S_i, b \in S_j$.
From the construction, we have that either of $S_i$ and $S_j$ contains the other.
Let $l = \max \set {i, j}$ so $a, b \in S_l$.
Then $a + \paren {-b} \in S_l$ and $a b \in S_l$, as $S_l$ is a subring.
Thus $a + \paren {-b} \in S$ and $a b \in S$.
By the Subring Test, $S$ is a subring of $R$.
== Sources ==
* : $\S 2.3$: Some properties of subrings and ideals: Lemma $2.13 \ \text{(ii)}$
Category:Set Union
Category:Subrings
Increasing and Ordering on Mappings implies Mapping is Composition

== Theorem ==
Let $L = \struct {S, \preceq}, R = \struct {T, \preccurlyeq}$ be ordered sets.
Let $g: S \to T, d: T \to S$ be mappings such that
:$g$ and $d$ are increasing mappings
and
:$d \circ g \preceq I_S$ and $I_T \preccurlyeq g \circ d$
where $\preceq, \preccurlyeq$ denotes the orderings on mappings.
Then $d = d \circ \paren {g \circ d}$ and $g = \paren {g \circ d} \circ g$
== Proof ==
Let $t \in T$.
By definition of ordering on mappings:
:$\map {I_T} t \preccurlyeq \map {\paren {g \circ d} } t$
By definition of identity mapping:
:$t \preccurlyeq \map {\paren {g \circ d} } t$
By definition of increasing mapping:
:$\map d t \preceq \map d {\map {\paren {g \circ d} } t}$
By definition of composition of mappings:
:$\map d t \preceq \map {\paren {d \circ \paren {g \circ d} } } t$
By definition of ordering on mappings:
:$\map {\paren {d \circ g} } {\map d t} \preceq \map {I_S} {\map d t}$
By definition of identity mapping:
:$\map {\paren {d \circ g} } {\map d t} \preceq \map d t$
By definition of composition of mappings:
:$\map {\paren {\paren {d \circ g} \circ d} } t \preceq \map d t$
By Composition of Mappings is Associative:
:$\map {\paren {d \circ \paren {g \circ d} } } t \preceq \map d t$
Thus by definition of antisymmetry:
:$\map d t = \map {\paren {d \circ \paren {g \circ d} } } t$
Thus $g = \paren {g \circ d} \circ g$ holds by mutatis mutandis.
== Sources ==
* 
Category:Galois Connections
Indecomposable Lattice of Subgroups does not necessarily form Totally Ordered Set

== Theorem ==
Let $\struct {G, \circ}$ be a Group.
Let $\mathbb G$ be the set of subgroups of $G$.
Let $\struct {\mathbb G, \subseteq}$ be the complete lattice formed by the subset ordering on $\mathbb G$.
Let $\struct {G, \circ}$ be an indecomposable group.
Then it is not necessarily the case that $\struct {\mathbb G, \subseteq}$ is totally ordered.
== Proof ==
First we note that from Set of Subgroups forms Complete Lattice, $\struct {\mathbb G, \subseteq}$ is indeed a complete lattice.
;Proof by Counterexample
Let $D_4$ denote the dihedral group of order $8$, also known as the symmetry group of the square.
From Internal Group Direct Product Examples: $D_4$, it is seen that $D_4$ is indecomposable group.
But from the Hasse diagram, we see:
:
it is seen that $\struct {\mathbb G, \subseteq}$, where $\mathbb G$ denotes the set of subsets of $D_4$, is not totally ordered.
Hence the result.
== Also see ==
* Lattice of Subgroups forming Totally Ordered Set is Indecomposable: the converse
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.16 \ \text {(b)}$
Category:Decomposable Groups
Independence System Induced from Set of Subsets

== Theorem ==
Let $S$ be a finite set.
Let $\mathscr A$ be a non-empty set of subsets of $S$.
Let $\mathscr I = \set{X \subseteq S : \exists A \in \mathscr A : X \subseteq A}$.
Then:
:$\struct{S, \mathscr I}$ is an independence system
== Proof ==
It is shown that $\mathscr I$ satisfies the independence system axioms.
=== Independence Axiom $(\text I 1)$ ===
We have $\mathscr A$ is non-empty.
Let $A \in \mathscr A$.
From Empty Set is Subset of All Sets:
:$\O \subseteq A$
By definition of $\mathscr I$:
:$\O \in \mathscr I$
It follows that $\mathscr I$ satisfies the independence system axiom $(\text I 1)$ by definition.
=== Independence Axiom $(\text I 2)$ ===
Let $X \in \mathscr I$.
Let $Y \subseteq X$.
By definition of $\mathscr I$:
:$\exists A \in \mathscr A : X \subseteq A$
From Subset Relation is Transitive:
:$Y \subseteq A$
By definition of $\mathscr I$:
:$Y \in \mathscr I$
It follows that $\mathscr I$ satisfies the independence system axiom $(\text I 2)$ by definition.
Hence $\mathscr I$ satisfies the independence system axioms and so $\struct{S, \mathscr I}$ is an independence system by definition.
Category:Subsets
Category:Matroid Theory
Independent Events are Independent of Complement

== Theorem ==
Let $A$ and $B$ be events in a probability space $\struct {\Omega, \Sigma, \Pr}$.
Then $A$ and $B$ are independent $A$ and $\Omega \setminus B$ are independent.
=== Corollary ===
== General Result ==
== Proof ==
For $A$ and $B$ to be independent:
:$\map \Pr {A \cap B} = \map \Pr A \map \Pr B$
We need to show that:
:$\map \Pr {A \cap \paren {\Omega \setminus B} } = \map \Pr A \map \Pr {\Omega \setminus B}$
First note that $\Omega \setminus B \equiv \relcomp \Omega B$ where $\complement_\Omega$ denotes the relative complement.
From Set Difference as Intersection with Relative Complement, we have then that $A \cap \paren {\Omega \setminus B} = A \setminus B$.
From Set Difference and Intersection form Partition, we have that:
:$\paren {A \setminus B} \cup \paren {A \cap B} = A$
:$\paren {A \setminus B} \cap \paren {A \cap B} = \O$
So from the Kolmogorov axioms, we have that:
:$\map \Pr A = \map \Pr {A \setminus B} + \map \Pr {A \cap B}$
Hence:
But as $A \setminus B = A \cap \paren {\Omega \setminus B}$ we have:
:$\map \Pr {A \cap \paren {\Omega \setminus B} } = \map \Pr A \map \Pr {\Omega \setminus B}$
which is what we wanted to show.
Now, suppose $A$ and $\Omega \setminus B$ are independent.
From the above, we have that $A$ and $\Omega \setminus \paren {\Omega \setminus B}$ are independent.
But $\Omega \setminus \paren {\Omega \setminus B} = B$ from Relative Complement of Relative Complement hence the result.
== Sources ==
* : $\S 1.7$: Independent Events: Exercise $22$
Category:Independent Events
Independent Events are Independent of Complement/Corollary

== Corollary to Independent Events are Independent of Complement ==
Let $A$ and $B$ be events in a probability space $\struct {\Omega, \Sigma, \Pr}$.
$A$ and $B$ are independent $\Omega \setminus A$ and $\Omega \setminus B$ are independent.
== Proof ==
Let $A$ and $B$ be independent.
Then from Independent Events are Independent of Complement, $A$ and $\Omega \setminus B$ are independent.
Setting $A' = \Omega \setminus B$ and $B' = A$, we see clearly that $A'$ and $B'$ are independent.
So from the main result, $A'$ and $\Omega \setminus B'$ are independent.
That is, $\Omega \setminus B$ and $\Omega \setminus A$ are independent.
The "only if" part of the result follows directly from Relative Complement of Relative Complement and another application of this result.
Category:Independent Events
Independent Events are Independent of Complement/General Result

== Theorem ==
Let $A_1, A_2, \ldots, A_m$ be events in a probability space $\struct {\Omega, \Sigma, \Pr}$.
Then $A_1, A_2, \ldots, A_m$ are independent $\Omega \setminus A_1, \Omega \setminus A_2, \ldots, \Omega \setminus A_m$ are also independent.
== Proof ==
Proof by induction:
For all $n \in \N: n \ge 2$, let $\map P n$ be the proposition:
:$A_1, A_2, \ldots, A_n$ are independent $\Omega \setminus A_1, \Omega \setminus A_2, \ldots, \Omega \setminus A_n$ are independent.
=== Basis for the Induction ===
$\map P 2$ is the case:
:$A_1$ and $A_2$ are independent $\Omega \setminus A_1$ and $\Omega \setminus A_2$ are independent.
This is proved in Independent Events are Independent of Complement: Corollary.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$A_1, A_2, \ldots, A_k$ are independent $\Omega \setminus A_1, \Omega \setminus A_2, \ldots, \Omega \setminus A_k$ are independent.
Then we need to show:
:$A_1, A_2, \ldots, A_{k + 1}$ are independent $\Omega \setminus A_1, \Omega \setminus A_2, \ldots, \Omega \setminus A_{k + 1}$ are independent.
=== Induction Step ===
This is our induction step.
Suppose $A_1, A_2, \ldots, A_{k + 1}$ are independent.
Then:
So we see that $\ds \bigcap_{i \mathop = 1}^k A_i$ and $A_{k + 1}$ are independent.
So $\ds \bigcap_{i \mathop = 1}^k A_i$ and $\Omega \setminus A_{k + 1}$ are independent.
So, from the above results, we can see that $\Omega \setminus A_1, \Omega \setminus A_2, \ldots, \Omega \setminus A_{k + 1}$ are independent.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
The reverse implication follows directly.
Therefore:
:$A_1, A_2, \ldots, A_n$ are independent $\Omega \setminus A_1, \Omega \setminus A_2, \ldots, \Omega \setminus A_n$ are independent.
== Sources ==
* : $\S 1.7$: Independent Events: Exercise $23$
Category:Independent Events
Independent Set can be Augmented by Larger Independent Set

== Theorem ==
Let $M = \struct{S, \mathscr I}$ be a matroid.
Let $X, Y \in \mathscr I$ such that:
:$\size X < \size Y$
Then there exists non-empty $Z \subseteq Y \setminus X$ such that:
:$X \cup Z \in \mathscr I$
:$\size {X \cup Z} = \size Y$
=== Corollary ===
== Proof ==
Let $\mathscr Z = \set {Z \subseteq Y \setminus X : X \cup Z \in \mathscr I}$
Note that $\O \in \mathscr Z $
So $\mathscr Z \ne \O$
Let $Z_0 \in \mathscr Z : \size {Z_0} = \max \set {\size Z : Z \in \mathscr Z}$
:
:$\size {X \cup Z_0} < \size Y$
By matroid axiom $(\text I 3)$:
:$\exists y \in Y \setminus \paren{X \cup Z_0} : X \cup Z_0 \cup \set y \in \mathscr I$
By choice of $Z_0$ and $y$:
:$Z_0 \cup \set y \subseteq Y \setminus X$
So:
:$Z_0 \cup \set y \in \mathscr Z$
Then:
This contradicts the choice of $Z_0$.
It follows that:
From Finite Set Contains Subset of Smaller Cardinality:
:$\exists Z \subseteq Z_0 : \size Z = \size Y - \size X$
Then:
We have:
== Sources ==
* Chapter $1.$ $\S 5.$ Properties of independent sets and bases, Theorem $5.1$
Category:Matroid Independent Subsets
Independent Set can be Augmented by Larger Independent Set/Corollary

== Theorem ==
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $X \subseteq S$ be an independent subset of $M$.
Let $B \subseteq S$ be a base of $M$.
Then:
:$\exists Z \subseteq B \setminus X : \card{X \cup Z} = \card B : X \cup Z$ is a base of $M$
== Proof ==
From Cardinality of Independent Set of Matroid is Smaller or Equal to Base:
:$\card X \le \card B$
=== Case 1: $\card X < \card B$ ===
From Independent Set can be Augmented by Larger Independent Set:
:$\exists Z \subseteq B \setminus X : X \cup Z \in \mathscr I : \card {X \cup Z} = \card B$
=== Case 2: $\card X = \card B$ ===
Let $Z = \O$.
Then:
:$Z \subseteq B \setminus X : X \cup Z \in \mathscr I : \card {X \cup Z} = \card B$
From Independent Subset is Base if Cardinality Equals Cardinality of Base:
:$X \cup Z$ is a base of $M$
Category:Matroid Independent Subsets
Independent Sets of Dual Matroid

== Theorem == 
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $\mathscr B$ be the set of bases of the matroid $M$.
Then the independent subsets of the dual $M^*$ of $M$ is:
:$\mathscr I^* = \set{X \subseteq S : \exists B \in \mathscr B : X \subseteq \paren{S \setminus B}}$
== Proof ==
By definition of the dual matroid the set of bases $\mathscr B^*$ of the dual $M^*$ of $M$:
:$\mathscr B^* = \set{S \setminus B : B \in \mathscr B}$
From Characterization of Matroid Independent Sets in Terms of Bases:
:$\mathscr I^* = \set{X \subseteq S : \exists B \in \mathscr B : X \subseteq \paren{S \setminus B}}$
Category:Dual Matroids
Category:Matroid Independent Subsets
Independent Subset Contains No Dependent Subset

== Theorem ==
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $X \subseteq S$ be any independent subset of $M$.
Then:
:No dependent subset $D$ of $M$ is a subset of $X$.
=== Corollary 1 ===
=== Corollary 2 ===
=== Corollary 3 ===
== Proof ==
By definition of independent subset:
:$X \in \mathscr I$
By definition of matroid, specifically matroid axiom $( \text I 2)$:
:$\forall Y \subseteq X : Y \in \mathscr I$
By definition of dependent subset:
:$\forall Y \subseteq X : Y$ is not a dependent subset
Category:Matroid Independent Subsets
Category:Matroid Dependent Subsets
Category:Independent Subset Contains No Dependent Subset