Skip to main content
2 of 7
added 113 characters in body
user76284
  • 2.2k
  • 15
  • 24

Shortest axiom of infinity for foundationless set theory

Let $T$ be the theory with a binary symbol $\in$, an unary symbol $S$, and the following axioms:

Axiom of extension: \begin{equation} \forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \rightarrow x = y) \end{equation}

Axiom of heredity: \begin{equation} \forall x (S x \leftrightarrow \forall y (y \in x \rightarrow S y)) \end{equation}

Axiom schema of comprehension: \begin{equation} \forall x (\phi x \rightarrow S x) \rightarrow \exists y \forall x (x \in y \leftrightarrow \phi x) \end{equation} for every formula $\phi$ not containing $S$.


Let $I$ be the formula \begin{equation} \exists x (S x \land \varnothing \in x \land \forall y (y \in x \rightarrow y \cup \{y\} \in x)) \end{equation}

asserting the existence of an inductive set, where $\varnothing \in x$ and $y \cup \{y\} \in x$ are expanded according to their usual definitions in set theory. What is the shortest formula $\psi$ such that $T, \psi \vdash I$ and $T, \psi \nvdash \bot$? How strong is the resulting theory $T, \psi$? Since $T$ lacks foundation, such a $\psi$ must deal with the possibility of non-well-founded sets.

user76284
  • 2.2k
  • 15
  • 24