Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBounded Invariant Equivalence Relations
110
0
0.0
(
0
)
Authors
Tomasz Rzepecki
Ask ChatGPT about the research
No Arabic abstract
We study strong types and Galois groups in model theory from a topological and descriptive-set-theoretical point of view, leaning heavily on topological dynamical tools. More precisely, we give an abstract (not model theoretic) treatment of problems related to cardinality and Borel cardinality of strong types, quotients of definable groups and related objecets, generalising (and often improving) essentially all hitherto known results in this area. In particular, we show that under reasonable assumptions, strong type spaces are locally quotients of compact Polish groups. It follows that they are smooth if and only if they are type-definable, and that a quotient of a type-definable group by an analytic subgroup is either finite or of cardinality at least continuum.
rate research
Read More
We generalise the main theorems from the paper The Borel cardinality of Lascar strong types by I. Kaplan, B. Miller and P. Simon to a wider class of bounded invariant equivalence relations. We apply them to describe relationships between fundamental properties of bounded invariant equivalence relations (such as smoothness or type-definability) which also requires finding a series of counterexamples. Finally, we apply the generalisation mentioned above to prove a conjecture from a paper by the first author and J. Gismatullin, showing that the key technical assumption of the main theorem (concerning connected components in definable group extensions) from that paper is not only sufficient but also necessary to get the conclusion.
We extend some recent results about bounded invariant equivalence relations and invariant subgroups of definable groups: we show that type-definability and smoothness are equivalent conditions in a wider class of relations than heretofore considered, which includes all the cases for which the equivalence was proved before. As a by-product, we show some analogous results in purely topological context (without direct use of model theory).
Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility $leq_c$. This gives rise to a rich degree-structure. In this paper, we lift the study of $c$-degrees to the $Delta^0_2$ case. In doing so, we rely on the Ershov hierarchy. For any notation $a$ for a non-zero computable ordinal, we prove several algebraic properties of the degree-structure induced by $leq_c$ on the $Sigma^{-1}_{a}smallsetminus Pi^{-1}_a$ equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of $c$-degrees.
The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations $R$ and $S$ on natural numbers, $R$ is computably reducible to $S$ if there is a computable function $f colon omega to omega$ that induces an injective map from $R$-equivalence classes to $S$-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. In this work, we explore $mathbf{Peq}$, the degree structure generated by primitive recursive reducibility on punctual equivalence relations (i.e., primitive recursive equivalence relations with domain $omega$). In contrast with all other known degree structures on equivalence relations, we show that $mathbf{Peq}$ has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of $mathbf{Peq}$, proving, e.g., that the structure is neither rigid nor homogeneous.
We study the bi-embeddability and elementary bi-embeddability relation on graphs under Borel reducibility and investigate the degree spectra realized by this relations. We first give a Borel reduction from embeddability on graphs to elementary embeddability on graphs. As a consequence we obtain that elementary bi-embeddability on graphs is a analytic complete equivalence relation. We then investigate the algorithmic properties of this reduction to show that every bi-embeddability spectrum of a graph is the jump spectrum of an elementary bi-embeddability spectrum of a graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
