avewright/proofwiki-math huggingface dataset:
Theorem: Vitali Set Existence Theorem

There exists a set of real numbers which is not Lebesgue measurable.

Proof:
=== Lemma ===
{{:Vitali Set Existence Theorem/Lemma}}{{qed|lemma}}
Let $\map \mu X$ denote the Lebesgue measure of a set $X$ of real numbers.
We have that:
{{begin-itemize}}
{{item|(1):|$\map \mu X$ is a countably additive function}}
{{item|(2):|$\map \mu X$ is translation invariant}}
{{item|(3):|From Measure of Interval is Length, $\map \mu {\closedint a b} {{=}} b - a$ for every closed interval $\closedint a b$}}
{{end-itemize}}
For all real numbers in the closed unit interval $\mathbb I = \closedint 0 1$, define the relation $\sim$ such that:
:$\forall x, y \in \mathbb I: x \sim y \iff x - y \in \Q$
where $\Q$ is the set of rational numbers.
That is, $x \sim y$ {{iff}} their difference is rational.
By the {{Lemma|Vitali Set Existence Theorem}}, $\sim$ is an equivalence relation.
For each $x \in \mathbb I$, let $\eqclass x \sim$ denote the equivalence class of $x$ under $\sim$.
Let us use the Axiom of Choice to create a set $M \subset \mathbb I$ containing exactly $1$ element from each equivalence class.
Hence:
:for each $x \in \R$ there exists a unique $y \in M$ and $r \in \Q$ such that $x = y + r$.
Let:
:$M_r = \set {y + r: y \in M}$
for each $r \in \Q$.
Thus $\R$ is partitioned into countably many disjoint sets:
:$(1): \quad \ds \R = \bigcup \set {M_r: r \in \Q}$
{{AimForCont}} $M$ were Lebesgue measurable.
First, $\map \mu M = 0$ is impossible, because from $(1)$ this would mean  $\map \mu \R = 0$.
Suppose $\map \mu M > 0$.
Then:
{{begin-eqn}}
{{eqn | l = \closedint 0 2
      | o = \supseteq
      | r = \bigcup \set {M_r: r \in \Q \land 0 \le r \le 1}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \map \mu {\closedint 0 2}
      | o = \ge
      | r = \map \mu {\bigcup \set {M_r: r \in \Q \land 0 \le r \le 1} }
      | c = Measure is Monotone
}}
{{eqn | r = \sum_{\substack {r \mathop \in \Q \\ 0 \mathop \le r \mathop \le 1} } \map \mu {M_r}
      | c = Axiom $(2)$ of Measure
}}
{{eqn | r = \infty
      | c = as each $M_r$ would have to have the same measure as $M$
}}
{{end-eqn}}
So $\map \mu M > 0$ is also impossible.
Hence $M$ is not Lebesgue measurable.
{{qed}}
Theorem: Vitali Set Existence Theorem

There exists a set of real numbers which is not Lebesgue measurable.

