User:Ascii/ProofWiki Sampling Notes for Theorems
Jump to navigation
Jump to search
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
- Set is Subset of Itself
- $\forall S: S \subseteq S$
- Singleton of Element is Subset
- $x \in S \iff \{x\} \subseteq S$
- Subset Relation is Transitive
- $\paren {R \subseteq S} \land \paren {S \subseteq T} \implies R \subseteq T$
- 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$
- Set Equals Itself
- $S = S$
- Set Inequality
- $S \ne T \iff \left({S \nsubseteq T}\right) \lor \left({T \nsubseteq S}\right)$
- Empty Set is Subset of All Sets
- $\forall S: \O \subseteq S$
- Empty Set is Unique
- The empty set $\O$ is unique.
- Empty Set is Element of Power Set
- $\forall S: \O \in \mathcal P (S)$
- Set is Element of its Power Set
- $S \in \powerset S$
- Power Set of Empty Set
- $P \left({\varnothing}\right) = \left\{{\varnothing}\right\}$
Union
- Set Union is Idempotent
- $S \cup S = S$
- Union is Commutative
- $S \cup T = T \cup S$
- Union is Associative
- $(S \cup T) \cup R = S \cup (T \cup R)$
- Union with Empty Set
- $S \cup \O = S$
- Set is Subset of Union
- $S \subseteq S \cup T$
- Set Union Preserves Subsets
- $A \subseteq B, \ S \subseteq T \implies A \cup S \subseteq B \cup T$
- Union is Smallest Superset
- $\paren {S_1 \subseteq T} \land \paren {S_2 \subseteq T} \iff \paren {S_1 \cup S_2} \subseteq T$
- 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$
- Union with Superset is Superset
- $S \subseteq T \iff S \cup T = T$
- 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
- Set Intersection is Idempotent
- $S \cap S = S$
- Intersection is Commutative
- $S \cap T = T \cap S$
- Intersection is Associative
- $A \cap \paren {B \cap C} = \paren {A \cap B} \cap C$
- Intersection is Subset
- $S \cap T \subseteq S$
- Intersection with Empty Set
- $S \cap \O = \O$
- 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$
- Intersection with Subset is Subset‎
- $S \subseteq T \iff S \cap T = S$
- 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
- Intersection is Subset of Union
- $S \cap T \subseteq S \cup T$
- Intersection Distributes over Union
- $R \cap \paren {S \cup T} = \paren {R \cap S} \cup \paren {R \cap T}$
- Union Distributes over Intersection
- $R \cup \paren {S \cap T} = \paren {R \cup S} \cap \paren {R \cup T}$
- Absorption Laws (Set Theory)/Intersection with Union
- $S \cap \paren {S \cup T} = S$
- Absorption Laws (Set Theory)/Union with Intersection
- $S \cup \paren {S \cap T} = S$
- 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
- Set Difference is Subset
- $S \setminus T \subseteq S$
- Set Difference with Empty Set is Self
- $S \setminus \O = S$
- Set Difference with Superset is Empty Set
- $S \subseteq T \iff S \setminus T = \O$
- Set Difference with Self is Empty Set
- $S \setminus S = \O$
- Set Difference Equals First Set iff Empty Intersection
- $S \setminus T = S \iff S \cap T = \O$
- Equal Set Differences iff Equal Intersections
- $R \setminus S = R \setminus T \iff R \cap S = R \cap T$
- Set Difference Union Second Set is Union
- $\left({S \setminus T}\right) \cup T = S \cup T$
- Set Difference Union First Set is First Set
- $\paren {S \setminus T} \cup S = S$
- Set Difference with Union is Set Difference
- $\left({S \cup T}\right) \setminus T = S \setminus T$
- Intersection with Set Difference is Set Difference with Intersection
- $\left({R \setminus S}\right) \cap T = \left({R \cap T}\right) \setminus S$
- Set Difference Intersection with Second Set is Empty Set
- $\left({S \setminus T}\right) \cap T = \varnothing$
- 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}$
- 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}$
- 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$
- 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)$
- Set Difference Union Intersection
- $S = \left({S \setminus T}\right) \cup \left({S \cap T}\right)$
- 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$
- Set Difference is Anticommutative
- $S = T \iff S \setminus T = T \setminus S = \varnothing$
Relative Complement
- Relative Complement of Empty Set
- $\complement_S \left({\varnothing}\right) = S$
- Relative Complement with Self is Empty Set
- $\complement_S \left({S}\right) = \varnothing$
- Relative Complement of Relative Complement
- $\relcomp S {\relcomp S T} = T$
- Intersection with Relative Complement is Empty
- $T \cap \complement_S \left({T}\right) = \varnothing$
- Union with Relative Complement
- $\complement_S \left({T}\right) \cup T = S$
- 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$.
- Set Difference as Intersection with Relative Complement
- Let $A, B \subseteq S$.
- $A \setminus B = A \cap \relcomp S B$
Symmetric Difference
- 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\}$
- Symmetric Difference is Commutative
- $S * T = T * S$
- Symmetric Difference with Self is Empty Set
- $S * S = \O$
- Symmetric Difference of Equal Sets
- $S = T \iff S * T = \O$
- Symmetric Difference with Empty Set
- $S * \O = S$
- 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}$
- Symmetric Difference of Unions
- $\left({R \cup T}\right) * \left({S \cup T}\right) = \left({R * S}\right) \setminus T$
- Symmetric Difference is Associative
- $R * \paren {S * T} = \paren {R * S} * T$
Universe
- Intersection with Universe
- $\mathbb U \cap S = S$
- Union with Universe
- $\mathbb U \cup S = \mathbb U$
- Complement of Empty Set is Universe
- $\complement \paren \O = \mathbb U$
- Complement of Universe is Empty Set
- $\complement \paren {\mathbb U} = \O$
- Complement of Complement
- $\map \complement {\map \complement S} = S$
- Intersection with Complement
- $S \cap \complement \left({S}\right) = \varnothing$
- Union with Complement
- $S \cup \complement \left({S}\right) = \mathbb U$
- 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$.
- Set Difference as Intersection with Complement
- $A \setminus B = A \cap \complement \left({B}\right)$
- Intersection with Complement is Empty iff Subset
- $S \subseteq T \iff S \cap \complement \paren T = \O$
- Set Complement inverts Subsets
- $S \subseteq T \iff \complement \left({T}\right) \subseteq \complement \left({S}\right)$
- Set Difference of Complements
- $\complement \left({S}\right) \setminus \complement \left({T}\right) = T \setminus S$
- Empty Intersection iff Subset of Complement
- $S \cap T = \varnothing \iff S \subseteq \complement \paren T$
- Symmetric Difference of Complements
- $\map \complement S * \map \complement T = S * T$
- Symmetric Difference with Universe
- $\mathbb U * S = \complement \paren S$
- De Morgan's Laws (Set Theory)/Set Complement/Complement of Union
- $\overline {T_1 \cup T_2} = \overline T_1 \cap \overline T_2$
- De Morgan's Laws (Set Theory)/Set Complement/Complement of Intersection
- $\overline {T_1 \cap T_2} = \overline T_1 \cup \overline T_2$
- Symmetric Difference with Complement
- $S * \relcomp {} S = \mathbb U$
Cartesian Product
- Equality of Ordered Pairs
- $\tuple {a, b} = \tuple {c, d} \iff a = c \land b = d$
- Cartesian Product is Empty iff Factor is Empty
- $S \times T = \O \iff S = \O \lor T = \O$
- Cartesian Product is Anticommutative
- Let $S, T \ne \O$.
- Then $S \times T = T \times S \implies S = T$
- 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$.
- 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}$
- 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}$
- 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}$
- 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)$
- 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}$