avewright/proofwiki-math huggingface dataset:
Theorem: Number of Hamilton Cycles in Complete Graph

For all $n \ge 3$, the number of distinct Hamilton cycles in the complete graph $K_n$ is $\dfrac {\paren {n - 1}!} 2$.

Proof:
In a complete graph, every vertex is adjacent to every other vertex.
Therefore, if we were to take all the vertices in a complete graph in any order, there will be a path through those vertices in that order.
Joining either end of that path gives us a Hamilton cycle.
From Cardinality of Set of Bijections, there are $n!$ different ways of picking the vertices of $G$ in some order.
Hence there are $n!$ ways of building such a Hamilton cycle.
Not all these are different, though.
On any such cycle, there are:
:$n$ different places you can start
:$2$ different directions you can travel.
So any one of these $n!$ cycles is in a set of $2 n$ cycles which all contain the same sequence of edges.
So there are $\dfrac {n!} {2 n} = \dfrac {\paren {n - 1}!} 2$ distinct Hamilton cycles.
{{qed}}
Category:Hamiltonian Graphs
Category:Combinatorics
b6u7y1zqmmg7vd52imocvcpdmbzw2f5
Theorem: Coreflexive Relation is Subset of Diagonal Relation

A coreflexive relation is a subset of the diagonal relation.

Proof:
Let $\RR \subseteq S \times S$ be a coreflexive relation.
Let $\tuple {x, y} \in \RR$.
By definition of coreflexive, it follows that $x = y$, and hence $\tuple {x, y} = \tuple {x, x}$.
So by definition of the diagonal relation:
:$\tuple {x, y} \in \Delta_S$
Hence the result.
{{qed}}
Category:Coreflexive Relations
Category:Diagonal Relation
4q8huu5aj0tw2irad0l45pphcwzzku6
Theorem: Reflexive Euclidean Relation is Equivalence

A relation is an equivalence {{iff}} it is either left-Euclidean or right-Euclidean, and also reflexive.

Proof:
=== Sufficient Condition ===
Let $\RR$ be an equivalence relation.
Then by definition it is reflexive.
It is also transitive and symmetric.
So, let $x, y, z \in \RR$ such that $x \mathrel \RR y$ and $x \mathrel \RR z$.
From symmetry, we have $y \mathrel \RR x$, and by transitivity it follows that $y \mathrel \RR z$.
Hence $\RR$ is right-Euclidean.
Now let $x, y, z \in \RR$ such that $x \mathrel \RR z$ and $y \mathrel \RR z$.
From symmetry, we have $z \mathrel \RR y$, and by transitivity it follows that $x \mathrel \RR y$.
Hence $\mathrel \RR$ is left-Euclidean.
So $\mathrel \RR$ is '''both''' left-Euclidean and right-Euclidean.
We know by definition that it is reflexive.
Thus an equivalence relation is both left-Euclidean and right-Euclidean and also reflexive.
Theorem: Reflexive Relation is Serial

Every reflexive relation is also a serial relation.

Proof:
Let $\RR \subseteq S \times S$ be a relation in $S$.
We have that $\RR$ is serial {{iff}}:
:$\forall x \in S: \exists y \in S: \tuple {x, y} \in \RR$
That is, {{iff}} every element relates to at least one element.
We have that $\RR$ is reflexive {{iff}}:
:$\forall x \in S: \tuple {x, x} \in \RR$
Hence if $\RR$ is reflexive, every $x$ is related to itself, thereby fulfilling the criterion for $\RR$ to be serial.
{{qed}}
Category:Reflexive Relations
Category:Serial Relations
glrh822q4qiqs94kxeupq6v2ufnizev
Theorem: Complement of Complete Bipartite Graph

Let $K_{p, q}$ be a complete bipartite graph.
The complement of $K_{p, q}$ consists of a disconnected graph with two components:
:The complete graph $K_p$
:The complete graph $K_q$.

