Intereting Posts

If $R$ is an integral domain with unity having only finitely many subdomains (not necessarily with unity), then is $R$ finite?
Cauchy-Schwarz in complex case, using discriminant
How to get the characteristic equation from a recurrence relation of this form?
Prove that $i^i$ is a real number
Development of imaginary exponent without appealing to “ambiguity” between $i$ and $-i$
Integrate $\csc^3{x} \ dx$
How a group represents the passage of time?
Reconciling several different definitions of Radon measures
How to prove this inequality(7)?
Prove that: $x_1\cdot x_2\cdots x_n>y_1\cdot y_2\cdots y_m$.
Compute $\int_0^\infty \frac{dx}{1+x^3}$
What is an example of real application of cubic equations?
Topologies of test functions and distributions
Levin's u-transformation
Functional equations leading to sine and cosine

Let $f:A\rightarrow A$ be a function. We can simply define $f\circ f$, $f\circ f\circ f$, etc., for each given natural number inductively.

$f^{(0)}=id_A$

$\forall n\in\omega \qquad f^{(n+1)}=f\circ f^{(n)}$

- Why is CH true if it cannot be proved?
- Integer induction without infinity
- Foundations of logic
- Example of set which contains itself
- Why can't we use implication for the existential quantifier?
- What axioms does ZF have, exactly?

How to define $f^{(\omega)}$ such that it be a function from $A$ to $A$? Is it possible to define $f^{(\alpha)}$ for arbitrary large ordinal number $\alpha$?

- If $A \subseteq C$ and $B \subseteq D$ then $A \times B \subseteq C \times D$
- Jech's proof of Silver's Theorem on SCH
- Failure of Choice only for sets above a certain rank
- Can any infinite ordinal be expressed as the sum of a limit ordinal and a finite ordinal?
- I read that ordinal numbers relate to length, while cardinal numbers relate to size. How do 'length' and 'size' differ?
- Sequence of surjections imply choice
- What are the main relationships between exclusive OR / logical biconditional?
- Composition of 2 involutions
- Why is this true? $(\exists x)(P(x) \Rightarrow (\forall y) P(y))$
- Couldn't we have defined the material conditional differently?

Yes, and no. Essentially, sometimes.

Consider the function $f(x)=-x$ for $x\in\Bbb R$. Then what would $f^{(\omega)}(x)$ be? It should be a limit of $f^{(n)}(x)$. But there is no limit.

Or consider the function $f(x)=x+1$ for $x\in\Bbb N$. Then $f^{(\omega)}(0)$ is what?

But consider the function $f(x)=x+1$ for $x\in\omega_1$, then $f^{(\omega)}(x)=x+\omega$ which is perfectly defined. But then $f^{(\omega_1)}$ causes the same issues as before.

You can sometimes talk about infinite iterations, but you need to have some mechanism to handle the limit steps. This usually requires topology, and convergence. And even then you may have to end up changing the domain a little bit.

So under additional assumptions (e.g. the function is surjective, and there is a way to assign values at limit points), yes. In general no.

One case, relatively simple and general, where you probably *can* do this sort of thing would seem to be given by Theorem 7.25 in Y. Moschovakis, *Notes on Set Theory* (2nd edition, Springer 2006).

I’ll paraphrase the statement of the theorem a little, because on the one hand, it doesn’t use your suggestive $f^{(\alpha)}$ notation, and on the other hand, it is couched in terms defined earlier in the book.

I have also extended the statement of the theorem, because as it stands, it only determines (in your notation) $f^{(\alpha)}(\bot)$ for one particular element $\bot$ of a particular kind of ordered set, whereas it seems clear that this special case can immediately be generalised by working in a subset of the ordered set.

(*Caveat emptor!* I may be talking rubbish, but if so, someone will surely correct me.)

Let $P$ be any partially ordered set which is chain-complete, i.e. every totally ordered subset $S \subseteq P$ has a least upper bound, $\sup S$.

Let $f: P \to P$ be any function which, while it might not necessarily preserve the order relation on $P$, is nevertheless “expansive” [I don’t know if this is a standard term, but it is the one used in the book], meaning that it satisfies the condition $f(x) \geqslant x$ for all $x \in P$.

Let $U$ be any well-ordered set, for example an ordinal $\beta$, considered as the set of all ordinals $\alpha < \beta$.

Then there is a unique definition of an expansive mapping $f^{(\alpha)}: P \to P$, for all $\alpha \in U$, such that:

$$

f^{(0)}(x) = x, \\

f^{(\alpha + 1)}(x) = f\big(f^{(\alpha)}(x)\big), \\

f^{(\lambda)}(x) = \sup_{\kappa < \lambda} f^{(\kappa)}(x)

$$

where $x$ is any element of $P$, $\alpha$ is any element of $U$, and $\lambda$ is a any limit element of $U$, i.e. $\lambda \ne 0$, and for all $\kappa < \lambda$, there exists $\mu$ such that $\kappa < \mu < \lambda$.

Moreover, if $\alpha \leqslant \gamma$, then $f^{(\alpha)}(x) \leqslant f^{(\gamma)}(x)$ (generalisation of the “expansive” property).

Finally, note that if $V$ is any other well-ordered set, then either $U$ or $V$ is (uniquely) isomorphic to an initial segment (not necessarily proper, of course) of the other; and if for example (w.l.o.g.) $\Psi: V \to U$ is an order-preserving injection, then $f^{(\delta)} = f^{(\Psi(\delta))}$, for all $\delta \in V$, by the uniqueness clause of the theorem.

In particular (the most important case, presumably), if both $U$ and $V$ are ordinals, then one of them is greater than or equal to the other, and it doesn’t matter whether you consider a smaller ordinal $\alpha$ as an element of $U$ or as an element of $V$: $f^{(\alpha)}$ is uniquely defined, for any ordinal $\alpha$.

I imagine one also has:

$$

f^{(\alpha + \beta)}(x) = f^{(\beta)}\big(f^{(\alpha)}(x)\big), \\

f^{(\alpha\beta)}(x) = \big(f^{(\alpha)}\big)^{(\beta)}(x),

$$

for all ordinals $\alpha$, $\beta$, all $x \in P$, and all expansive $f: P \to P$ (but I’m only guessing).

I also imagine this is pretty close to what started old Cantor off on the whole ordinal number thing!

(See e.g. P. E. B. Jourdain’s introduction to his translation of Cantor, *Contributions to the Founding of the Theory of Transfinite Numbers*, Dover reprint, p.35f. – Cantor was interested in transfinite iterations of a “derived set” operation, defined on a class of subsets of the real line.)

- Limit, solution in unusual way
- Infinitely many primes of the form $4n+3$
- Why is a matrix $A\in \operatorname{SL}(2,\mathbb{R})$ with $|\operatorname{tr}(A)|<2$ conjugate to a matrix of the following form?
- Conjugacy Class of Isomorphisms Between Two Isomorphic Groups Definition
- Prime counting function; when is it true that $\pi(n) > \pi(2n) -\pi(n)$?
- Proof a graph is bipartite if and only if it contains no odd cycles
- Number of coprimes of $n$ divisible by 3
- Are there $n$ groups of order $n$ for some $n>1$?
- Classifying groups of order 90.
- The $I$ in the smallest sigma algebra generated by collection of subsets of $\Omega$
- Upper triangular matrix and nilpotent
- How are the average rate of change and the instantaneous rate of change related for ƒ(x) = 2x + 5?
- Recursive formula for the number of connected labelled graphs with n vertices and k edges
- At least one prime between $\sqrt{n}$ and $n$?
- How prove this $|ON|\le \sqrt{a^2+b^2}$