nyuuzyou/wikis huggingface dataset:
Set Intersection is Idempotent/Indexed Family

== Theorem ==
Let $\family {F_i}_{i \mathop \in I}$ be a non-empty indexed family of sets.
Suppose that all the sets in the $\family {F_i}_{i \mathop \in I}$ are the same.
That is, suppose that for some set $S$:
:$\forall i \in I: F_i = S$
Then:
:$\ds \bigcap_{i \mathop \in I} F_i = S$
where $\ds \bigcap_{i \mathop \in I} F_i$ is the intersection of $\family {F_i}_{i \mathop \in I}$.
== Proof ==
First we show that:
:$\ds \bigcap_{i \mathop \in I} F_i \subseteq S$
Let $x \in \ds \bigcap_{i \mathop \in I} F_i$.
Since $I$ is non-empty, it has an element $k$.
By the definition of intersection, $x \in F_k$.
By the premise, $F_k = S$, so $x \in S$.
Since this holds for all $x \in \ds \bigcap_{i \mathop \in I} F_i$:
:$\ds \bigcap_{i \mathop \in I} F_i \subseteq S$
Next we show that:
:$\ds S \subseteq \bigcap_{i \mathop \in I} F_i$
Let $x \in S$.
Then for all $i \in I$, $F_i = S$, so $x \in F_i$.
Thus by the definition of intersection:
:$x \in \ds \bigcap_{i \mathop \in I} F_i$
Since this holds for all $x \in S$:
:$S \subseteq \ds \bigcap_{i \mathop \in I} F_i$
By definition of set equality:
:$\ds \bigcap_{i \mathop \in I} F_i = S$
Category:Set Intersection
Category:Indexed Families
Category:Examples of Idempotence‎
Set Intersection is Self-Distributive

== Theorem ==
Set intersection is self-distributive:
:$\forall A, B, C: \paren {A \cap B} \cap \paren {A \cap C} = A \cap B \cap C = \paren {A \cap C} \cap \paren {B \cap C}$
where $A, B, C$ are sets.
=== Families of Sets ===
=== General Result ===
== Proof ==
We have:
:Intersection is Associative
:Intersection is Commutative
:Set Intersection is Idempotent
The result follows from Associative Commutative Idempotent Operation is Self-Distributive.
Category:Set Intersection
Category:Examples of Self-Distributive Operations
Category:Set Intersection is Self-Distributive
Set Intersection is Self-Distributive/Families of Sets

== Theorem ==
Let $I$ be an indexing set.
Let $\family {A_\alpha}_{\alpha \mathop \in I}$ and $\family {B_\alpha}_{\alpha \mathop \in I}$ be indexed families of subsets of a set $S$.
Then:
:$\ds \map {\bigcap_{\alpha \mathop \in I} } {A_\alpha \cap B_\alpha} = \paren {\bigcap_{\alpha \mathop \in I} A_\alpha} \cap \paren {\bigcap_{\alpha \mathop \in I} B_\alpha}$
where $\ds \bigcap_{\alpha \mathop \in I} A_\alpha$ denotes the intersection of $\family {A_\alpha}$.
== Proof ==
Thus by definition of subset:
:$\ds \map {\bigcap_{\alpha \mathop \in I} } {A_\alpha \cap B_\alpha} \subseteq \paren {\bigcap_{\alpha \mathop \in I} A_\alpha} \cap \paren {\bigcap_{\alpha \mathop \in I} B_\alpha}$
Thus by definition of subset:
:$\ds \paren {\bigcap_{\alpha \mathop \in I} A_\alpha} \cap \paren {\bigcap_{\alpha \mathop \in I} B_\alpha} \subseteq \map {\bigcap_{\alpha \mathop \in I} } {A_\alpha \cap B_\alpha}$
By definition of set equality:
:$\ds \map {\bigcap_{\alpha \mathop \in I} } {A_\alpha \cap B_\alpha} = \paren {\bigcap_{\alpha \mathop \in I} A_\alpha} \cap \paren {\bigcap_{\alpha \mathop \in I} B_\alpha}$
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 4$: Indexed Families of Sets: Exercise $1 \ \text{(d)}$
* : $\S 1$: Naive Set Theory: $\S 1.4$: Sets of Sets: Exercise $1.4.4 \ \text{(iv)}$
Category:Set Intersection is Self-Distributive
Category:Indexed Families
Set Intersection is Self-Distributive/General Result

== Theorem ==
Let $\family {\mathbb S_i} _{i \mathop \in I}$ be an $I$-indexed family of sets of sets.
Then:
:$\ds \bigcap_{i \mathop \in I} \bigcap \mathbb S_i = \bigcap \bigcap_{i \mathop \in I} \mathbb S_i$
== Proof ==
Category:Set Intersection is Self-Distributive
Set Intersection is not Cancellable

== Theorem ==
Set intersection is not a cancellable operation.
That is, for a given $A, B, C \subseteq S$ for some $S$, it is not always the case that:
:$A \cap B = A \cap C \implies B = C$
== Proof ==
Proof by Counterexample:
Let $S = \set {a, b, c}$.
Let:
:$A = \set a$
:$B = \set {a, b}$
:$C = \set {a, c}$
Then:
but:
== Sources ==
* : $\S 2.1$: Sets: Exercise $\text{B} \ 3$
Category:Set Intersection
Set Less than Cardinal Product

== Theorem ==
Let $S$ and $T$ be sets.
Let $T$ be nonempty.
Suppose that $S \times T \sim \card {S \times T}$.
Then:
:$\card S \le \card {S \times T}$
== Proof ==
Let $y \in T$.
Define the mapping $f : S \to S \times T$ as follows:
:$\map f x = \tuple {x, y}$
If $\map f {x_1} = \map f {x_2}$, then $\tuple {x_1, y} = \tuple {x_2, y}$ by the definition of $f$.
It follows that $x_1 = x_2$ by Equality of Ordered Pairs.
Thus, $f: S \to S \times T$ is an injection.
By Injection implies Cardinal Inequality, it follows that $\card S \le \card {S \times T}$
== Sources ==
* : $\S 10.25$
Category:Cardinals
Set Operations on Primitive Recursive Relations

== Theorem ==
Let $\RR_1 \subseteq N^k$ and $\RR_2 \subseteq N^k$ be $k$-ary relations on $N^k$.
Let $\RR_1$ and $\RR_2$ be primitive recursive.
Then the following are all primitive recursive relations:
:$\TT = \neg \RR_1$
:$\UU = \RR_1 \land \RR_2$
:$\VV = \RR_1 \lor \RR_2$
== Proof ==
By hypothesis, the characteristic functions $\chi_{\RR_1}, \chi_{\RR_2}$ of $\RR_1$ and $\RR_2$ are primitive recursive.
Then we have that the characteristic functions of $\TT, \UU, \VV$ are given by:
:$\chi_\TT = \map {\overline \sgn} {\chi_{\RR_1} }$
:$\chi_\UU = \chi_{\RR_1} \times \chi_{\RR_2}$
:$\chi_\VV = \map {\overline \sgn} {\chi_{\RR_1} + \chi_{\RR_2} }$
Compare Complement of Primitive Recursive Set, Intersection of Primitive Recursive Sets and Union of Primitive Recursive Sets.
Hence the result.
Category:Primitive Recursive Functions
Set Partition/Examples/Integers by Parity

== Example of Set Partition ==
Let $\Z$ denote the set of integers.
Let $\Z_E$ denote the set of even integers.
Let $\Z_O$ denote the set of odd integers.
Then $P = \set {\Z_E, \Z_O}$ forms a partition of $\Z$.
== Sources ==
* 
* 
Category:Examples of Set Partitions
Set Partition/Examples/Integers by Sign

== Example of Set Partition ==
Let $\Z$ denote the set of integers.
Let $\Z_{> 0}$ denote the set of strictly positive integers.
Let $\Z_{< 0}$ denote the set of strictly negative integers.
Let $\Z_0$ denote the singleton $\set 0$
Then $P = \set {\Z_{> 0}, \Z_{< 0}, \Z_0}$ forms a partition of $\Z$.
== Sources ==
* : $\S 2.3$. Partitions: Example $33$
Category:Examples of Set Partitions
Set Partition/Examples/Partition into Singletons