Proof:
By definition, the complete bipartite graph $K_{p, q}$ consists of two sets of vertices: $A$ of cardinality $p$, and $B$ of cardinality $q$, such that:
:Every vertex in $A$ is adjacent to every vertex in $B$
:No vertex in $A$ is adjacent to any other vertex in $A$
:No vertex in $B$ is adjacent to any other vertex in $B$.
The complement of $K_{p, q}$ therefore must be a graph $G$ such that:
:No vertex in $A$ is adjacent to any vertex in $B$
:Every vertex in $A$ is adjacent to every other vertex in $A$
:Every vertex in $B$ is adjacent to every other vertex in $B$.
The second and third of these conditions describes the complete graphs $K_p$ and $K_q$.
From the first of these conditions, it follows that $G$ comes in two disconnected graph components.
Hence the result.
{{qed}}
Category:Bipartite Graphs
4a3yu1at7zsk2bdzjhseodlc0qv808t
Theorem: Complement of Strict Total Ordering

Let $\struct {S, \prec}$ be a relational structure such that $\prec$ is a strict total ordering.
Then the complement of $\prec$ is a weak total ordering.

Proof:
We need to show that $\nprec$ is a weak total ordering.
First we check in turn each of the criteria for an ordering:
Theorem: Strict Weak Ordering Induces Partition

Let $\struct {S, \prec}$ be a relational structure such that $\prec$ is a strict weak ordering on $S$.
Then $S$ can be partitioned into equivalence classes whose equivalence relation is "is non-comparable".
That is, each of the partitions $A$ of $S$ is a relational structure $\struct {\mathbb S, <}$ such that:
:$\mathbb S$ is the set of these partitions of $S$;
:$<$ is the strict total ordering on $\mathbb S$ '''induced by''' $\prec$.

Proof:
From the definition of strict weak ordering, we define the symbol $\Bumpeq$ as:
:$a \Bumpeq b := \neg a \prec b \land \neg b \prec a$
that is, $a \Bumpeq b$ means "$a$ and $b$ are non-comparable".
Checking in turn each of the criteria for equivalence:
Theorem: Mahler's Inequality

The geometric mean of the termwise sum of two finite sequences of positive real numbers is never less than the sum of their two separate geometric means:
:$\ds \prod_{k \mathop = 1}^n \paren {x_k + y_k}^{1/n} \ge \prod_{k \mathop = 1}^n x_k^{1/n} + \prod_{k \mathop = 1}^n y_k^{1/n}$
where $x_k, y_k > 0$ for all $k$.

Proof:
{{begin-eqn}}
{{eqn | l = \prod_{k \mathop = 1}^n \paren {\frac {x_k} {x_k + y_k} }^{1/n}
      | o = \le
      | r = \frac 1 n \sum_{k \mathop = 1}^n \frac {x_k} {x_k + y_k}
      | c = Cauchy's Mean Theorem
}}
{{eqn | l = \prod_{k \mathop = 1}^n \paren {\frac {y_k} {x_k + y_k} }^{1/n}
      | o = \le
      | r = \frac 1 n \sum_{k \mathop = 1}^n \frac {y_k} {x_k + y_k}
      | c = Cauchy's Mean Theorem
}}
{{eqn | ll= \leadsto
      | l = \prod_{k \mathop = 1}^n \paren {\frac {x_k} {x_k + y_k} }^{1/n} + \prod_{k \mathop = 1}^n \paren {\frac {y_k} {x_k + y_k} }^{1/n}
      | o = \le
      | r = \frac 1 n \sum_{k \mathop = 1}^n \frac {x_k} {x_k + y_k} + \frac 1 n \sum_{k \mathop = 1}^n \frac {y_k} {x_k + y_k}
      | c = adding them together
}}
{{eqn | r = \frac 1 n \sum_{k \mathop = 1}^n \frac {x_k + y_k} {x_k + y_k}
      | c = 
}}
{{eqn | r = \frac 1 n n
      | c = 
}}
{{eqn | r = 1
      | c = 
}}
{{end-eqn}}
This leads to:
{{begin-eqn}}
{{eqn | l = \prod_{k \mathop = 1}^n \paren {\frac {x_k} {x_k + y_k} }^{1/n} + \prod_{k \mathop = 1}^n \paren {\frac {y_k} {x_k + y_k} }^{1/n}
      | o = \le
      | r = 1
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \frac {\ds \prod_{k \mathop = 1}^n \paren {x_k}^{1/n} } {\ds \prod_{k \mathop = 1}^n \paren {x_k + y_k}^{1/n} } + \frac {\ds \prod_{k \mathop = 1}^n \paren {y_k}^{1/n} } {\ds \prod_{k \mathop = 1}^n \paren {x_k + y_k}^{1/n} }
      | o = \le
      | r = 1
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \frac {\ds \prod_{k \mathop = 1}^n \paren {x_k}^{1/n} + \prod_{k \mathop = 1}^n \paren {y_k}^{1/n} } {\ds \prod_{k \mathop = 1}^n \paren {x_k + y_k}^{1/n} }
      | o = \le
      | r = 1
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \prod_{k \mathop = 1}^n \paren {x_k}^{1/n} + \prod_{k \mathop = 1}^n \paren {y_k}^{1/n}
      | o = \le
      | r = \prod_{k \mathop = 1}^n \paren {x_k + y_k}^{1/n}
      | c = 
}}
{{end-eqn}}
{{qed}}
{{Namedfor|Kurt Mahler|cat = Mahler}}
Category:Algebra
Category:Measures of Central Tendency
bj85m005h7tm9vom35ryqij4kyyt8od
Theorem: Equivalence of Definitions of Transitive Closure of Relation/Intersection is Smallest

