Set algebra
As these are fairly commonly used in all manners of proofs, here's a wide variety of properties of various set operations, including in relation to topological spaces.
1. Basic set operations
For brevity here, we will use a lot of the set builder notation. Although this is not necessary, it is usually more readable and quicker to work with. As a reminder, the set builder notation corresponds to
\begin{eqnarray} A = \{ a | \phi \} &\leftrightarrow& \forall a, (a \in A \leftrightarrow \phi)\\ b \in \{ a | \phi \} &\leftrightarrow& \exists b, (b = a \wedge \phi) \end{eqnarray}The second one meaning that this is equivalent to $\phi$ with $b$ substituted for $a$. In particular we have the relations
\begin{eqnarray} A &=& \{ a | a \in A \}\\ \varnothing &=& \{ a | \bot \} \end{eqnarray}We could also get $V = \{ a | \top \}$, the universal set, but as it is not included in ZFC, for consistency reasons, it's best to avoid using it. In fact, if we have some binary set operation $\intercal$
\begin{eqnarray} A \intercal B = \{ a | a \in A \star a \in B \} \end{eqnarray}for some logical operation $\star$, we may want to avoid $a \in A \star a \in B$ to be true for all $a$. As the universal set is not in ZFC, this mostly means that we should watch out for the empty set, as $a \in \varnothing$ is false for every $a$. We can therefore concentrate on the 8 logical operations which are not true for two falsehoods, at least if we want them to apply to every possible set. These are the contradiction ($p F q \leftrightarrow \bot$), the converse non-implication ($p \nleftarrow q$), the non-implication ($p \nrightarrow q$), the exclusive disjunction ($p \oplus q$), the conjunction ($p \wedge q$), disjunction ($p \vee q$) and projections (mapping $p$ and $q$ to $p$ and $q$ respectively).
The contradiction only maps everything to the empty set and is therefore not terribly interesting, and the projections will map $A$ and $B$ to $A$ and $B$, as can be guessed. This leaves us with 5 operations which will work for every pair of sets.
A common occurence in the proofs below is the appearance of nested set builders. These are equivalent to
\begin{eqnarray} &\vdash& (A \intercal_1 B) \intercal_2 C = \{ b | b \in C \star_2 b \in \{ a | a \in A \star_1 a \in B \} \}\\ &\vdash&\forall b, (b \in (A \intercal_1 B) \intercal_2 C \leftrightarrow b \in C \star_2 (b \in A \star_1 b \in B)) \\ &\vdash& (A \intercal_1 B) \intercal_2 C = \{ b | b \in C \star_2 (b \in A \star_1 b \in B) \} \end{eqnarray}If we have additional constraints on our sets $A$ and $B$, we can freely add them to the set builder by the following process. A constraint on $A$ and $B$ is simply a proposition $\phi(A,B)$ that is always true, so that $\phi(A,B) \leftrightarrow \top$. We also have that for any proposition $p$, $p \leftrightarrow p \wedge \top$. By appropriately chaining together our equivalences, this means that if $\phi(A,B)$ is a tautology,
\begin{eqnarray} A \intercal B = \{ a | (a \in A \star a \in B) \wedge \phi(A, B) \} \end{eqnarray}This will be quite useful for specific cases of our operation.
1.1. Union and intersection
The two most basic set operations are the union and intersection of two sets, defined by
\begin{eqnarray} A \cup B &=& \{ a | a \in A \vee a \in B \}\\ A \cap B &=& \{ a | a \in A \wedge a \in B \} \end{eqnarray}As the logical conjunction and disjunction are symmetric, we have
\begin{eqnarray} A \cup B &=& B \cup A\\ A \cap B &=& B \cap A \end{eqnarray}No element belongs to the empty set, meaning that $a \in \varnothing$ is always false : $a \in \varnothing \leftrightarrow \bot$. Therefore,
\begin{eqnarray} A \cup \varnothing &=& \{ a | a \in A \} = A\\ A \cap \varnothing &=& \{ a | \bot \} = \varnothing \end{eqnarray}as we have $p \wedge p \leftrightarrow p$ and $p \vee p \leftrightarrow p$, we also get
\begin{eqnarray} A \cup A &=& \{ a | a \in A \} = A\\ A \cap A &=& \{ a | a \in A \} = A \end{eqnarray}The composition of two unions corresponds to
\begin{equation} (A \cup B) \cup C = \{ a | a \in C \vee (a \in A \vee a \in B) \} \} \end{equation}As $\vee$ is associative, it can be shown that this is equivalent to $A \cup (B \cup C)$, and the same proof applies for $(A \cap B) \cap C$ and $A \cap (B \cap C)$. Therefore, both intersection and union are associative :
\begin{eqnarray} (A \cup B) \cup C &=& A \cup (B \cup C)\\ (A \cap B) \cap C &=& A \cap (B \cap C) \end{eqnarray}If we have $A \subset B$, ie, $a \in A \to a \in B$, we can use the rule $p \to q$ and $\neg p \to q$ implies $q$, giving us
\begin{eqnarray} A \cup B &=& \{ a | (a \in A \vee a \in B) \wedge (a \in A \to a \in B) \} \\ &=& \{ a | (\neg (a \in A) \to a \in B) \wedge (a \in A \to a \in B) \}\\ &=& \{ a | a \in B \}\\ &=& B \end{eqnarray} \begin{eqnarray} A \cap B &=& \{ a | a \in A \wedge a \in B \} \\ &=& \{ a | \neg (a \in A \to \neg (a \in B)) \}\\ \end{eqnarray}...
1.2. Relative complement
The relative complement is the case in which we use the non-implication, $p \nrightarrow q$.
\begin{equation} A \setminus B = \{ a | a \in A \wedge \neg (a \in B) \} \end{equation}From the contradiction $p \wedge \neg p \leftrightarrow \bot$, we get that
\begin{equation} A \setminus A = \{ a | a \in A \wedge \neg (a \in A) \} = \varnothing \end{equation} \begin{equation} \varnothing \setminus A = \{ a | \bot \wedge \neg (a \in A) \} = \varnothing \end{equation} \begin{equation} A \setminus \varnothing = \{ a | a \in A \wedge \top \} = A \end{equation}If $A \subset B$, as $a \in A \to a \in B$, we obtain a contradiction, and therefore
\begin{equation} A \setminus B = \{ a | \bot \} = \varnothing \end{equation}...
Symmetric difference
The symmetric difference is the set operation constructed from the exclusive disjunction
\begin{equation} A \Delta B = \{ a | a \in A \oplus a \in B \} \end{equation}As we have $p \oplus q \leftrightarrow ((p \wedge \neg q) \vee (\neg p \wedge q))$, it follows that
\begin{eqnarray} (A \setminus B) \cup (B \setminus A) &=& A \Delta B \end{eqnarray}As we also have $p \oplus q \leftrightarrow (\neg (p \wedge q) \wedge (p \vee q))$, we also have
\begin{eqnarray} (A \cup B) \setminus (A \cap B) &=& A \Delta B \end{eqnarray}As the exclusive disjunction is commutative and associative, so is the symmetric difference.
\begin{eqnarray} A \Delta B &=& B \Delta A\\ (A \Delta B) \Delta C &=& A \Delta (B \Delta C) \end{eqnarray}From the properties of the relative complement, if $A \subset B$, then
\begin{eqnarray} A \Delta B &=& (A \setminus B) \cup (B \setminus A)\\ &=& \varnothing \cup (B \setminus A)\\ &=& B \setminus A \end{eqnarray}Topological properties
A topology $\tau$ on a set $X$ is a set of subsets of $X$ such that $X$ and $\varnothing$ belong to $\tau$, if $U, V \in \tau$, then $U \cap V \in \tau$, and for a collection $\{ U_i \}$, $U_i \in \tau$, $i \in I$, we have
\begin{equation} \bigcup_{i \in I} U_i \in \tau \end{equation}In other words, finite intersection and arbitrary union preserves that property. Sets belonging to $\tau$ are called open sets. On a topology, we also define the notion of complement, noted $A^C$, such that the complement of a subset $A$ of $X$ is the relative complement of $X$ in $A$
\begin{equation} A^C = X \setminus A \end{equation}We define closed sets to be sets which have an open complement.
\begin{equation} A \in \text{Closed} \leftrightarrow A^C \in \tau \end{equation}A lot of properties of the complement naturally follow from its definition
\begin{eqnarray} \varnothing^C &=& X\\ X^C &=& \varnothing \end{eqnarray}Therefore, in $X$, both $X$ and $\varnothing$ are closed and open.
Behaviour of topology under set operations
From the definition of open sets, we have, rather simply
\begin{eqnarray} A \in \tau \wedge B \in \tau &\to& A \cup B \in \tau\\ A \in \tau \wedge B \in \tau &\to& A \cap B \in \tau\\ \end{eqnarray}Relative complement
Boundaries and interiors
\begin{equation} \forall A \subset X, \forall U \in \tau, (A \subset U \wedge \end{equation}Last updated : 2020-01-16 10:59:25