# Is there a least-fixed-point formulation of inaccessible cardinals?

The infinity axiom can be formulated by defining a function $S$ as

$$S(N) = \{0\} \cup \{n+1\\ |\\ n \in N\}$$

(FWIW, I'm assuming the von Neumann ordinals.) The axiom is then

$$\exists I . I = S(I)$$

which gives us our first infinite set. Then $\omega$ is the intersection of all the subsets of $I$ that are also fixed points, or the least fixed point of $S$.

I've been curious about this for a while now: can the first (strongly, uncountable) inaccessible cardinal be defined similarly?

-

Every inaccessible cardinal is a fixed point of the operation $P$ that assigns to every set $X$ of ordinals the set $P(X)=\{2^{|\alpha|}:\alpha\in X\}\cup\bigcup X$. On the other hand, every (nonempty) fixed point of $P$ is a strong limit, the least nonempty fixed point being $\omega$.

Now here is the problem: If you have any operation $R$ on sets of ordinals that is

(1) monotone, i.e., $A\leq B$ implies $R(A)\leq R(B)$, and

(2) continuous, i.e., if $\mathcal A$ is an increasing chain of sets of ordinals, then $R(\bigcup\mathcal A)=\bigcup\{R(A):A\in\mathcal A\}$,

then you can construct fixed points by choosing an increasing sequence $(\alpha_n)_{n\in\omega}$ such that for all $n$, $R(\alpha_n)<\alpha_{n+1}$. Then $\alpha=\sup_{n\in\omega}\alpha_n$ is a fixed point of $R$, but it is of countable cofinality and hence, if uncountable, not inaccessible.

If you don't like the fact that I am using functions from sets of ordinals to sets of ordinals instead of functions from ordinals to ordinals, just observe that the "sets of ordinals" formulation is actually more general. Strong limits are also fixed points of the operation $\alpha\mapsto\sup\{2^{|\beta|}:\beta<\alpha\}$.

So, if you want inaccesibles as fixed points, you will have to go with operations that are either not monotone or not continuous. A non-monotone operation that works is this: map every ordinal to the first inaccessible. (Doesn't charaterize inaccessibles, just the first.) A non-continuous operation that works is this:

Map every ordinal $\alpha$ to itself if it is inaccessible and to $\alpha+1$ otherwise. This is of course silly and hence you have to give some more restrictions on the kind of functions that you allow. I think monotone and continuous is natural, but doesn't work.

-

A different sort of answer is possible if one works in type theory, rather than in set theory. In type theory, the corresponding notion to a "least fixed point" is an inductively defined type. For instance, the natural numbers are inductively defined by zero and the successor operation. More general inductive types, with correspondingly stronger induction principles, correspond to the existence of larger ordinals in set theory. I believe that a form of inductive type which roughly corresponds to an inaccessible is an "inductive-recursive universe". If I remember correctly, the general principle of definition by induction-recursion seems to be about as strong as a Mahlo cardinal.

-
I'd like to, but I don't know a whole lot about it yet myself. One reference which looks promising is "Induction-recursion and initial algebras" by Dybjer and Setzer. –  Mike Shulman Jul 16 '11 at 3:25

There is a monotone (but discontinuous) operation $F$ that does what you want in a way that is quite natural (in my opinion):

$F(\alpha)=(\omega+1)\cup\sup_{f\in{}^{<\alpha}\alpha}\left(\left(\sup_{\gamma\in\mathrm{ran}(f)}|P(f(\gamma))|\right)+1\right)$.

-
An over-powered metamathematical alternative is to let $F(\alpha)$ be the set of ordinals definable, using ordinal parameters less than $\alpha$, in $\mathrm{ZFC}^2$ (i.e., ZFC with Replacement bumped up to its second-order version that quantifies over external functions). The models of $\mathrm{ZFC}^2$ are exactly those $V_\kappa$ where $\kappa$ is inaccessible. These models are also known as the (uncountable) <a href="en.wikipedia.org/wiki/… universes</a>, which are characterized by a finite list of closure properties (some of them second-order). –  David Milovich Jul 15 '11 at 19:39
Sorry for the mangled link. Try en.wikipedia.org/wiki/Grothendieck_universe –  David Milovich Jul 15 '11 at 19:43
One can attain something like a positive solution with the observation that the inaccessible cardinals are precisely the regular fixed points of the beth function $\alpha\mapsto\beth_\alpha$, which is monotone and continuous. In particular, the first inaccessible cardinal is the smallest regular beth fixed point.