Proof:
We construct such a set.
For $x, y \in \hointr 0 1$, define the sum modulo 1:
:$x +_1 y = \begin {cases} x + y & : x + y < 1 \\ x + y - 1 & : x + y \ge 1 \end {cases}$
Let $E \subset \hointr 0 1$ be a measurable set.
Let $E_1 = E \cap \hointr 0 {1 - x}$ and $E_2 = E \cap \hointr {1 - x} 1$.
By Measure of Interval is Length, these disjoint intervals are measurable.
By Measurable Sets form Algebra of Sets, so are these intersections $E_1$ and $E_2$.
So:
:$\map m {E_1} + \map m {E_2} = \map m E$
We have:
:$E_1 +_1 x = E_1 + x$
By Lebesgue Measure is Translation Invariant:
:$\map m {E_1 +_1 x} = \map m {E_1}$
Also:
:$E_2 +_1 x = E_2 + x - 1$
and so:
:$\map m {E_2 +_1 x} = \map m {E_2}$
Then we have:
:$\map m {E +_1 x} = \map m {E_1 +_1 x} + \map m {E_2 +_1 x} = \map m {E_1} + \map m {E_2} = \map m E$
So, for each $x \in \hointr 0 1$, the set $E +_1 x$ is measurable and:
:$\map m {E + x} = \map m E$
Taking, as before, $x, y \in \hointr 0 1$, define the relation:
:$x \sim y \iff x - y \in \Q$
where $\Q$ is the set of rational numbers.
By Difference is Rational is Equivalence Relation, $\sim$ is an equivalence relation.
As this is an equivalence relation we can invoke the fundamental theorem on equivalence relations.
Hence $\sim$ partitions $\hointr 0 1$ into equivalence classes.
By the axiom of choice, there is a set $P$ which contains exactly one element from each equivalence class.
{{AimForCont}} $P$ is measurable.
Let $\set {r_i}_{i \mathop = 0}^\infty$ be an enumeration of the rational numbers in $\hointr 0 1$ with $r_0 = 0$.
Let $P_i := P +_1 r_i$.
Then $P_0 = P$.
Let $x \in P_i \cap P_j$.
Then:
:$x = p_i + r_i = p_j + r_j$
where $p_i, p_j$ are elements of $P$.
But then $p_i - p_j$ is a rational number.
Since $P$ has only one element from each equivalence class:
:$i = j$
The $P_i$ are pairwise disjoint.
Each real number $x \in \hointr 0 1$ is in ''some'' equivalence class and hence is equivalent to an element of $P$.
But if $x$ differs from an element in $P$ by the rational number $r_i$, then $x \in P_i$ and so:
:$\ds \bigcup P_i = \hointr 0 1$
Since each $P_i$ is a translation modulo $1$ of $P$, each $P_i$ will be measurable if $P$ is, with measure $\map m {P_i} = \map m P$.
But if this were the case, then:
:$\ds m \hointr 0 1 = \sum_{i \mathop = 1}^\infty m \paren {P_i} = \sum_{i \mathop = 1}^\infty \map m P$
Therefore:
:$\map m P = 0$ implies $m \hointr 0 1 = 0$
and:
:$\map m P \ne 0$ implies $m \hointr 0 1 = \infty$
This contradicts Measure of Interval is Length.
So the set $P$ is not measurable.
{{Qed}}
Theorem: Finite Number of Groups of Given Finite Order

Let $n \in \Z_{>0}$ be a (strictly) positive integer.
Then there exists a finite number of types of group of order $n$.

Proof:
For any group $\struct {G, \circ}$ of order $n$ and any set of $n$ elements, $X$ can be the underlying set of a group which is isomorphic to $\struct {G, \circ}$, as follows:
Choose a bijection $\phi: G \to X$.
Define the group operation $*$ on $X$ by the rule:
:$\map \phi {g_1} * \map \phi {g_2} = \map \phi {g_1 \circ g_2}$
for all $g_1, g_2 \in G$.
By definition, $\phi$ is an isomorphism.
From Isomorphism Preserves Groups it follows that $\struct {X, *}$ is a group.
Thus all groups of order $n$ of all possible types appear among all possible arrangements of binary operation.
But from Count of Binary Operations on Set, this count is $n^{\paren {n^2} }$.
This is the upper bound to the number of types of group of order $n$.
{{qed}}
Theorem: Nu of Prime Number is 1

Let $p$ be a prime number.
Then:
:$\map \nu p = 1$
where $\nu$ denotes the $\nu$ function: the number of types of group of a given order.

Proof:
Let $G_1$ and $G_2$ be groups of order $p$.
From Prime Group is Cyclic, $G_1$ and $G_2$ are both cyclic groups.
From Cyclic Groups of Same Order are Isomorphic, $G_1$ and $G_2$ are isomorphic.
Thus by definition, $G_1$ and $G_2$ are of the same type.
Hence the result.
{{qed}}
Theorem: Image of Subset under Relation equals Union of Images of Elements

