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
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, …
- 236k
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 …
- 236k
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
9
votes
Accepted
Do the Lebesgue-null sets cover "all the sets can naturally be regarded as sort-of-null sets"?
The answer is no, by a construction using the axiom of choice.
We shall build a counterexample set $A$ by a transfinite recursive
process of length continuum. At each stage, we shall promise that
cer …
- 236k
4
votes
Applications of infinite graph theory
A model of set theory $\langle M,\in\rangle$ is a certain kind of directed graph. So graph theory has the capacity to serve as a foundation of mathematics, having a copy of virtually any conceivable m …
- 236k
4
votes
Given a sequence of reals, we can find a dense sequence avoiding it, but can we find one con...
If you replace the reals $\mathbb{R}$ with Cantor space $2^{\mathbb{N}}$ or with Baire space $\mathbb{N}^{\mathbb{N}}$ (homeomorphic to the space of irrationals), then the answer is yes. Indeed, one c …
- 236k