Timeline for Big O notation and the maximal set of comparable functions
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2010 at 14:54 | comment | added | Joel David Hamkins | But the point is that a continuum-indexed family will have a cofinal countable subset, and Yuval's argument can get above it, contradicting maximality. So no continuum-parameterized family can be maximal, if increasing the parameters makes the function higher in the order. In my answer, I tried to explain how this is not just about fast-growing functions, but pervasive in every local region of the order, since countable cuts can always be filled. | |
| Nov 10, 2010 at 10:15 | comment | added | Piotr Migdal | Uncountability says nothing about explicit construction (it need not to be recursive). For example $x^\alpha$ (for $\alpha\in\mathbb{R}$) form a uncountable set. Thanks for link to 'fast-growing hierarchy'. | |
| Nov 10, 2010 at 4:47 | history | answered | Yuval Filmus | CC BY-SA 2.5 |