User:Ascii/ProofWiki Sampling Notes for Theorems

I hope to not clog up $\mathsf{Pr} \infty \mathsf{fWiki}$ with Userpage notes. My dream for the site is that it has a solid core and these notes can help me contribute.

Sets and Elements

1. Set is Subset of Itself

   $\forall S: S \subseteq S$

2. Singleton of Element is Subset

   $x \in S \iff \{x\} \subseteq S$

3. Subset Relation is Transitive

   $\paren {R \subseteq S} \land \paren {S \subseteq T} \implies R \subseteq T$

4. Equivalence of Definitions of Set Equality

   $S = T \iff \paren {\forall x: x \in S \iff x \in T}$

   $S = T \iff S \subseteq T \land T \subseteq S$

5. Set Equals Itself

   $S = S$

6. Set Inequality

   $S \ne T \iff \left({S \nsubseteq T}\right) \lor \left({T \nsubseteq S}\right)$

7. Empty Set is Subset of All Sets

   $\forall S: \O \subseteq S$

8. Empty Set is Unique

   The empty set $\O$ is unique.

9. Empty Set is Element of Power Set

   $\forall S: \O \in \mathcal P (S)$

10. Set is Element of its Power Set

    $S \in \powerset S$

11. Power Set of Empty Set

    $P \left({\varnothing}\right) = \left\{{\varnothing}\right\}$

Union

1. Set Union is Idempotent

   $S \cup S = S$

2. Union is Commutative

   $S \cup T = T \cup S$

3. Union is Associative

   $(S \cup T) \cup R = S \cup (T \cup R)$

4. Union with Empty Set

   $S \cup \O = S$

5. Set is Subset of Union

   $S \subseteq S \cup T$

6. Set Union Preserves Subsets

   $A \subseteq B, \ S \subseteq T \implies A \cup S \subseteq B \cup T$

7. Union is Smallest Superset

   $\paren {S_1 \subseteq T} \land \paren {S_2 \subseteq T} \iff \paren {S_1 \cup S_2} \subseteq T$

8. Union of Subsets is Subset

   $\left({S_1 \subseteq T}\right) \land \left({S_2 \subseteq T}\right) \implies \left({S_1 \cup S_2}\right) \subseteq T$

9. Union with Superset is Superset

   $S \subseteq T \iff S \cup T = T$

10. Set Union is Self-Distributive

    $\forall A, B, C: \left({A \cup B}\right) \cup \left({A \cup C}\right) = A \cup B \cup C = \left({A \cup C}\right) \cup \left({B \cup C}\right)$

Intersection

1. Set Intersection is Idempotent

   $S \cap S = S$

2. Intersection is Commutative

   $S \cap T = T \cap S$

3. Intersection is Associative

   $A \cap \paren {B \cap C} = \paren {A \cap B} \cap C$

4. Intersection is Subset

   $S \cap T \subseteq S$

5. Intersection with Empty Set

   $S \cap \O = \O$

6. Intersection of Subsets is Subset/Set of Sets

   Let $T$ be a set and $\mathbb S$ be a non-empty set of sets.

   Suppose that for each $S \in \mathbb S$: $S \subseteq T$

   Then $\bigcap \mathbb S \subseteq T$

7. Intersection with Subset is Subset‎

   $S \subseteq T \iff S \cap T = S$

8. Set Intersection is Self-Distributive

   $\forall A, B, C: \left({A \cap B}\right) \cap \left({A \cap C}\right) = A \cap B \cap C = \left({A \cap C}\right) \cap \left({B \cap C}\right)$

Union and Intersection

1. Intersection is Subset of Union

   $S \cap T \subseteq S \cup T$

2. Intersection Distributes over Union

   $R \cap \paren {S \cup T} = \paren {R \cap S} \cup \paren {R \cap T}$

3. Union Distributes over Intersection

   $R \cup \paren {S \cap T} = \paren {R \cup S} \cap \paren {R \cup T}$

4. Absorption Laws (Set Theory)/Intersection with Union

   $S \cap \paren {S \cup T} = S$

5. Absorption Laws (Set Theory)/Union with Intersection

   $S \cup \paren {S \cap T} = S$

6. Union equals Intersection iff Sets are Equal

   $\left({S \cup T = S}\right) \land \left({S \cap T = S}\right) \iff S = T$

Set Difference