Let $S$ and $T$ be sets.
Let $\RR \subseteq S \times T$ be a relation on $S \times T$.
Let $X \subseteq S$ be a subset of $S$.
Then:
:$\ds \RR \sqbrk X = \bigcup_{x \mathop \in X} \map \RR x$
where:
:$\RR \sqbrk X$ is the image of the subset $X$ under $\RR$
:$\map \RR x$ is the image of the element $x$ under $\RR$.

Proof:
By definition:
:$\RR \sqbrk X = \set {y \in T: \exists x \in X: \tuple {x, y} \in \RR}$
:$\map \RR x = \set {y \in T:\tuple {x, y} \in \RR}$
First:
{{begin-eqn}}
{{eqn | l = y 
      | o = \in
      | r = \RR \sqbrk X
}}
{{eqn | ll= \leadsto
      | q = \exists x \in X
      | l = \tuple {x, y}
      | o = \in
      | r = \RR
      | c = Definition of $\RR \sqbrk X$
}}
{{eqn | ll= \leadsto
      | l = \tuple {x, y}
      | o = \in
      | r = \bigcup_{x \mathop \in X} \set {\tuple {x, y} \in \RR}
      | c = {{Defof|Set Union}}
}}
{{eqn | ll= \leadsto
      | l = y
      | o = \in
      | r = \bigcup_{x \mathop \in X} \set {y \in T: \tuple {x, y} \in \RR}
      | c = {{Defof|Relation}}
}}
{{eqn | ll= \leadsto
      | l = y
      | o = \in
      | r = \bigcup_{x \mathop \in X} \map \RR x
      | c = Definition of $\map \RR x$
}}
{{eqn | ll= \leadsto
      | l = \RR \sqbrk X
      | o = \subseteq
      | r = \bigcup_{x \mathop \in X} \map \RR x
      | c = {{Defof|Subset}}
}}
{{end-eqn}}
Then:
{{begin-eqn}}
{{eqn | l = y
      | o = \in
      | r = \bigcup_{x \mathop \in X} \map \RR x
      | c = 
}}
{{eqn | ll= \leadsto
      | l = y
      | o = \in
      | r = \bigcup_{x \mathop \in X} \set {y \in T: \tuple {x, y} \in \RR}
      | c = Definition of $\map \RR x$
}}
{{eqn | ll= \leadsto
      | q = \exists x \in X
      | l = \tuple {x, y}
      | o = \in
      | r = \RR
      | c = {{Defof|Set Union}}
}}
{{eqn | ll= \leadsto
      | l = y 
      | o = \in
      | r = \set {y \in T: \exists x \in X: \tuple {x, y} \in \RR}
      | c = {{Defof|Relation}}
}}
{{eqn | ll= \leadsto
      | l = y
      | o = \in
      | r = \RR \sqbrk X
      | c = Definition of $\RR \sqbrk X$
}}
{{eqn | ll= \leadsto
      | l = \bigcup_{x \mathop \in X} \map \RR x
      | o = \subseteq
      | r = \RR \sqbrk X
      | c = {{Defof|Subset}}
}}
{{end-eqn}}
So:
:$\ds \bigcup_{x \mathop \in X} \map \RR x \subseteq \RR \sqbrk X$
and:
:$\ds \RR \sqbrk X \subseteq \bigcup_{x \mathop \in X} \map \RR x$
The result follows by definition of set equality.
{{qed}}
Category:Relation Theory
Category:Subsets
Category:Set Union
3jyr36zv92wq7nsd3jy534x0eq9msds
Theorem: Preimage of Subset under Relation equals Union of Preimages of Elements

Let $S$ and $T$ be sets.
Let $\RR \subseteq S \times T$ be a relation on $S \times T$.
Let $\RR^{-1} \subseteq T \times S$ be the inverse relation to $\RR$
Let $Y \subseteq T$ be a subset of $T$.
Then:
:$\RR^{-1} \sqbrk Y = \ds \bigcup_{y \mathop \in Y} \map {\RR^{-1} } y$
where:
:$\RR^{-1} \sqbrk Y$ is the preimage of the subset $Y$ under $\RR$
:$\RR^{-1} \sqbrk Y$ is the preimage of the element $y$ under $\RR$.

