avewright/proofwiki-math huggingface dataset:
Theorem: Construction of Inverse Completion/Invertible Elements in Quotient Structure

Every cancellable element of $S'$ is invertible in $T'$.

Proof:
From Identity of Quotient Structure, $\struct {T', \oplus'}$ has an identity, and it is $\eqclass {\tuple {c, c} } \boxtimes$ for any $c \in C$.
Call this identity $e_{T'}$.
Let the mapping $\psi: S \to T'$ be defined as:
:$\forall x \in S: \map \psi x = \eqclass {\tuple {x \circ a, a} } \boxtimes$
From Image of Cancellable Elements in Quotient Mapping:
:$C' = \psi \sqbrk C$
So:
{{begin-eqn}}
{{eqn | l = x'
      | o = \in
      | r = C'
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists x \in C
      | l = x'
      | r = \map \psi x
      | c = as $\psi$ is a surjection
}}
{{eqn | ll= \leadsto
      | q = \forall a \in C
      | l = x'
      | r = \eqclass {\tuple {x \circ a, a} } \boxtimes
      | c = Definition of $\psi$
}}
{{end-eqn}}
The inverse of $x'$ is $\eqclass {\tuple {a, a \circ x} } \boxtimes$, as follows:
{{begin-eqn}}
{{eqn | l = a \circ x
      | o = \in
      | r = C
      | c = Cancellable Elements of Semigroup form Subsemigroup
}}
{{eqn | l = a \circ a \circ x
      | o = \in
      | r = C
      | c = Cancellable Elements of Semigroup form Subsemigroup
}}
{{eqn | ll= \leadsto
      | l = \eqclass {\tuple {x \circ a, a} } \boxtimes \oplus' \eqclass {\tuple {a, a \circ x} } \boxtimes
      | r = \eqclass {\tuple {x \circ a \circ a, a \circ a \circ x} } \boxtimes
      | c = Definition of $\oplus'$
}}
{{eqn | r = \eqclass {\tuple {a \circ a \circ x, a \circ a \circ x} } \boxtimes
      | c = Commutativity of $\circ$
}}
{{eqn | r = e_{T'}
      | c = Identity of Quotient Structure
}}
{{end-eqn}}
thus showing that the inverse of $\eqclass {\tuple {x \circ a, a} } \boxtimes$ is $\eqclass {\tuple {a, a \circ x} } \boxtimes$.
{{Qed}}
Theorem: Construction of Inverse Completion/Generator for Quotient Structure

$T' = S' \cup \paren {C'}^{-1}$ is a generator for the semigroup $T'$.

Proof:
Let $\tuple {x, y} \in S \times C$. Then:
{{begin-eqn}}
{{eqn | l = \map \psi x \oplus' \paren {\map \psi y}^{-1}
      | r = \eqclass {\tuple {x \circ a, a} } \boxtimes \oplus' \eqclass {\tuple {a, a \circ y} } \boxtimes
      | c = Invertible Elements in Quotient Structure above
}}
{{eqn | r = \eqclass {\tuple {x \circ a \circ a, a \circ a \circ y} } \boxtimes
      | c = Definition of $\oplus'$
}}
{{eqn | r = \eqclass {\tuple {x \circ a \circ a, y \circ a \circ a} } \boxtimes
      | c = Commutativity of $\circ$
}}
{{eqn | r = \eqclass {\tuple {x, y} } \boxtimes
      | c = Cancellability of $a \in C$
}}
{{end-eqn}}
{{Qed}}
Theorem: Construction of Inverse Completion/Quotient Structure is Inverse Completion

$T'$ is an inverse completion of its subsemigroup $S'$.

Proof:
Every cancellable element of $S'$ is invertible in $T'$, from Invertible Elements in Quotient Structure.
$T' = S' \cup \paren {C'}^{-1}$ is a generator for the semigroup $T'$, from Generator for Quotient Structure.
Hence the result, by definition of inverse completion
{{Qed}}
Theorem: Ring of Integers Modulo Composite is not Integral Domain

Let $m \in \Z: m \ge 2$.
Let $\struct {\Z_m, +, \times}$ be the ring of integers modulo $m$.
Let $m$ be a composite number.
Then $\struct {\Z_m, +, \times}$ is not an integral domain.

Proof:
Let $m \in \Z: m \ge 2$ be composite.
Then:
:$\exists k, l \in \N_{> 0}: 1 < k < m, 1 < l < m: m = k \times l$
Thus:
{{begin-eqn}}
{{eqn | l = \eqclass 0 m
      | r = \eqclass m m
      | c = 
}}
{{eqn | r = \eqclass {k l} m
      | c = 
}}
{{eqn | r = \eqclass k m \times \eqclass l m
      | c = 
}}
{{end-eqn}}
So $\struct {\Z_m, +, \times}$ is a ring with zero divisors.
So by definition $\struct {\Z_m, +, \times}$ is not an integral domain.
{{qed}}
Theorem: Ring Zero is not Cancellable

Let $\struct {R, +, \circ}$ be a ring which is not null.
Let $0$ be the ring zero of $R$.
Then $0$ is not a cancellable element for the ring product $\circ$.

Proof:
{{AimForCont}} $0$ is cancellable.
Let $a, b \in R$ such that $a \ne b$.
By definition of ring zero:
:$0 \circ a = 0 = 0 \circ b$
By our supposition that $0$ is cancellable:
:$a = b$
The result follows by Proof by Contradiction.
{{qed}}
Theorem: Congruence Relation on Ring induces Ideal

Let $\struct {R, +, \circ}$ be a ring.
Let $\EE$ be a congruence relation on $R$.
Let $J = \eqclass {0_R} \EE$ be the equivalence class of $0_R$ under $\EE$.
Then $J$ is an ideal of $R$.

Proof:
Let $J = \eqclass {0_R} \EE$.
By Congruence Relation induces Normal Subgroup, $\struct {J, +}$ is a normal subgroup of $\struct {R, +}$.
Thus the elements of $\struct {R, +} / \struct {J, +}$ are the cosets of $\eqclass {0_R} \EE$ by $+$.
We have that $\EE$ is also compatible with $\circ$.
Thus from Quotient Structure is Well-Defined, and so:
:$\eqclass {x_1} \EE = \eqclass {x_2} \EE \land \eqclass {y_1} \EE = \eqclass {y_2} \EE \implies \eqclass {x_1 \circ y_1} \EE = \eqclass {x_2 \circ y_2} \EE$
Putting $x_1 = 0_R, x_2 = x, y_1 = y_2 = y$, so that $\eqclass {y_1} \EE = \eqclass {y_2} \EE$ by definition:
:$\eqclass 0 \EE = \eqclass x \EE  \implies \eqclass {0 \circ y} \EE = \eqclass {x \circ y} \EE$
Hence:
:$\forall y \in R: \eqclass y \EE \circ \eqclass {0_R} \EE = \eqclass {0_R} \EE = \eqclass {0_R} \EE \circ \eqclass y \EE$
That is:
:$\forall x \in J, y \in R: y \circ x \in J, x \circ y \in J$
demonstrating that $J$ is an ideal of $R$.
{{qed}}
Theorem: Ideal induces Congruence Relation on Ring

Let $\struct {R, +, \circ}$ be a ring.
Let $J$ be an ideal of $R$
Then $J$ induces a congruence relation $\EE_J$ on $R$ such that $\struct {R / J, +, \circ}$ is a quotient ring.

Proof:
From Ideal is Additive Normal Subgroup, we have that $\struct {J, +}$ is a normal subgroup of $\struct {R, +}$.
Let $x \mathop {\EE_J} y$ denote that $x$ and $y$ are in the same coset, that is:
:$x \mathop {\EE_J} y \iff x + N = y + N$
From Congruence Modulo Normal Subgroup is Congruence Relation, $\EE_J$ is a congruence relation for $+$.
Now let $x \mathop {\EE_J} x', y \mathop {\EE_J} y'$.
By definition of congruence modulo $J$:
:$x + \paren {-x'} \in J$
:$y + \paren {-y'} \in J$
Then:
:$x \circ y + \paren {-x' \circ y'} = \paren {x + \paren {-x'} } \circ y + x' \circ \paren {y + \paren {-y'} } \in J$
demonstrating that $\EE_J$ is a congruence relation for $\circ$.
Hence the result by definition of quotient ring.
{{qed}}
Theorem: Vector Space has Basis between Linearly Independent Set and Spanning Set

Let $V$ be a vector space over a field $F$.
Let $L$ be a linearly independent subset of $V$.
Let $S$ be a set that spans $V$.
Suppose that $L \subseteq S$.
Then $V$ has a basis $B$ such that $L \subseteq B \subseteq S$.

Proof:
Let $\mathscr I$ be the set of linearly independent subsets of $S$ that contain $L$, ordered by inclusion.
Note that $L \in \mathscr I$, so $\mathscr I \ne \O$.
Let $\mathscr C$ be a chain in $\mathscr I$.
Let $C = \bigcup \mathscr C$.
{{AimForCont}} that $C$ is linearly dependent.
Then there exist $v_1, v_2, \ldots, v_n \in C$ and $r_1, r_2, \ldots, r_n \in F$ such that $r_1 \ne 0$:
:$\ds \sum_{k \mathop = 1}^n r_k v_k = 0$
Then there are $C_1, C_2, \ldots, C_n \in \mathscr C$ such that $v_k \in C_k$ for each $k \in \set {1, 2, \ldots, n}$.
Since $\mathscr C$ is a chain, $C_1 \cup C_2 \cup \cdots \cup C_n$ must equal $C_k$ for some $k \in \set {1, 2, \ldots, n}$.
But then $C_k \in \mathscr C$ and $C_k$ is linearly dependent, which is a contradiction.
Thus $C$ is linearly independent.
By Zorn's Lemma, $\mathscr I$ has a maximal element $M$ (one that is not contained in any other element).
Since $M \in \mathscr I$, $M$ is linearly independent.
All that remains is to show that $M$ spans $V$.
{{AimForCont}} there exists a $v \in V \setminus \map \span M$.
Then, since $S$ spans $V$, there must be an element $s$ of $S$ such that $s \notin \map \span M$.
Then $M \cup \set s$ is linearly independent.
Thus $M \cup \set s \supsetneq M$, contradicting the maximality of $M$.
Thus $M$ is a linearly independent subset of $V$ that spans $V$.
Therefore, by definition, $M$ is a basis for $V$.
{{qed}}
Theorem: Null Ring is Trivial Ring

Let $R$ be the null ring.
Then $R$ is a trivial ring.

Proof:
We have that $R$ is the null ring.
That is, by definition it has a single element, which can be denoted $0_R$, such that:
:$R := \struct {\set {0_R}, +, \circ}$
where ring addition and the ring product are defined as:
{{begin-eqn}}
{{eqn | l = 0_R + 0_R
      | r = 0_R
}}
{{eqn | l = 0_R \circ 0_R
      | r = 0_R
}}
{{end-eqn}}
Consider the operation $+$.
By definition, the algebraic structure $\struct {\set {0_R}, +}$ is a trivial group.
Then:
:$\forall a, b \in R: a \circ b = 0_R$
Thus by definition, $R$ is a trivial ring.
{{qed}}
Theorem: Null Ring is Ring

Let $R$ be the null ring.
That is, let:
:$R := \struct {\set {0_R}, +, \circ}$
where ring addition and ring product are defined as:
{{begin-eqn}}
{{eqn | l = 0_R + 0_R
      | r = 0_R
}}
{{eqn | l = 0_R \circ 0_R
      | r = 0_R
}}
{{end-eqn}}
Then $R$ is a ring.

Proof:
A null ring is a trivial ring.
So, by Trivial Ring is Commutative Ring, the result follows.
{{qed}}
Category:Null Ring
74kr1nos4nmsxq3pbnyepbpfj63dpjm
Theorem: Trivial Group is Cyclic Group

The trivial group is a cyclic group.

Proof:
In Trivial Group is Group it is shown that the algebraic structure $\struct {\set e, \circ}$ such that $e \circ e = e$ is in fact a group.
It remains to be shown that it is cyclic.
In order for $G$ to be a cyclic group, every element $x$ of $G$ has to be expressible in the form $x = g^n$ for some $g \in G$ and some $n \in \Z$.
In this case, for every integer $n$, every element of $G$ can be expressed in the form $e^n$.
Thus $G$ is trivially a cyclic group.
{{qed}}
Theorem: Trivial Ring is Commutative Ring

Let $\struct {R, +, \circ}$ be a trivial ring.
Then $\struct {R, +, \circ}$ is a commutative ring.

Proof:
First we need to show that a trivial ring is actually a ring in the first place.
Taking the ring axioms in turn:
Theorem: Congruence Relation and Ideal are Equivalent

Let $\struct {R, +, \circ}$ be a ring.
Let $\EE$ be an equivalence relation on $R$ compatible with both $\circ$ and $+$, that is, a congruence relation on $R$.
Let $J = \eqclass {0_R} \EE$ be the equivalence class of $0_R$ under $\EE$.
Then:
: $(1a): \quad J = \eqclass {0_R} \EE$ is an ideal of $R$
: $(2a): \quad$ The equivalence defined by the quotient ring $R / J$ is $\EE$ itself.
Similarly, let $J$ be an ideal of $R$.
Then:
: $(1b): \quad J$ induces a congruence relation $\EE_J$ on $R$
: $(2b): \quad$ The ideal of $R$ defined by $\EE_J$ is $J$ itself.

Proof:
=== Part $(1a)$ ===
This is shown on Congruence Relation on Ring induces Ideal.
{{qed|lemma}}
Theorem: Quotient Ring is Ring

Let $\struct {R, +, \circ}$ be a ring.
Let $J$ be an ideal of $R$.
Let $\struct {R / J, +, \circ}$ be the quotient ring of $R$ by $J$.
Then $R / J$ is also a ring.

Proof:
First, it is to be shown that $+$ and $\circ$ are in fact well-defined operations on $R / J$.
Theorem: Ideal is Additive Normal Subgroup

Let $\left({R, +, \circ}\right)$ be a ring.
Let $J$ be an ideal of $R$.
Then $\left({J, +}\right)$ is a normal subgroup of $\left({R, +}\right)$.

Proof:
As $J$ is an ideal, $\left({J, +}\right)$ is a subgroup of $\left({R, +}\right)$.
By definition of a ring, $\left({R, +}\right)$ is abelian.
The result follows from Subgroup of Abelian Group is Normal.
{{qed}}
Category:Ideal Theory
eas96ddq9bmt95eqmyswfp6se6v6le4
Theorem: Congruence Relation on Ring induces Ring

Let $\struct {R, +, \circ}$ be a ring.
Let $\EE$ be a congruence relation on $R$ for both $+$ and $\circ$.
Let $R / \EE$ be the quotient set of $R$ by $\EE$.
Let $+_\EE$ and $\circ_\EE$ be the operations induced on $R / \EE$ by $+$ and $\circ$ respectively.
Then $\struct {R / \EE, +_\EE, \circ_\EE}$ is a ring.

Proof:
Let $q_\EE$ be the quotient mapping from $\struct {R, +, \circ}$ to $\struct {R / \EE, +_\EE, \circ_\EE}$.
From Quotient Mapping on Structure is Epimorphism:
:$q_\EE: \struct {R, +} \to \struct {R / \EE, +_\EE}$ is an epimorphism
:$q_\EE: \struct {R, \circ} \to \struct {R / \EE, \circ _\EE}$ is an epimorphism.
As the morphism property holds for both $+$ and $\circ$, it follows that $q_\EE: \struct {R, +, \circ} \to \struct {R / \EE, +_\EE, \circ_\EE}$ is also an epimorphism.
From Epimorphism Preserves Rings, it follows that $\struct {R / \EE, +_\EE, \circ_\EE}$ is a ring.
{{qed}}
Theorem: Subring is not necessarily Ideal

Let $\struct {R, +, \circ}$ be a ring.
Let $\struct {S, +_S, \circ_S}$ be a subring of $R$.
Then it is not necessarily the case that $S$ is also an ideal of $R$.

Proof:
Consider the field of real numbers $\struct {\R, +, \times}$.
We have that a field is by definition a ring, hence so is $\struct {\R, +, \times}$.
From Rational Numbers form Subfield of Real Numbers and Integers form Subdomain of Rationals, it follows that the integers $\struct {\Z, +, \times}$ are a subring of $\struct {\R, +, \times}$.
Consider $1 \in \Z$, and consider $\dfrac 1 2 \in \R$.
We have that $1 \times \dfrac 1 2 = \dfrac 1 2 \notin \Z$.
From this counterexample it is seen that $\Z$ is not an ideal of $R$.
Hence the result, again by Proof by Counterexample.
{{qed}}
Theorem: Characterization of Integrable Functions

Let $\struct {X, \Sigma, \mu}$ be a measure space.
Let $f: X \to \overline \R, f \in \MM_{\overline \R}$ be a $\Sigma$-measurable function.
{{TFAE}}
{{begin-itemize}}
{{item|(1):|$f \in \map {\LL_{\overline \R} } \mu$, that is, $f$ is $\mu$-integrable}}
{{item|(2):|The positive and negative parts $f^+$ and $f^-$ are $\mu$-integrable}}
{{item|(3):|The absolute value $\size f$ of $f$ is $\mu$-integrable}}
{{item|(4):|There exists an $\mu$-integrable function $g: X \to \overline \R$ such that $\size f \le g$ pointwise}}
{{end-itemize}}
{{refactor|level = advanced|Several results here, making specific referencing imprecise}}

Proof:
We prove the whole cycle of implications:
:$(1) \implies (2) \quad$ by definition of $(1)$
:$(2) \implies (3)\quad$ because $\size f =  f^+ + f^-$ and Integral of Positive Measurable Function is Additive 
:$(3) \implies (4)\quad$ because $g:= \size f$ exists
It remains to demonstrate $(4) \implies (1)$.
Let $f \in \MM_{\overline \R}$ and $g$ according to $(4)$.
Then:
:$f = f^+ - f^-$
where $f^+$ is the positive and $f^-$ is the negative part of $f$.
We have that $f^+$ and $f^-$ are positive and measurable.
Let $f^0$ stand for either $f^+$ or $f^-$.
We have that:
:$\size f = f^+ + f^-$
Therefore:
:$f^0 \le \size f \le g$
It is to be shown that the Integral of Positive Measurable Function of $f^0$ exists and is finite.
Let $\EE^+$ and $\map {I_\mu} h$ be defined as in Integral of Positive Measurable Function.
Then:
:$\forall h \in \EE^+$: $h \le f^0 \implies h \le g$
Hence:
:$\set {h: h \le f^0, h \in \EE^+} \subseteq \set {h: h \le g, h \in \EE^+}$
:$\ds \int f^0 \rd \mu := \sup \set {\map {I_\mu} h: h \le f^0, h \in \EE^+} \le \sup \set {\map {I_\mu} h: h \le g, h \in \EE^+} < \infty$
We have that the integrals for $f^+$ and $f^-$ both are finite.
Therefore $f$ is $\mu$-integrable according to definition.
{{qed}}
{{MissingLinks|The steps in the above need to be demonstrated and explained by linking to appropriate results on {{ProofWiki}} As it stands, none of the above can be followed without knowing all about this subject.}}.
Theorem: Quotient Ring is Ring/Quotient Ring Addition is Well-Defined

Let $\struct {R, +, \circ}$ be a ring whose zero is $0_R$ and whose unity is $1_R$.
Let $J$ be an ideal of $R$.
Let $\struct {R / J, +, \circ}$ be the quotient ring of $R$ by $J$.
Then $+$ is well-defined on $R / J$, that is:
:$x_1 + J = x_2 + J, y_1 + J = y_2 + J \implies \paren {x_1 + y_1} + J = \paren {x_2 + y_2} + J$

Proof:
From Ideal is Additive Normal Subgroup that $J$ is a normal subgroup of $R$ under $+$.
Thus, the quotient group $\struct {R / J, +}$ is defined, and as a Quotient Group is Group, $+$ is well-defined.
Theorem: Implicitly Defined Real-Valued Function

Let $F: \struct {\mathbf X' \subseteq \R^{n + 1} } \to \struct {\mathbb I' \subseteq \R}$ have continuous partial derivatives. 
{{explain|Can the language of this be brought into line with existing definitions of implicit functions?}}
Let $\tuple {\mathbf x, z}$ denote an element of $\R^{n + 1}$, where $\mathbf x \in \R^n$ and $z \in \R$.
Suppose $\exists \tuple {\mathbf x_0, z_0} \in \mathbf X'$ such that:
:$\map F {\mathbf x_0, z_0} = 0$
:$\dfrac \partial {\partial z} \map F {\mathbf x_0, z_0} \ne 0$
Then there exists a unique mapping of the form:
:$g: \mathbf X \to \mathbb I$
where $\mathbf X \subseteq \R^n$ contains $\mathbf x_0$ and $\mathbb I$ is an open real interval containing $z_0$, such that:
:$\forall \mathbf x \in \mathbf X, z \in \mathbb I: \map F {\mathbf x, z} = 0 \iff z = \map g {\mathbf x}$
and $g$ itself has continuous partial derivatives.
{{proofread}}

Proof:
This is a special case of the Implicit Function Theorem.
{{qed}}
Theorem: Characteristic Function of Subset

Let $A \subseteq B \subseteq S$.
Then:
:$\forall s \in S: \map {\chi_A} s \le \map {\chi_B} s$
where $\chi$ denotes characteristic function.

Proof:
Both $\chi_A$ and $\chi_B$ take values in $\set {0, 1}$ as they are characteristic functions.
So if $\map {\chi_A} s = 0$, then the statement of the theorem is automatically satisfied (since both $0 \le 0$ and $0 \le 1$).
Now assume $\map {\chi_A} s = 1$.
By definition of $\chi_A$, this happens {{iff}} $s \in A$.
But as $A \subseteq B$, this implies $s \in B$ as well.
Hence, $\map {\chi_B} s = 1$, and so $\map {\chi_A} s \le \map {\chi_B} s$.
The theorem follows from Proof by Cases.
{{qed}}
Category:Characteristic Functions
94w3jp4ivudtmmoj3ijkep6gmilq615
Theorem: Characteristic Function Determined by 0-Fiber

Let $A \subseteq S$.
Let $f: S \to \set {0, 1}$ be a mapping.
Denote by $\chi_A$ the characteristic function on $A$.
{{TFAE}}
{{begin-itemize}}
{{item|(1):|$f {{=}} \chi_A$}}
{{item|(2):|$\forall s \in S: \map f s {{=}} 0 \iff s \notin A$}}
{{end-itemize}}
Using the notion of a fiber, $(2)$ may also be expressed as:
:$(2'): \quad \map {f^{-1} } 0 = S \setminus A$

Proof:
=== $(1)$ implies $(2)$ ===
Follows directly from the definition of characteristic function.
{{qed|lemma}}
Theorem: Ideal induced by Congruence Relation defines that Congruence

Let $\struct {R, +, \circ}$ be a ring.
Let $\EE$ be a congruence relation on $R$.
Let $J = \eqclass {0_R} \EE$ be the ideal induced by $\EE$.
Then the equivalence defined by the coset space $\struct {R, +} / \struct {J, +}$ is $\EE$ itself.

Proof:
Let $J = \eqclass {0_R} \EE$.
From Congruence Relation on Ring induces Ideal, we have that $J$ is an ideal of $R$.
From Ideal is Additive Normal Subgroup, we have that $\struct {J, +}$ is a normal subgroup of $\struct {R, +}$.
From Normal Subgroup induced by Congruence Relation defines that Congruence, the equivalence defined by the partition $\struct {R, +} / \struct {J, +}$ is $\EE$.
As $\EE$ was the congruence relation on $R$ that was originally posited, we already know that it is compatible with $\circ$.
Thus the equivalence defined by $J$ is the same congruence relation on $R$ that gave rise to $J$ to start with.
Hence the result.
{{qed}}
Theorem: Rational Numbers form Null Set under Lebesgue Measure

Let $\lambda$ be $1$-dimensional Lebesgue measure on $\R$.
Let $\Q$ be the set of rational numbers.
Then:
:$\map \lambda \Q = 0$
that is, $\Q$ is a $\lambda$-null set.

Proof:
We have that the Rational Numbers are Countably Infinite.
The result follows from Countable Set is Null Set under Lebesgue Measure.
{{qed}}
Theorem: Cartesian Product of Intersections/General Case

:$\ds \paren {\prod_{i \mathop \in I} S_i} \cap \paren {\prod_{i \mathop \in I} T_i} = \prod_{i \mathop \in I} \paren {S_i \cap T_i}$

Proof:
Let $\family {x_i}_{i \mathop \in I} \in \ds \paren {\prod_{i \mathop \in I} S_i} \cap \paren {\prod_{i \mathop \in I} T_i}$.
By definition of intersection, this is equivalent to the conjunction of:
:$\family {x_i}_{i \mathop \in I} \in \ds \prod_{i \mathop \in I} S_i$
:$\family {x_i}_{i \mathop \in I} \in \ds \prod_{i \mathop \in I} T_i$
By definition of Cartesian product, this means, for all $i \in I$:
:$x_i \in S_i$ and $x_i \in T_i$
Again by definition of intersection, this is equivalent to, for all $i \in I$:
:$x_i \in S_i \cap T_i$
Finally, by definition of Cartesian product, this is equivalent to:
:$\family {x_i}_{i \mathop \in I} \in \ds \prod_{i \mathop \in I} \paren {S_i \cap T_i}$
The result follows by definition of set equality.
{{qed}}
Category:Cartesian Product of Intersections
k3skgdc4gf80sgg3o70nsj5hv8etzcz
Theorem: Cartesian Product of Semirings of Sets

Let $\SS$ and $\TT$ be semirings of sets.
Then $\SS \times \TT$ is also a semiring of sets.
Here, $\times$ denotes Cartesian product.

Proof:
Recall the conditions for $\SS \times \TT$ to be a semiring of sets:
:$(1): \quad \O \in \SS \times \TT$
:$(2): \quad \SS \times \TT$ is $\cap$-stable
:$(3'):\quad$ If $A, B \in \SS \times \TT$, then there exists a finite sequence of pairwise disjoint sets $A_1, A_2, \ldots, A_n \in \SS \times \TT$ such that $\ds A \setminus B = \bigcup_{k \mathop = 1}^n A_k$.
Theorem: Congruence Relation on Group induces Normal Subgroup

Let $\struct {G, \circ}$ be a group whose identity is $e$.
Let $\RR$ be a congruence relation for $\circ$.
Let $H = \eqclass e \RR$, where $\eqclass e \RR$ is the equivalence class of $e$ under $\RR$.
Then:
:$\struct {H, \circ \restriction_H}$ is a normal subgroup of $G$
where $\circ \restriction_H$ denotes the restriction of $\circ$ to $H$.

Proof:
We are given that $\RR$ is a congruence relation for $\circ$.
From Equivalence Relation is Congruence iff Compatible with Operation, we have:
:$\forall u \in G: x \mathrel \RR y \implies \paren {x \circ u} \mathrel \RR \paren {y \circ u}, \paren {u \circ x} \mathrel \RR \paren {u \circ y}$
==== Proof of being a Subgroup ====
We show that $H$ is a subgroup of $G$.
First we note that $H$ is not empty:
:$e \in H \implies H \ne \O$
Then we show $H$ is closed:
{{begin-eqn}}
{{eqn | l = x, y
      | o = \in
      | r = H
      | c = 
}}
{{eqn | ll= \leadsto
      | l = e
      | o = \RR
      | r = x
      | c = 
}}
{{eqn | lo= \land
      | l = e
      | o = \RR
      | r = y
      | c = by definition of $H$
}}
{{eqn | ll= \leadsto
      | l = \paren {e \circ e}
      | o = \RR
      | r = \paren {x \circ y}
      | c = $\RR$ is compatible with $\circ$
}}
{{eqn | ll= \leadsto
      | l = x \circ y
      | o = \in
      | r = H
      | c = by definition of $H$
}}
{{end-eqn}}
Next we show that $x \in H \implies x^{-1} \in H$:
{{begin-eqn}}
{{eqn | l = x
      | o = \in
      | r = H
      | c = 
}}
{{eqn | ll= \leadsto
      | l = e
      | o = \RR
      | r = x
      | c = Definition of $H$
}}
{{eqn | ll= \leadsto
      | l = \paren {x^{-1} \circ e}
      | o = \RR
      | r = \paren {x^{-1} \circ x}
      | c = $\RR$ is compatible with $\circ$
}}
{{eqn | ll= \leadsto
      | l = x^{-1}
      | o = \RR
      | r = e
      | c = Group properties
}}
{{eqn | ll= \leadsto
      | l = x^{-1}
      | o = \in
      | r = H
      | c = Definition of $H$
}}
{{end-eqn}}
Thus by the Two-Step Subgroup Test, $H$ is a subgroup of $G$.
{{qed|lemma}}
==== Proof of Normality ====
Next we show that $H$ is normal in $G$.
Thus:
{{begin-eqn}}
{{eqn | l = x
      | o = \in
      | r = H
      | c = 
}}
{{eqn | ll= \leadsto
      | l = e
      | o = \RR
      | r = h
      | c = for some $h \in H$, by definition of $H$
}}
{{eqn | ll= \leadsto
      | l = \paren {x \circ e}
      | o = \RR
      | r = \paren {x \circ h}
      | c = $\RR$ is compatible with $\circ$
}}
{{eqn | ll= \leadsto
      | l = \paren {x \circ e \circ x^{-1} }
      | o = \RR
      | r = \paren {x \circ h \circ x^{-1} }
      | c = $\RR$ is compatible with $\circ$
}}
{{eqn | ll= \leadsto
      | l = e
      | o = \RR
      | r = \paren {x \circ h \circ x^{-1} }
      | c = Group properties
}}
{{eqn | ll= \leadsto
      | l = x \circ h \circ x^{-1}
      | o = \in
      | r = H
      | c = Definition of $H$
}}
{{end-eqn}}
Thus from Subgroup is Normal iff Contains Conjugate Elements, we have that $H$ is normal.
{{qed}}