1. Set Difference is Subset

   $S \setminus T \subseteq S$

2. Set Difference with Empty Set is Self

   $S \setminus \O = S$

3. Set Difference with Superset is Empty Set

   $S \subseteq T \iff S \setminus T = \O$

4. Set Difference with Self is Empty Set

   $S \setminus S = \O$

5. Set Difference Equals First Set iff Empty Intersection

   $S \setminus T = S \iff S \cap T = \O$

6. Equal Set Differences iff Equal Intersections

   $R \setminus S = R \setminus T \iff R \cap S = R \cap T$

7. Set Difference Union Second Set is Union

   $\left({S \setminus T}\right) \cup T = S \cup T$

8. Set Difference Union First Set is First Set

   $\paren {S \setminus T} \cup S = S$

9. Set Difference with Union is Set Difference

   $\left({S \cup T}\right) \setminus T = S \setminus T$

10. Intersection with Set Difference is Set Difference with Intersection

    $\left({R \setminus S}\right) \cap T = \left({R \cap T}\right) \setminus S$

11. Set Difference Intersection with Second Set is Empty Set

    $\left({S \setminus T}\right) \cap T = \varnothing$

12. De Morgan's Laws (Set Theory)/Set Difference/Difference with Intersection

    $S \setminus \paren {T_1 \cap T_2} = \paren {S \setminus T_1} \cup \paren {S \setminus T_2}$

13. De Morgan's Laws (Set Theory)/Set Difference/Difference with Union

    $S \setminus \paren {T_1 \cup T_2} = \paren {S \setminus T_1} \cap \paren {S \setminus T_2}$

14. Set Difference with Union

    $R \setminus \left({S \cup T}\right) = \left({R \cup T}\right) \setminus \left({S \cup T}\right) = \left({R \setminus S}\right) \setminus T = \left({R \setminus T}\right) \setminus S$

15. Set Difference with Set Difference is Union of Set Difference with Intersection

    $R \setminus \left({S \setminus T}\right) = \left({R \setminus S}\right) \cup \left({R \cap T}\right)$

16. Set Difference Union Intersection

    $S = \left({S \setminus T}\right) \cup \left({S \cap T}\right)$

17. Set Difference of Intersection with Set is Empty Set

    $\left({S \cap T}\right) \setminus S = \varnothing$

    $\left({S \cap T}\right) \setminus T = \varnothing$

18. Set Difference is Anticommutative

    $S = T \iff S \setminus T = T \setminus S = \varnothing$

Relative Complement

1. Relative Complement of Empty Set

   $\complement_S \left({\varnothing}\right) = S$

2. Relative Complement with Self is Empty Set

   $\complement_S \left({S}\right) = \varnothing$

3. Relative Complement of Relative Complement

   $\relcomp S {\relcomp S T} = T$

4. Intersection with Relative Complement is Empty

   $T \cap \complement_S \left({T}\right) = \varnothing$

5. Union with Relative Complement

   $\complement_S \left({T}\right) \cup T = S$

6. Set with Relative Complement forms Partition

   Let $\varnothing \subsetneqq T \subsetneqq S$.

   Then $\left\{{T, \complement_S \left({T}\right)}\right\}$ is a partition of $S$.

7. Set Difference as Intersection with Relative Complement

   Let $A, B \subseteq S$.

   $A \setminus B = A \cap \relcomp S B$

Symmetric Difference

1. Equivalence of Definitions of Symmetric Difference

   $S * T := \paren {S \setminus T} \cup \paren {T \setminus S}$

   $S * T = \paren {S \cup T} \setminus \paren {S \cap T}$

   $S * T = \left({S \cap \overline T}\right) \cup \left({\overline S \cap T}\right)$

   $S * T = \left({S \cup T}\right) \cap \left({\overline S \cup \overline T}\right)$

   $S * T := \left\{{x: x \in S \oplus x \in T}\right\}$

2. Symmetric Difference is Commutative

   $S * T = T * S$

3. Symmetric Difference with Self is Empty Set

   $S * S = \O$

4. Symmetric Difference of Equal Sets

   $S = T \iff S * T = \O$

5. Symmetric Difference with Empty Set

   $S * \O = S$

6. Intersection Distributes over Symmetric Difference

   $\paren {R * S} \cap T = \paren {R \cap T} * \paren {S \cap T}$

   $T \cap \paren {R * S} = \paren {T \cap R} * \paren {T \cap S}$

