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 8133
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.
5
votes
Accepted
Descriptive set theoretic complexity of computable maps with respect to the Turing jump of t...
Every such set is both $F_\sigma$ and $G_\delta$, i.e. ${\bf \Delta^0_2}$.
The clear upper bound is that $Y$ is in $Z$ iff for some finite string $\sigma$ such that $\{a\}^\sigma(0)\downarrow=0$ we ha …
- 20.6k
12
votes
Examples of concrete games to apply Borel determinacy to
Here are four, of various different flavors:
A silly one
I described in a different MO question a game where players work together to turn the harmonic series into an alternating (so conditionally co …
- 20.6k
3
votes
Quantifier complexity of the definition of continuity of functions
The following should really be a comment rather than an answer, but it's too long:
Continuity is rarely $\exists^*$ or $\forall^*$ characterizable.
Specifically, consider the following two properties …
- 20.6k
1
vote
Non-analytically measurable set in $\Delta^1_2$
You write:
I can prove that such a set exists but just wondering if there's a (fairly) concrete example.
The following might just be the proof you allude to, but I think it is fairly concrete:
A set …
- 20.6k
3
votes
Accepted
A continuous map relating co-constructible reals
By "formula" I will mean "formula of set theory with ordinal parameters." Note that "ordinal parameters" is equivalent to "constructible parameters" for our purposes, since $L$ carries a definable bij …
- 20.6k
1
vote
Accepted
Reference request: a version of $\Sigma^1_1$ bounding for structures
After asking around for a while, it appears that there is no prior reference for this fact. I'm posting and accepting this answer to move this question off the unanswered list. That said, if anyone do …
- 20.6k
4
votes
Accepted
$\mathtt{PSP}$ implies the consistency of inaccessible cardinals
See Proposition 11.5 (and the discussion leading up to it) in Kanamori's book The Higher Infinite. Note that Kanamori states the result a bit more optimally: if $M\models\mathsf{ZF}$ + "$\omega_1$ is …
- 20.6k
4
votes
Games that never begin
A slightly more tangential answer, but one which I hope is still useful: there is a well-known connection between infinite games and infintary logic. In the usual context of games with no ending, dete …
- 1,446
7
votes
Accepted
What sets can be unraveled?
I emailed Itay Neeman, and he told me the following:
As far as I know it's open. I don't think anything is known about
unraveling beyond what you can get from my methods. These give the
Suslin operat …
- 20.6k
8
votes
Accepted
A submodel of set theory with all reals which every set is analytic
In fact, the principle "Every set is analytic" is not consistent with $\mathsf{ZF}$ in the first place. We don't need choice to get a surjection $h$ from Baire space to the set of continuous maps on B …
- 20.6k
0
votes
When does an "$\mathbb{R}$-generated" space have a short description?
This should be a comment, but it's too long - here's a $\mathsf{ZFC}+\mathsf{CH}$ example:
Let $\mathfrak{F}$ be the set of full-measure subsets of $\mathbb{R}$ (we could also take the set of non-mea …
- 20.6k
13
votes
Accepted
Descriptive set theory for computer scientists?
For the last point, besides texts explicitly on computability-theoretic descriptive set theory (e.g. the hard-to-find Mansfield-Weitkampf, the freely-accessible section $3$ of Moschovakis' book, or th …
- 20.6k
2
votes
Accepted
"Robinson arithmetic" for (some) levels of $L$?
EDIT: to my chagrin, the notion of "$n$-admissibility" is not what I thought it was! What I wanted was $\Sigma_n$-admissibility. You can find the definition of $n$-admissibles here; they are vastly sm …
- 20.6k
0
votes
Accepted
Detecting comprehension topologically
Statements about existence of $\omega$-models can be topologically detected.
Specifically, fix $X$ a Turing ideal. For $t\in X$ say that $t$ enumerates a family of sets if:
Exactly one $p\in c_X(t) …
- 20.6k
7
votes
Accepted
Can it be that universal measurability is preserved by projections?
I'm not an expert, so please correct me if I'm wrong:
We can indeed continue the projective hierarchy beyond its finite levels. And like the Borel hierarchy, we can do this "from below" as follows: …
- 20.6k