Let us work in ZFC set theory, let A and B be two sets and C be the set of functions with domain A and range B. Question: what can be said about c=rank(C), knowing a=rank(A) and b=rank(B) ? Gérard Lang
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Kunen, chapter III, exercise 4. $\endgroup$– GoldsternCommented Nov 24, 2013 at 17:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Note that every function $f$ is a subset of $A\times B$, and so the rank of $C$ is at most $\newcommand{\rank}{\operatorname{rank}}\rank(\mathcal P(A\times B))$.
It is possible that $\rank(A\times B)=\rank(A)=\rank(B)$. For example in the case $A=B=\omega$. But it is possible that $\rank(A\times B)>\rank(A),\rank(B)$. For example where $A$ and $B$ are finite sets.
More generally if $\max\{\rank(A),\rank(B)\}$ is a limit ordinal then you can show that $A\times B$ will have the same rank as that maximum, otherwise it will have a strictly larger rank.
To be on the safe side, you can always show that $\rank{A^B}\geq\max\{\rank(A),\rank(B)\}+3$.
answered Nov 24, 2013 at 16:37
-
1$\begingroup$ If you use a flat pairing function (and your sets have infinite rank), you can reduce the $+3$ to $+1$, since in that case pairs do not increase rank. The $+3$ arises from the Kuratowski pairing function, which increases rank by $2$, but there are other pairing function that do not do this. $\endgroup$ Commented Nov 24, 2013 at 17:56
-
$\begingroup$ True, Joel. Thank you for pointing that out. It's one of the places where the choice of encoding the pairs matters. $\endgroup$– Asaf Karagila ♦Commented Nov 24, 2013 at 19:01
-
$\begingroup$ Another ranking function which will accomplish what Joel's describes is Quine's pairing function: en.wikipedia.org/wiki/Ordered_pair#Quine-Rosser_definition $\endgroup$ Commented Nov 25, 2013 at 3:05