4
votes
0answers
120 views

$\infty$-Borel Determinacy?

An $\infty$-Borel set is a set $X\subseteq\mathbb{R}$ which has an $\infty$-Borel code - a set $r$ coding the construction of $X$ via open sets, complementation, and well-ordered unions (see ...
14
votes
2answers
391 views

Pathological behavior of Borel sets?

Usually in set theory, Borel sets are much more nicely behaved than arbitrary sets of reals. One reason for this is Borel determinacy, which immediately yields measurability, Baireness, and the ...
4
votes
1answer
199 views

Perfect set property implies $\omega_1$ is a limit cardinal in $L$

Specker proved in 1957 that if in $V$ every set of real numbers has the perfect set property, than in $L$, $\omega_1^V$ is actually a limit cardinal. The original proof is in German, and I've been ...
5
votes
1answer
203 views

A model of Krivine

In a paper by J.-L. Krivine, Modèles de ZF+AC dans lesquels tout ensemble de réels définissable en termes d'ordinaux est mesurable-Lebesgue [C. R. Acad. Sci. Paris Sér. A-B 269 (1969), A549–A552, ...
9
votes
1answer
173 views

Obtaining a lightface pointclass from a boldface one

Define a pointclass to be: boldface inductive-like if it is $\mathbb{R}$-parameterized, has the scale property, and is closed under $\wedge$, $\vee$, $\forall^\mathbb{R}$, $\exists^\mathbb{R}$, and ...
2
votes
0answers
149 views

How many Dedekind-finite sets can $\mathbb{R}$ be partitioned into?

Building off Asaf Karagila's answer to my previous question (Can $\mathbb{R}$ be partitioned into dedekind-finite sets?) on partitioning $\mathbb{R}$ into strictly Dedekind-finite sets: (1) What ...
-1
votes
1answer
150 views

Algebra generated by a tree [Edit] [closed]

Suppose that $(T,\leq)$ is a partially ordered set, we say $T$ is a tree* if for every $i\in T$, $\{s: s\in T, s\leq t\}$ is a well-founded chain. What I need to know is: Can the algebra ...
8
votes
1answer
221 views

Can $\mathbb{R}$ be partitioned into dedekind-finite sets?

Assuming $ZF$ itself is consistent, it is consistent that there are sets $D$ which are infinite but cannot be placed in bijection with any of their proper subsets; such sets are called "strictly ...
6
votes
1answer
362 views

Is there a suitably generalized Baire property for topological spaces of arbitrary cardinalities?

Is there some suitable generalization to the notion of Baire property for topological spaces of arbitrary cardinalities which satisfies the following condition: The meager sets are sets which are ...
5
votes
1answer
238 views

Failure of Shoenfield's Absoluteness

Shoenfield's absoluteness states that if $M \subseteq N$ are models of $ZF$ and $M \supseteq \omega_1^N$, then every $\Sigma^1_2$ formula with parameters in $M$ is absolute between $M$ and $N$. In ...
9
votes
0answers
190 views

Are there trees for $(\Sigma^2_1)^{\text{uB}}$?

If there is a proper class of Woodin cardinals, then Woodin showed (using stationary towers) that $(\Sigma^2_1)^{\text{uB}}$ statements are generically absolute, where $\text{uB}$ denotes the ...
7
votes
2answers
190 views

Natural $\Pi^1_2$ (or worse) classes of structures?

(To clarify, my interest is mainly lightface, that is, $\Pi^1_2$ instead of $\bf \Pi^1_2$, although it doesn't particularly matter.) This is just an idle curiosity. In logic, I find myself frequently ...
5
votes
1answer
175 views

Is the consistency of $\mathcal{L}_{\infty\omega}$-sentences absolute?

The question is exactly that of the title. Suppose $\varphi\in V$ is an $\mathcal{L}_{\infty\omega}$-sentence, and $W$ is an inner model of $V$ such that $\varphi\in W$. Is the statement ...
10
votes
1answer
151 views

n odd: $\bf\Delta^1_n$ wadge degrees are $< \bf\delta^1_{n+1}$

My adviser is out of town and there is a comment in the Van Wesep paper "wadge degrees and descriptive set theory" that I can't figure out. Work in ZF+AD throughout. As stated in the title, the ...
9
votes
1answer
255 views

Universal $(\Sigma^2_1)^{\text{Hom}_{\mathord{<}\lambda}}$ set

Does anyone know of a reference for the fact that if $\lambda$ is a limit of Woodin cardinals, then the pointclass $(\Sigma^2_1)^{\text{Hom}_{\mathord{<}\lambda}}$ is $\omega$-parameterized? By ...
9
votes
1answer
272 views

Concerning Silver's result

Jack Silver proved that if $x$ is a real so that every $x$-admissible ordinal is a cardinal in $L$, then $0^{\sharp}$ exists. I wonder whether various weaker or stronger versions of Silver's result ...
5
votes
2answers
220 views

Does the boldface class $\Delta^1_2$ have the uniformization property? (assuming $V=L$)

DISCLAIMER: All pointclasses considered here are boldface. Most of the time, when doing descriptive set theory, we want the projective sets to "behave well;" for example, maybe we don't want there to ...
3
votes
1answer
146 views

Is the ideal of compact operators strongly Borel?

Let $H$ be a separable infinite dimensional Hilbert space. Denote by $\mathcal{B}(H)$ the space of bounded operators on $H$, and $\mathcal{K}(H)$ the ideal of compact operators. When endowed with the ...
5
votes
1answer
213 views

Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?

Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where $\phi$ contains no ...
3
votes
2answers
298 views

Cohen algebra (generalization)

Let Bor($X$) = class of all borel subsets of $X$. Cohen algebra is defined as Bor(X) modulo the ideal of meager sets. The Cohen algebra has a combinatorial : it is the unique atomless complete ...
20
votes
0answers
770 views

Godel on recursion-theoretic hierarchies

At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes: "Another mathematical eternal return: Toward the end of his ...
3
votes
1answer
147 views

Complexity of winning strategies for open games (for open player)

If $G\subseteq\omega^{<\omega}$ is a computable clopen game, then $G$ has a winning strategy which is hyperarithmetic $(\Delta^1_1)$, by an inductive ranking process. The key observation here is ...
4
votes
1answer
157 views

When do substructures have computable copies?

Say that a class $\mathcal{C}$ of countable first-order structures in some finite signature has the effective substructure property if $\mathcal{C}$ is closed under isomorphism and whenever $A\in ...
9
votes
1answer
176 views

Ensuring nonempty lightface Borel sets have elements via theories of second-order arithmetic

This question is an outgrowth of this MathSE question: http://math.stackexchange.com/questions/276068/members-of-lightface-borel-sets. A Borel set $X\subseteq 2^\omega$ is a member of the smallest ...
4
votes
1answer
372 views

Definition of HYP in $L_{\omega_1^{CK}}[a]$?

The structure $L_{\omega_1^{CK}}$ consists of only HYP sets (I believe) and HYP in this structure is the same as the actual hyperaritmetic sets. Now if I move to the structure $L_{\omega_1^{CK}}[a]$ ...
6
votes
0answers
165 views

$\omega$-models of $\mathbf{\Sigma^1_1}-DC$ and $\mathbf{\Delta^1_1}-CA$

So what is needed to demonstrate something (say like $L_{\omega_1^{CK}}[a]$ is a $\omega$-models of $\mathbf{\Sigma^1_1}$-$DC$ or $\mathbf{\Delta^1_1}$-$CA$? It's not like I don't understand what the ...
5
votes
0answers
325 views

Proof of “AD + every set of reals is Suslin” implies AD$_\mathbb{R}$

Could someone point me toward a proof that "ZF + AD + every set of reals is Suslin" (+ $\mathsf{DC}\_\mathbb{R}$?) implies $\mathsf{AD}\_\mathbb{R}$, either with a reference or a hint? I am ...
6
votes
1answer
259 views

Determinacy and definable ultrafilters

It is a simple consequence of AD that there are no non-principal ultrafilters on $\omega$: for $U$ an ultrafilter on $\omega$, consider the game $G_U$ where players I and II play natural numbers $x_0$ ...
10
votes
1answer
212 views

Which forcings preserve (some) determinacy?

The question is exactly as in the title. I'm interested in general in all questions of the form "which forcings preserve property P?" for any P, but determinacy assumptions occupy a special place in ...
5
votes
0answers
181 views

Infinity-Borel sets in ZFC

The notion of an $\infty$-Borel set of reals is useful in the study of AD. Under ZFC it becomes trivial: every set of reals is $\infty$-Borel. However, the notion of an $\infty$-Borel code is still ...
8
votes
0answers
449 views

Existence (or non) of “definable” ultrafilters

This is a question which I suspect has an absurdly easy answer, but I'm not seeing it. Let $\langle\cdot,\cdot\rangle:\omega^2\rightarrow\omega$ be your favorite pairing map (for me, this is the ...
9
votes
1answer
430 views

Constructing an injective reduction of equivalence relations

[Metastuff: I asked this question in a slightly different way on mathSE last week, and it didn't go anywhere, which is why I am asking here. I added the DST tag because it's basically a problem about ...
5
votes
1answer
193 views

Companion of the pointclass of inductive sets

This question is about the notion of a companion for a Spector class, as defined in Moschovakis's book Elementary Induction on Abstract Structures. I am interested in Spector classes on $\mathbb{R}$, ...
3
votes
1answer
208 views

sigma-algebra generated by OD sets

Assume $V=L(\mathbb{R})$ and the Axiom of Determinacy. Is every set of reals generated by ordinal-definable sets of reals under the operations of countable union and intersection? The class of sets ...
6
votes
2answers
299 views

Weakly homogeneous trees under AD

If AD$_\mathbb{R}$ holds and $\kappa < \Theta$ then every tree $T$ on $\kappa$ is weakly homogeneous (Martin–Woodin, "Weakly homogeneous trees.") I recall hearing that the hypothesis can be ...
5
votes
0answers
321 views

Sets of reals amenable to each L[x]

If $A$ is a set of reals such that $A \cap L[x] \in L[x]$ for each real $x$, is there a real $z$ such that $A \cap L[x] \in OD_z^{L[x]}$ for a cone of $x$? This can be proved under the Axiom of ...
0
votes
1answer
173 views

Trees on $\omega$

I am going to give a construction of a tree on $\omega$ that at first appears as though it is well founded. However, this tree cannot be well-founded because, using the rank function on finite ...
6
votes
3answers
574 views

About the axiom of choice, the fundamental theorem of algebra, and real numbers

About fundamental theorem of algebra, there is a large collection different demonstrations. I ask: is there some proof that avoids AC (choice axiom)? In a general topos (with natural number object) ...
3
votes
1answer
216 views

Indeterminacy of long games

Hello, all, Several months ago I sat in on a seminar on AD+, which was incredibly wonderful even though I could barely follow it at all. AD+ is a technical variant of AD, the axiom of determinacy, ...
10
votes
1answer
413 views

How badly does compactness fail in $\mathcal{L}_{\omega_1\omega}$?

I would like to get a better idea of how badly compactness fails in $\mathcal{L}_{\omega_1\omega}$. Let $\Gamma$ be an arbitrary set of sentences from $\mathcal{L}_{\omega_1\omega}$. Let the ...
14
votes
1answer
734 views

Decomposing $\mathbf{\Pi}^1_1$ sets into closed sets

It is well known that every $\mathbf{\Pi}^1_1$-set is a union of $\aleph_1$-many Borel sets. I wonder whether it can be improved under certain reasonable set theory axioms assumption. For example, ...
2
votes
0answers
127 views

Unbounded Class of Orbit Equivalence Relations

In their paper titled "The Classification of Hypersmooth Borel Equivalence Relations" Alexander Kechris and Alain Louveau quote the following (Theorem 5.2 in the article) as "Harrington, unpublished": ...
5
votes
0answers
548 views

ZFC+``every analytical set is measurable"

I know that "ZFC+the existence of an inaccessible cardinal" is equconsistent to "ZFC + every $\mathbf{\Sigma}^1_3$ set is measurable". Then how about the light face case? Without large cardinal ...
26
votes
0answers
809 views

Concerning the various proofs from the axiom of choice that R^3 admits of surprising geometrical decompositions into circles, skew lines and so on: can we prove in any instance that there are no Borel such decompositions? Or that AC is required?

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 ...
5
votes
1answer
471 views

Countable admissible ordinals

Jensen claimed that for any finite increasing sequence countable admissible ordinals $\omega= \alpha_0<\alpha_1\cdots <\alpha_n$, there is a real $x$ so that, for each $m\leq n$, $\alpha_m$ is ...
7
votes
3answers
371 views

Question of combinatorics in the lower part of the Borel hierarchy.

Let $S^\omega$ denote either $\omega^\omega$ or $2^\omega$. Let's call a function $f: S^\omega \rightarrow$ {0,1} 'nice' if there exists a function $g_f: S^{\lt \omega} \rightarrow 2$ such that for ...
12
votes
1answer
450 views

2-colorings of the reals

It's easy to prove that, if $\mathbb{R}$ is well-orderable, then there is a 2-coloring of pairs of reals with no uncountable homogeneous set, i.e., there is an $m: [\mathbb{R}]^2\rightarrow 2$ such ...
2
votes
1answer
310 views

Large cardinal axioms and the perfect set property

It is known that if there is a measurable cardinal then every $\Pi_1^1$ set has the perfect set property (i.e it is either countable or contains a copy of $2^{\omega}$). Also if we have ...
8
votes
2answers
434 views

Exact consistency-strength of “all projective sets are Ramsey”

I wonder if the exact consistency strength of "All projective sets have the Ramsey property" is still open. In Solovay's model, all sets have the Ramsey property, so the consistency strength of this ...
12
votes
3answers
931 views

Partitioning $\mathbb{R}$ into $\aleph_1$ Borel sets

I just ran into this deceptively simple looking question. Is it always possible to partition $\mathbb{R}$ (or any other standard Borel space) into precisely $\aleph_1$ Borel sets? On the one ...