Proof:
By definition, $\RR^{-1} \subseteq T \times S$ is a relation on $T \times S$.
Thus Image of Subset under Relation equals Union of Images of Elements can be applied directly.
{{qed}}
Category:Relation Theory
h2kcezt8nswgbhvmdszqs4q0igjmyeo
Theorem: Preimage of Subset under Mapping equals Union of Preimages of Elements

Let $S$ and $T$ be sets.
Let $f: S \to T$ be a mapping from $S$ to $T$.
Let $f^{-1} \subseteq T \times S$ be the inverse of $f$, defined as:
:$f^{-1} = \set {\tuple {t, s}: \map f s = t}$
Let $Y \subseteq T$ be a subset of $T$.
Then:
:$\ds f^{-1} \sqbrk Y = \bigcup_{y \mathop \in Y} \map {f^{-1} } y$
where:
:$f^{-1} \sqbrk Y$ is the preimage of the subset $Y$ under $f$
:$\map {f^{-1} } y$ is the preimage of the element $y$ under $f$.

Proof:
By definition, $f^{-1} \subseteq T \times S$ is a relation on $T \times S$.
Thus Image of Subset under Relation equals Union of Images of Elements can be applied directly.
{{qed}}
Category:Preimages under Mappings
Category:Subsets
Category:Set Union
3dwfblsxgav2kxtnvq5h5v003e9y11i
Theorem: Image of Domain of Mapping is Image Set

Let $S$ and $T$ be sets.
Let $f: S \to T$ be a mapping.
The image of $S$ is the image set of $f$:
:$f \sqbrk S = \Img f$

Proof:
By definition, a mapping is a relation.
Thus Image of Domain of Relation is Image Set applies.
{{qed}}
Theorem: Image of Singleton under Mapping

Let $f: S \to T$ be a mapping.
Then the image of an element of $S$ is equal to the image of a singleton containing that element, the singleton being a subset of $S$:
:$\forall s \in S: \set {\map f s} = f \sqbrk {\set s}$

Proof:
By definition, a mapping is a relation.
Thus Image of Singleton under Relation applies.
{{Qed}}
Theorem: Image of Subset under Mapping equals Union of Images of Elements

Let $S$ and $T$ be sets.
Let $f: S \to T$ be a mapping from $S$ to $T$.
Let $X \subseteq S$ be a subset of $S$.
Then:
:$\ds f \sqbrk X = \bigcup_{x \mathop \in X} \map f x$
where:
:$f \sqbrk X$ is the image of the subset $X$ under $f$
:$\map f x$ is the image of the element $x$ under $f$.

Proof:
By definition, a mapping is a relation.
Thus Image of Subset under Relation equals Union of Images of Elements applies.
{{Qed}}
Theorem: Mapping Images are Disjoint only if Domains are Disjoint

Let $S$ and $T$ be sets.
Let:
:$f \sqbrk S \cap f \sqbrk T = \O$
where $f \sqbrk S$ denotes the image set of $S$.
Then:
:$S \cap T = \O$

Proof:
From Image of Intersection under Mapping:
:$f \sqbrk {S \cap T} \subseteq f \sqbrk S \cap f \sqbrk T$
From Empty Set is Subset of All Sets:
:$f \sqbrk {S \cap T} = \O$
From Image of Subset under Mapping is Subset of Image:
:$S \cap T = \O$
{{qed}}
Theorem: Image of Relation is Domain of Inverse Relation

Let $\RR \subseteq S \times T$ be a relation.
Let $\RR^{-1} \subseteq T \times S$ be the inverse of $\RR$.
Then:
:$\Img \RR = \Dom {\RR^{-1} }$
That is, the image of a relation is the domain of its inverse.

