Source author record

Philipp Schlicht

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO Logic in Computer Science math.GN

Catalog footprint

Research overview

9works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Countable ranks at the first and second projective levels

A rank is a notion in descriptive set theory that describes ranks such as the Cantor-Bendixson rank on the set of closed subsets of a Polish space, differentiability ranks on the set of differentiable functions in $C[0,1]$ such as the Kechris-Woodin rank and many other ranks in descriptive set theory and real analysis. The complexity of many natural ranks is $Π^1_1$ or $Σ^1_2$ . We propose to understand the least length of ranks on a set as a measure of its complexity. Therefore, the aim is to understand which lengths such ranks may have. The main result determines the suprema of lengths of countable ranks at the first and second projective levels. Furthermore, we characterise the existence of countable ranks on specific classes of $Σ^1_2$ sets. The connections arising between $Σ^1_2$ sets with countable ranks on the one hand and $Σ^1_2$ Borel sets on the other lead to a conjecture that unifies several results in descriptive set theory such as the Mansfield-Solovay theorem and a recent result of Kanovei and Lyubetsky.

preprint2022arXiv

Decision times of infinite computations

The decision time of an infinite time algorithm is the supremum of its halting times over all real inputs. The decision time of a set of reals is the least decision time of an algorithm that decides the set; semidecision times of semidecidable sets are defined similary. It is not hard to see that $ω_1$ is the maximal decision time of sets of reals. Our main results determine the supremum of countable decision times as $σ$ and that of countable semidecision times as $τ$ , where $σ$ and $τ$ denote the suprema of $Σ_1$ - and $Σ_2$ -definable ordinals, respectively, over $L_{ω_1}$ . We further compute analogous suprema for singletons.

preprint2022arXiv

Forcing over choiceless models and generic absoluteness

We develop a toolbox for forcing over arbitrary models of set theory without the axiom of choice. In particular, we introduce a variant of the countable chain condition and prove an iteration theorem that applies to many classical forcings such as Cohen forcing and random algebras. Our approach sidesteps the problem that forcing with the countable chain condition can collapse $ω_1$ by a recent result of Karagila and Schweber. Using this, we show that adding many Cohen reals and random reals leads to different theories. This result is due to Woodin. Thus one can always change the theory of the universe by forcing, just like the continuum hypothesis and its negation can be obtained by forcing over arbitrary models with choice. We further study principles stipulating that the first-order theory of the universe remains the same in all generic extension by a fixed class of forcings. Extending a result of Woodin, we show that even for very restricted classes such as the class of all finite support products of Cohen forcing or the class of all random algebras, this principle implies that all infinite cardinals have countable cofinality.

preprint2022arXiv

Uniformization and Internal Absoluteness

Measurability with respect to ideals is tightly connected with absoluteness principles for certain forcing notions. We study a uniformization principle that postulates the existence of a uniformizing function on a large set, relative to a given ideal. We prove that for all $σ$ -ideals $I$ such that the ideal forcing $\mathbb{P}_I$ of Borel sets modulo $I$ is proper, this uniformization principle is equivalent to an absoluteness principle for projective formulas with respect to $\mathbb{P}_I$ that we call internal absoluteness. In addition, we show that it is equivalent to measurability with respect to $I$ together with $1$ -step absoluteness for the poset $\mathbb{P}_I$ . These equivalences are new even for Cohen and random forcing and they are, to the best of our knowledge, the first precise equivalences between regularity and absoluteness beyond the second level of the projective hierarchy.

preprint2021arXiv

Long Games and $σ$ -Projective Sets

We prove a number of results on the determinacy of $σ$ -projective sets of reals, i.e., those belonging to the smallest pointclass containing the open sets and closed under complements, countable unions, and projections. We first prove the equivalence between $σ$ -projective determinacy and the determinacy of certain classes of games of variable length ${<}ω^2$ (Theorem 2.4). We then give an elementary proof of the determinacy of $σ$ -projective sets from optimal large-cardinal hypotheses (Theorem 4.4). Finally, we show how to generalize the proof to obtain proofs of the determinacy of $σ$ -projective games of a given countable length and of games with payoff in the smallest $σ$ -algebra containing the projective sets, from corresponding assumptions (Theorems 5.1 and 5.4).

