Do you want to publish a course? Click here

Definability patterns and their symmetries

143   0   0.0 ( 0 )
 Added by Ehud Hrushovski
 Publication date 2019
  fields
and research's language is English




Ask ChatGPT about the research

We identify a canonical structure J associated to any first-order theory, the {it space of definability patterns}. It generalizes the imaginary algebraic closure in a stable theory, and the hyperimaginary bounded closure in simple theories. J admits a compact topology, not necessarily Hausdorff, but the Hausdorff part can already be bigger than the Kim-Pillay space. Using it, we obtain simple proofs of a number of results previously obtained using topological dynamics, but working one power set level lower. The Lascar neighbour relation is represented by a canonical relation on the compact Hausdorff part J; the general Lascar group can be read off this compact structure. This gives concrete form to results of Krupinski, Newelski, Pillay, Rzepecki and Simon, who used topological dynamics applied to large models to show the existence of compact groups mapping onto the Lascar group. In an appendix, we show that a construction analogous to the above but using infinitary patterns recovers the Ellis group of cite{kns}, and use this to sharpen the cardinality bound for their Ellis group from $beth_5$ to $beth_3$, showing the latter is optimal. There is also a close connection to another school of topological dynamics, set theory and model theory, centered around the Kechris-Pestov-Todorv cevic correspondence. We define the Ramsey property for a first order theory, and show - as a simple application of the construction applied to an auxiliary theory - that any theory admits a canonical minimal Ramsey expansion. This was envisaged and proved for certain Fraisse classes, first by Kechris-Pestov-Todorv cevic for expansions by orderings, then by Melleray, Nguyen Van The, Tsankov and Zucker for more general expansions.



rate research

Read More

130 - T. Kotek , J.A. Makowsky 2009
We consider functions of natural numbers which allow a combinatorial interpretation as density functions (speed) of classes of relational structures, s uch as Fibonacci numbers, Bell numbers, Catalan numbers and the like. Many of these functions satisfy a linear recurrence relation over $mathbb Z$ or ${mathbb Z}_m$ and allow an interpretation as counting the number of relations satisfying a property expressible in Monadic Second Order Logic (MSOL). C. Blatter and E. Specker (1981) showed that if such a function $f$ counts the number of binary relations satisfying a property expressible in MSOL then $f$ satisfies for every $m in mathbb{N}$ a linear recurrence relation over $mathbb{Z}_m$. In this paper we give a complete characterization in terms of definability in MSOL of the combinatorial functions which satisfy a linear recurrence relation over $mathbb{Z}$, and discuss various extensions and limitations of the Specker-Blatter theorem.
We study the randomness properties of reals with respect to arbitrary probability measures on Cantor space. We show that every non-computable real is non-trivially random with respect to some measure. The probability measures constructed in the proof may have atoms. If one rules out the existence of atoms, i.e. considers only continuous measures, it turns out that every non-hyperarithmetical real is random for a continuous measure. On the other hand, examples of reals not random for any continuous measure can be found throughout the hyperarithmetical Turing degrees.
It is shown that if the C operator for a PT-symmetric Hamiltonian with simple eigenvalues is not unique, then it is unbounded. Apart from the special cases of finite-matrix Hamiltonians and Hamiltonians generated by differential expressions with PT-symmetric point interactions, the usual situation is that the C operator is unbounded. The fact that the C operator is unbounded is significant because, while there is a formal equivalence between a PT-symmetric Hamiltonian and a conventionally Hermitian Hamiltonian in the sense that the two Hamiltonians are isospectral, the Hilbert spaces are inequivalent. This is so because the mapping from one Hilbert space to the other is unbounded. This shows that PT-symmetric quantum theories are mathematically distinct from conventional Hermitian quantum theories.
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.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا