6
votes
1answer
323 views

What are $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$?

Sometimes reading on wikipedia or in this site (and in very different context like topology, arithmetic and logic) I have found these symbols $\Sigma _n^i$, $\Pi _n^i$ and $\Delta _n^i$. They are ...
2
votes
1answer
97 views

What would be arithmetic hierarchy of $\Sigma_1^0 \wedge \Pi_1^0$?

What would be arithmetic hierarchy of the form of formula like $\phi \wedge \psi$ where $\phi$ is $\Sigma_1^0$ and $\psi$ is $\Pi_1^0$? Prenex normal form seems to give me no answer for this.
1
vote
1answer
163 views

Formula of hierarchies - arithmetic hierarchy and analytical hierarchy

I am recently learning on these topics, and to help understand these things, it would be helpful if some examples of formula of various arithmetic hierarchies and analytical hierarchies are provided. ...
3
votes
1answer
146 views

Members of (lightface) Borel sets

I'm fairly certain this question has a very simple answer, and that I've learned it before; I just can't seem to remember it. Suppose I have a nonempty lightface Borel set $X\subseteq 2^\omega$. What ...
4
votes
2answers
258 views

Which are “big theorems” of descriptive set theory?

Question: If one were to fully understand 10 theorems in DST, or 15,20,25,30 theorems, which ones would be the most important to understand in order to work towards an understanding of descriptive set ...
6
votes
3answers
248 views

From lightface $\Sigma^1_1$ to boldface $\mathbf\Delta^1_1$

Fix some standard Polish space, e.g. Baire's space. It's a simple observation that every $\Delta^1_1$ is also $\mathbf\Delta^1_1$. It is the same observation that $\Sigma^1_1$ becomes ...
3
votes
0answers
81 views

An application of Descriptive set theory in Model theory.

In page 162 of D.Marker Model theory book he proved that the set $S_n(F,T)$ of all $F$-types realized by some $n$-tuple in some countable model of $T$ is analytic (this is with any $F$:= $countable$ ...
2
votes
1answer
70 views

Question about a defined function in D.Marker Model Theory book.

In page 162 of D.Marker Model theory book he proved that the set $S_n(F,T)$ of all $F$-types realized by some $n$-tuple in some countable model of $T$ is analytic (this is with any $F$:= $countable$ ...
10
votes
2answers
180 views

How does Borelness overlap with definability, computability, or constructiveness?

Background: I am writing a short paper aimed at math undergrads and focused as narrowly as possible on Borel equivalence relations. So, e.g., I am not assuming familiarity with recursion theory and am ...
3
votes
1answer
94 views

Borel linear order cannot have uncountable increasing chain

I am trying to make sense of what this theorem from C.I. Steinhorn, Borel Structures and Measure and Category Logics, says. Theorem 1.3.3. A Borel linear order cannot have an uncountable increasing ...
2
votes
2answers
131 views

Complexity of subset relation on Borel Sets

Fix $A, B \in \mathbf{\Delta}_{1}^{1}$ (i.e. they're Borel). Is the statement $A \subseteq B$ generally only $\mathbf{\Pi}^{1}_{1}$ (at best)? Of course, it's $\mathbf{\Pi}^{1}_{1}$ via $\forall x[x ...
0
votes
1answer
124 views

Simple Question about Borel Hierarchy

I'm a bit confused about the basics of the borel hierarchy. My question is this: if i have a closed set P and I make the set $\forall^\omega P$, is that $\Pi^0_3$? Similarly, if I have an open set P ...
3
votes
1answer
67 views

Analytic, Coanalytic space of functions

I'm having trouble showing that the set of differentiable functions on $[0,1]$ is coanalytic ($\mathbf{\Pi}_{1}^{1}$) and the set of continuously differentiable functions of $[0,1]$ is analytic ...
2
votes
1answer
450 views

Arithmetic hierarchy definition

From Wikipedia, Arithmetic hierarchy: The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted $\Sigma^0_n$ ...
4
votes
1answer
154 views

Projecting onto (lightface) Borel sets

Suppose $A \subseteq \omega^{\omega} \times \omega^{\omega}$ is Borel. If we project $A$ onto $\omega^\omega$, we get a $\mathbf{\Sigma^{1}_{1}}$ set $\{y: \exists x (y,x) \in A\}$. What if we project ...
8
votes
1answer
253 views

Definable order types without infinity axiom.

Denote by $ZF^\times$ the theory of $ZF$ without the axiom of infinity. We know that $V_\omega$, the set of all hereditarily finite sets in a model of $ZF$, is a model of $ZF^\times$. We further know ...
4
votes
1answer
115 views

Notation in Sacks' 'Higher Recursion Theory'

I'm having trouble with the notation in Sacks' Higher Recursion Theory. I've asked specific questions from page 4. Instead of reading my question in detail and trying to understand my confusion (which ...
4
votes
1answer
75 views

Determinacy of Negation of Class of Formula

First, this question is strictly in the context of Reverse Mathematics where various set comprehension and various axiom of choice may not be available. Question: Over $\text{RCA}_0$, if one has ...
11
votes
1answer
439 views

“Nice” well-orderings of the reals

I have a question which I believe could be easily resolved if I happened to look at the right source - hence my asking it here as opposed to at MathOverflow. I've tried googling it, but I haven't been ...
7
votes
2answers
190 views

Complexity of the set of computable ordinals

According to http://en.wikipedia.org/wiki/Analytical_hierarchy The set of all natural numbers which are indices of computable ordinals is a $\Pi^1_1$ set which is not $\Sigma^1_1$. However, "the ...
5
votes
3answers
503 views

Applications of descriptive set theory to mathematical logic?

The Wikipedia article Descriptive Set Theory asserts it has applications to logic, but gives no examples. Kechris' text Classical Descriptive Set Theory does not discuss logical applications, judging ...
5
votes
2answers
372 views

Does every infinite $\Sigma^1_1$ set have an infinite $\Delta^1_1$ subset?

The question is exactly that in the title: Does every infinite $\Sigma^1_1$ set of natural numbers have an infinite $\Delta^1_1$ subset? Some background: The lower-level analog of this question, Does ...