== Example of Set Partition ==
Let $S$ be a set.
Consider the family of subsets $\family {\set x}_{x \mathop \in S}$ indexed by $S$ itself.
Then $\family {\set x}_{x \mathop \in S}$ is a partitioning of $S$ into singletons.
Its associated partition is:
:$\set {\set x: x \in S}$
== Sources ==
* : $\S 6$. Indexed families; partitions; equivalence relations: Example $6.3$
Category:Examples of Set Partitions
Set Products on Same Set are Equivalent

== Theorem ==
Let $S$ and $T$ be sets.
Let $\struct {P, \phi_1, \phi_2}$ and $\struct {Q, \psi_1, \psi_2}$ be products of $S$ and $T$.
Then there exists a unique bijection $\chi: Q \to P$ such that:
:$\phi_1 \circ \chi = \psi_1$
:$\phi_2 \circ \chi = \psi_2$
== Proof ==
We have that $\struct {P, \phi_1, \phi_2}$ is a set product.
From the definition of set product $\chi: Q \to P$ is the unique mapping such that:
:$\phi_1 \circ \chi = \psi_1$
:$\phi_2 \circ \chi = \psi_2$
Similarly, we have that $\struct {Q, \psi_1, \psi_2}$ is a set product.
So from the definition of set product there exists a unique mapping $\xi: P \to Q$ such that:
:$\psi_1 \circ \xi = \phi_1$
:$\psi_2 \circ \xi = \phi_2$
It can be seen that $\chi \circ \xi: P \to P$ is the unique mapping such that:
:$\phi_1 \circ \chi \circ \xi = \phi_1$
:$\phi_2 \circ \chi \circ \xi = \phi_2$
and similarly that $\xi \circ \chi: Q \to Q$ is the unique mapping such that:
:$\psi_1 \circ \xi \circ \chi = \psi_1$
:$\psi_2 \circ \xi \circ \chi = \psi_2$
So it appears that:
:$\chi \circ \xi = I_P$
:$\xi \circ \chi = I_Q$
where $I_P$ and $I_Q$ are the identity mappings on $P$ and $Q$ respectively.
From the corollary to Bijection iff Left and Right Inverse it follows that $\chi$ and $\xi$ are bijections such that $\chi = \xi^{-1}$.
== Sources ==
* : $\S 5$. Induced mappings; composition; injections; surjections; bijections: Theorem $5.13$
Category:Set Products
Set System Closed under Intersection is Commutative Semigroup

== Theorem ==
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 that $\struct {\SS, \cap}$ is closed.
=== Associativity ===
The operation $\cap$ is associative from Intersection is Associative.
=== Commutativity ===
The operation $\cap$ is commutative from Intersection is Commutative.
Hence, by definition, the result.
== Also see ==
* Set System Closed under Union is Commutative Semigroup
* Set System Closed under Symmetric Difference is Abelian Group
Category:Set Systems
Category:Set Intersection
Category:Commutative Semigroups
Set System Closed under Symmetric Difference is Abelian Group

== Theorem ==
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 ==
=== ===
By presupposition on $\SS$, $\struct {\SS, \symdif}$ is closed.
=== ===
:$\forall A, B, C \in \SS: \paren {A \symdif B} \symdif C = A \symdif \paren {B \symdif C}$ as Symmetric Difference is Associative.
So $\symdif$ is associative.
=== ===
From Symmetric Difference with Self is Empty Set, we have that:
:$\forall A \in \SS: A \symdif A = \O$
So it is clear that $\O$ is in $\SS$, from the fact that $\struct {\SS, \symdif}$ is closed.
Then we have:
:$\forall A \in \SS: A \symdif \O = A = \O \symdif A$ from Symmetric Difference with Empty Set and Symmetric Difference is Commutative.
Thus $\O$ acts as an identity.
=== ===
From the above, we know that $\O$ is the identity element of $\struct {\SS, \symdif}$.
We also noted that
:$\forall A \in \SS: A \symdif A = \O$
From Symmetric Difference with Self is Empty Set.
Thus each $A \in \SS$ is self-inverse.
=== Commutativity ===
:$\forall A, B \in \SS: A \symdif B = B \symdif A$ as Symmetric Difference is Commutative.
So $\symdif$ is commutative.
We see that $\struct {\SS, \symdif}$ is closed, associative, commutative, has an identity element $\O$, and each element has an inverse (itself), so it satisfies the criteria for being an abelian group.
== Also see ==
* Set System Closed under Union is Commutative Semigroup
* Set System Closed under Intersection is Commutative Semigroup
Category:Abelian Groups
Category:Symmetric Difference
Category:Set Systems
Set System Closed under Union is Commutative Semigroup

