Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUnstable classes of metric structures
489
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove a strong non-structure theorem for a class of metric structures with an unstable pair of formulae. As a consequence, we show that weak categoricity (that is, categoricity up to isomorphisms and not isometries) implies severa
rate research
Read More
We compare three notions of genericity of separable metric structures. Our analysis provides a general model theoretic technique of showing that structures are generic in descriptive set theoretic (topological) sense and in measure theoretic sense. In particular, it gives a new perspective on Vershiks theorems on genericity and randomness of Urysohns space among separable metric spaces.
The general theory developed by Ben Yaacov for metric structures provides Fraisse limits which are approximately ultrahomogeneous. We show here that this result can be strengthened in the case of relational metric structures. We give an extra condition that guarantees exact ultrahomogenous limits. The condition is quite general. We apply it to stochastic processes, the class of diversities, and its subclass of $L_1$ diversities.
When classes of structures are not first-order definable, we might still try to find a nice description. There are two common ways for doing this. One is to expand the language, leading to notions of pseudo-elementary classes, and the other is to allow infinite conjuncts and disjuncts. In this paper we examine the intersection. Namely, we address the question: Which classes of structures are both pseudo-elementary and $mathcal{L}_{omega_1 omega}$-elementary? We find that these are exactly the classes that can be defined by an infinitary formula that has no infinitary disjunctions.
Henle, Mathias, and Woodin proved that, provided that $omegarightarrow(omega)^{omega}$ holds in a model $M$ of ZF, then forcing with $([omega]^{omega},subseteq^*)$ over $M$ adds no new sets of ordinals, thus earning the name a barren extension. Moreover, under an additional assumption, they proved that this generic extension preserves all strong partition cardinals. This forcing thus produces a model $M[mathcal{U}]$, where $mathcal{U}$ is a Ramsey ultrafilter, with many properties of the original model $M$. This begged the question of how important the Ramseyness of $mathcal{U}$ is for these results. In this paper, we show that several classes of $sigma$-closed forcings which generate non-Ramsey ultrafilters have the same properties. Such ultrafilters include Milliken-Taylor ultrafilters, a class of rapid p-points of Laflamme, $k$-arrow p-points of Baumgartner and Taylor, and extensions to a class of ultrafilters constructed by Dobrinen, Mijares and Trujillo. Furthermore, the class of Boolean algebras $mathcal{P}(omega^{alpha})/mathrm{Fin}^{otimes alpha}$, $2le alpha<omega_1$, forcing non-p-points also produce barren extensions.
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from polynomial space by showing that all Turing-complete sets for certain levels of the exponential-time hierarchy are autoreducible but there exists some Turing-complete set for doubly exponential space that is not. Although we already knew how to separate these classes using diagonalization, our proofs separate classes solely by showing they have different structural properties, thus applying Posts Program to complexity theory. We feel such techniques may prove unknown separations in the future. In particular, if we could settle the question as to whether all Turing-complete sets for doubly exponential time are autoreducible, we would separate either polynomial time from polynomial space, and nondeterministic logarithmic space from nondeterministic polynomial time, or else the polynomial-time hierarchy from exponential time. We also look at the autoreducibility of complete sets under nonadaptive, bounded query, probabilistic and nonuniform reductions. We show how settling some of these autoreducibility questions will also read to new complexity class separations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
