*arrow_back*

*arrow_downward*

# The fundamental theorem of equivalence relations

**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