Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We establish that the isomorphism problem for the classes of computable nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is \(\Sigma _{1}^{1}\) -complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes. PubDate: 2022-01-20
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: This paper studies various equivalent characterizations of left semisimple rings from the standpoint of reverse mathematics. We first show that \(\mathrm ACA_{0}\) is equivalent to the statement that any left module over a left semisimple ring is semisimple over \(\mathrm RCA_{0}\) . We then study characterizations of left semisimple rings in terms of projective modules as well as injective modules, and obtain the following results: (1) \(\mathrm ACA_{0}\) is equivalent to the statement that any left module over a left semisimple ring is projective over \(\mathrm RCA_{0}\) ; (2) \(\mathrm ACA_{0}\) is equivalent to the statement that any left module over a left semisimple ring is injective over \(\mathrm RCA_{0}\) ; (3) \(\mathrm RCA_{0}\) proves the statement that if every cyclic left R-module is projective, then R is a left semisimple ring; (4) \(\mathrm ACA_{0}\) proves the statement that if every cyclic left R-module is injective, then R is a left semisimple ring. PubDate: 2022-01-17
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We show that \( VTC ^0\) , the basic theory of bounded arithmetic corresponding to the complexity class \(\mathrm {TC}^0\) , proves the \( IMUL \) axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the \(\mathrm {TC}^0\) iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, \( VTC ^0\) can also prove the integer division axiom, and (by our previous results) the \( RSUV \) -translation of induction and minimization for sharply bounded formulas. Similar consequences hold for the related theories \(\Delta ^b_1\text{- } CR \) and \(C^0_2\) . As a side result, we also prove that there is a well-behaved \(\Delta _0\) definition of modular powering in \(I\Delta _0+ WPHP (\Delta _0)\) . PubDate: 2022-01-04
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In Schwichtenberg (Studies in logic and the foundations of mathematics, vol 90, Elsevier, pp 867–895, 1977), Schwichtenberg fine-tuned Tait’s technique (Tait in The syntax and semantics of infinitary languages, Springer, pp 204–236, 1968) so as to provide a simplified version of Gentzen’s original cut-elimination procedure for first-order classical logic (Gallier in Logic for computer science: foundations of automatic theorem proving, Courier Dover Publications, London, 2015). In this note we show that, limited to the case of classical propositional logic, the Tait–Schwichtenberg algorithm allows for a further simplification. The procedure offered here is implemented on Kleene’s sequent system G4 (Kleene in Mathematical logic, Wiley, New York, 1967; Smullyan in First-order logic, Courier corporation, London, 1995). The specific formulation of the logical rules for G4 allows us to provide bounds on the height of cut-free proofs just in terms of the logical complexity of their end-sequent. PubDate: 2021-11-26 DOI: 10.1007/s00153-021-00800-8
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We study the notion of weak amalgamation in the context of diagonal conjugacy classes. Generalizing results of Kechris and Rosendal, we prove that for every countable structure M, Polish group G of permutations of M, and \(n \ge 1\) , G has a comeager n-diagonal conjugacy class iff the family of all n-tuples of G-extendable bijections between finitely generated substructures of M, has the joint embedding property and the weak amalgamation property. We characterize limits of weak Fraïssé classes that are not homogenizable. Finally, we investigate 1- and 2-diagonal conjugacy classes in groups of ball-preserving bijections of certain ordered ultrametric spaces. PubDate: 2021-11-26 DOI: 10.1007/s00153-021-00807-1
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Structural reasoning is simply reasoning that is governed exclusively by structural rules. In this context a proof system can be said to be structural if all of its inference rules are structural. A logic is considered to be structuralizable if it can be equipped with a sound and complete structural proof system. This paper provides a general formulation of the problem of structuralizability of a given logic, giving specific consideration to a family of logics that are based on the Dunn–Belnap four-valued semantics. It is shown how sound and complete structural proof systems can be constructed for a spectrum of logics within different logical frameworks. PubDate: 2021-11-24 DOI: 10.1007/s00153-021-00806-2
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Using a countable support product of creature forcing posets, we show that consistently, for uncountably many different functions the associated Yorioka ideals’ uniformity numbers can be pairwise different. In addition we show that, in the same forcing extension, for two other types of simple cardinal characteristics parametrised by reals (localisation and anti-localisation cardinals), for uncountably many parameters the corresponding cardinals are pairwise different. PubDate: 2021-11-24 DOI: 10.1007/s00153-021-00809-z
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Let T be a theory. If T eliminates \(\exists ^\infty \) , it need not follow that \(T^{\mathrm {eq}}\) eliminates \(\exists ^\infty \) , as shown by the example of the p-adics. We give a criterion to determine whether \(T^{\mathrm {eq}}\) eliminates \(\exists ^\infty \) . Specifically, we show that \(T^{\mathrm {eq}}\) eliminates \(\exists ^\infty \) if and only if \(\exists ^\infty \) is eliminated on all interpretable sets of “unary imaginaries.” This criterion can be applied in cases where a full description of \(T^{\mathrm {eq}}\) is unknown. As an application, we show that \(T^{\mathrm {eq}}\) eliminates \(\exists ^\infty \) when T is a C-minimal expansion of ACVF. PubDate: 2021-11-23 DOI: 10.1007/s00153-021-00803-5
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We present a sequent calculus with the Henkin constants in the place of the free variables. By disposing of the eigenvariable condition, we obtained a proof system with a strong locality property—the validity of each inference step depends only on its active formulas, not its context. Our major outcomes are: the cut elimination via a non-Gentzen-style algorithm without resorting to regularization and the elimination of Skolem functions with linear increase in the proof length for a subclass of derivations with cuts. PubDate: 2021-11-22 DOI: 10.1007/s00153-021-00798-z
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In this paper, we introduce the variety of algebras, which we call monadic \(k\times j\) -rough Heyting algebras. These algebras constitute an extension of monadic Heyting algebras and in \(3\times 2\) case they coincide with monadic 3-valued Łukasiewicz–Moisil algebras. Our main interest is the characterization of simple and subdirectly irreducible monadic \(k\times j\) -rough Heyting algebras. In order to this, an Esakia-style duality for these algebras is developed. PubDate: 2021-11-13 DOI: 10.1007/s00153-021-00802-6
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We show that certain type of tree forcings, including Sacks forcing, increases the covering of the strong measure zero ideal \({{\mathcal {S}}}{{\mathcal {N}}}\) . As a consequence, in Sacks model, such covering number is equal to the size of the continuum, which indicates that this covering number is consistently larger than any other classical cardinal invariant of the continuum. Even more, Sacks forcing can be used to force that \(\mathrm {non}({{\mathcal {S}}}{{\mathcal {N}}})<\mathrm {cov}({{\mathcal {S}}}{{\mathcal {N}}})<\mathrm {cof}({{\mathcal {S}}}{{\mathcal {N}}})\) , which is the first consistency result where more than two cardinal invariants associated with \({{\mathcal {S}}}{{\mathcal {N}}}\) are pairwise different. Another consequence is that \({{\mathcal {S}}}{{\mathcal {N}}}\subseteq s^0\) in ZFC where \(s^0\) denotes Marczewski’s ideal. PubDate: 2021-11-10 DOI: 10.1007/s00153-021-00808-0
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We use the forcing with overlapping extenders (Gitik in Blowing up the power of a singular cardinal of uncountable cofinality, to appear in JSL) to give a direct construction of a model of \(\lnot \) SCH+Reflection. PubDate: 2021-11-09 DOI: 10.1007/s00153-021-00805-3
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We study the definability of ultrafilter bases on \(\omega \) in the sense of descriptive set theory. As a main result we show that there is no coanalytic base for a Ramsey ultrafilter, while in L we can construct \(\Pi ^1_1\) P-point and Q-point bases. We also show that the existence of a \({\varvec{\Delta }}^1_{n+1}\) ultrafilter is equivalent to that of a \({\varvec{\Pi }}^1_n\) ultrafilter base, for \(n \in \omega \) . Moreover we introduce a Borel version of the classical ultrafilter number and make some observations. PubDate: 2021-11-03 DOI: 10.1007/s00153-021-00801-7
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: This short note is on the question whether the intersection of all fixed points of a positive arithmetic operator and the intersection of all its closed points can proved to be equivalent in a weak fragment of second order arithmetic. PubDate: 2021-11-01 DOI: 10.1007/s00153-021-00761-y
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We study ultraproducts of finite residue rings \(\prod \nolimits _{n\in {\mathbb {N}}} {\mathbb {Z}}/n{\mathbb {Z}}\diagup {\mathcal {U}} \) where \({\mathcal {U}}\) is a non-principal ultrafilter. We find sufficient conditions of the ultrafilter \({\mathcal {U}}\) to determine if the resulting ultraproduct \(\prod \nolimits _{n\in {\mathbb {N}}} {\mathbb {Z}}/n{\mathbb {Z}}\diagup {\mathcal {U}}\) has simple, NIP, \(\mathrm {NTP}_{2}\) but not simple nor NIP, or \(\mathrm {TP}_{2}\) theory, noting that all these four cases occur. PubDate: 2021-11-01 DOI: 10.1007/s00153-021-00760-z
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We show that the quantifier elimination result for the Shelah-Spencer almost sure theories of sparse random graphs \(G(n,n^{-\alpha })\) given by Laskowski (Isr J Math 161:157–186, 2007) extends to their various analogues. The analogues will be obtained as theories of generic structures of certain classes of finite structures with a notion of strong substructure induced by rank functions and we will call the generics Baldwin–Shi hypergraphs. In the process we give a method of constructing extensions whose ‘relative rank’ is negative but arbitrarily small in context. We give a necessary and sufficient condition for the theory of a Baldwin–Shi hypergraph to have atomic models. We further show that for certain well behaved classes of theories of Baldwin–Shi hypergraphs, the existentially closed models and the atomic models correspond. PubDate: 2021-11-01 DOI: 10.1007/s00153-021-00765-8
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In finite type arithmetic, the real numbers are represented by rapidly converging Cauchy sequences of rational numbers. Ulrich Kohlenbach introduced abstract types for certain structures such as metric spaces, normed spaces, Hilbert spaces, etc. With these types, the elements of the spaces are given directly, not through the mediation of a representation. However, these abstract spaces presuppose the real numbers. In this paper, we show how to set up an abstract type for the real numbers. The appropriateness of our construction works in tandem with the bounded functional interpretation. PubDate: 2021-11-01 DOI: 10.1007/s00153-021-00772-9
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We introduce the notion of hereditary G-compactness (with respect to interpretation). We provide a sufficient condition for a poset to not be hereditarily G-compact, which we use to show that any linear order is not hereditarily G-compact. Assuming that a long-standing conjecture about unstable NIP theories holds, this implies that an NIP theory is hereditarily G-compact if and only if it is stable (and by a result of Simon, this holds unconditionally for \(\aleph _0\) -categorical theories). We show that if G is definable over A in a hereditarily G-compact theory, then \(G^{00}_A=G^{000}_A\) . We also include a brief survey of sufficient conditions for G-compactness, with particular focus on those which can be used to prove or disprove hereditary G-compactness for some (classes of) theories. PubDate: 2021-11-01 DOI: 10.1007/s00153-021-00763-w
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We characterize the category of Sambin’s positive topologies as the result of the Grothendieck construction applied to a doctrine over the category Loc of locales. We then construct an adjunction between the category of positive topologies and that of topological spaces Top, and show that the well-known adjunction between Top and Loc factors through the constructed adjunction. PubDate: 2021-11-01 DOI: 10.1007/s00153-021-00768-5
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In the present paper, we show the first-order definability of the jump operator in the upper semi-lattice of the \(\omega \) -enumeration degrees. As a consequence, we derive the isomorphicity of the automorphism groups of the enumeration and the \(\omega \) -enumeration degrees. PubDate: 2021-11-01 DOI: 10.1007/s00153-021-00766-7
Hybrid journal (It can contain Open Access articles)
[2469 journals]
