arrow_back arrow_downward

The fundamental theorem of equivalence relations

$ \def \N {{ \mathbb N }} \def \Z {{ \mathbb Z }} \def \Q {{ \mathbb Q }} \def \R {{ \mathbb R }} \def \C {{ \mathbb C }} \def \H {{ \mathbb H }} \def \S {{ \mathbb S }} \def \P {{ \mathbb P }} \def \to { \longrightarrow } \def \mapsto { \longmapsto } \def \then { ~ \Longrightarrow ~ } \def \iff { ~ \Longleftrightarrow ~ } \def \and { ~ \wedge ~ } \def \or { ~ \vee ~ } \def \d {{~\rm d}} % We prepend a space to the differential symbol `d`, for good measure! \def \IFF {{\hskip4pt \sc iff \hskip2pt}} \def \Int {{ \bf Int }} \def \Clo {{ \bf Clo }} \def \Lim {{ \bf Lim }} \def \Dom {{ \bf Dom }} \def \Cod {{ \bf Cod }} \def \Ker {{ \bf Ker }} \def \Img {{ \bf Img }} \def \coKer {{ \bf coKer }} \def \coImg {{ \bf coImg }} \def \rem {{ \hskip4pt \rm rem \hskip4pt }} \def \tab {{ \hskip16pt }} $

Unions and intersections of sets are something I find confusing. But they’re super important. For instance, when learning general topology, we must become fluent with unions, intersections, and other set-theoretic stuff (like complements, powersets, subsets, functions, covers, uncountability, etc.), because general topology is basically just the topology of sets, and all the important ideas in general topology (like continuous, compact, metrizable, second-countable, Hausdorff, paracompact, countably locally finite, etc.) are stated in the language of sets.

Union: the elements that are in at least one element

There’s two notations to denote unions (both of which I find useful).
One is \(\cup A\). This is a unary operation.
The other is \(A \cup B\). This is a binary operation.
The unary operation \(\cup\) takes the set \(A\) to the set \(\cup A\). The set \(\cup A\) is a new set, made of the elements that are in at least one element of \(A\).
The binary operation \(\cup\) takes the sets \(A\) and \(B\) to the set \(A \cup B\). The set \(A \cup B\) is a new set, made of all the elements in \(A\) and all the elements in \(B\).

\(\tab\) Example. Let \(A\) be the set \(\{a1, a2, a3\}\).
Then the set \(\cup A\) is the set \(\cup \{a1, a2, a3\}\), and this set can also be written as \(a1 \cup a2 \cup a3\). To pin it down explicitly we need more information.
Let \(a1\) be the set \(\{a11, a12\}\), let \(a2\) be the set \(\{a21, a22\}\), let \(a3\) be the set \(\{a31, a32\}\).
Assume that
\(\tab\) \(a11 \neq a21\), and \(a11 \neq a22\), and \(a11 \neq a31\), and \(a11 \neq a32\), and
\(\tab\) \(a12 \neq a21\), and \(a12 \neq a22\), and \(a12 \neq a31\), and \(a12 \neq a32\), and
\(\tab\) \(a21 \neq a11\), and \(a21 \neq a12\), and \(a21 \neq a31\), and \(a21 \neq a32\), and
\(\tab\) \(a22 \neq a11\), and \(a22 \neq a12\), and \(a22 \neq a31\), and \(a22 \neq a32\), and
\(\tab\) \(a31 \neq a11\), and \(a31 \neq a12\), and \(a31 \neq a21\), and \(a31 \neq a22\), and
\(\tab\) \(a32 \neq a11\), and \(a32 \neq a12\), and \(a32 \neq a21\), and \(a32 \neq a22\).
Now the set \(\cup A\) is the set \(\cup \{a1, a2, a3\}\), which is the set \(\cup\{\{a11, a12\}, \{a21, a22\}, \{a31, a32\}\}\), which is the set \(\{a11, a12, a21, 22, a31, a32, b11, b12, b21, 22, b31, b32\}\), by the definition of "*the elements that are in at least one element*".
Notice that the set \(\cup A\) is the set \(\cup \{\{a11, a12\}, \{a21, a22\}, \{a31, a32\}\}\) (in unary notation) and also the set \(\{a11, a12\} \cup \{a21, a22\} \cup \{a31, a32\}\) (in binary notation).