Proof:
By definition:
{{begin-eqn}}
{{eqn | l = \Img \RR
      | o = :=
      | r = \set {t \in T: \exists s \in S: \tuple {s, t} \in \RR}
}}
{{eqn | l = \Dom {\RR^{-1} }
      | o = :=
      | r = \set {t \in T: \exists s \in S: \tuple {t, s} \in \RR^{-1} }
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = x
      | o = \in
      | r = \Img \RR
}}
{{eqn | ll= \leadstoandfrom
      | q = \exists s \in S
      | l = \tuple {s, x}
      | o = \in
      | r = \RR
      | c = {{Defof|Image of Relation}}
}}
{{eqn | ll= \leadstoandfrom
      | q = \exists s \in S
      | l = \tuple {x, s}
      | o = \in
      | r = \RR^{-1}
      | c = {{Defof|Inverse Relation}}
}}
{{eqn | ll= \leadstoandfrom
      | l = x
      | o = \in
      | r = \Dom {\RR^{-1} }
      | c = {{Defof|Domain of Relation}}
}}
{{end-eqn}}
{{qed}}
Theorem: Domain of Relation is Image of Inverse Relation

Let $\RR \subseteq S \times T$ be a relation.
Let $\RR^{-1} \subseteq T \times S$ be the inverse of $\RR$.
Then:
:$\Dom \RR = \Img {\RR^{-1} }$
That is, the domain of a relation is the image of its inverse.

Proof:
By definition:
{{begin-eqn}}
{{eqn | l = \Dom \RR
      | o = :=
      | r = \set {s \in S: \exists t \in T: \tuple {s, t} \in \RR}
}}
{{eqn | l = \Img {\RR^{-1} }
      | o = :=
      | r = \set {s \in S: \exists T \in T: \tuple {t, s} \in \RR^{-1} }
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = x
      | o = \in
      | r = \Dom \RR
}}
{{eqn | ll= \leadstoandfrom
      | q = \exists t \in T
      | l = \tuple {x, t}
      | o = \in
      | r = \RR
      | c = {{Defof|Domain of Relation}}
}}
{{eqn | ll= \leadstoandfrom
      | q = \exists t \in T
      | l = \tuple {t, x}
      | o = \in
      | r = \RR^{-1}
      | c = {{Defof|Inverse Relation}}
}}
{{eqn | ll= \leadstoandfrom
      | l = x
      | o = \in
      | r = \Img {\RR^{-1} }
      | c = {{Defof|Image of Relation}}
}}
{{end-eqn}}
{{qed}}
Theorem: Element in Preimage of Image under Mapping

Let $f: S \to T$ be a mapping.
Let $f^{-1} \sqbrk {\map f x}$ denote the preimage of $\map f x$ under $f$.
Then:
:$\forall x \in S: x \in f^{-1} \sqbrk {\map f x}$

Proof:
A mapping is by definition a left-total relation.
Therefore Preimage of Image under Left-Total Relation is Superset applies:
:$A \subseteq S \implies A \subseteq f^{-1} \sqbrk {f \sqbrk A}$
Thus:
:$\set x \subseteq S \implies \set x \subseteq f^{-1} \sqbrk {f \sqbrk A}$
Hence the result.
{{qed}}
Theorem: Element in Image of Preimage under Mapping

Let $f: S \to T$ be a mapping.
Then:
:$\forall y \in T: \in f \sqbrk {f^{-1} \sqbrk y} = \set y$

Proof:
A mapping is by definition a relation.
Therefore {{Corollary|Image of Preimage under Mapping}} applies:
:$B \subseteq \Img S \implies \paren {f \circ f^{-1} } \sqbrk B = B$
Thus:
:$\set y \subseteq T \implies f^{-1} \sqbrk {f \sqbrk {\set y} } = \set y$
Hence the result.
{{qed}}
Theorem: Image of Set Difference under Injection

Let $f: S \to T$ be a mapping.
Let $S_1$ and $S_2$ be subsets of $S$.
Let $S_1 \setminus S_2$ denote the set difference between $S_1$ and $S_2$.
Then:
:$\forall S_1, S_2 \subseteq S: f \sqbrk {S_1} \setminus f \sqbrk {S_2} = f \sqbrk {S_1 \setminus S_2}$
{{iff}} $f$ is an injection.

