Suppose $\mathbb{X}$ and $\mathbb{Y}$ are classes, and $f:\mathbb{X}\rightarrow\mathbb{Y}$. It seems like pretty standard course to consider an 'induced function' $f:\mathcal{P}\mathbb{X}\rightarrow\mathcal{P}\mathbb{Y}$ defined by $f(U)=\{f(u):u\in U\}$ for all $U\in\mathcal{P}\mathbb{X}$, and $f=\langle f(U):U\in\mathcal{P}\mathbb{X}\rangle$ (where we have abused the symbol $f$ in a safe way since the former function induces the latter and vice-verse by the image of singletons).

This is done when considering the continuity of a function in topology, for example, since we actually want to consider the preimage of open sets of $\mathbb{Y}$ under the mapping $f:\mathcal{P}\mathbb{X}\rightarrow\mathcal{P}\mathbb{Y}$ instead of individual elements.

I was wondering if this behaviour had been formalized and studied, particularly the suggested inductive tower of functions defined by $$f_0=f:\mathbb{X}\rightarrow\mathbb{Y},$$ $$f_{n+1}=\langle f_n(U):U\subseteq dmn f_n\rangle,$$ so $dmnf_0=\mathbb{X},\ dmnf_1=\mathcal{P}\mathbb{X},\dots,dmnf_n=\mathcal{P}^n\mathbb{X}=\mathcal{P}\dots\mathcal{P}\mathbb{X}$. I believe we could further define $$\mathcal{P}^\omega\mathbb{X}=\bigcup_{n<\omega}\mathcal{P}^n\mathbb{X},$$ or perhaps $$\mathcal{P}^\omega\mathbb{X}=\{\mathcal{U}:\mathcal{U}\subseteq\bigcup_{n<\omega}\mathcal{P}^n\mathbb{X}\},$$ and then define $f_\omega:\mathcal{P}^\omega\mathbb{X}\rightarrow\mathcal{P}^\omega\mathbb{Y}$ in the same fashion as above and extend the recursion on $\omega$ to a recursion on all of $O_n$ where we repeat the above step each time we encounter a limit ordinal. This would allow for the construction of an inductive tower of functions $\{f_\alpha\}_{\alpha\in O_n}$, where each successor function $f_{n+1}$ is, in general, much more complicated than $f_n$ (for example if $f_n$ is defined on a countable set then $f_{n+1}$ will be defined on an uncountable set, so on and so forth, and it also seems like $f_{n+1}$ carries the 'topological information' about $f_n$ in some sense), but all members of the tower are faithfully induced by some single base function.

I thought that perhaps a model theorist or a set theorist had written something about this somewhere that I could read to enlighten myself, or that perhaps one of the members here could see some obvious connection to a more well-known area of mathematics.

EDIT: Another place where it appears we are implicitly thinking in this manner is fibrations -- the Hopf fibration $p:S^3\rightarrow S^2$ seems to be the unique function from $S^3$ to $S^2$ whose induced function $p_1:\mathcal{P}S^3\rightarrow\mathcal{P}S^2$ has the property that $p_1^{-1}(U)$ is a circle in $S^3$ iff $U$ is a singleton. I believe that higher geometrical thinking can also be done in this fashion, since all the 'shapes' in $\mathbb{R}^n$ are elements of $\mathcal{P}\mathbb{R}^n$, so functions to lower dimensional spaces whose induced functions map certain kinds of subsets onto singletons should be fibrations of some type.

My question is really whether or not there are books/articles/papers already written which explore this approach, understanding higher order properties of functions in terms of induced functions on higher order powersets rather than considering the action of a element-wise function on a subset/collection of subsets etc.

  • $\begingroup$ ${\mathcal P}X=2^X$, is it? $\endgroup$ Sep 26, 2017 at 9:46
  • $\begingroup$ @SergeiAkbarov $\mathcal{P}\mathbb{X}$ is the powerclass of $\mathbb{X}$, so I'm considering it as the class of all subsets of $\mathbb{X}$ which is not technically a space of functions, but it is isomorphic to $2^\mathbb{X}$ where we identify a subset $U\subseteq\mathbb{X}$ with the function $f:\mathbb{X}\rightarrow\{0,1\}$ defined by $f(x)=1\iff x\in U$, $f(x)=0$ otherwise. $\endgroup$
    – Alec Rhea
    Sep 26, 2017 at 10:08
  • 1
    $\begingroup$ Alec I think you should specify your question, it looks a bit vague. If you just want to find a reading about this, I doubt that you'll find someting interesting. But if you are thinking about a concrete problem, you should specify it, and it will be easier for people to react. $\endgroup$ Sep 26, 2017 at 12:23

1 Answer 1


If you work in ZFA (ZF with atoms), and if $A$ is the class (or set) of atoms, and $f:A\to A$ is a permutation, then $f$ will (inductively, as you have described) induce a permutation $\bar f$ of the whole universe $V_A$, where $V_A = \bigcup_{\alpha\in ORD} V_{A,\alpha}$, $V_{A,0}=A$, $V_{A,\alpha+1} = A \cup {\mathcal P}V_{A,\alpha}$, $V_{A,\delta} = \bigcup_{\alpha < \delta} V_{A,\alpha}$ for limit ordinals $\alpha$.

Such maps $f$ and $\bar f$ have been studied a long time ago; they can be used to construct a "Fraenkel-Mostowski model"; in this model (of ZFA) the axiom of choice fails.

  • $\begingroup$ Fascinating and right along the lines of what I was looking for -- thank you. $\endgroup$
    – Alec Rhea
    Sep 27, 2017 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.