\(\tab\) Example. Let \(A\) be the set \(\{a1, a2, a3\}\), let \(B\) be the set \(\{b1, b2, b3\}\).
Then the set \(A \cup B\) is the set \(\{a1, a2, a3\} \cup \{b1, b2, b3\}\), and this set can also be written as \(\cup\{A, B\}\), or as \(\cup\{ \{a1, a2, a3\}, \{b1, b2, b3\} \}\). To pin it down explicitly we need more information.
Assume that
\(\tab\) \(a1 \neq b1\), and \(a2 \neq b1\), and \(a3 \neq b1\), and
\(\tab\) \(a1 \neq b2\), and \(a2 \neq b2\), and \(a3 \neq b2\), and
\(\tab\) \(a1 \neq b3\), and \(a2 \neq b3\), and \(a3 \neq b3\).
Now the set \(A \cup B\) is the set \(\{a1, a2, a3\} \cup \{b1, b2, b3\}\), which is the set \(\{a1, a2, a3, b1, b2, b3\}\), by the definition of "*all the elements in \(A\) and all the elements of \(B\)*".
Notice that the set \(A \cup B\) is the set \(\cup \{\{a1, a2, a3\}, \{b1, b2, b3\}\}\) (in unary notation) and also the set \(\{a1, a2, a3\} \cup \{b1, b2, b3\}\) (in binary notation).

The moral of the story is that we can take the union \(\cup A\) of a single set \(A\), but then we’re seeing \(A\) as a set of sets (because we’re focusing on the elements of its elements).
And we can take the union \(A \cup B\) of two sets \(A\) and \(B\), but then we’re seeing \(A\) and \(B\) as just sets (because we’re focusing on their elements).
But, in ZFC, a set can only contain other sets. So the elements of a set \(A\) are always sets, which actually makes \(A\) a set of sets, and the elements of the elements of \(A\) are also sets, which actually makes \(A\) a set of sets of sets, and ... It’s sets all the way down (until you reach the empty set). So calling something "a set" or "a set of sets" or "a set of sets of sets of sets ... of sets" is just relative (to a particular level in this hierarchy). \(\tab\) Definition. The union \(\cup A\) of a set \(A\) is the set of all elements that are in at least one element of \(A\).

\(\tab\) Definition. The union \(A \cup B\) of two sets \(A\) and \(B\) is the set of all elements of \(A\) and all elements \(B\).

Axiomatically, in ZFC we form the union \(\cup A\) of the set \(A\) using the axiom of union.
And we form the union \(A \cup B\) of the sets \(A\) and \(B\) using the axiom of pair and the axiom of union. The axiom of pair yields the pair \(\{A, B\}\), and the axiom of union yields the union \(\cup\{A, B\}\). Then we can define the set \(A \cup B\) as the set \(\cup\{A, B\}\) (which is confusing because we’re using the same symbol \(\cup\) for two different operations: one unary operation and one binary operation).

Intersection: the elements that are in every element

There’s two notations to denote intersections.
One is \(\cap A\). This is a unary operation.
The other is \(A \cap B\). This is a binary operation.
The unary operation \(\cap\) takes the set \(A\) to the set \(\cap A\). The set \(\cap A\) is a new set, made of the elements that are in every element of \(A\).
The binary operation \(\cap\) takes the sets \(A\) and \(B\) to the set \(A \cap B\). The set \(A \cap B\) is a new set, made of the elements that \(A\) and \(B\) have in common.

\(\tab\) Example. Let \(A\) be the set \(\{a1, a2, a3\}\).
Then the set \(\cap A\) is the set \(\cap\{a1, a2, a3\}\), and this set can also be written as \(a1 \cap a2 \cap a3\). To pin it down explicitly we need more information.
Let \(a1\) be the set \(\{a11, a12\}\), let \(a2\) be the set \(\{a21, a22\}\), let \(a3\) be the set \(\{a31, a32\}\).
Assume that
\(\tab\) \(a11 \neq a21\), and \(a11 \neq a22\), and \(a11 \neq a31\), and \(a11 \neq a32\), and
\(\tab\) \(a12 \neq a21\), and \(a12 \neq a22\), and \(a12 \neq a31\), and \(a12 \neq a32\), and
\(\tab\) \(a21 \neq a11\), and \(a21 \neq a12\), and \(a21 \neq a31\), and \(a21 \neq a32\), and
\(\tab\) \(a22 \neq a11\), and \(a22 \neq a12\), and \(a22 \neq a31\), and \(a22 \neq a32\), and
\(\tab\) \(a31 \neq a11\), and \(a31 \neq a12\), and \(a31 \neq a21\), and \(a31 \neq a22\), and
\(\tab\) \(a32 \neq a11\), and \(a32 \neq a12\), and \(a32 \neq a21\), and \(a32 \neq a22\).
Now the set \(\cap A\) is the set \(\cap \{a1, a2, a3\}\), which is the set \(\cap\{\{a11, a12\}, \{a21, a22\}, \{a31, a32\}\}\), which is the set \(\{\}\), by the definition of "*the elements that are in every element*".
Notice that the set \(\cap A\) is the set \(\cap \{\{a11, a12\}, \{a21, a22\}, \{a31, a32\}\}\) (in unary notation) and also the set \(\{a11, a12\} \cap \{a21, a22\} \cap \{a31, a32\}\) (in binary notation).

