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: Abstract Definitionally: strongly effectively immune sets are infinite and their c.e. subsets have maximums effectively bounded in their c.e. indices; whereas, for effectively immune sets, their c.e. subsets’ cardinalities are what’re effectively bounded. This definitional difference between these two kinds of sets is very nicely paralleled by the following difference between their complements. McLaughlin: strongly effectively immune sets cannot have immune complements; whereas, the main theorem herein: effectively immune sets cannot have hyperimmune complements. Ullian: effectively immune sets can have effectively immune complements. The main theorem improves Arslanov’s, effectively hyperimmune sets cannot have effectively hyperimmune complements: the improvement omits the second ‘effectively’. Two natural examples of strongly effectively immune sets are presented with new cases of the first proved herein. The first is the set of minimal-Blum-size programs for the partial computable functions; the second, the set of Kolmogorov-random strings. A proved, natural example is presented of an effectively dense simple, not strongly effectively simple set; its complement is a set of maximal run-times. Further motivations for this study are presented. Kleene recursion theorem proofs herein emphasize how to conceptualize them. Finally, is suggested, future, related work—illustrated by a first, natural, strongly effectively \(\Sigma _2^0\) -immune set—included: solution of an open problem from Rogers’ book. PubDate: 2025-01-29 DOI: 10.1007/s00153-024-00958-x
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: Abstract We develop an algebraic study of W.S. Cooper’s three-valued propositional logic of ordinary discourse ( \(\mathcal{O}\mathcal{L}\) ). This logic displays a number of unusual features: \(\mathcal{O}\mathcal{L}\) is not weaker but incomparable with classical logic, it is connexive, paraconsistent and contradictory. As a non-structural logic, \(\mathcal{O}\mathcal{L}\) cannot be algebraized by the standard methods. However, we show that \(\mathcal{O}\mathcal{L}\) has an algebraizable structural companion, and determine its equivalent semantics, which turns out to be a finitely-generated discriminator variety. We provide an equational and a twist presentation for this class of algebras, which allow us to compare it with other well-known algebras of non-classical logics. In this way we establish that \(\mathcal{O}\mathcal{L}\) is definitionally equivalent to an expansion of the three-valued logic \({\mathcal {J}}3\) of D’Ottaviano and da Costa, itself a schematic extension of paraconsistent Nelson logic. PubDate: 2025-01-27 DOI: 10.1007/s00153-024-00961-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: Abstract We provide a complete axiomatization of modal inclusion logic—team-based modal logic extended with inclusion atoms. We review and refine an expressive completeness and normal form theorem for the logic, define a natural deduction proof system, and use the normal form to prove completeness of the axiomatization. Complete axiomatizations are also provided for two other extensions of modal logic with the same expressive power as modal inclusion logic: one augmented with a might operator and the other with a single-world variant of the might operator. PubDate: 2025-01-27 DOI: 10.1007/s00153-024-00957-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: Abstract We investigate the property of elimination of imaginaries for some special cases of ordered abelian groups. We show that certain Hahn products of ordered abelian groups do not eliminate imaginaries in the pure language of ordered groups. Moreover, we prove that, adding finitely many constants to the language of ordered abelian groups, the theories of the finite lexicographic products \(\mathbb {Z}^n\) and \(\mathbb {Z}^n \times \mathbb {Q}\) have definable Skolem functions. PubDate: 2025-01-15 DOI: 10.1007/s00153-025-00965-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: Abstract For a free filter F on \(\omega \) , let \(N_F=\omega \cup \{p_F\}\) , where \(p_F\not \in \omega \) , be equipped with the following topology: every element of \(\omega \) is isolated whereas all open neighborhoods of \(p_F\) are of the form \(A\cup \{p_F\}\) for \(A\in F\) . The aim of this paper is to study spaces of the form \(N_F\) in the context of the Nikodym property of Boolean algebras. By \(\mathcal{A}\mathcal{N}\) we denote the class of all those ideals \(\mathcal {I}\) on \(\omega \) such that for the dual filter \(\mathcal {I}^*\) the space \(N_{\mathcal {I}^*}\) carries a sequence \(\langle \mu _n:n\in \omega \rangle \) of finitely supported signed measures such that \(\Vert \mu _n\Vert \rightarrow \infty \) and \(\mu _n(A)\rightarrow 0\) for every clopen subset \(A\subseteq N_{\mathcal {I}^*}\) . We prove that \(\mathcal {I}\in \mathcal{A}\mathcal{N}\) if and only if there exists a density submeasure \(\varphi \) on \(\omega \) such that \(\varphi (\omega )=\infty \) and \(\mathcal {I}\) is contained in the exhaustive ideal \(\text{ Exh }(\varphi )\) . Consequently, we get that if \(\mathcal {I}\subseteq \text{ Exh }(\varphi )\) for some density submeasure \(\varphi \) on \(\omega \) such that \(\varphi (\omega )=\infty \) and \(N_{\mathcal {I}^*}\) is homeomorphic to a subspace of the Stone space \(St(\mathcal {A})\) of a given Boolean algebra PubDate: 2025-01-10 DOI: 10.1007/s00153-024-00964-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: Abstract In a previous paper of the author it was shown that the question whether systems of exponential diophantine equations are solvable in \({\mathbb {Q}}\) is undecidable. Now we show that the solvability of a conjunction of exponential diophantine equations in \({\mathbb {Q}}\) is equivalent to the solvability of just one such equation. It follows that the problem whether an exponential diophantine equation has solutions in \({\mathbb {Q}}\) is undecidable. We also show that two particular forms of exponential diophantine equations are undecidable. PubDate: 2025-01-03 DOI: 10.1007/s00153-024-00960-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: Abstract A complete theory T has the Schröder–Bernstein property or simply the SB-property if any pair of elementarily bi-embeddable models are isomorphic. This property has been studied in the discrete first-order setting and can be seen as a first step towards classification theory. This paper deals with the SB-property on continuous theories. Examples of complete continuous theories that have this property include Hilbert spaces and any completion of the theory of probability algebras. We also study a weaker notion, the SB-property up to perturbations. This property holds if any two elementarily bi-embeddable models are isomorphic up to perturbations. We prove that the theory of Hilbert spaces expanded with a bounded self-adjoint operator has the SB-property up to perturbations of the operator and that the theory of atomless probability algebras with a generic automorphism have the SB-property up to perturbations of the automorphism. We also study how the SB-property behaves with respect to randomizations. Finally we prove, in the continuous setting, that if T is a strictly stable theory then T does not have the SB-property. PubDate: 2025-01-03 DOI: 10.1007/s00153-024-00949-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: Abstract This paper studies categories and functors in the context of reverse and computable mathematics. In ordinary reverse mathematics, we only focuses on categories whose objects and morphisms can be represented by natural numbers. We first consider morphism sets of categories and prove several associated theorems equivalent to \(\mathrm ACA_{0}\) over the base system \(\mathrm RCA_{0}\) . The Yoneda Lemma is a basic result in category theory and homological algebra. We then develop an effective version of the Yoneda Lemma in \(\mathrm RCA_{0}\) ; as an application, we formalize an effective version of the Yoneda Embedding in \(\mathrm RCA_{0}\) . Products and coproducts are basic notions for defining special categories like semi-additive categories and additive categories. We study properties of products and coproducts of a sequence of objects of categories and provide effective characterizations of semi-additive categories and additive categories in terms of products and coproducts. Finally, we further consider the strength of theorems of category theory that are studied in this paper by methods of higher-order reverse mathematics PubDate: 2024-12-31 DOI: 10.1007/s00153-024-00962-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: Abstract We discuss the externally definable Ramsey property, a weakening of the Ramsey property for relational structures, where the only colourings considered are those that are externally definable: that is, definable with parameters in an elementary extension. We show a number of basic results analogous to the classical Ramsey theory, and show that, for an ultrahomogeneous structure M with countable age, the externally definable Ramsey property is equivalent to the dynamical statement that, for all \(n \in \mathbb {N} \) , every subflow of the space \(S_n(M)\) of n-types has a fixed point. We discuss a range of examples, including results regarding the lexicographic product of structures. PubDate: 2024-12-27 DOI: 10.1007/s00153-024-00950-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: Abstract In Bagaria (J Symb Log 81(2), 584–604, 2016), Bagaria and Väänänen developed a framework for studying the large cardinal strength of downwards Löwenheim-Skolem theorems and related set theoretic reflection properties. The main tool was the notion of symbiosis, originally introduced by the third author in Väänänen (Applications of set theory to generalized quantifiers. PhD thesis, University of Manchester, 1967); Väänänen (in Logic Colloquium ’78 (Mons, 1978), volume 97 of Stud. Logic Foundations Math., pages 391–421. North-Holland, Amsterdam 1979) Symbiosis provides a way of relating model theoretic properties of strong logics to definability in set theory. In this paper we continue the systematic investigation of symbiosis and apply it to upwards Löwenheim-Skolem theorems and reflection principles. To achieve this, we need to adapt the notion of symbiosis to a new form, called bounded symbiosis. As one easy application, we obtain upper and lower bounds for the large cardinal strength of upwards Löwenheim–Skolem-type principles for second order logic. PubDate: 2024-12-23 DOI: 10.1007/s00153-024-00955-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: Abstract We explore approximate categoricity in the context of distortion systems, introduced in our previous paper (Hanson in Math Logic Q 69(4):482–507, 2023), which are a mild generalization of perturbation systems, introduced by Yaacov (J Math Logic 08(02):225–249, 2008). We extend Ben Yaacov’s Ryll-Nardzewski style characterization of separably approximately categorical theories from the context of perturbation systems to that of distortion systems. We also make progress towards an analog of Morley’s theorem for inseparable approximate categoricity, showing that if there is some uncountable cardinal \(\kappa \) such that every model of size \(\kappa \) is ‘approximately saturated,’ in the appropriate sense, then the same is true for all uncountable cardinalities. Finally we present some examples of these phenomena and highlight an apparent interaction between ordinary separable categoricity and inseparable approximate categoricity. PubDate: 2024-12-21 DOI: 10.1007/s00153-024-00952-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: Abstract Using the Feferman-Vaught Theorem, we prove that a definable subset of a product structure must be a Boolean combination of open sets, in the product topology induced by giving each factor structure the discrete topology. We prove that for families of structures with certain properties, including families of integral domains, the pure Boolean generalized product is definable in the direct product structure. We use these results to obtain characterizations of the definable subsets of \(\prod _p \mathbb {F}_p\) —in particular, every formula is equivalent to a Boolean combination of \(\exists \forall \exists \) formulae. PubDate: 2024-12-06 DOI: 10.1007/s00153-024-00954-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: Abstract In the analysis of the blurry \(\textsf{HOD}\) hierarchy, one of the fundamental concepts is that of a leap, and it turned out that critical leaps are of particular interest. A critical leap is a leap which is the cardinal successor of a singular strong limit cardinal. Such a leap is sudden if its cardinal predecessor is not a leap, and otherwise, it is smooth. In prior work, I showed that the existence of a sudden critical leap is equiconsistent with the existence of a measurable cardinal. Here, I show that if the cofinality of the cardinal predecessor of a sudden critical leap is required to be uncountable, the consistency strength increases considerably. I also show that when focusing on critical leaps whose cardinal predecessors have uncountable cofinality, the consistency strength of a smooth critical leap is much lower than that of a sudden critical leap. Finally, I observe that in contrast to the countable cofinality setting, \(\aleph _{\omega _1+1}\) , e.g., cannot be a sudden critical leap. PubDate: 2024-11-26 DOI: 10.1007/s00153-024-00951-4
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: Abstract We study relativized Lascar groups, which are formed by relativizing Lascar groups to the solution set of a partial type \(\Sigma \) . We introduce the notion of a Lascar tuple for \(\Sigma \) and by considering the space of types over a Lascar tuple for \(\Sigma \) , the topology for a relativized Lascar group is (re-)defined and some fundamental facts about the Galois groups of first-order theories are generalized to the relativized context. In particular, we prove that any closed subgroup of a relativized Lascar group corresponds to a stabilizer of a bounded hyperimaginary having at least one representative in the solution set of the given partial type \(\Sigma \) . Using this, we find the correspondence between subgroups of the relativized Lascar group and the relativized strong types. PubDate: 2024-11-13 DOI: 10.1007/s00153-024-00953-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: Abstract We investigate whether classical combinatorial theorems are provable in ZF. Some statements are not provable in ZF, but they are equivalent within ZF. For example, the following statements (i)–(iii) are equivalent: \(cf({\omega }_1)={\omega }_1\) , \({\omega }_1\rightarrow ({\omega }_1,{\omega }+1)^2\) , any family \(\mathcal {A}\subset [{On}]^{<{\omega }}\) of size \({\omega }_1\) contains a \(\Delta \) -system of size \({\omega }_1\) . Some classical results cannot be proven in ZF alone; however, we can establish weaker versions of these statements within the framework of ZF, such as \({{\omega }_2}\rightarrow ({\omega }_1,{\omega }+1)\) , any family \(\mathcal {A}\subset [{On}]^{<{\omega }}\) of size \({\omega }_2\) contains a \(\Delta \) -system of size \({\omega }_1\) . Some statements can be proven in ZF using purely combinatorial arguments, such as: given a set mapping \(F:{\omega }_1\rightarrow {[{\omega }_1]}^{<{\omega }}\) , the set \({\omega }_1\) has a partition into \({\omega }\) -many F-free sets. Other statements can be proven in ZF by employing certain methods of absoluteness, for example: given a set mapping \(F:{\omega }_1\rightarrow {[{\omega }_1]}^{<{\omega }}\) , there is an F-free set of size \({\omega }_1\) , for each \(n\in {\omega }\) , every family \(\mathcal {A}\subset {[{\omega }_1]}^{{\omega }}\) with \( A\cap B \le n\) for \(\{A,B\}\in {[\mathcal {A}]}^{2}\) has property B. In contrast to statement (5), we show that the following ZFC theorem of Komjáth is not provable from ZF + \(cf({\omega }_1)={\omega }_1\) : (6 PubDate: 2024-11-10 DOI: 10.1007/s00153-024-00946-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: Abstract We address some phenomena about the interaction between lower semicontinuous submeasures on \({\mathbb {N}}\) and \(F_{\sigma }\) ideals. We analyze the pathology degree of a submeasure and present a method to construct pathological \(F_{\sigma }\) ideals. We give a partial answers to the question of whether every nonpathological tall \(F_{\sigma }\) ideal is Katětov above the random ideal or at least has a Borel selector. Finally, we show a representation of nonpathological \(F_{\sigma }\) ideals using sequences in Banach spaces. PubDate: 2024-11-01 DOI: 10.1007/s00153-024-00910-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: Abstract We obtain several game characterizations of Baire 1 functions between Polish spaces X, Y which extends the recent result of V. Kiss. Then we propose similar characterizations for equi-Bare 1 families of functions. Also, using related ideas, we give game characterizations of Baire measurable and Lebesgue measurable functions. PubDate: 2024-11-01 DOI: 10.1007/s00153-024-00922-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: Abstract For a free filter F on \(\omega \) , endow the space \(N_F=\omega \cup \{p_F\}\) , where \(p_F\not \in \omega \) , with the topology in which every element of \(\omega \) is isolated whereas all open neighborhoods of \(p_F\) are of the form \(A\cup \{p_F\}\) for \(A\in F\) . Spaces of the form \(N_F\) constitute the class of the simplest non-discrete Tychonoff spaces. The aim of this paper is to study them in the context of the celebrated Josefson–Nissenzweig theorem from Banach space theory. We prove, e.g., that, for a filter F, the space \(N_F\) carries a sequence \(\langle \mu _n:n\in \omega \rangle \) of normalized finitely supported signed measures such that \(\mu _n(f)\rightarrow 0\) for every bounded continuous real-valued function f on \(N_F\) if and only if \(F^*\le _K{\mathcal {Z}}\) , that is, the dual ideal \(F^*\) is Katětov below the asymptotic density ideal \({\mathcal {Z}}\) . Consequently, we get that if \(F^*\le _K{\mathcal {Z}}\) , then: (1) if X is a Tychonoff space and \(N_F\) is homeomorphic to a subspace of X, then the space \(C_p^*(X)\) of bounded continuous real-valued functions on X contains a complemented copy of the space \(c_0\) endowed with the pointwise topology, (2) if K is a compact Hausdorff space and \(N_F\) is homeomorphic to a subspace of K, then the Banach space C(K) of continuous real-valued functions on K is not a Grothendieck space. The latter result generalizes the well-known fact stating that if a compact Hausdorff space K contains a non-trivial convergent sequence, then the space C(K) is not Grothendieck. PubDate: 2024-11-01 DOI: 10.1007/s00153-024-00920-x
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: Abstract We study the relations between two consequences of the Continuum Hypothesis discovered by Wacław Sierpiński, concerning uniform continuity of continuous functions and uniform convergence of sequences of real-valued functions, defined on subsets of the real line of cardinality continuum. PubDate: 2024-11-01 DOI: 10.1007/s00153-024-00925-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: Abstract We give several new equivalences of NIP for formulas and new proofs of known results using Talagrand (Ann Probab 15:837–870, 1987) and Haydon et al. (in: Functional Analysis Proceedings, The University of Texas at Austin 1987–1989, Lecture Notes in Mathematics, Springer, New York, 1991). We emphasize that Keisler measures are more complicated than types (even in the NIP context), in an analytic sense. Among other things, we show that for a first order theory T and a formula \(\phi (x,y)\) , the following are equivalent: \(\phi \) has NIP with respect to T. For any global \(\phi \) -type p(x) and any model M, if p is finitely satisfiable in M, then p is generalized DBSC definable over M. In particular, if M is countable, then p is DBSC definable over M. (Cf. Definition 3.7, Fact 3.8.) For any global Keisler \(\phi \) -measure \(\mu (x)\) and any model M, if \(\mu \) is finitely satisfiable in M, then \(\mu \) is generalized Baire-1/2 definable over M. In particular, if M is countable, \(\mu \) is Baire-1/2 definable over M. (Cf. Definition 3.9.) For any model M and any Keisler \(\phi \) -measure \(\mu (x)\) over M, $$\begin{aligned} \sup _{b\in M}\Big \frac{1}{k}\sum _{i=1}^k\phi (p_i,b)-\mu (\phi (x,b))\Big \rightarrow 0, \end{aligned}$$ for almost every \((p_i)\in S_{\phi }(M)^{\mathbb N}\) with the product measure \(\mu ^{\mathbb N}\) . (Cf. Theorem 4.4.) Suppose moreover that T is countable and NIP, then for any countable model M, the space of global M-finitely satisfied types/measures is a Rosenthal compactum. (Cf. Theorem 5.1.) PubDate: 2024-06-03 DOI: 10.1007/s00153-024-00932-7