How should I write this function $f:\mathcal P_{fin}(\omega^{<\omega})\to \mathcal P_{fin}(\omega^{<\omega})$?

123 Views Asked by At

How should I most clearly define the function that $f:\mathcal P_{fin}(\omega^{<\omega})\to \mathcal P_{fin}(\omega^{<\omega})$ which maps certain subsets of the power set of $\omega^{<\omega}$ to singletons, by deleting the smallest term of any ordinal (written in Cantor normal form) and reducing the exponent of all other terms by one:

$f:\displaystyle \bigcup_{s_1\in X}\{\omega^{b-1}\cdot s_1+\omega^{b-2}\cdot s_2+\ldots s_b:s_b \in X\subseteq\Bbb N\}\mapsto \{\omega^{b-2}\cdot s_1+\omega^{b-3}\cdot s_2+\ldots s_{b-1}\}$

Where $X\subseteq N$ and $s_b$ are drawn from $\Bbb N$?

Then this is surjective over $\mathcal P_{fin}(\omega^{<\omega})$ which indicates the subset of the power set, containing only finite sets of finite strings of naturals.

If this isn't clear, how best do I write this function so as to be clear?

Is "contraction mapping" an appropriate name for this function given that it must eventually terminate?

1

There are 1 best solutions below

5
On BEST ANSWER

In your written definition of the function, there are several things that are unclear; for example, I don't really understand the emphasis on $s_1$ over the other terms, or how you're interpreting "$\bigcup$." I also don't understand your claim that it maps sets to singletons, given your example $\{\omega+1,\omega+2,\omega+3,\omega^2\cdot 3\}\mapsto\{1,\omega\cdot 3\}$.

Based on your example in the comments, though, I suspect that what you're asking for is the following. I'll first build it in stages, rather than describing it all at once, and then give an all-at-once definition below.

Incidentally, it does not always terminate; e.g. $f(\{\omega^n:n\in\mathbb{N}\})=\{\omega^n: n\in\mathbb{N}\}$ if I understand it correctly. Maybe you want to look at $\mathcal{P}_{fin}(\omega^{<\omega})$ - the set of finite sets of finite strings of naturals - instead of $\mathcal{P}(\omega^{<\omega})$? Also, the term "contraction mapping" has a technical meaning in the study of metric spaces, which this could conceivably fit but only after you've defined an appropriate metric structure.


  • First, let $C: \omega^{<\omega}\rightarrow\omega^\omega$ be the Cantor normal form function, sending a finite string of naturals to the ordinal $<\omega^\omega$ which it represents. (Note that $C$ is noninjective - for example, it sends both $\langle 0,1\rangle$ and $\langle 1\rangle$ to $1$ - so if you want an injection, it will be a slight modification of the obvious $C$.)

  • Next, we have the truncation function $$trun:\omega^{<\omega}\setminus\{\langle\rangle\}\rightarrow\omega^{<\omega}: \langle a_1,..., a_n\rangle\mapsto \langle a_1,..., a_{n-1}\rangle.$$ Note that this isn't defined on the empty string; if you prefer, you could define it to be the identity on the empty string, that is, set $trun(\langle\rangle)=\langle\rangle$.

  • Next, we have the pointwise version of your $f$: $$g:\omega^{<\omega}\rightarrow\omega^{<\omega}: C(\sigma)\mapsto C(trunc(\sigma)).$$ This does what you want on a single finite string of ordinals; e.g. $$g(\omega^2+\omega)=g(C\langle1,1,0\rangle)=C(trunc(\langle 1,1,0\rangle))=\omega+1.$$ Note that we have to show that $g$ is actually well-defined - that is, if $C(\alpha)=C(\beta)$ then $C(trunc(\alpha))=C(trunc(\beta))$ - but this is easy.

  • Finally, your $f$ is the "set version" of $g$: $$f:\mathcal{P}(\omega^{<\omega})\rightarrow\mathcal{P}(\omega^{<\omega}): S\mapsto\{g(s): s\in S\}.$$


OK, now here's the all-at-once definition: $f$ is the function from $\mathcal{P}(\omega^{<\omega})$ to $\mathcal{P}(\omega^{<\omega})$ which sends a set $X$ to the set

$$\{\omega^n\cdot s_{n+1}+\omega^{n-1}\cdot s_n+...+\omega^0\cdot s_1: \exists t(\omega^{n+1}\cdot s_{n+1}+\omega^{n}\cdot s_n+...+\omega^{1}\cdot s_1+t\in X)\}.$$