To be more specific than the short title, I try to gauge the size of some "normal" function spaces as e.g. found in functional analysis against set universe sizes at certain stages.

For the sake of the argument, let's think of an integral transformation such as $$ I(f)(x):=\int_0^x f(x+y) {\mathbb d}y $$ which we can read as a nicely behaved subset of $$(\mathbb R \to \mathbb R)\to(\mathbb R \to \mathbb R).$$ In terms of cardinality the latter is $$(|\mathbb R|^{|\mathbb R|})^{|\mathbb R|^{|\mathbb R|}}$$ and since $$|\mathbb R\to\{0,1\}|=|\{0,1\}|^{|\mathbb R|} = |{\mathcal P }\mathbb R | > |\mathbb R|$$ those space of transformation is already quite large.

Now on the other hand, let's look at the Neumann universe at a certain level. With $V_{\omega}$ we have the collection of all hereditarily finite sets and from he we want to apply the power set operation a finite number of times, e.g. $$V_{\omega+k}={\mathcal P }\,{\mathcal P }\,\cdot \cdot \cdot {\mathcal P }\,{\mathcal P }\,{\mathcal P }\,V_{\omega}$$ My issue is that the base of the exponential with ${\mathcal P }$ is "merely" what you get with exponentiation of $|\{0,1\}|$ but with function spaces I exponentiate (exponentials of) the reals.

The question is for what $\alpha$ a containing set $V_{\alpha}$ is "save", if I don't want to do induction of the exponential but stick to finite length expressions for functions spaces as the one above. I gather $V_{\omega+\omega}$ suffices for most math and the stuff I posted above, although it doesn't make for a closed universe when considering functions of bigger ordinals (out of scope of my question).

If I'm right with the above, desn't $V_{\omega+k}$ work too? Are there operations (or maybe, secondarily, proofs) that lead me out of a finite nuumer of powers of $V_{\omega}$?

Finaly, can does it suffice to consider constructive $_{\omega+k}$ or $_{\omega+\omega}$ instead of the $V$ variants at the same stage here? (I know that they coincide for just $L_\omega$.)


Generally speaking, that depends a lot on how you code things. You could encode the real numbers so that they appear, as the concrete object, at any arbitrarily chosen point in the hierarchy (e.g. you could say that the ordered pair $(a,b)$ is coded by $\{\{a\},\{a,b\},\alpha\}$ for some infinite ordinal $\alpha$, which ensures that anything whose definition goes through ordered pairs, like functions or equivalence relations, would have rank of at least $\alpha+1$).

If we ignore coding and only consider cardinality, i.e. "what would be the least rank in which we can encode such object", then the answer is that $V_{\omega+1}$ is the set of reals, and therefore the real numbers appear, as an object, in $V_{\omega+2}$.

Now, taking each power set brings you up by another level, as you pointed out. So the $\alpha$th power set of the real numbers is $V_{\omega+1+\alpha}$. If $\alpha\geq\omega$, this is just $\omega+\alpha$, and if $\alpha\geq\omega^2$ it's just $\alpha$.

If you just want the finite powers, then, $\alpha=\omega$, i.e. $V_{\omega+\omega}$, is your buddy, then. If you only care for a finite bound, $k$, then going for $k+1$ power sets, i.e. $V_{\omega+k+2}$, is enough.

Regarding the constructible hierarchy, though, this is a whole other thing. For one, $V=L$ is not a consequence of $\sf ZFC$, and for another $L_\alpha$ has the same cardinality as $\alpha$, whereas $V_\alpha$ can be enormously bigger than $\alpha$. Especially so in the cases you're interested in.

  • $\begingroup$ Thanks for the response. To if we consider efficient/small encoding of e.g. the graphs of functions, and I construct finite expressions from just "$\mathbb R$" and "$(*\to *)$", I understand $V_{\omega + \omega}$ is enough. But, for arbitrary long but finite quantities of those expression, can any $V_{\omega + k}$ for finite $k$ work too? $\endgroup$ – Nikolaj-K May 11 at 11:24
  • $\begingroup$ If you choosing your coding in a very particular way (which is not usually "just $\Bbb R$ and $(\cdot\to\cdot)$", but it also requires understanding what is $\Bbb R$ and what is $\cdot\to\cdot$ as set theoretic representations), then every "power set" is just one step in the hierarchy. You're asking how large is "my algorithm will take when compiled", but you're not specifying the language you're programming in, or the compiler, or the architecture of your computer. $\endgroup$ – Asaf Karagila May 11 at 11:29
  • $\begingroup$ Basically I want to understand the jumps in size of $x \mapsto 2^x $ vs. $x \mapsto |{\mathbb R}|^x$. Thinking of $|{\mathbb R}|$ as the first uncountable cardinal, I'm actually surprised that the requirements w.r.t. $\alpha$ in $V_\alpha$ depend on the representation. So since your answer to my previous question isn't a straight out no, I gather there are (possibly pathological) models of all those things where the finite expressions of such spaces do fit into $V_{\omega + k}$? Thanks for the answer. $\endgroup$ – Nikolaj-K May 11 at 11:41
  • $\begingroup$ Well, $|\Bbb R|$ is not the first uncountable cardinals. The point I am trying to get across here is that $\Bbb R$ or ordered pairs are not set theoretic objects. We can interpret them using sets. If you use the Kuratowski coding of ordered pairs, the result is different from using a "flat" pairing function (that does not increase rank), and if you use Dedekind cuts you will have a different rank than using Cauchy sequences. We are talking about "machine-level optimization" situation here, again. $\endgroup$ – Asaf Karagila May 11 at 11:48
  • 1
    $\begingroup$ @AlessandroCodenotti: First look at the normal coding of ordered pairs, and the fact that for any infinite $\alpha$, $V_\alpha\times V_\alpha$ has a bijection with $\alpha$. Moreover, these bijections are defined by recursion, so they are uniform. Now code $(a,b)$ as either the Kuratowski coding for finite-ranked $a,b$, or taking $f_\alpha(a,b)$ where $\alpha$ is the maximal rank of $a$ and $b$. I should have been more careful, and specify that it doesn't increase rank for infinite rank pairs. But there are so few finite ranked ones... :-) $\endgroup$ – Asaf Karagila May 12 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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