Abstract: Publication date: Available online 20 January 2020Source: Annals of Pure and Applied LogicAuthor(s): Alejandro PovedaAbstractLet cof(μ)=μ and κ be a supercompact cardinal with μ

Abstract: Publication date: Available online 7 January 2020Source: Annals of Pure and Applied LogicAuthor(s): Ivan GeorgievAbstractWe consider the complexity of the integration operator on real functions with respect to the subrecursive class M2. We prove that the definite integral of a uniformly M2-computable analytic real function with M2-computable limits is itself M2-computable real number. We generalise this result to integrals with parameters and with varying limits. As an application, we show that the Euler-Mascheroni constant is M2-computable.

Abstract: Publication date: Available online 7 January 2020Source: Annals of Pure and Applied LogicAuthor(s): Darío GarcíaAbstractWe introduce the concept of o-asymptotic classes of finite structures, melding ideas coming from 1-dimensional asymptotic classes and o-minimality. Along with several examples and non-examples of these classes, we present some classification theory results of their infinite ultraproducts: Every infinite ultraproduct of structures in an o-asymptotic class is superrosy of Uþ-rank 1, and NTP2 (in fact, inp-minimal).

Abstract: Publication date: Available online 13 December 2019Source: Annals of Pure and Applied LogicAuthor(s): Alexander G. Melnikov, Victor L. Selivanov, Mars M. YamaleevAbstractIn the late 1980s, Selivanov used typed Boolean combinations of arithmetical sets to extend the Ershov hierarchy beyond Δ20 sets. Similar to the Ershov hierarchy, Selivanov's fine hierarchy {Σγ}γ

Abstract: Publication date: Available online 28 November 2019Source: Annals of Pure and Applied LogicAuthor(s): Slavko Moconja, Predrag TanovićAbstractWe introduce the notions of stationarily ordered types and theories; the latter generalizes weak o-minimality and the former is a relaxed version of weak o-minimality localized at the locus of a single type. We show that forking, as a binary relation on elements realizing stationarily ordered types, is an equivalence relation and that each stationarily ordered type in a model determines some order-type as an invariant of the model. We study weak and forking non-orthogonality of stationarily ordered types, show that they are equivalence relations and prove that invariants of non-orthogonal types are closely related. The techniques developed are applied to prove that in the case of a binary, stationarily ordered theory with fewer than 2ℵ0 countable models, the isomorphism type of a countable model is determined by a certain sequence of invariants of the model. In particular, we confirm Vaught's conjecture for binary, stationarily ordered theories.

Abstract: Publication date: Available online 13 November 2019Source: Annals of Pure and Applied LogicAuthor(s): Masato FujitaAbstractWe define and investigate a uniformly locally o-minimal structure of the second kind in this paper. All uniformly locally o-minimal structures of the second kind have local monotonicity, which is a local version of monotonicity theorem of o-minimal structures. We also demonstrate a local definable cell decomposition theorem for definably complete uniformly locally o-minimal structures of the second kind. We define dimension of a definable set and investigate its basic properties when the given structure is a locally o-minimal structure which admits local definable cell decomposition.

Abstract: Publication date: Available online 11 November 2019Source: Annals of Pure and Applied LogicAuthor(s): Manuela Busaniche, José Luis Castiglioni, Noemí LubomirskyAbstractConsider any subvariety of BL-algebras generated by a single BL-chain which is the ordinal sum of the standard MV-algebra on [0,1] and a basic hoop H. We present a geometrical characterization of elements in the finitely generated free algebra of each of these subvarieties. In this characterization there is a clear insight of the role of the regular and dense elements of the generating chain. As an application, we analyze maximal and prime filters in the free algebra.

Abstract: Publication date: Available online 6 November 2019Source: Annals of Pure and Applied LogicAuthor(s): Nebojša Ikodinović, Zoran Ognjanović, Aleksandar Perović, Miodrag RaškovićAbstractWe study propositional probabilistic logics (LPP–logics) with probability operators of the form P≥r (“the probability is at least r”) with σ–additive semantics. For regular infinite cardinals κ and λ, the probabilistic logic LPPκ,λ has λ propositional variables, allows conjunctions of

Abstract: Publication date: Available online 4 November 2019Source: Annals of Pure and Applied LogicAuthor(s): Sato KentaroAbstractWe introduce a new axiom called inductive dichotomy, a weak variant of the axiom of inductive definition, and analyze the relationships with other variants of inductive definition and with related axioms, in the general second order framework, including second order arithmetic, second order set theory and higher order arithmetic. By applying these results to the investigations on the determinacy axioms, we show the following. (i) Clopen determinacy is consistency-wise strictly weaker than open determinacy in these frameworks, except second order arithmetic; this is an enhancement of Schweber–Hachtman separation of open and clopen determinacy into the consistency-wise separation. (ii) Hausdorff–Kuratowski hierarchy of differences of opens is faithfully reflected by the hierarchy of consistency strengths of corresponding parameter-free determinacies in the aforementioned frameworks; this result is valid also in second order arithmetic only except clopen determinacy.

Abstract: Publication date: Available online 7 October 2019Source: Annals of Pure and Applied LogicAuthor(s): J.P. AguileraAbstractTakeuti introduced an infinitary proof system for determinate logic and showed that for transitive models of Zermelo-Fraenkel set theory with the Axiom of Dependent Choice that contain all reals, the cut-elimination theorem is equivalent to the Axiom of Determinacy, and in particular contradicts the Axiom of Choice.We consider variants of Takeuti's theorem without assuming the failure of the Axiom of Choice. For instance, we show that if one removes atomic formulae of infinite arity from the language of Takeuti's proof system, then cut elimination is equivalent to a determinacy hypothesis provable, e.g., in ZFC + “there are infinitely many Woodin cardinals.” A slight extension of the proof system admits cut elimination for countable sequents under the same assumptions.A simple modification of the proof system yields analogs of the results above for the Axiom of Real Determinacy and uncountably many Woodin cardinals.

Abstract: Publication date: Available online 10 September 2019Source: Annals of Pure and Applied LogicAuthor(s): Moritz Müller, Ján PichAbstractWe ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length n. In 1995 Razborov showed that many can be proved in PV1, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small n of doubly logarithmic order. It is open whether PV1 proves known lower bounds in succinct formalizations for n of logarithmic order. We give such proofs in APC1, an extension of PV1 formalizing probabilistic polynomial time reasoning: for parity and AC0, for mod q and AC0[p] (only for n slightly smaller than logarithmic), and for k-clique and monotone circuits. We also formalize Razborov and Rudich's natural proof barrier.We ask for short propositional proofs of circuit lower bounds expressed succinctly by propositional formulas of size nO(1) or at least much smaller than the 2O(n) size of the common “truth table” formula. We discuss two such expressions: one via feasible functions witnessing errors of circuits, and one via the anticheckers of Lipton and Young 1994. Our APC1 formalizations yield conditional upper bounds for the succinct formulas obtained by witnessing: we get short Extended Frege proofs from general circuit lower bounds expressed by the common “truth-table” formulas. We also show how to construct in quasipolynomial time propositional proofs of quasipolynomial size tautologies expressing AC0[p] quasipolynomial size lower bounds; these proofs are in Jeřábek's system WF.

Abstract: Publication date: Available online 5 September 2019Source: Annals of Pure and Applied LogicAuthor(s): Gabriel Conant, Kyle GannonAbstractIn NIP theories, generically stable Keisler measures can be characterized in several ways. We analyze these various forms of “generic stability” in arbitrary theories. Among other things, we show that the standard definition of generic stability for types coincides with the notion of a frequency interpretation measure. We also give combinatorial examples of types in NSOP theories that are finitely approximated but not generically stable, as well as ϕ-types in simple theories that are definable and finitely satisfiable in a small model, but not finitely approximated. Our proofs demonstrate interesting connections to classical results from Ramsey theory for finite graphs and hypergraphs.