Notes - Set Theory HT25, Basic axioms

Created: January 20, 2025
Updated: February 04, 2025

Flashcards

Axioms

@State the extensionality axiom.
\[\forall x \forall y (x = y \leftrightarrow \forall z(z \in x \leftrightarrow z \in y))\]

@State the empty set axiom.
\[\exists x \forall y \text{ } y \notin x\]

@State the pairing axiom.
\[\forall x \forall y \exists z \forall w \text{ } (w \in z \leftrightarrow (w = x \lor w = y))\]

@State the union axiom.
\[\forall x \exists y \forall z \text{ } (z \in y \leftrightarrow \exists w (w \in x \land z \in w))\]

@State the powerset axiom.
\[\forall x \exists y \forall z \text{ } (z \in y \leftrightarrow z \subseteq x)\]

@State the comprehension axiom.

For any formula $\phi(z)$ with parameter $z$,

\[\forall x \exists y \forall z (z \in y \leftrightarrow (z \in x \land \phi(x)))\]

Notation

@Define the notation $\bigcup x$ and $\bigcup \{x, y\}$.

$\bigcup x$ is the set guaranteed to exist by the union axiom.

$\bigcup \{x, y\}$ is the union of $x$ and $y$.

@Define the notation $x \subseteq y$.
\[x \subseteq y \iff \forall z (z \in x \to z \in y)\]

@Define the notation $\bigcap x$.
\[\bigcap x := \\{a \in \bigcup x : \forall y \in x \text{ } a \in y\\}\]

Consequences

@Justify that there is a unique set with no elements.

Existence follows from the empty set axiom.

For uniqueness, suppose $x$ and $y$ both have no elements so that $\forall z \text{ } z \notin x$ and $\forall z \text{ } z \notin y$. But then by the extensionality axiom

\[\forall x \forall y (x = y \leftrightarrow \forall z(z \in x \leftrightarrow z \in y))\]

it follows that $x = y$.

@Justify that for any sets $x$ and $y$, there is a unique set whose elements are precisely $x$ and $y$.

Existence follows from the pairing axiom.

For uniqueness, suppose $a$ and $b$ both have this property. But then extensionality implies $a = b$.

What is

\[\mathcal P(\mathcal P(\mathcal P(\emptyset)))\]

?
\[\begin{aligned} \mathcal P(\mathcal P(\mathcal P(\emptyset))) &= \mathcal P(\mathcal P(\\{\emptyset\\})) \\\\ &= \mathcal P(\\{\emptyset, \\{\emptyset\\}\\}) \\\\ &= \\{\emptyset, \\{\emptyset\\}, \\{\\{\emptyset\\}\\}, \\{\emptyset, \\{\emptyset\\}\\}\\} \end{aligned}\]

@example~

@Prove that there is no set of all sets, i.e. no set $\Omega$ such that $\forall x \text{ } x \in \Omega$.

Suppose $\Omega$ exists. Then by comprehension, consider $R := \{x \in \Omega \mid x \notin x\}$. But then $R \in \Omega$, but this implies $R \notin R$, a contradiction.



Related posts