Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with descriptive-set-theory
Search options answers only
not deleted
user 14340
Descriptive Set Theory is the study of definable subsets of Polish spaces, where definable is taken to mean from the Borel or projective hierarchies. Other topics include infinite games and determinacy, definable equivalence relations and Borel reductions between them, Polish groups, and effective descriptive set theory.
1
vote
Hyperarithmetically least elements in $\Pi^1_1$ sets
It is well known that there is a nonempty $\Pi^0_1$ set $A\subseteq \omega^{\omega}$ containing no hyperarithmetic member.(Considering a $\Sigma^1_1$ set without a hyperarithmetic member, it is a proj …
- 4,201
2
votes
Intersection of (relativized/preimage) measure 0 with every hyperarithmetic perfect set
The answer is no.
Let $X$ be any nonempty $\Delta^1_1$ set without hyperarithmetic member. Now suppose that $T$ is a $\Delta^1_1$-perfect tree. So there is a hyperarithmetic homeomorphism $f:[T]\to 2^ …
- 4,201
4
votes
Accepted
$\Pi^0_2$ singleton forming minimal pair with $0''$
Maybe I should give a more detailed answer.
Harrington proved (or claimed) the following result in his handwritten draft.
Theorem There is a $\Pi^0_2$-singleton $x$ so that $\forall n<\omega (x^{(n)} …
- 4,201
2
votes
A Borel perfectly everywhere surjective function on the Cantor set
I think that recursion theory gives a clearer way to answer the question. If $f$ is a Borel function, then it is a hyperarithmetic reduction relative to a real, say $x$. Then fix any "regular" forcin …
- 4,201
1
vote
Borel hierarchy and tail sets
Here is an example: Let $A=\{0,1\}$ and for any $x\in \{0,1\}^{\omega}$, let $n<_x m$ if $x(2^n\cdot 3^m)=1$. For any countable ordinal $\alpha$, let $x\in U_{\alpha}$ if there is some $l$ so that $ …
- 4,201
1
vote
Accepted
The measure of ideals generated by random reals
The question has a negative answer. The technique is essentially due to Jockusch and Posner.
Proof: Let $x$ be a real in which every constructible real is recursive. Now $$A=\{r\mid r\mbox{ is Mar …
- 4,201
2
votes
Regularity properties of Turing-invariant and arbitrary sets of reals
Here is not an answer but an example:
Let PSP be the statement that every uncountable set of reals has a perfect subset and TPSP that every uncountable set of Turing degrees has a perfect subset.
Th …
- 4,201
0
votes
Accepted
A partial relativization of Gandy's basis theorem
Hmmm, it seems the answer to the question is no.
Fix any nonhyperarithmetic real $x$ so that the $\Sigma^1_1(x)$ set $$A_x=\{y\mid \forall n \in \mathscr{O} ( x\not\leq_T y^{(|n|)})\}$$ is not empty, …
- 4,201
10
votes
Is it known how the Sigma Algebra generated by Jordan measurable sets compares to universall...
Here is an answer to your question.
Assume $V=L$, there is a null $\Pi^1_1$-set which is not in $\sigma(J)$.
Proof: Let $A=\{x\mid x\in L_{\omega_1^x}\}$ be the $\Pi^1_1$-null set. Now suppos …
- 4,201
3
votes
$\Delta^{1}_{2}$ and degrees of constructibility $\textbf{on sets}$
Here is a partial positive answer: i.e. either $A$ or $\bar{A}$ contain elements of all degrees of constructibility of reals.
Given an infinite set of numbers $x$, let $f:\omega\to \omega\cup \{x\} $ …
- 4,201
3
votes
Is there a Borel subset of $ \mathbb{R}^{2} $, with finite vertical cross-sections, whose pr...
There is a pure recursion theoretical proof of the result. The idea is as follows: By Spector-Gandy theorem, a lightface Borel set $(x,y)$ is an r.e set over $L_{\omega_1^{CK}}[x,y]$. If there are at …
- 4,201
4
votes
Vitali Sets vs Bernstein Sets...
For your second definition of Vitali set, I have a weak partial answer. Namely the existence of a Bernstein set does not imply the existence of a $T$-Vitali set. The answer can be found in logic blog …
- 53.3k
4
votes
Accepted
Degree of unsolvability of finding a open approximation to a Borel set, given its Borel code
I think this is a well known fact.
For example, let $\alpha$ be a recursive ordinal and $B=\{g\mid g\mbox{ is a }0^{(\alpha)}\mbox{-generic real}\}$. Then $B$ is a hyperarithmetic set and so has a re …
- 4,201
6
votes
Borel cross section
There is a recursion theory method which is quite similar to Samuel's.
By a classical recursion theory result, there is a recursive functional $F$ so that for any $x\in \omega^{\omega}$, $F(x)$ code …
- 4,201
4
votes
Accepted
Analytic uniformization
There is an arithmetical set $A\subseteq 2^{<\omega}\times \omega^{<\omega}$ so that for any $x\in 2^{\omega}$, $A(x)=\{\sigma\mid \exists n(x|n,\sigma)\in A\}$ is an $x$-recursive tree which has an i …
- 4,201