8
$\begingroup$

Axiom of Infinity says there is an inductive set (i.e. a set which includes $\emptyset$ and is closed under successor operator). Formally:

$Inf:\exists x~(\emptyset\in x~\wedge~\forall y\in x~~~S(y)\in x )$

But there are many other definable operators in set theory and one can define an infinite set/infinity axiom corresponding to some of these operators. For example consider the following version of Axiom of Infinity with respect to power set as an 1-ary operator.

$Inf^P:\exists x~(\emptyset\in x~\wedge~\forall y\in x~~~P(y)\in x )$

Now remove the Axiom of Infinity from the foundation and add a new $n_f$ - ary function symbol $f$ to $LST:=\{\in\}$ which is defined using a formula $\varphi (x_1,...,x_{n_f},y)$. i.e. We have $ZFC-Inf\vdash \forall x_1,...,x_{n_f}\exists !~y~\varphi (x_1,...,x_{n_f},y)$ and we are working within $\{\in,f\}$-theory $ZFC-Inf\cup \{\forall x_1,...,x_{n_f}~~~\varphi (x_1,...,x_{n_f},f(x_1,...,x_{n_f}))\}$.

Definition 1. For each defined operator $f$ in $ZFC-Inf$ define an axiom as follows:

$Inf^{f}: \exists x~(\emptyset\in x~\wedge~\forall x_1,...,x_{n_f}\in x~~~f(x_1,...,x_{n_f})\in x )$

(i.e. There exists an inductive set in the sense of the operator $f$)

Definition 2. We call a defined operator $f$ in $ZFC-Inf$ using formula $\varphi (x_1,...,x_{n_f},y)$, to be an "infinity producer" if one can prove existence of an infinite set within $\{\in,f\}$-theory $ZFC- Inf+Inf^{f} \cup \{\forall x_1,...,x_{n_f}~\varphi (x_1,...,x_{n_f},f(x_1,...,x_{n_f}))\}$ .

(By an "infinite set" I mean a set $x$ which there is no bijection from $x$ to a natural number. Note that the notion of a natural number is clearly definable using successor operator in $ZFC-Inf$)

Question 1. What are the necessary and sufficient conditions on the formula $\varphi (x_1,...,x_{n_f},y)$ such that the operator $f$ defined by the formula $\varphi (x_1,...,x_{n_f},y)$ is an infinity producer?

Question 2. Are all infinity producer operators "equivalent" or some of them produce stronger theories in the sense of implication or consistency strength? Precisely if $f,g$ are infinity producer operators defined by formulas $\varphi,\psi$, are these necessarily true?

(a) $Con(ZFC- Inf+Inf^{f} \cup \{\forall x_1,...,x_{n_f}~\varphi (x_1,...,x_{n_f},f(x_1,...,x_{n_f}))\})\Longleftrightarrow$

$Con(ZFC- Inf+Inf^{g} \cup \{\forall x_1,...,x_{n_g}~\psi (x_1,...,x_{n_g},g(x_1,...,x_{n_g}))\})$

(b) $\forall \sigma\in\{\in\}-Sent$

$ZFC- Inf+Inf^{f} \cup \{\forall x_1,...,x_{n_f}~\varphi (x_1,...,x_{n_f},f(x_1,...,x_{n_f}))\}\vdash \sigma\Longleftrightarrow$

$ZFC- Inf+Inf^{g} \cup \{\forall x_1,...,x_{n_g}~\psi (x_1,...,x_{n_g},g(x_1,...,x_{n_g}))\}\}\vdash \sigma$

Question 3. Is there a large cardinal axiom $A$ which is an upper bound for the consistency strength of all theories which one can produce using this kind of axioms of infinity? Precisely, is there a large cardinal axiom $A$ such that for all infinity producer operator $f$ defined by formula $\varphi$ within $ZFC-Inf$ we have

$Con(ZFC+A)\Longrightarrow Con(ZFC- Inf+Inf^{f} \cup \{\forall x_1,...,x_{n_f}~\varphi (x_1,...,x_{n_f},f(x_1,...,x_{n_f}))\})$

Question 4. If all infinity producer operators are "not" equivalent, which one of them should we choose to add to our foundation ($ZFC-Inf$) to produce infinite sets? Why should we prefer the successor operator $S$?

$\endgroup$
  • $\begingroup$ Isn't $Inf^P$ inconsistent (with ZF)? It seems that $Inf^P$ includes an unbounded sequence of cardinals, which seems awefully close to a set of all sets... $\endgroup$ – fgp May 7 '14 at 15:01
  • 2
    $\begingroup$ Why would that be the case? Isn't $Inf^P$ satisfied by $\{V_n:n\in\omega\}$, whose existence would otherwise be guaranteed by the usual infinity axiom? $\endgroup$ – J.P. May 7 '14 at 15:20
  • $\begingroup$ A simpler axiom of infinity would be to postulate the existence of at least one Dedekind-infinite set, i.e. a set $X$ on which there is defined an injective function $f$ that is not surjective. From $X$, you could select at least one subset that satisfies Peano's Axioms with $f$ being the successor function. This, of course, assumes all the machinery of functions. $\endgroup$ – Dan Christensen May 7 '14 at 15:23
  • $\begingroup$ @J.P. Hm, true. $\endgroup$ – fgp May 7 '14 at 15:36
0
$\begingroup$

