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

A fixed point for the jump operator on structures

278   0   0.0 ( 0 )
 نشر من قبل Antonio Montalban
 تاريخ النشر 2011
  مجال البحث
والبحث باللغة English
 تأليف Antonio Montalban




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

Assuming that $0^#$ exists, we prove that there is a structure that can effectively interpret its own jump. In particular, we get a structure $mathcal A$ such that [ Sp({mathcal A}) = {{bf x}:{bf x}in Sp ({mathcal A})}, ] where $Sp ({mathcal A})$ is the set of Turing degrees which compute a copy of $mathcal A$. It turns out that, more interesting than the result itself, is its unexpected complexity. We prove that higher-order arithmetic, which is the union of full $n$th-order arithmetic for all $n$, cannot prove the existence of such a structure.



قيم البحث

اقرأ أيضاً

We define the bounded jump of A by A^b = {x | Exists i <= x [phi_i (x) converges and Phi_x^[A|phi_i(x)](x) converges} and let A^[nb] denote the n-th bounded jump. We demonstrate several properties of the bounded jump, including that it is strictly in creasing and order preserving on the bounded Turing (bT) degrees (also known as the weak truth-table degrees). We show that the bounded jump is related to the Ershov hierarchy. Indeed, for n > 1 we have X <=_[bT] 0^[nb] iff X is omega^n-c.e. iff X <=_1 0^[nb], extending the classical result that X <=_[bT] 0 iff X is omega-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every X such that 0^b <=_[bT] X <=_[bT] 0^[2b], there is a Y <=_[bT] 0^b such that Y^b =_[bT] X.
We investigate four model-theoretic tameness properties in the context of least fixed-point logic over a family of finite structures. We find that each of these properties depends only on the elementary (i.e., first-order) limit theory, and we comple tely determine the valid entailments among them. In contrast to the context of first-order logic on arbitrary structures, the order property and independence property are equivalent in this setting. McColm conjectured that least fixed-point definability collapses to first-order definability exactly when proficiency fails. McColms conjecture is known to be false in general. However, we show that McColms conjecture is true for any family of finite structures whose limit theory is model-theoretically tame.
This paper is an attempt to solve the following problem: given a logic, how to turn it into a paraconsistent one? In other words, given a logic in which emph{ex falso quodlibet} holds, how to convert it into a logic not satisfying this principle? We use a framework provided by category theory in order to define a category of consequence structures. Then, we propose a functor to transform a logic not able to deal with contradictions into a paraconsistent one. Moreover, we study the case of paraconsistentization of propositional classical logic.
132 - Dino Rossegger 2017
We study a new notion of reduction between structures called enumerable functors related to the recently investigated notion of computable functors. Our main result shows that enumerable functors and effective interpretability with the equivalence re lation computable are equivalent. We also obtain results on the relation between enumerable and computable functors.
In this preliminary study, we examine the chiral properties of the parametrized Fixed-Point Dirac operator D^FP, see how to improve its chirality via the Overlap construction, measure the renormalized quark condensate Sigma and the topological suscep tibility chi_t, and investigate local chirality of near zero modes of the Dirac operator. We also give a general construction of chiral currents and densities for chiral lattice actions.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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