Can the epsilon induction condition be presented with successor case and limit case, similar to transfinite induction?

Question

The epsilon induction looks like this: $\forall x \Big(\forall y (y \in x \rightarrow P(y)) \rightarrow P(x)\Big) \rightarrow \forall x P(x)$

Here, the quantifiers "run over" any sets and not only over ordinals, for which there are notions "successor" and "limit" used in transfinite induction (http://en.wikipedia.org/wiki/Transfinite_induction).

Thus, the question can be made more precise if notions similar to "successor" and "limit" for any sets are defined. There is some similarity between unary successor operation for ordinals and the binary operation over any sets called "adjunction" denoted as ";" (semicolon) and defined like this: $x;y = x \cup ${$y$}. But any non-empty set X is a successor of a set, since $X = (X \setminus ${x}) ; x, for any element x of $X$.

My interest in adjunction is due to a theory of inheritably finite sets based on adjunction operation with one induction principle by Laurence Kirby http://projecteuclid.org/euclid.ndjfl/1257862036

This theory has the negation of infinity axiom as an axiom as well as the axioms:

$ 0;x \ne 0, \ \ \ \ \ \ (1)$

$(x;y);y = x;y, \ \ \ \ (2)$

$(x;y);z = (x;z);y,\ \ \ (3)$

$(x;y);z = x;y \ \leftrightarrow \ x;z = x \vee z = y, \ (4)$

and the axiom scheme

$ P(0)\ \& \ \forall x y$ (P(x) & P(y) $\to P(x; y)) \to \forall x P(x). \ (5)$

Interestingly, in this theory, all regular set theoretic operations, including the unary union operation, are defined by induction. But probably, this principle cannot help defining this operation if the infinity axiom is postulated, and without the union operation a set theory sounds too poor.

Addition 1

To minimally modify the main text (since it was read by some participants of this forum), I just deleted its ending and labeled several axioms to make to them reference here, where I continue with comments clarifying the question.

The transfinite induction principle (http://en.wikipedia.org/wiki/Transfinite_induction) discusses about ordinals, and its condition is a conjunction of 3 formulas called "cases" - "zero case", "successor case", "limit case". These formulas discuss about three pairwise disjoint subclasses of the universe of discourse of set theory. By its form, the transfinite principle differs from the mathematical induction principle, which discusses about finite ordinals, without the limit case. One can say that Kirby extended the successor case so that it discusses about sets - hereditarily finite sets, and not only about finite ordinals.

Based on the above reasoning, the following hypothesis imposes as verisimilar: the condition of epsilon-induction which is about arbitrary sets (and not only about ordinals), can be also represented as a conjunction of 3 cases, discussing about 3 pairwise disjoint subclasses of the universe of discourse of set theory.

The induction principle is used in "proofs by induction", and such proofs employ different methods for each case. Therefore, if this hypothesis is a theorem in a set theory (in particular - an axiom), then this theorem will be a good contribution to proof theory for that set theory.

In search of a new form of induction principle, I proceed the manner described next. Suppose T is a theory with the axiom of infinity (and not its negation as in Kirby theory) and the axioms (1) - (4) of Kirby theory (but not also with the axiom scheme (5) of Kirby theory). For theory T, I present the induction principle with a condition which is the conjunction of three "cases" -- universal closures of these formulas:

Zero case: $P(0)$

Successor case: $\sigma(P)$

Limit case: $\lambda(P)$,

Here, $\sigma(P)$ and $\lambda(P)$ are built of terms like "P(x)", where the expression "to be built of" has the same meaning as the expression "$ (P(x) \& P(y) \to P(x; y))$ is built of $P(x)$" in (5) -- I am not sure how they would say this in logic.

Now, I am looking for the formulas $\sigma(P)$ and $\lambda(P)$. "Unfortunately", "$ (P(x) \& P(y) \to P(x; y))$ cannot serve as $\sigma(P)$, because every non-empty set is described by this condition, so that this condition covers both the "successor case" and the "limit case". Thus, only a stronger condition than $ (P(x) \& P(y) \to P(x; y))$ can play the role of $\sigma(P)$, and then $\lambda(P)$ would be $\neg (P(0) \vee \lambda(P))$. But I did not find such a "successor case" stronger than Kerby's which would also make sense in set-theoretic conceptuality.

I am looking for a three case induction proceeding from Kirby theory only because this theory looks attractive to me due to its axioms which use an operation rather than the relation of membership (notice, that $x ; y = y \ \leftrightarrow \ x \ \epsilon \ y$, and thus the membership relation can be expressed in this theory). But my question is wider than the question which makes reference to Kirby theory.

Answer 1

First, a tangential remark: keep in mind that transfinite induction itself isn't really a two-piece statement: it's just $$\forall \alpha(\forall \beta<\alpha(P(\beta))\implies P(\alpha))\implies \forall \alpha (P(\alpha)).$$

Note that this is basically identical to set induction. The picture of induction as having two cases comes from our intuition first being developed for finite ordinals, where "successor induction" $$P(0)\wedge \forall \alpha(P(\alpha)\implies P(\alpha+1)))\implies\forall\alpha (P(\alpha))$$ is sufficient, and then trying to extend this picture to arbitrary ordinals. The phrasing for the limit case - "if it holds below a limit then $P$ holds at the limit" - is already capturing all of induction.

---

OK, but can we still develop notions of "successor" and "limit" for arbitrary sets?

Well, if we can, we certainly want limit ordinals to be limit sets, and successor ordinals to be successor sets. One obvious approach is the following: Let $(*P)$ denote the statement "$P(x)\wedge P(y)\implies P(x;y)$. If we know $P(\beta)$, then assuming $(*P)$ we automatically know $P(\beta;\beta)=P(\beta+1)$.

By contrast, if $(*)$ is all we know about $P$ and $\lambda$ is a nonzero limit ordinal, then there is no way to write $\lambda=A;\beta$ so that $P(A)\wedge (*P)\implies P(\lambda)$; to see this, take $P$ to be the property $$P(x)\iff x\cap \lambda\text{ is a cofinal proper subset of $\lambda$}.$$ Certainly $(*P)$ is true - if $P(x)\wedge P(y)$, then $(x;y)\cap\lambda=x\cap \lambda$ is a cofinal proper subset of $\lambda$ - but whenever we write $\lambda=A; \beta$ we have $\neg P(\beta)$, and of course $P(\lambda)$ itself does not hold.

So here's a first stab at a definition:

A set $A$ is a successor set of type 1 if there is some $b\in A$ such that for any $P$, if $(*P)$ holds and $P(A-\{b\})$ holds, then $P(A)$ holds.

Unfortunately, this turns out to be a very limited definition: $A$ is a successor of type 1 iff $A=B\cup\{B\}=B;B$. This is pretty successor-ish, but seems to me too narrow to be a good candidate: for example, $\{0, 1, 2, 17\}$ is not a successor of type 1, but does feel successor-ish to me.

---

Here's a much more natural - at least from a classical set-theoretic perspective - notion of limit set: von Neumann rank. Given a set $A$, let $$rk(A)=\min\{\alpha: A\in V_\alpha\}$$ be the least level of the cumulative hierarchy where it appears. A limit set is then just a set whose rank is the successor of a limit. (We need "the successor of" since $V_\lambda=\bigcup_{\beta<\lambda} V_\beta$ for limit $\lambda$, that is, no new sets are added at limit stages.) Then the following is a natural breakup of the set induction principle into "successor" and "limit" cases:

$P$ holds for all $x$, assuming:

• If $P$ holds for all sets of rank $\alpha$, then $P$ holds for all sets of rank $\alpha + 1$; and

• If $P$ holds for all sets of rank $<\lambda$ ($\lambda$ limit), then $P$ holds for all sets of rank $\lambda+1$. (Again, that "+1" is used to get around the "no new sets at limit levels" issue.)

As in the ordinals case, the limit clause subsumes the successor clause.

Now we might object, "Hey! This is just a recasting of ordinary (heh) induction!" But ordinary transfinite induction is how we prove set induction, so for me this is actually the "right" way to look at it.

From the perspective of the OP, this is probably very unsatisfying due to the use of ordinals and the lack of reference to adjunction. I would argue, though, that this is unavoidable: adjunction is an extremely "local" operation, and full set induction is a "global" principle. For such global principles, adjunction isn't really relevant, and ordinals are the crucial objects which give us a "local" understanding of the universe, via ranks.