What is the abstract definition of an iteration?

172 Views Asked by At

There are lots of iterated processes in mathematics. The basic example in arithmetic is where you obtain addition through iterating successor operator and multiplication by iterating addition and exponentiation by iterating multiplication and so on.

I look for an abstract (set/category theoretic) definition of the notion of iteration in mathematics if there is any (please provide references); a definition which covers almost all forms of iteration in mathematics. Can it be viewed as an operator itself?

1

There are 1 best solutions below

0
On

I think that definition by recursion, in its various forms, is what you're looking for. I'll talk about definition by recursion from two angles: computability-theoretic and set-theoretic.


In the context of the natural numbers, there are many forms of recursion, beginning with primitive recursion (which is enough to build addition from successor, multiplication from addition, exponentiation from multiplication, tetration from exponentiation, etc.), and ending with $\mu$-recursion. One major topic in computability theory (often under the name "subrecursive hierarchies") is what functions can be built from a "starting set" using some fixed recursion principle; for example, $\mu$-recursion lets us build every computable function just starting with (essentially) successor, the projection functions, and the constant function $x\mapsto 0$, while primitive recursion can build lots of functions from these basic ingredients (addition, multiplication, exponentiation, tetration, ... the vast majority of functions on natural numbers which appear in practice are primitive recursive) but misses things like the Ackermann function.

Between primitive recursion and $\mu$-recursion is a vast swath of notions of recursiveness, and lots of research has gone into understanding this area and its various well-behaved subhierarchies. There is, however, a fundamental gap between primitive and $\mu$-recursion which prevents any "reasonable" hierarchy from "going all the way": namely, the primitive recursive functions are effectively listable and total, which means we can "diagonalize out of them:" letting $\psi(n)=1+p_n(n)$, where $p_n$ is the $n$th primitive recursive function in some fixed effective listing, yields a computable function which is not primitive recursive. Similarly, every level of the fast-growing hierarchy can be diagonalized out of. The $\mu$-recursive functions don't fall prey to this, since - while they are effectively listable - they aren't all total, and in fact we can't separate out the total ones from the partial ones.

Indeed, no good hierarchy for the computable functions in general is known, and in fact there are various results pointing towards the nonexistence of such a hierarchy.


Going far more generally, we can look at arbitrary definitions by transfinite recursion. The single-variable version goes as follows.

Suppose $\lambda$ is an ordinal and $X$ is some set (the codomain; often $\lambda$ itself). Let $F_{\lambda, X}$ denote the set of functions from some proper initial segment of $\lambda$ to $X$; an element of $F_{\lambda, X}$ can be thought of as a part of a whole function $\lambda\rightarrow X$.

Now suppose $I$ is a function from $F_{\lambda, X}$ to $X$; the idea being that when we feed $I$ some map $p: \alpha\rightarrow X$ ($\alpha<X$), $I$ tells us how to extend this map to one more value (namely, to a map $p': \alpha+1\rightarrow X$). We now intuitively want to define a map $f_I:\lambda\rightarrow X$ by iteratively applying $I$ at successor steps, and taking unions at limit steps.

We can in fact prove that this is always possible, and in a unique way:

Whenever $\lambda, X, I$ are as above, there is a unique map $f_I:\lambda\rightarrow X$ such that for all $\alpha<\lambda$, $f_I(\alpha)=I(f_I\upharpoonright\alpha)$.

The $n$-variable version of transfinite recursion is basically identical: we now have $n$-many iterators, $I_1, ...,I_n$; $I_i$ tells us how to define $f_{I_1, ..., I_n}(a_1, ...,a_i+1, ..., a_n)$ having already defined $f_{I_1, ..., I_n}(b_1, ..., b_n)$ for all $b_i\le a_i$. (This is similar to induction on multiple variables simultaneously; indeed induction is the proof technique corresponding to the construction method of recursion.)

Again, there is a unique "solution" for each $\lambda, X, I_1, ..., I_n$, and this lets us e.g. define ordinal exponentiation in terms of ordinal multiplication and so forth. The details are messier to write down, though.

We can generalize this to arbitrary well-founded partial orders, not just ordinals - this is a transfinite version of structural induction. This is the most general notion of recursive definition that I'm aware of.

(We can also treat class-sized domains - e.g. we can define a class function on the ordinals, by recursion on the ordinals. Nothing new happens here, we just need to say "class function" instead of "function," and so forth - the usual stuff.)


As a coda, there are also category-theoretic takes on definition by recursion; but I'm basically illiterate here, so I'll just point vaguely at some sources.

I think that this text by Moss and Danner on definition by corecursion is a very good source in this direction. Let me also point to this paper of Milius and Moss, which discusses this in more detail and mentions a number of interesting sources. Also see this text by Rutten on coinduction, which can be thought of as an interesting alternate approach to definition by recursion. And the keyword "monad" is going to show up a lot when looking at recursive definitions from a category-theoretic perspective.

It's worth noting that when approaching recursion from a more algebraic perspective (and so, often in category theory), we're frequently interested in less generality than that above: not all recursions are created equal, and the ones with "appropriate structure" are often a very proper subset of all the things a computability- or set-theorist would call "recursion." Category theory doesn't always try to make things maximally general; I'd say rather that it looks for the right amount of generality, and that's often less than full.