\(\tab\) Example. Let \(A\) be the set \(\{a1, a2, a3\}\), let \(B\) be the set \(\{b1, b2, b3\}\).
Then the set \(A \cap B\) is the set \(\{a1, a2, a3\} \cap \{b1, b2, b3\}\), and this set can also be written as \(\cap{A, B}\), or as \(\cap\{\{a1, a2, a3\}, \{b1, b2, b3\}\}\). To pin it down explicitly we need more information. Assume that
\(\tab\) \(a1 \neq b1\), and \(a2 \neq b1\), and \(a3 \neq b1\), and
\(\tab\) \(a1 \neq b2\), and \(a2 \neq b2\), and \(a3 \neq b2\), and
\(\tab\) \(a1 \neq b3\), and \(a2 \neq b3\), and \(a3 \neq b3\).
Now the set \(A \cap B\) is the set \(\{a1, a2, a3\} \cap \{b1, b2, b3\}\), which is the set \(\{\}\), by the definition of "*all the elements that \(A\) and \(B\) have in common*".
Notice that the set \(A \cap B\) is the set \(\cap \{\{a1, a2, a3\}, \{b1, b2, b3\}\}\) (in unary notation) and also the set \(\{a1, a2, a3\} \cap \{b1, b2, b3\}\) (in binary notation).

\(\tab\) Definition. The intersection \(\cap A\) of a set \(A\) is the set of all elements that are in every element of \(A\).

\(\tab\) Definition. The intersection \(A \cap B\) of two sets \(A\) and \(B\) is the set of all elements that \(A\) and \(B\) have in common.

The fundamental theorem of unions and intersections: de Morgan’s laws

After understanding what union and intersections do (to sets), the next thing is to understand that they’re the same. Well, they’re not actually the same, but they’re two sides of the same coin: unions are dual to intersections. In category-theoretic language, unions are coproducts and intersections are products. Also, unions are defined using logical disjunction (ie. logical or), and intersections are defined using logical conjunction (ie. logical and). Disjunctions are products and conjunctions are coproducts, so disjunctions are dual to conjunctions. The duality between unions and intersections is known as de Morgan’s theorem (or de Morgan’s laws, or de Morgan duality).

Before stating the fundamental theorem of unions and intersecions (aka. de Morgan’s laws), we need a new operation: complement (aka. set complement or set-theoretic complement).

\(\tab\) Example. Let \(A\) be the set \(\{a1, a2, a3, a4, a5\}\), let \(A' \subseteq A\) be the set \(\{a2, a4, a5\}\). The complement \(\overline{A'}\) of \(A'\) (in \(A\)), also denoted \(A \setminus A'\), is the set \(\{a1, a3\}\), meaning
\(\tab\tab1)\) \(\overline{A'}\) equals \(\{a1, a3\}\)
\(\tab\tab2)\) \(A \setminus A'\) equals \(\{a1, a3\}\).
\(\tab\) Definition. Let \(A\) be a set, and let \(A' \subseteq A\) be a subset of \(A\).
The complement \(\overline{A'}\) of \(A'\) (in \(A\)), also denoted \(A \setminus A'\), is the set of all elements of \(A\) that are not elements of \(A'\). In symbols,
\(\tab\tab1)\) \(\overline{A'} \hskip8pt := \hskip8pt \{a \in A \hskip6pt | \hskip6pt a \notin A' \}\)
\(\tab\tab2)\) \(A \setminus A' \hskip8pt := \hskip8pt \{a \in A \hskip6pt | \hskip6pt a \notin A' \}\).
We’re ready to state

\(\tab\) Theorem (de Morgan’s theorem). Let \(A\) be a set, let \(A1\) and \(A2\) be subsets of \(A\). Now,
\(\tab\tab1)\) \(\overline{A1 \cup A2} \hskip8pt = \hskip8pt \overline{A1} \cap \overline{A2}\)
\(\tab\tab2)\) \(\overline{A1 \cap A2} \hskip8pt = \hskip8pt \overline{A1} \cup \overline{A2}\).
Equivalently,
\(\tab\tab1')\) \(A \setminus (A1 \cup A2) \hskip8pt = \hskip8pt (A \setminus A1) \hskip4pt\cap\hskip4pt (A \setminus A2)\)
\(\tab\tab2')\) \(A \setminus (A1 \cap A2) \hskip8pt = \hskip8pt (A \setminus A1) \hskip4pt\cup\hskip4pt (A \setminus A2)\).
\(\tab\) Proof. TODO