Proof:
An injection is a type of one-to-one relation, and therefore also a one-to-many relation.
Therefore One-to-Many Image of Set Difference applies:
:$\RR \sqbrk {S_1} \setminus \RR \sqbrk {S_2} = \RR \sqbrk {S_1 \setminus S_2}$
{{iff}} $\RR$ is one-to-many.
We have that $f$ is a mapping and therefore a many-to-one relation.
So $f$ is a one-to-many relation {{iff}} $f$ is also an injection.
It follows that:
:$\forall S_1, S_2 \subseteq S: f \sqbrk {S_1} \setminus f \sqbrk {S_2} = f \sqbrk {S_1 \setminus S_2}$
{{iff}} $f$ is an injection.
{{qed}}
Theorem: De Morgan's Laws (Set Theory)/Set Complement/Family of Sets/Complement of Union

:$\ds \map \complement {\bigcup_{i \mathop \in I} S_i} = \bigcap_{i \mathop \in I} \map \complement {S_i}$

Proof:
{{begin-eqn}}
{{eqn | l = \map \complement {\bigcup_{i \mathop \in I} S_i}
      | r = \mathbb U \setminus \paren {\bigcup_{i \mathop \in I} S_i}
      | c = {{Defof|Set Complement}}
}}
{{eqn | r = \bigcap_{i \mathop \in I} \paren {\mathbb U \setminus S_i}
      | c = De Morgan's Laws for Set Difference: Difference with Union
}}
{{eqn | r = \bigcap_{i \mathop \in I} \map \complement {S_i}
      | c = {{Defof|Set Complement}}
}}
{{end-eqn}}
{{qed}}
{{Namedfor|Augustus De Morgan}}
Theorem: De Morgan's Laws (Set Theory)/Set Complement/Family of Sets/Complement of Intersection

:$\ds \map \complement {\bigcap_{i \mathop \in I} S_i} = \bigcup_{i \mathop \in I} \map \complement {S_i}$

Proof:
{{begin-eqn}}
{{eqn | l = \map \complement {\bigcap_{i \mathop \in I} S_i}
      | r = \mathbb U \setminus \paren {\bigcap_{i \mathop \in I} S_i}
      | c = {{Defof|Set Complement}}
}}
{{eqn | r = \bigcup_{i \mathop \in I} \paren {\mathbb U \setminus S_i}
      | c = De Morgan's Laws for Set Difference: Difference with Intersection
}}
{{eqn | r = \bigcup_{i \mathop \in I} \map \complement {S_i}
      | c = {{Defof|Set Complement}}
}}
{{end-eqn}}
{{qed}}
Theorem: Limit of Sets Exists iff Limit Inferior contains Limit Superior

Let $\Bbb S = \set {E_n : n \in \N}$ be a sequence of sets.
Then $\Bbb S$ converges to a limit {{iff}}:
:$\ds \limsup_{n \mathop \to \infty} E_n \subseteq \liminf_{n \mathop \to \infty}E_n$

Proof:
=== Sufficient Condition ===
Let $\Bbb S$ converge to a limit.
Then by definition:
:$\ds \limsup_{n \mathop \to \infty} E_n = \liminf_{n \mathop \to \infty} E_n$
and so by definition of set equality:
:$\ds \limsup_{n \mathop \to \infty} E_n \subseteq \liminf_{n \mathop \to \infty}E_n$
{{qed|lemma}}
Theorem: Closure of Intersection and Symmetric Difference imply Closure of Set Difference

Let $\RR$ be a system of sets such that for all $A, B \in \RR$:
:$(1): \quad A \cap B \in \RR$
:$(2): \quad A \symdif B \in \RR$
where $\cap$ denotes set intersection and $\symdif$ denotes set symmetric difference.
Then:
:$\forall A, B \in \RR: A \setminus B \in \RR$
where $\setminus$ denotes set difference.