== Theorem ==
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 that $\struct {\SS, \cup}$ is closed.
=== Associativity ===
The operation $\cup$ is associative from Union is Associative.
=== Commutativity ===
The operation $\cup$ is commutative from Union is Commutative.
Hence, by definition, the result.
== Also see ==
* Set System Closed under Intersection is Commutative Semigroup
* Set System Closed under Symmetric Difference is Abelian Group
Category:Set Systems
Category:Set Union
Category:Commutative Semigroups
Set Theory/Examples

== Examples in Set Theory ==
=== Unions and Intersections $1$ ===
=== Unions and Intersections $2$ ===
=== Equations $A \cup \paren {X \cap B} = C$, $\paren {A \cup X} \cap B = D$ ===
=== Simplify $\paren {A \cap B} \cup \paren {C \cap A} \cup \relcomp {\Bbb U} {\relcomp {\Bbb U} A \cup \relcomp {\Bbb U} B}$ ===
----
Let $A$, $B$ and $C$ be sets defined by circles embedded in the complex plane as follows:
=== Example of Intersection with Union ===
=== Example of Intersection of Unions ===
=== Example of Union of Intersections ===
=== Example of Union of Intersections with Set Complements ===
Category:Examples in Set Theory
Set Theory/Examples/(A cap B) cup (C cap A) cup Complement (Complement A cup Complement B)

== Example in Set Theory ==
The expression:
:$\paren {A \cap B} \cup \paren {C \cap A} \cup \relcomp {\Bbb U} {\relcomp {\Bbb U} A \cup \relcomp {\Bbb U} B}$
can be simplified to:
:$A \cap \paren {B \cup C}$
== Proof ==
== Sources ==
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $12$
Category:Examples in Set Theory
Set Theory/Examples/A cup (X cap B) = C, (A cup X) cap B = D

== Example in Set Theory ==
Let $A, B, C, D$ be subsets of a set $S$.
Let there exist $X \subseteq S$ such that:
:$A \cup \paren {X \cap B} = C$
:$\paren {A \cup X} \cap B = D$
Then:
:$A \cap B \subseteq D \subseteq B$
and:
:$A \cup D = C$
=== Converse ===
== Proof ==
Then:
== Sources ==
* : Chapter $1$: Sets and Logic: Exercise $12$
Category:Examples in Set Theory
Set Theory/Examples/A cup (X cap B) = C, (A cup X) cap B = D/Converse

== Example in Set Theory ==
Let $A, B, C, D$ be subsets of a set $S$.
Let the following conditions hold:
:$A \cap B \subseteq D \subseteq B$
and:
:$A \cup D = C$
Then these equations hold:
:$A \cup \paren {X \cap B} = C$
:$\paren {A \cup X} \cap B = D$
if:
: $X = D \setminus A$
== Proof ==
Suppose $X = D \setminus A$.
Then:
== Sources ==
* : Chapter $1$: Sets and Logic: Exercise $12$
Category:Examples in Set Theory
Set Theory/Examples/Intersection of Unions/3 Circles in Complex Plane

== Example in Set Theory ==
Let $A$, $B$ and $C$ be sets defined by circles embedded in the complex plane as follows:
$\paren {A \cup B} \cap \paren {B \cup C}$ can be illustrated graphically as:
:400px
where the intersection of the unions is depicted in yellow.
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: Point Sets: $123 \ \text{(d)}$
Category:Examples in Set Theory
Set Theory/Examples/Intersection with Union/3 Circles in Complex Plane

== Example in Set Theory ==
Let $A$, $B$ and $C$ be sets defined by circles embedded in the complex plane as follows:
$C \cap \paren {A \cup B}$ can be illustrated graphically as:
:
where the intersection with the union is depicted in yellow.
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: Point Sets: $123 \ \text{(d)}$
Category:Examples in Set Theory
Set Theory/Examples/Union of Intersections/3 Circles in Complex Plane

== Example in Set Theory ==
Let $A$, $B$ and $C$ be sets defined by circles embedded in the complex plane as follows:
$\paren {A \cap B} \cup \paren {B \cap C} \cup \paren {C \cap A}$ can be illustrated graphically as:
:400px
where the union of the intersections is depicted in yellow.
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: Point Sets: $123 \ \text{(e)}$
Category:Examples in Set Theory
Set Theory/Examples/Union of Intersections with Set Complements/3 Circles in Complex Plane

== Example in Set Theory ==
Let $A$, $B$ and $C$ be sets defined by circles embedded in the complex plane as follows:
$\paren {A \cap \tilde B} \cup \paren {B \cap \tilde C} \cup \paren {C \cap \tilde A}$, where $\tilde A$ denotes the complement of $A$, can be illustrated graphically as:
:400px
where the union of the intersections is depicted in yellow.
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: Point Sets: $123 \ \text{(f)}$
Category:Examples in Set Theory
Set Theory/Examples/Unions and Intersections 1

== Example in Set Theory ==
Let:
Then:
Thus:
:$V_1$ and $V_2$ are disjoint
:$V_2$ and $V_3$ are disjoint.
== Sources ==
* : Appendix $\text{A}.1$: Sets and Subsets: Problem Set $\text{A}.1$: $4$
Category:Examples in Set Theory
Category:Examples of Set Union
Category:Examples of Set Intersection
Category:Examples of Disjoint Sets
Set Union/Examples

== Examples of Set Union ==
=== Example: $2$ Arbitrarily Chosen Sets ===
=== Example: $2$ Arbitrarily Chosen Sets of Complex Numbers ===
=== Example: $3$ Arbitrarily Chosen Sets ===
=== Example: $3$ Arbitrarily Chosen Sets of Complex Numbers ===
=== Example: People who are Blue-Eyed or British ===
=== Example: Overlapping Integer Sets ===
=== Example: Subset of Union ===
=== Example: $2$ Circles in Complex Plane ===
=== Example: $3$ Circles in Complex Plane ===
=== Arbitrary Example $1$ ===
=== Arbitrary Example $2$ ===
Category:Examples of Set Union
Set Union/Examples/2 Arbitrarily Chosen Sets of Complex Numbers

== Example of Set Union ==
Let:
Then:
:$A \cup B = \set {3, -i, 0, -1, 4, 2 + i, 5}$
== Sources ==
* : $1$: Complex Numbers: Solved Problems: Point Sets: $46 \ \text {(a)}$
Category:Examples of Set Union
Set Union/Examples/2 Circles in Complex Plane

== Example of Set Union ==
Let $A$ and $B$ be sets defined by circles embedded in the complex plane as follows:
Then $A \cup B$ can be illustrated graphically as:
:
where the union is depicted in yellow.
== Sources ==
* : $1$: Complex Numbers: Solved Problems: Miscellaneous Problems: $49 \ \text{(b)}$
Category:Examples of Set Union
Set Union/Examples/3 Arbitrarily Chosen Sets

== Example of Set Union ==
Let:
Then:
:$A_1 \cup A_2 \cup A_3 = \set {1, 2, 3, 4, 5, 6, 8, 12}$
== Sources ==
* : $\S 7$: Unions and Intersections
Category:Examples of Set Union
Set Union/Examples/3 Arbitrarily Chosen Sets of Complex Numbers

== Example of Set Union ==
Let:
Then:
:$\paren {A \cup B} \cup C = \set {2, 1, -i,1, 1 + i}$
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: Point Sets: $121 \ \text{(a)}$
Category:Examples of Set Union
Set Union/Examples/3 Circles in Complex Plane

