Timeline for Order type of the smallest set containing the identity function and closed under exponentiation
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| May 23, 2013 at 1:51 | comment | added | George Lowther | @Joel: I added an answer with my construction of the order isomorphism now. | |
| May 23, 2013 at 0:59 | comment | added | Vladimir Reshetnikov | It is difficult to imagine any plausible candidate below $\epsilon_0$ because they all have a non-self-referential representation in the Cantor normal form, i.e. basically are exponential polynomials. So why it would be an $\alpha$ rather than, say, $\omega^\alpha$? | |
| May 23, 2013 at 0:53 | comment | added | Joel David Hamkins | George, please go ahead if you'd like to! Otherwise, I'll be happy to do it. | |
| May 23, 2013 at 0:51 | comment | added | George Lowther | I can add another answer fleshing this out | |
| May 23, 2013 at 0:32 | comment | added | Joel David Hamkins | I see; this is the percolation-upward idea that I had imagined.... | |
| May 23, 2013 at 0:30 | comment | added | George Lowther | @Joel: My idea is to use the fact that $(n^{n^i})^{n^{n^j}}=n^{n^{i+n^j}}$. Now define $F$ to be the smallest subset of $\mathbb{N}^\mathbb{N}$ containing the 0 function and, whenever it contains $f,g$ then it contains $f+n^g$. Then $E$ is just the set of functions of the form $n^{n^f}$ for $f\in F$. The order isomorphism between $F$ and $\epsilon_0$ is a little bit clearer than for $E$ and $\epsilon_0$. | |
| May 23, 2013 at 0:23 | comment | added | Joel David Hamkins | George and Steven, I have to think about what you write, but I am worried about the lack of $+$ in this algebra. At first, I had agreed that it should obviously be $\epsilon_0$, but it seems difficult to get a robust ordinal representation without using $+$. | |
| May 23, 2013 at 0:13 | comment | added | George Lowther | ...and I claim that this gives an order isomorphism between $\epsilon_0$ and $E$. | |
| May 23, 2013 at 0:10 | comment | added | George Lowther | Define a map $\theta$, say, from $\epsilon_0$ to $\mathbb{N}^\mathbb{N}$ as follows. Take 0 to the 0 function. Then every ordinal $\alpha < \epsilon_0$ can be written as $\omega^\beta+\gamma$ for ordinals $\beta,\gamma < \alpha$. Write $\theta(\alpha)(n)=n^{\theta(\beta)(n)}+\theta(\gamma)(n)$. Transfinite induction defines $\theta\colon\epsilon_0\to\mathbb{N}^{\mathbb{N}}$. Now map to the set $E$ by taking an ordinal $\alpha$ to the function $n\mapsto n^{n^{\theta(\alpha)(n)}}$. | |
| May 23, 2013 at 0:08 | comment | added | Steven Stadnicki | Likewise, if we have an expression of the form $n^{n^{f(n}}$ then by exponentiating by $n^{g(n)}$ we get $\left(n^{n^{f(n)}}\right)^{\left(n^{g(n)}\right)} = n^{\left(n^{f(n)}\cdot n^{g(n)}\right)} = n^{n^{(f(n)+g(n))}}$, so on the second level of exponential if we have expressions of the form $f(n)$ and $g(n)$ we can generate an expression of the form $f(n)+g(n)$ (and in particular, we can generate $f(n)+1$). This should be enough to generate all ordinals $\lt\epsilon_0$. | |
| May 23, 2013 at 0:06 | comment | added | Steven Stadnicki | It seems like it's easy to embed all the ordinals less than $\epsilon_0$ in this ordering, because by taking a 'virtual logarithm' we essentially shunt exponentiation is shunted down to multiplication, and by taking another multiplication is shunted down to addition. $(n^{f(n)})^n = n^{n\cdot f(n)}$ so if we can 'generate' an expression of the form $f(n)$ in an exponent then we can generate an expression of the form $n\cdot f(n)$. (continued next comment :-) | |
| May 23, 2013 at 0:03 | comment | added | George Lowther | Looks to me that it is of ordinal type $\epsilon_0$. | |
| May 22, 2013 at 23:49 | history | undeleted | Joel David Hamkins | ||
| May 22, 2013 at 23:49 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 585 characters in body; added 38 characters in body; deleted 5 characters in body; added 8 characters in body
|
| May 22, 2013 at 23:33 | history | deleted | Joel David Hamkins | ||
| May 22, 2013 at 23:31 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |