Let $f\colon\alpha\to\beta$ be a function from an ordinal $\alpha$ into an ordinal $\beta$. Since ordinals are transitive sets (i.e. a set $x$ so that $\forall y(y \in x \Longrightarrow y \subseteq x))$, the notation $f(\gamma)$ is somewhat ambiguous: it's not clear whether it denotes the unique element $\eta$ of $\beta$ so that the ordered pair $(\gamma,\eta)$ belongs to the relation $f$ or a set subset $\{ \eta < \beta \mid (\exists \xi < \gamma)((\xi,\eta) \in f) \}$ of $\beta$.

Generallity, this ambiguity is present in any situation where we have a function $f\colon X\to Y$ from a transitive set $X$.

However, what I'm interested in is when this ambiguity is actually phantom, that is, regardless whether $\gamma$ is considered as an element of $\alpha$ or a subset of $\alpha$, the value of $\gamma$ under $f$ and the image of $\gamma$ under $f$ are equal.

Suppose $f$ is an order-preserving surjective function with respect to the strict order $<$. Let $\gamma < \alpha$.

  • Let $\eta$ be an ordinal less than the value of $\gamma$ under $f$. Since $f$ is surjective there is an ordinal $\xi < \alpha$ so that $f(\xi) = \eta$. Since ordinals are totally ordered, we must either have $\xi < \gamma, \gamma < \xi$ or $\gamma = \xi$. $\gamma < \xi$ (resp., $\gamma = \xi$) imply $f(\gamma) < \eta$ (resp., $f(\gamma) = \eta$), contradicting the assumption that $\eta < f(\gamma)$. Thus, we must have $\xi < \gamma$, which means that there is an element $\xi$ of $\gamma$ so that $\eta = f(\xi)$, which means $\eta$ belongs to the image of $\gamma$ under $f$.

  • Let $\eta$ be an element of the image of $\gamma$ under $f$. Then there is $\xi < \gamma$ so that $f(\xi) = \eta$. Since $\xi < \gamma$ and $f$ is order-preserving, it implies $\eta = f(\xi) < f(\gamma)$.

But do we really need $f$ to be order-preserving and surjective?

  • 5
    $\begingroup$ This is why we use $f[A]$ or $f''A$ or $f"A$ to denote $\{f(a)\mid a\in A\}$ in contexts where all objects are sets. $\endgroup$
    – Asaf Karagila
    Sep 23, 2018 at 11:54
  • 1
    $\begingroup$ In set theory a function $f:A\to B$ is its graph, which is a certian kind of subset of $A\times B.$ Set theorists write $y=f(x)$ to mean $(x,y)\in f.$ And they write $Y=f''X$ (read $f$ -double-prime-$X$ or informally $ f$-double-tick-$X$ ) to mean $Y=\{f(x):x\in X\}$ when $X \subset$ dom$(f)$. $\endgroup$ Sep 23, 2018 at 12:10
  • $\begingroup$ @DanielWainfleet: Also called "$f$-double-hook" sometimes. $\endgroup$
    – Asaf Karagila
    Sep 23, 2018 at 14:06
  • $\begingroup$ @AsafKaragila. Anything to distinguish it from the 2nd derivative is fine with me. (I once wrote a memo to Prof, W.Weiss about a polynomial $f$ on a real-closed field where I used $f'$ for its formal deivative and used $f''$ for $f$-double-tick, as he called it.) $\endgroup$ Sep 23, 2018 at 15:04

1 Answer 1


Let $f$ be a function and let's assume that for any set $A$ we have $f(A)=\{f(a):a\in A\}$. We can't really give a domain that is a proper set (in the ZFC sense) without giving up that property on all subsets of the domain because if we had a domain $X$, $f(2^X)$ would be just as well defined but missing in the domain. But we can always restrict our function to a certain domain afterwards.

Now the property gives us some interesting properties already. Let $\operatorname{succ}X$ be defined as $X\cup\{X\}$ for any set $X$ and $\bigcup X = \{a:\exists Y\in X \mbox{ with } a\in Y\}$ as usual. Then we have $$f(\operatorname{succ}X) = f(X\cup\{X\}) = \{f(x):x\in X\} \cup \{f(X)\} = f(X) \cup \{f(X)\}=\operatorname{succ}f(X)$$ and $$f(\bigcup X) = \{f(a):\exists Y\in X \mbox{ with } a\in Y\} = \{\{f(a):a\in Y\} :Y\in X\}=\{f(Y):Y\in X\} = f(X)$$ Note that I need $\neg\emptyset\in X$ or $\exists Y\in X:f(Y)=\emptyset$ for the last line to work completely. From the union we additionally get $$f(X\cup Y)=f(\bigcup\{X,Y\})=f(\{X,Y\})=\{f(X),f(Y)\}$$ for non empty sets $X,Y$. Setting $Y=\{X\}$ confirms the first identity again.

Finally, we always have $f(\emptyset) = \{f(x):x\in\emptyset\} = \emptyset$. So if we restrict the domain to the ordinals (which is still no proper set), then $f$ is the identity function on the ordinals.

Let's try something else. For any ordinal $\alpha$, set $\alpha'=\alpha\setminus\{0\}$, e.g. we have $1'=\emptyset,2'=\{1\},3'=\{1,2\},4'=\{1,2,3\}$ etc. Since $f$ acts as identity on the ordinals, it is not difficult to see that $f(\alpha')=\alpha'$ again. Same holds for the new Elements generated by the $\alpha'$ elements, for example $\operatorname{succ}2'=\{1,\{1\}\}$.

Anything in ZFC is effectively built from the empty set in finite steps, so if you go down deep enough with the sets, you will always end up with the identity, no matter what your domain is (because the regularity axiom forbids infinitly recursing sets). Only way out is to explicitly forbid $\emptyset$ from being in the domain to begin with and give a better seed. For example $f(1):= \{1,\{1\}\}$, then $f(2)=\{1,\{1\},\{1,\{1\}\}\}$ etc., so that $f$ maps an ordinal $\alpha$ to $\operatorname{succ} \alpha$, but with all empty sets in its nested empty set representation replaced by 1. Feel free to try other seeds to come up with something more interesting :)

If the function $f$ is surjective depends solely on what you want your $Y$ in $f:X\to Y$ to be. I didn't use any ordering on purpose. Hope you have fun with these ideas.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .