avewright/proofwiki-math huggingface dataset:
Theorem: Tschirnhaus Transformation yields Depressed Polynomial

Let $\map f x$ be a polynomial of order $n$:
:$a_n x^n + a_{n - 1} x^{n - 1} + \cdots + a_1 x + a_0$
Then the Tschirnhaus transformation:
$y = x + \dfrac {a_{n - 1} } {n a_n}$
converts $f$ into a depressed polynomial:
:$b_n y^n + b_{n - 1} y^{n - 1} + \cdots + b_1 y + b_0$
where $b_{n - 1} = 0$.

Proof:
Substituting $y = x + \dfrac {a_{n - 1} } {n a_n}$ gives us:
:$x = y - \dfrac {a_{n - 1} } {n a_n}$
By the Binomial Theorem:
:$a_n x^n = a_n \paren {y^n - \dfrac {a_{n - 1} } {a_n} y^{n - 1} + \map {f'_{n - 2} } y}$
where $\map {f'_{n - 2} } y$ is a polynomial in $y$ of order $n - 2$.
Now we note that:
:$a_{n - 1} x^{n-  1} = a_{n - 1} y^{n - 1} - \map {f' '_{n - 2} } y$
where $\map {f' '_{n - 2} } y$ is another polynomial in $y$ of order $n - 2$.
The terms in $y^{n - 1}$ cancel out.
Hence the result.
{{qed}}
{{Namedfor|Ehrenfried Walther von Tschirnhaus|cat = Tschirnhaus}}
Category:Polynomial Theory
Category:Tschirnhaus Transformations
fswdiqtmhj0n92kp4vtrifdgu8f6krd
Theorem: Ring of Sets is Semiring of Sets

Let $\RR$ be a ring of sets.
Then $\RR$ is also a semiring of sets.

Proof:
{{Explain|It is not clear which of the definitions in Definition:Ring of Sets is being used. In any case, this proof seems to just address axiom (3) in Definition:Semiring of Sets. An explanation (even if trivial) of why (1) and (2) hold is missing. Especially because the explanation depends on which definition of ring of sets is being used.}}
Let $A \in \RR$.
Suppose $A_1 \subseteq A$.
Let $A_2 = A \setminus A_1$, where $A \setminus A_1$ denotes set difference.
By definition, $A_2$ is then the relative complement of $A_1$ with respect to $A$.
From Union with Relative Complement it then follows that $A_1 \cup A_2 = A$.
By Ring of Sets Closed under Various Operations:
:$A \setminus A_1 = A_2 \in \RR$
But by Set Difference Intersection with Second Set is Empty Set:
:$\paren {A \setminus A_1} \cap A_1 = \O$
Hence for any given $A$ for which we have $A_1 \subseteq A$, we can represent $A$ as the finite expansion $A_1 \cup A_2$ such that $A_1 \cap A_2 = \O$ and $A_1, A_2 \in \RR$
Thus, by definition, $\RR$ is a semiring of sets.
{{qed}}
Category:Rings of Sets
Category:Semirings of Sets
t8dkv5taq5aspzt2rfmamcbrbgyvjdn
Theorem: Set of All Real Intervals is Semiring of Sets

Let $\mathbb S$ be the set of all real intervals.
Then $\mathbb S$ is a semiring of sets, but is '''not''' a ring of sets.

Proof:
Consider the types of real interval that exist.
In the following, $a, b \in \R$ are real numbers.
There are:
* Closed intervals:
** $\closedint a b = \set {x \in \R: a \le x \le b}$
* Open intervals:
** $\openint a b = \set {x \in \R: a < x < b}$
* Half-open intervals:
** $\hointr a b = \set {x \in \R: a \le x < b}$
** $\hointl a b = \set {x \in \R: a < x \le b}$
* Unbounded closed and unbounded open intervals:
** $\hointr a {+\infty} = \set {x \in \R: a \le x}$
** $\hointl {-\infty} a = \set {x \in \R: x \le a}$
** $\openint a {+\infty} = \set {x \in \R: a < x}$
** $\openint {-\infty} a = \set {x \in \R: x < a}$
** $\openint {-\infty} {+\infty} = \R$
* The empty interval:
** $\openint a a = \set {x \in \R: a < x < a} = \O$
* Singleton intervals:
** $\closedint a a = \set {x \in \R: a \le x \le a} = \set a$
Theorem: Ring of Sets Generated by Semiring

Let $\SS$ be a semiring of sets.
Let $\map \RR \SS$ be the minimal ring generated by $\SS$.
Let $\LL$ be the system of sets $A$ with the finite expansions:
:$\ds A = \bigcup_{k \mathop = 1}^n A_k$
with respect to the sets $A_k \in \SS$.
Then $\LL = \map \RR \SS$.

Proof:
First we need to show that $\LL$ is a ring of sets.
Let $A, B \in \LL$.
Then by definition of $\LL$, they have expansions:
{{begin-eqn}}
{{eqn | l = A
      | r = \bigcup_{i \mathop = 1}^m A_i
      | c = where $A_i \in \SS$
}}
{{eqn | l = B
      | r = \bigcup_{j \mathop = 1}^n B_j
      | c = where $B_j \in \SS$
}}
{{end-eqn}}
Since $\SS$ is a semiring of sets, we have:
:$C_{ij} = A_i \cap B_j \in \SS$
By Pairwise Disjoint Subsets in Semiring Part of Partition, there exist finite expansions:
{{begin-eqn}}
{{eqn | l = A_i
      | r = \paren {\bigcup_{j \mathop = 1}^n C_{i j} } \cup \paren {\bigcup_{k \mathop = 1}^{r_i} D_{i k} }
      | c = where $D_{i k} \in \SS$
}}
{{eqn | l = B_j
      | r = \paren {\bigcup_{i \mathop = 1}^m C_{i j} } \cup \paren {\bigcup_{l \mathop = 1}^{s_j} E_{j l} }
      | c = where $E_{j l} \in \SS$
}}
{{end-eqn}}
From these, it follows that $A \cap B$ and $A \ast B$ have the finite expansions:
{{begin-eqn}}
{{eqn | l = A \cap B
      | r = \bigcup_{i, \ j} C_{i j}
      | c = 
}}
{{eqn | l = A \ast B
      | r = \paren {\bigcup_{i, \ k} D_{i k} } \cup \paren {\bigcup_{j, \ l} E_{j l} }
      | c = 
}}
{{end-eqn}}
Hence both $A \cap B \in \LL$ and $A \ast B \in \LL$.
So by definition, $\LL$ is a ring of sets.
From the details of the above construction, the fact that $\LL$ is the '''minimal''' ring generated by $\SS$ follows immediately.
{{qed}}
Category:Rings of Sets
Category:Semirings of Sets
5okbaw6ibuidwoh2q9p5fyb74zy5o7s
Theorem: Ring of Sets is Closed under Finite Intersection

Let $\RR$ be a ring of sets.
Let $A_1, A_2, \ldots, A_n \in \RR$.
Then:
:$\ds \bigcap_{j \mathop = 1}^n A_j \in \RR$

Proof:
Proof by induction:
For all $n \in \N_{>0}$, let $\map P n$ be the proposition:
:$\ds \bigcap_{j \mathop = 1}^n A_j \in \RR$
$\map P 1$ is true, as this just says $A_1 \in \RR$.
Theorem: Sigma-Algebra is Delta-Algebra

A $\sigma$-algebra is also a $\delta$-algebra.

Proof:
Let $\SS$ be a $\sigma$-algebra whose unit is $\mathbb U$.
Let $A_1, A_2, \ldots$ be a countably infinite collection of elements of $\SS$.
Then:
{{begin-eqn}}
{{eqn | q = \forall i
      | l = \mathbb U \setminus A_i
      | o = \in
      | r = \SS
      | c = $\SS$ is closed under relative complement with $\mathbb U$
}}
{{eqn | ll= \leadsto
      | l = \bigcup_{i \mathop = 1}^\infty \paren {\mathbb U \setminus A_i}
      | o = \in
      | r = \SS
      | c = $\SS$ is closed under countable unions
}}
{{eqn | ll= \leadsto
      | l = \mathbb U \setminus \bigcap_{i \mathop = 1}^\infty A_i
      | o = \in
      | r = \SS
      | c = De Morgan's Laws
}}
{{eqn | ll= \leadsto
      | l = \bigcap_{i \mathop = 1}^\infty A_i
      | o = \in
      | r = \SS
      | c = $\SS$ is closed under relative complement with $\mathbb U$
}}
{{end-eqn}}
Thus $\SS$ is a $\delta$-algebra.
{{qed}}
Theorem: Addition Law of Probability

Let $\Pr$ be a probability measure on an event space $\Sigma$.
Let $A, B \in \Sigma$.
The probability of the occurrence of the union of $A$ and $B$ can be evaluated as:
:$\map \Pr {A \cup B} = \map \Pr A + \map \Pr B - \map \Pr {A \cap B}$
That is, the probability of either event occurring equals the sum of their individual probabilities less the probability of them both occurring.
This is known as the '''addition law of probability'''.

Proof:
By definition, a probability measure is a measure.
Hence, again by definition, it is a countably additive function.
By Measure is Finitely Additive Function, we have that $\Pr$ is an additive function.
So Additive Function is Strongly Additive can be applied directly.
{{qed}}
Theorem: Addition Law of Probability

Let $\Pr$ be a probability measure on an event space $\Sigma$.
Let $A, B \in \Sigma$.
The probability of the occurrence of the union of $A$ and $B$ can be evaluated as:
:$\map \Pr {A \cup B} = \map \Pr A + \map \Pr B - \map \Pr {A \cap B}$
That is, the probability of either event occurring equals the sum of their individual probabilities less the probability of them both occurring.
This is known as the '''addition law of probability'''.

Proof:
From Set Difference and Intersection form Partition:
:$A$ is the union of the two disjoint sets $A \setminus B$ and $A \cap B$
:$B$ is the union of the two disjoint sets $B \setminus A$ and $A \cap B$.
So, by the definition of probability measure:
:$\map \Pr A = \map \Pr {A \setminus B} + \map \Pr {A \cap B}$
:$\map \Pr B = \map \Pr {B \setminus A} + \map \Pr {A \cap B}$
From Set Difference is Disjoint with Reverse:
:$\paren {A \setminus B} \cap \paren {B \setminus A} = \O$
Hence:
{{begin-eqn}}
{{eqn | l = \map \Pr A + \map \Pr B
      | r = \map \Pr {A \setminus B} + 2 \map \Pr {A \cap B} + \map \Pr {B \setminus A}
      | c = 
}}
{{eqn | r = \map \Pr {\paren {A \setminus B} \cup \paren {A \cap B} \cup \paren {B \setminus A} } + \map \Pr {A \cap B}
      | c = Set Differences and Intersection form Partition of Union
}}
{{eqn | r = \map \Pr {A \cup B} + \map \Pr {A \cap B}
      | c = 
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Cardinality is Additive Function

Let $S$ be a finite set.
Let $\powerset S$ be the power set of $S$.
The function $C: \powerset S \to \R$, where $C$ is defined as the cardinality of a set, is an additive function.

Proof:
We have that $\powerset S$ is an algebra of sets.
{{ProofWanted}}
Category:Set Systems
r3r1nsnaic0xb44ofi9q9och3iiqjos
Theorem: Finite Union of Sets in Additive Function

Let $\AA$ be an algebra of sets.
Let $f: \AA \to \overline {\R}$ be an additive function.
Let $A_1, A_2, \ldots, A_n$ be any finite collection of pairwise disjoint elements of $\AA$.
Then:
:$\ds \map f {\bigcup_{i \mathop = 1}^n A_i} = \sum_{i \mathop = 1}^n \map f {A_i}$
That is, for any collection of pairwise disjoint elements of $\AA$, $f$ of their union equals the sum of $f$ of the individual elements.

Proof:
Proof by induction:
In the below, we assume that $A_1, A_2, \ldots$ are all pairwise disjoint elements of $\AA$.
For all $n \in \N_{>0}$, let $\map P n$ be the proposition:
:$\ds \map f {\bigcup_{i \mathop = 1}^n A_i} = \sum_{i \mathop = 1}^n \map f {A_i}$
$\map P 1$ is the case:
:$\ds \map f {\bigcup_{i \mathop = 1}^1 A_i} = \map f {A_1} = \sum_{i \mathop = 1}^1 \map f {A_i}$
Thus $\map P 1$ is seen to hold.
Theorem: Measure is Finitely Additive Function

Let $\Sigma$ be a $\sigma$-algebra on a set $X$.
Let $\mu: \Sigma \to \overline {\R}$ be a measure on $\Sigma$.
Then $\mu$ is finitely additive.

Proof:
From the definition of a measure, $\mu$ is countably additive.
From Countably Additive Function also Finitely Additive, $\mu$ is finitely additive.
{{qed}}
Theorem: Finite Union of Sets in Subadditive Function

Let $\AA$ be an algebra of sets.
Let $f: \AA \to \overline \R$ be a subadditive function.
Let $A_1, A_2, \ldots, A_n$ be any finite collection of elements of $\AA$.
Then:
:$\ds \map f {\bigcup_{i \mathop = 1}^n A_i} \le \sum_{i \mathop = 1}^n \map f {A_i}$
That is, for any finite collection of elements of $\AA$, $f$ of their union is less than or equal to the sum of $f$ of the individual elements.

Proof:
Proof by induction:
In the below, let $A_1, A_2, \ldots$ all be elements of $\AA$.
For all $n \in \N_{>0}$, let $\map P n$ be the proposition:
:$\ds \map f {\bigcup_{i \mathop = 1}^n A_i} \le \sum_{i \mathop = 1}^n \map f {A_i}$
$\map P 1$ is trivially true, as this just says $\map f {A_1} \le \map f {A_1}$.
Theorem: Additive Function on Empty Set is Zero

Let $\AA$ be an algebra of sets.
Let $f: \AA \to \overline \R$ be an additive function on $\AA$.
Then $\map f \O = 0$.

Proof:
From Properties of Algebras of Sets:
:$\O \in \AA$
Let $X \in \AA$.
Then:
{{begin-eqn}}
{{eqn | l = X \cap \O
      | r = \O
      | c = Intersection with Empty Set
}}
{{eqn | ll= \leadsto
      | l = \map f X + \map f \O
      | r = \map f {X \cup \O}
      | c = {{Defof|Additive Function (Measure Theory)}}
}}
{{eqn | r = \map f X
      | c = Union with Empty Set
}}
{{eqn | ll= \leadsto
      | l = \map f \O
      | r = 0
}}
{{end-eqn}}
{{qed}}
Category:Set Systems
2i1r2ut9eh3akmdgn0x3glp1u66gsoj
Theorem: Additive Function is Strongly Additive

Let $\SS$ be an algebra of sets.
Let $f: \SS \to \overline \R$ be an additive function on $\SS$.
Then $f$ is also strongly additive.
That is:
:$\forall A, B \in \SS: \map f {A \cup B} + \map f {A \cap B} = \map f A + \map f B$

Proof:
From Set Difference and Intersection form Partition:
:$A$ is the union of the two disjoint sets $A \setminus B$ and $A \cap B$
:$B$ is the union of the two disjoint sets $B \setminus A$ and $A \cap B$.
So, by the definition of additive function:
:$\map f A = \map f {A \setminus B} + \map f {A \cap B}$
:$\map f B = \map f {B \setminus A} + \map f {A \cap B}$
We also have from Set Difference is Disjoint with Reverse that:
:$\paren {A \setminus B} \cap \paren {B \setminus A} = \O$
From Sum of Additive Function Values is Well-Defined, it follows that $\map f A + \map f B$ is well-defined.
Hence:
{{begin-eqn}}
{{eqn | l = \map f A + \map f B
      | r = \map f {A \setminus B} + 2 \map f {A \cap B} + \map f {B \setminus A}
}}
{{eqn | r = \map f {\paren {A \setminus B} \cup \paren {A \cap B} \cup \paren {B \setminus A} } + \map f {A \cap B}
      | c = Set Differences and Intersection form Partition of Union
}}
{{eqn | r = \map f {A \cup B} + \map f {A \cap B}
      | c = {{Defof|Set Union}}
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Additive Function is Strongly Additive

Let $\SS$ be an algebra of sets.
Let $f: \SS \to \overline \R$ be an additive function on $\SS$.
Then $f$ is also strongly additive.
That is:
:$\forall A, B \in \SS: \map f {A \cup B} + \map f {A \cap B} = \map f A + \map f B$

Proof:
Recall that $\sqcup$ denotes the disjoint union.
First, since:
{{begin-eqn}}
{{eqn | l = A \cup B
      | r = A \cup \paren {B \setminus A}
      | c = Set Difference Union Second Set is Union
}}
{{eqn | r = A \sqcup \paren {B \setminus A}
      | c = in view of {{Defof|Set Difference}}
}}
{{end-eqn}}
we have:
:$\paren 1 : \quad \map f {A \cup B} = \map f A + \map f {B \setminus A}$
Secondly, since
{{begin-eqn}}
{{eqn | l = B
      | r = \paren {B \setminus A} \cup \paren {A \cap B}
      | c = Set Difference Union Intersection
}}
{{eqn | r = \paren {B \setminus A} \sqcup \paren {A \cap B}
      | c = Set Difference and Intersection are Disjoint
}}
{{end-eqn}}
we have:
:$\paren 2 : \quad \map f B = \map f {B \setminus A} + \map f {A \cap B}$
On the other hand:
{{begin-eqn}}
{{eqn | l = A \cup B
      | r = \paren {A \cap B} \cup \paren {A \cup B}
      | c = as $A \cap B \subseteq A \cup B$
}}
{{eqn | r = \paren {A \cap B} \cup \paren { \paren {A \cup B} \setminus \paren {A \cap B } }
      | c = Set Difference Union Second Set is Union
}}
{{eqn | r = \paren {A \cap B} \sqcup \paren { \paren {A \cup B} \setminus \paren {A \cap B } }
      | c = in view of {{Defof|Set Difference}}
}}
{{end-eqn}}
so that:
:$\map f {A \cup B} = \map f {A \cap B} + \map f {\paren {A \cup B} \setminus \paren {A \cap B} }$
In particular, we have neither:
:$\map f {A \cup B} = + \infty \land \map f {A \cap B} = - \infty$
nor:
:$\map f {A \cup B} = - \infty \land \map f {A \cap B} = + \infty$
Thus the sum in $\overline {\R}$:
:$\map f {A \cup B} + \map f {A \cap B}$
is well-defined.
Finally:
{{begin-eqn}}
{{eqn | l = \map f {A \cup B} + \map f {A \cap B}
      | r = \map f A + \map f {B \setminus A} + \map f {A \cap B}
      | c = by $\paren 1$
}}
{{eqn | r = \map f A + \map f B
      | c = by $\paren 2$
}}
{{end-eqn}}
{{qed}}
Theorem: Set Difference is Disjoint with Reverse

:$\paren {S \setminus T} \cap \paren {T \setminus S} = \O$

Proof:
We assume that $S, T \subseteq \mathbb U$ where $\mathbb U$ is the universal set.
Then we can use the definition of Set Difference as Intersection with Complement.
{{begin-eqn}}
{{eqn | o =
      | r = \paren {S \setminus T} \cap \paren {T \setminus S}
      | c = 
}}
{{eqn | r = \paren {S \cap \map \complement T} \cap \paren {T \cap \map \complement S}
      | c = Set Difference as Intersection with Complement
}}
{{eqn | r = \paren {S \cap \map \complement S} \cap \paren {T \cap \map \complement T}
      | c = Intersection is Associative and Intersection is Commutative
}}
{{eqn | r = \O \cap \O
      | c = Intersection with Complement
}}
{{eqn | r = \O
      | c = Empty Set Disjoint with Itself
}}
{{end-eqn}}
{{qed}}
Category:Set Difference
Category:Set Intersection
dz2u8m1yc1yvvdlitfp4gxzelf5994a
Theorem: Measure is Monotone

Let $\struct {X, \Sigma, \mu}$ be a measure space.
Then $\mu$ is monotone, that is:
:$\forall E, F \in \Sigma: E \subseteq F \implies \map \mu E \le \map \mu F$

Proof:
A direct corollary of Non-Negative Additive Function is Monotone.
{{qed}}
Theorem: Measure is Monotone

Let $\struct {X, \Sigma, \mu}$ be a measure space.
Then $\mu$ is monotone, that is:
:$\forall E, F \in \Sigma: E \subseteq F \implies \map \mu E \le \map \mu F$

Proof:
From Set Difference Union Second Set is Union:
:$A \cup B = \paren {B \setminus A} \cup A$
From Set Difference Intersection with Second Set is Empty Set:
:$\paren {B \setminus A} \cap A = \O$
From the Addition Law of Probability:
:$\map \Pr {A \cup B} = \map \Pr {B \setminus A} + \map \Pr A$
From Union with Superset is Superset:
:$A \subseteq B \implies A \cup B = B$
Thus:
:$\map \Pr B = \map \Pr {B \setminus A} + \map \Pr A$
By definition of probability measure:
:$\map \Pr {B \setminus A} \ge 0$
from which it follows that:
:$\map \Pr B \ge \map \Pr A$
{{qed}}
Theorem: Measure is Monotone

Let $\struct {X, \Sigma, \mu}$ be a measure space.
Then $\mu$ is monotone, that is:
:$\forall E, F \in \Sigma: E \subseteq F \implies \map \mu E \le \map \mu F$

Proof:
As by definition a probability measure is a measure, we can directly use the result Measure is Monotone.
{{qed}}
Theorem: Countably Additive Function also Finitely Additive

Let $\AA$ be a $\sigma$-algebra.
Let $\overline \R$ denote the extended set of real numbers.
Let $f: \AA \to \overline \R$ be a countably additive function.
Then $f$ is a finitely additive function.

Proof:
We have that $f$ is defined as countably additive {{iff}}:
:$\ds \map f {\bigcup_{i \mathop \ge 1} A_i} = \sum_{i \mathop \ge 1} \map f {A_i}$
where $\sequence {A_i}$ is any sequence of pairwise disjoint elements of $\AA$.
We need to show that:
:$\ds \forall n \in \N: \map f {\bigcup_{i \mathop = 1}^n A_i} = \sum_{i \mathop = 1}^n \map f {A_i}$
The claim is trivial if $f=+\infty$ or $f=-\infty$, constantly.
Thus we assume $\map f \O = 0$ by Countably Additive Function Dichotomy by Empty Set.
Let $n \in \N$ be any arbitrary natural number.
Let $\sequence {B_i}$ be the sequence of pairwise disjoint elements of $\AA$ defined as:
:$B_i = \begin{cases}
A_i & : i \le n \\
\O & : i > n
\end{cases}$
It follows that:
:$\ds \bigcup_{i \mathop \ge 1} B_i = \bigcup_{i \mathop = 1}^n A_i$
Thus:
{{begin-eqn}}
{{eqn | l = \map f {\bigcup_{i \mathop = 1}^n A_i}
      | r = \map f {\bigcup_{i \mathop \ge 1} B_i}
}}
{{eqn | r = \sum_{i \mathop \ge 1} \map f {B_i}
}}
{{eqn | r = \sum_{i \mathop = 1}^n \map f {A_i} + \sum_{i \mathop > n} \map f \O
}}
{{eqn | r = \sum_{i \mathop = 1}^n \map f {A_i}
      | c = as $\map f \O = 0$
}}
{{end-eqn}}
Hence the result.
{{qed}}
Category:Set Systems
Category:Measure Theory
s6d5os4bvlt6qtulsco4pjfor0d0zvx
Theorem: Countably Additive Function of Null Set

Let $\AA$ be a $\sigma$-algebra.
Let $\overline \R$ denote the extended set of real numbers.
Let $f: \AA \to \overline \R$ be a function be a countably additive function.
Suppose that there exists at least one $A \in \AA$ where $\map f A$ is a finite number.
Then:
: $\map f \O = 0$

Proof:
Suppose that $A \in \AA$ such that $\map f A$ is a finite number.
So, let $\map f A = x$.
Consider the sequence $\sequence {S_i} \subseteq \AA$ defined as:
:$\forall i \in \N: S_i = \begin{cases}  A & : i = 0 \\  \O & : i > 0  \end{cases}$
Then:
:$\ds \bigcup_{i \mathop \ge 0} S_i = A$
Hence:
{{begin-eqn}}
{{eqn | l = \map f A
      | r = x
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \map f {\bigcup_{i \mathop \ge 0} S_i}
      | r = x
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \sum_{i \mathop \ge 0} \map f {S_i}
      | r = x
      | c = {{Defof|Countably Additive Function}}
}}
{{eqn | ll= \leadsto
      | l = \map f A + \sum_{i \mathop > 0} \map f \O
      | r = x
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \sum_{i \mathop > 0} \map f \O
      | r = 0
      | c = 
}}
{{end-eqn}}
It follows directly that:
: $\map f \O = 0$
{{qed}}
Theorem: Non-Negative Additive Function is Monotone

Let $\SS$ be an algebra of sets.
Let $f: \SS \to \overline \R$ be an additive function, that is:
:$\forall A, B \in \SS: A \cap B = \O \implies \map f {A \cup B} = \map f A + \map f B$
If $\forall A \in \SS: \map f A \ge 0$, then $f$ is monotone, that is:
:$A \subseteq B \implies \map f A \le \map f B$

Proof:
Let $A \subseteq B$.
Then:
{{begin-eqn}}
{{eqn | l = B
      | r = \paren {B \setminus A} \cup \paren {A \cap B}
      | c = Set Difference Union Intersection
}}
{{eqn | r = \paren {B \setminus A} \cup A
      | c = Intersection with Subset is Subset
}}
{{eqn | l = \O
      | r = \paren {B \setminus A} \cap A
      | c = Set Difference Intersection with Second Set is Empty Set
}}
{{eqn | l = 0
      | o = \le
      | r = \map f {B \setminus A}
      | c = {{hypothesis}}
}}
{{eqn | ll= \leadsto
      | l = \map f A
      | o = \le
      | r = \map f {B \setminus A} + \map f A
}}
{{eqn | ll= \leadsto
      | l = \map f A
      | o = \le
      | r = \map f B
      | c = {{Defof|Additive Function (Measure Theory)}}
}}
{{end-eqn}}
{{qed}}
Category:Set Systems
0dcuuvldzdj5za7td6vtrh6a4du5stt
Theorem: Power Set is Sigma-Algebra

The power set of a set is a sigma-algebra.

Proof:
Let $S$ be a set, and let $\powerset S$ be its power set.
We have that a power set is an algebra of sets, and so:
:$(1): \quad \forall A, B \in \powerset S: A \cup B \in \powerset S$
:$(2): \quad \relcomp S A \in \powerset S$
Let $\sequence {A_i}$ be a countably infinite sequence of sets in $\powerset S$.
Then from Power Set is Closed under Countable Unions:
:$\ds \bigcup_{i \mathop \in \N} A_i \in \powerset S$
So, by definition, $\powerset S$ is a sigma-algebra.
{{qed}}
Theorem: Probability Measure on Equiprobable Outcomes

Let $\struct {\Omega, \Sigma, \Pr}$ be an equiprobability space.
Let $\card \Omega = n$.
Then:
:$\forall \omega \in \Omega: \map \Pr \omega = \dfrac 1 n$
:$\forall A \subseteq \Omega: \map \Pr A = \dfrac {\card A} n$.

Proof:
By definition, $\map \Pr {\omega_i} = \map \Pr {\omega_j}$ for all $\omega_i, \omega_j \in \Omega$.
So let $\map \Pr {\omega_i} = p$.
Also, by definition of probability measure, we have:
:$\map \Pr \Omega = 1$
We have that $\set {\omega_i} \cap \set {\omega_j} = \O$ when $i \ne j$ and so, by definition of definition of probability measure:
:$\map \Pr {\set {\omega_i} \cup \set {\omega_j} } = \map \Pr {\set {\omega_i} } + \map \Pr {\set {\omega_j} }$
Using the fact that $\ds \Omega = \bigcup_{i \mathop = 1}^n \set {\omega_i}$:
:$\ds \map \Pr \Omega = \sum_{i \mathop = 1}^n \map \Pr {\set {\omega_i} } = \sum_{i \mathop = 1}^n p = n p$
But we have that $\map \Pr \Omega = 1$, and so $1 = n p$.
Hence:
:$\forall \omega \in \Omega: \map \Pr \omega = \dfrac 1 n$
Now consider $A \subseteq \Omega$.
Let the cardinality of $A$ be $k$, that is $\card A = k$.
Thus:
:$\ds \map \Pr A = \sum_i \map \Pr {\omega_i} \sqbrk {\omega_i \in A}$
where $\sqbrk {\omega_i \in A}$ uses Iverson's convention.
Hence:
:$\map \Pr A = k p$
and so:
:$\map \Pr A = \dfrac {\card A} n$
{{qed}}
Category:Probability Theory
qsq264ohyabwaxnluz7vp40wwwcdsgs