Let $\RR$ be a relation on a set $S$.
Then the intersection of all transitive relations on $S$ that contain $\RR$ is the smallest transitive relation on $S$ that contains $\RR$.

Proof:
Note that the trivial relation $\TT = S \times S$ on $S$ contains $\RR$, by the definition of a relation on $S$.
Further, $\TT$ is transitive by Trivial Relation is Equivalence.
Thus there is at least one transitive relation on $S$ that contains $\RR$.
Now define $\RR^+$ as the intersection of all transitive relations on $S$ that contain $\RR$:
:$\ds \RR^+ := \bigcap \set {\RR': \text {$\RR'$ is transitive and $\RR \subseteq \RR'$} }$
By Intersection of Transitive Relations is Transitive, $\RR^+$ is also a transitive relation on $S$.
By Set Intersection Preserves Subsets, it also holds that $\RR \subseteq \RR^+$.
Lastly, by Intersection is Subset, for any transitive relation $\RR'$ containing $\RR$, it must be that $\RR^+ \subseteq \RR'$.
Thus $\RR^+$ is indeed the smallest transitive relation on $S$ containing $\RR$.
{{qed}}
Theorem: Intersection of Transitive Relations is Transitive

The intersection of two transitive relations is also a transitive relation.

Proof:
Let $\RR_1$ and $\RR_2$ be transitive relations on an arbitrary set $S$.
Let $\tuple {s_1, s_2} \in \RR_1 \cap \RR_2$ and $\tuple {s_2, s_3} \in \RR_1 \cap \RR_2$.
Then by definition of intersection:
:$\tuple {s_1, s_2} \in \RR_1$ and $\tuple {s_1, s_2} \in \RR_2$
:$\tuple {s_2, s_3} \in \RR_1$ and $\tuple {s_2, s_3} \in \RR_2$
Then as $\RR_1$ and $\RR_2$ are both transitive:
:$\tuple {s_1, s_3} \in \RR_1$ and $\tuple {s_1, s_3} \in \RR_2$
and by definition of intersection:
:$\tuple {s_1, s_3} \in \RR_1 \cap \RR_2$
hence $\RR_1 \cap \RR_2$ is transitive.
{{qed}}
Category:Intersection of Transitive Relations is Transitive
Category:Transitive Relations
Category:Set Intersection
gfwfwn6qabwfj44f5tf6ho57py3skbn
Theorem: Intersection of Reflexive Relations is Reflexive

The intersection of two reflexive relations is also a reflexive relation.

Proof:
Let $\RR_1$ and $\RR_2$ be reflexive relations on a set $S$.
From Relation Contains Diagonal Relation iff Reflexive, we have that:
: $\Delta_S \subseteq \RR_1$
: $\Delta_S \subseteq \RR_2$
Hence from Intersection is Largest Subset:
: $\Delta_S \subseteq \RR_1 \cap \RR_2$
Hence the result, from Relation Contains Diagonal Relation iff Reflexive.
{{qed}}
Category:Reflexive Relations
Category:Set Intersection
sqsqb8vlgz8upv3njcflp89ng7v67wa
Theorem: Intersection of Symmetric Relations is Symmetric

The intersection of two symmetric relations is also a symmetric relation.

Proof:
Let $\RR_1$ and $\RR_2$ be symmetric relations on a set $S$.
Let $\RR_3 = \RR_1 \cap \RR_2$.
Then:
{{begin-eqn}}
{{eqn | l = \tuple {x, y}
      | o = \in
      | r = \RR_3
      | c =
}}
{{eqn | ll= \leadsto
      | l = \tuple {x, y}
      | o = \in
      | r = \RR_1
      | c = {{Defof|Set Intersection}}
}}
{{eqn | lo= \land
      | l = \tuple {x, y}
      | o = \in
      | r = \RR_2
      | c =
}}
{{eqn | ll= \leadsto
      | l = \tuple {y, x}
      | o = \in
      | r = \RR_1
      | c = {{Defof|Symmetric Relation}}
}}
{{eqn | lo= \land
      | l = \tuple {y, x}
      | o = \in
      | r = \RR_2
}}
{{eqn | ll= \leadsto
      | l = \tuple {y, x}
      | o = \in
      | r = \RR_3
      | c = {{Defof|Set Intersection}}
}}
{{end-eqn}}
{{qed}}
Category:Symmetric Relations
Category:Set Intersection
8pzufp5ukmtw5agh2uogv1scrulfqv9
Theorem: Union of Reflexive Relations is Reflexive

The union of two reflexive relations is also a reflexive relation.

Proof:
Let $\RR_1$ and $\RR_2$ be reflexive relations on a set $S$.
From Relation Contains Diagonal Relation iff Reflexive, we have that:
: $\Delta_S \subseteq \RR_1$
: $\Delta_S \subseteq \RR_2$
Hence from Subset Relation is Transitive:
: $\Delta_S \subseteq \RR_1 \cup \RR_2$
Hence the result, by definition of reflexive relation.
{{qed}}
Category:Reflexive Relations
Category:Set Union
ccqf3heksm0vauibsdpd3f8hadxav00
Theorem: Union of Symmetric Relations is Symmetric

The union of two symmetric relations is also a symmetric relation.

Proof:
Let $\RR_1$ and $\RR_2$ be symmetric relations on a set $S$.
Let $\RR_3 = \RR_1 \cup \RR_2$.
Then:
{{begin-eqn}}
{{eqn | l = \tuple {x, y}
      | o = \in
      | r = \RR_3
      | c =
}}
{{eqn | ll= \leadsto
      | l = \tuple {x, y}
      | o = \in
      | r = \RR_1
      | c = {{Defof|Set Union}}
}}
{{eqn | lo= \lor
      | l = \tuple {x, y}
      | o = \in
      | r = \RR_2
      | c =
}}
{{eqn | ll= \leadsto
      | l = \tuple {y, x}
      | o = \in
      | r = \RR_1
      | c = {{Defof|Symmetric Relation}}
}}
{{eqn | lo= \lor
      | l = \tuple {y, x}
      | o = \in
      | r = \RR_2
      | c =
}}
{{eqn | ll= \leadsto
      | l = \tuple {y, x}
      | o = \in
      | r = \RR_3
      | c = {{Defof|Set Union}}
}}
{{end-eqn}}
{{qed}}
Category:Symmetric Relations
Category:Set Union
jwm4rwtov5t6vkzhltys6jjm4z9esq6
Theorem: Union of Transitive Relations Not Always Transitive

The union of transitive relations is not necessarily itself transitive.

Proof:
Proof by counterexample:
Let $S = \set {a, b, c, d}$.
Let $\RR_1$ be the transitive relation $\set {\tuple {a, b}, \tuple {b, c}, \tuple {a, c} }$.
Let $\RR_2$ be the transitive relation $\set {\tuple {b, c}, \tuple {c, d}, \tuple {b, d} }$.
Then we have that $\tuple {a, b} \in \RR_1 \cup \RR_2$ and $\tuple {b, d} \in \RR_1 \cup \RR_2$.
However, $\tuple {a, d} \notin \RR_1 \cup \RR_2$, and so $\RR_1 \cup \RR_2$ is not transitive.
{{qed}}
Category:Transitive Relations
Category:Set Union
ja9x5q1i1pnxh46bnj8d1jv6ykh6bip
Theorem: Set System Closed under Intersection is Commutative Semigroup

Let $\SS$ be a system of sets.
Let $\SS$ be such that:
:$\forall A, B \in \SS: A \cap B \in \SS$
Then $\struct {\SS, \cap}$ is a commutative semigroup.

Proof:
=== Closure ===
We have {{hypothesis}} that $\struct {\SS, \cap}$ is closed.
Theorem: Set System Closed under Union is Commutative Semigroup

Let $\SS$ be a system of sets.
Let $\SS$ be such that:
:$\forall A, B \in \SS: A \cup B \in \SS$
Then $\struct {\SS, \cup}$ is a commutative semigroup.

Proof:
===  Closure ===
We have {{hypothesis}} that $\struct {\SS, \cup}$ is closed.
Theorem: Set System Closed under Symmetric Difference is Abelian Group

Let $\SS$ be a system of sets.
Let $\SS$ be such that:
:$\forall A, B \in \SS: A \symdif B \in \SS$
where $A \symdif B$ denotes the symmetric difference between $A$ and $B$.
Then $\struct {\SS, \symdif}$ is an abelian group.

Proof:
=== {{Group-axiom|0|nolink}} ===
By presupposition on $\SS$, $\struct {\SS, \symdif}$ is closed.
{{qed|lemma}}
Theorem: Ring of Sets is Commutative Ring

A ring of sets $\struct {\RR, \symdif, \cap}$ is a commutative ring whose zero is $\O$.

Proof:
By definition, the operations $\cap$ and $\symdif$ are closed in $\RR$.
Hence we can apply the following results:
* Set System Closed under Symmetric Difference is Abelian Group: $\struct {\RR, \symdif}$ is an abelian group.
* Set System Closed under Intersection is Commutative Semigroup: $\struct {\RR, \cap}$ is a commutative semigroup.
* Intersection Distributes over Symmetric Difference.
* The identity of $\struct {\RR, \symdif}$ is $\O$, and this, by definition, is the zero.
So $\struct {\RR, \symdif, \cap}$ is a commutative ring whose zero is $\O$.
{{qed}}
Category:Commutative Rings
Category:Rings of Sets
tw5km224lhuknkmzsioujjhntrar11p
Theorem: Union as Symmetric Difference with Intersection

Let $A$ and $B$ be sets.
Then:
:$A \cup B = \paren {A \symdif B} \symdif \paren {A \cap B}$
where:
:$A \cup B$ denotes set union
:$A \cap B$ denotes set intersection
:$A \symdif B$ denotes set symmetric difference

Proof:
From the definition of symmetric difference:
:$\paren {A \symdif B} \symdif \paren {A \cap B} = \paren {\paren {A \symdif B} \cup \paren {A \cap B} } \setminus \paren {\paren {A \symdif B} \cap \paren {A \cap B} }$
Also from the definition of symmetric difference:
:$\paren {A \symdif B} \cap \paren {A \cap B} = \paren {\paren {A \cup B} \setminus \paren {A \cap B} } \cap \paren {A \cup B}$
From Set Difference Intersection with Second Set is Empty Set:
:$\paren {S \setminus T} \cap T = \O$
Hence:
:$\paren {\paren {A \cup B} \setminus \paren {A \cup B} } \cap \paren {A \cup B} = \O$
This leaves:
{{begin-eqn}}
{{eqn | o = 
      | r = \paren {\paren {A \symdif B} \cup \paren {A \cap B} } \setminus \paren {\paren {A \symdif B} \cap \paren {A \cap B} }
      | c = 
}}
{{eqn | r = \paren {\paren {A \symdif B} \cup \paren {A \cap B} } \setminus \O
      | c = 
}}
{{eqn | r = \paren {A \symdif B} \cup \paren {A \cap B}
      | c = Set Difference with Empty Set is Self
}}
{{end-eqn}}
Then:
{{begin-eqn}}
{{eqn | o = 
      | r = \paren {A \symdif B} \cup \paren {A \cap B}
      | c = 
}}
{{eqn | r = \paren {A \setminus B} \cup \paren {B \setminus A} \cup \paren {A \cap B}
      | c = {{Defof|Symmetric Difference|index = 1}}
}}
{{eqn | r = \paren {\paren {A \setminus B} \cup \paren {A \cap B} } \cup \paren {\paren {B \setminus A} \cup \paren {A \cap B} }
      | c = Set Union is Idempotent, Union is Commutative and Union is Associative
}}
{{eqn | r = A \cup B
      | c = Set Difference Union Intersection
}}
{{end-eqn}}
Hence the result.
{{qed}}
Category:Set Union
Category:Set Intersection
Category:Symmetric Difference
5auxwnyosv2f6eymvelr3lc90iih6bp
Theorem: Set Difference as Symmetric Difference with Intersection

:$S \setminus T = S \symdif \paren {S \cap T}$
where:
:$S \setminus T$ denotes set difference
:$S \symdif T$ denotes set symmetric difference
:$S \cap T$ denotes set intersection.

Proof:
{{begin-eqn}}
{{eqn | l = S \symdif \paren {S \cap T}
      | r = \paren {S \setminus \paren {S \cap T} } \cup \paren {\paren {S \cap T} \setminus S}
      | c = {{Defof|Symmetric Difference}}
}}
{{eqn | r = \paren {S \setminus \paren {S \cap T} } \cup \O
      | c = Set Difference of Intersection with Set is Empty Set
}}
{{eqn | r = \paren {S \setminus T} \cup \O
      | c = Set Difference with Intersection is Difference
}}
{{eqn | r = S \setminus T
      | c = Union with Empty Set
}}
{{end-eqn}}
{{qed}}
Category:Set Intersection
Category:Set Difference
Category:Symmetric Difference
1f49w6c33bh2rfh9hxv7d0dp03vuq9f
Theorem: Unit of System of Sets is Unique

The unit of a system of sets, if it exists, is unique.
If $U$ is the unit of a system of sets $\SS$, then $\forall A \in \SS: A \subseteq U$.

Proof:
Let $\SS$ be a system of sets.
Suppose $U$ and $U'$ are both units of $\SS$.
Then, by definition:
:$\forall A \in \SS: A \cap U = A$
:$\forall A \in \SS: A \cap U' = A$
This applies to both $U$ and $U'$, of course.
So $U \cap U' = U$ and $U' \cap U = U'$.
From Intersection with Subset is Subset it follows that $U \subseteq U'$ and $U' \subseteq U$.
By definition of set equality:
:$U = U'$
We also see that from Intersection with Subset is Subset, $A \cap U = A \iff A \subseteq U$, which shows that:
:$\forall A \in \SS: A \subseteq U$.
{{qed}}
Category:Set Systems
rd2yn9o9fe451p5dfp7ih4nbdlqvr3y
Theorem: Power Set is Algebra of Sets

Let $S$ be a set.
Let $\powerset S$ be the power set of $S$.
Then $\powerset S$ is an algebra of sets where $S$ is the unit.

Proof:
From Power Set is Closed under Intersection and Power Set is Closed under Symmetric Difference, we have that:
:$(1): \quad \forall A, B \in \powerset S: A \cap B \in \powerset S$
:$(2): \quad \forall A, B \in \powerset S: A * B \in \powerset S$
From the definition of power set:
:$\forall A \in \powerset S: A \subseteq S$
and so $S$ is the unit of $\powerset S$.
Thus we see that $\powerset S$ is a ring of sets with a unit.
Hence the result, by definition of an algebra of sets.
{{qed}}
Category:Power Set
Category:Algebras of Sets
1wxbt4bx0oywzpy1ridl2ptzl7mm25s
Theorem: Power Set is Closed under Intersection

Let $S$ be a set.
Let $\powerset S$ be the power set of $S$.
Then:
:$\forall A, B \in \powerset S: A \cap B \in \powerset S$

Proof:
Let $A, B \in \powerset S$.
Then by the definition of power set, $A \subseteq S$ and $B \subseteq S$.
From Intersection is Subset we have that $A \cap B \subseteq A$.
It follows from Subset Relation is Transitive that $A \cap B \subseteq S$.
Thus $A \cap B \in \powerset S$ and closure is proved.
{{qed}}
Theorem: Power Set is Closed under Symmetric Difference

Let $S$ be a set.
Let $\powerset S$ be the power set of $S$.
Then:
:$\forall A, B \in \powerset S: A \symdif B \in \powerset S$
where $A \symdif B$ is the symmetric difference between $A$ and $B$.

Proof:
Let $A, B \in \powerset S$.
Then by definition of power set:
:$A, B \subseteq S$
Then:
{{begin-eqn}}
{{eqn | l = A \symdif B
      | o = \subseteq
      | r = A \cup B
      | c = Symmetric Difference is Subset of Union
}}
{{eqn | o = \subseteq
      | r = S
      | c = Union is Smallest Superset
}}
{{eqn | ll= \leadsto
      | l = A \symdif B
      | o = \in
      | r = \powerset S
      | c = {{Defof|Power Set}}
}}
{{end-eqn}}
{{qed}}
Theorem: Intersection of Rings of Sets

Let $\RR_k$ be a ring of sets, where $k$ is an element of an arbitrary set of indices.
Then their intersection $\ds \RR = \bigcap_k \RR_k$ is itself a ring of sets.

Proof:
Consider the set $\ds \SS = \bigcup_k \RR_k$.
Let $S = \set {X \in Y: Y \in \SS}$.
This contains all the elements of all the sets contained in all the $\RR_k$.
Now consider the power set $\powerset S$ of $S$.
By Power Set is Algebra of Sets and the definition of algebra of sets, we have that $\powerset S$ is a ring of sets.
Thus $\struct {\powerset S, *, \cap}$ is a ring (in the abstract algebraic sense of the term).
From the method of construction of $\powerset S$, it follows that all the $\struct {\RR_k, *, \cap}$ are subrings of $\powerset S$.
The result then follows from Intersection of Subrings is Subring.
{{qed}}
Category:Rings of Sets
eqkl03p0cjp73qvycpausg9f2b00w5r
Theorem: Minimal Ring Generated by System of Sets

Let $\SS$ be a non-empty system of sets.
Then there is a unique ring of sets $\map \RR \SS$ which:
:$(1): \quad$ contains $\SS$
:$(2): \quad$ is contained by every ring of sets which also contains $\SS$.
This ring of sets $\map \RR \SS$ is called the '''minimal ring generated by $\SS$'''.

Proof:
=== Uniqueness ===
Suppose there were two such rings of sets $\map \RR \SS$ and $\map \RR \SS'$.
Then by definition their intersection $\map \RR \SS \cap \map \RR \SS'$ would also contain $\SS$.
By Intersection of Rings of Sets, $\map \RR \SS \cap \map \RR \SS'$ is also a ring of sets.
From Intersection is Subset, $\map \RR \SS \cap \map \RR \SS' \subseteq \map \RR \SS$ and $\map \RR \SS \cap \map \RR \SS' \subseteq \map \RR \SS'$.
Hence either $\map \RR \SS$ or $\map \RR \SS'$ can not be minimal.
So if $\map \RR \SS$ exists, it has to be unique.
Theorem: Menelaus's Theorem

Let $ABC$ be a triangle.
Let points $D, E, F$ lie on lines $BC, AC, AB$ respectively (produced if necessary).
Then $D, E$ and $F$ are collinear {{iff}}:
: $\dfrac {AF} {FB} \cdot \dfrac {BD} {DC} \cdot \dfrac {CE} {EA} = -1$
In the above, the line segments $AF, BD, EA$ are determined to have negative length if they lie outside the line segments $AB, BC, CA$.

Proof:
=== Necessary Condition ===
First we check that the equation works out negative.
From Pasch's Axiom, the line $DEF$ must intersect either two sides of $\triangle ABC$:
:500px
or none of them:
:500px
That means there is an odd number of negative contributions to the product.
Hence the equation works out to be negative.
Next, the magnitude can be checked.
The method is illustrated using the second of the above options; the first works the same.
:500px
Construct perpendiculars $AD$, $CH$ and $BI$ from $A$, $B$ and $C$ to $DEF$.
The triangles $\triangle AEG$, $\triangle CEH$ are similar.
The triangles $\triangle BDI$, $\triangle CDH$ are also similar.
The triangles $\triangle BFI$, $\triangle AFG$ are also similar.
Hence:
:$\dfrac {CE} {EA} = \dfrac {CH} {AG}, \dfrac {BD} {DC} = \dfrac {BI} {CH}, \dfrac {AF} {FB} = \dfrac {AG} {BI}$
Thus:
:$\size {\dfrac {AF} {FB} \cdot \dfrac{BD} {DC} \cdot \dfrac{CE} {EA} } = \size {\dfrac {AG} {BI} \cdot \dfrac {BI} {CH} \cdot \dfrac {CH} {AG} } = 1$
Hence the result.
{{qed|lemma}}