Proof:
Let $A, B \in \RR$.
From Set Difference as Symmetric Difference with Intersection:
:$A \symdif \paren {A \cap B} = A \setminus B$
By hypothesis:
:$A \cap B \in \RR$
and:
:$A \symdif \paren {A \cap B} \in \RR$
and so:
:$A \setminus B \in \RR$
{{qed}}
Category:Set Intersection
Category:Set Difference
Category:Symmetric Difference
Category:Set Systems
i42i8yhivt5p8agvwv5yeswfspsv6vt
Theorem: Closure of Intersection and Symmetric Difference imply Closure of Union

Let $\R R$ be a system of sets such that for all $A, B \in \RR$:
:$(1): \quad A \cap B \in \RR$
:$(2): \quad A \symdif B \in \RR$
where $\cap$ denotes set intersection and $\symdif$ denotes set symmetric difference.
Then:
:$\forall A, B \in \RR: A \cup B \in \RR$
where $\cup$ denotes set union.

Proof:
Let $A, B \in \RR$.
From Union as Symmetric Difference with Intersection:
:$\paren {A \symdif B} \symdif \paren {A \cap B} = A \cup B$
By hypothesis:
:$A \cap B \in \RR$
and:
:$\paren {A \symdif B} \symdif \paren {A \cap B} \in \RR$
and so:
:$A \cup B \in \RR$
{{qed}}
Category:Set Intersection
Category:Set Union
Category:Symmetric Difference
Category:Set Systems
fmjyu3p1y7qwwl2s1sdik143iy4kbwg
Theorem: Empty Set and Set form Algebra of Sets

Let $S$ be any non-empty set.
Then $\set {S, \O}$ is (trivially) an algebra of sets, where $S$ is the unit.

Proof:
From Set Union is Idempotent:
:$S \cup S = S$
and
:$\O \cup \O = \O$
Then from Union with Empty Set:
:$S \cup \O = S$
So $\set {S, \O}$ is closed under union.
From Relative Complement of Empty Set:
:$\relcomp S \O = S$
and from Relative Complement with Self is Empty Set:
:$\relcomp S S = \O$
so $\set {S, \O}$ is closed under complement.
Hence the result, by definition of algebra of sets.
{{qed}}
Category:Algebras of Sets
jf9cwmcsvsk83m8kkxahqex7y1wdojx
Theorem: Closure of Union and Complement imply Closure of Set Difference

Let $\RR$ be a system of sets on a universe $\mathbb U$ such that for all $A, B \in \RR$:
:$(1): \quad A \cup B \in \RR$
:$(2): \quad \map \complement A \in \RR$
where $\cup$ denotes set union and $\complement$ denotes complement (relative to $\mathbb U$).
Then:
:$\forall A, B \in \RR: A \setminus B \in \RR$
where $\setminus$ denotes set difference.

Proof:
Let $A, B \in \RR$.
{{begin-eqn}}
{{eqn | l = A \setminus B
      | r = A \cap \map \complement B
      | c = Set Difference as Intersection with Complement
}}
{{eqn | r = \map \complement {\map \complement A \cup B}
      | c = De Morgan's Laws: Complement of Intersection
}}
{{end-eqn}}
As both set union and complement are closed in $\RR$ the result follows.
{{qed}}
Theorem: Complement of Limit Inferior is Limit Superior of Complements

Let $\sequence {E_n}_{n \mathop \in \N}$ be a sequence of sets.
Then:
:$\ds \map \complement {\liminf_{n \mathop \to \infty} \ E_n} = \limsup_{n \mathop \to \infty} \ \map \complement {E_n}$
where $\liminf$ and $\limsup$ denote the limit inferior and limit superior, respectively.

Proof:
{{begin-eqn}}
{{eqn | l = \map \complement {\liminf_{n \mathop \to \infty} \ E_n}
      | r = \map \complement {\bigcup_{n \mathop = 0}^\infty \bigcap_{i \mathop = n}^\infty E_n}
      | c = {{Defof|Limit Inferior of Sequence of Sets|index = 1}}
}}
{{eqn | r = \bigcap_{n \mathop = 0}^\infty \map \complement {\bigcap_{i \mathop = n}^\infty E_n}
      | c = De Morgan's Laws
}}
{{eqn | r = \bigcap_{n \mathop = 0}^\infty \bigcup_{i \mathop = n}^\infty \map \complement {E_n}
      | c = De Morgan's Laws
}}
{{eqn | r = \limsup_{n \mathop \to \infty} \ \map \complement {E_n}
      | c = {{Defof|Limit Superior of Sequence of Sets|index = 1}}
}}
{{end-eqn}}
{{qed}}
Theorem: Complement of Limit Superior is Limit Inferior of Complements

Let $\sequence {E_n}_{n \mathop \in \N}$ be a sequence of sets.
Then:
:$\ds \map \complement {\limsup_{n \mathop \to \infty} \ E_n} = \liminf_{n \mathop \to \infty} \ \map \complement {E_n}$
where $\limsup$ and $\liminf$ denote the limit superior and limit inferior, respectively.

Proof:
{{begin-eqn}}
{{eqn | l = \map \complement {\limsup_{n \mathop \to \infty} \ E_n}
      | r = \map \complement {\bigcap_{n \mathop = 0}^\infty \bigcup_{i \mathop = n}^\infty E_n}
      | c = {{Defof|Limit Superior of Sequence of Sets|index = 1}}
}}
{{eqn | r = \bigcup_{n \mathop = 0}^\infty \map \complement {\bigcup_{i \mathop = n}^\infty E_n}
      | c = De Morgan's Laws
}}
{{eqn | r = \bigcup_{n \mathop = 0}^\infty \bigcap_{i \mathop = n}^\infty \map \complement {E_n}
      | c = De Morgan's Laws
}}
{{eqn | r = \liminf_{n \mathop \to \infty} \ \map \complement {E_n}
      | c = {{Defof|Limit Inferior of Sequence of Sets|index = 1}}
}}
{{end-eqn}}
{{qed}}
Theorem: Sigma-Ring is Closed under Countable Intersections

Let $\RR$ be a $\sigma$-ring.
Let $\sequence {A_n}_{n \mathop \in \N} \in \RR$ be a sequence of sets in $\RR$.
Then:
:$\ds \bigcap_{n \mathop = 1}^\infty A_n \in \RR$

Proof:
{{begin-eqn}}
{{eqn | q = \forall n \in \N_{>0}
      | l = A_1, A_n \in \RR
      | o = \leadsto
      | r = A_1 \setminus A_n \in \RR
      | c = Axiom $(\text {SR} 2)$ for $\sigma$-rings
}}
{{eqn | o = \leadsto
      | r = \bigcup_{n \mathop = 2}^\infty \paren {A_1 \setminus A_n} \in \RR
      | c = Axiom $(\text {SR} 3)$ for $\sigma$-rings
}}
{{eqn | o = \leadsto
      | r = A_1 \setminus \paren {\bigcup_{n \mathop = 2}^\infty \paren {A_1 \setminus A_n} } \in \RR
      | c = Axiom $(\text {SR} 2)$ for $\sigma$-rings
}}
{{end-eqn}}
From De Morgan's laws: Difference with Intersection:
:$\ds \bigcup_{n \mathop = 2}^\infty \paren {A_1 \setminus A_n} = A_1 \setminus \paren {\bigcap_{n \mathop = 2}^\infty A_n}$
From Set Difference with Set Difference:
{{begin-eqn}}
{{eqn | l = A_1 \setminus \paren {A_1 \setminus \paren {\ds \bigcap_{n \mathop = 2}^\infty A_n} }
      | r = A_1 \cap \paren {\ds \bigcap_{n \mathop = 2}^\infty A_n}
}}
{{eqn | r = {\bigcap_{n \mathop = 1}^\infty A_n}
}}
{{end-eqn}}
Combining the previous equalities, it follows that:
:$\ds \bigcap_{n \mathop = 1}^\infty A_n \in \RR$
{{qed}}