ترغب بنشر مسار تعليمي؟ اضغط هنا

Siblings of an $aleph_0$-categorical relational structure

132   0   0.0 ( 0 )
 نشر من قبل Maurice Pouzet
 تاريخ النشر 2018
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

A sibling of a relational structure $R$ is any structure $S$ which can be embedded into $R$ and, vice versa, in which $R$ can be embedded. Let $sib(R)$ be the number of siblings of $R$, these siblings being counted up to isomorphism. Thomasse conjectured that for countable relational structures made of at most countably many relations, $sib(R)$ is either $1$, countably infinite, or the size of the continuum; but even showing the special case $sib(R)=1$ or infinite is unsettled when $R$ is a countable tree. This is related to Bonato-Tardif conjecture asserting that for every tree $T$ the number of trees which are sibling of $T$ is either one or infinite. We prove that if $R$ is countable and $aleph_{0}$-categorical, then indeed $sib(R)$ is one or infinite. Furthermore, $sib(R)$ is one if and only if $R$ is finitely partitionable in the sense of Hodkinson and Macpherson. The key tools in our proof are the notion of monomorphic decomposition of a relational structure introduced in a paper by Pouzet and Thiery 2013 and studied further by Oudrar and Pouzet 2015, and a result of Frasnay 1984.



قيم البحث

اقرأ أيضاً

231 - Paolo Bertozzini 2014
We provide an algebraic formulation of C.Rovellis relational quantum theory that is based on suitable notions of non-commutative higher operator categories, originally developed in the study of categorical non-commutative geometry. As a way to implem ent C.Rovellis original intuition on the relational origin of space-time, in the context of our proposed algebraic approach to quantum gravity via Tomita-Takesaki modular theory, we tentatively suggest to use this categorical formalism in order to spectrally reconstruct non-commutative relational space-time geometries from categories of correlation bimodules between operator algebras of observables. Parts of this work are joint collaborations with: Dr.Roberto Conti (Sapienza Universita di Roma), Assoc.Prof.Wicharn Lewkeeratiyutkul (Chulalongkorn University, Bangkok), Dr.Rachel Dawe Martins (Istituto Superior Tecnico, Lisboa), Dr.Matti Raasakka (Paris 13 University), Dr.Noppakhun Suthichitranont.
The distinguishing number of a graph $G$ is the smallest positive integer $r$ such that $G$ has a labeling of its vertices with $r$ labels for which there is no non-trivial automorphism of $G$ preserving these labels. Albertson and Collins computed t he distinguishing number for various finite graphs, and Imrich, Klavv{z}ar and Trofimov computed the distinguishing number of some infinite graphs, showing in particular that the Random Graph has distinguishing number 2. We compute the distinguishing number of various other finite and countable homogeneous structures, including undirected and directed graphs, and posets. We show that this number is in most cases two or infinite, and besides a few exceptions conjecture that this is so for all primitive homogeneous countable structures.
Simpson and the second author asked whether there exists a characterization of the natural numbers by a second-order sentence which is provably categorical in the theory RCA$^*_0$. We answer in the negative, showing that for any characterization of t he natural numbers which is provably true in WKL$^*_0$, the categoricity theorem implies $Sigma^0_1$ induction. On the other hand, we show that RCA$^*_0$ does make it possible to characterize the natural numbers categorically by means of a set of second-order sentences. We also show that a certain $Pi^1_2$-conservative extension of RCA$^*_0$ admits a provably categorical single-sentence characterization of the naturals, but each such characterization has to be inconsistent with WKL$^*_0$+superexp.
We study the computational complexity of deciding whether a given set of term equalities and inequalities has a solution in an $omega$-categorical algebra $mathfrak{A}$. There are $omega$-categorical groups where this problem is undecidable. We show that if $mathfrak{A}$ is an $omega$-categorical semilattice or an abelian group, then the problem is in P or NP-hard. The hard cases are precisely those where Pol$(mathfrak{A}, eq)$ has a uniformly continuous minor-preserving map to the clone of projections on a two-element set. The results provide information about algebras $mathfrak{A}$ such that Pol$(mathfrak{A}, eq)$ does not satisfy this condition, and they are of independent interest in universal algebra. In our proofs we rely on the Barto-Pinsker theorem about the existence of pseudo-Siggers polymorphisms. To the best of our knowledge, this is the first time that the pseudo-Siggers identity has been used to prove a complexity dichotomy.
Distributive Stonean residuated lattices are closely related to Stone algebras since their bounded lattice reduct is a Stone algebra. In the present work we follow the ideas presented by Chen and Gr{a}tzer and try to apply them for the case of Stonea n residuated lattices. Given a Stonean residuated lattice, we consider the triple formed by its Boolean skeleton, its algebra of dense elements and a connecting map. We define a category whose objects are these triples and suitably defined morphisms, and prove that we have a categorical equivalence between this category and that of Stonean residuated lattices. We compare our results with other works and show some applications of the equivalence.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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