Using only the axioms of FOL and ZFC-AoI, can we prove the following?

$0\in N$

$\land \forall x\in N: S(x)\in N$

$\land \forall x,y \in N:[S(x)=S(y)\implies x=y]$

$\land \forall x\in N:S(x)\neq 0$

$\land \forall P\subset N: [0\in P \land \forall x\in P: [S(x)\in P] \implies P=N]$

$\implies \exists I: [\emptyset \in I \land \forall x\in I: [x\cup \{ x \}\in I]]$

EDIT: I assume only the existence of the algebraic structure $(N, S, 0)$ described in the antecedent, FOL and the axioms of ZFC-AoI.


closed as unclear what you're asking by Andrés E. Caicedo, Asaf Karagila, Leucippus, Shailesh, Namaste Aug 10 '17 at 1:26

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Dan, the question makes no sense. The Axiom of Infinity is formulated in the language of set theory and PA is formulated in the language of arithmetic. So PA cannot even talk about the existence of sets, they are not part of the signature. $\endgroup$ – Asaf Karagila Aug 9 '17 at 21:57
  • 1
    $\begingroup$ @Eric: Yes, that is what I understand from the question. But past experience with its OP had taught me to ask for every possible clarification, and never guess what is or isn't intended. $\endgroup$ – Asaf Karagila Aug 9 '17 at 22:14
  • 3
    $\begingroup$ Dan, variables and constants are not the same. You are not using $N$ as a variable so, in spite of your comment, you are treating it as a constant. An obvious problem with this is that there are no constants in ZFC, so constants are understood as abbreviations introduced via definitions. So, before you can state the axioms, you need to define N. What is the formal definition you are using? $\endgroup$ – Andrés E. Caicedo Aug 9 '17 at 22:36
  • 3
    $\begingroup$ If you intend $N $ to be treated as a variable, then you need to quantify over $N $ and replace your formula with a sentence. Precisely what sentence do you intend? $\endgroup$ – Andrés E. Caicedo Aug 9 '17 at 22:38
  • 2
    $\begingroup$ Also, what exactly is $S $? $\endgroup$ – Andrés E. Caicedo Aug 9 '17 at 22:39

Yes. To be precise, the following is a theorem of ZFC-Infinity:

Suppose there exists a set $N$, a function $S:N\to N$, and an element $0\in N$ such that $(N,S,0)$ satisfies the second-order Peano axioms (that is, the list of properties you wrote). Then the axiom of infinity is true (that is, there exists a set $I$ such that $\emptyset\in I$ and for all $x\in I$, $x\cup\{x\}\in I$).

[Note that this statement includes existential quantifiers on $N$, $S$, and $0$ which yours omits, which is necessary in order for it to be expressible as a sentence in the language of set theory.]

It is pretty complicated to write out all the details of the proof, but basically you develop all the usual theory of the natural numbers on the structure $(N,S,0)$ from the second-order Peano axioms to prove it is in bijection with the ordinal $\omega$. In particular, you prove that you can define functions on $N$ by recursion: given any (class) function $G$ and any $a$, you can define another (class) function $f$ with domain $N$ such that $f(0)=a$ and $f(S(x))=G(f(x))$ for all $x\in N$.

(Proof sketch: define a relation $\leq$ on $N$ by $x\leq y$ iff every subset of $N$ containing $x$ and closed under $S$ also contains $y$. Now prove by induction on $x$ that there exists a unique function $f_x$ on $\{y\in N:y\leq x\}$ such that $f(0)=a$ and $f(S(y))=G(f(y))$ for all $y<x$. The union of all these functions $f_x$ is then a function $f$ defined on all of $N$ with the required properties.)

In particular you can define a function $f$ on $N$ such that $f(0)=\emptyset$ and $f(S(x))=x\cup\{x\}$ for all $x$. By the axiom of replacement, the image of this function $f$ is a set $I$, which then witnesses the axiom of infinity.

  • $\begingroup$ +1 - however, note to the OP that we cannot prove the existence of the initial $N$ in your question in ZF-Inf alone. So from such an $N$ (or rather, such a $(0, S, N)$) ZF-Inf can deduce the existence of $\omega$, but that's all. $\endgroup$ – Noah Schweber Aug 9 '17 at 23:54
  • $\begingroup$ Does this proof make use of $0=\emptyset, S(0)=\{ \emptyset \}, S(S(0)) = \{\emptyset, \{ \emptyset\}\},$ etc.? If so, can we still prove this theorem without these definitions? $\endgroup$ – Dan Christensen Aug 10 '17 at 2:23
  • $\begingroup$ @DanChristensen: No, not at all. It uses entirely "ordinary" mathematical reasoning about $(N,S,0)$ as an algebraic structure, and doesn't care at all what its elements are. $\endgroup$ – Eric Wofsey Aug 10 '17 at 2:31
  • $\begingroup$ @Dan: If that was really your question, how do you explain this answer of yours from three years ago, which claims that Infinity is equivalent to the existence of a set with a non-surjective injection from itself to itself? I mean, remove the 2nd order axiom from the list in your question, you get exactly what you claimed is already equivalent to Infinity. So... now your question is unclear for other reasons. $\endgroup$ – Asaf Karagila Aug 10 '17 at 5:36
  • 1
    $\begingroup$ @Dan Christensen: that clarification would probably be better as part of the question, which several people found unclear $\endgroup$ – Carl Mummert Aug 10 '17 at 16:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.