Recent zbMATH articles in MSC 03https://zbmath.org/atom/cc/032021-11-25T18:46:10.358925ZWerkzeugBook review of: J. Lenhard (ed.) and M. Carrier (ed.), Mathematics as a tool. Tracing new roles of mathematics in the scienceshttps://zbmath.org/1472.000282021-11-25T18:46:10.358925Z"Muthsam, H."https://zbmath.org/authors/?q=ai:muthsam.herbert-jReview of [Zbl 1372.00052].Book review of: A. Pietruszczak, Foundations of the theory of parthood. A study of mereologyhttps://zbmath.org/1472.000372021-11-25T18:46:10.358925Z"Tkaczyk, Marcin"https://zbmath.org/authors/?q=ai:tkaczyk.marcinReview of [Zbl 1461.03003].Cantor and continuityhttps://zbmath.org/1472.010142021-11-25T18:46:10.358925Z"Kanamori, Akihiro"https://zbmath.org/authors/?q=ai:kanamori.akihiroThe author describes in detail Cantor's work on sets and number as well as his struggle for forming the concepts of limit and continuity. Especially, he wants to point out the changes and transmutations of this changes as a result of the progress of mathematics, and compelled by this progress. Moreover, he intends to demonstrate the difficulties of this process of conceptualization and to show the arduous way to our basis of transfinite numbers, continuity and set theory.
For the entire collection see [Zbl 1454.01002].Ludwig Wittgenstein. Vienna edition. Vol. 7. Synopsis of manuscript volumes I--IV. Edited by Michael Nedohttps://zbmath.org/1472.010282021-11-25T18:46:10.358925Z"Wittgenstein, Ludwig"https://zbmath.org/authors/?q=ai:wittgenstein.ludwigVolume 7 of the Vienna edition of the writings of Ludwig Wittgenstein presents a reconstruction and critical edition of typescripts TS 208 and TS 210 containing the synopsis of the manuscript volumes I to IV edited in Vol.\ 1 and 2 of the Vienna edition. The synopsis was dictated in 1930. The remarks were then used to rearrange cuttings from the typescripts. TS 208, e.g., was reworked to TS 209 which became the textual basis for Rush Rhees' 1964 edition of the book [\textit{L. Wittgenstein}, Philosophische Bemerkungen. Oxford: Blackwell (1964)]. The volume is introduced by the editor giving details on the historical circumstances of the formation of the synopsis and the way Wittgenstein worked with it. It ends with a usefull stemma, relating manuscripts, typescripts, cuttings and editions to one another (p.\ XVI).\par The synopsis edited in this volume contains comprehensive observations, remarks and problems (questions) concerning the philosophy of mathematics and logic, among them the role of mathematics, the epistemology of mathematics, the nature of mathematical objects, the function of symbols, rule following, Brouwer's intuitionism, and further topics. The volume helps to reconstruct the development of Wittgenstein's thought from his early \textit{Tractatus logico-philosophicus} to his later work.Handbook of computability and complexity in analysishttps://zbmath.org/1472.030012021-11-25T18:46:10.358925Z"Brattka, Vasco"https://zbmath.org/authors/?q=ai:brattka.vasco"Hertling, Peter"https://zbmath.org/authors/?q=ai:hertling.peter-hPublisher's description: Computable analysis is the modern theory of computability and complexity in analysis that arose out of Turing's seminal work in the 1930s. This was motivated by questions such as: which real numbers and real number functions are computable, and which mathematical tasks in analysis can be solved by algorithmic means?
Nowadays this theory has many different facets that embrace topics from computability theory, algorithmic randomness, computational complexity, dynamical systems, fractals, and analog computers, up to logic, descriptive set theory, constructivism, and reverse mathematics. In recent decades computable analysis has invaded many branches of analysis, and researchers have studied computability and complexity questions arising from real and complex analysis, functional analysis, and the theory of differential equations, up to (geometric) measure theory and topology.
This handbook represents the first coherent cross-section through most active research topics on the more theoretical side of the field. It contains 11 chapters grouped into parts on computability in analysis; complexity, dynamics, and randomness; and constructivity, logic, and descriptive complexity. All chapters are written by leading experts working at the cutting edge of the respective topic. Researchers and graduate students in the areas of theoretical computer science and mathematical logic will find systematic introductions into many branches of computable analysis, and a wealth of information and references that will help them to navigate the modern research literature in this field.
The articles of this volume will be reviewed individually.Probabilistic extensions of various logical systemshttps://zbmath.org/1472.030022021-11-25T18:46:10.358925Z"Ognjanović, Zoran"https://zbmath.org/authors/?q=ai:ognjanovic.zoranPublisher's description: The contributions in this book survey results on combinations of probabilistic and various other classical, temporal and justification logical systems. Formal languages of these logics are extended with probabilistic operators. The aim is to provide a systematic overview and an accessible presentation of mathematical techniques used to obtain results on formalization, completeness, compactness and decidability. The book will be of value to researchers in logic and it can be used as a supplementary text in graduate courses on non-classical logics.
The articles of this volume will be reviewed individually.The semantic conception of logic. Essays on consequence, invariance, and meaninghttps://zbmath.org/1472.030032021-11-25T18:46:10.358925Z"Sagi, Gil"https://zbmath.org/authors/?q=ai:sagi.gil"Woods, Jack"https://zbmath.org/authors/?q=ai:woods.jackPublisher's description: This collection of new essays presents cutting-edge research on the semantic conception of logic, the invariance criteria of logicality, grammaticality, and logical truth. Contributors explore the history of the semantic tradition, starting with Tarski, and its historical applications, while central criticisms of the tradition, and especially the use of invariance criteria to explain logicality, are revisited by the original participants in that debate. Other essays discuss more recent criticism of the approach, and researchers from mathematics and linguistics weigh in on the role of the semantic tradition in their disciplines. This book will be invaluable to philosophers and logicians alike.
The articles of mathematical interest will be reviewed individually.Judgements and truth. Essays in honour of Jan Woleńskihttps://zbmath.org/1472.030042021-11-25T18:46:10.358925Z"Schumann, Andrew"https://zbmath.org/authors/?q=ai:schumann.andrewPublisher's description: Jan Woleński is known due to his works on epistemological aspects of logic and his systematization of semantic truth theory.
He became the successor and the worthy continuer of prominent Polish logicians: Alfred Tarski and Kazimierz Ajdukiewicz. This volume is collected on the 80th anniversary of Woleński's birth and draws together new research papers devoted to judgments and truth.
These papers take measure of the scope and impact of Woleński's views on truth conceptions, and present new contributions to the field of philosophy and logic.
The articles of this volume will be reviewed individually.Connexive restricted quantificationhttps://zbmath.org/1472.030052021-11-25T18:46:10.358925Z"Francez, Nissim"https://zbmath.org/authors/?q=ai:francez.nissimThis paper deals with \textit{connexive logics}, which are logics in which the implication is, unlike classical implication, connecting the antecdent and the succedent, much like relevant implication does. The questions asked regard the meaning \textit{restricted quantification} (RQ\(_{\forall}\)), \(\forall x. \phi\rightarrow \psi\) has, where \(\rightarrow\) is the implication of one of three connexive logics, the first two described in [\textit{H. Wansing}, in: Advances in modal logic. Vol. 5. Selected papers from the 5th conference (AiML 2004), Manchester, UK, September 9--11, 2004. London: King's College Publications. 367--383 (2005; Zbl 1107.03017)] and in [\textit{G. Priest}, Topoi 18, No. 2, 141--148 (1999; Zbl 0946.03011)], and the third is the author's variation of the second one, together with an investigation of the kind of connexive class theory (RQ\(_{\forall}\)) is inducing. While the application of (RQ\(_{\forall}\)) in the the first two connexive logics does not meet the yardstick for a connexive class theory, it does meet that yardstick for the author's own proposal of a connexive logic.Confused terms in ordinary languagehttps://zbmath.org/1472.030062021-11-25T18:46:10.358925Z"Frost-Arnold, Greg"https://zbmath.org/authors/?q=ai:frost-arnold.greg"Beebe, James R."https://zbmath.org/authors/?q=ai:beebe.james-rAs the authors themselves declare at the end of the Introduction, ``this article is a contribution to the growing sub-field David Ripley has dubbed `experimental philosophical logic''' (p. 199). Accordingly, the core of the article relies on a survey of logico-semantical accounts of ``confused terms'' in ordinary language followed by an empirical study designed to assess the formal theories against their ability to describe how humans actually deal with confused terms.
The subject-matter which is investigated from both the logical and the experimental perspectives is the presence of confused terms in sentences taken from ordinary language. In the Introduction, the authors aptly circumscribe the topic to the following more precise question: ``What semantics should be used for sentences containing multiply-signifying names?'' (p. 199), where ``multiply-signifying names'' are defined as ``any linguistic item that grammatically or syntactically behaves like a proper name, yet conflates distinct things'' (p. 198).
In order to apply both logical and experimental methods to this classical problem in philosophy of language, the authors introduce the following story (p. 198) as a case-study for the subsequent discussions: ``Fred goes to the pet store and purchases an ant colony in a box. The owner of the pet store tells Fred that every ant colony comes with many small ants but only one big ant. After Fred gets home and begins unpacking his new purchase, he says ``I'm going to call the big ant in this colony `Charley.''' Unbeknownst to Fred, however, there are actually two large ants in this colony. Call them `Ant A' and `Ant B.'''
In Section 2, without attempting to be exhaustive, the authors survey several semantic proposals for `Charley' intended as a multiply-signifying term. The proposals, articulated under the labels of ``neutral'', ``negative'', and ``positive'' semantics are: weak and strong Kleene schemes in their internal and external negation versions (neutral semantics); Burge semantics (negative); supervaluational, contextualist, and ``at-least-one'' semantics in both its Lewis-Priest's and McLeish's versions (positive). For each proposal, the authors briefly reports pros and cons taken from the logico-philosophical literature.
In Section 3, the authors present the empirical study, based on a test constituted by eleven sentences which involve the term `Charley' and which are presumed to make corresponding statements about Fred's story. The participants -- a population of about two hundred undergraduates -- are asked to assign to each sentence a judgment selected among the following: ``True'', ``False'', ``Both true and false'', ``Neither true nor false'', ``Don't know/can't tell''. Some other instructions are given to the participants, sophisticating a bit the experiment.
After describing the experiment, the authors move on to elaborate the results. First, they discuss, for each one of the semantic proposals surveyed in Section 2, which answers to the test should be expected according to the theory. The theoretical answers are then contrasted with those given by the participants to the test, drawing some conclusions about how accurately each formal theory predicts ordinary speakers' judgements. They conclude that the results seem to favour positive over negative or neutral semantics.
This is a very-well-structured article contributing by a specific experiment a topic in philosophical logic where there is no abundance of empirical data. The empirical study is cleverly and purposefully designed and certainly provides interesting findings though, probably, not strong enough to draw definite conclusions on the subject, as the authors themselves honestly warn the reader (see, for instance, footnote 27 on page 217).Hintikka and the functions of logichttps://zbmath.org/1472.030072021-11-25T18:46:10.358925Z"Link, Montgomery"https://zbmath.org/authors/?q=ai:link.montgomerySummary: Jaakko Hintikka (1929--2015) points out the power of Skolem functions to affect both what there is and what we know. There is a tension in his presupposition that these functions actually extend the realm of logic. He claims to have resolved the tension by ``reconstructing constructivism'' along epistemological lines, instead of by a typical ontological construction; however, after the collapse of the distinction between first and second order, that resolution is not entirely satisfactory. Still, it does throw light on the conceptual analysis Hintikka proposes.Prospects for a theory of decyclinghttps://zbmath.org/1472.030082021-11-25T18:46:10.358925Z"Litland, Jon Erling"https://zbmath.org/authors/?q=ai:litland.jon-erlingThe solutions presented in the author's [``Grounding, explanation, and the limit of internality'', Philos. Review 124, No. 4, 481--532 (2015; \url{doi:10.1215/00318108-3147011})] and \textit{K. Fine} [Notre Dame J. Formal Logic 51, 97--118 (2010; Zbl 1256.03034)] to a range of puzzles about what grounds what belong to the family of what the author refers to as ``decycling'' solutions. Puzzles of a self-referential nature, one of which is called (S1) in this paper and is used as a test case, ``present more serious challenges to such decycling solutions than has previously been realized. The goal of this paper is to examine to what extent these challenges can be met.'' First, a number of general constraints that any reasonable decycling solution has to meet are identified. Any solution that meets all the constraints agrees on the treatment of (S1). However, the existing decycling solutions in [loc. cit.] fail to meet some of those constraints. On the other hand, the author constructs a solution that meets all those constraints and shows that that particular solution is not only not unique, but that there are uncountably many distinct solutions that meet the constraints. This ``can be interpreted to mean that the notion of ground is indeterminate.''Existential graphs on nonplanar surfaceshttps://zbmath.org/1472.030092021-11-25T18:46:10.358925Z"Oostra, Arnold"https://zbmath.org/authors/?q=ai:oostra.arnoldSummary: Existential graphs on the plane constitute a two-dimensional representation of classical logic, in which a Jordan curve stands for the negation of its inside. In this paper we propose a program to develop existential Alpha graphs, which correspond to propositional logic, on various surfaces. The geometry of each manifold determines the possible Jordan curves on it, leading to diverse interpretations of negation. This may open a way for appointing a ``natural'' logic to any surface.To Peirce Hintikka's thoughtshttps://zbmath.org/1472.030102021-11-25T18:46:10.358925Z"Pietarinen, Ahti-Veikko"https://zbmath.org/authors/?q=ai:pietarinen.ahti-veikkoSummary: This paper compares Peirce's and Hintikka's logical philosophies and identifies a cross-section of similarities in their thoughts in the areas of action-first epistemology, pragmaticist meaning, philosophy of science, and philosophy of logic and mathematics.Perspectives on the logical study of languagehttps://zbmath.org/1472.030112021-11-25T18:46:10.358925Z"Hintikka, Jaakko"https://zbmath.org/authors/?q=ai:hintikka.jaakkoSummary: Published originally as [``Loogisen kielentutkimuksen näköaloja'', Ajatus 19, 81--96 (1956)], the following piece by \textit{J. Hintikka} is the first essay he published in his mother tongue of Finnish. It is seen to provide both a state-of-the-art review of current topics emerging in the philosophy of language in the mid-1950, as well as outlines of \textsc{Hintikka}'s own evaluation of major theses of that era, in particular those of \textsc{Quine}'s and \textsc{Wittgenstein}'s concerning language use. \textsc{Hintikka} evaluates contributions that the logical study of language use can make to the solving of philosophical questions. Published in 1956 in \textit{Ajatus: The Yearbook of the Philosophical Society of Finland}, \textsc{Hintikka}'s essay served to introduce these topical issues to the Finnish-speaking audience soon after the original works had appeared in print. It also puts the theses into the perspectives of \textsc{Hintikka}'s own fledgling logical philosophy. One can see the germs of game-theoretical semantics is his comments on \textsc{Wittgenstein}'s notion of a language-game, and his remarks on general habits of action anticipate the importance of strategic rules in \textsc{Hintikka}'s mature, inquiry-led and `action-first' epistemology. This is manifest in \textsc{Hintikka}'s characteristic approach to the methodology of philosophy of science and mathematics as an attempt to understand the nature of scientific and mathematical practices and operations through the logical analysis of their central concepts. Topics indicated below thus became the hallmarks of \textsc{Hintikka}'s next sixty years of work, which saw the development of a range of logical methods by which language and its use can be studied, and in particular in such a way that progress can be made in solving problems of genuinely philosophical nature that one encounters across various fields of science. This piece was very briefly summarized in English by \textit{A. Salomaa} [``K. Jaakko J. Hintikka. Loogisen kielentutkimuksen näköaloja (On the logical study of language). Ajatus, vol. 19 (1956), pp. 81--96.'', J. Symb. Log. 28, No. 2, 165 (1963; \url{doi:10.2307/2271600})] and it is translated from the original Finnish by \textsc{Jukka Nikulainen} and \textsc{Ahti-Veikko Pietarinen}.Open sets in computability theory and reverse mathematicshttps://zbmath.org/1472.030122021-11-25T18:46:10.358925Z"Normann, Dag"https://zbmath.org/authors/?q=ai:normann.dag"Sanders, Sam"https://zbmath.org/authors/?q=ai:sanders.samThe authors examine the effects of using a higher-order definition of open sets on the strength of several theorems of analysis, from viewpoints of reverse mathematics and higher-order computability theory. The higher-order framework is that of [\textit{U. Kohlenbach}, Lect. Notes Log. 21, 281--295 (2005; Zbl 1097.03053)]. In the higher-order setting, an open set in a complete separable metric space can be represented by its type \(1 \to 0\) (third order) characteristic function. Theorems analyzed include the Heine-Borel theorem for countable and for uncountable covers, the Cantor-Bendixson theorem, the perfect set theorem, the Urysohn lemma, the Tietze extension theorem, and the Baire category theorem. When formulated using characteristic function based open sets, these theorems tend to be strong, often not provable in \(\mathbb Z ^\omega _2 \equiv \cup_k \Pi^1_k {\text -}\mathsf{CA}_0^\omega\), and with no realizers computable from a functional of type 2. In the last section, alternative representations for open sets are considered, leading to the definition of a converting functional \(\Delta\) related to hyperarithmetic functions.On logic embeddings and Gödel's Godhttps://zbmath.org/1472.030132021-11-25T18:46:10.358925Z"Benzmüller, Christoph"https://zbmath.org/authors/?q=ai:benzmuller.christoph-e"Paleo, Bruno Woltzenlogel"https://zbmath.org/authors/?q=ai:woltzenlogel-paleo.brunoSummary: We have applied an elegant and flexible logic embedding approach to verify and automate a prominent philosophical argument: the ontological argument for the existence of God. In our ongoing computer-assisted study, higher-order automated reasoning tools have made some interesting observations, some of which were previously unknown.
For the entire collection see [Zbl 1327.68013].Hintikka, free logician. Singular terms in world lines semanticshttps://zbmath.org/1472.030142021-11-25T18:46:10.358925Z"Fontaine, Matthieu"https://zbmath.org/authors/?q=ai:fontaine.matthieuSummary: The combination of quantifiers with a semantics for epistemic operators in a modal framework is one of the major contributions of Hintikka in intensional logic. Hintikka's starting point is his diagnosis of the failure of existential generalization and the substitution of identicals in terms of referential multiplicity. In this paper, I introduce Hintikka as a free logician. Indeed, Hintikka's first-order epistemic logic is grounded on a logic free of ontological presuppositions with respect to singular terms. It is also a logic free of presuppositions of uniqueness of reference. After having focused on the use of quantifiers and singular terms in Hintikka's epistemic logic, I discuss some consequences from a semantico-logical perspective, but also from a philosophical one. By arguing against the so-called contingent \textit{a priori} truths defended by Kripke, I conclude with a proposal in favour of Hintikka's non-rigid interpretation of proper names.On modal logics arising from scattered locally compact Hausdorff spaceshttps://zbmath.org/1472.030152021-11-25T18:46:10.358925Z"Bezhanishvili, Guram"https://zbmath.org/authors/?q=ai:bezhanishvili.guram"Bezhanishvili, Nick"https://zbmath.org/authors/?q=ai:bezhanishvili.nick"Lucero-Bryan, Joel"https://zbmath.org/authors/?q=ai:lucero-bryan.joel-gregory"van Mill, Jan"https://zbmath.org/authors/?q=ai:van-mill.janSummary: For a topological space \(X\), let \(\mathsf{L}(X)\) be the modal logic of \(X\) where \(\square\) is interpreted as interior (and hence \(\diamond\) as closure) in \(X\). It was shown in [the first author and \textit{J. Harding}, Order 29, No. 2, 271--292 (2012; Zbl 1259.03030)] that the modal logics \textsf{S4}, \textsf{S4.1}, \textsf{S4.2}, \textsf{S4.1.2}, \textsf{S4.Grz}, \(\mathsf{S4} . \mathsf{Grz}_n\) (\(n \geq 1\)), and their intersections arise as \(\mathsf{L}(X)\) for some Stone space \(X\). We give an example of a scattered Stone space whose logic is not such an intersection. This gives an affirmative answer to [loc. cit., Question 6.2]. On the other hand, we show that a scattered Stone space that is in addition hereditarily paracompact does not give rise to a new logic; namely we show that the logic of such a space is either \textsf{S4.Grz} or \(\mathsf{S4} . \mathsf{Grz}_n\) for some \(n \geq 1\). In fact, we prove this result for any scattered locally compact open hereditarily collectionwise normal and open hereditarily strongly zero-dimensional space.Rules with parameters in modal logic. II.https://zbmath.org/1472.030162021-11-25T18:46:10.358925Z"Jeřábek, Emil"https://zbmath.org/authors/?q=ai:jerabek.emilThis paper deals with the computational complexity of admissibility and unifiability with parameters in transitive modal logics. It is a continuation of the author's paper [ibid. 166, No. 9, 881--933 (2015; Zbl 1408.03015)], which the author strongly suggests to read. Thus we confine ourselves to quote from the present paper's Abstract: ''We completely classify the complexity of unifiability or inadmissibility in any clx (i.e., cluster-extensible) logic as being complete for one of \(\Sigma^{\mathrm{exp}}_{2}\), NEXP, coNEXP, PSPACE or \(\Pi^{p}_{2}\). [\dots] Our upper bounds are specific to clx logics, but we also include similar results for logics of bounded depth and width. In contrast, our lower bounds are very general: they apply each to a class of all transitive logics whose frames allow occurrence of certain finite subframes. [\dots] We prove PSCACE-hardness of derivability for a broad class of transitive logics that include all logics with a disjunctive property.''Labelled tableau systems for some subintuitionistic logicshttps://zbmath.org/1472.030172021-11-25T18:46:10.358925Z"Ma, Minghui"https://zbmath.org/authors/?q=ai:ma.minghuiSummary: Labelled tableau systems are developed for subintuitionistic logics \(\mathbf{wK}_\sigma, \mathbf{wKT}_\sigma\) and \(\mathbf{wK4}_\sigma\). These subintuitionistic logics are embedded into corresponding normal modal logics. Hintikka's model systems are applied to prove the completeness of labelled tableau systems. The finite model property, decidability and disjunction property are obtained by labelled tableau method.Modal logic axioms valid in quotient spaces of finite CW-complexes and other families of topological spaceshttps://zbmath.org/1472.030182021-11-25T18:46:10.358925Z"Nogin, Maria"https://zbmath.org/authors/?q=ai:nogin.maria-s"Xu, Bing"https://zbmath.org/authors/?q=ai:xu.bing.1Summary: In this paper we consider the topological interpretations of \(\mathcal{L}_\square\), the classical logic extended by a ``box'' operator \(\square\) interpreted as interior. We present extensions of S4 that are sound over some families of topological spaces, including particular point topological spaces, excluded point topological spaces, and quotient spaces of finite CW-complexes.The normal and self-extensional extension of Dunn-Belnap logichttps://zbmath.org/1472.030192021-11-25T18:46:10.358925Z"Avron, Arnon"https://zbmath.org/authors/?q=ai:avron.arnon\medskip: A logic is \textit{self-extensional} if it has the \textit{replacement property}; a logic \textit{has an implication} if it enjoys the \textit{ classical deduction theorem}. The main result of the paper is to show that (up to the choice of the primitive connectives) there is exactly one self-extensional 4-valued expansion with an implication of Belnap-Dunn 4-valued logic (cf. Theorem 4.6). This expansion is built as follows. Let \( \{t,f,\top ,\bot \}\) be the set of truth-values of Belnap and Dunn's matrix \( \mathcal{FOUR}\). And let \(T=\{t,\top \}\) and \(F=\{f,\bot \}\). The author expands \(\mathcal{FOUR}\) by adding a conditional function \(I\) defined for all formulas \(A,B\), as follows: \(T\in I(A\rightarrow B)\) iff \(T\notin I(A)\) or \(T\in I(B)\); \(F\in I(A\rightarrow B)\) iff \(F\notin I(A)\) and \(F\in I(B)\).
Using the techniques of \textit{A. Avron} et al. [Theory of effective propositional paraconsistent logics. London: College Publications (2018; Zbl 1448.03001)], the author provides a Gentzen-type system (with cut-elimination) and then a deductively equivalent Hilbert-style system, \(H_{\mathrm{SE4}}\). It has to be remarked that a (definitionally) Hilbert-type system equivalent to \(H_{\mathrm{SE4}}\), PŁ4, had previously been defined in the literature (cf. [\textit{J. M. Méndez} and \textit{G. Robles}, Log. Univers. 9, No. 4, 501--522 (2015; Zbl 1373.03026)]): \(H_{\mathrm{SE4}}\) is defined with \( \rightarrow ,\wedge ,\vee \) and \(\lnot \), while PŁ4 is defined only with \( \rightarrow ,\lnot \)). Moreover, in [\textit{N. Kamide} and \textit{H. Omori}, Lect. Notes Comput. Sci. 10455, 79--93 (2017; Zbl 06810774)], it is noted that the logics \(\mathrm{BD}_{+}\), FDEP and PM4N (cf. [\textit{M. De} and \textit{H. Omori}, Stud. Log. 103, No. 4, 825--851 (2015; Zbl 1373.03029); \textit{J.-Y. Béziau}, Log. Anal., Nouv. Sér. 54, No. 213, 109--121 (2011; Zbl 1228.03003)], respectively) are equivalent to PŁ4, and so, to \(H_{\mathrm{SE4}}\).Noncontractive classical logichttps://zbmath.org/1472.030202021-11-25T18:46:10.358925Z"Rosenblatt, Lucas"https://zbmath.org/authors/?q=ai:rosenblatt.lucas-danielSummary: One of the most fruitful applications of substructural logics stems from their capacity to deal with self-referential paradoxes, especially truth-theoretic paradoxes. Both the structural rules of contraction and the rule of cut play a crucial role in typical paradoxical arguments. In this paper I address a number of difficulties affecting noncontractive approaches to paradox that have been discussed in the recent literature. The situation was roughly this: if you decide to go substructural, the nontransitive approach to truth offers a lot of benefits that are not available in the noncontractive account. I sketch a noncontractive theory of truth that has these benefits. In particular, it has both a proof- and a model-theoretic presentation, it can be extended to a first-order language, and it retains every classically valid inference.Semilinear substructural logics with the finite embeddability propertyhttps://zbmath.org/1472.030212021-11-25T18:46:10.358925Z"Wang, Sanmin"https://zbmath.org/authors/?q=ai:wang.sanminSummary: Three semilinear substructural logics \({\mathbf{HpsUL}}_\omega ^*\), \({\mathbf{UL}}_\omega \) and \({\mathbf{IUL}}_\omega \) are constructed. Then the completeness of \({ \mathbf{UL}}_\omega \) and \({\mathbf{IUL}}_\omega \) with respect to classes of finite \(\mathbf{UL}\) and \(\mathbf{IUL}\)-algebras, respectively, is proved. Algebraically, non-integral \({\mathbf{UL}}_\omega \) and \({\mathbf{IUL}}_\omega \)-algebras have the finite embeddability property, which gives a characterization for finite \({\mathbf{UL}}\) and \({\mathbf{IUL}}\)-algebras.Skolemization and Herbrand theorems for lattice-valued logicshttps://zbmath.org/1472.030222021-11-25T18:46:10.358925Z"Cintula, Petr"https://zbmath.org/authors/?q=ai:cintula.petr"Diaconescu, Denisa"https://zbmath.org/authors/?q=ai:diaconescu.denisa"Metcalfe, George"https://zbmath.org/authors/?q=ai:metcalfe.georgeSummary: Skolemization and Herbrand theorems are obtained for first-order logics based on algebras with a complete lattice reduct and operations that are monotone or antitone in each argument. These lattice-valued logics, defined as consequence relations on inequations between formulas, typically lack properties underlying automated reasoning in classical first-order logic such as prenexation, deduction theorems, or reductions from consequence to satisfiability. Skolemization and Herbrand theorems for the logics therefore take various forms, applying to the left or right of consequences, and restricted classes of inequations. In particular, in the presence of certain witnessing conditions, they admit sound ``parallel'' Skolemization procedures where a strong quantifier is removed by introducing a finite disjunction or conjunction of formulas with new function symbols. A general expansion lemma is also established that reduces consequence in a lattice-valued logic between inequations containing only strong occurrences of quantifiers on the left and weak occurrences on the right to consequence between inequations in the corresponding propositional logic. If propositional consequence is finitary, this lemma yields a Herbrand theorem for the logic.Tree-like proof systems for finitely-many valued non-deterministic consequence relationshttps://zbmath.org/1472.030232021-11-25T18:46:10.358925Z"Pawlowski, Pawel"https://zbmath.org/authors/?q=ai:pawlowski.pawelAn abstract framework for sequent-based proof systems for non-deterministic logics were constructed in [\textit{A. Avron} and \textit{L. Lev}, J. Log. Comput. 15, No. 3, 241--261 (2005; Zbl 1070.03010)]. The current paper presents an abstract framework for constructing tree-like (tableaux) proof systems for finitely-many valued deterministic and non-deterministic consequence relations. This framework is quite general and there is a mechanical procedure for finding a counter-model for any invalid inference which is an advantage over sequent-based systems. The framework is illustrated for the paraconsistent weak Kleene logic PKW [\textit{S. Bonzio} et al., Stud. Log. 105, No. 2, 253--297 (2017; Zbl 1417.03191)] as a deterministic example and for the non-deterministic examples CLuN [\textit{D. Batens} and \textit{K. De Clercq}, Log. Anal., Nouv. Sér. 47, No. 185--188, 227--257 (2004; Zbl 1078.03024)] and BAT [the author, Log. J. IGPL 26, No. 1, 96--108 (2018; Zbl 07072099); the author and \textit{R. Urbaniak}, Rev. Symb. Log. 11, No. 2, 207--223 (2018; Zbl 06914162)]. It is shown that the proof systems generated by the framework are complete.Deciding the Bernays-Schoenfinkel fragment over bounded difference constraints by simple clause learning over theorieshttps://zbmath.org/1472.030242021-11-25T18:46:10.358925Z"Bromberger, Martin"https://zbmath.org/authors/?q=ai:bromberger.martin"Fiori, Alberto"https://zbmath.org/authors/?q=ai:fiori.alberto"Weidenbach, Christoph"https://zbmath.org/authors/?q=ai:weidenbach.christophSummary: Simple clause learning over theories SCL(T) is a decision procedure for the Bernays-Schoenfinkel fragment over bounded difference constraints BS(BD). The BS(BD) fragment consists of clauses built from first-order literals without function symbols together with simple bounds or difference constraints, where for the latter it is required that the variables of the difference constraint are bounded from below and above. The SCL(T) calculus builds model assumptions over a fixed finite set of fresh constants. The model assumptions consist of ground foreground first-order and ground background theory literals. The model assumptions guide inferences on the original clauses with variables. We prove that all clauses generated this way are non-redundant. As a consequence, expensive testing for tautologies and forward subsumption is completely obsolete and termination with respect to a fixed finite set of constants is a consequence. We prove SCL(T) to be sound and refutationally complete for the combination of the Bernays Schoenfinkel fragment with any compact theory. Refutational completeness is obtained by enlarging the set of considered constants. For the case of BS(BD) we prove an abstract finite model property such that the size of a sufficiently large set of constants can be fixed a priori.
For the entire collection see [Zbl 1471.68017].Compositional satisfiability solving in separation logichttps://zbmath.org/1472.030252021-11-25T18:46:10.358925Z"Le, Quang Loc"https://zbmath.org/authors/?q=ai:le.quang-locSummary: We introduce a novel decision procedure to the satisfiability problem in array separation logic combined with general inductively defined predicates and arithmetic. Our proposal differentiates itself from existing works by solving satisfiability through compositional reasoning. First, following Fermat's method of infinite descent, it infers for every inductive definition a ``base'' that precisely characterises the satisfiability. It then utilises the base to derive such a base for any formula where these inductive predicates reside in. Especially, we identify an expressive decidable fragment for the compositionality. We have implemented the proposal in a tool and evaluated it over challenging problems. The experimental results show that the compositional satisfiability solving is efficient and our tool is effective and efficient when compared with existing solvers.
For the entire collection see [Zbl 1471.68017].First-order definitions of subgraph isomorphism through the adjacency and order relationshttps://zbmath.org/1472.030262021-11-25T18:46:10.358925Z"Grigoryan, Oleg"https://zbmath.org/authors/?q=ai:grigoryan.oleg"Makarov, Mikhail"https://zbmath.org/authors/?q=ai:makarov.mikhail-v"Zhukovskii, Maksim"https://zbmath.org/authors/?q=ai:zhukovskii.maximGiven a graph \(F\), let \(\mathcal S(F)\) be the graphical property of having \(F\) as a (not necessarily induced) subgraph. If \(\sim\) is the vertex adjacency relation symbol, let \(\Sigma = \{ \sim, < \}\) be the signature for linearly ordered finite graphs. A first-order sentence \(\varphi\) of signature \(\Sigma\) defines \(\mathcal S(F)\) if, for any graph \(G\), and any linear ordering of \(G\)'s vertices, if \(G'\) is \(G\) expanded by that linear ordering, then \(G' \models \varphi\) iff \(G\) has \(F\) as a (not necessarily induced) subgraph. Let \(D_< (F)\) be the minimum quantifier depth of any \(\Sigma\)-sentence defining \(\mathcal S(F)\) and let \(W_< (F)\) be the minimum number of variables of any \(\Sigma\)-sentence defining \(\mathcal S(F)\).
The primary result of this paper is that if \(F\) is a tree of \(\ell\) vertices, then \(D_< (F) \leq \ell/2 + \lceil \log_2 (\ell + 2) \rceil - 1\); they also observe that \(W_< (F) \leq \ell/2 + 2\). In addition, using Fraïsse-Ehrenfeucht games, \(D_<(F)\) is computed for each graph \(F\) of order less than \(5\).
There are some typos, so readers should take care.Finite coverability propertyhttps://zbmath.org/1472.030272021-11-25T18:46:10.358925Z"Botur, Michal"https://zbmath.org/authors/?q=ai:botur.michal"Broušek, Martin"https://zbmath.org/authors/?q=ai:brousek.martinSummary: In this article we present a new characterization of the class \(\mathrm{HSP}_U(\mathcal {K})\) using a condition analogous to the finite embeddability property.Super modelshttps://zbmath.org/1472.030282021-11-25T18:46:10.358925Z"Hintikka, Jaakko"https://zbmath.org/authors/?q=ai:hintikka.jaakkoSummary: Published originally in [in: I. Patoluoto, E. Saarinen, P. Stenman (eds.), Vexing questions: an urnful of essays in honour of Veikko Rantala on the occasion of his fiftieth birthday. Reports from the Department of Philosophy. Helsinki: University of Helsinki. 12--18 (1983)].Definable relations in finite-dimensional subspace lattices with involutionhttps://zbmath.org/1472.030292021-11-25T18:46:10.358925Z"Herrmann, Christian"https://zbmath.org/authors/?q=ai:herrmann.christian"Ziegler, Martin"https://zbmath.org/authors/?q=ai:ziegler.martinSummary: For a large class of finite dimensional inner product spaces \(V\), over division \(*\)-rings \(F\), we consider definable relations on the subspace lattice \(\mathsf{L}(V)\) of \(V\), endowed with the operation of taking orthogonals. In particular, we establish translations between the relevant first order languages, in order to associate these relations with definable and invariant relations on \(F\)-focussing on the quantification type of defining formulas. As an intermediate structure we consider the \(*\)-ring \(\mathsf{R}(V)\) of endomorphisms of \(V\), thereby identifying \(\mathsf{L}(V)\) with the lattice of right ideals of \(\mathsf{R}(V)\), with the induced involution. As an application, model completeness of \(F\) is shown to imply that of \(\mathsf{R}(V)\) and \(\mathsf{L}(V)\).A new look at interpretability and saturationhttps://zbmath.org/1472.030302021-11-25T18:46:10.358925Z"Malliaris, M."https://zbmath.org/authors/?q=ai:malliaris.maryanthe-elizabeth"Shelah, S."https://zbmath.org/authors/?q=ai:shelah.saharonSummary: We investigate the interpretability ordering \(\trianglelefteq^\ast\) using generalized Ehrenfeucht-Mostowski models. This gives a new approach to proving inequalities and investigating the structure of types.Equational theories of fieldshttps://zbmath.org/1472.030312021-11-25T18:46:10.358925Z"Martin-Pizarro, Amador"https://zbmath.org/authors/?q=ai:martin-pizarro.amador"Ziegler, Martin"https://zbmath.org/authors/?q=ai:ziegler.martin.1Let \(T\) be a first-order theory. A formula \(\varphi(x;y)\), with a given partition of free variables into \(x\) and \(y\), is called an \textit{equation} if, in every model \(M\) of \(T\), the collection of finite intersections of instances \(\varphi(x;a)\) with \(a\in M\) has the descending chain condition. The theory \(T\) is said to be \textit{equational} if every formula is equivalent to a Boolean combination of equations modulo \(T\). Equationality is a strengthening of stability. For example, the theory of an equivalence relation with infinitely many infinite classes, the theory of algebraically closed fields, and the theory of separably closed fields of characteristic \(p>0\) and finite imperfection degree are equational.
In the paper under review, it is proven that the theory of separably closed fields of arbitrary imperfection degree and the theory of proper pairs of algebraically closed fields are equational.
Thus, the authors are able to deal with theories where the models (as fields) have infinite linear dimension over a definable subfield. Indeed, if \(K\) is a separably closed field of characteristic \(p\) and infinite imperfection degree, then \(K\) has infinite linear dimension over the definable subfield \(K^p\). Similarly, if \((K; +, \cdot, C)\) is a proper pair of algebraically closed fields then the linear dimension of \(K\) over \(C\) is infinite.Coxeter groups and abstract elementary classes: the right-angled casehttps://zbmath.org/1472.030322021-11-25T18:46:10.358925Z"Hyttinen, Tapani"https://zbmath.org/authors/?q=ai:hyttinen.tapani"Paolini, Gianluca"https://zbmath.org/authors/?q=ai:paolini.gianlucaSummary: We study classes of right-angled Coxeter groups with respect to the strong submodel relation of a parabolic subgroup. We show that the class of all right-angled Coxeter groups is not smooth and establish some general combinatorial criteria for such classes to be abstract elementary classes (AECs), for them to be finitary, and for them to be tame. We further prove two combinatorial conditions ensuring the strong rigidity of a right-angled Coxeter group of arbitrary rank. The combination of these results translates into a machinery to build concrete examples of AECs satisfying given model-theoretic properties. We exhibit the power of our method by constructing three concrete examples of finitary classes. We show that the first and third classes are nonhomogeneous and that the last two are tame, uncountably categorical, and axiomatizable by a single \(L_{\omega_1,\omega}\)-sentence. We also observe that the isomorphism relation of any countable complete first-order theory is \(\kappa \)-Borel reducible (in the sense of generalized descriptive set theory) to the isomorphism relation of the theory of right-angled Coxeter groups whose Coxeter graph is an infinite random graph.Fields with automorphism and valuationhttps://zbmath.org/1472.030332021-11-25T18:46:10.358925Z"Beyarslan, Özlem"https://zbmath.org/authors/?q=ai:beyarslan.ozlem"Hoffmann, Daniel Max"https://zbmath.org/authors/?q=ai:hoffmann.daniel-max"Onay, Gönenç"https://zbmath.org/authors/?q=ai:onay.gonenc"Pierce, David"https://zbmath.org/authors/?q=ai:pierce.david-a|pierce.david-mIn this short paper, the authors study problems around companionability of the theories involving a valuation and an automorphism on a field. They obtain two results which clarify the situation under the assumption of ``freeness'', that is the authors assume that there is no interaction between the valuation and the automorphism in question. These results are as follows.
1. The model companion of the theory of the aforementioned fields with valuation and automorphism exists.
2. A natural candidate, which is the theory of models of ACFA equipped with a valuation, is NOT this model companion.A simple criterionhttps://zbmath.org/1472.030342021-11-25T18:46:10.358925Z"Blossier, Thomas"https://zbmath.org/authors/?q=ai:blossier.thomas"Martin-Pizarro, Amador"https://zbmath.org/authors/?q=ai:martin-pizarro.amadorSummary: In this article, we mimic the proof of the simplicity of the theory ACFA of generic difference fields in order to provide a criterion, valid for certain theories of pure fields and fields equipped with operators, which shows that a complete theory is simple whenever its definable and algebraic closures are controlled by an underlying stable theory.Definable \(V\)-topologies, Henselianity and NIPhttps://zbmath.org/1472.030352021-11-25T18:46:10.358925Z"Halevi, Yatir"https://zbmath.org/authors/?q=ai:halevi.yatir"Hasson, Assaf"https://zbmath.org/authors/?q=ai:hasson.assaf"Jahnke, Franziska"https://zbmath.org/authors/?q=ai:jahnke.franziskaIn the article under review, the authors prove that every \(t\)-Henselian NIP valued infinite field admits at most one definable V-topology, and as a consequence, they show that a positive answer to Shelah's conjecture implies the Henselianity conjecture, which states that every definable valuation on an infinite NIP field must be Henselian.
Shelah's conjecture states that an infinite NIP field is either separably closed, real closed or it can be equipped with a non-trivial definable Henselian valuation (cf. [\textit{F. Jahnke} and \textit{J. Koenigsmann}, J. Symb. Log. 80, No. 1, 85--99 (2015; Zbl 1372.03078)]). Johnson has affirmatively proved the conjecture when the field is dp-minimal, that is, of dp-rank \(1\). A crucial part of his proof was to provide the field with a definable V-topology, that is, a definable topology induced by either an archimedean absolute value or by a valuation. Furthermore, Johnson showed that the V-topology is canonical and hence unique.
In this paper, the authors generalise the uniqueness of the V-topology for all \(t\)-Henselian NIP valued fields, by showing (Theorem 5.3) that they admit at most one definable V-topology. Recall that a valued field is \(t\)-Henselian if for every natural number \(n\ge 2\), the collection of tuples \((a_0, \ldots, a_{n-1})\) such that the polynomial
\[
T^n +a_{n-1}T^{n-1}+\cdots+a_0
\]
has a simple root in \(K\) is an open subset of \(K^n\).
As a by-product of their result, the authors show in Theorem 6.3 that a positive answer to Shelah's conjecture yields a positive answer to the Henselianity conjecture, which states that every definable valuation on an infinite NIP field must be Henselian. In [\textit{W. Johnson}, Ann. Pure Appl. Logic 172, No. 6, Article ID 102949, 33 p. (2021; Zbl 07333020)], the latter conjecture has been answered positively whenever the field has positive characteristic.Some properties of the polynomially bounded o-minimal expansions of the real field and of some quasianalytic local ringshttps://zbmath.org/1472.030362021-11-25T18:46:10.358925Z"Berraho, M."https://zbmath.org/authors/?q=ai:berraho.mouradLet \(\mathcal E_n\) be the ring of germs of smooth functions in \(\mathbb R^n\) at the origin. The Borel map is a map from \(\mathcal E_n\) onto the ring of formal power series \(\mathbb R[[x_1,\ldots, x_n]]\). The image \(\widehat{f}\) of an \(f \in \mathcal E_n\) under the Borel map is defined as the infinite Taylor expansion of \(f\) at the origin. This paper discusses subrings \(\mathcal C\) of \(\mathcal E_n\) when the restrictions of the Borel map to \(\mathcal C\) are bijective. Its results are as follows:
Let \(\mathcal D_n\) be of the subring of \(\mathcal E_n\) consisting of the germs of real analytic functions definable in a polymonially bounded o-minimal expansion of the field of reals. The Weierstrass division and preparation theorems for \(\mathcal D_2\) hold true when the restriction of the Borel map to \(\mathcal D_1\) is bijective.
When a subring \(\mathcal C\) of \(\mathcal E_1\) satisfies the technical condition called the stability under monomial division and the restriction of the Borel map to it is bijective, the local ring \(\mathcal C\) with the \((x_1)\)-adic topology is complete.Structure theorems in tame expansions of o-minimal structures by a dense sethttps://zbmath.org/1472.030372021-11-25T18:46:10.358925Z"Eleftheriou, Pantelis E."https://zbmath.org/authors/?q=ai:eleftheriou.pantelis-e"Günaydin, Ayhan"https://zbmath.org/authors/?q=ai:gunaydin.ayhan"Hieronymi, Philipp"https://zbmath.org/authors/?q=ai:hieronymi.philippThe present paper studies properties of definable sets and functions in so-called ``tame`` expansions of o-minimal groups in the language \(L\) by a dense set \(P\). The authors prove structure theorems for these expansions in terms of cones and large dimension: a decomposition of a definable set into a finite union of cones; every definable map is given by an \(L\)-definable map off a subset of the domain of smaller large dimension; and the group operation around generic elements of a definable group is given by an \(L\)-definable map.The Marker-Steinhorn theorem via definable linear ordershttps://zbmath.org/1472.030382021-11-25T18:46:10.358925Z"Walsberg, Erik"https://zbmath.org/authors/?q=ai:walsberg.erikSummary: We give a short proof of the Marker-Steinhorn theorem for o-minimal expansions of ordered groups. The key tool is Ramakrishnan's classification of definable linear orders in such structures.On the degree structure of equivalence relations under computable reducibilityhttps://zbmath.org/1472.030392021-11-25T18:46:10.358925Z"Ng, Keng Meng"https://zbmath.org/authors/?q=ai:ng.kengmeng"Yu, Hongyuan"https://zbmath.org/authors/?q=ai:yu.hongyuanSummary: We study the degree structure of the \(\omega \)-c.e., \(n\)-c.e., and \(\Pi_1^0\) equivalence relations under the computable many-one reducibility. In particular, we investigate for each of these classes of degrees the most basic questions about the structure of the partial order. We prove the existence of the greatest element for the \(\omega \)-c.e. and \(n\)-computably enumerable equivalence relations. We provide computable enumerations of the degrees of \(\omega \)-c.e., \(n\)-c.e., and \(\Pi^0_1\) equivalence relations. We prove that for all the degree classes considered, upward density holds and downward density fails.Incompleteness and jump hierarchieshttps://zbmath.org/1472.030402021-11-25T18:46:10.358925Z"Lutz, Patrick"https://zbmath.org/authors/?q=ai:lutz.patrick"Walsh, James"https://zbmath.org/authors/?q=ai:walsh.james-bruce|walsh.james-a|walsh.james-jThe paper is devoted to the investigation of the relationship between Gödel's second incompleteness theorem and the well-foundedness of jump hierarchies. An alternative proof of the classical Spector theorem is given -- the proof uses Gödel's second incompleteness theorem instead of the theory of admissible ordinals. A semantic version of the second incompleteness theorem, originally due to \textit{C. Mummert} and \textit{S. G. Simpson} [J. Symb. Log. 69, No. 2, 612--616 (2004; Zbl 1075.03031)], is derived from this result. Some results on the calculation of the ranks of reals in this well-founded relation from Spector's theorem are provided as well.Solovay reducibility and continuityhttps://zbmath.org/1472.030412021-11-25T18:46:10.358925Z"Kumabe, Masahiro"https://zbmath.org/authors/?q=ai:kumabe.masahiro"Miyabe, Kenshi"https://zbmath.org/authors/?q=ai:miyabe.kenshi"Mizusawa, Yuki"https://zbmath.org/authors/?q=ai:mizusawa.yuki"Suzuki, Toshio"https://zbmath.org/authors/?q=ai:suzuki.toshioSolovay reducibility is introduced by Solovay to investigate left-c.e. random reals. In the paper under review, the author gives a characterization of Solovay reducibility from the analytical point of view. I.e., roughly speaking, for left-c.e. reals \(\alpha\) and \(\beta\), \(\alpha\) is Solovay reducible to \(\beta\) if and only if there is a partial computable Lipschitz function \(f:[s,\beta]\to \mathbb{R}\), where \(s\) is a rational point, so that there is an increasing sequence rationals \(\{r_n\}_{n}\) from \([s, \beta]\) with \(r_n\to \beta\) for which \(f(r_n)\to \alpha\) and \(\forall nf(r_n)\leq \alpha\). They also introduce a weaker reducibility, called quasi-Solovay reducibility, and found its characerterization via Hölder continuity.Computable copies of \(\ell^{p^1}\)https://zbmath.org/1472.030422021-11-25T18:46:10.358925Z"McNicholl, Timothy H."https://zbmath.org/authors/?q=ai:mcnicholl.timothy-hSummary: Suppose \(p\) is a computable real so that \(p\geqslant 1\). It is shown that the halting set can compute a surjective linear isometry between any two computable copies of \(\ell^p\) . It is also shown that this result is optimal in that when \(p\neq 2\) there are two computable copies of \(\ell^p\) with the property that any oracle that computes a linear isometry of one onto the other must also compute the halting set. Thus, \(\ell^p\) is \(\Delta_2^0\)-categorical and is computably categorical if and only if \(p = 2\) . It is also demonstrated that there is a computably categorical Banach space that is not a Hilbert space. These results hold in both the real and complex case.Distributive Aronszajn treeshttps://zbmath.org/1472.030432021-11-25T18:46:10.358925Z"Brodsky, Ari Meir"https://zbmath.org/authors/?q=ai:brodsky.ari-meir"Rinot, Assaf"https://zbmath.org/authors/?q=ai:rinot.assafSummary: \textit{S. Ben-David} and \textit{S. Shelah} [Isr. J. Math. 53, 93--96 (1986; Zbl 0617.03026)] proved that if $\lambda $ is a singular strong-limit cardinal and $2^\lambda =\lambda ^+$, then $\square ^*_\lambda $ entails the existence of a normal $\lambda $-distributive $\lambda ^+$-Aronszajn tree. Here, it is proved that the same conclusion remains valid after replacing the hypothesis $\square ^*_\lambda $ by $\square (\lambda ^+,{<}\lambda)$. As $\square (\lambda ^+,{<}\lambda)$ does not impose a bound on the order-type of the witnessing clubs, our construction is necessarily different from that of Ben-David and Shelah [loc. cit.], and instead uses walks on ordinals augmented with club guessing. A major component of this work is the study of postprocessing functions and their effect on square sequences. A byproduct of this study is the finding that for $\kappa $ regular uncountable, $\square (\kappa)$ entails the existence of a partition of $\kappa $ into $\kappa $ many fat sets. When contrasted with a classical model of Magidor, this shows that it is equiconsistent with the existence of a weakly compact cardinal that $\omega_2$ cannot be split into two fat sets.A note on set mappings: an extension of results of Hajnal and Máté under GCHhttps://zbmath.org/1472.030442021-11-25T18:46:10.358925Z"Komjáth, Péter"https://zbmath.org/authors/?q=ai:komjath.peterSummary: A set mapping $f:[\lambda]^r\to \mathcal{P}(\lambda)$ is of order $(\mu_0,\mu_1,\dots ,\mu_r)$ if for $s\in [\lambda]^r$ increasingly enumerated as $\{\alpha_0,\alpha_1,\dots ,\alpha_{r-1}\}$ we have $|f(s)\cap (\alpha_i,\alpha_{i+1})| < \mu_{i+1}$ for $-1\leq i\leq r$ where $\alpha_{-1}=0$ and $\alpha_r=\lambda $. If GCH holds, $1\leq r < \omega $, $\kappa $ is an infinite cardinal, and $f:[\kappa ^{+r}]^r\to \mathcal{P}(\kappa ^{+r})$ is a set mapping of order $(\kappa ,\kappa ^+,\dots ,\kappa ^{+r})$, then there is a free set of order type $\kappa ^++r-1$. This is sharp in the sense that no free set of larger type can be guaranteed, and if any of the $\mu_i$'s is increased then even a free set of cardinality $\aleph_\omega $ cannot be guaranteed (for any $\kappa $).There may be no minimal non-\(\sigma\)-scattered linear ordershttps://zbmath.org/1472.030452021-11-25T18:46:10.358925Z"Lamei Ramandi, Hossein"https://zbmath.org/authors/?q=ai:ramandi.hossein-lamei"Moore, Justin Tatch"https://zbmath.org/authors/?q=ai:moore.justin-tatchSummary: In this paper, we demonstrate that it is consistent, relative to the existence of a supercompact cardinal, that there is no linear order which is minimal with respect to being non-\(\delta\)-scattered. This shows that a theorem of \textit{R. Laver} [Ann. Math. (2) 93, 89--111 (1971; Zbl 0208.28905)], which asserts that the class of \(\delta\)-scattered linear orders is well quasi-ordered, is sharp. We also prove that \(\mathrm{PFA}^{+}\) implies that every non-\(\delta\)-scattered linear order either contains a real type, an Aronszajn type, or a ladder system indexed by a stationary subset of \(\omega_1\), equipped with either the lexicographic or reverse lexicographic order. Our work immediately implies that CH is consistent with ``no Aronszajn tree has a base of cardinality \(\aleph_1\).'' This gives an affirmative answer to a problem due to Baumgartner.On the existence of skinny stationary subsetshttps://zbmath.org/1472.030462021-11-25T18:46:10.358925Z"Matsubara, Yo"https://zbmath.org/authors/?q=ai:matsubara.yo"Sakai, Hiroshi"https://zbmath.org/authors/?q=ai:sakai.hiroshi"Usuba, Toshimichi"https://zbmath.org/authors/?q=ai:usuba.toshimichiSummary: \textit{Y. Matsubara} and \textit{T. Usuba} [J. Symb. Log. 78, No. 2, 667--680 (2013; Zbl 1275.03142)] introduced the notion of skinniness and its variants for subsets of \(\mathcal{P}_\kappa \lambda\) and showed that the existence of skinny stationary subsets of \(\mathcal{P}_\kappa \lambda\) is related to large cardinal properties of ideals over \(\mathcal{P}_\kappa \lambda\) and to Jensen's diamond principle on \(\lambda\). In this paper, we study the existence of skinny stationary sets in more detail.Diagonalising an ultrafilter and preserving a $P$-pointhttps://zbmath.org/1472.030472021-11-25T18:46:10.358925Z"Mildenberger, Heike"https://zbmath.org/authors/?q=ai:mildenberger.heikeSummary: With Ramsey-theoretic methods we show: It is consistent that there is a forcing that diagonalises one ultrafilter over $\omega $ and preserves another ultrafilter.Derived topologies on ordinals and stationary reflectionhttps://zbmath.org/1472.030482021-11-25T18:46:10.358925Z"Bagaria, Joan"https://zbmath.org/authors/?q=ai:bagaria.joanSummary: We study the transfinite sequence of topologies on the ordinal numbers that is obtained through successive closure under Cantor's derivative operator on sets of ordinals, starting from the usual interval topology. We characterize the non-isolated points in the \( \xi \)th topology as those ordinals that satisfy a strong iterated form of stationary reflection, which we call \( \xi \)-simultaneous-reflection. We prove some properties of the ideals of non-\( \xi \)-simultaneous-stationary sets and identify their tight connection with indescribable cardinals. We then introduce a new natural notion of \( \Pi ^1_\xi \)-indescribability, for any ordinal \( \xi \), which extends to the transfinite the usual notion of \( \Pi ^1_n\)-indescribability, and prove that in the constructible universe \( L\), a regular cardinal is \( (\xi +1)\)-simultaneously-reflecting if and only if it is \( \Pi ^1_\xi \)-indescribable, a result that generalizes to all ordinals \( \xi \) previous results of \textit{R. B. Jensen} [Ann. Math. Logic 4, 229--308 (1972; Zbl 0257.02035)] in the case \( \xi =2\), and \textit{J. Bagaria} et al. [Isr. J. Math. 208, 1--11 (2015; Zbl 1371.03069)] in the case \( \xi =n\). This yields a complete characterization in \( L\) of the non-discreteness of the \( \xi \)-topologies, both in terms of iterated stationary reflection and in terms of indescribability.Reducibility of equivalence relations arising from nonstationary ideals under large cardinal assumptionshttps://zbmath.org/1472.030492021-11-25T18:46:10.358925Z"Asperó, David"https://zbmath.org/authors/?q=ai:aspero.david"Hyttinen, Tapani"https://zbmath.org/authors/?q=ai:hyttinen.tapani"Kulikov, Vadim"https://zbmath.org/authors/?q=ai:kulikov.vadim"Moreno, Miguel"https://zbmath.org/authors/?q=ai:moreno.miguelSummary: Working under large cardinal assumptions such as supercompactness, we study the Borel reducibility between equivalence relations modulo restrictions of the nonstationary ideal on some fixed cardinal \(\kappa \). We show the consistency of \(E^{\lambda^{++},\lambda^{++}}_{\lambda\text{-}\text{club}} \), the relation of equivalence modulo the nonstationary ideal restricted to \(S^{\lambda^{++}}_{\lambda}\) in the space \((\lambda^{++})^{\lambda^{++}}\), being continuously reducible to \(E^{2,\lambda^{++}}_{\lambda^+\text{-}\text{club}} \), the relation of equivalence modulo the nonstationary ideal restricted to \(S^{\lambda^{++}}_{\lambda^+}\) in the space \(2^{\lambda^{++}}\). Then we show that for \(\kappa\) ineffable \(E^{2,\kappa}_{\operatorname{reg}} \), the relation of equivalence modulo the nonstationary ideal restricted to regular cardinals in the space \(2^{\kappa}\) is \({\Sigma_1^1}\)-complete. We finish by showing that, for \(\Pi_2^1\)-indescribable \(\kappa \), the isomorphism relation between dense linear orders of cardinality \(\kappa\) is \({\Sigma_1^1}\)-complete.The bi-embeddability relation for countable abelian groupshttps://zbmath.org/1472.030502021-11-25T18:46:10.358925Z"Calderoni, Filippo"https://zbmath.org/authors/?q=ai:calderoni.filippo"Thomas, Simon"https://zbmath.org/authors/?q=ai:thomas.simon-rSummary: We analyze the complexity of the bi-embeddability relations for countable torsion-free abelian groups and for countable torsion abelian groups.Haar null and Haar meager sets: a survey and new resultshttps://zbmath.org/1472.030512021-11-25T18:46:10.358925Z"Elekes, Márton"https://zbmath.org/authors/?q=ai:elekes.marton"Nagy, Donát"https://zbmath.org/authors/?q=ai:nagy.donatThis is a~survey of results about Haar null sets in Polish groups. The notion of a~Haar measure zero set is well defined in locally compact groups although a~Haar measure is not unique. This notion can be generalized for non-locally compact groups although the Haar measure cannot be generalized for groups that are not locally compact. Two such generalizations are considered: the notion of a~Haar null set and the notion of a~generalized Haar null set. Another notion of smallness considered in the paper is the notion of a~Haar meager set. The Haar meager sets were defined in the literature as a~topological counterpart to the Haar null sets. Every Haar meager set is meager but there are Polish groups in which the converse is not true. However, in locally compact Polish groups the Haar meager sets coincide with the meager sets. All these notions define translation invariant \(\sigma\)-ideals of sets. A~number of characterizations of these notions are presented in the survey. The authors present several results by which they discuss the possibility of generalizations of the following theorems for non-locally compact Polish groups: Fubini's theorem, Kuratowski-Ulam theorem, the Steinhaus theorem, the countable chain condition, and a~decomposition into a~Haar null set and a~Haar meager set. They present a~brief outlook of applications of Haar null sets in various fields of mathematics.Absoluteness theorems for arbitrary Polish spaceshttps://zbmath.org/1472.030522021-11-25T18:46:10.358925Z"Mejía, Diego Alejandro"https://zbmath.org/authors/?q=ai:mejia.diego-alejandro"Rivera-Madrid, Ismael E."https://zbmath.org/authors/?q=ai:rivera-madrid.ismael-eSummary: By coding Polish metric spaces with metrics on countable sets, we propose an interpretation of Polish metric spaces in models of ZFC and extend Mostowski's classical theorem of absoluteness of analytic sets for any Polish metric space in general. In addition, we prove a general version of Shoenfield's absoluteness theorem.Q-Wadge degrees as free structureshttps://zbmath.org/1472.030532021-11-25T18:46:10.358925Z"Selivanov, Victor"https://zbmath.org/authors/?q=ai:selivanov.victor-lSoon after the notion of Wadge degrees of subsets of \(\omega^\omega\) was introduced, it was generalized to degrees of functions from \(\omega^\omega\) to bqo's. Various sets of such degrees have been described in terms of forests. From those graph-theoretic descriptions, the present paper derives different characterizations that possess a more category-theoretic/universal-algebraic flavor. More specifically, for an arbitrary countable bpo, the author examines various initial segments, specified by levels of the Borel hierarchy, of the Wadge degrees of functions from \(\omega^\omega\) to that bpo. The author shows that these segments are isomorphic to reducts of initial objects of certain categories based upon the category of \(\sigma\)-semilattices.Iterates of \(M_1\)https://zbmath.org/1472.030542021-11-25T18:46:10.358925Z"Zhu, Yizheng"https://zbmath.org/authors/?q=ai:zhu.yizhengSummary: Assume \( \boldsymbol{\Delta}^1_2\)-determinacy. Let \( L_{\kappa _3}[T_2]\) be the admissible closure of the Martin-Solovay tree and let \( M_{1,\infty }\) be the direct limit of all iterates of \( M_1\) via countable trees. We show that \( L_{\kappa _3}[T_2] \cap V_{u_{\omega }} \) is the universe of \( M_{1,\infty } \vert u_{\omega }\).Topological properties of incomparable familieshttps://zbmath.org/1472.030552021-11-25T18:46:10.358925Z"Campero-Arena, G."https://zbmath.org/authors/?q=ai:campero-arena.g"Cancino, J."https://zbmath.org/authors/?q=ai:cancino.jonathan|cancino.johan"Hrušák, M."https://zbmath.org/authors/?q=ai:hrusak.michael"Meza-Alcántara, D."https://zbmath.org/authors/?q=ai:meza-alcantara.david"Miranda-Perea, F. E."https://zbmath.org/authors/?q=ai:miranda-perea.favio-ezequielSummary: We study topological properties of families of mutually incomparable subsets of $\omega $. We say that two subsets $a$ and $b$ of $\omega $ are incomparable if both $a\setminus b$ and $b\setminus a$ are infinite. We raise the question whether there may be an analytic maximal incomparable family and show that (1) it cannot be $K_\sigma $, and (2) every incomparable family with the Baire property is meager. On the other hand, we show that non-meager incomparable families exist in $\mathsf{ZFC}$, while the existence of a non-null incomparable family is consistent. Finally, we show that there are maximal incomparable families which are both meager and null assuming either $\mathfrak r=\mathfrak c$ or the existence of a completely separable MAD family; in particular they exist if $\mathfrak c < \aleph_\omega $. Assuming $\mathsf{CH}$, we can even construct a maximal incomparable family which is concentrated on a countable set, and hence of strong measure zero.On Ramsey choice and partial choice for infinite families of \(n\)-element setshttps://zbmath.org/1472.030562021-11-25T18:46:10.358925Z"Halbeisen, Lorenz"https://zbmath.org/authors/?q=ai:halbeisen.lorenz-j"Tachtsis, Eleftherios"https://zbmath.org/authors/?q=ai:tachtsis.eleftheriosFor \(n \geq 2\), the Ramsey choice \(\mathrm{RC}_n\) is the following weak choice principle ``every infinite set \(x\) has an infinite subset \(y\) such that \([y]^n\) has a choice function'' and \(\mathrm{C}_n^{-}\) is the weak principle ``every infinite family of \(n\)-element sets has an infinite subfamily with a choice function''.
Montenegro showed that for \(n = 2,3,4\), \(\mathrm{RC}_n \rightarrow \mathrm{C}_n^{-}\) and asked for which \(n\) is the implication \(\mathrm{RC}_n \rightarrow \mathrm{C}_n^{-}\) true. Here, the authors obtain various results concerning the connection between \(\mathrm{RC}_n\) and \(\mathrm{C}_n^{-}\). So they show that for \(n=2,3\),
\(\mathrm{RC}_5 + \mathrm{C}_n^{-}\) implies \(\mathrm{C}_5^{-}\) and that \(\mathrm{RC}_5\) implies neither \(\mathrm{C}_2^{-}\) nor \(\mathrm{C}_3^{-}\) in ZF set theory. In order to show their results, they make use of Fraenkel-Mostowski models for ZFA and apply the Pincus transfer theorem to obtain ZF results.
The chain-antichain principle CAC is the following statement: Every infinite partially ordered set has either an infinite chain or an infinite antichain. The authors show that CAC implies neither \(RC_n\) nor \(\mathrm{C}_n^{-}\) in ZF for every \(n\geq 2\).How to have more things by forgetting how to count themhttps://zbmath.org/1472.030572021-11-25T18:46:10.358925Z"Karagila, Asaf"https://zbmath.org/authors/?q=ai:karagila.asaf"Schlicht, Philipp"https://zbmath.org/authors/?q=ai:schlicht.philippSummary: Cohen's first model is a model of Zermelo-Fraenkel set theory in which there is a Dedekind-finite set of real numbers, and it is perhaps the most famous model where the Axiom of Choice fails. We force over this model to add a function from this Dedekind-finite set to some infinite ordinal \(\kappa \). In the case that we force the function to be injective, it turns out that the resulting model is the same as adding \(\kappa\) Cohen reals to the ground model, and that we have just added an enumeration of the canonical Dedekind-finite set. In the case where the function is merely surjective it turns out that we do not add any reals, sets of ordinals, or collapse any Dedekind-finite sets. This motivates the question if there is any combinatorial condition on a Dedekind-finite set \(A\) which characterises when a forcing will preserve its Dedekind-finiteness or not add new sets of ordinals. We answer this question in the case of `Adding a Cohen subset' by presenting a varied list of conditions each equivalent to the preservation of Dedekind-finiteness. For example, \(2^{}A\) is extremally disconnected, or \([A]^< \omega\) is Dedekind-finite.Diagonal supercompact Radin forcinghttps://zbmath.org/1472.030582021-11-25T18:46:10.358925Z"Ben-Neria, Omer"https://zbmath.org/authors/?q=ai:ben-neria.omer"Lambie-Hanson, Chris"https://zbmath.org/authors/?q=ai:lambie-hanson.chris"Unger, Spencer"https://zbmath.org/authors/?q=ai:unger.spencer-tFor several decades, a major open problem in set theory has been the question whether it is consistent that the tree property holds at every regular cardinal \(\kappa>\omega_1\). Results of \textit{E. Specker} [Colloq. Math. 2, 9--12 (1949; Zbl 0040.16703)] and \textit{R. B. Jensen} [Ann. Math. Logic 4, 229--308 (1972; Zbl 0257.02035)] show that, for this question to be answered positively, one would at a minimum need to obtain a model in which both GCH and the weak square principle \(\square^*_\mu\) fail everywhere. In fact, the failure of \(\square^*_\mu\) is equivalent to the nonexistence of special \(\mu^+\)-Aronszajn trees, but this would be a significant step towards the ultimate goal of eliminating all Aronszajn trees. It has turned out that the most difficult aspects of this problem involve the interaction between cardinal arithmetic at singular cardinals and the tree property (or other compactness properties) at their successor (and double successors). The reason for this essentially boils down to the fact that the failure of GCH or SCH is an anticompactness feature, while the tree property (or the failure of forms of \(\square\)) is a compactness property.
In the present paper, the authors start from a supercompact cardinal \(\kappa\) with an inaccessible above and produce a forcing extension in which \(\kappa\) remains inaccessible and has a club of singular cardinals \(\nu\) at which both the singular cardinal hypothesis and \(\square^*_\nu\) fail. The fact that \(\kappa\) remains inaccessible is significant, since their extension can then be cut off at \(\kappa\) to produce a model with a proper class of singular cardinals with the stated properties.
The main forcing utilized is an upgraded version of both the Gitik-Sharon forcing from [\textit{M. Gitik} and \textit{A. Sharon}, Proc. Am. Math. Soc. 136, No. 1, 311--320 (2008; Zbl 1140.03033)] and \textit{D. Sinapova}'s forcing from [J. Symb. Log. 73, No. 4, 1361--1372 (2008; Zbl 1156.03045)]. As a flavour of Radin forcing, it preserves the inaccessibility of \(\kappa\) while adding a club of newly singular strong limit cardinals at which SCH fails. Weak square does in fact hold at some of the points of this club, but the authors show that those points are quite sparse (their complement in \(\kappa\) is a fat stationary set), so a club avoiding them can be added without disrupting the remaining structure.Non-uniformizable sets with countable cross-sections on a given level of the projective hierarchyhttps://zbmath.org/1472.030592021-11-25T18:46:10.358925Z"Kanovei, Vladimir"https://zbmath.org/authors/?q=ai:kanovei.vladimir-g"Lyubetsky, Vassily"https://zbmath.org/authors/?q=ai:lyubetsky.vassily-aSummary: We present a model of set theory in which, for a given $n\ge 2$, there exists a planar non-ROD-uniformizable lightface $\varPi ^{1}_{n}$ set, all of whose vertical cross-sections are countable sets and, more specifically, Vitali classes, while all planar boldface ${\boldsymbol\Sigma}^{1}_{n}$ sets with countable cross-sections are ${\boldsymbol\Delta}^{1}_{n+1}$-uniformizable. Thus it is true in this model that the ROD-uniformization principle for sets with countable cross-sections first fails precisely at a given projective level.Specializing Aronszajn trees with strong axiom A and Halvinghttps://zbmath.org/1472.030602021-11-25T18:46:10.358925Z"Mildenberger, Heike"https://zbmath.org/authors/?q=ai:mildenberger.heike"Shelah, Saharon"https://zbmath.org/authors/?q=ai:shelah.saharonSummary: We construct creature forcings with strong Axiom A that specialize a given Aronszajn tree. We work with tree creature forcing. The creatures that live on the Aronszajn tree are normed and have the halving property. We show that our models fulfill \[\aleph_1=\mathfrak{d}< \operatorname{unif}({\mathcal{M}})=\aleph_2=2^{\omega}.\]Sufficient conditions for the forcing theorem, and turning proper classes into setshttps://zbmath.org/1472.030612021-11-25T18:46:10.358925Z"Holy, Peter"https://zbmath.org/authors/?q=ai:holy.peter"Krapf, Regula"https://zbmath.org/authors/?q=ai:krapf.regula"Schlicht, Philipp"https://zbmath.org/authors/?q=ai:schlicht.philippSummary: We present three natural combinatorial properties for class forcing notions, which imply the forcing theorem to hold. We then show that all known sufficient conditions for the forcing theorem (except for the forcing theorem itself), including the three properties presented in this paper, imply yet another regularity property for class forcing notions, namely that proper classes of the ground model cannot become sets in a generic extension, that is, they do not have set-sized names in the ground model. We then show that over certain models of Gödel-Bernays set theory without the power set axiom, there is a notion of class forcing which turns a proper class into a set, however does not satisfy the forcing theorem. Moreover, we show that the property of not turning proper classes into sets can be used to characterize pretameness over such models of Gödel-Bernays set theory.The Ketonen orderhttps://zbmath.org/1472.030622021-11-25T18:46:10.358925Z"Goldberg, Gabriel"https://zbmath.org/authors/?q=ai:goldberg.gabrielThe Ketonen order \(<_k\) on countably complete ultrafilters on ordinals is defined by : \(U <_k W\) if \(j_W [U]\) is contained in a countably complete ultrafilter \(K\) of \(M_W\) with \(K \cap P ([id]_W) \not= \emptyset\). The author proves that
\begin{itemize}
\item[(1)] for normal ultrafilters, the order is the same as the Mitchell order,
\item[(2)] the order is strict and wellfounded,
\item[(3)] the linearity of the order is equivalent to the author's ultrapower axiom, and
\item[(4)] assuming the ultrapower axiom, the order coincides with Lipschitz reducibility in the sense of generalized descriptive set theory.
\end{itemize}Dowker filters and Magidor forcinghttps://zbmath.org/1472.030632021-11-25T18:46:10.358925Z"Garti, Shimon"https://zbmath.org/authors/?q=ai:garti.shimon"Hayut, Yair"https://zbmath.org/authors/?q=ai:hayut.yairA uniform filter \(K\) on an uncountable regular cardinal \(\sigma\) is a \textit{Dowker filter} if (a) for any \(f : \sigma \rightarrow K\), there are \(\alpha < \beta < \sigma\) with \(\alpha \in f ( \beta)\) and \(\beta \in f (\alpha)\), and (b) for any \(e : \sigma \rightarrow 2\), there is \(g : \sigma \rightarrow K\) with the property that \(e (\alpha) = e (\beta)\) whenever \(\alpha < \beta < \sigma\) are such that \(\alpha \in g ( \beta)\) and \(\beta \in g (\alpha)\). Dowker proved that there is no Dowker filter on \(\omega_1\). The authors establish the following two results.
(A) Suppose that in \(V\), GCH holds and \(\kappa\) is a regular uncountable cardinal. Then in the generic extension obtained by adding \(\kappa^+\) Cohen subsets of \(\kappa\), there is a Dowker filter on \(\kappa^+\).
(B) Suppose that in \(V\), \(\kappa\) is a measurable cardinal of Mitchell order at least \(\omega_1\). Then there is a generic extension in which \(\kappa\) is a strong limit singular cardinal, \(2^\kappa = \kappa^+\) and there is a Dowker filter on \(\kappa^+\).$G_\delta $-topology and compact cardinalshttps://zbmath.org/1472.030642021-11-25T18:46:10.358925Z"Usuba, Toshimichi"https://zbmath.org/authors/?q=ai:usuba.toshimichiSummary: For a topological space $X$, let $X_\delta $ be the space $X$ with the $G_\delta $-topology of $X$. For an uncountable cardinal $\kappa $, we prove that the following are equivalent: (1) $\kappa $ is $\omega_1$-strongly compact. (2) For every compact Hausdorff space $X$, the Lindelöf degree of $X_\delta $ is $\le \kappa $. (3) For every compact Hausdorff space $X$, the weak Lindelöf degree of $X_\delta $ is $\le \kappa $. This shows that the least $\omega_1$-strongly compact cardinal is the supremum of the Lindelöf and the weak Lindelöf degrees of compact Hausdorff spaces with the $G_\delta $-topology. We also prove that the least measurable cardinal is the supremum of the extents of compact Hausdorff spaces with the $G_\delta $-topology. For the square of a Lindelöf space, using a weak $G_\delta $-topology, we prove that the following are consistent: (1) The least $\omega_1$-strongly compact cardinal is the supremum of the (weak) Lindelöf degrees of the squares of regular $T_1$ Lindelöf spaces. (2) The least measurable cardinal is the supremum of the extents of the squares of regular $T_1$ Lindelöf spaces.The nominal/FM Yoneda lemmahttps://zbmath.org/1472.030652021-11-25T18:46:10.358925Z"Crole, R. L."https://zbmath.org/authors/?q=ai:crole.roy-lSummary: This paper explores versions of the Yoneda Lemma in settings founded upon FM sets. In particular, we explore the lemma for three base categories: the category of nominal sets and equivariant functions; the category of nominal sets and all finitely supported functions, introduced in this paper; and the category of FM sets and finitely supported functions. We make this exploration in ordinary, enriched and internal settings. We also show that the finite support of Yoneda natural transformations is a \textit{theorem for free}.Fraïssé's conjecture in \(\Pi_1^1\)-comprehensionhttps://zbmath.org/1472.030662021-11-25T18:46:10.358925Z"Montalbán, Antonio"https://zbmath.org/authors/?q=ai:montalban.antonioOn rudimentarity, primitive recursivity and representabilityhttps://zbmath.org/1472.030672021-11-25T18:46:10.358925Z"Salehi, Saeed"https://zbmath.org/authors/?q=ai:salehi.saeed|salehi.saeed.1In this paper, the author revisits two fundamental questions in classical recursion theory regarding: (i) a natural example of a primtive recursive relation which is not rudimentary (i.e., \(\Delta_0\) or bounded definable), and (ii) a direct proof that weak representability of functions implies their strong representability. The example given in (i) is inspired by Tarski's result that he truth relation of arithmetical sentences is not arithmetically definable. It is simply the \(\Delta_0\)-satisfaction relation, which turns out to not be \(\Delta_0\), but which is primitive recursive. For (ii), the author presents a direct proof, which bypasses the usual detour ``a weakly representable is recursive'' and ``a recursive function is strongly representable.''Differentiating convex functions constructivelyhttps://zbmath.org/1472.030682021-11-25T18:46:10.358925Z"Diener, Hannes"https://zbmath.org/authors/?q=ai:diener.hannes"Hendtlass, Matthew"https://zbmath.org/authors/?q=ai:hendtlass.matthewIn classical mathematics, it has been proven that every convex function \(f(x)\) of one variable is differentiable everywhere except for a countable set. The usual proof is based on the fact that for a convex function, its left derivative is monotonic, and is, thus, continuous everywhere except for a countable set -- so outside this set, \(f(x)\) is differentiable. This proof, however, cannot be extended to the constructive case, since the existence of the left derivative cannot be constructively proven: this existence is equivalent to decidability of equality between real numbers, and no algorithm is possible for deciding whether a constructively given real number is equal to 0. In spite of this negative result about left derivatives, the authors do provide a constructive proof of the convex-functions result: namely, they prove the existence of a sequence \(x_n\) so that a convex function \(f(x)\) is differentiable for all \(x\) which are different from the \(x_i\)'s.
As an auxiliary result, the authors provide an example of a constructively defined monotonic function for which differentiability at any point implies \(a=0\vee a\ne 0\). They also provide an example of a constructively defined convex function for which the existence of the second derivative at any point implies \(a=0\vee a\ne 0\) -- while classically, the second derivative of a convex function exists almost everywhere.Fuzzy \(n\)-fold filters of pseudoresiduated latticeshttps://zbmath.org/1472.030692021-11-25T18:46:10.358925Z"Kadji, Albert"https://zbmath.org/authors/?q=ai:kadji.albert"Lele, Celestin"https://zbmath.org/authors/?q=ai:lele.celestin"Tonga, Marcel"https://zbmath.org/authors/?q=ai:tonga.marcelSummary: Given a pseudoresiduated lattice \(M\) and a lattice \(L\), we introduce and characterize the fuzzy versions of different \(n\)-fold implicative (resp., obstinate, Boolean, normal, and extended involutive) filters of \(M\). Moreover, we study some relationships between these different types of fuzzy \(n\)-fold filters.Representability of Lyndon-Maddux relation algebrashttps://zbmath.org/1472.030702021-11-25T18:46:10.358925Z"Alm, Jeremy F."https://zbmath.org/authors/?q=ai:alm.jeremy-fSummary: In 2016, the author et al. [Rev. Symb. Log. 9, No. 3, 511--521 (2016; Zbl 1392.03060)] defined relation algebras \(\mathfrak {L}(q,n)\) that generalize Roger Lyndon's relation algebras from projective lines, so that \(\mathfrak {L}(q,0)\) is a Lyndon algebra. In that paper, it was shown that if \(q>2304n^2+1\), then \(\mathfrak {L}(q,n)\) is representable, and if \(q<2n\), then \(\mathfrak {L}(q,n)\) is not representable. In the present paper, we reduced this gap by proving that if \(q\geq n(\log n)^{1+\varepsilon }\), then \(\mathfrak {L}(q,n)\) is representable.State hyper equality algebrashttps://zbmath.org/1472.030712021-11-25T18:46:10.358925Z"Cheng, Xiao Yun"https://zbmath.org/authors/?q=ai:cheng.xiaoyun"Wang, Jun Tao"https://zbmath.org/authors/?q=ai:wang.juntaoSummary: By assigning state operators to hyper equality algebras, the concept of state hyper equality algebras is introduced and some related properties of it are provided. Some generated representation of state strong hyper deductive systems are obtained and (maximal, prime) state strong hyper deductive systems are investigated. By means of state regular congruence relation, state operators on quotient hyper equality algebras are induced, and also states on state hyper equality algebras are considered via special state operators.Radicals of prefilters in EQ-algebrashttps://zbmath.org/1472.030722021-11-25T18:46:10.358925Z"Gao, Xiao Li"https://zbmath.org/authors/?q=ai:gao.xiaoli"Xin, Xiao Long"https://zbmath.org/authors/?q=ai:xin.xiaolong"Wang, Jun Tao"https://zbmath.org/authors/?q=ai:wang.juntaoSummary: The crux of the matter of this essay is to explore the radical of a prefilter (\(R(W)\) for short) in EQ-algebras. To begin with, the notion of the radical of a prefilter is defined and \(R(W)\) with the help of an unary formula is characterized. After that, the relations between prefilters and radicals of prefilters are investigated. Finally, the definition of semi-maximal prefilters is given. That a (maximal, implicative, obstinate) prefilter is also a semi-maximal prefilter is obtained.On the finiteness problem for classes of modular latticeshttps://zbmath.org/1472.060072021-11-25T18:46:10.358925Z"Herrmann, Christian"https://zbmath.org/authors/?q=ai:herrmann.christianSummary: The finiteness problem is shown to be unsolvable for any sufficiently large class of modular lattices.How to introduce the connective implication in orthomodular posetshttps://zbmath.org/1472.060082021-11-25T18:46:10.358925Z"Chajda, Ivan"https://zbmath.org/authors/?q=ai:chajda.ivan"Länger, Helmut"https://zbmath.org/authors/?q=ai:langer.helmut-mThe authors use the connective implication \(x \to y\) in an orthomodular poset defined as the set \(\{ x' \lor z \mid z \le x,\ z \le y \}\) (inspired by the definition \(x' \lor (x \land y)\) in orthomodular lattices). They show that this implication with the partial meet operation forms the so-called unsharp residuated poset and, converselly, an unsharp residuated poset with special properties form an orthomodular poset. This correspondence is almost one-to-one (same orthomodular posets are obtained for unsharp residuated posets with unsharp adjoint operations to implication identical on orthogonal couples).States on wEMV-algebrashttps://zbmath.org/1472.060152021-11-25T18:46:10.358925Z"Dvurečenskij, Anatolij"https://zbmath.org/authors/?q=ai:dvurecenskij.anatolijEMV-algebras, introduced by the author and \textit{O. Zahiri} [Fuzzy Sets Syst. 373, 116--148 (2019; Zbl 1423.06048)], is a common generalization of MV-algebras and generalized Boolean algebras. Weak EMV-algebras (wEMV-algebras) is a further generalization of EMV-algebras in a signature extended by a subtraction-like operation \(\ominus\) [the author and \textit{O. Zahiri}, Fuzzy Sets Syst. 418, 101--125 (2021; Zbl 1467.06008)]. States on EMV-algebras were investigated in [the author and \textit{O. Zahiri}, Soft Comput. 23, No. 17, 7513--7536 (2019; Zbl 1418.06008)]. A state on a wEMV-algebra \(M\) is defined differently, as a mapping \(s\) to \([0,1]\) that obeys the condition (\(s(y \ominus x) = s(y) - s(x)\) whenever \(x \ominus y = 0\)) and takes the value 1 on some element. Just as in EMV-algebras, a state on \(M\) is extremal if and only if it is a state-morphism if and only if its kernel is a maximal ideal of \(M\). In contrast to the case of EMV-algebras, not every non-trivial wEMV-algebra has a state, one-to one correspondence is established only between the set of state-morphisms and a set of maximal ideals having a special property, and every state on \(M\) is shown to be a weak limit of a net of convex combinations of state-morphisms only under some conditions.Term algebras of elementarily equivalent atom structureshttps://zbmath.org/1472.060182021-11-25T18:46:10.358925Z"Andréka, Hajnal"https://zbmath.org/authors/?q=ai:andreka.hajnal"Németi, István"https://zbmath.org/authors/?q=ai:nemeti.istvanSummary: We exhibit two relation algebra atom structures such that they are elementarily equivalent but their term algebras are not. This answers Problem 14.19 in \textit{R. Hirsch} and \textit{I. Hodkinson}'s text [Relation algebras by games. Amsterdam: North-Holland (2002; Zbl 1018.03002)].Demiquantifiers on \(\ell \)-groupshttps://zbmath.org/1472.060212021-11-25T18:46:10.358925Z"Petrovich, Alejandro"https://zbmath.org/authors/?q=ai:petrovich.alejandro-gustavoSummary: In this paper we introduce two kinds of unary operations on abelian \(\ell \)-groups with a positive distinguished element \(u\). One of them, called demiquantifier of type I, behaves like an existential quantifier (in the sense of \textit{C. Cimadamore} and \textit{J. P. Díaz Varela} [Stud. Log. 98, No. 1--2, 175--201 (2011; Zbl 1247.06008)]) in the negative cone, and like a universal quantifier in the positive cone. The other kind of unary operation we introduce, called demiquantifier of type II, satisfies analogous properties to demiquantifiers of type I via a translation of the negative cone, by means of the element \(u\). These unary operations are interdefinable with the usual existential quantifiers, provided the distinguished element \(u\) is a strong unit. Moreover, if \(G\) is an abelian \(\ell \)-group, then the restriction of a demiquantifier of type II to the MV-algebra \(\Gamma (G,u)\) yields a different type of quantifier, where \(\Gamma \) is \textit{D. Mundici}'s functor [J. Funct. Anal. 65, 15--63 (1986; Zbl 0597.46059)]. These quantifiers are interdefinable with the usual existential quantifiers on MV-algebras given by \textit{J. D. Rutledge} [A preliminary investigation of the infinitely many-valued predicate calculus. Ithaca, NY: Cornell University (PhD Thesis) (1959)] , provided that the involution of the corresponding MV-algebras have a fixed point.Algebraic geometry for \(\ell \)-groupshttps://zbmath.org/1472.060232021-11-25T18:46:10.358925Z"Di Nola, Antonio"https://zbmath.org/authors/?q=ai:di-nola.antonio"Lenzi, Giacomo"https://zbmath.org/authors/?q=ai:lenzi.giacomo"Vitale, Gaetano"https://zbmath.org/authors/?q=ai:vitale.gaetanoSummary: In this paper we focus on the algebraic geometry of the variety of \(\ell \)-groups (i.e. lattice ordered abelian groups). In particular we study the role of the introduction of constants in functional spaces and \(\ell \)-polynomial spaces, which are themselves \(\ell \)-groups, evaluated over other \(\ell \)-groups. We use different tools and techniques, with an increasing level of abstraction, to describe properties of \(\ell \)-groups, topological spaces (with the Zariski topology) and a formal logic, all linked by the underlying theme of solutions of \(\ell \)-equations.Lyapunov decomposition in \(\mathrm{d}_{0}\)-algebrashttps://zbmath.org/1472.060262021-11-25T18:46:10.358925Z"Avallone, Anna"https://zbmath.org/authors/?q=ai:avallone.anna"Vitolo, Paolo"https://zbmath.org/authors/?q=ai:vitolo.paoloIt is proved that a closed \(d_0\)-measure on a \(d_0\)-algebra can be decomposed into the sum of a Lyapunov \(d_0\)-measure and an anti-Lyapunov \(d_0\)-measure. The same results are obtained for cancellative BCK-algebras.Infinitary Baker-Pixley theoremhttps://zbmath.org/1472.080042021-11-25T18:46:10.358925Z"Vaggione, Diego J."https://zbmath.org/authors/?q=ai:vaggione.diego-joseSummary: An important theorem of \textit{K. A. Baker} and \textit{A. F. Pixley} [Math. Z. 143, 165--174 (1975; Zbl 0292.08004)] states that if \(\mathbf {A}\) is a finite algebra with a \((d+1)\)-ary near-unanimity term and \(f\) is an \(n\)-ary operation on \(A\) such that every subalgebra of \(\mathbf {A}^{d}\) is closed under \(f\), then \(f\) is representable by a term in \(\mathbf {A}\). It is well known that the Baker-Pixley theorem does not hold when \(\mathbf {A}\) is infinite. We give an infinitary version of the Baker-Pixley theorem which applies to an arbitrary class of structures with a \((d+1)\)-ary near-unanimity term instead of a single finite algebra.\( \omega \)-categorical structures avoiding height 1 identitieshttps://zbmath.org/1472.080062021-11-25T18:46:10.358925Z"Bodirsky, Manuel"https://zbmath.org/authors/?q=ai:bodirsky.manuel"Mottet, Antoine"https://zbmath.org/authors/?q=ai:mottet.antoine"Olšák, Miroslav"https://zbmath.org/authors/?q=ai:olsak.miroslav"Opršal, Jakub"https://zbmath.org/authors/?q=ai:oprsal.jakub"Pinsker, Michael"https://zbmath.org/authors/?q=ai:pinsker.michael"Willard, Ross"https://zbmath.org/authors/?q=ai:willard.rossIt is an open problem whether there exists a P/(NP-complete) dichotomy for first-order reducts of finitely bounded homogeneous structures. This paper refutes some plausible conjectures related to this problem. The two main theorems are:
Theorem~1.3. For every nontrivial height \(1\) condition \(\Sigma\) there exists a structure \(\mathbb B\) such that
\begin{itemize}
\item \(\mathbb B\) is a first-order reduct of a finitely bounded homogeneous structure;
\item \(\textrm{Pol}(\mathbb B)\) does not satisfy \(\Sigma\);
\item \(\textrm{Pol}(\mathbb B)\) satisfies some other nontrivial height \(1\) condition (consequently, there is no minion homomorphism to \(\mathcal P\));
\item \(\textrm{CSP}(\mathbb B)\) is in \(P\).
\end{itemize}
Theorem~1.4. There exists a structure \(\mathbb S\) with the following properties:
\begin{enumerate}
\item[(1)] \(\mathbb S\) is an \(\omega\)-categorical structure with less than doubly exponential orbit growth.
\item[(2)] \(\textrm{Pol}(\mathbb S)\) has a minion homomorphism to \(\mathcal P\).
\item[(3)] \(\textrm{Pol}(\mathbb S)\) has no uniformly continuous minion homomorphism to \(\mathcal P\).
\end{enumerate}
In these theorems, \(\mathcal P\) (calligraphic font) is the clone of projections.Taylor term does not imply any nontrivial linear one-equality Maltsev conditionhttps://zbmath.org/1472.080072021-11-25T18:46:10.358925Z"Kazda, Alexandr"https://zbmath.org/authors/?q=ai:kazda.alexandrSummary: It is known that any finite idempotent algebra that satisfies a nontrivial Maltsev condition must satisfy the linear one-equality Maltsev condition (a variant of the term discovered by \textit{M. H. Siggers} [Algebra Univers. 64, No. 1--2, 15--20 (2010; Zbl 1216.08002)] and refined by \textit{K. Kearnes} et al. [Algebra Univers. 72, No. 1, 91--100 (2014; Zbl 1305.08008)]):
\[
t(r,a,r,e)\approx t(a,r,e,a).
\]
We show that if we drop the finiteness assumption, the \(k\)-ary weak near unanimity equations imply only trivial linear one-equality Maltsev conditions for every \(k\geq3\). From this it follows that there is no nontrivial linear one-equality condition that would hold in all idempotent algebras having Taylor terms. \textit{M. Olšák} [Bull. Lond. Math. Soc. 49, No. 6, 1028--1047 (2017; Zbl 1414.08002)] has recently shown that there is a weakest nontrivial strong Maltsev condition for idempotent algebras. Olšák has found several such (mutually equivalent) conditions consisting of two or more equations. Our result shows that Olšák's equation systems cannot be compressed into just one equation.Exponential-constructible functions in \(P\)-minimal structureshttps://zbmath.org/1472.140642021-11-25T18:46:10.358925Z"Chambille, Saskia"https://zbmath.org/authors/?q=ai:chambille.saskia"Cubides Kovacsics, Pablo"https://zbmath.org/authors/?q=ai:cubides-kovacsics.pablo"Leenknegt, Eva"https://zbmath.org/authors/?q=ai:leenknegt.evaThere exist many results showing that certain classes of functions are closed under integration; the main result of the present paper is also such a result, for functions on a finite extension \(K\) of the field \(\mathbb Q_p\) of \(p\)-adic numbers. Recall that there is a natural (Haar) measure on such fields \(K\), yielding a notion of integration of functions \(K^n \to \mathbb C\). More precisely, the authors specify certain classes \(\mathcal H\) of such functions which are ``base-stable under integration'', meaning that whenever a function \(f\colon K^{n+1} \to \mathbb C\) lies in \(\mathcal H\), then so does the function \(K^n \to \mathbb C, x \mapsto \int_{K} f(x, y)\,dy\). To be precise, the authors more generally consider functions on certain subsets of \(K^n \times \mathbb Z^m\), where \(\mathbb Z\) is equipped with the counting measure. In this review, I will for simplicity stick to functions on \(K^n\), and I will write \(\mathcal H(K^n)\) for those functions in \(\mathcal H\) which live on \(K^n\).
In many results of that kind (including the one in the present paper), one first fixes a certain first-order language \(\mathcal L\) on \(K\), yielding in particular a notion of \(\mathcal L\)-definable functions from \(K^n \to \mathbb Z\) (where \(\mathbb Z\) is considered as the value group of \(K\)). Then \(\mathcal H(K^n)\) is defined as some algebra generated by certain specific functions which are specified in terms of \(\mathcal L\)-definable functions.
A classical result of that kind is the one by \textit{J. Denef} [Prog. Math. None, 25--47 (1985; Zbl 0597.12021)], where \(\mathcal L\) is the valued field language, and where \(\mathcal H(K^n)\) is the \(\mathbb Q\)-algebra generated by functions of the form \(\alpha\colon K^n \to \mathbb Z\) and \(K^n \to \mathbb Q, x \mapsto q^{\alpha(x)}\), where \(\alpha\) is \(\mathcal L\)-definable. This has then been generalized in two directions: (a) allow other languages \(\mathcal L\); (b) add more generators to \(\mathcal H(K^n)\).
An important generalization of type (b) is to consider classes of functions containing additive characters \(\psi\colon (K, +) \to (\mathbb C^\times, \cdot)\), since those naturally appear in representation theory and in Fourier transforms. In direction (a), it is tempting to believe that one can take \(\mathcal L\) to be any P-minimal language on \(K\); P-minimality is an axiomatic condition implying that \(\mathcal L\)-definable objects are ``tame'' in some geometric sense. Up to recently, assuming P-minimality was not enough to prove the desired closedness under intergration; one additionally had to assume the existence of definable Skolem functions. This assumption has now been dropped. More precisely, in a previous paper, \textit{P. Cubides Kovacsics} and \textit{E. Leenknegt} [J. Symb. Log. 81, No. 3, 1124--1141 (2016; Zbl 1428.03060)] proved closedness under integration for any P-minimal \(\mathcal L\) when \(\mathcal H(K^n)\) is generated by the same kinds of functions as in the above-mentioned result by Denef. In the present paper, they now show that this result also extends to algebras \(\mathcal H(K^n)\) containing additive characters. In particular, the authors had to find the ``right'' algebras \(\mathcal H(K^n)\) (which are not a straight forward generalization of the ones when definable Skolem functions exist).Counting algebraic points in expansions of o-minimal structures by a dense sethttps://zbmath.org/1472.140652021-11-25T18:46:10.358925Z"Eleftheriou, Pantelis E."https://zbmath.org/authors/?q=ai:eleftheriou.pantelis-eThe Pila-Wilkie theorem, which was used in Pila's solution of André-Oort conjecture [\textit{J. Pila}, Ann. Math. 173, No. 3, 1779--1840 (2011; Zbl 1243.14022)], assets that a set definable in an o-minimal structure having many rational points contains an infinite semialgebraic set [\textit{J. Pila} et al., Duke Math. J. 133, No. 3, 591--616 (2006; Zbl 1217.11066)].
This paper extends the Pila-Wilkie theorem to an expansion \(\langle \mathcal R, P \rangle\) of an o-minimal structure \(\mathcal R\) by a dense set \(P\), (1) which is either an elementary substructure of \(\mathcal R\), or (2) it is dcl-independent. Under these assumptions, a set definable in \(\langle \mathcal R, P \rangle\) having many algebraic points contains an infinite set which is \(\emptyset\)-definable in \(\langle \mathcal R, P \rangle\). The definition of algebraic points comes from [\textit{J. Pila}, Selecta Math. N. S. 15, No. 1, 151--170 (2009; Zbl 1218.11068)]. The structures of the form \(\langle \mathcal R, P \rangle\) satisfying the assumptions are introduced in [\textit{A. van den Dries}, Fund. Math. 157, No. 1, 61--78 (1998; Zbl 0906.03036)] and [\textit{A. Dolich} et al., Ann. Pure Appl. Logic 167, No. 8, 684--706 (2016; Zbl 1432.03070)], respectively.
The above theorem is deduced from Pila's result on algebraic points by introducing a generalization of Pila's algebraic part called algebraic trace part. The proof is brief in the case (1). In the case (2), the theorem is reduced to the case in which the set is a cone using the cone decomposition theorem given in [\textit{P. Eleftheriou} et al., Isr. J. Math. 239, No. 1, 435--500 (2020; Zbl 1472.03037)].Corrigendum to: ``The Gerstenhaber problem for commuting triples of matrices is `decidable' ''https://zbmath.org/1472.150242021-11-25T18:46:10.358925Z"O'Meara, Kevin C."https://zbmath.org/authors/?q=ai:omeara.kevin-cSummary: I correct a slip in an argument in the above paper [the author, ibid. 48, No. 2, 453--466 (2020; Zbl 1436.15018)]. This does not affect the
main result: the Gerstenhaber Problem is Turing computable for all fields.On the Dixmier-Moeglin equivalence for Poisson-Hopf algebrashttps://zbmath.org/1472.170802021-11-25T18:46:10.358925Z"Launois, Stéphane"https://zbmath.org/authors/?q=ai:launois.stephane"León Sánchez, Omar"https://zbmath.org/authors/?q=ai:leon-sanchez.omarSummary: We prove that the Poisson version of the Dixmier-Moeglin equivalence holds for cocommutative affine Poisson-Hopf algebras. This is a first step towards understanding the symplectic foliation and the representation theory of (cocommutative) affine Poisson-Hopf algebras. Our proof makes substantial use of the model theory of fields equipped with finitely many possibly noncommuting derivations. As an application, we show that the symmetric algebra of a finite dimensional Lie algebra, equipped with its natural Poisson structure, satisfies the Poisson Dixmier-Moeglin equivalence.On linear exactness propertieshttps://zbmath.org/1472.180022021-11-25T18:46:10.358925Z"Jacqmin, Pierre-Alain"https://zbmath.org/authors/?q=ai:jacqmin.pierre-alain"Janelidze, Zurab"https://zbmath.org/authors/?q=ai:janelidze.zurabThe authors elaborate on the conceptual framework they introduced in [\textit{P.-A. Jacqmin} and \textit{Z. Janelidze}, Adv. Math. 377, Article ID 107484, 56 p. (2021; Zbl 1452.18005)]. There, an abstract formalism was developed, based on the notion of sketch, in order to give an abstract account of exactness properties on a small finitely complete category \(\mathbb{C}\) that are preserved under pro-completion (completion under co-filtered limits, given by the embedding \( \mathbb{C} \hookrightarrow \mathrm{Lex}(\mathbb{C},\mathrm{Set})^{op}).\) Here the same formalism is used in order to obtain exactness properties in regular categories such that, when the category is algebraic, turn out to be equivalent to the existence of certain Mal'tsev terms in the corresponding algebraic theory. The main characterization theorem of the article (Theorem 3.3) asserts the equivalence of suitable exactness conditions and the existence of Mal'tsev terms and equations in the context of essentially algebraic (hence locally finitely presentable) regular categories. The theorem exploits a reformulation of those exactness conditions on a finitely cocomplete regular category in terms of a certain morphism, in the image of a left Kan extension with values in the finitely cocomplete category, being a regular epimorphism (Theorem 2.1).Regular ternary semirings in terms of bipolar fuzzy idealshttps://zbmath.org/1472.201462021-11-25T18:46:10.358925Z"Bashir, Shahida"https://zbmath.org/authors/?q=ai:bashir.shahida"Mazhar, Rabia"https://zbmath.org/authors/?q=ai:mazhar.rabia"Abbas, Hasnain"https://zbmath.org/authors/?q=ai:abbas.hasnain"Shabir, Muhammad"https://zbmath.org/authors/?q=ai:shabir.muhammadThe central objective of this paper is to introduce $(\alpha,\beta)$-bipolar fuzzy ideals (left, lateral and right) and bi-ideals in ternary semirings by applying the definitions of belongingness $(\epsilon)$ and quasi-coincidence $(q)$ of a bipolar fuzzy point with a bipolar fuzzy set. In this work, upper parts and lower parts of bipolar fuzzy set in ternary semirings are also discussed. Regular and intra-regular ternary semirings in terms of $(\epsilon,\epsilon\vee q)$-bipolar fuzzy (left, lateral and right) ideals and $(\epsilon,\epsilon\vee q)$-bipolar fuzzy bi-ideals are characterized. This paper generalizes some ideals to bipolar fuzzy ideals in semirings. All results are typical.The relationship between word complexity and computational complexity in subshiftshttps://zbmath.org/1472.370172021-11-25T18:46:10.358925Z"Pavlov, Ronnie"https://zbmath.org/authors/?q=ai:pavlov.ronnie"Vanier, Pascal"https://zbmath.org/authors/?q=ai:vanier.pascalGiven a finite set \(A\), a subshift over \(A\) is a subset of \(A^\mathbb{Z}\) which is closed in the product topology and invariant under the shift map \(\sigma\) defined by \((\sigma x)(n)=x(n+1)\). The word complexity function \(c_n(X)\) of a subshift \(X\) is defined by \(c_n(X)=|{\mathcal L}_n(X)|\), where \({\mathcal L}_n(X)\) is the set of all words of length \(n\), i.e., \(c_n(X)\) is the number of all words with length \(n\) appearing in some \(x\in X\).
The Turing spectrum of a subshift \(X\), denoted by \(\mathrm{Sp} (X)\), is the set \(\{\mathbf{d} | \exists x\in X, \mathrm{deg}_T (x) = \mathbf{d}\}\) of all Turing degrees of all points of \(X\). \par The authors study the relationship between the word complexity function of a subshift and the Turing spectrum of the subshift. In particular, it is proved that a Turing spectrum can be realized via a subshift of linear complexity if and only if it consists of the union of a finite set and a finite number of cones, that a Turing spectrum can be realized via a subshift of exponential complexity if and only if it contains a cone, and that every Turing spectrum which either contains degree \(\mathbf 0\) or is a union of cones is realizable by subshifts with a wide range of ``intermediate'' complexity growth rates between linear and exponential.Isomorphic universality and the number of pairwise nonisomorphic models in the class of Banach spaceshttps://zbmath.org/1472.460032021-11-25T18:46:10.358925Z"Džamonja, Mirna"https://zbmath.org/authors/?q=ai:dzamonja.mirnaSummary: We develop the framework of \textit{natural spaces} to study isomorphic embeddings of Banach spaces. We then use it to show that a sufficient failure of the generalized continuum hypothesis implies that the universality number of Banach spaces of a given density under a certain kind of positive embedding (\textit{very positive embedding}) is high. An example of a very positive embedding is a positive onto embedding between \(C(K)\) and \(C \left(L\right)\) for 0-dimensional \(K\) and \(L\) such that the following requirement holds for all \(h \neq 0\) and \(f \geq 0\) in \(C(K)\): if \(0 \leq T h \leq T f\), then there are constants \(a \neq 0\) and \(b\) with \(0 \leq a \cdot h + b \leq f\) and \(a \cdot h + b \neq 0\).Order topology on orthocomplemented posets of linear subspaces of a pre-Hilbert spacehttps://zbmath.org/1472.460212021-11-25T18:46:10.358925Z"Buhagiar, D."https://zbmath.org/authors/?q=ai:buhagiar.david"Chetcuti, E."https://zbmath.org/authors/?q=ai:chetcuti.emmanuel"Weber, H."https://zbmath.org/authors/?q=ai:weber.hansSummary: Motivated by the Hilbert-space model for quantum mechanics, we define a pre-Hilbert space logic to be a pair \((S,\mathcal{L})\), where \(S\) is a pre-Hilbert space and \(\mathcal{L}\) is an orthocomplemented poset of orthogonally closed linear subspaces of \(S\), closed w.r.t. finite-dimensional perturbations (i.e., if \(M\in\mathcal{L}\) and \(F\) is a finite-dimensional linear subspace of \(S\), then \(M+F\in\mathcal{L})\). We study the order topology \(\tau_o(\mathcal{L})\) on \(\mathcal{L}\) and show that completeness of \(S\) can by characterized by the separation properties of the topological space \((\mathcal{L},\tau_o(\mathcal{L}))\). It will be seen that the remarkable lack of a proper probability theory on pre-Hilbert space logics -- for an incomplete \(S\) -- comes out elementarily from this topological characterization.Thinking programs. Logical modeling and reasoning about languages, data, computations, and executionshttps://zbmath.org/1472.680022021-11-25T18:46:10.358925Z"Schreiner, Wolfgang"https://zbmath.org/authors/?q=ai:schreiner.wolfgangPublisher's description: This book describes some basic principles that allow developers of computer programs (computer scientists, software engineers, programmers) to clearly \textit{think} about the artifacts they deal with in their daily work: data types, programming languages, programs written in these languages that compute from given inputs wanted outputs, and programs that describe continuously executing systems. The core message is that clear thinking about programs can be expressed in a single universal language, the formal language of \textit{logic}. Apart from its universal elegance and expressiveness, this ``logical'' approach to the formal modeling of and reasoning about computer programs has another advantage: due to advances in computational logic (automated theorem proving, satisfiability solving, model checking), nowadays much of this process can be supported by \textit{software}. This book therefore accompanies its theoretical elaborations by practical demonstrations of various systems and tools that are based on respectively make use of the presented logical underpinnings.A synchronous effects logic for temporal verification of pure Esterelhttps://zbmath.org/1472.680202021-11-25T18:46:10.358925Z"Song, Yahui"https://zbmath.org/authors/?q=ai:song.yahui"Chin, Wei-Ngan"https://zbmath.org/authors/?q=ai:chin.wei-nganSummary: Esterel is an imperative synchronous language that has found success in many safety-critical applications. Its precise semantics makes it natural for programming and reasoning. Existing techniques tackle either one of its main challenges: correctness checking or temporal verification. To resolve the issues simultaneously, we propose a new solution via a Hoare-style forward verifier and a term rewriting system (TRS) on \textit{Synced Effects}. The first contribution is, by deploying a novel effects logic, the verifier computes the deterministic program behaviour via construction rules at the source level, defining program evaluation syntactically. As a second contribution, by avoiding the complex translation from LTL formulas to Esterel programs, our purely algebraic TRS efficiently checks temporal properties described by expressive Synced Effects. To demonstrate our method's feasibility, we prototype this logic; prove its correctness; provide experimental results, and a number of case studies.
For the entire collection see [Zbl 1471.68017].selp: a single-shot epistemic logic program solverhttps://zbmath.org/1472.680222021-11-25T18:46:10.358925Z"Bichler, Manuel"https://zbmath.org/authors/?q=ai:bichler.manuel"Morak, Michael"https://zbmath.org/authors/?q=ai:morak.michael"Woltran, Stefan"https://zbmath.org/authors/?q=ai:woltran.stefanSummary: Epistemic logic programs (ELPs) are an extension of answer set programming (ASP) with epistemic operators that allow for a form of meta-reasoning, that is, reasoning over multiple possible worlds. Existing ELP solving approaches generally rely on making multiple calls to an ASP solver in order to evaluate the ELP. However, in this paper, we show that there also exists a direct translation from ELPs into non-ground ASP with bounded arity. The resulting ASP program can thus be solved in a single shot. We then implement this encoding method, using recently proposed techniques to handle large, non-ground ASP rules, into the prototype ELP solving system ``selp,'' which we present in this paper. This solver exhibits competitive performance on a set of ELP benchmark instances.Foundations of logic programming in hybridised logicshttps://zbmath.org/1472.680252021-11-25T18:46:10.358925Z"Găină, Daniel"https://zbmath.org/authors/?q=ai:gaina.danielSummary: The present paper sets the foundation of logic programming in hybridised logics. The basic logic programming semantic concepts such as query and solutions, and the fundamental results such as the existence of initial models and Herbrand's theorem, are developed over a very general hybrid logical system. We employ the hybridisation process proposed by Diaconescu over an arbitrary logical system captured as an institution to define the logic programming framework.
For the entire collection see [Zbl 1327.68013].An institutional foundation for the \(\mathbb {K}\) semantic frameworkhttps://zbmath.org/1472.680342021-11-25T18:46:10.358925Z"Chiriţă, Claudia Elena"https://zbmath.org/authors/?q=ai:chirita.claudia-elena"Şerbănuţă, Traian Florin"https://zbmath.org/authors/?q=ai:serbanuta.traian-florinSummary: We advance an institutional formalisation of the logical systems that underlie the \(\mathbb {K}\) semantic framework and are used to capture both structural properties of program configurations through pattern matching, and changes of configurations through reachability rules. By defining encodings of matching and reachability logic into the institution of first-order logic, we set the foundation for integrating \(\mathbb {K}\) into logic graphs of heterogeneous institution-based specification languages such as \textsc{HetCasl}. This will further enable the use of the \(\mathbb {K}\) tool with other existing formal specification and verification tools associated with \textsc{Hets}.
For the entire collection see [Zbl 1327.68013].On subexponentials, synthetic connectives, and multi-level delimited controlhttps://zbmath.org/1472.680382021-11-25T18:46:10.358925Z"Liang, Chuck"https://zbmath.org/authors/?q=ai:liang.chuck"Miller, Dale"https://zbmath.org/authors/?q=ai:miller.dale-aSummary: We construct a partially-ordered hierarchy of delimited control operators similar to those of the CPS hierarchy of
\textit{O. Danvy} and \textit{A. Filinski} [``Abstracting control'', in: Proceedings of the 1990 ACM conference on LISP and functional programming, LFP'90. New York, NY: Association for Computing Machinery (ACM). 151--160 (1990; \url{doi:10.1145/91556.91622})].
However, instead of relying on nested CPS translations, these operators are directly interpreted in linear logic extended with subexponentials (i.e., multiple pairs of ! and ?). We construct an independent proof theory for a fragment of this logic based on the principle of focusing. It is then shown that the new constraints placed on the permutation of cuts correspond to multiple levels of delimited control.
For the entire collection see [Zbl 1326.68013].Property-based testing for Spark Streaminghttps://zbmath.org/1472.680412021-11-25T18:46:10.358925Z"Riesco, A."https://zbmath.org/authors/?q=ai:riesco.adrian"Rodríguez-Hortalá, J."https://zbmath.org/authors/?q=ai:rodriguez-hortala.juanSummary: Stream processing has reached the mainstream in the last years, as a new generation of open-source distributed stream processing systems, designed for scaling horizontally on commodity hardware, has brought the capability for processing high-volume and high-velocity data streams to companies of all sizes. In this work, we propose a combination of temporal logic and property-based testing (PBT) for dealing with the challenges of testing programs that employ this programming model. We formalize our approach in a discrete time temporal logic for finite words, with some additions to improve the expressiveness of properties, which includes timeouts for temporal operators and a binding operator for letters. In particular, we focus on testing Spark Streaming programs written with the Spark API for the functional language Scala, using the PBT library ScalaCheck. For that we add temporal logic operators to a set of new ScalaCheck generators and properties, as part of our testing library sscheck.Generative program analysis and beyond: the power of domain-specific languages (invited paper)https://zbmath.org/1472.680422021-11-25T18:46:10.358925Z"Steffen, Bernhard"https://zbmath.org/authors/?q=ai:steffen.bernhard"Murtovi, Alnis"https://zbmath.org/authors/?q=ai:murtovi.alnisSummary: In this paper we position Linear Time Temporal Logic (LTL), structural operational semantics (SOS), and a graphical generalization of BNF as central DSLs for program analysis and verification tasks in order to illustrate the impact of language to the mindset: (1) Specifying program analyses in LTL changes the classical algorithmic `HOW' thinking into a property-oriented `WHAT' thinking that allows one to logically combine analysis goals and eases proofs. (2) Playing with the original store component in SOS configurations allows one to elegantly realize variants of abstract program interpretations, and to align different aspects, like e.g., the symbolic values of variables and path conditions. (3) Specializing languages by refining their BNF-like meta models has the power to lift certain verification tasks from the program to the programming language level. We will illustrate the advantages of the change of mindset imposed by these three DSLs, as well as the fact that these advantages come at low price due to available adequate generator technology.
For the entire collection see [Zbl 1471.68017].Give me another one!https://zbmath.org/1472.680652021-11-25T18:46:10.358925Z"Behrisch, Mike"https://zbmath.org/authors/?q=ai:behrisch.mike"Hermann, Miki"https://zbmath.org/authors/?q=ai:hermann.miki"Mengel, Stefan"https://zbmath.org/authors/?q=ai:mengel.stefan"Salzer, Gernot"https://zbmath.org/authors/?q=ai:salzer.gernotSummary: We investigate the complexity of an optimization problem in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find a satisfying assignment with minimal Hamming distance to a given assignment that satisfies the formula (\textsf{NearestOtherSolution}, \textsf{NOSol}).
We present a complete classification with respect to the relations admitted in the formula. We give polynomial-time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness regarding poly-APX, NPO, or equivalence to a well-known hard optimization problem.
For the entire collection see [Zbl 1326.68015].Erratum to: ``Solving Horn clauses on inductive data types without induction''https://zbmath.org/1472.680862021-11-25T18:46:10.358925Z"De Angelis, Emanuele"https://zbmath.org/authors/?q=ai:de-angelis.emanuele"Fioravanti, Fabio"https://zbmath.org/authors/?q=ai:fioravanti.fabio"Pettorossi, Alberto"https://zbmath.org/authors/?q=ai:pettorossi.alberto"Proietti, Maurizio"https://zbmath.org/authors/?q=ai:proietti.maurizioSome misprints in a few lines in the authors' paper [ibid. 18, No. 3--4, 452--469 (2018; Zbl 1451.68172)] are corrected.Model checking algorithms for hyperproperties (invited paper)https://zbmath.org/1472.680882021-11-25T18:46:10.358925Z"Finkbeiner, Bernd"https://zbmath.org/authors/?q=ai:finkbeiner.berndSummary: Hyperproperties generalize trace properties by expressing relations between multiple computations. Hyperpropertes include policies from information-flow security, like observational determinism or noninterference, and many other system properties including promptness and knowledge. In this paper, we give an overview on the model checking problem for temporal hyperlogics. Our starting point is the model checking algorithm for HyperLTL, a reduction to Büchi automata emptiness. This basic construction can be extended with propositional quantification, resulting in an algorithm for HyperQPTL. It can also be extended with branching time, resulting in an algorithm for HyperCTL*. However, it is not possible to have both extensions at the same time: the model checking problem of HyperQCTL* is undecidable. An attractive compromise is offered by MPL[\textit{E}], i.e., monadic path logic extended with the equal-level predicate. The expressiveness of MPL[\textit{E}] falls strictly between that of HyperCTL* and HyperQCTL*. MPL[\textit{E}] subsumes both HyperCTL* and HyperKCTL*, the extension of HyperCTL* with the knowledge operator. We show that the model checking problem for MPL[\textit{E}] is still decidable.
For the entire collection see [Zbl 1471.68017].A design of GPU-based quantitative model checkinghttps://zbmath.org/1472.680912021-11-25T18:46:10.358925Z"Kwon, YoungMin"https://zbmath.org/authors/?q=ai:kwon.youngmin"Kim, Eunhee"https://zbmath.org/authors/?q=ai:kim.eunheeSummary: In this paper, we implement a GPU-based quantitative model checker and compare its performance with a CPU-based one. Linear Temporal Logic for Control (LTLC) is a quantitative variation of LTL to describe properties of a linear system and LTLC-Checker is an implementation of its model checking algorithm. In practice, its long and unpredictable execution time has been a concern in applying the technique to real-time applications such as automatic control systems. In this paper, we design an LTLC model checker using a GPGPU programming technique. The resulting model checker is not only faster than the CPU-based one especially when the problem is not simple, but it has less variation in the execution time as well. Furthermore, multiple counterexamples can be found together when the CPU-based checker can find only one.
For the entire collection see [Zbl 1471.68017].What Is a derived signature morphism?https://zbmath.org/1472.680972021-11-25T18:46:10.358925Z"Mossakowski, Till"https://zbmath.org/authors/?q=ai:mossakowski.till"Krumnack, Ulf"https://zbmath.org/authors/?q=ai:krumnack.ulf"Maibaum, Tom"https://zbmath.org/authors/?q=ai:maibaum.thomas-s-eSummary: The notion of signature morphism is basic to the theory of institutions. It provides a powerful primitive for the study of specifications, their modularity and their relations in an abstract setting. The notion of derived signature morphism generalises signature morphisms to more complex constructions, where symbols may be mapped not only to symbols, but to arbitrary terms. The purpose of this work is to study derived signature morphisms in an institution-independent way. We will recall and generalize two known approaches to derived signature morphisms, introduce a third one, and discuss their pros and cons. We especially study the existence of colimits of derived signature morphisms. The motivation is to give an independent semantics to the notion of derived signature morphism, query and substitution in the context of the Distributed Ontology, Modeling and Specification Language DOL.
For the entire collection see [Zbl 1327.68013].A hybrid of tense logic \(\mathrm{S}4_\mathrm{T}\) and multi-agent logic with interacting agentshttps://zbmath.org/1472.681922021-11-25T18:46:10.358925Z"Rybakov, Vladimir V."https://zbmath.org/authors/?q=ai:rybakov.vladimir-vladimirovich"Babenyshev, Sergej V."https://zbmath.org/authors/?q=ai:babenyshev.sergej-vSummary: In this paper we introduce a temporal multi-agent logic \(\mathrm{S}4_\mathrm{T}^{\mathcal{IA}}\), which implements interacting agents. Logic \(\mathrm{S}4_\mathrm{T}^{\mathcal{IA}}\) is defined semantically as the set of all formulas of the appropriate propositional language that are valid in special Kripke models. The models are based on S4-like time frames, i.e., with reflexive and transitive time-accessibility relations. Agents knowledge-accessibility relations \(R_i\), defined independently for each individual agent, are S5-relations on \(R\)-time clusters, and interaction of the agents consists of passing knowledge along arbitrary paths of such relations. The key result of the paper is an algorithm for checking satisfiability and recognizing theorems of \(\mathrm{S}4_\mathrm{T}^{\mathcal{IA}}\). We also prove the effective finite model property for the logic \(\mathrm{S}4_\mathrm{T}^{\mathcal{IA}}\).Algorithms using ROBDD as a base for Boolean constraintshttps://zbmath.org/1472.682302021-11-25T18:46:10.358925Z"Ignat'ev, A. S."https://zbmath.org/authors/?q=ai:ignatev.a-s"Semenov, A. A."https://zbmath.org/authors/?q=ai:semenov.aleksandr-anatolevichSummary: In the paper, we study algorithmic properties of ROBDD considered in the role of Boolean constraints in the hybrid (SAT+ROBDD) logical derivation. We suggest ROBDD-analogs for the basic algorithmic procedures used in DPLL-derivation such as variable assignment, unit clause, clause learning, and the techniques of delayed computations. A new algorithm intended for ROBDD reordering is proposed. Computational complexity of all the considered algorithms is provided.Natural vs. artificial topologies on a relativistic spacetimehttps://zbmath.org/1472.830782021-11-25T18:46:10.358925Z"Papadopoulos, Kyriakos"https://zbmath.org/authors/?q=ai:papadopoulos.kyriakosSummary: Consider a set \(M\) equipped with a structure \(\ast \). We call a natural topology \(T_\ast \), on (M, \( \ast )\), the topology induced by \(\ast \). For example, a natural topology for a metric space \((X, d)\) is a topology \(T_d\) induced by the metric \(d\), and for a linearly ordered set \((X, <)\), a natural topology should be the topology \(T_<\) that is induced by the order \(<\). This fundamental property, for a topology to be called ``natural,'' has been largely ignored while studying topological properties of spacetime manifolds \((M, g)\), where \(g\) is the Lorentz ``metric,'' and the manifold topology \(T_M\) has been used as a natural topology, ignoring the spacetime ``metric'' \(g\). In this survey, we review critically candidate topologies for a relativistic spacetime manifold, and we pose open questions and conjectures with the aim to establish a complete guide on the latest results in the field and give the foundations for future discussions. We discuss the criticism against the manifold topology, a criticism that was initiated by people like Zeeman, Göbel, Hawking-King-McCarthy and others, and we examine what should be meant by the term ``natural topology'' for a spacetime. Since the common criticism against spacetime topologies, other than the manifold topology, claims that there has not been established yet a physical theory to justify such topologies, we give examples of seemingly physical phenomena, under the manifold topology, which are actually purely effects depending on the choice of the topology; the Limit Curve Theorem, which is linked to singularity theorems in general relativity, and the Gao-Wald type of ``time dilation'' are such examples.
For the entire collection see [Zbl 1470.49002].Optimization of usable leftover cutting stock problems using fuzzy approachhttps://zbmath.org/1472.900612021-11-25T18:46:10.358925Z"Bressan, Glaucia Maria"https://zbmath.org/authors/?q=ai:bressan.glaucia-maria"de Souza Sobrinho, Monique Gabrielle"https://zbmath.org/authors/?q=ai:de-souza-sobrinho.monique-gabrielle"Agulhari, Christiano Marcos"https://zbmath.org/authors/?q=ai:agulhari.christiano-marcosSummary: The objectives of this paper are to analyze different linear optimization models for the one-dimensional cutting stock problem and, by using a fuzzy classification approach, determine the reutilization of the leftovers from the cutting process. The optimal solutions of the proposed linear models are obtained from simplex method. The fuzzy classification system is a collaborative decision-making tool, which analyzes uncertain parameters in the manufacturing process in order to determine, according to the given objective, the most appropriate cutting pattern, also classifying the results provided by different linear optimization models. The comparison of the results allows to infer the most appropriate model to use according to the specifications of the problem to be solved. Results are obtained from a case study, in a packaging company, located in the state of Paraná, Brazil, which aims to select the best cutting pattern for two different scenarios: one with concentration of leftovers on standardized objects, and the other on non-standardized objects.Metastability of the proximal point algorithm with multi-parametershttps://zbmath.org/1472.900862021-11-25T18:46:10.358925Z"Dinis, Bruno"https://zbmath.org/authors/?q=ai:dinis.bruno"Pinto, Pedro"https://zbmath.org/authors/?q=ai:pinto.pedro-cSummary: In this article we use techniques of proof mining to analyse a result, due to \textit{Y. Yao} and \textit{M. A. Noor} [J. Comput. Appl. Math. 217, No. 1, 46--55 (2008; Zbl 1147.65049)], concerning the strong convergence of a generalized proximal point algorithm which involves multiple parameters. Yao and Noor's result [loc. cit.] ensures the strong convergence of the algorithm to the nearest projection point onto the set of zeros of the operator. Our quantitative analysis, guided by \textit{F. Ferreira} and \textit{P. Oliva}'s [Ann. Pure Appl. Logic 135, No. 1--3, 73--112 (2005; Zbl 1095.03060)] bounded functional interpretation, provides a primitive recursive bound on the metastability for the convergence of the algorithm, in the sense of Terence Tao. Furthermore, we obtain quantitative information on the asymptotic regularity of the iteration. The results of this paper are made possible by an arithmetization of the lim sup.Using temporary logics and model checkers for dynamic control abnormal deviations of the systemhttps://zbmath.org/1472.931142021-11-25T18:46:10.358925Z"Prokop'ev, S. E."https://zbmath.org/authors/?q=ai:prokopev.s-eSummary: We propose to apply the temporary logics and model checkers for dynamic control of ``abnormal'' deviations of a system by approximating its ``normal'' features with the temporary logic formulas. Also, we propose an exhaustive blind search algorithm for discovering regularities which can be expressed with the help of the temporal logics.