Mixing
How should I write this function $f:mathcal P_fin(omega^<omega)to mathcal P_fin(omega^<omega)$? [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
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_1in Xomega^b-1cdot s_1+omega^b-2cdot s_2+ldots s_b:s_b in XsubseteqBbb Nmapsto omega^b-2cdot s_1+omega^b-3cdot s_2+ldots s_b-1$
Where $Xsubseteq 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?
elementary-set-theory notation terminology ordinals
asked Jul 21 at 9:26
Robert Frost
3,880936
closed as unclear what you're asking by Andrés E. Caicedo, Andreas Blass, amWhy, José Carlos Santos, Parcly Taxel Jul 23 at 1:46
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
 |Â
show 1 more comment
up vote
0
down vote
favorite
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_1in Xomega^b-1cdot s_1+omega^b-2cdot s_2+ldots s_b:s_b in XsubseteqBbb Nmapsto omega^b-2cdot s_1+omega^b-3cdot s_2+ldots s_b-1$
Where $Xsubseteq 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?
elementary-set-theory notation terminology ordinals
asked Jul 21 at 9:26
Robert Frost
3,880936
closed as unclear what you're asking by Andrés E. Caicedo, Andreas Blass, amWhy, José Carlos Santos, Parcly Taxel Jul 23 at 1:46
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
2
What do you mean with $mathcal P(omega^<omega)$ here?
– Wojowu
Jul 21 at 10:38
@Wojowu definitively I'm talking about $omega^<omega$ being the set of strings of positive integers of unlimited length but I'm pretty sure the ordinals I've given in Cantor normal form express this as the set of all ordinals less than $omega^omega$. Then $mathcal P(omega^<omega)$ is its power set.
– Robert Frost
Jul 21 at 11:27
There's one thing I know I'm not doing so well here, and that's for $f$ to be well-defined over over all of $mathcal P(omega^<omega)$ then I should probably better express how it will map certain sets to non-singletons
– Robert Frost
Jul 21 at 12:02
1
For any given set, are all the $s$'s except the first the same or do they and $b$ range over all of $Bbb N$? If $X$ were $1,2,3$ would the set have three elements with $b$ and the larger $s_i$ the same, or would it be all ordinals with the largest term having a coefficient of $1,2,$ or $3$? In any case it is not injective as $omega+1$ and $omega+2$ both go to $1$.
– Ross Millikan
Jul 21 at 14:15
@RossMillikan yes, sorry re injective that was silly. $f(omega+1,omega+2,omega+3,omega^2cdot3)=1,omegacdot 3$.
– Robert Frost
Jul 21 at 16:18
 |Â
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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_1in Xomega^b-1cdot s_1+omega^b-2cdot s_2+ldots s_b:s_b in XsubseteqBbb Nmapsto omega^b-2cdot s_1+omega^b-3cdot s_2+ldots s_b-1$
Where $Xsubseteq 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?
elementary-set-theory notation terminology ordinals
asked Jul 21 at 9:26
Robert Frost
3,880936
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_1in Xomega^b-1cdot s_1+omega^b-2cdot s_2+ldots s_b:s_b in XsubseteqBbb Nmapsto omega^b-2cdot s_1+omega^b-3cdot s_2+ldots s_b-1$
Where $Xsubseteq 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?
elementary-set-theory notation terminology ordinals
asked Jul 21 at 9:26
Robert Frost
3,880936
edited Aug 10 at 14:54
asked Jul 21 at 9:26
Robert Frost
3,880936
asked Jul 21 at 9:26
Robert Frost
3,880936
asked Jul 21 at 9:26
Robert Frost
3,880936
3,880936
closed as unclear what you're asking by Andrés E. Caicedo, Andreas Blass, amWhy, José Carlos Santos, Parcly Taxel Jul 23 at 1:46
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
closed as unclear what you're asking by Andrés E. Caicedo, Andreas Blass, amWhy, José Carlos Santos, Parcly Taxel Jul 23 at 1:46
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
2
What do you mean with $mathcal P(omega^<omega)$ here?
– Wojowu
Jul 21 at 10:38
@Wojowu definitively I'm talking about $omega^<omega$ being the set of strings of positive integers of unlimited length but I'm pretty sure the ordinals I've given in Cantor normal form express this as the set of all ordinals less than $omega^omega$. Then $mathcal P(omega^<omega)$ is its power set.
– Robert Frost
Jul 21 at 11:27
There's one thing I know I'm not doing so well here, and that's for $f$ to be well-defined over over all of $mathcal P(omega^<omega)$ then I should probably better express how it will map certain sets to non-singletons
– Robert Frost
Jul 21 at 12:02
1
For any given set, are all the $s$'s except the first the same or do they and $b$ range over all of $Bbb N$? If $X$ were $1,2,3$ would the set have three elements with $b$ and the larger $s_i$ the same, or would it be all ordinals with the largest term having a coefficient of $1,2,$ or $3$? In any case it is not injective as $omega+1$ and $omega+2$ both go to $1$.
– Ross Millikan
Jul 21 at 14:15
@RossMillikan yes, sorry re injective that was silly. $f(omega+1,omega+2,omega+3,omega^2cdot3)=1,omegacdot 3$.
– Robert Frost
Jul 21 at 16:18
 |Â
show 1 more comment
2
What do you mean with $mathcal P(omega^<omega)$ here?
– Wojowu
Jul 21 at 10:38
@Wojowu definitively I'm talking about $omega^<omega$ being the set of strings of positive integers of unlimited length but I'm pretty sure the ordinals I've given in Cantor normal form express this as the set of all ordinals less than $omega^omega$. Then $mathcal P(omega^<omega)$ is its power set.
– Robert Frost
Jul 21 at 11:27
There's one thing I know I'm not doing so well here, and that's for $f$ to be well-defined over over all of $mathcal P(omega^<omega)$ then I should probably better express how it will map certain sets to non-singletons
– Robert Frost
Jul 21 at 12:02
1
For any given set, are all the $s$'s except the first the same or do they and $b$ range over all of $Bbb N$? If $X$ were $1,2,3$ would the set have three elements with $b$ and the larger $s_i$ the same, or would it be all ordinals with the largest term having a coefficient of $1,2,$ or $3$? In any case it is not injective as $omega+1$ and $omega+2$ both go to $1$.
– Ross Millikan
Jul 21 at 14:15
@RossMillikan yes, sorry re injective that was silly. $f(omega+1,omega+2,omega+3,omega^2cdot3)=1,omegacdot 3$.
– Robert Frost
Jul 21 at 16:18
2
2
What do you mean with $mathcal P(omega^<omega)$ here?
– Wojowu
Jul 21 at 10:38
What do you mean with $mathcal P(omega^<omega)$ here?
– Wojowu
Jul 21 at 10:38
@Wojowu definitively I'm talking about $omega^<omega$ being the set of strings of positive integers of unlimited length but I'm pretty sure the ordinals I've given in Cantor normal form express this as the set of all ordinals less than $omega^omega$. Then $mathcal P(omega^<omega)$ is its power set.
– Robert Frost
Jul 21 at 11:27
@Wojowu definitively I'm talking about $omega^<omega$ being the set of strings of positive integers of unlimited length but I'm pretty sure the ordinals I've given in Cantor normal form express this as the set of all ordinals less than $omega^omega$. Then $mathcal P(omega^<omega)$ is its power set.
– Robert Frost
Jul 21 at 11:27
There's one thing I know I'm not doing so well here, and that's for $f$ to be well-defined over over all of $mathcal P(omega^<omega)$ then I should probably better express how it will map certain sets to non-singletons
– Robert Frost
Jul 21 at 12:02
There's one thing I know I'm not doing so well here, and that's for $f$ to be well-defined over over all of $mathcal P(omega^<omega)$ then I should probably better express how it will map certain sets to non-singletons
– Robert Frost
Jul 21 at 12:02
1
1
For any given set, are all the $s$'s except the first the same or do they and $b$ range over all of $Bbb N$? If $X$ were $1,2,3$ would the set have three elements with $b$ and the larger $s_i$ the same, or would it be all ordinals with the largest term having a coefficient of $1,2,$ or $3$? In any case it is not injective as $omega+1$ and $omega+2$ both go to $1$.
– Ross Millikan
Jul 21 at 14:15
For any given set, are all the $s$'s except the first the same or do they and $b$ range over all of $Bbb N$? If $X$ were $1,2,3$ would the set have three elements with $b$ and the larger $s_i$ the same, or would it be all ordinals with the largest term having a coefficient of $1,2,$ or $3$? In any case it is not injective as $omega+1$ and $omega+2$ both go to $1$.
– Ross Millikan
Jul 21 at 14:15
@RossMillikan yes, sorry re injective that was silly. $f(omega+1,omega+2,omega+3,omega^2cdot3)=1,omegacdot 3$.
– Robert Frost
Jul 21 at 16:18
@RossMillikan yes, sorry re injective that was silly. $f(omega+1,omega+2,omega+3,omega^2cdot3)=1,omegacdot 3$.
– Robert Frost
Jul 21 at 16:18
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
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^2cdot 3mapsto1,omegacdot 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:ninmathbbN)=omega^n: ninmathbbN$ if I understand it correctly. Maybe you want to look at $mathcalP_fin(omega^<omega)$ - the set of finite sets of finite strings of naturals - instead of $mathcalP(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^<omegarightarrowomega^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,1rangle$ and $langle 1rangle$ 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^<omegasetminuslangleranglerightarrowomega^<omega: langle a_1,..., a_nranglemapsto langle a_1,..., a_n-1rangle.$$ 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(langlerangle)=langlerangle$.
Next, we have the pointwise version of your $f$: $$g:omega^<omegarightarrowomega^<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(Clangle1,1,0rangle)=C(trunc(langle 1,1,0rangle))=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:mathcalP(omega^<omega)rightarrowmathcalP(omega^<omega): Smapstog(s): sin S.$$
OK, now here's the all-at-once definition: $f$ is the function from $mathcalP(omega^<omega)$ to $mathcalP(omega^<omega)$ which sends a set $X$ to the set
$$omega^ncdot s_n+1+omega^n-1cdot s_n+...+omega^0cdot s_1: exists t(omega^n+1cdot s_n+1+omega^ncdot s_n+...+omega^1cdot s_1+tin X).$$
answered Jul 21 at 19:20
Noah Schweber
111k9140261
Thank-you. I can't believe something so easy to say "delete the smallest term of any ordinal (in Cantor normal form) and reduce the exponent of all other terms" is so difficult for me to work out how to write clearly.
– Robert Frost
Jul 21 at 19:24
One final thing... this always terminates on iteration, and... is it okay to call it a contraction mapping?
– Robert Frost
Jul 21 at 19:26
...PPS why do you have $C: omega^<omegarightarrowomega^omega$ rather than$C: omega^<omegarightarrowomega^<omega$?
– Robert Frost
Jul 21 at 19:27
2
@RobertFrost $C$ is the function that takes in a finite string and outputs the ordinal it names, so it's a map from $omega^<omega$ to $omega^omega$. As I explained, however, $f$ does not always terminate on iteration (unless you change $mathcalP(omega^<omega)$ to $mathcalP_fin(omega^<omega)$, that is, restrict the domain to finite sets of finite sequences), and since the term "contraction mapping" already has meaning, it would be incorrect to use it here, unless you establish that it does in fact fit that definition. I would call it a "truncation map," personally.
– Noah Schweber
Jul 21 at 19:36
P.s. re mapping to singletons and $s_1$, it maps sets of elements whose sequence is identical except for $s_1$ to singletons.
– Robert Frost
Jul 22 at 1:25
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
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^2cdot 3mapsto1,omegacdot 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:ninmathbbN)=omega^n: ninmathbbN$ if I understand it correctly. Maybe you want to look at $mathcalP_fin(omega^<omega)$ - the set of finite sets of finite strings of naturals - instead of $mathcalP(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^<omegarightarrowomega^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,1rangle$ and $langle 1rangle$ 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^<omegasetminuslangleranglerightarrowomega^<omega: langle a_1,..., a_nranglemapsto langle a_1,..., a_n-1rangle.$$ 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(langlerangle)=langlerangle$.
Next, we have the pointwise version of your $f$: $$g:omega^<omegarightarrowomega^<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(Clangle1,1,0rangle)=C(trunc(langle 1,1,0rangle))=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:mathcalP(omega^<omega)rightarrowmathcalP(omega^<omega): Smapstog(s): sin S.$$
OK, now here's the all-at-once definition: $f$ is the function from $mathcalP(omega^<omega)$ to $mathcalP(omega^<omega)$ which sends a set $X$ to the set
$$omega^ncdot s_n+1+omega^n-1cdot s_n+...+omega^0cdot s_1: exists t(omega^n+1cdot s_n+1+omega^ncdot s_n+...+omega^1cdot s_1+tin X).$$
answered Jul 21 at 19:20
Noah Schweber
111k9140261
Thank-you. I can't believe something so easy to say "delete the smallest term of any ordinal (in Cantor normal form) and reduce the exponent of all other terms" is so difficult for me to work out how to write clearly.
– Robert Frost
Jul 21 at 19:24
One final thing... this always terminates on iteration, and... is it okay to call it a contraction mapping?
– Robert Frost
Jul 21 at 19:26
...PPS why do you have $C: omega^<omegarightarrowomega^omega$ rather than$C: omega^<omegarightarrowomega^<omega$?
– Robert Frost
Jul 21 at 19:27
2
@RobertFrost $C$ is the function that takes in a finite string and outputs the ordinal it names, so it's a map from $omega^<omega$ to $omega^omega$. As I explained, however, $f$ does not always terminate on iteration (unless you change $mathcalP(omega^<omega)$ to $mathcalP_fin(omega^<omega)$, that is, restrict the domain to finite sets of finite sequences), and since the term "contraction mapping" already has meaning, it would be incorrect to use it here, unless you establish that it does in fact fit that definition. I would call it a "truncation map," personally.
– Noah Schweber
Jul 21 at 19:36
P.s. re mapping to singletons and $s_1$, it maps sets of elements whose sequence is identical except for $s_1$ to singletons.
– Robert Frost
Jul 22 at 1:25
 |Â
show 1 more comment
up vote
1
down vote
accepted
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^2cdot 3mapsto1,omegacdot 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:ninmathbbN)=omega^n: ninmathbbN$ if I understand it correctly. Maybe you want to look at $mathcalP_fin(omega^<omega)$ - the set of finite sets of finite strings of naturals - instead of $mathcalP(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^<omegarightarrowomega^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,1rangle$ and $langle 1rangle$ 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^<omegasetminuslangleranglerightarrowomega^<omega: langle a_1,..., a_nranglemapsto langle a_1,..., a_n-1rangle.$$ 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(langlerangle)=langlerangle$.
Next, we have the pointwise version of your $f$: $$g:omega^<omegarightarrowomega^<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(Clangle1,1,0rangle)=C(trunc(langle 1,1,0rangle))=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:mathcalP(omega^<omega)rightarrowmathcalP(omega^<omega): Smapstog(s): sin S.$$
OK, now here's the all-at-once definition: $f$ is the function from $mathcalP(omega^<omega)$ to $mathcalP(omega^<omega)$ which sends a set $X$ to the set
$$omega^ncdot s_n+1+omega^n-1cdot s_n+...+omega^0cdot s_1: exists t(omega^n+1cdot s_n+1+omega^ncdot s_n+...+omega^1cdot s_1+tin X).$$
answered Jul 21 at 19:20
Noah Schweber
111k9140261
Thank-you. I can't believe something so easy to say "delete the smallest term of any ordinal (in Cantor normal form) and reduce the exponent of all other terms" is so difficult for me to work out how to write clearly.
– Robert Frost
Jul 21 at 19:24
One final thing... this always terminates on iteration, and... is it okay to call it a contraction mapping?
– Robert Frost
Jul 21 at 19:26
...PPS why do you have $C: omega^<omegarightarrowomega^omega$ rather than$C: omega^<omegarightarrowomega^<omega$?
– Robert Frost
Jul 21 at 19:27
2
@RobertFrost $C$ is the function that takes in a finite string and outputs the ordinal it names, so it's a map from $omega^<omega$ to $omega^omega$. As I explained, however, $f$ does not always terminate on iteration (unless you change $mathcalP(omega^<omega)$ to $mathcalP_fin(omega^<omega)$, that is, restrict the domain to finite sets of finite sequences), and since the term "contraction mapping" already has meaning, it would be incorrect to use it here, unless you establish that it does in fact fit that definition. I would call it a "truncation map," personally.
– Noah Schweber
Jul 21 at 19:36
P.s. re mapping to singletons and $s_1$, it maps sets of elements whose sequence is identical except for $s_1$ to singletons.
– Robert Frost
Jul 22 at 1:25
 |Â
show 1 more comment
up vote
1
down vote
accepted
up vote
1
down vote
accepted
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^2cdot 3mapsto1,omegacdot 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:ninmathbbN)=omega^n: ninmathbbN$ if I understand it correctly. Maybe you want to look at $mathcalP_fin(omega^<omega)$ - the set of finite sets of finite strings of naturals - instead of $mathcalP(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^<omegarightarrowomega^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,1rangle$ and $langle 1rangle$ 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^<omegasetminuslangleranglerightarrowomega^<omega: langle a_1,..., a_nranglemapsto langle a_1,..., a_n-1rangle.$$ 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(langlerangle)=langlerangle$.
Next, we have the pointwise version of your $f$: $$g:omega^<omegarightarrowomega^<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(Clangle1,1,0rangle)=C(trunc(langle 1,1,0rangle))=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:mathcalP(omega^<omega)rightarrowmathcalP(omega^<omega): Smapstog(s): sin S.$$
OK, now here's the all-at-once definition: $f$ is the function from $mathcalP(omega^<omega)$ to $mathcalP(omega^<omega)$ which sends a set $X$ to the set
$$omega^ncdot s_n+1+omega^n-1cdot s_n+...+omega^0cdot s_1: exists t(omega^n+1cdot s_n+1+omega^ncdot s_n+...+omega^1cdot s_1+tin X).$$
answered Jul 21 at 19:20
Noah Schweber
111k9140261
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^2cdot 3mapsto1,omegacdot 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:ninmathbbN)=omega^n: ninmathbbN$ if I understand it correctly. Maybe you want to look at $mathcalP_fin(omega^<omega)$ - the set of finite sets of finite strings of naturals - instead of $mathcalP(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^<omegarightarrowomega^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,1rangle$ and $langle 1rangle$ 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^<omegasetminuslangleranglerightarrowomega^<omega: langle a_1,..., a_nranglemapsto langle a_1,..., a_n-1rangle.$$ 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(langlerangle)=langlerangle$.
Next, we have the pointwise version of your $f$: $$g:omega^<omegarightarrowomega^<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(Clangle1,1,0rangle)=C(trunc(langle 1,1,0rangle))=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:mathcalP(omega^<omega)rightarrowmathcalP(omega^<omega): Smapstog(s): sin S.$$
OK, now here's the all-at-once definition: $f$ is the function from $mathcalP(omega^<omega)$ to $mathcalP(omega^<omega)$ which sends a set $X$ to the set
$$omega^ncdot s_n+1+omega^n-1cdot s_n+...+omega^0cdot s_1: exists t(omega^n+1cdot s_n+1+omega^ncdot s_n+...+omega^1cdot s_1+tin X).$$
answered Jul 21 at 19:20
Noah Schweber
111k9140261
edited Jul 21 at 19:35
answered Jul 21 at 19:20
Noah Schweber
111k9140261
answered Jul 21 at 19:20
Noah Schweber
111k9140261
answered Jul 21 at 19:20
Noah Schweber
111k9140261
111k9140261
Thank-you. I can't believe something so easy to say "delete the smallest term of any ordinal (in Cantor normal form) and reduce the exponent of all other terms" is so difficult for me to work out how to write clearly.
– Robert Frost
Jul 21 at 19:24
One final thing... this always terminates on iteration, and... is it okay to call it a contraction mapping?
– Robert Frost
Jul 21 at 19:26
...PPS why do you have $C: omega^<omegarightarrowomega^omega$ rather than$C: omega^<omegarightarrowomega^<omega$?
– Robert Frost
Jul 21 at 19:27
2
@RobertFrost $C$ is the function that takes in a finite string and outputs the ordinal it names, so it's a map from $omega^<omega$ to $omega^omega$. As I explained, however, $f$ does not always terminate on iteration (unless you change $mathcalP(omega^<omega)$ to $mathcalP_fin(omega^<omega)$, that is, restrict the domain to finite sets of finite sequences), and since the term "contraction mapping" already has meaning, it would be incorrect to use it here, unless you establish that it does in fact fit that definition. I would call it a "truncation map," personally.
– Noah Schweber
Jul 21 at 19:36
P.s. re mapping to singletons and $s_1$, it maps sets of elements whose sequence is identical except for $s_1$ to singletons.
– Robert Frost
Jul 22 at 1:25
 |Â
show 1 more comment
Thank-you. I can't believe something so easy to say "delete the smallest term of any ordinal (in Cantor normal form) and reduce the exponent of all other terms" is so difficult for me to work out how to write clearly.
– Robert Frost
Jul 21 at 19:24
One final thing... this always terminates on iteration, and... is it okay to call it a contraction mapping?
– Robert Frost
Jul 21 at 19:26
...PPS why do you have $C: omega^<omegarightarrowomega^omega$ rather than$C: omega^<omegarightarrowomega^<omega$?
– Robert Frost
Jul 21 at 19:27
2
@RobertFrost $C$ is the function that takes in a finite string and outputs the ordinal it names, so it's a map from $omega^<omega$ to $omega^omega$. As I explained, however, $f$ does not always terminate on iteration (unless you change $mathcalP(omega^<omega)$ to $mathcalP_fin(omega^<omega)$, that is, restrict the domain to finite sets of finite sequences), and since the term "contraction mapping" already has meaning, it would be incorrect to use it here, unless you establish that it does in fact fit that definition. I would call it a "truncation map," personally.
– Noah Schweber
Jul 21 at 19:36
P.s. re mapping to singletons and $s_1$, it maps sets of elements whose sequence is identical except for $s_1$ to singletons.
– Robert Frost
Jul 22 at 1:25
Thank-you. I can't believe something so easy to say "delete the smallest term of any ordinal (in Cantor normal form) and reduce the exponent of all other terms" is so difficult for me to work out how to write clearly.
– Robert Frost
Jul 21 at 19:24
Thank-you. I can't believe something so easy to say "delete the smallest term of any ordinal (in Cantor normal form) and reduce the exponent of all other terms" is so difficult for me to work out how to write clearly.
– Robert Frost
Jul 21 at 19:24
One final thing... this always terminates on iteration, and... is it okay to call it a contraction mapping?
– Robert Frost
Jul 21 at 19:26
One final thing... this always terminates on iteration, and... is it okay to call it a contraction mapping?
– Robert Frost
Jul 21 at 19:26
...PPS why do you have $C: omega^<omegarightarrowomega^omega$ rather than$C: omega^<omegarightarrowomega^<omega$?
– Robert Frost
Jul 21 at 19:27
...PPS why do you have $C: omega^<omegarightarrowomega^omega$ rather than$C: omega^<omegarightarrowomega^<omega$?
– Robert Frost
Jul 21 at 19:27
2
2
@RobertFrost $C$ is the function that takes in a finite string and outputs the ordinal it names, so it's a map from $omega^<omega$ to $omega^omega$. As I explained, however, $f$ does not always terminate on iteration (unless you change $mathcalP(omega^<omega)$ to $mathcalP_fin(omega^<omega)$, that is, restrict the domain to finite sets of finite sequences), and since the term "contraction mapping" already has meaning, it would be incorrect to use it here, unless you establish that it does in fact fit that definition. I would call it a "truncation map," personally.
– Noah Schweber
Jul 21 at 19:36
@RobertFrost $C$ is the function that takes in a finite string and outputs the ordinal it names, so it's a map from $omega^<omega$ to $omega^omega$. As I explained, however, $f$ does not always terminate on iteration (unless you change $mathcalP(omega^<omega)$ to $mathcalP_fin(omega^<omega)$, that is, restrict the domain to finite sets of finite sequences), and since the term "contraction mapping" already has meaning, it would be incorrect to use it here, unless you establish that it does in fact fit that definition. I would call it a "truncation map," personally.
– Noah Schweber
Jul 21 at 19:36
P.s. re mapping to singletons and $s_1$, it maps sets of elements whose sequence is identical except for $s_1$ to singletons.
– Robert Frost
Jul 22 at 1:25
P.s. re mapping to singletons and $s_1$, it maps sets of elements whose sequence is identical except for $s_1$ to singletons.
– Robert Frost
Jul 22 at 1:25
 |Â
show 1 more comment
2
What do you mean with $mathcal P(omega^<omega)$ here?
– Wojowu
Jul 21 at 10:38
@Wojowu definitively I'm talking about $omega^<omega$ being the set of strings of positive integers of unlimited length but I'm pretty sure the ordinals I've given in Cantor normal form express this as the set of all ordinals less than $omega^omega$. Then $mathcal P(omega^<omega)$ is its power set.
– Robert Frost
Jul 21 at 11:27
There's one thing I know I'm not doing so well here, and that's for $f$ to be well-defined over over all of $mathcal P(omega^<omega)$ then I should probably better express how it will map certain sets to non-singletons
– Robert Frost
Jul 21 at 12:02
1
For any given set, are all the $s$'s except the first the same or do they and $b$ range over all of $Bbb N$? If $X$ were $1,2,3$ would the set have three elements with $b$ and the larger $s_i$ the same, or would it be all ordinals with the largest term having a coefficient of $1,2,$ or $3$? In any case it is not injective as $omega+1$ and $omega+2$ both go to $1$.
– Ross Millikan
Jul 21 at 14:15
@RossMillikan yes, sorry re injective that was silly. $f(omega+1,omega+2,omega+3,omega^2cdot3)=1,omegacdot 3$.
– Robert Frost
Jul 21 at 16:18