On Question 1: it is not entirely clear what you're after here, since Definition 2 trivially gives you necessary and sufficient conditions for $\phi(\vec{x}, y)$ to define an infinity operator. Perhaps you could be more specific.

On Question 2: the answer is "yes" in the sense of (b) (and thus in the sense of (a)). This follows from two results, namely:

${\bf Theorem}$ ${\bf 1.}$ ZFC proves $Inf^\phi$ for any formula $\phi$ which is provably functional in ZFC - $Inf$.

${\bf Theorem}$ ${\bf 2.}$ If $f$ is an infinity producer, then ZFC - $Inf$ + $Inf^f$ proves $Inf$.

Let $f$ be an infinity producer defined by $\phi\in\mathcal L_\in$. To see that (b) follows from theorems 1 and 2, first note that ZFC - $Inf$ + $Inf^f$ is conservative over ZFC - $Inf$ + $Inf^\phi$ with respect to $\mathcal L_\in$. Now let $\psi\in \mathcal L_\in$. By Theorem 1 and conservativity, if ZFC - $Inf$ + $Inf^f$ $\vdash \psi$, then ZFC $\vdash \psi$. Conversely, if ZFC $\vdash \psi$, then by Theorem 2, ZFC - $Inf$ + $Inf^f$ $\vdash \psi$. So every theory ZFC - $Inf$ + $Inf^f$ agrees with ZFC on formulas in $\mathcal L_\in$ and thus any two such theories agree with each other -- which is just what (b) says.

${\it Proof}$ ${\it of}$ ${\it Theorem}$ ${\it 1.}$ Working in ZFC, we can inductively define sets $x_n$ for $n\in \omega$ such that $x_0 = \{0\}$ and such that $z\in x_{n+1}$ whenever $\vec{y}\in \bigcup_{i\leq n}x_i$ and $\phi(\vec{y}, z)$. We just let $x_{n+1} = \{z: \exists\vec{y}\in \bigcup_{i\leq n}x_i \wedge \phi(\vec{y}, z)\}$ which exists by replacement. Now, I claim that $\bigcup_{n\in \omega}x_n$ is closed under $\phi$. If $\vec{y}\in\bigcup_{n\in \omega}x_n$, then there is some $n$ such that $\vec{y}\in \bigcup_{i\leq n}x_i$. So the unique $z$ such that $\phi(\vec{y}, z)$ is in $x_{n+1}$ and thus in $\bigcup_{n\in \omega}x_n$. $\Box$

${\it Proof}$ ${\it of}$ ${\it Theorem}$ ${\it 2.}$ If $f$ is an infinity producer, then ZFC - $Inf$ + $Inf^f$ proves there's an infinite set $x$. Now, define $F$ on $\mathcal P(x)$ such that $F(y) = |y|$ if the cardinality of $y$ exists and otherwise $F(y) = 0$. Then $rng(F)$ is a set by replacement and $\omega\subseteq rng(F)$ because $x$ is not one-one with any natural number. Thus ZFC - $Inf$ + $Inf^f$ proves $Inf$. $\Box$

On Question 3: The answer is "yes". In particular, since ZFC - $Inf$ + $Inf^f$ is conservative over ZFC - $Inf$ + $Inf^\phi$, it is a trivial consequence of Theorem 1 that if Con(ZFC), then Con(ZFC - $Inf$ + $Inf^f$).

On Question 4: This is conditional on a negative answer to Question 2 and so, by my answer to Question 2, not applicable.

$\endgroup$
0
$\begingroup$

A necessary and sufficient condition for a function $f$ to be an infinity producer is that on the inductive set $\omega^f$ given by $\textbf{Inf}^f$, $f$ is injective and does not have $0$ in its range.

For necessity:

If $f$ is not injective on $\omega^f$, there are some $x \neq y$ in $\omega^f$ with $f(x) = f(y)$. By the inductive definition of $\omega^f$, we have $x = f^n(0)$ and $y = f^m(0)$ for some natural numbers $m \neq n$. Let us suppose that $m < n$; but we have $f^{m+1}(0) = f^{n+1}(0)$ and hence $f^{m+k}(0) = f^{n+k}(0)$ for all naturals $k \ge 1$. In particular, $f^{m+(n-m)K+l}(0) = f^{m+(n-m)(K+1)+l}(0)$ for all naturals $K \ge 0$ and $n-m > l \ge 1$, so $f^{n-m}$ is the identity from $f^{m+1}(0)$ onwards. Thus, $\omega^f$ has only $m + n-m = n$ distinct elements.

If $f$ has $0$ in its range, there is some $x = f^n(0)$ in $\omega^f$ with $f(x) = f^{n+1}(0) = 0$. But then $f^{K(n+1) + l}(0) = f^l([[f^{n+1}]^K](0)) = f^l(0)$ for all naturals $K \ge 1$ and $l < n+1$, so there are again only $n$ distinct elements.

For sufficiency: Let the function $f$ interpret the successor function over $\omega^f$ [and let $0$ interpret $0$]; then $\omega^f$ is a model of the Peano axioms. The induction axiom follows because $\omega^f$ is the inductive set for $f$, the axiom "No $n$ has successor $0$" follows because $0$ is not in the range of $f$, and the axiom "Distinct numbers have distinct successors" follows because $f$ is injective on $\omega^f$.

$\endgroup$

Your Answer

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