Turing invariant sets and the perfect set property

We show that $\text{◂...▸}\mathsf{ZF}+\mathsf{DC}+\text{“all}\text{Turing}\text{invariant}\text{sets}\text{of}\text{reals}\text{have}\text{the}\text{perfect}\text{set}\text{property”}$ implies that all sets of reals have the perfect set property. We also show that this result generalizes to all countable analytic equivalence relations.     

A note on small sets of reals

We construct an example of a combinatorially large measure-zero set.     

Models of expansions of \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}${\mathbb N}$\end{document} with no end extensions

We deal with models of Peano arithmetic (specifically with a question of Ali Enayat). The methods are from creature forcing. We find an expansion of ${\mathbb N}$ such that its theory has models with no (elementary) end extensions. In fact there is a Borel uncountable set of subsets of ${\mathbb N}$ such that expanding ${\mathbb N}$ by any uncountably many of them suffice. Also we find arithmetically closed ${\mathcal A}$ with no ultrafilter on it with suitable definability demand (related to being Ramsey). © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Choiceless polynomial time

Turing machines define polynomial time (PTime) on strings but cannot deal with structures like graphs directly, and there is no known, easily computable string encoding of isomorphism classes of structures. Is there a computation model whose machines do not distinguish between isomorphic structures and compute exactly PTime properties? This question can be recast as follows: Does there exist a logic that captures polynomial time (without presuming the presence of a linear order)? Earlier, one of us conjectured a negative answer. The problem motivated a quest for stronger and stronger PTime logics. All these logics avoid arbitrary choice. Here we attempt to capture the choiceless fragment of PTime. Our computation model is a version of abstract state machines (formerly called evolving algebras). The idea is to replace arbitrary choice with parallel execution. The resulting logic expresses all properties expressible in any other PTime logic in the literature. A more difficult theorem shows that the logic does not capture all of PTime.     

Large weight does not yield an irreducible base

Answering a question of Juhász, Soukup and Szentmiklóssy, we show that it is consistent that some first countable space of uncountable weight does not contain an uncountable subspace which has an irreducible base.     

On some configurations related to the Shelah Weak Hypothesis

We show that some cardinal arithmetic configurations related to the negation of the Shelah Weak Hypothesis and natural from the forcing point of view are impossible. Received: 8 September 1999 / Published online: 3 October 2001     

Around random algebra

It is shown that there is a subalgebra of the measure algebra forcing dominating reals. Also results are given about iterated forcing connected with random reals.The first author would like to thank NSF for its partial support under Grant DMS-8701828The second author would like to thank U.S.-Israel BSF for partial supportNote. In the first version of this paper we proved only a weak form of the main result of Sect. 2 (see 2.2). Also, the first version contained a third section, but the main result of that version is a weak form of 2.5