Function with an ordinal domain: an ambiguity between a notation for a value and for an image

79 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.