Timeline for Big O notation and the maximal set of comparable functions
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Nov 14, 2010 at 22:16 | comment | added | Joel David Hamkins | Andreas, great! You should post this as an answer. | |
| Nov 14, 2010 at 21:07 | comment | added | Andreas Blass | There is no Borel (or even analytic) maximal chain. Kechris and Saint-Raymond proved (independently) that any analytic subset A of $\omega^\omega$ either (1) is bounded in the "smaller on a cofinite set" order or (2) includes all the branches of some superperfect tree (= Miller tree). In case (1) one easily gets a strict upper bound in the "big O" ordering, so A can't be a maximal chain. In case (2), it's easy to check that A can't be a chain at all. (I'm rather embarrassed not to have remembered the theorem of Kechris and Saint-Raymond in the first place, since I've often cited it.) | |
| Nov 11, 2010 at 0:15 | comment | added | Joel David Hamkins | Well, I haven't been able to make that idea work out. Do you know how to ruin a Borel maximal linear subfamily by forcing? I think that your version of the question---whether there is a Borel maximal linear chain---is the best way to take the question. Perhaps this should be asked as a separate question... | |
| Nov 10, 2010 at 17:38 | comment | added | Joel David Hamkins | I think perhaps there can't be, since if $b$ is the Borel code for it, then the assertion that $b$ is the code of a maximal Borel chain is $\Pi^1_1$ and hence absolute to forcing extensions. But it seems that we can ruin this possibility by forcing to make the bounding number intermediate in a model where $\omega_1^L$ is also collapsed. Doesn't this rule out such Borel orders in the extension by the Mansfield-Solovay theorem? If so, then there couldn't have been a Borel order to begin with. (But I'm not sure if this all works.) | |
| Nov 10, 2010 at 17:25 | comment | added | Andreas Blass | Is it known that there can't be a Borel maximal chain in this preorder? | |
| Nov 10, 2010 at 12:21 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |