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 not deleted
user 1946
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.
12
votes
Accepted
What is the least $\alpha$ such that $L_\alpha$ contains a non-measurable set
The question makes the most sense if we assume $V=L$, since otherwise it could be that every set of reals in $L$ is countable and hence measurable.
If $V=L$, the answer is $\omega_1+1$. Every set in $ …
- 236k
19
votes
Examples of concrete games to apply Borel determinacy to
The game of infinite Hex, proceeding from an arbitrary position, is a good example with all the features you seek. The game was the subject of my Oxford student Davide Leonessi's masters MFoCS dissert …
- 236k
27
votes
Accepted
Writing a function on $\mathbb{R}$ as a sum of two injections
The answer is yes. Every function on the reals is the sum of two injective functions, and this can be done in a highly effective manner, constructing the two functions $g,h$ from $f$ without any need …
- 236k
3
votes
Conflating reals and sets of countable ordinals "nicely"
Here is another way to answer, which builds a bi-interpretation between $H_{\omega_1}$ and $H_{\omega_2}$, rather than just the power sets, and this is a very nice connection indeed. Meanwhile, the po …
- 236k
92
votes
3
answers
14k
views
Is every sigma-algebra the Borel algebra of a topology?
This question arises from the excellent question posed on math.SE
by Salvo Tringali, namely, Correspondence
between Borel algebras and topology.
Since the question was not answered there after some ti …
26
votes
Quantifier complexity of the definition of continuity of functions
It is truly a very nice question, one of those questions with an answer one feels must be right, but it is not so clear at first how to prove it.
Nevertheless, aiming at partial progress, I claim that …
- 236k
24
votes
2
answers
1k
views
What is the complexity of the winning condition in infinite Hex? In particular, is infinite ...
Consider the game of infinite Hex, where two players Red and Blue alternately place their stones on the infinite hex grid, each aiming to create a winning configuration.
Red wins after infinite play, …
- 740
49
votes
0
answers
3k
views
Concerning proofs from the axiom of choice that ℝ³ admits surprising geometrical decompositi...
This question follows up on a comment I made on Joseph O'Rourke's
recent question, one of several questions here on mathoverflow
concerning surprising geometric partitions of space using the axiom
of …
- 12.9k
8
votes
When is $A$ "$L$-ish" whenever $B$ is "$L$-ish"?
This is a fascinating question! I really like your relation.
Here is some small progress. (I am hopeful that more definitive answers will appear later).
First, you didn't mention it, but for definiten …
- 20.5k
9
votes
1
answer
603
views
Does every cofinal branch through Kleene's O compute true arithmetic?
My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides
ordinal denotations for any desired c …
- 3,073
1
vote
Source on smooth equivalence relations under continuous reducibility?
This is more of a comment than an answer, since it is not a perfect fit. But I just thought I would mention the following paper, which is concerned not with continuous reducibility, but computable red …
- 236k
11
votes
Examples of statements with a high quantifier complexity
Consider the statement:
"Neither player has a winning strategy in the game of Tic-tac-toe."
This is a natural statement, often asserted and believed, and the most natural formulation of it has com …
- 236k
25
votes
Accepted
How (non-)computable is set theory?
The question is extremely interesting, and I have looked into this kind of thing with various colleagues (including Russell Miller and Kameryn Williams), although our investigation has not yet resulte …
- 236k
6
votes
Accepted
Nice arrangement of open sets in $\sigma$-algebras
Not necessarily. Let $X$ be an uncountable set with the discrete topology, and let $\mathcal{E}$ be the collection of singletons, which is a base for the topology, since every set is a union of single …
- 236k
4
votes
Products and Gale-Stewart games
It is a very nice question.
I claim that it is not sufficient that $C$ is determined, and indeed, there
are counterexamples where $C$ is a game with only two moves.
Consider the two-dimensional gam …
- 236k