preprint2016arXiv

The Hurewicz dichotomy for generalized Baire spaces

By classical results of Hurewicz, Kechris and Saint-Raymond, an analytic subset of a Polish space $X$ is covered by a $K_σ$ subset of $X$ if and only if it does not contain a closed-in- $X$ subset homeomorphic to the Baire space ${}^ωω$ . We consider the analogous statement (which we call Hurewicz dichotomy) for $Σ^1_1$ subsets of the generalized Baire space ${}^κκ$ for a given uncountable cardinal $κ$ with $κ=κ^{<κ}$ , and show how to force it to be true in a cardinal and cofinality preserving extension of the ground model. Moreover, we show that if the Generalized Continuum Hypothesis (GCH) holds, then there is a cardinal preserving class-forcing extension in which the Hurewicz dichotomy for $Σ^1_1$ subsets of ${}^κκ$ holds at all uncountable regular cardinals $κ$ , while strongly unfoldable and supercompact cardinals are preserved. On the other hand, in the constructible universe L the dichotomy for $Σ^1_1$ sets fails at all uncountable regular cardinals, and the same happens in any generic extension obtained by adding a Cohen real to a model of GCH. We also discuss connections with some regularity properties, like the $κ$ -perfect set property, the $κ$ -Miller measurability, and the $κ$ -Sacks measurability.

preprint2013arXiv

Lipschitz and uniformly continuous reducibilities on ultrametric Polish spaces

We analyze the reducibilities induced by, respectively, uniformly continuous, Lipschitz, and nonexpansive functions on arbitrary ultrametric Polish spaces, and determine whether under suitable set-theoretical assumptions the induced degree-structures are well-behaved.

preprint2012arXiv

The mate-in-n problem of infinite chess is decidable

Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The mate-in-n problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most n moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with 2n alternating quantifiers---there is a move for white, such that for every black reply, there is a counter-move for white, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth. Nevertheless, the main theorem of this article, confirming a conjecture of the first author and C. D. A. Evans, establishes that the mate-in-n problem of infinite chess is computably decidable, uniformly in the position and in n. Furthermore, there is a computable strategy for optimal play from such mate-in-n positions. The proof proceeds by showing that the mate-in-n problem is expressible in what we call the first-order structure of chess, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Indeed, it is definable in Presburger arithmetic. Unfortunately, this resolution of the mate-in-n problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess is not known.

preprint2010arXiv

Non-permutation invariant Borel quantifiers

Every permutation invariant Borel subset of the space of countable structures is definable in $\La_{ω_1ω}$ by a theorem of Lopez-Escobar. We prove variants of this theorem relative to fixed relations and fixed non-permutation invariant quantifiers. Moreover we show that for every closed subgroup $G$ of the symmetric group $S_{\infty}$ , there is a closed binary quantifier $Q$ such that the $G$ -invariant subsets of the space of countable structures are exactly the $\La_{ω_1ω}(Q)$-definable sets.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Philipp Schlicht

Research overview

Is this your work?

9 publications

Countable ranks at the first and second projective levels

Decision times of infinite computations

Forcing over choiceless models and generic absoluteness

Uniformization and Internal Absoluteness

Long Games and $σ$ -Projective Sets

The Hurewicz dichotomy for generalized Baire spaces

Lipschitz and uniformly continuous reducibilities on ultrametric Polish spaces

The mate-in-n problem of infinite chess is decidable

Non-permutation invariant Borel quantifiers

See the researcher in context

Building this map preview

Philipp Schlicht

Research overview

Is this your work?

9 publications

Countable ranks at the first and second projective levels

Decision times of infinite computations

Forcing over choiceless models and generic absoluteness

Uniformization and Internal Absoluteness

Long Games and σσσ-Projective Sets

The Hurewicz dichotomy for generalized Baire spaces

Lipschitz and uniformly continuous reducibilities on ultrametric Polish spaces

The mate-in-n problem of infinite chess is decidable

Non-permutation invariant Borel quantifiers

See the researcher in context

Building this map preview

Long Games and $σ$ -Projective Sets