Timeline for Intuition behind the non-Borel Lusin example
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 3, 2023 at 17:43 | comment | added | Will Brian | You're right. I meant something a little different from what I wrote: There is some $\alpha$ such that if $B$ is a $G_\delta$ set containing only well-founded relations, then $B$ cannot contain all relations of rank $<\alpha$ (and similarly for other classes beyond $G_\delta$). I don't suppose you know of any restrictions like this? | |
| Apr 3, 2023 at 17:32 | comment | added | Noah Schweber | @WillBrian Nothing like that can be true: consider a singleton whose element codes a really big ordinal. It's the lightface complexity, not topological complexity, that is essential here. | |
| Apr 3, 2023 at 17:30 | comment | added | Will Brian | OK, thanks. That makes sense, although it's not what I was hoping you meant. (I was hoping you were going to tell me something along the lines of: there is some $\alpha$ such that if $B$ is a $G_\delta$ set containing only well-founded relations, then $B$ contains no relations of rank $\geq \alpha$ (and similarly for other classes beyond $G_\delta$).) | |
| Apr 3, 2023 at 16:44 | comment | added | Noah Schweber | @WillBrian It's just $\Sigma^1_1$-bounding relativized to the Borel code. Suppose $\sigma$ is a real coding a Borel set $B_\sigma$ which contains only (reals that represent) well-founded relations. Let $\alpha$ be the least $\sigma$-noncomputable ordinal. If any well-ordering of ordertype $\ge\alpha$ were in $B_\sigma$, we would be able to determine which $\sigma$-computable linear orders are well-orders in a $\Sigma^1_1$-in-$\sigma$ way, namely by asking whether the order in question embedded into some element fo $B_\sigma$. This can't happen, by (relativized) $\Sigma^1_1$ bounding. | |
| Apr 3, 2023 at 13:03 | comment | added | Will Brian | Noah, I'm curious what exactly you mean by this: "The point is that Borel sets have a kind of "overspill" property: sets of fixed Borel rank that contain reals coding well-founded relations of too high rank, also contain reals coding ill-founded relations." Is there someplace I can read a more precise version of this statement? | |
| Nov 3, 2016 at 15:10 | vote | accept | Jon-S | ||
| Nov 3, 2016 at 14:28 | comment | added | Noah Schweber | "The sequence $f$ must not begin "$110$" (that is, Yes Yes No)." That is, $(*)$ says that $f$ must not lie in the open set generated by "$110$", so $(*)$ corresponds to a closed set! More generally, each "small" requirement says something about what finitely many bits of $f$ can't be - and it's a good exercise to show that any such requirement corresponds to a small set. Being a linear order is determined by universal statements "$\forall a, b$...". These correspond to intersections, and atomic formulas like "$aRb$" are clopen. So being a linear order is an intersection of clopens: closed. | |
| Nov 3, 2016 at 14:24 | comment | added | Noah Schweber | Now, these are three "big" requirements, but they split into countably many "small" requirements - like $$\mbox{$(*)$ "If $(2, 5)\in R$ and $(5, 631)\in R$, then $(2, 631)\in R$".}$$ Since intersections of closed sets are closed, it's enough to show that each individual requirement of this form corresponds to a closed set - for example, we want that the set of $f\in 2^\omega$ coding an $R$ satisfying $(*)$ from above is closed. Well, $(*)$ is a condition on bits: suppose $\langle 2, 5\rangle=0$, $\langle 5, 631\rangle=1$ and $\langle 2, 631\rangle=2$ for simplicity. Then $(*)$ says (contd) | |
| Nov 3, 2016 at 14:21 | comment | added | Noah Schweber | Now, as to why $S_{linear}$ is closed, this is a nice argument. What does a real $r$ have to do to be in $S_{linear}$? Well, first let's think about what a relation $R$ on $\mathbb{N}$ has to do to be a linear order. We need: (1) if $(a, b)\in R$, then $(b, a)\not\in R$ (I'm thinking of $R$ as "$<$" rather than "$\le$", here). (2) If $(a, b)\in R$ and $(b, c)\in R$, then $(a, c)\in R$. (3) For all $a\not=b$, either $(a, b)\in R$ or $(b, a)\in R$. (cont'd) | |
| Nov 3, 2016 at 14:19 | comment | added | Noah Schweber | @Jon-S Borel sets work the same way in $2^\omega$ - the topology is slightly different, but the Borel sets are constructed in the same way from it. (In case you're not aware: the topology on $2^\omega$ is generated by basic clopen sets of the form $\{f\in 2^\omega: \sigma\prec f\}$ for $\sigma$ a finite binary string. So, e.g., the set of all infinite binary strings beginning "$01001$" is open and closed in $2^\omega$. More generally, if I have a tree $T\subseteq 2^{<\omega}$ of finite binary strings, the set of paths through $T$ is closed; and every closed set has this form.) (cont'd) | |
| Nov 3, 2016 at 14:05 | comment | added | Jon-S | ... Basically, I "feel" (intuitively) that a Borel is something that can be constructed by iteration of a process of the form : take countable unions or intersections of sets built from taking countable unions or intersections of sets built from... (etc.) ...from open or closed sets of $\mathbb{R}$. When we work with $2^\omega$ instead, I kind of lose my (topological) intuition. For example, I don't "see" why $S_{linear}$ is closed. | |
| Nov 3, 2016 at 14:01 | comment | added | Jon-S | Thank you for your answer, it helps giving a better idea of what is behind. I think that the difficulty I have to understand intuitively the failure of being Borel starts early in the argument. I have only a very basic intuition of being Borel, which is based on the topology of $\mathbb{R}$. | |
| Nov 3, 2016 at 2:48 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 186 characters in body
|
| Nov 3, 2016 at 2:46 | comment | added | Noah Schweber | @AndreasBlass Dangit! Of course you're right, I was typing too fast. Fixed. | |
| Nov 3, 2016 at 2:34 | comment | added | Andreas Blass | Unless I overlooked a negation somewhere in the definitions, $S_{WF}$ is not analytic but co-analytic. | |
| Nov 3, 2016 at 2:16 | history | answered | Noah Schweber | CC BY-SA 3.0 |