== Example of Set Union ==
Let $A$, $B$ and $C$ be sets defined by circles embedded in the complex plane as follows:
Then $A \cup B \cup C$ can be illustrated graphically as:
:
where the union is depicted in yellow.
== Sources ==
* : $1$: Complex Numbers: Supplementary Problems: Point Sets: $123 \ \text{(b)}$
Category:Examples of Set Union
Set Union/Examples/Finite Subfamily of Unbounded Above Open Real Intervals

== Example of Union of Set of Sets ==
Let $\R$ denote the set of real numbers.
For a given $a \in \R$, let $S_a$ denote the (real) interval:
:$S_a = \openint a \to = \set {x \in \R: x > a}$
Let $\SS$ denote the family of sets indexed by $\R$:
:$\SS := \family {S_a}_{a \mathop \in \R}$
Let $\TT$ be a finite subfamily of $\SS$.
Then:
:$\bigcup \TT$ is a proper subset of $\R$.
== Proof ==
According to the definition of subfamily, let $\TT$ be the family of sets indexed by $U$, where $U \subseteq \R$ is a finite subset of $\R$.
By construction it is seen that $\TT \subseteq \R$
By definition, $\R$ is totally ordered by $>$.
By Subset of Toset is Toset, $U$ is also totally ordered by $>$.
From Finite Totally Ordered Set is Well-Ordered, $U$ has a smallest element $m$, say.
Thus:
:$\TT = \set {x \in \R: x > m}$
Let $n \in \R: n < m$.
Then it is seen that $n \notin \TT$ and the result follows.
== Sources ==
* : Chapter $\text{I}$: Sets and Functions: Unions and Intersections
Category:Examples of Set Union
Set Union/Examples/Set of Arbitrary Sets

== Example of Union of Set of Sets ==
Let:
Let $\mathscr S = \set {A, B, C}$.
Then:
:$\bigcup \mathscr S = \set {1, 2, 3, 4, a}$
== Sources ==
* : $\S 1.8$. Sets of sets: Example $26$
Category:Examples of Set Union
Set Union/Examples/Set of Initial Segments

== Example of Union of Set of Sets ==
Let $\Z$ denote the set of integers.
Let $\map \Z n$ denote the initial segment of $\Z_{>0}$:
:$\map \Z n = \set {1, 2, \ldots, n}$
Let $\mathscr S := \set {\map \Z n: n \in \Z_{>0} }$
That is, $\mathscr S$ is the set of all initial segments of $\Z_{>0}$.
Then:
:$\bigcup \mathscr S = \Z_{>0}$
that is, the set of strictly positive integers.
== Sources ==
* : $\S 1.8$. Sets of sets: Example $28$
Category:Examples of Set Union
Set Union/Examples/Set of Unbounded Above Open Real Intervals

== Example of Union of Set of Sets ==
Let $\R$ denote the set of real numbers.
For a given $a \in \R$, let $S_a$ denote the (real) interval:
:$S_a = \openint a \to = \set {x \in \R: x > a}$
Let $\SS$ denote the family of sets indexed by $\R$:
:$\SS := \family {S_a}_{a \mathop \in \R}$
Then:
:$\bigcup \SS = \R$.
== Proof ==
By construction we have that $\SS \subseteq \R$.
It remains to prove that $\R \subseteq \SS$
 $x \in \R$ such that $x \notin \SS$.
Then by definition of set union:
:$\not \exists a \in \R: x \in S_a$
That is:
:$\forall a \in \R: x \le a$
But then we have:
:$x - 1 \in \R$
leading to:
:$x < x - 1$
which contradicts the properties of real numbers, which leads to:
:$x > x - 1$
Hence the result.
== Sources ==
* : Chapter $\text{I}$: Sets and Functions: Unions and Intersections
Category:Examples of Set Union
Set Union/Examples/Subset of Union

== Example of Set Union ==
Let $U, V, W$ be non-empty sets.
Let $W$ be such that for all $w \in W$, either:
:$w \in U$
or:
:$w \in V$
Then:
:$W \subseteq U \cup V$
== Proof ==
== Sources ==
* : Appendix $\text{A}.1$: Sets and Subsets: Problem Set $\text{A}.1$: $2$
Category:Examples of Set Union
Set Union Preserves Subsets

== Theorem ==
Let $A, B, S, T$ be sets.
Then:
:$A \subseteq B, \ S \subseteq T \implies A \cup S \subseteq B \cup T$
=== Corollary ===
=== Families of Sets ===
=== General Result ===
== Proof 1 ==
== Proof 2 ==
== Also see ==
* Union is Increasing
Category:Set Union
Category:Subsets
Category:Compatible Relations
Category:Set Union Preserves Subsets
Set Union Preserves Subsets/Corollary

== Corollary to Set Union Preserves Subsets ==
Let $A, B, S$ be sets.
Then:
:$A \subseteq B \implies A \cup S \subseteq B \cup S$
:$A \subseteq B \implies S \cup A \subseteq S \cup B$
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 1.6$: Set Identities and Other Set Relations: Exercise $1 \ \text{(d)}$
Category:Set Union Preserves Subsets
Set Union Preserves Subsets/Corollary/Proof 1

== Corollary to Set Union Preserves Subsets ==
== Proof ==
Let $A \subseteq B$, and let $S$ be any set.
From Set Union Preserves Subsets, substituting $S$ for $T$:
:$A \subseteq B, \ S \subseteq S \implies A \cup S \subseteq B \cup S$
From Set is Subset of Itself, $S \subseteq S$ for all sets $S$.
Hence the first result:
:$A \subseteq B \implies A \cup S \subseteq B \cup S$
The second result follows from Union is Commutative.
== Sources ==
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: $\text{(e)}$
Category:Set Union Preserves Subsets
Category:Compatible Relations
Set Union Preserves Subsets/Corollary/Proof 2

== Corollary to Set Union Preserves Subsets ==
== Proof ==
Let $A$, $B$, and $S$ be sets.
Let $A \subseteq B$.
Let $x \in A \cup S$.
By the definition of union:
:$x \in A$ or $x \in S$
Suppose $x \in A$.
Then by the definition of subset:
:$x \in B$
Thus by the definition of union:
:$x \in B \cup S$
Suppose instead that $x \in S$.
Then by the definition of union:
:$x \in B \cup S$
Thus for all $x \in A \cup S$:
:$x \in B \cup S$
The second result follows from Union is Commutative.
Category:Set Union Preserves Subsets
Set Union Preserves Subsets/Families of Sets

== Theorem ==
Let $I$ be an indexing set.
Let $\family {A_\alpha}_{\alpha \mathop \in I}$ and $\family {B_\alpha}_{\alpha \mathop \in I}$ be indexed families of subsets of a set $S$.
Let:
:$\forall \beta \in I: A_\beta \subseteq B_\beta$
Then:
:$\ds \bigcup_{\alpha \mathop \in I} A_\alpha \subseteq \bigcup_{\alpha \mathop \in I} B_\alpha$
== Proof ==
By definition of subset:
:$\ds \bigcup_{\alpha \mathop \in I} A_\alpha \subseteq \bigcup_{\alpha \mathop \in I} B_\alpha$
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 4$: Indexed Families of Sets: Exercise $1 \ \text{(e)}$
Category:Set Union Preserves Subsets
Category:Indexed Families
Set Union Preserves Subsets/General Result

== Theorem ==
Let $\mathbb S, \mathbb T$ be sets of sets.
Suppose that for each $S \in \mathbb S$ there exists a $T \in \mathbb T$ such that $S \subseteq T$.
Then $\bigcup \mathbb S \subseteq \bigcup \mathbb T$.
== Proof ==
Let $x \in \bigcup \mathbb S$.
By the definition of union, there exists an $S \in \mathbb S$ such that $x \in S$.
By the premise, there exists a $T \in \mathbb T$ such that $S \subseteq T$.
By the definition of Subset:
:$x \in T$
Thus by the definition of union:
:$x \in \bigcup \mathbb T$
Category:Set Union Preserves Subsets