nyuuzyou/wikis huggingface dataset:
Relation on Slowly Progressing Mapping which fulfils conditions of General Double Induction Principle

== Theorem ==
Let $M$ be a class.
Let $g: M \to M$ be a slowly progressing mapping on $M$.
Let $\map \RR {x, y}$ be the relation on $M$ defined as:
:$\forall x, y \in M: \tuple {x, y} \in \R \iff x \subseteq y \lor y \subseteq x$
Then $\RR$ satisfies the conditions of the General Double Induction Principle:
:$({\text D'}_1): \quad \map \RR {x, 0}$ and $\map \RR {0, x}$ hold for every $x \in M$
:$({\text D'}_2): \quad \forall x, y \in M: \paren {\map \RR {x, y} \land \map \RR {x, \map g y} \land \map \RR {\map g x, y} } \implies \map \RR {\map g x, \map g y}$
== Proof ==
== Sources ==
* : Chapter $3$: The Natural Numbers: $\S 9$ Supplement -- optional: Lemma $S_2$
Category:Double Induction Principle
Category:Slowly Progressing Mappings
Category:Relation on Slowly Progressing Mapping which fulfils conditions of General Double Induction Principle
Relation to Empty Set is Mapping iff Domain is Empty

== Theorem ==
Let $S$ be a set
Let $S \times \O$ denote the cartesian product of $S$ with the empty set $\O$.
Let $\RR \subseteq S \times \O$ be a relation in $S$ to $\O$.
Then $\RR$ is a mapping $S = \O$.
== Proof ==
Let $S \ne \O$.
Then $\exists s \in S$.
But there exists no $t \in \O$.
Hence there is no $\tuple {s, t} \in \RR$.
So $\RR$ is not a mapping by definition.
Let $S = \O$.
Then $\RR$ is the empty mapping by definition.
From Empty Mapping is Mapping, it is demonstrated that $\RR$ is indeed a mapping.
Hence the result.
Category:Empty Mapping
Category:Relation Theory
Relational Closure Exists for Set-Like Relation

== Theorem ==
Let $A$ be a class.
Let $\prec$ be a relation on $A$.
Furthermore, let $\map {\prec^{-1} } a$ be a small class for each $a \in A$.
Let $S$ be a small class that is a subset of the class $A$.
Let $G$ be a mapping such that:
:$\map G x = A \cap \paren {\map {\prec^{-1} } x}$
Let $F$ be defined using the Principle of Recursive Definition:
:$\map F 0 = S$
:$\map F {n^+} = \map F n \cup \map G {\map F n}$
Let $\ds T = \bigcup_{n \mathop \in \omega} \map F n$.
Then:
:$(1): \quad T$ is a set and satisfies:
::::$\forall x \in A: \forall y \in T: \paren {x \prec y \implies x \in T}$
::::In other words, $T$ is $\prec$-transitive.
:$(2): \quad S \subseteq T$
:$(3): \quad$ If $R$ is $\prec$-transitive and $S \subseteq R$, then $T \subseteq R$.
That is, given any set $S$, there is an explicit construction for its relational closure.
== Proof ==
=== Proof of $(1)$ ===
Let $x \in A$ and $y \in T$ such that $x \prec y$.
Then by definition:
:$x \in \map {\prec^{-1} } y$
Moreover, since $y \in T$:
:$\exists n \in \omega: y \in \map F n$
Therefore:
:$x \in \map F {n + 1}$
and so:
:$x \in T$
=== Proof of $(2)$ ===
Let $x \in S$.
We have that:
:$\map F 0 = S$
Therefore:
:$\exists n \in \omega: x \in \map F n$
It follows that $x \in T$.
By the definition of subset, it follows that:
:$S \subseteq T$
=== Proof of $(3)$ ===
Let $R$ be $\prec$-transitive.
Let $S \subseteq R$.
Then:
:$\map F n \subseteq R$ shall be proved 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:
:$\forall n \in \omega: \map F n \subseteq R$
Then by Indexed Union Subset:
:$T \subseteq R$
== Sources ==
* : $\S 9.3$
Category:Relational Closures
Relational Closure from Transitive Closure

== Theorem ==
Let $A$ be a set or class.
Let $\RR$ be a relation on $A$.
Let $\RR^+$ be the transitive closure of $\RR$.
Let $B \subseteq A$.
Let $B' = B \cup \inv {\paren {\RR^+} } B$.
Let $C$ be an $\RR$-transitive subset or subclass of $A$ such that $B \subseteq C$.
Then:
:$B'$ is $\RR$-transitive
:$B' \subseteq C$
:If $B$ is a set and $\RR$ is set-like then $B'$ is a set.
That is, $B'$ is the relational closure of $B$ under $\RR$.
== Proof ==
=== $B'$ is $\RR$-transitive ===
Let $x \in B'$ and $y \in A$, and let $y \mathrel \RR x$.
If $x \in B$, then by the definition of transitive closure:
:$y \mathrel {\RR^+} x$
so:
:$y \in B'$
Let $x \in \inv {\paren {\RR^+} } B$.
Then:
:$x \mathrel {\RR^+} b$
for some $b \in B$.
Since $\RR \subseteq \RR^+$, it follows that:
:$y \mathrel {\RR^+} x$
Since $\RR^+$ is transitive:
:$y \mathrel {\RR^+} b$
That is:
:$y \in \inv {\paren {\RR^+} } B$
so $y \in B'$.
As this holds for all such $x$ and $y$, $B'$ is $\RR$-transitive.
=== $B' \subseteq C$ ===
Let $x \in B'$.
Then $x \in B$ or $x \in \inv {\paren {\RR^+} } B$.
Let $x \in B$.
Then because $B \subseteq C$:
:$x \in C$
Suppose that $x \in \inv {\paren {\RR^+} } B$.
Then for some $b \in B$:
:$x \mathrel \RR b$
By the definition of transitive closure:
:for some $n \in \N_{>0}$ there exist $a_0, a_1, \dots, a_n$ such that:
::$x = a_0 \mathrel \RR a_1 \mathrel \RR \cdots \mathrel \RR a_n = b$
Thus by the Principle of Mathematical Induction:
:$x \in C$
=== Set-like implies set ===
Let $B$ be a set.
Let $\RR$ be set-like.
Then by Inverse Image of Set under Set-Like Relation is Set:
:$\paren {\RR^+}^{-1}$ is a set.
Thus $B'$ is a set by the Axiom of Unions.
Category:Relational Closures
Relational Structure admits Lower Topology

== Theorem ==
Let $R = \left({S, \preceq}\right)$ be a relational structure.
Then there exists a relational structure with lower topology $T = \left({S, \preceq, \tau}\right)$ such that $T$ is a topological space.
== Proof ==
Define $B := \left\{ {\complement_S\left({x^\succeq}\right): x \in S}\right\}$
where $x^\succeq$ denotes the upper closure of $x$.
By definition of generated topology:
:$\tau\left({B}\right)$ is a topology on $S$
where $B$ is a sub-basis of $\tau \left({B}\right)$.
Thus by definition of lower topology:
:$T := \left({S, \preceq, \tau\left({B}\right)}\right)$ has a lower topology.
Thus by definition:
:$T$ is a topological space.
== Sources ==
* 
* 
Category:Topological Order Theory
Relational Structure with Topology of Subsets with Property (S) is Topological Space

== Theorem ==
Let $T = \struct {S, \preceq, \tau}$ be a relational structure with topology
where
:$\struct {S, \preceq}$ is an up-complete ordered set
:$\tau$ is the set of all subsets of $S$ with property (S).
Then $\struct {S, \tau}$ is topological space.
== Proof ==
We will prove that
:$S$ has property (S).
Let $D$ be a directed subset of $S$ such that
:$\sup D \in S$
By definition of non-empty set:
:$\exists y: y \in D$
Thus $y \in D$.
Thus by definition of subset:
:$\forall x \in D: y \preceq x \implies x \in S$
Then:
$(\text O 3): \quad S \in \tau$
We will prove that:
:$(\text O 1): \quad \forall F \subseteq \tau: \bigcup F \in \tau$
Let $F \subseteq \tau$.
To prove that $\bigcup F \in \tau$ it should be proved that
:$\bigcup F$ has property (S).
Let $D$ be a directed subset of $S$ such that
:$\sup D \in \bigcup F$
By definition of union:
:$\exists X \in F: \sup D \in X$
By definition of subset:
:$X \in \tau$
By assumption:
:$X$ has property (S).
By definition of property (S):
:$\exists y \in D: \forall x \in D: y \preceq x \implies x \in X$
Thus $y \in D$.
Let $x \in D$ such that
:$y \preceq x$
Then $x \in X$.
Thus by definition of union:
:$x \in \bigcup F$
We will prove that
:$(\text O 2): \quad \forall X, Y \in \tau: X \cap Y \in \tau$
Let $X, Y \in \tau$.
By assumption:
:$X$ and $Y$ have property (S).
To prove that $X \cap Y \in \tau$ it should be proved that:
:$X \cap Y$ has property (S).
Let $D$ be a directed subset of $S$ such that:
:$\sup D \in X \cap Y$
By definition of intersection:
:$\sup D \in X$ and $\sup D \in Y$
By definition of property (S):
:$\exists x \in D: \forall z \in D: x \preceq z \implies z \in X$
and
:$\exists y \in D: \forall z \in D: y \preceq z \implies z \in X$
By definition of directed:
:$\exists z \in D: x \preceq z \land y \preceq z$
Thus $z \in D$.
Let $u \in D$ such that
:$z \preceq u$
By definition of transitivity:
:$x \preceq u$ and $y \preceq u$
Then:
:$u \in X$ and $u \in Y$
Thus by definition of intersection:
:$u \in X \cap Y$
Hence by $(\text O 1)$, $(\text O 2)$, $(\text O 3)$, and definition:
:$\struct {S, \tau}$ is topological space.
== Sources ==
* 
* 
Category:Topological Order Theory
Category:Topology
Relations Compatible with Group Form Complete Boolean Algebra

== Theorem ==
Let $\struct {S, \circ}$ be a group.
Let $C$ be the set of relations on $S$ which are compatible with $\circ$.
Then $\struct {C, \cap, \cup, \subseteq}$ is a complete Boolean lattice.
== Proof ==
Category:Compatible Relations
Category:Complete Lattices
Category:Boolean Lattices
Relations Compatible with Operation Form Complete Distributive Lattice

== Theorem ==
Let $\struct {S, \circ}$ be an algebraic structure.
Let $C$ be the set of relations on $S$ compatible with $\circ$.
Then $\struct {C, \cap, \cup, \subseteq}$ is a complete distributive lattice.
== Proof ==
Category:Compatible Relations
Category:Complete Lattices
Category:Distributive Lattices
Relations of Finite Partition and Finite Sub-Sigma-Algebra

== Theorem ==
Let $\struct {\Omega, \Sigma, \Pr}$ be a probability space.
Let $\eta, \gamma$ be finite partitions of $\Omega$.
Let $\BB, \CC \subseteq \Sigma$ be finite sub-$\sigma$-algebras.
Let:
:$\map \xi \cdot$ denote the generated finite partition
:$\map \sigma \cdot$ denote the generated $\sigma$-algebra
:$\le$ denote the order by refinement of partition.
Then the following results hold:
=== Generated Finite Partition of Generated Finite Sub-Sigma-Algebra is Itself ===
=== Generated Finite Sub-Sigma-Algebra of Generated Finite Partition is Itself ===
=== Generating Finite Sub-Sigma-Algebra Preserves Order ===
=== Generating Finite Partition Preserves Order ===
== Sources ==
* $4.1$: Partitions and Subalgebras
Category:Probability Theory
Category:Ergodic Theory
Relationship between Component Types

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
Let $p \in S$.
Let:
: $A$ be the arc component of $p$
: $P$ be the path component of $p$
: $C$ be the component of $p$
: $Q$ be the quasicomponent of $p$.
Then:
:$A \subseteq P \subseteq C \subseteq Q$
In general, the inclusions do not hold in the other direction.
== Proof ==
Let $f \in A$.
By Arc in Topological Space is Path we have that $f \in P$.
That is, $A \subseteq P$.
----
Let $f \in P$.
From Path-Connected Space is Connected we have directly that $P \subseteq C$.
----
Let $f \in C$.
From Connected Space is Connected Between Two Points we have directly that $C \subseteq Q$.
Hence the result.
== Also see ==
* Path Component is not necessarily Arc Component
* Component is not necessarily Path Component
* Quasicomponent is not necessarily Component
== Sources ==
* : Part $\text I$: Basic Definitions: Section $4$: Connectedness
Category:Connected Spaces
Relationship between Limit Inferior and Lower Limit

== Theorem ==
Let $\struct {S, \tau}$ be a topological space.
Let $f: S \to \R \cup \set {-\infty, \infty}$ be an extended real-valued function.
Let $\sequence {s_n}_{n \mathop \in \N}$ be a convergent sequence in $S$ such that $s_n \to \bar s$.
Then the lower limit of $f$ at $\bar s$ is bounded above by the limit inferior of $\sequence {\map f {s_n} }$:
:$\ds \liminf_{s \mathop \to \bar s} \map f s \le \liminf_{n \mathop \to \infty} \map f {s_n}$
== Proof ==
Let $\NN_{\bar s}$ denote the neighborhood filter of $\bar s$.
By definition of the lower limit, there exists a sequence of open neighborhoods $\sequence {V_k}_{k \mathop \in \N} \in \NN_{\bar s}$ such that:
:$\ds \lim_{k \mathop \to \infty} \set {\inf_{s \mathop \in V_k} \map f s} = \liminf_{s \mathop \to \bar s} \map f s$
This implies that $\forall \epsilon > 0 \exists k_\epsilon \in \N$ such that:
:$\ds \inf_{s \mathop \in V_{k_\epsilon} } \map f s \ge \liminf_{s \mathop \to \bar s} \map f s - \epsilon$
By our hypothesis $s_n \to \bar s$ and because $V_{k_\epsilon} \in N_{\bar s}$ there exists $\map N {k_\epsilon} \in \N$ such that:
:$\ds \forall n \ge \map N {k_\epsilon}: s_n \in V_{k_\epsilon}$
Consequently:
Combining these estimates, it follows that for all $\epsilon > 0$:
:$\ds \liminf_{s \mathop \to \bar s} \map f s \le \liminf_{n \mathop \to \infty} \map f {s_n} + \epsilon$
Hence the result.
Category:Topology
Relationship between Limit Point Types

== Theorem ==
Let $T = \struct {X, \tau}$ be a topological space.
Let $A \subseteq X$.
Let:
:$C$ be the set of condensation points of $A$
:$W$ be the set of $\omega$-accumulation points of $A$
:$L$ be the set of limit points of $A$
:$D$ be the set of adherent points of $A$.
Then:
:$C \subseteq W \subseteq L \subseteq D$
That is:
:Every condensation point is an $\omega$-accumulation point
:Every $\omega$-accumulation point is a limit point
:Every limit point is an adherent point.
In general, the inclusions do not hold in the other direction.
== Proof ==
Let $x \in C$.
By definition of condensation point, every open set of $T$ containing $x$ also contains an uncountable number of points of $A$.
As an uncountable number is also an infinite number, we could also say that every open set of $T$ containing $x$ also contains an infinite number of points of $A$.
That is, $x$ is also by definition an $\omega$-accumulation point.
So $x \in W$ and by definition of subset:
:$C \subseteq W$
Note that if $x \in W$ then it could be that there exists an open set $U$ of $T$ containing $x$ with a countably infinite number of points of $A$.
In that case $x \notin C$.
That is, not every $\omega$-accumulation point is necessarily a condensation point.
Let $x \in W$.
By definition of $\omega$-accumulation point, every open set $U$ of $T$ containing $x$ also contains an infinite number of points of $A$.
So every open set $U$ of $T$ such that $x \in U$ contains some point of $A$ other than $x$ (an infinite number, indeed).
That is, $x$ is also by definition a limit point.
So $x \in L$ and by definition of subset:
:$W \subseteq L$
Let $T = \struct {S, \tau_p}$ be a particular point space.
From Limit Points in Particular Point Space, every point $x \ne p$ is a limit point of $T$.
From Point in Particular Point Space is not Omega-Accumulation Point, $x$ is not an definition of $\omega$-accumulation point of $T$. 
So it is seen that not every limit point is necessarily an $\omega$-accumulation point.
Let $x \in L$.
By definition of limit point, every open set $U$ of $T$ containing $x$ also contains some point of $A$ other than $x$.
So every open set $U$ of $T$ such that $x \in U$ contains some point of $A$.
That is, $x$ is also by definition an adherent point.
So $x \in L$ and by definition of subset:
:$L \subseteq D$
Note that if $x \in D$ then it could be that there exists an open set $U$ of $T$ containing $x$ in which the only point of $A$ is $x$ itself.
In that case $x \notin L$.
That is, not every adherent point is necessarily a limit point.
Hence the result.
== Sources ==
* : Part $\text I$: Basic Definitions: Section $1$: General Introduction: Limit Points
Category:Limit Points
Category:Omega-Accumulation Points
Category:Adherent Points
Category:Condensation Points
Relationship between Transitive Closure Definitions

== Theorem ==
Let $x$ be a set.
Let $a$ be the smallest set such that $x \in a$ and $a$ is transitive.
Let $b$ be the smallest set such that $x \subseteq b$ and $b$ is transitive.
Then $a = b \cup \set x$.
== Proof ==
We have that:
:$x \in a$
and $a$ is transitive.
So:
:$x \subseteq a$
Thus by the definition of $b$ and of smallest set:
:$b \subseteq a$
Since we also have $x \in a$:
:$b \cup \set x \subseteq a$
$x \in \set x$, so:
:$x \in b \cup \set x$
$b \cup \set x$ is transitive:
If $p \in b$ then:
:$p \subseteq b \subseteq b \cup \set x$.
If $p \in \set x$ then:
:$p = x$
So by the definition of $b$:
:$p \subseteq b \subseteq b \cup \set x$
Thus by the definition of $a$:
:$a \subseteq b \cup \set x$
Thus the theorem holds by definition of set equality.
Category:Set Theory
Relative Algebraic Closure with Algebraically Closed Extension is Algebraic Closure

== Theorem ==
Let $L$ be an algebraically closed field.
Let $L/K$ be a field extension.
Then the relative algebraic closure of $K$ contained in $L$ is an algebraic closure of $K$.
== Proof ==
Let $K'$ denote the relative algebraic closure of $K$ contained in $L$.
By definition, $K' = \{\alpha \in L \mid \alpha \text{ is algebraic over } K\}$.
First we show that $K'$ is a field extension of $K$.
By Field is Algebraic over itself, $K \subseteq K'$.
Since $K$ is a field, it and (therefore) $K'$ are nonzero.
Let $\alpha, \beta \in K'$ be arbitrary.
By definition of generated field extension, $\alpha, \beta \in K(\alpha, \beta) \subseteq L$.
By the field axioms, $\alpha - \beta, \alpha\beta^{-1} \in K(\alpha, \beta) \subseteq L$.
By Finitely Generated Algebraic Extension is Finite and Finite Field Extension is Algebraic, we have that $K(\alpha, \beta)/K$ is algebraic.
Therefore both $\alpha - \beta$ and $\alpha\beta^{-1}$ are algebraic over $K$.
So, by definition, $\alpha - \beta, \alpha\beta^{-1} \in K'$.
Using the Subfield Test/Three-Step, we conclude that $K'$ is a subfield of $L$.
So $K'$ is a field containing $K$, ergo $K'/K$ is a field extension.
Furthermore, $K'$ is algebraically closed.
Indeed, let $p \in K'[X]$, where $K'[X]$ is the ring of polynomials with coefficients in $K'$.
Since $K'[X] \subseteq L[X]$ and, by hypothesis, $L$ is algebraically closed, $p$ has a root in $L$.
Let $\alpha \in L$ be a root of $p$.
Consider the field extension $K'(\alpha)/K'$.
By Finitely Generated Algebraic Extension is Finite and Finite Field Extension is Algebraic, $K'(\alpha)/K'$ is algebraic.
By definition of $K'$, the extension $K'/K$ is algebraic.
Therefore, by Transitivity of Algebraic Extensions, $K'(\alpha)/K$ is algebraic.
Thus $\alpha \in K'(\alpha)$ is algebraic over $K$.
By definition again, we conclude $\alpha \in K'$.
Thus $p$ has a root in $K'$.
We have that $K'/K$ is an algebraically closed algebraic field extension.
Therefore, by definition, $K'$ is an algebraic closure of $K$.
== Example ==
Let $L =$ $\C$ and let $K$ be a subfield of $\C$.
Then the set $\{\alpha \in \C \mid \alpha \text{ is algebraic over } K\}$ is an algebraic closure of $K$.
== Also see ==
* Definition:Relative Algebraic Closure
* Definition:Algebraic Closure
* Definition:Algebraically Closed Field
Category:Field Extensions
Relative Complement/Examples/Even Integers

== Examples of Relative Complement ==
Let $E$ denote the set of all even integers.
Then the relative complement of $E$ in $\Z$:
:$\relcomp \Z E$
is the set of all odd integers.
== Sources ==
* : $\S 6$: Subsets
* 
* 
Category:Examples of Relative Complements
Relative Complement Mapping on Powerset is Bijection

== Theorem ==
Let $S$ be a set.
Let $\complement_S: \powerset S \to \powerset S$ denote the relative complement mapping on the power set of $S$.
Then $\complement_S$ is a bijection.
Thus each $T \subseteq S$ is in one-to-one correspondence with its relative complement.
== Proof 1 ==
== Proof 2 ==
Category:Relative Complement
Category:Examples of Bijections
Category:Relative Complement Mapping on Powerset is Bijection
Relative Complement Mapping on Powerset is Bijection/Proof 1

== Theorem ==
== Proof ==
From Relative Complement of Relative Complement:
:$\forall X \subseteq S: \relcomp S {\relcomp S X} = X$
That is, $\complement_S$ is an involution.
The result follows from Mapping is Involution iff Bijective and Symmetric.
Category:Relative Complement Mapping on Powerset is Bijection
Relative Complement Mapping on Powerset is Bijection/Proof 2

== Theorem ==
== Proof ==
Let $f: \powerset S \to \powerset S$ be a mapping defined as:
:$\forall T \in \powerset S: \map f T = \relcomp S T$
It is to be demonstrated that $f$ is a bijection.
By definition of relative complement:
:$\relcomp S T = S \setminus T = \set {x \in S: x \notin T}$
and so it can be seen that $f$ is well-defined.
Let $T_1, T_2 \in \powerset S: \map f {T_1} = \map f {T_2}$.
Then:
That is, $f$ is an injection.
Also:
That is, for all $T \in \powerset S$ there exists an $X$ such that $T = \map f X$.
This demonstrates that $f$ is a surjection.
The result follows by definition of bijection.
Category:Relative Complement Mapping on Powerset is Bijection
Relative Complement inverts Subsets

== Theorem ==
Let $S$ be a set.
Let $A \subseteq S, B \subseteq S$ be subsets of $S$.
Then:
:$A \subseteq B \iff \relcomp S B \subseteq \relcomp S A$
where $\complement_S$ denotes the complement relative to $S$.
== Proof 1 ==
== Proof 2 ==
== Also known as ==
This result can be referred to by saying that:
:the subset operation is inclusion-inverting
:the relative complement operation, considered as a mapping on the ordered structure $\struct {S, \subseteq}$, is decreasing
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 3$: Unions and Intersections of Sets: Exercise $3.3 \ \text{(e)}$
* : $\S 1$: Naive Set Theory: $\S 1.2$: Operations on Sets: Exercise $1.2.2 \ \text{(ii)}$
* 
Category:Subsets
Category:Relative Complement
Category:Relative Complement inverts Subsets
Relative Complement inverts Subsets of Relative Complement

== Theorem ==
Let $S$ be a set.
Let $A \subseteq S, B \subseteq S$ be subsets of $S$.
Then:
:$A \subseteq \relcomp S B \iff B \subseteq \relcomp S A$
where $\complement_S$ denotes the complement relative to $S$.
== Proof ==
We have:
Category:Subsets
Category:Relative Complement
Relative Complement of Cartesian Product

== Theorem ==
Let $A$ and $B$ be sets.
Let $X \subseteq A$ and $Y \subseteq B$.
Then:
:$\relcomp {A \mathop \times B} {X \times Y} = \paren {A \times \relcomp B Y} \cup \paren {\relcomp A X \times B}$
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 5$: Products of Sets: Exercise $1$
Category:Relative Complement of Cartesian Product
Category:Cartesian Product
Category:Relative Complement
Relative Complement of Cartesian Product/Proof 1

== Theorem ==
== Proof ==
From Set with Relative Complement forms Partition:
:$A = \set {X \mid \relcomp A X}$
:$B = \set {Y \mid \relcomp B Y}$
and so by definition of partition:
:$A = X \cup \relcomp A X$
:$B = Y \cup \relcomp B Y$
By Cartesian Product of Unions:
:$A \times B = \paren {X \times Y} \cup \paren {\relcomp A X \times \relcomp B Y} \cup \paren {X \times \relcomp B Y} \cup \paren {\relcomp A X \times Y}$
and so:
Category:Relative Complement of Cartesian Product
Relative Complement of Decreasing Sequence of Sets is Increasing

== Theorem ==
Let $X$ be a set.
Let $\sequence {E_n}_{n \mathop \in \N}$ be a decreasing sequence of sets in $X$. 
Then $\sequence {X \setminus E_n}_{n \mathop \in \N}$ is an increasing sequence of sets in $X$. 
== Proof ==
Since $\sequence {E_n}_{n \mathop \in \N}$ is decreasing, we have: 
:$E_{n + 1} \subseteq E_n$ for each $n \in \N$. 
From Relative Complement inverts Subsets, we then have: 
:$X \setminus E_n \subseteq X \setminus E_{n + 1}$ for each $n \in \N$. 
So $\sequence {X \setminus E_n}_{n \mathop \in \N}$ is an increasing sequence of sets in $X$.
Category:Increasing Sequences of Sets
Category:Relative Complement
Category:Decreasing Sequences of Sets
Relative Complement of Empty Set

== Theorem ==
The relative complement of the empty set is the set itself:
:$\relcomp S \O = S$
== Proof ==
== Also see ==
* Relative Complement with Self is Empty Set
== Sources ==
* : $\S 5$: Complements and Powers
* : Chapter $1$: Set Theory: $1.3$: Set operations
* : Chapter $\text I$: Algebraic Structures: $\S 3$: Unions and Intersections of Sets: Theorem $3.2$
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems
Category:Relative Complement
Category:Empty Set