7. Symmetric Difference of Unions

   $\left({R \cup T}\right) * \left({S \cup T}\right) = \left({R * S}\right) \setminus T$

8. Symmetric Difference is Associative

   $R * \paren {S * T} = \paren {R * S} * T$

Universe

1. Intersection with Universe

   $\mathbb U \cap S = S$

2. Union with Universe

   $\mathbb U \cup S = \mathbb U$

3. Complement of Empty Set is Universe

   $\complement \paren \O = \mathbb U$

4. Complement of Universe is Empty Set

   $\complement \paren {\mathbb U} = \O$

5. Complement of Complement

   $\map \complement {\map \complement S} = S$

6. Intersection with Complement

   $S \cap \complement \left({S}\right) = \varnothing$

7. Union with Complement

   $S \cup \complement \left({S}\right) = \mathbb U$

8. Set with Complement forms Partition

   Let $\varnothing \subset S \subset \mathbb U$.

   Then $S$ and its complement $\complement \left({S}\right)$ form a partition of the universal set $\mathbb U$.

9. Set Difference as Intersection with Complement

   $A \setminus B = A \cap \complement \left({B}\right)$

10. Intersection with Complement is Empty iff Subset

    $S \subseteq T \iff S \cap \complement \paren T = \O$

11. Set Complement inverts Subsets

    $S \subseteq T \iff \complement \left({T}\right) \subseteq \complement \left({S}\right)$

12. Set Difference of Complements

    $\complement \left({S}\right) \setminus \complement \left({T}\right) = T \setminus S$

13. Empty Intersection iff Subset of Complement

    $S \cap T = \varnothing \iff S \subseteq \complement \paren T$

14. Symmetric Difference of Complements

    $\map \complement S * \map \complement T = S * T$

15. Symmetric Difference with Universe

    $\mathbb U * S = \complement \paren S$

16. De Morgan's Laws (Set Theory)/Set Complement/Complement of Union

    $\overline {T_1 \cup T_2} = \overline T_1 \cap \overline T_2$

17. De Morgan's Laws (Set Theory)/Set Complement/Complement of Intersection

    $\overline {T_1 \cap T_2} = \overline T_1 \cup \overline T_2$

18. Symmetric Difference with Complement

    $S * \relcomp {} S = \mathbb U$

Cartesian Product

1. Equality of Ordered Pairs

   $\tuple {a, b} = \tuple {c, d} \iff a = c \land b = d$

2. Cartesian Product is Empty iff Factor is Empty

   $S \times T = \O \iff S = \O \lor T = \O$

3. Cartesian Product is Anticommutative

   Let $S, T \ne \O$.

   Then $S \times T = T \times S \implies S = T$

4. Cartesian Product of Subsets

   Let $A, B, S, T$ be sets such that $A \subseteq B$ and $S \subseteq T$.

   Then $A \times S \subseteq B \times T$.

   Also $A \times S \subseteq B \times T \iff A \subseteq B \land S \subseteq T$.

5. Cartesian Product of Intersections

   $\paren {S_1 \cap S_2} \times \paren {T_1 \cap T_2} = \paren {S_1 \times T_1} \cap \paren {S_2 \times T_2}$

6. Cartesian Product of Unions

   $\paren {S_1 \cup S_2} \times \paren {T_1 \cup T_2} = \paren {S_1 \times T_1} \cup \paren {S_2 \times T_2} \cup \paren {S_1 \times T_2} \cup \paren {S_2 \times T_1}$

7. Cartesian Product Distributes over Union

   $A \times \paren {B \cup C} = \paren {A \times B} \cup \paren {A \times C}$

   $\paren {B \cup C} \times A = \paren {B \times A} \cup \paren {C \times A}$

8. Cartesian Product Distributes over Set Difference

   $S \times \left({T_1 \setminus T_2}\right) = \left({S \times T_1}\right) \setminus \left({S \times T_2}\right)$

   $\left({T_1 \setminus T_2}\right) \times S = \left({T_1 \times S}\right) \setminus \left({T_2 \times S}\right)$

9. Set Difference of Cartesian Products

   $\paren {S_1 \times S_2} \setminus \paren {T_1 \times T_2} = \paren {S_1 \times \paren {S_2 \setminus T_2} } \cup \paren {\paren {S_1 \setminus T_1} \times S_2}$