Set Theory HT25, Foundation


Flashcards

@State the axiom of foundation.


\[\forall x (x \ne \emptyset \to \exists y ( y \in x \land 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$.

@Justify that the axiom of foundation makes sure that certain pathological sets don’t exist:

  1. There is no $x$ with $x \in x$.
  2. There are no $x$ and $y$ with $x \in y \in x$.
  3. There is no $x$ such that $\mathcal P(x) \in x$.
  4. There is no $x$ such that $\langle x, y\rangle \in x$ for any set $y$.

  1. If $x \in x$, then $\lbrace x\rbrace$ violates the axiom of foundation, since the only element of $\lbrace x\rbrace$ is $x$, but $x \cap \lbrace x\rbrace = \lbrace x\rbrace \ne \emptyset$.
  2. If $x \in y \in x$, then $\lbrace x, y\rbrace$ violates foundation, since $y \in x \cap \lbrace x, y\rbrace$ and $x \in y \cap \lbrace x, y\rbrace$.
  3. If $\mathcal P(x) \in x$, then $y = \lbrace x, \mathcal P(x)\rbrace$ violates foundation, since $x \cap y \ne \emptyset$ and $\mathcal P(x) \cap y \ne \emptyset$.
  4. If $\langle x, y \rangle \in x$ for some $y$, then $x \in \lbrace x\rbrace \in \langle x, y \rangle \in x$ and hence $Y = \lbrace x, \lbrace x\rbrace , \langle x, y \rangle\rbrace$ 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$.

@Prove that the axiom of foundation implies there are no infinite descending $\in$-chains, i.e. there cannot exist a sequence $(x _ n) _ {n \in \mathbb N}$ such that for all $n$, $x _ {n} \ni x _ {n+1}$. Visually:

\[x _ 0 \ni x _ 1 \ni x _ 2 \ni \cdots\]

Formally, such a sequence is a class function $f : \omega \to V$. By the axiom of replacement, the image of $f$ is a set. But apply the axiom of foundation to this set.

Examples

@Justify that every non-empty 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~




Related posts