اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCategorical characterizations of the natural numbers require primitive recursion
261
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 the 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 examine the degree structure $mathbf{ER}$ of equivalence relations on $omega$ under computable reducibility. We examine when pairs of degrees have a join. In particular, we show that sufficiently incomparable pairs of degrees do not have a join bu
t that some incomparable degrees do, and we characterize the degrees which have a join with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are definable in $mathbf{ER}$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $mathbf{d}oplus mathbf{Id_1}$ neednt be a strong minimal cover of a self-full degree $mathbf{d}$. Finally, we show that the theory of the degree structure $mathbf{ER}$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second order arithmetic.
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 conject
ured 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.
This paper grew out of the observation that the possibilities of proof by induction and definition by recursion are often confused. The paper reviews the distinctions. The von Neumann construction of the ordinal numbers includes a construction of nat
ural numbers as a special kind of ordinal. In any case, the natural numbers can be understood as composing a free algebra in a certain signature, {0,s}. The paper here culminates in a construction of, for each algebraic signature S, a class ON_S that is to the class of ordinals as S is to {0,s}. In particular, ON_S has a subclass that is a free algebra in the signature S.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
