Set Theory HT25, Foundation
Flashcards
@State the axiom of foundation.
Every non-empty set $x$ has an $\in$-minimal element, i.e. an element $y \in x$ such that no element of $x$ is an element of $y$.
@Justify that the axiom of foundation makes sure that certain pathological sets don’t exist:
- There is no $x$ with $x \in x$.
- There are no $x$ and $y$ with $x \in y \in x$.
- There is no $x$ such that $\mathcal P(x) \in x$.
- There is no $x$ such that $\langle x, y\rangle \in x$ for any set $y$.
- If $x \in x$, then $\{x\}$ violates the axiom of foundation, since the only element of $\{x\}$ is $x$, but $x \cap \{x\} = \{x\} \ne \emptyset$.
- If $x \in y \in x$, then $\{x, y\}$ violates foundation, since $y \in x \cap \{x, y\}$ and $x \in y \cap \{x, y\}$.
- If $\mathcal P(x) \in x$, then $y = \{x, \mathcal P(x)\}$ violates foundation, since $x \cap y \ne \emptyset$ and $\mathcal P(x) \cap y \ne \emptyset$.
- If $\langle x, y \rangle \in x$ for some $y$, then $x \in \{x\} \in \langle x, y \rangle \in x$ and hence $Y = \{x, \{x\}, \langle x, y \rangle\}$ has no $\in$-minimal element.
For reference, the axiom of foundation states:
\[\forall x (x \ne \emptyset \to \exists y \in x \text{ }y \cap x = \emptyset)\]Every non-empty set $x$ has an $\in$-minimal element, i.e. an element $y \in x$ such that no element of $x$ is an element of $y$.
Examples
@Justify that every transitive set contains $\emptyset$.
Suppose $X$ is such a set. Then $X$ has an $\in$-minimal element, say $x$. Suppose that $x \ne \emptyset$, so that $y \in x$. But then by transitivity, $y \in X$, which contradicts $x$ being $\in$-minimal.
@exam~ @example~
@Justify that if $x^+ = y^+$, then $x = y$.
If $x \cup \{x\} = y \cup \{y\}$, then either $x = y$ or $x \in y$ and either $y = x$ or $y \in x$. If $x \ne y$, then $x \in y \in x$ violates the axiom of foundation.
@exam~ @example~