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

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

2011-05-14T03:10:07Z

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?

Answer by Stefan Geschke for Is there a least-fixed-point formulation of inaccessible cardinals?

2011-05-14T06:19:56Z

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.

Answer by David Milovich for Is there a least-fixed-point formulation of inaccessible cardinals?

2011-07-14T22:35:56Z

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)$.

Answer by Mike Shulman for Is there a least-fixed-point formulation of inaccessible cardinals?

2011-07-15T03:24:08Z

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.

Answer by Joel David Hamkins for Is there a least-fixed-point formulation of inaccessible cardinals?

2011-07-15T11:05:23Z

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.