6
$\begingroup$

As I understand, the Axiom of Infinity in ZFC theory gives us an infinite set from which the natural numbers can be extracted. (See "Axiom of Infinity" at http://en.wikipedia.org/wiki/Axiom_of_infinity)

Might the following proposed axiom be a weaker version (using everyday functional notation)?

$\exists X,S,x_0( S:X\to X\land \forall a,b\in X(S(a)=S(b)\to a=b) \land x_0\in X \land \forall a\in X(S(a)\ne x_0 ))$

In words, there exists $X,S$ and $x_0$ such that $S$ is a an injective function on $X$, and $x_0\in X$, and $x_0$ has no pre-image in $X$ under $S$.

Note: It can be shown that $X$ is Dedekind-infinite, and that it is possible to extract the natural numbers (as defined by Peano's Axioms) from $X$ where $S$ is the usual successor function and $x_0$ is the $0$ (or $1$).

$\endgroup$
  • 1
    $\begingroup$ Dan, as indicated in the answer, $\mathsf{ZF}$ without the axiom of infinity suffices to deduce the usual axiom of infinity from this version, so they are indeed equivalent. The key idea in that answer is the use of the recursion theorem. First, you prove that you can argue by induction on ordinals. Second, you verify (using induction) that for every natural number $n$ there is a unique function $f_n$ with domain $\{m\mid m<n\}$ and such that $f_n(0)=x_0$ and $f_n(t+1)=S(f_n(t))$ for all $t$ such that $t+1$ is in the domain of $f_n$. $\endgroup$ – Andrés E. Caicedo Aug 28 '13 at 20:50
  • 1
    $\begingroup$ Third, you check that if $m\ne n$, then $f_m$ and $f_n$ agree on their common domain. This allows you to fourth, extract a "function" (perhaps a proper class) by "pasting together" all the $f_n$. The range of this function is in bijection with its domain, $\omega$, since $S$ is injective. The range is a definable subclass of $X$, so it is a set. By replacement, the domain of this function is a set as well, so $\omega$ exists. The answer indicates that there are even ways to avoid the use of replacement. $\endgroup$ – Andrés E. Caicedo Aug 28 '13 at 20:54
  • $\begingroup$ @AndresCaicedo It is interesting to know that my "axiom" is indeed equivalent to AOI in ZF. It really just postulates the existence of what might be called a partial Peano system (one without induction). I have shown that, from this stripped down system, a full Peano system (with 2nd order induction) can be extracted. In a way, it justifies 2nd order induction -- but only if you assume the existence of this other quite similar system postulated by my "axiom." $\endgroup$ – Dan Christensen Aug 29 '13 at 3:01
  • $\begingroup$ Yes, I think it is interesting that this apparently very different approach ends up being equivalent. It also ties up nicely with your other question. $\endgroup$ – Andrés E. Caicedo Aug 29 '13 at 3:15
2
$\begingroup$

Your axiom is actually equivalent to the Axiom of Infinity modulo ZFC-{Infinity}. This is very easy to see via the replacement axiom, but it follows even just using Extensionality, Pairs, Unions, Specification and Powers: you can prove a version of the recursion theorem, from which you can extract the usual set $\omega$ of von Neumann numerals.

$\endgroup$
  • $\begingroup$ What does "modulo ZFC" mean? Are you saying the proposed axiom is not weaker? $\endgroup$ – Dan Christensen Aug 20 '13 at 14:26
  • $\begingroup$ "Modulo ZFC" means that the axioms of ZFC (without Infinity) prove their equivalence. And yes, I am saying the proposed axiom is not weaker. $\endgroup$ – walcher Aug 20 '13 at 14:30
  • $\begingroup$ Perhaps I don't have a proper understanding of the notion relative weakness, but the proposed axiom allows for $S(a)=a$ for some $a\in X$. Isn't this is not the case in ZFC? If so, doesn't this make the proposed axiom weaker in some sense? $\endgroup$ – Dan Christensen Aug 20 '13 at 14:38
  • $\begingroup$ @DanChristensen: Suppose we use the Axiom of Replacement to isolate the subset of $X$ for which $S(a) \neq a$. The injectivity and lack of "predecessor" for $x_0$ would be conserved, hence the Axiom of Infinity would be provable. $\endgroup$ – hardmath Aug 20 '13 at 14:51
  • 2
    $\begingroup$ Shouldn't you say "modulo $\mathsf{ZFC}-\text{Infinity}$"? Any tautology is equivalent to the Axiom of Infinity modulo $\mathsf{ZFC}$. $\endgroup$ – Trevor Wilson Aug 20 '13 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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