اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMost simple extensions of $mathsf{FL_e}$ are undecidable
214
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
All known structural extensions of the substructural logic $mathsf{FL_e}$, Full Lambek calculus with exchange/commutativity, (corresponding to subvarieties of commutative residuated lattices axiomatized by ${vee, cdot, 1}$-equations) have decidable theoremhood; in particular all the ones defined by knotted axioms enjoy strong decidability properties (such as the finite embeddability property). We provide infinitely many such extensions that have undecidable theoremhood, by encoding machines with undecidable halting problem. An even bigger class of extensions is shown to have undecidable deducibility problem (the corresponding varieties of residuated lattices have undecidable word problem); actually with very few exceptions, such as the knotted axioms and the other prespinal axioms, we prove that undecidability is ubiquitous. Known undecidability results for non-commutative extensions use an encoding that fails in the presence of commutativity, so and-branching counter machines are employed. Even these machines provide encodings that fail to capture proper extensions of commutativity, therefore we introduce a new variant that works on an exponential scale. The correctness of the encoding is established by employing the theory of residuated frames.
قيم البحث
اقرأ أيضاً
In cite{CGH15} we introduced TiRS graphs and TiRS frames to create a new natural setting for duals of canonical extensions of lattices. In this continuation of cite{CGH15} we answer Problem 2 from there by characterising the perfect lattices that are
dual to TiRS frames (and hence TiRS graphs). We introduce a new subclass of perfect lattices called PTi lattices and show that the canonical extensions of lattices are PTi lattices, and so are `more than just perfect lattices. We introduce morphisms of TiRS structures and put our correspondence between TiRS graphs and TiRS frames from cite{CGH15} into a full categorical framework. We illustrate our correspondences between classes of perfects lattices and classes of TiRS graphs by examples.
By exploiting the geometry of involutions in $N_circ^circ$-groups of finite Morley rank, we show that any simple group of Morley rank $5$ is a bad group all of whose proper definable connected subgroups are nilpotent of rank at most $2$. The main res
ult is then used to catalog the nonsoluble connected groups of Morley rank $5$.
We show that Morleys theorem on the number of countable models of a countable first-order theory becomes an undecidable statement when extended to second-order logic. More generally, we calculate the number of equivalence classes of $sigma$-projectiv
e equivalence relations in several models of set theory. Our methods include random and Cohen forcing, Woodin cardinals and Inner Model Theory.
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. Moreo
ver, 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.
Fix a countable nonstandard model $mathcal M$ of Peano Arithmetic. Even with some rather severe restrictions placed on the types of minimal cofinal extensions $mathcal N succ mathcal M$ that are allowed, we still find that there are $2^{aleph_0}$ pos
sible theories of $(mathcal N,M)$ for such $mathcal N$s.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
