Recent zbMATH articles in MSC 03https://www.zbmath.org/atom/cc/032021-03-30T15:24:00+00:00WerkzeugBook review of: P. A. Ebert (ed.) and M. Rossberg (ed.), Essays on Frege's \textit{Basic laws of arithmetic}.https://www.zbmath.org/1455.000122021-03-30T15:24:00+00:00"Landini, Gregory"https://www.zbmath.org/authors/?q=ai:landini.gregoryReview of [Zbl 1435.03012].Book review of: Ø. Linnebo, Thin objects. An abstractionist account.https://www.zbmath.org/1455.000052021-03-30T15:24:00+00:00"Donaldson, Thomas"https://www.zbmath.org/authors/?q=ai:donaldson.thomas.1Review of [Zbl 1391.00030].Representing small ordinals by finite automata.https://www.zbmath.org/1455.680882021-03-30T15:24:00+00:00"Ésik, Zoltan"https://www.zbmath.org/authors/?q=ai:esik.zoltanSummary: It is known that an ordinal is the order type of the lexicographic ordering of a regular language if and only if it is less than \(\omega^{\omega}\). We design a polynomial time algorithm that constructs, for each well-ordered regular language \(L\) with respect to the lexicographic ordering, given by a deterministic finite automaton, the Cantor Normal Form of its order type. It follows that there is a polynomial time algorithm to decide whether two deterministic finite automata accepting well-ordered regular languages accept isomorphic languages. We also give estimates on the size of the smallest automaton representing an ordinal less than \(\omega^{\omega}\), together with an algorithm that translates each such ordinal to an automaton.
For the entire collection see [Zbl 1392.68027].Real sets.https://www.zbmath.org/1455.180112021-03-30T15:24:00+00:00"Janelidze, George"https://www.zbmath.org/authors/?q=ai:janelidze.george"Street, Ross"https://www.zbmath.org/authors/?q=ai:street.ross-hSummary: After reviewing a universal characterization of the extended positive real numbers published by \textit{D. Higgs} [Indag. Math. 40, 448--455 (1978; Zbl 0407.08001)], we define a category which provides an answer to the questions:
\(\bullet\) what is a set with half an element?
\(\bullet\) what is a set with \(\pi\) elements?
The category of these extended positive real sets is equipped with a countable tensor product. We develop somewhat the theory of categories with countable tensors; we call the commutative such categories \textit{series monoidal} and conclude by only briefly mentioning the non-commutative possibility called \(\omega\)-\textit{monoidal}. We include some remarks on sets having cardinalities in \([-\infty,\infty]\).Light logics and higher-order processes.https://www.zbmath.org/1455.681212021-03-30T15:24:00+00:00"Dal Lago, Ugo"https://www.zbmath.org/authors/?q=ai:dal-lago.ugo"Martini, Simone"https://www.zbmath.org/authors/?q=ai:martini.simone"Sangiorgi, Davide"https://www.zbmath.org/authors/?q=ai:sangiorgi.davideSummary: We show that the techniques for resource control that have been developed in the so-called ``light logics'' can be fruitfully applied also to process algebras. In particular, we present a restriction of Higher-Order \(\pi\)-calculus inspired by Soft Linear Logic. We prove that any soft process terminates in polynomial time. We argue that the class of soft processes may be naturally enlarged so that interesting processes are expressible, still maintaining the polynomial bound on executions.
For the entire collection see [Zbl 1415.68027].Process behaviour: formulae vs. tests (extended abstract).https://www.zbmath.org/1455.681202021-03-30T15:24:00+00:00"Cerone, Andrea"https://www.zbmath.org/authors/?q=ai:cerone.andrea"Hennessy, Matthew"https://www.zbmath.org/authors/?q=ai:hennessy.matthew-gSummary: Process behaviour is often defined either in terms of the tests they satisfy, or in terms of the logical properties they enjoy. Here we compare these two approaches, using extensional testing in the style of DeNicola, Hennessy, and a recursive version of the property logic HML.
We first characterise subsets of this property logic which can be captured by tests. Then we show that those subsets of the property logic capture precisely the power of tests.
For the entire collection see [Zbl 1415.68027].Null subsets of all sizes inside Vitali sets.https://www.zbmath.org/1455.280022021-03-30T15:24:00+00:00"Kainth, Surinder Pal Singh"https://www.zbmath.org/authors/?q=ai:kainth.surinder-pal-singhThe author would like to state and prove the following (correct) result:
Any Vitali set contains Lebesgue null subsets of an arbitrary cardinality which is at most the cardinality of the continuum (equivalently: there is such a subset of cardinality continuum). His formulation is a bit unclear, and his argument has a gap, since he erroneously assumes that the cardinality of the set \(A\) he is using necessarily has countable cofinality.
For a correct proof he should have used a set \(A\) of cardinality continuum, e.g., the Cantor set, thus proving the equivalent version above.
Reviewer: Petr Holický (Praha)Free sequences in \({\mathscr{P}}( \omega) /\mathrm{fin}\).https://www.zbmath.org/1455.030622021-03-30T15:24:00+00:00"Chodounský, David"https://www.zbmath.org/authors/?q=ai:chodounsky.david"Fischer, Vera"https://www.zbmath.org/authors/?q=ai:fischer.vera"Grebík, Jan"https://www.zbmath.org/authors/?q=ai:grebik.janA free sequence in a Boolean algebra, as defined in [\textit{J. D. Monk}, Commentat. Math. Univ. Carol. 52, No. 4, 593--610 (2011; Zbl 1249.06034)],
is a sequence \(\langle a_\alpha:\alpha<\gamma\rangle\) of elements such that
for every \(\beta\le\gamma\) the set
\(\{a_\alpha:\alpha<\beta\}\cup\{a_\alpha':\beta\le\alpha<\gamma\}\)
is centered.
It is maximal if it has no free end-extension.
Though the order(-type) of the sequence is important in this definition
the cardinal number \(\mathfrak f(B)\) is defined to be the
minimum \textit{cardinality\/} of a free sequence in the algebra \(B\);
if \(B=\mathcal{P}(\omega)/\mathrm{fin}\), then one simply writes \(\mathfrak f\).
After making some remarks on free sequences in \(\mathcal{P}(\omega)/\mathrm{fin}\)
and indicating how much is still unknown the authors show the consistency
of \(\mathfrak i=\mathfrak f<\mathfrak u\), where \(\mathfrak i\) is the minimum cardinality
of a maximal independent family and \(\mathfrak u\) is the minimum character
of an ultrafilter.
They show that this holds in \textit{S. Shelah}'s model for \(\mathfrak i<\mathfrak u\)
from [Arch. Math. Logic 31, No. 6, 433--443 (1992; Zbl 0785.03029)] and give a self-contained presentation of this model.
An independent family is a free sequence no matter how it is ordered and
one would expect some relation between \(\mathfrak i\) and \(\mathfrak f\) to hold;
the Miller model satisfies \(\mathfrak f<\mathfrak i\) but it is not (yet) known
whether \(\mathfrak i<\mathfrak f\) is consistent.
Reviewer: K. P. Hart (Delft)Contextual types, explained. Invited tutorial.https://www.zbmath.org/1455.030162021-03-30T15:24:00+00:00"Pientka, Brigitte"https://www.zbmath.org/authors/?q=ai:pientka.brigitteResumptions, weak bisimilarity and big-step semantics for While with interactive I/O: an exercise in mixed induction-coinduction.https://www.zbmath.org/1455.681002021-03-30T15:24:00+00:00"Nakata, Keiko"https://www.zbmath.org/authors/?q=ai:nakata.keiko"Uustalu, Tarmo"https://www.zbmath.org/authors/?q=ai:uustalu.tarmoSummary: We look at the operational semantics of languages with interactive I/O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While, we define several big-step semantics for While with interactive I/O, based on resumptions and termination-sensitive weak bisimilarity. These require nesting inductive definitions in coinductive definitions, which is interesting both mathematically and from the point-of-view of implementation in a proof assistant.
After first defining a basic semantics of statements in terms of resumptions with explicit internal actions (delays), we introduce a semantics in terms of delay-free resumptions that essentially removes finite sequences of delays on the fly from those resumptions that are responsive. Finally, we also look at a semantics in terms of delay-free resumptions supplemented with a silent divergence option. This semantics hinges on decisions between convergence and divergence and is only equivalent to the basic one classically. We have fully formalized our development in Coq.
For the entire collection see [Zbl 1392.68008].Congruence from the operator's point of view: compositionality requirements on process semantics.https://www.zbmath.org/1455.680992021-03-30T15:24:00+00:00"Gazda, Maciej"https://www.zbmath.org/authors/?q=ai:gazda.maciej-w"Fokkink, Wan"https://www.zbmath.org/authors/?q=ai:fokkink.wan|fokkink.wan-jSummary: One of the basic sanity properties of a behavioural semantics is that it constitutes a congruence with respect to standard process operators. This issue has been traditionally addressed by the development of rule formats for transition system specifications that define process algebras. In this paper we suggest a novel, orthogonal approach. Namely, we focus on a number of process operators, and for each of them attempt to find the widest possible class of congruences. To this end, we impose restrictions on sublanguages of Hennessy-Milner logic, so that a semantics whose modal characterization satisfies a given criterion is guaranteed to be a congruence with respect to the operator in question. We investigate action prefix, alternative composition, two restriction operators, and parallel composition.
For the entire collection see [Zbl 1392.68008].New substitution bases for complexity classes.https://www.zbmath.org/1455.030512021-03-30T15:24:00+00:00"Mazzanti, Stefano"https://www.zbmath.org/authors/?q=ai:mazzanti.stefanoIn this paper, the author improves earlier work by showing that well-known function complexity classes can be characterised as the substitution closure of finite sets of simple functions \(\mathbf{AC}^0(F)\). Intuitively, this work is about finding fitting substitution bases, that is, finite sets of functions that define a function class (projection functions and substitution is allowed). For instance, if \(F=\{\text{mult}\}\) then \(\mathbf{AC}^0(F)=\mathbf{TC}^0\). Furthermore, the author present in the concluding section a discussion on how the introduced function algebras may lead to a new, algebraic proof that \(\mathbf{AC}^0\neq\mathbf{TC}^0\). At the end of the preliminaries, the author gives already a short outlook on the results he is going to prove which gives a nice context. Some results (e.g., Lemma 3.8, Lemma 3.12) in the main part are not proven (``straightforward''). Unfortunately, there is little intertext between the lemmas which could guide a reader a bit more.
Section 5 presents new bases for \(\mathbf{TC}^0\), and, in the next Section 6, one gets a nice characterisation of the complexity classes \(\mathbf{NC}^1, \mathbf{L}, \mathbf{P},\) and \(\mathbf{PSPACE}\) in terms of function sets \(F\) such that they respectively coincide with \(\mathbf{AC}^0(F)\).
Reviewer: Arne Meier (Hannover)Invariance and definability, with and without equality.https://www.zbmath.org/1455.030032021-03-30T15:24:00+00:00"Bonnay, Denis"https://www.zbmath.org/authors/?q=ai:bonnay.denis"Engström, Fredrik"https://www.zbmath.org/authors/?q=ai:engstrom.fredrikSummary: The dual character of invariance under transformations and definability by some operations has been used in classical works by, for example, Galois and Klein. Following Tarski, philosophers of logic have claimed that logical notions themselves could be characterized in terms of invariance. In this article, we generalize a correspondence due to Krasner between invariance under groups of permutations and definability in \(\mathcal{L}_{\infty\infty}\) so as to cover the cases (quantifiers, logics without equality) that are of interest in the logicality debates, getting McGee's theorem about quantifiers invariant under all permutations and definability in pure \(\mathcal{L}_{\infty\infty}\) as a particular case. We also prove some optimality results along the way, regarding the kinds of relations which are needed so that every subgroup of the full permutation group is characterizable as a group of automorphisms.A completion for distributive nearlattices.https://www.zbmath.org/1455.060042021-03-30T15:24:00+00:00"González, Luciano J."https://www.zbmath.org/authors/?q=ai:gonzalez.luciano-javier"Calomino, Ismael"https://www.zbmath.org/authors/?q=ai:calomino.ismaelBy a polarity a triple \((X,Y,R)\) is meant where \(X,Y\) are nonempty sets and \(R\) is a binary relation between \(X\) and \(Y\). For a poset \(P\), a completion of \(P\) is a pair \((L,e)\) where \(L\) is a complete lattice and \(e\) is an order embedding of \(P\) into \(L\). A collection \(F\) of upsets of \(P\) is \(standard\) if it contains all principal filters of \(P\), dually for a collection \(I\) of downsets of \(P\). A polarity is \(standard\) if it is of the form \((F,I,R)\) for standard collections \(F\) and \(I\). The authors introduce the so-called \((F,I)\)-compact and \((F,I)\)-dense polarities and the so-called \((F,I)\)-completion They prove that every distributive nearlattice can be embedded into a complete distributive lattice via an \((F,I)\)-completion and presented a connection with free distributive lattice extension. They study how an \(n\)-ary operation can be extended on a distributive nearlattice.
Reviewer: Ivan Chajda (Přerov)Blowing up the power of a singular cardinal of uncountable cofinality.https://www.zbmath.org/1455.030632021-03-30T15:24:00+00:00"Gitik, Moti"https://www.zbmath.org/authors/?q=ai:gitik.motiThe author establishes the foliowing two results : (A) Suppose that GCH holds, \(\theta\) is a singular limit of strong cardinals, and \(\lambda\) is a regular cardinal above \(\theta\). Then there is a cardinal preserving extension in which \(\theta\) is a strong limit cardinal of power \(\lambda\). (B) It is possible to blow up the power of a proper class club of singular cardinals in the core model in a cofinality preserving extension.
Reviewer: Pierre Matet (Caen)Computability at zero temperature.https://www.zbmath.org/1455.370322021-03-30T15:24:00+00:00"Burr, Michael"https://www.zbmath.org/authors/?q=ai:burr.michael-a"Wolf, Christian"https://www.zbmath.org/authors/?q=ai:wolf.christianThe authors give some answers concerning the computability of basic thermodynamic invariants at zero temperature. They investigate the computability of the residual entropy on the space of continuous potentials for subshifts of finite type (SFTs).
Let \(f : X\rightarrow X\) be a subshift of finite type over an alphabet with \(d\) elements and let \(\mathcal{M}\) be the set of \(f\)-invariant Borel probability measures on \(X\) endowed with the weak* topology. Define \(\mathcal{M}_{\max}(\phi) = \{\mu\in \mathcal{M}: \mu(\phi) = b_{\phi}\}\), where \(\phi:X\rightarrow \mathbb{R}\) is a continuous function. The residual entropy of the potential \(\phi\) is defined by \(h_{\infty,\phi}= \sup\{h_{\mu}(f): \mu\in \mathcal{M}_{\max}(\phi)\}\), where \(h_{\mu}(f)\) is the measure entropy of \(f\) with respect to the measure \(\mu\). The authors prove that the function \(\phi\rightarrow h_{\infty,\phi}\) is upper semi-computable, but not computable on \(C(X,\mathbb{R})\). Moreover, the map \(\phi\rightarrow h_{\infty,\phi}\) is continuous at \(\phi_0\) if and only if \(h_{\infty,\phi_0} = 0\). Therefore, they prove that the residual entropy is semi-computable, but not computable. Then they study locally constant potentials for which the zero-temperature measure is known to exist. Let LC\((X,\mathbb{R}) =\bigcup_{k\in \mathbb{N}}\)LC\(_{k}(X,\mathbb{R})\) denote the space of locally constant potentials, where LC\(_{k}(X,\mathbb{R})\) denotes the space of potentials that are constant on cylinders of length \(k\). The authors prove that if \(f : X\rightarrow X\) is a transitive SFT with positive topological entropy, then the set \(\mathcal{O}\) has no interior points in LC\((X,\mathbb{R})\), where \(\mathcal{O}\) is the set of locally constant potentials that are uniquely maximizing.
Reviewer: Hasan Akin (Gaziantep)Some results on extension of lattice-valued XOR, XOR-implications and E-implications.https://www.zbmath.org/1455.030302021-03-30T15:24:00+00:00"Palmeira, Eduardo"https://www.zbmath.org/authors/?q=ai:palmeira.eduardo-silva"Bedregal, Benjamín"https://www.zbmath.org/authors/?q=ai:bedregal.benjamin-r-callejasSummary: The extension problem is an important and interesting issue that be addressed for many different classes of operator. For instance, one can thing who to extend a fuzzy operator from a lattice to a bigger one preserving its algebraic properties. In this paper we attempt to the extension of lattice-valued version of XOR (exclusive) operator using a special method based on retractions. Also we discuss about XOR-implications end E-implications.
For the entire collection see [Zbl 1385.68004].Deep reinforcement learning with temporal logics.https://www.zbmath.org/1455.681902021-03-30T15:24:00+00:00"Hasanbeig, Mohammadhosein"https://www.zbmath.org/authors/?q=ai:hasanbeig.mohammadhosein"Kroening, Daniel"https://www.zbmath.org/authors/?q=ai:kroning.daniel"Abate, Alessandro"https://www.zbmath.org/authors/?q=ai:abate.alessandroSummary: The combination of data-driven learning methods with formal reasoning has seen a surge of interest, as either area has the potential to bolstering the other. For instance, formal methods promise to expand the use of state-of-the-art learning approaches in the direction of certification and sample efficiency. In this work, we propose a deep Reinforcement Learning (RL) method for policy synthesis in continuous-state/action unknown environments, under requirements expressed in Linear Temporal Logic (LTL). We show that this combination lifts the applicability of deep RL to complex temporal and memory-dependent policy synthesis goals. We express an LTL specification as a Limit Deterministic Büchi Automaton (LDBA) and synchronise it on-the-fly with the agent/environment. The LDBA in practice monitors the environment, acting as a modular reward machine for the agent: accordingly, a modular Deep Deterministic Policy Gradient (DDPG) architecture is proposed to generate a low-level control policy that maximises the probability of the given LTL formula. We evaluate our framework in a cart-pole example and in a Mars rover experiment, where we achieve near-perfect success rates, while baselines based on standard RL are shown to fail in practice.
For the entire collection see [Zbl 1455.68021].Theorem prover for intuitionistic logic based on the inverse method.https://www.zbmath.org/1455.682512021-03-30T15:24:00+00:00"Pavlov, V. A."https://www.zbmath.org/authors/?q=ai:pavlov.v-a"Pak, V. G."https://www.zbmath.org/authors/?q=ai:pak.v-g.1Summary: The first-order intuitionistic logic is a formal theory from the family of constructive logics. In intuitionistic logic, it is possible to extract a particular example \(x = a\) and a proof of a formula \(P(a)\) from a proof of a formula \(\exists x P(x)\). Owing to this feature, intuitionistic logic has many applications in mathematics and computer science. Many modern proof assistants include automated tactics for the first-order intuitionistic logic, which simplify the task of solving challenging problems, such as formal verification of software, hardware, and protocols. In this paper, a new theorem prover (called WhaleProver) for full first-order intuitionistic logic is presented. Testing on the ILTP benchmarking library has shown that WhaleProver performance is comparable with the state-of-the-art intuitionistic provers. Our prover has solved more than 800 problems from the ILTP version 1.1.2. Some of them are intractable for other provers. WhaleProver is based on the inverse method proposed by S. Yu. Maslov. We introduce an intuitionistic inverse method calculus which is, in turn, a special kind of sequent calculus. It is also described how to adopt for this calculus several existing proof search strategies proposed for different logical calculi by S. Yu. Maslov, V. P. Orevkov, A. A. Voronkov, and others. In addition, a new proof search strategy is proposed that allows one to avoid redundant inferences. The paper includes results of experiments with WhaleProver on the ILTP library. We believe that WhaleProver can be used as a test bench for different inference procedures and strategies, as well as for educational purposes.Undecidability of \(\mathbb{Q}^{(2)} \).https://www.zbmath.org/1455.111662021-03-30T15:24:00+00:00"Martínez-Ranero, Carlos"https://www.zbmath.org/authors/?q=ai:martinez-ranero.carlos"Utreras, Javier"https://www.zbmath.org/authors/?q=ai:utreras.javier"Videla, Carlos R."https://www.zbmath.org/authors/?q=ai:videla.carlos-rThe main result of the paper being reveiwed here is the undecidability of the full first-order theory in the language of rings of a field of algebraic numbers that is the compositum of all extensions of degree 2 over \(\mathbb Q\). Videla showed in an earlier paper that the ring of integers of such a field has a first-order definition over the field, and thus it would be enough to show that the the ring of integers of this field has an undecidable first-order theory in the language of rings. To do this, the authors use a method of J. Robinson as modified by Hanson:
Let \(R\) be a ring of algebraic integers and let \({\mathcal F} \subset {\mathcal P}(R)\) be a family of
subsets of \(R\) parametrised by a language of the rings formula \(\phi(x; y_1, \ldots, y_n)\), i.e.,
\[
F \in {\mathcal F} \Leftrightarrow \exists b_1, \ldots, b_n \in R| \forall x \in R, x\in F \Leftrightarrow \phi(x; b_1, \dots , b_n).
\]
If the family \({\mathcal F}\) contains sets of arbitrary large finite cardinality, then the theory of
the ring Th(R) is undecidable.
This is a nice result, and the proof is very short.
Reviewer: Alexandra Shlapentokh (Greenville)Commutative ideals of BCK-algebras based on uni-hesitant fuzzy set theory.https://www.zbmath.org/1455.060092021-03-30T15:24:00+00:00"Aldhafeeri, Shuaa"https://www.zbmath.org/authors/?q=ai:aldhafeeri.shuaa"Muhiuddin, G."https://www.zbmath.org/authors/?q=ai:muhiuddin.ghulamRelations between uni-hesitant fuzzy commutative ideals and uni-hesitant fuzzy ideals of BCK-algebras are discussed. Conditions for a uni-hesitant
fuzzy ideal to be a uni-hesitant fuzzy commutative ideal are provided.
Extension property for a uni-hesitant fuzzy commutative ideal is
established. A part of results is a consequence of the so-called transfer principle for fuzzy sets.
Reviewer: Wiesław A. Dudek (Wrocław)A characterization of the countable paracompactness for products of ordinals.https://www.zbmath.org/1455.540082021-03-30T15:24:00+00:00"Hirata, Yasushi"https://www.zbmath.org/authors/?q=ai:hirata.yasushi"Yajima, Yukinobu"https://www.zbmath.org/authors/?q=ai:yajima.yukinobuLet \(A\) and \(B\) be subspaces of an uncountable ordinal, \(X\) be a topological space and \(e(X)=\mathrm{sup}\{|D|:D\) is a closed discrete subset of \(X\}+\omega\) be the extent of \(X\).
\textit{N. Kemoto} et al. [Topology Appl. 45, No. 3, 245--260 (1992; Zbl 0789.54006)] found a set-theoretic condition for the countable paracompactness of \(A\times B\).
The authors of this paper were able to find a simpler condition than the one mentioned above. In their main Theorem 3.3 they prove that the countable paracompactness of \(A\times B\) is equivalent to the following: if a closed rectangle \(A'\times B'\) of \(A\times B\) contains a closed discrete subset of size \(\kappa\), where \(\kappa\) is a regular uncountable cardinal, then either \(A'\) or \(B'\) also contains a closed discrete subset of size \(\kappa\).
Assuming that there is no weakly inaccessible cardinal, in their Corollary 4.2 the authors also show that \(A\times B\) is countably paracompact if and only if \(e(A'\times B')=e(A')+e(B')\) holds true for every closed rectangle \(A'\times B'\) of \(A\times B\).
Reviewer: Ivan S. Gotchev (New Britain)Semigroups in stable structures.https://www.zbmath.org/1455.030462021-03-30T15:24:00+00:00"Halevi, Yatir"https://www.zbmath.org/authors/?q=ai:halevi.yatirSummary: Assume that \(G\) is a definable group in a stable structure \(M\). \textit{L. Newelski} [J. Symb. Log. 79, No. 4, 1199--1223 (2014; Zbl 1353.03022)] showed that the semigroup \(S_{G}(M)\) of complete types concentrated on \(G\) is an inverse limit of the \(\infty\)-definable (in \(M^{\text{eq}}\)) semigroups \(S_{G,\Delta}(M)\). He also showed that it is strongly \(\pi\)-regular: for every \(p\in S_{G,\Delta}(M)\), there exists \(n\in\mathbb{N}\) such that \(p^{n}\) is in a subgroup of \(S_{G,\Delta}(M)\). We show that \(S_{G,\Delta}(M)\) is in fact an intersection of definable semigroups, so \(S_{G}(M)\) is an inverse limit of definable semigroups, and that the latter property is enjoyed by all \(\infty\)-definable semigroups in stable structures.Set mappings on 4-tuples.https://www.zbmath.org/1455.030602021-03-30T15:24:00+00:00"Mohsenipour, Shahram"https://www.zbmath.org/authors/?q=ai:mohsenipour.shahram"Shelah, Saharon"https://www.zbmath.org/authors/?q=ai:shelah.saharonSummary: In this article, we study set mappings on 4-tuples. We continue a previous work of Komjath and Shelah by getting new finite bounds on the size of free sets in a generic extension. This is obtained by an entirely different forcing construction. Moreover, we prove a ZFC result for set mappings on 4-tuples. Also, as another application of our forcing construction, we give a consistency result for set mappings on triples.A partition theorem of \(\omega^{\omega^{\alpha}}\).https://www.zbmath.org/1455.030582021-03-30T15:24:00+00:00"Piña, Claribet"https://www.zbmath.org/authors/?q=ai:pina.claribetSummary: We consider finite partitions of the closure \(\overline{\mathcal{F}}\) of an \(\omega^{\alpha}\)-uniform barrier \(\mathcal{F}\). For each partition, we get a homogeneous set having both the same combinatorial and topological structure as \(\overline{\mathcal{F}}\), seen as a subspace of the Cantor space \(2^{\mathbb{N}}\).On the spectrum of characters of ultrafilters.https://www.zbmath.org/1455.030592021-03-30T15:24:00+00:00"Garti, Shimon"https://www.zbmath.org/authors/?q=ai:garti.shimon"Magidor, Menachem"https://www.zbmath.org/authors/?q=ai:magidor.menachem"Shelah, Saharon"https://www.zbmath.org/authors/?q=ai:shelah.saharonSummary: We show that the character spectrum \(\mathrm{Sp}_{\chi}(\lambda)\) (for a singular cardinal \(\lambda\) of countable cofinality) may include any prescribed set of regular cardinals between \(\lambda\) and \(2^{\lambda}\).Ehrenfeucht's lemma in set theory.https://www.zbmath.org/1455.030652021-03-30T15:24:00+00:00"Fuchs, Gunter"https://www.zbmath.org/authors/?q=ai:fuchs.gunter"Gitman, Victoria"https://www.zbmath.org/authors/?q=ai:gitman.victoria"Hamkins, Joel David"https://www.zbmath.org/authors/?q=ai:hamkins.joel-davidSummary: Ehrenfeucht's lemma asserts that whenever one element of a model of Peano arithmetic is definable from another, they satisfy different types. We consider here the analogue of Ehrenfeucht's lemma for models of set theory. The original argument applies directly to the ordinal-definable elements of any model of set theory, and, in particular, Ehrenfeucht's lemma holds fully for models of set theory satisfying \(V=\mathsf{HOD}\). We show that the lemma fails in the forcing extension of the universe by adding a Cohen real. We go on to formulate a scheme of natural parametric generalizations of Ehrenfeucht's lemma, namely, the principles of the form \(\mathsf{EL}(A,P,Q)\), which asserts that \(P\)-definability from \(A\) implies \(Q\)-discernibility. We also consider various analogues of Ehrenfeucht's lemma obtained by using algebraicity in place of definability, where a set \(b\) is algebraic in \(a\) if it is a member of a finite set definable from \(a\). Ehrenfeucht's lemma holds for the ordinal-algebraic sets, we prove, if and only if the ordinal-algebraic and ordinal-definable sets coincide. Using a similar analysis, we answer two open questions posed earlier by the third author and C. Leahy, showing that (i) algebraicity and definability need not coincide in models of set theory and (ii) the internal and external notions of being ordinal algebraic need not coincide.Short proofs for slow consistency.https://www.zbmath.org/1455.030782021-03-30T15:24:00+00:00"Freund, Anton"https://www.zbmath.org/authors/?q=ai:freund.anton"Pakhomov, Fedor"https://www.zbmath.org/authors/?q=ai:pakhomov.fedor-nFor a consistent, polynomial-time axiomatized theory \(T\) containing some arithmetic, let \(\mathrm{Con}_x(T)\) be a natural formalization of the statement that there is no proof of contradiction in \(T\) containing at most \(x\) symbols. [\textit{P. Pudlák}, Stud. Logic Found. Math. 120, 165--196 (1986; Zbl 0619.03037)] showed that for any standard natural number \(n\), a theory \(T\) as above can prove \(\mathrm{Con}_n(T)\) by a proof of size polynomial in \(n\). In contrast, Pudlák [loc. cit.] has also conjectured that \(T\) will no longer have polynomial-size proofs of \(\mathrm{Con}_n(T + \mathrm{Con}(T))\). The conjecture has important implications for computational complexity, propositional proof complexity, and related fields.
In this paper, the authors consider the problem whether PA has small proofs of \(\mathrm{Con}_n(\mathrm{PA} + \mathrm{Con}^*(\mathrm{PA}))\), where \(\mathrm{Con}^*(\mathrm{PA})\) is the ``slow consistency'' principle of [\textit{S.-D. Friedman} et al., Ann. Pure Appl. Logic 164, No. 3, 382--393 (2013; Zbl 1263.03055)]: ``for every \(x\) such that \(F_{\epsilon_0}(x)\) exists, \(\mathrm{Con}(\mathrm{I}\Sigma_x)\) holds''. Here, \(F_{\epsilon_0}\) is the \(\epsilon_0\)-th function in the Hardy hierarchy of fast-growing functions. \(\mathrm{PA}\) does not prove that \(F_{\epsilon_0}\) is a total function, and indeed \(\mathrm{PA} + \mathrm{Con}^*(\mathrm{PA})\) is strictly intermediate in strength between \(\mathrm{PA}\) and \(\mathrm{PA} + \mathrm{Con}(\mathrm{PA})\).
The main theorem of the paper is that \(\mathrm{PA}\) can prove \(\mathrm{Con}_n(\mathrm{PA} + \mathrm{Con}^*(\mathrm{PA}))\) by proofs of size polynomial in \(n\). Moreover, the result still holds if \(\mathrm{Con}^*(\mathrm{PA})\) is strengthened to a ``slow uniform \(\Pi_2\) reflection'' principle, \(\mathrm{RFN}^*_{\Pi_2}(\mathrm{PA})\), which says ``for every \(x\) such that \(F_{\epsilon_0}(x)\) exists, no false \(\Pi_2\) statement can be derived from \(\mathrm{PA}\) by a proof containing at most \(x\) symbols''.
The proof of the main theorem has two major ingredients. The first of these is showing that already \(\mathrm{I}\Sigma_1\) proves ``for every \(x\), if \(F_{\epsilon_0}(x)\) exists, then \(\mathrm{Con}_x(\mathrm{PA} + \mathrm{Con}^*(\mathrm{PA}))\) holds''. This is achieved by interpreting \(\mathrm{RFN}^*_{\Pi_2}(\mathrm{PA})\) as a sentence expressing the totality of a function that grows considerably slower than \(F_{\epsilon_0}\), and then analyzing that sentence in terms of an infinitary proof system due to \textit{W. Buchholz} and \textit{S. Wainer} [Contemp. Math. 65, 179--198 (1987; Zbl 0635.03056)]. Proving the main theorem then comes down to showing that for standard \(n\), \(\mathrm{PA}\) is able to prove the existence of the value \(F_{\epsilon_0}(n)\) by proofs of size polynomial in \(n\). Such proofs are obtained using the transfinite induction available in \(\mathrm{PA}\). Their construction is more or less as expected but with some technical wrinkles.
Interestingly, the statement ``for every \(x\), if \(F_{\epsilon_0}(x)\) exists, then \(\mathrm{Con}_x(\mathrm{PA} + \mathrm{Con}(\mathrm{PA}))\) holds'' is unprovable even in \(\mathrm{PA}\). This may suggest that the main theorem of the paper says more about the weakness of \(\mathrm{Con}^*(\mathrm{PA})\) compared to \(\mathrm{Con}(\mathrm{PA})\) than about Pudlák's conjecture [loc. cit.] as such.
Reviewer: Leszek Aleksander Kołodziejczyk (Warszawa)Coding and definability in computable structures.https://www.zbmath.org/1455.030562021-03-30T15:24:00+00:00"Montalbán, Antonio"https://www.zbmath.org/authors/?q=ai:montalban.antonioSummary: These are the lecture notes from a 10-hour course that the author gave at the University of Notre Dame in September 2010. The objective of the course was to introduce some basic concepts in computable structure theory and develop the background needed to understand the author's research on back-and-forth relations.On a metric generalization of the \(tt\)-degrees and effective dimension theory.https://www.zbmath.org/1455.030552021-03-30T15:24:00+00:00"Kihara, Takayuki"https://www.zbmath.org/authors/?q=ai:kihara.takayukiIn classical computability, tt-reducibility can be characterised as follows: \(A \leq_\text{tt} B\) iff there exists a total computable functional \(\Phi\colon 2^\omega \to 2^\omega\) such that \(\Phi(A) = B\). \textit{T. H. McNicholl} and \textit{J. Rute} [``A uniform reducibility in computably presented Polish spaces'', talk held at AMS sectional meeting AMS special session on ``effective mathematics in discrete and continuous worlds'', October 28--30, 2016] generalised this to a metric setting. For computable metric spaces \(\mathcal{X}\) and \(\mathcal{Y}\) and points \(x \in \mathcal{X}\), \(y \in \mathcal{Y}\), \(x \leq_\text{tt} y\) if there is a total computable functional \(\Phi\colon \omega^\omega \to \omega^\omega\) mapping every Cauchy name of \(x\) to one of \(y\).
The author further explores the metric \(\leq_\text{tt}\) relation and the associated degree structure. A first-level Borel function \(f\colon \mathcal{X} \to \mathcal{Y}\) is one for which the preimage of any F\(_\sigma\) set is F\(_\sigma\); the author shows that \(\omega \times \mathcal{X}\) and \(\omega \times \mathcal{Y}\) are first-level Borel isomorphic iff they have the same tt-degree structures relative to a common oracle.
In \S3, metric tt-degrees are used to connect (effective) topological dimension to the Schnorr packing dimension \(\operatorname{dim}^\text{Sch}_P\) of \textit{R. Downey} et al. [Math. Struct. Comput. Sci. 16, No. 5, 789--811 (2006; Zbl 1125.03033)]. The main result is that every point in an \(n\)-dimensional computable compact metric space is tt-equivalent to some \(y\) with \(\operatorname{dim}^\text{Sch}_P(y) \leq n\).
Reviewer: Jordan Mitchell Barrett (Wellington)Full-blooded anti-exceptionalism about logic.https://www.zbmath.org/1455.030052021-03-30T15:24:00+00:00"da Costa, Newton C. A."https://www.zbmath.org/authors/?q=ai:da-costa.newton-carneiro-affonso"Becker Arenhart, Jonas R."https://www.zbmath.org/authors/?q=ai:arenhart.jonas-rafael-beckerSummary: Problems of logical theory choice are current being widely discussed in the context of anti-exceptionalist views on logic. According to those views, logic is not a special science among others, so, in particular, the methodology for theory choice should be the same in logic as for other scientific disciplines. Richard Routley advanced one such methodology which meshes well with anti-exceptionalism, and argued that it leads one to choosing one single logic, which is a kind of ultralogic. We argue that the choice for only one correct system of logic may be rejected on the basis of the methodology proposed by Routley and, furthermore, that taking anti-exceptionalism about logic seriously recommends that a pluralist view of logic should be accepted. We call this view ``full-blooded anti-exceptionalism'', and the resulting view on logic, lacking a proper name, ``local pluralism''.Starting the dismantling of classical mathematics.https://www.zbmath.org/1455.030242021-03-30T15:24:00+00:00"Brady, Ross T."https://www.zbmath.org/authors/?q=ai:brady.ross-thomasSummary: This paper uses the relevant logic, MCQ, of meaning containment to explore mathematics without various classical theses, in particular, without the law of excluded middle.Syllogistic logic with cardinality comparisons, on infinite sets.https://www.zbmath.org/1455.030392021-03-30T15:24:00+00:00"Moss, Lawrence S."https://www.zbmath.org/authors/?q=ai:moss.lawrence-s"Topal, Selçuk"https://www.zbmath.org/authors/?q=ai:topal.selcukThis paper presents a study of what the author calls ``extended syllogistic logics''. These logics deal with expressions of the form \(\forall (p, q)\), \(\exists (p, q)\), \(\exists^\geq (p, q)\), and \(\exists^> (p, q)\), which are to be read as ``All \(p\) are \(q\)'', ``Some \(p\) are \(q\)'', ``There are at least as many \(p\) as \(q\)'', and ``There are more \(p\) than \(q\)'' respectively. Variables \(p\), \(q\), etc. stand for nouns, which can also be complemented, so that \(\overline{p}\), \(\overline{q}\), etc. are also nouns. One defines an interpretation function \([[{\, }]]\) as a map from the set of nouns to the power set of a universe of discourse, interpreting thus nouns as subsets of the universe \(M\). There is an additional property that for all \(p\), \([[\overline{p}]] = M\,\backslash\,[[p]]\) for all nouns \(p\). A satisfaction relation between models and expressions of the language is defined as follows: \(\mathcal{M}\models \forall (p, q)\) iff \([[p]] \subseteq [[q]]\); \(\mathcal{M}\models \exists (p, q)\) iff \([[p]] \cap [[q]] \neq\emptyset\); \(\mathcal{M}\models \exists^\geq (p, q)\) iff \(\operatorname{card}[[p]] \geq \operatorname{card}[[q]]\); \(\mathcal{M}\models \exists^> (p, q)\) iff \(\operatorname{card}[[p]] > \operatorname{card}[[q]]\), where \(\operatorname{card} S\) stands for the cardinality of a given set \(S\). Importantly, \([[p]]\) and \([[q]]\) could be empty or infinite, but not necessarily so. The consequence relation \(\Gamma \models\varphi\) is defined as usual, saying that in any model \(\mathcal{M} \), \(\mathcal{M} \models [[\varphi]]\) whenever \(\mathcal{M} \models [[\Gamma]]\). The author constructs a proof system which formalizes the semantic consequence relation so defined, and proves the soundness and completeness theorems for this system.
Reviewer: Yaroslav Shramko (Kryvyi Rih)Regularized models of audiovisual integration of speech with predictive power for sparse behavioral data.https://www.zbmath.org/1455.911882021-03-30T15:24:00+00:00"Andersen, Tobias S."https://www.zbmath.org/authors/?q=ai:andersen.tobias-s"Winther, Ole"https://www.zbmath.org/authors/?q=ai:winther.oleSummary: Audiovisual integration can facilitate speech comprehension by integrating information from lip-reading with auditory speech perception. When incongruent acoustic speech is dubbed onto a video of a talking face, this integration can lead to the McGurk illusion of hearing a different phoneme than that spoken by the voice. Several computational models of the information integration process underlying these phenomena exist. All are based on the assumption that the integration process is, in some sense, optimal. They differ, however, in assuming that it is based on either continuous or categorical internal representations. Here we develop models of audiovisual integration of the phonetic information represented on an internal representation that is continuous and cyclical. We compare these models to the fuzzy logical model of perception (FLMP), which is based on a categorical internal representation. Using cross-validation, we show that model evaluation criteria based on the goodness-of-fit are poor measures of the models' generalization error even if they take the number of free parameters into account. We also show that the predictive power of all the models benefit from regularization that limits the precision of the internal representation. Finally, we show that, unlike the FLMP, models based on a continuous internal representation have good predictive power when properly regularized.Int-soft implicative hyper BCK-ideals in hyper BCK-algebras.https://www.zbmath.org/1455.060102021-03-30T15:24:00+00:00"Borzooei, Rajab Ali"https://www.zbmath.org/authors/?q=ai:borzooei.rajab-ali"Xin, Xiao Long"https://www.zbmath.org/authors/?q=ai:xin.xiaolong"Roh, Eun Hwan"https://www.zbmath.org/authors/?q=ai:roh.eun-hwan"Jun, Young Bae"https://www.zbmath.org/authors/?q=ai:jun.young-baeRelations between various types of int-soft hyper BCK-ideals are discussed.
Conditions for an int-soft hyper BCK-ideal to be an int-soft weak
implicative hyper BCK-ideal are provided. Using an int-soft weak
implicative hyper BCK-ideal, a new int-soft weak implicative hyper
BCK-ideal is established.
Reviewer: Wiesław A. Dudek (Wrocław)Weak completeness notions for exponential time.https://www.zbmath.org/1455.680682021-03-30T15:24:00+00:00"Ambos-Spies, Klaus"https://www.zbmath.org/authors/?q=ai:ambos-spies.klaus"Bakibayev, Timur"https://www.zbmath.org/authors/?q=ai:bakibayev.timurIn the present paper, the authors investigate reduction notions that can be employed in the context of linear exponential time (E).
It is well known that the complexity class E is not closed under polynomial many-to-one reductions (Lemma 1) through a padding argument.
Because of that, \textit{J. H. Lutz} [SIAM J. Comput. 24, No. 6, 1170--1189 (1995; Zbl 0845.68048)] formalised in a way a type of measure for that class.
The authors introduce two weak hardness notions for E, namely, (strong) E-nontriviality.
Intuitively, a subclass of E is negligible if it is contained in some \(\mathrm{E}_k= \mathrm{DTIME}(2^{kn})\) in the exponential-time hierarchy.
Arguing that ``E-nontriviality is the most general weak hardness notion for E'', the authors stress that it ``generalised E-hardness and implies intractability but that it also reflects the internal, hierarchical structure of E hence considers finite parts of the linear exponential time hierarchy to be negligible.''
The strong variant of this concept lies strictly between the weak notion and the ones of measure- and category-hardnesses.
The authors give a verbose overview of the sections in the introduction and motivate quite well.
Section 2 then handles the new central notions and Lemma 3 is an important result showing how meaningful their approach is.
Theorem 1 characterises the strong variant via \(\mathrm{E}_1\)-bi-immune sets (a set \(A\) is \(C\)-bi-immune for a class \(C\) if there is no infinite \(B\in C\) such that \(B\subseteq A\) or \(B\cap A=\emptyset\)).
Section 3 provides then some examples.
First, the existence of an E-trivial set in \(\mathrm{E}\setminus \mathrm{P}\) (Theorem 2), but also E-trivial sets in arbitrarily high levels \(\mathrm{E}\setminus \mathrm{E}_k\) of the E-hierarchy (Theorem 4).
Section 4 considers sparse and tally sets in this context.
The authors show the existence of an E-category-complete set which is sparse and that no such set is tally (Theorem 8).
Yet, there are tally sets which are strongly E-nontrivial (Theorem 9).
The authors show the context when tally sets are E-nontrivial (Theorem 10) and when even an E-nontrivial set is exptally (Corollary 2) which is also not strongly E-nontrivial (Corollary 3).
Theorem 13 then gives the context for a set \(A\) to be E-hard, E-measure-hard, E-category-hard, strongly E-nontrivial, E-nontrivial, and intractable (in this order).
Section 5 talks about information content. Can one, from splitting ``a weakly complete set \(A\) into two parts \(A_0\) and \(A_1\)'', deduce weak completeness for either of them?
The authors show that this is true for E-nontriviality but for the remainder of the weak completeness notions this is false.
Reviewer: Arne Meier (Hannover)On the relationship between \(L\)-fuzzy closure spaces and \(L\)-fuzzy rough sets.https://www.zbmath.org/1455.030732021-03-30T15:24:00+00:00"Yadav, Vijay K."https://www.zbmath.org/authors/?q=ai:yadav.vijay-k"Yadav, Swati"https://www.zbmath.org/authors/?q=ai:yadav.swati"Tiwari, S. P."https://www.zbmath.org/authors/?q=ai:tiwari.s-pSummary: This work is towards the establishment of bijective correspondence between the family of all \(L\)-fuzzy reflexive/tolerance approximation spaces and the family of all quasi-discrete L-fuzzy closure spaces satisfying a certain condition.
For the entire collection see [Zbl 1411.65006].Sailing over three problems of Koszmider.https://www.zbmath.org/1455.460282021-03-30T15:24:00+00:00"Cabello Sánchez, Félix"https://www.zbmath.org/authors/?q=ai:cabello-sanchez.felix"Castillo, Jesús M. F."https://www.zbmath.org/authors/?q=ai:castillo.jesus-m-f"Marciszewski, Witold"https://www.zbmath.org/authors/?q=ai:marciszewski.witold"Plebanek, Grzegorz"https://www.zbmath.org/authors/?q=ai:plebanek.grzegorz"Salguero-Alarcón, Alberto"https://www.zbmath.org/authors/?q=ai:salguero-alarcon.albertoSummary: We discuss three problems of \textit{P. Koszmider} [Proc. Am. Math. Soc. 133, No. 7, 2137--2146 (2005; Zbl 1085.46015)] on the structure of the spaces of continuous functions on the Stone compact \(K_{\mathcal{A}}\) generated by an almost disjoint family \(\mathcal{A}\) of infinite subsets of \(\omega \) -- we present a solution to two problems and develop previous results of \textit{W. Marciszewski} and \textit{R. Pol} answering the third one [J. Math. Anal. Appl. 350, No. 2, 708--722 (2009; Zbl 1167.46311)]. We will show, in particular, that assuming Martin's axiom, the space \(C( K_{\mathcal{A}})\) is uniquely determined up to isomorphism by the cardinality of \(\mathcal{A}\) whenever \(| \mathcal{A} | < \mathfrak{c} \), while there are \(2^{\mathfrak{c}}\) nonisomorphic spaces \(C( K_{\mathcal{A}})\) with \(| \mathcal{A} | = \mathfrak{c} \). We also investigate Koszmider's problems in the context of the class of separable Rosenthal compacta and indicate the meaning of our results in the language of twisted sums of \(c_0\) and some \(C(K)\) spaces.A logic for the discovery of deterministic causal regularities.https://www.zbmath.org/1455.030362021-03-30T15:24:00+00:00"Beirlaen, Mathieu"https://www.zbmath.org/authors/?q=ai:beirlaen.mathieu"Leuridan, Bert"https://www.zbmath.org/authors/?q=ai:leuridan.bert"Van De Putte, Frederik"https://www.zbmath.org/authors/?q=ai:van-de-putte.frederikSummary: We present a logic, \(\mathbf {ELI^r}\), for the discovery of deterministic causal regularities starting from empirical data. Our approach is inspired by Mackie's theory of causes as INUS-conditions, and implements a more recent adjustment to Mackie's theory according to which the left-hand side of causal regularities is required to be a minimal disjunction of minimal conjunctions. To derive such regularities from a given set of data, we make use of the adaptive logics framework. Our knowledge of deterministic causal regularities is, as Mackie noted, most often gappy or elliptical. The adaptive logics framework is well-suited to explicate both the internal and the external dynamics of the discovery of such gappy regularities. After presenting \(\mathbf {ELI^r}\), we first discuss these forms of dynamics in more detail. Next, we consider some criticisms of the INUS-account and show how our approach avoids them, and we compare \(\mathbf {ELI^r}\) with the CNA algorithm that was recently proposed by Michael Baumgartner.Questions as information types.https://www.zbmath.org/1455.030382021-03-30T15:24:00+00:00"Ciardelli, Ivano"https://www.zbmath.org/authors/?q=ai:ciardelli.ivano-aSummary: This paper argues that questions have an important role to to play in logic, both semantically and proof-theoretically. Semantically, we show that by generalizing the classical notion of entailment to questions, we can capture not only the standard relation of logical consequence, which holds between pieces of information, but also the relation of logical \textit{dependency}, which holds between information \textit{types}. Proof-theoretically, we show that questions may be used in inferences as placeholders for arbitrary information of a given type; by manipulating such placeholders, we may construct formal proofs of dependencies. Finally, we show that such proofs have a specific kind of constructive content: they do not just witness the existence of a certain dependency, but actually encode a method for transforming information of the types described by the assumptions into information of the type described by the conclusion.General non-commutative locally compact locally Hausdorff Stone duality.https://www.zbmath.org/1455.060052021-03-30T15:24:00+00:00"Bice, Tristan"https://www.zbmath.org/authors/?q=ai:bice.tristan-matthew"Starling, Charles"https://www.zbmath.org/authors/?q=ai:starling.charlesClassical Stone duality constructs a contravariant equivalence between the categories of \(0\)-dimensional compact Hausdorff
spaces (plus continuous maps) and Boolean algebras (plus homomorphisms). On the one side there is a category of topological structures and continuous homomorphisms; on the other there is a category whose objects constitute an elementary productive class -- in the model-theoretic sense -- of finitary relational structures. (Another famous example of this phenomenon is Pontryagin duality between the compact Hausdorff and the discrete abelian groups.) In the early 1980s, this reviewer asked whether Stone duality could be properly extended to a full subcategory of the compact Hausdorff spaces -- in such a way that the dual category is still an elementary productive class -- and \textit{B. Banaschewski} [Can. J. Math. 36, 1113--1118 (1984; Zbl 0561.18004)] gave an elegant proof that it could not. In the present paper, the authors take a different approach to the problem of going beyond \(0\)-dimensionality and set about showing that ``certain bases of general locally compact locally Hausdorff étale groupoids are dual to a natural first order finitely axiomatizable class of inverse semigroups.'' The details are quite involved, and the interested reader is invited to consult the paper.
Reviewer: Paul Bankston (Milwaukee)Computable numberings of families of infinite sets.https://www.zbmath.org/1455.030532021-03-30T15:24:00+00:00"Dorzhieva, M. V."https://www.zbmath.org/authors/?q=ai:dorzhieva.marina-valerianovnaA Friedberg numbering of a set is an effective enumeration of the set's members without repetition. In [Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys. 6, 1--5 (1958; Zbl 0084.24902)] \textit{R. M. Friedberg} gave such an enumeration of the c.e. sets. This paper shows by diagonal argument that there is no such enumeration for the infinite c.e. sets. Extending these arguments to the analytical hierarchy, there is neither a \(\pi^1_1\)-computable numbering for all infinite \(\pi^1_1\) sets, nor a \(\varepsilon^1_2\)-computable numbering for all infinite \(\varepsilon^1_2\) sets.
Moreover, that for \(k>2\) there is no \(\varepsilon^1_k\)-computable numbering of the infinite \(\varepsilon^1_k\) sets is a consequence of Gödel's axiom of constructibility, whence existence of such an ordering is unprovable in ZF. Whether or not its nonexistence is provable in ZF is an open question.
Reviewer: Joseph S. Ullian (Santa Barbara)Adding an abstraction barrier to ZF set theory.https://www.zbmath.org/1455.682562021-03-30T15:24:00+00:00"Dunne, Ciarán"https://www.zbmath.org/authors/?q=ai:dunne.ciaran"Wells, J. B."https://www.zbmath.org/authors/?q=ai:wells.joe-b"Kamareddine, Fairouz"https://www.zbmath.org/authors/?q=ai:kamareddine.fairouz-dSummary: Much mathematical writing exists that is, explicitly or implicitly, based on set theory, often Zermelo-Fraenkel set theory (ZF) or one of its variants. In ZF, the domain of discourse contains only sets, and hence every mathematical object must be a set. Consequently, in ZF with the usual encoding of an ordered pair \(\langle a,b\rangle\), formulas like \(\{a\}\in\langle a,b\rangle\) have truth values, and operations like \(\mathcal{P}{(\langle a,b\rangle)}\) have results that are sets. Such ``accidental theorems'' do not match how people think about the mathematics and also cause practical difficulties when using set theory in machine-assisted theorem proving. In contrast, in a number of proof assistants, mathematical objects and concepts can be built of type-theoretic stuff so that many mathematical objects can be, in essence, terms of an extended typed \(\lambda\)-calculus. However, dilemmas and frustration arise when formalizing mathematics in type theory.
Motivated by problems of formalizing mathematics with (1) purely set-theoretic and (2) type-theoretic approaches, we explore an option with much of the flexibility of set theory and some of the useful features of type theory. We present ZFP: a modification of ZF that has ordered pairs as primitive, non-set objects. ZFP has a more natural and abstract axiomatic definition of ordered pairs free of any notion of representation. This paper presents axioms for ZFP, and a proof in ZF (machine-checked in Isabelle/ZF) of the existence of a model for ZFP, which implies that ZFP is consistent if ZF is. We discuss the approach used to add this abstraction barrier to ZF.
For the entire collection see [Zbl 1452.68005].On elementary theories of algebraically closed groups.https://www.zbmath.org/1455.030452021-03-30T15:24:00+00:00"Durnev, Valeriĭ Georgievich"https://www.zbmath.org/authors/?q=ai:durnev.valerii-georgievich"Zetkina, Oksana Valer'evna"https://www.zbmath.org/authors/?q=ai:zetkina.oksana-valerevna"Zetkina, Alena Igor'evna"https://www.zbmath.org/authors/?q=ai:zetkina.alena-igorevnaSummary: In paper for any algebraically closed group \(G\), as well as for the class of the algebraically closed groups, we prove algorithmic undecidability of the positive \(\forall^2 \exists^{24}\)-theory and \(\forall^3 \exists^2\)-theory. For an arbitrary \(g\in G\), we also prove the decidability of the equation of the type
\[w(x_1, \ldots , x_n) = g,\]
where \(w(x_1, \ldots , x_n)\) is a non-empty irreducible word in the unknowns \(x_1,\ldots x_n\in G\).Mathematical writings 1804--1810. Edited by Steve Russ and Edgar Morscher.https://www.zbmath.org/1455.010382021-03-30T15:24:00+00:00"Bolzano, Bernard"https://www.zbmath.org/authors/?q=ai:bolzano.bernardThis volume opens the first series of the \textit{Bernard Bolzano Gesamtausgabe} (BGA), containing the writings which appeared during Bolzono's lifetime, of which 26 volumes have already been published (among them eight volumes of the \textit{Lehrbuch der Religionswissenschaft}, and twelve volumes of the eminent \textit{Wissenschaftslehre}). Bolzano started his publication activities with mathematical writings: his \textit{Betrachtungen über einige Gegenstände der Elementargeometrie} of 1804, and after having become Professor of Religious Studies at Prague University in 1805, his \textit{Beyträge zu einer begründeteren Darstellung der Mathematik} (1810). In his introductory ``Preface'', E.\ Morscher relates this volume to the BGA and its editorial principles.
The two small monographies are critically edited and introduced by S. Russ and E. Morscher. The editor's introduction (pp.\ 13--16) to Bolzano's first book \textit{Betrachtungen über einige Gegenstände der Elementargeometrie} (pp. 18--80) is very informative sketching Bolzano's basic ideas and relating them to the mathematics of his time. Bolzano intends a methodological renewal of geometry, challenging the claim of evidence without proof and rejecting the application of the concept of movement in geometrical proofs. He argues that the theory of movement presupposes the theory of space, so the use of the concept of movement in geometry entails a \textit{petitio principii} (pp.\ 24--25).
In their helpful introduction (pp.\ 83--90) to the \textit{Beyträge} (pp.\ 92--166), the editors call them a turning point in the view on mathematical concepts, axioms, theorems and proofs (p.\ 83).
In the first part ``On the concept of mathematics and its distinction'', Bolzano defines mathematics as the science of general laws (forms) which have to be followed by the things in their being (\S\ 8), with this definition deviating from the traditional concept of mathematics as the theory of magnitudes. In the second part ``On the mathematical method'', Bolzano discusses foundational metamathematical concepts like ``\textit{Erklärungen}'' (i.e., declarations, definitions), and ``\textit{Grundsätze}'' (i.e., principles), the last standing for an \textit{objective} truth independent of an arbitrary subjective acceptance. These principles cannot be proved, but do not need any proof, a condition discussed extensively (\S\S\ 10--16). Bolzano takes up I. Kant's distinction between analytical and synthetical judgements, but denies the possibility that analytical judgements could be principles. The \textit{Beyträge} are closed by an appendix ``On Kantian doctrine of the construction of concepts by intuition'', i.e., the Kantian definition of doing mathematics (pp.\ 159--166), criticizing in particular Kant's concept of (pure and empirical) intuition.
The volume is closed by a comprehensive bibliography, indices of persons (with further information on the persons mentioned) and matters.
Reviewer: Volker Peckhaus (Paderborn)Computer says no: verdict explainability for runtime monitors using a local proof system.https://www.zbmath.org/1455.681032021-03-30T15:24:00+00:00"Francalanza, Adrian"https://www.zbmath.org/authors/?q=ai:francalanza.adrian"Cini, Clare"https://www.zbmath.org/authors/?q=ai:cini.clareSummary: Monitors in Runtime Verification are often constructed as black boxes: they provide verdicts on whether a property is satisfied or violated by the executing system under scrutiny, without much explanation as to why this is the case. In the best of cases, monitors might also return the trace observed, still leaving it up to the user to figure out the logic employed to reach the declared verdict from this trace. In this paper, we propose a local proof system for Linear Temporal Logic -- a popular logic used in Runtime Verification -- formalising the symbolic deductions within the constraints of Runtime Verification. We prove novel soundness and partial completeness results for this proof system with respect to the original semantics of the logic. Crucially, we show how such a deductive system can be used as a realistic basis for constructing online runtime monitors that provide explanations for their verdicts; we also show the resulting monitor algorithms to satisfy pleasing correctness criteria identified by other works, such as the decidability and incrementality of the analysis and the irrevocability of verdicts. Finally, we relate the expressiveness of the Linear Temporal Logic proof system to existing symbolic analysis techniques used in Runtime Verification.Abstract consequence and logics. Essays in honor of Edelcio G. de Souza.https://www.zbmath.org/1455.030012021-03-30T15:24:00+00:00"Costa-Leite, Alexandre (ed.)"https://www.zbmath.org/authors/?q=ai:costa-leite.alexandrePublisher's description: Edelcio G. de Souza (University of São Paulo, Brazil) is a Brazilian logician and philosopher who has researches in the domains of abstract logic, non-classical systems, philosophy of science and the foundations of mathematics. This book is in his honor with the purpose of celebrating his 60th birthday. It contains some articles connected with the above topics and other subjects in logical investigations.
The articles of this volume will be reviewed individually.
Indexed articles:
\textit{Beziau, Jean-Yves}, Logical structures from a model-theoretical viewpoint, 3-16 [Zbl 07325803]
\textit{Schurz, Gerhard}, Universal translatability: optimality-based justification of (not necessarily) classical logic, 17-36 [Zbl 07325804]
\textit{Batchelor, Roderick}, Abstract logic with vocables, 37-65 [Zbl 07325805]
\textit{Maranhão, Juliano}, An abstract definition of normative system, 67-77 [Zbl 07325806]
\textit{da Costa, Newton C. A.; Krause, Decio}, Suppes predicate for classes of structures and the notion of transportability, 79-97 [Zbl 07325807]
\textit{Velasco, Patricia Del Nero}, On a reconstruction of the valuation concept, 99-112 [Zbl 07325808]
\textit{Vasyukov, Vladimir L.}, Internal logic of the \(H-B\) topos, 115-133 [Zbl 07325809]
\textit{Coniglio, Marcelo E.}, On categorial combination of logics, 135-171 [Zbl 07325810]
\textit{Carnielli, Walter; Fuenmayor, David}, Gödel's incompleteness theorems from a paraconsistent perspective, 173-197 [Zbl 07325811]
\textit{Almeida, Edgar L. B.; Freire, Rodrigo A.}, On existence in arithmetic, 199-218 [Zbl 07325812]
\textit{Avron, Arnon}, A note on semi-implication with negation, 221-226 [Zbl 07325813]
\textit{Costa, Diana; Martins, Manuel A.}, A roadmap of paraconsistent hybrid logics, 227-242 [Zbl 07325814]
\textit{de Araujo Feitosa, Hércules; Moreira, Angela Pereira Rodrigues; Soares, Marcelo Reicher}, A relational model for the logic of deduction, 243-249 [Zbl 07325815]
\textit{Schumann, Andrew}, From pragmatic truths to emotional truths, 251-261 [Zbl 07325816]
\textit{Bensusan, Hilan; Carneiro, Gregory}, Paraconsistentization through antimonotonicity towards a logic of supplement, 263-274 [Zbl 07325817]
\textit{Dias, Diogo H. B.}, Hans Hahn and the foundations of mathematics, 277-287 [Zbl 07325818]
\textit{Rodrigues, Cassiano Terra}, A first survey of Charles S. Peirce's contributions to logic: from relatives to quantification, 289-299 [Zbl 07325819]
\textit{Arenhart, Jonas R. B.; Molick, Sanderson}, On the very idea of choosing a logic: the role of the background logic, 301-320 [Zbl 07325820]
\textit{Frade, Lorenzzo; Rodrigues, Abilio}, Sous remarks on logical realism and logical pluralism, 321-339 [Zbl 07325821]
\textit{Prelević, Duško}, Modal rationalism, logical pluralism, and the metaphysioal foundation of logic, 341-357 [Zbl 07325822]
\textit{Schang, Fabien}, Quasi-concepts of logic, 359-389 [Zbl 07325823]Factor relation analysis for sustainable recycling partner evaluation using probabilistic linguistic DEMATEL.https://www.zbmath.org/1455.900912021-03-30T15:24:00+00:00"Li, Peng"https://www.zbmath.org/authors/?q=ai:li.peng.4|li.peng.1|li.peng|li.peng.2|li.peng.3"Liu, Ju"https://www.zbmath.org/authors/?q=ai:liu.ju"Wei, Cuiping"https://www.zbmath.org/authors/?q=ai:wei.cuipingSummary: Evaluating and selecting suitable sustainable recycling partners is a key work in sustainable supply chain management. In order to deal with the probabilistic linguistic influence relations between criteria and obtain the key factors that influence the evaluation results of sustainable recycling partners, we propose a new decision-making trial and evaluation laboratory (DEMATEL) method. First, we propose a new generalized weighted ordered weighted averaging (GWOWA) operator and discuss its properties. Second, we use probabilistic linguistic term sets (PLTSs) to aggregate the experts' hesitant fuzzy linguistic decision-making information and develop a novel method of transforming PLTSs into triangular fuzzy numbers (TFNs) based on the proposed GWOWA operator and the characteristics of PLTSs. Furthermore, we propose a method of making criteria relation analysis based on DEMATEL with TFNs. With the method, we not only access the importance weights of criteria but also obtain the influence relation among the criteria and cluster the criteria into two groups: cause group and effect group. Finally, we apply our method to a real case of sustainable recycling partner selection.Checking deadlock-freedom of parametric component-based systems.https://www.zbmath.org/1455.681022021-03-30T15:24:00+00:00"Bozga, Marius"https://www.zbmath.org/authors/?q=ai:bozga.marius"Iosif, Radu"https://www.zbmath.org/authors/?q=ai:iosif.radu"Sifakis, Joseph"https://www.zbmath.org/authors/?q=ai:sifakis.josephSummary: We propose an automated method for computing inductive invariants used to proving deadlock freedom of parametric component-based systems. The method generalizes the approach for computing structural trap invariants from bounded to parametric systems with general architectures. It symbolically extracts trap invariants from interaction formulae defining the system architecture. The paper presents the theoretical foundations of the method and proves its soundness. It also reports on a preliminary experimental evaluation on several textbook examples.(Co)inductive proof systems for compositional proofs in reachability logic.https://www.zbmath.org/1455.030402021-03-30T15:24:00+00:00"Rusu, Vlad"https://www.zbmath.org/authors/?q=ai:rusu.vlad"Nowak, David"https://www.zbmath.org/authors/?q=ai:nowak.david-eSummary: Reachability Logic is a formalism that can be used, among others, for expressing partial-correctness properties of transition systems. In this paper we present three proof systems for this formalism, all of which are sound and complete and inherit the coinductive nature of the logic. The proof systems differ, however, in several aspects. First, they use induction and coinduction in different proportions. The second aspect regards compositionality, broadly meaning their ability to prove simpler formulas on smaller systems and to reuse those formulas as lemmas for proving more complex formulas on larger systems. The third aspect is the difficulty of their soundness proofs.
We show that the more induction a proof system uses, and the more specialised is its use of coinduction (with respect to our problem domain), the more compositional the proof system is, but the more difficult is its soundness proof.
We present formalisations of these results in the Coq proof assistant. In particular we have developed support for coinductive proofs that is comparable to that provided by Coq for inductive proofs. This may be of interest to a broader class of Coq users.A navigational logic for reasoning about graph properties.https://www.zbmath.org/1455.681472021-03-30T15:24:00+00:00"Navarro, Marisa"https://www.zbmath.org/authors/?q=ai:navarro.marisa"Orejas, Fernando"https://www.zbmath.org/authors/?q=ai:orejas.fernando"Pino, Elvira"https://www.zbmath.org/authors/?q=ai:pino.elvira"Lambers, Leen"https://www.zbmath.org/authors/?q=ai:lambers.leenSummary: Graphs play an important role in many areas of Computer Science. In particular, our work is motivated by model-driven software development and by graph databases. For this reason, it is very important to have the means to express and to reason about the properties that a given graph may satisfy. With this aim, in this paper we present a visual logic that allows us to describe graph properties, including \textit{navigational} properties, i.e., properties about the paths in a graph. The logic is equipped with a deductive tableau method that we have proved to be sound and complete.Formal specification and verification.https://www.zbmath.org/1455.680162021-03-30T15:24:00+00:00"Merz, Stephan"https://www.zbmath.org/authors/?q=ai:merz.stephanFrom the introduction: This chapter focuses on the Temporal Logic of Actions (TLA) and the specification language \(\mathrm{TLA}^+\). These are Lamport's contributions to the formal specification and verification of algorithms that have had the greatest impact in the academic community and in industry.
For the entire collection see [Zbl 1434.68029].The admissible rules of \(\mathsf{BD}_2\) and \(\mathsf{GSc}\).https://www.zbmath.org/1455.030342021-03-30T15:24:00+00:00"Goudsmit, Jeroen P."https://www.zbmath.org/authors/?q=ai:goudsmit.jeroen-pSummary: The Visser rules form a basis of admissibility for the intuitionistic propositional calculus. We show how one can characterize the existence of covers in certain models by means of formulae. Through this characterization, we provide a new proof of the admissibility of a weak form of the Visser rules. Finally, we use this observation, coupled with a description of a generalization of the disjunction property, to provide a basis of admissibility for the intermediate logics \({{\mathsf{BD}_{2}}}\) and \({\mathsf{GSc}}\).Eliminating disjunctions by disjunction elimination.https://www.zbmath.org/1455.030742021-03-30T15:24:00+00:00"Rinaldi, Davide"https://www.zbmath.org/authors/?q=ai:rinaldi.davide"Schuster, Peter"https://www.zbmath.org/authors/?q=ai:schuster.peter-michael"Wessel, Daniel"https://www.zbmath.org/authors/?q=ai:wessel.danielSummary: Completeness and other forms of Zorn's Lemma are sometimes invoked for semantic proofs of conservation in relatively elementary mathematical contexts in which the corresponding syntactical conservation would suffice. We now show how a fairly general syntactical conservation theorem that covers plenty of the semantic approaches follows from an utmost versatile criterion for conservation given by [\textit{L. Henkin} (ed.) et al., Proceedings of the Tarski symposium. An international symposium held to honor Alfred Tarski on the occasion of his seventieth birthday. Held at the University of California, Berkeley, June 23-30, 1971. Providence, RI: American Mathematical Society (AMS) (1974; Zbl 0291.00009)].
To this end we work with multi-conclusion entailment relations as extending single-conclusion entailment relations. In a nutshell, the additional axioms with disjunctions in positive position can be eliminated by reducing them to the corresponding disjunction elimination rules, which in turn prove admissible in all known mathematical instances. In deduction terms this means to fold up branchings of proof trees by way of properties of the relevant mathematical structures.
Applications include the syntactical counterparts of the theorems or lemmas known under the names of \textit{E. Artin} and \textit{O. Schreier} [Abh. Math. Semin. Univ. Hamb. 5, 85--99 (1926; JFM 52.0120.05)], \textit{W. Krull} [Math. Ann. 101, 729--744 (1929; JFM 55.0681.01)], and \textit{E. Szpilrajn} [Fundam. Math. 16, 386--389 (1930; JFM 56.0843.02)]. Related work has been done before on individual instances, e.g., in locale theory, dynamical algebra, formal topology and proof analysis.A new vision of Zadeh's \(Z\)-numbers.https://www.zbmath.org/1455.682122021-03-30T15:24:00+00:00"Massanet, Sebastia"https://www.zbmath.org/authors/?q=ai:massanet.sebastia"Riera, Juan Vicente"https://www.zbmath.org/authors/?q=ai:riera.juan-vicente"Torrens, Joan"https://www.zbmath.org/authors/?q=ai:torrens.joanSummary: From their introduction \(Z\)-numbers have been deeply studied and many investigations have appeared trying to reduce the inherent complexity in their computation. In this line, this paper presents a new vision of \(Z\)-numbers based on discrete fuzzy numbers with support in a finite chain \(L_n\). In this new approach, a \(Z\)-number associated with a variable, \(X\), is a pair \((A,\,B)\) of discrete fuzzy numbers, where A is interpreted as a fuzzy restriction on \(X\), while the estimation of the reliability of \(A\) is interpreted as a linguistic valuation based on the discrete fuzzy number \(B\). In this non-probabilistic approach an aggregation method is proposed with the aim of applying it in group decision making problems.
For the entire collection see [Zbl 1385.68004].Algorithm for generating finite totally ordered monoids.https://www.zbmath.org/1455.060082021-03-30T15:24:00+00:00"Petrík, Milan"https://www.zbmath.org/authors/?q=ai:petrik.milan"Vetterlein, Thomas"https://www.zbmath.org/authors/?q=ai:vetterlein.thomasSummary: The semantics of fuzzy logic is typically based on negative totally ordered monoids. This contribution describes an algorithm generating in a step-wise fashion all finite structures of this kind.
For the entire collection see [Zbl 1385.68004].Uninorms on interval-valued fuzzy sets.https://www.zbmath.org/1455.030712021-03-30T15:24:00+00:00"Kalina, Martin"https://www.zbmath.org/authors/?q=ai:kalina.martin"Král, Pavol"https://www.zbmath.org/authors/?q=ai:kral.pavolSummary: This paper is a kind of continuation of the paper by
\textit{G. Deschrijver} [Inf. Sci. 244, 48--59 (2013; Zbl 1355.03041)].
In that paper he constructed uninorms whose neutral element is arbitrary of the type \(\mathbf{e}=(e,e)\) and annihilator, \(\mathbf{a}\), is arbitrary point that is incomparable with \(\mathbf{e}\). In the present paper we intend to show what are all possibilities of the position of the pair \((\mathbf{e},\mathbf{a})\).
For the entire collection see [Zbl 1385.68004].Graded dominance and Cantor-Bernstein equipollence of fuzzy sets.https://www.zbmath.org/1455.030702021-03-30T15:24:00+00:00"Holčapek, Michal"https://www.zbmath.org/authors/?q=ai:holcapek.michalSummary: The aim of the paper is to propose a graded dominance for fuzzy sets that assigns to each pair of fuzzy sets a degree in which one fuzzy set has less cardinality than another one or the cardinalities of both fuzzy sets are approximately equal. The graded dominance for fuzzy sets is a natural generalization of the dominance relation for sets. The graded dominance is then used for the introduction of a fuzzy class equivalence that satisfies a graded version of the Cantor-Bernstein theorem.
For the entire collection see [Zbl 1385.68004].On perception-based logical deduction with fuzzy inputs.https://www.zbmath.org/1455.682092021-03-30T15:24:00+00:00"Dvořák, Antonín"https://www.zbmath.org/authors/?q=ai:dvorak.antonin"Štěpnička, Martin"https://www.zbmath.org/authors/?q=ai:stepnicka.martinSummary: We present and analyze inference method called Perception-based Logical Deduction (PbLD) aimed at the treatment of fuzzy IF-THEN rules as linguistically expressed genuine logical implications. We analyze two variants of PbLD (original and balancing) that differ in the selection of fired IF-THEN rules. We concentrate on a situation when inputs into inference are fuzzy sets (fuzzy inputs). We study the conditions under which both variants fulfill the interpolativity property.
For the entire collection see [Zbl 1385.68004].Towards fuzzy partial set theory.https://www.zbmath.org/1455.030672021-03-30T15:24:00+00:00"Běhounek, Libor"https://www.zbmath.org/authors/?q=ai:behounek.libor"Daňková, Martina"https://www.zbmath.org/authors/?q=ai:dankova.martinaSummary: We sketch a simple theory of fuzzy partial sets, i.e., fuzzy sets that can have undefined membership degrees. The theory is developed in the semantic framework of a first-order extension of the recently proposed fuzzy partial propositional logic. We introduce a selection of basic notions of fuzzy partial set theory, discuss their variants, and present a few initial results on the properties of fuzzy partial class operations and relations.
For the entire collection see [Zbl 1385.68004].How to incorporate excluding features in fuzzy relational compositions and what for.https://www.zbmath.org/1455.030682021-03-30T15:24:00+00:00"Cao, Nhung"https://www.zbmath.org/authors/?q=ai:cao.nhung"Štěpnička, Martin"https://www.zbmath.org/authors/?q=ai:stepnicka.martinSummary: The aim of this paper is, first, to recall fuzzy relational compositions (products) and, to introduce an idea, how the so-called excluding features could be incorporated into the theoretical background. Apart from rather natural definitions, we provide readers with a theoretical investigation that provides and answer to a rather natural question, under which conditions, in terms of the underlying algebraic structures, the proposed incorporation of excluding features preserves the same properties as the incorporation in the classical relational compositions. The positive impact of the incorporation on reducing the suspicions provided by the basic ``circlet'' composition without losing the possibly correct suspicion, as in the case of the use of the Bandler-Kohout products, is demonstrated on an example.
For the entire collection see [Zbl 1385.68004].A fix-point characterization of Herbrand equivalence of expressions in data flow frameworks.https://www.zbmath.org/1455.680422021-03-30T15:24:00+00:00"Babu, Jasine"https://www.zbmath.org/authors/?q=ai:babu.jasine"Krishnan, Karunakaran Murali"https://www.zbmath.org/authors/?q=ai:murali-krishnan.karunakaran"Paleri, Vineeth"https://www.zbmath.org/authors/?q=ai:paleri.vineethSummary: Computing Herbrand equivalences of terms in data flow frameworks is well studied in program analysis. While algorithms use iterative fix-point computation on some abstract lattice of expressions relevant to the flow graph, the definition of Herbrand equivalences is based on an equivalence over all program paths formulation, on the (infinite) set of all expressions. The aim of this paper is to develop a lattice theoretic fix-point formulation of Herbrand equivalence on a concrete lattice defined over the set of all terms constructible from variables, constants and operators of a program. This new formulation makes explicit the underlying lattice framework as well as the monotone function involved in computing Herbrand equivalences. We introduce the notion of Herbrand congruence and define an (infinite) concrete lattice of Herbrand congruences. Herbrand equivalence is defined as the maximum fix-point of a composite transfer function defined over an appropriate product lattice of the above concrete lattice. We then re-formulate the traditional meet over all paths definition in our lattice theoretic framework. and prove that the maximum fix-point (MFP) and the meet-over-all-paths (MOP) formulations coincide as expected.
For the entire collection see [Zbl 1422.03002].Unbalanced OWA operators for Atanassov intuitionistic fuzzy sets.https://www.zbmath.org/1455.682082021-03-30T15:24:00+00:00"De Miguel, Laura"https://www.zbmath.org/authors/?q=ai:de-miguel.laura"Barrenechea, Edurne"https://www.zbmath.org/authors/?q=ai:barrenechea.edurne"Pagola, Miguel"https://www.zbmath.org/authors/?q=ai:pagola.miguel"Jurio, Aranzazu"https://www.zbmath.org/authors/?q=ai:jurio.aranzazu"Sanz, Jose"https://www.zbmath.org/authors/?q=ai:sanz.jose-antonio"Elkano, Mikel"https://www.zbmath.org/authors/?q=ai:elkano.mikel"Bustince, Humberto"https://www.zbmath.org/authors/?q=ai:bustince.humbertoSummary: In this work we introduce a new class of OWA operators for Atanassov intuitionistic fuzzy sets which distinguishes between the weights for the membership degree and the weights for the nonmembership degree; we call these operators Unbalanced Atanassov Intuitionistic OWA operators. We also study under which conditions these operators are aggregation functions with respect to the Atanassov intuitionistic admissible linear orders. Finally, we apply these aggregation functions in an illustrative example of a decision making problem.
For the entire collection see [Zbl 1385.68004].Negation of graded beliefs.https://www.zbmath.org/1455.030182021-03-30T15:24:00+00:00"Legastelois, Bénédicte"https://www.zbmath.org/authors/?q=ai:legastelois.benedicte"Lesot, Marie-Jeanne"https://www.zbmath.org/authors/?q=ai:lesot.marie-jeanne"Revaultd'allonnes, Adrien"https://www.zbmath.org/authors/?q=ai:revaultdallonnes.adrienSummary: Negation is a key element in the construction of logical systems and plays a central role in reasoning and information manipulation tools. This paper considers the issue of negating graded beliefs, in the framework of a graded doxastic logic. It studies three interpretations of negation for these high level pieces of information, where negation is transferred to the three components of graded beliefs: the formula about which a belief is expressed, the belief modality and the belief level. The paper discusses the choice of appropriate formal frameworks for each of them, considering modal, fuzzy and many-valued logics; it characterises their use and underlines their relations, in particular regarding their effects on the belief degrees.
For the entire collection see [Zbl 1385.68004].A calculus for rational Łukasiewicz logic and related systems.https://www.zbmath.org/1455.030262021-03-30T15:24:00+00:00"Baldi, Paolo"https://www.zbmath.org/authors/?q=ai:baldi.paolo.1|baldi.paoloSummary: We introduce hypersequent calculi for Rational Łukasiewicz logic and for the logic \(\mathrm{KZ}(\pi)\), an extension of Kleene-Zadeh logic, motivated by game semantic investigations.
For the entire collection see [Zbl 1385.68004].Possibilistic semantics for a modal KD45 extension of Gödel fuzzy logic.https://www.zbmath.org/1455.030272021-03-30T15:24:00+00:00"Bou, Félix"https://www.zbmath.org/authors/?q=ai:bou.felix"Esteva, Francesc"https://www.zbmath.org/authors/?q=ai:esteva.francesc"Godo, Lluís"https://www.zbmath.org/authors/?q=ai:godo.lluis"Rodriguez, Ricardo Oscar"https://www.zbmath.org/authors/?q=ai:rodriguez.ricardo-oscarSummary: In this paper we provide a simplified semantics for the logic KD45(\textbf{G}), i.e. the many-valued Gödel counterpart of the classical modal logic KD45. More precisely, we characterize KD45(\textbf{G}) as the set of valid formulae of the class of possibilistic Gödel Kripke Frames \(\langle W,\pi\rangle\), where \(W\) is a non-empty set of worlds and \(\pi:W\rightarrow[0,1]\) is a normalized possibility distribution on \(W\).
For the entire collection see [Zbl 1385.68004].Łukasiewicz public announcement logic.https://www.zbmath.org/1455.030172021-03-30T15:24:00+00:00"Cabrer, Leonardo"https://www.zbmath.org/authors/?q=ai:cabrer.leonardo-manuel"Rivieccio, Umberto"https://www.zbmath.org/authors/?q=ai:rivieccio.umberto"Rodriguez, Ricardo Oscar"https://www.zbmath.org/authors/?q=ai:rodriguez.ricardo-oscarSummary: In this work we lay a theoretical framework for developing dynamic epistemic logics in a many-valued setting. We consider in particular the logic of Public Announcements, which is one of the simplest and best-known dynamic epistemic systems in the literature. We show how to develop a Public Announcement Logic based on finite-valued Łukasiewicz modal logic. We define our logic through a relational semantics based on many-valued Kripke models, and also introduce an alternative but equivalent algebra-based semantics using MV-algebras endowed with modal operators. We provide a Hilbert-style calculus for our logic and prove completeness with respect to both semantics.
For the entire collection see [Zbl 1385.68004].From Kripke to neighborhood semantics for modal fuzzy logics.https://www.zbmath.org/1455.030282021-03-30T15:24:00+00:00"Cintula, Petr"https://www.zbmath.org/authors/?q=ai:cintula.petr"Noguera, Carles"https://www.zbmath.org/authors/?q=ai:noguera.carles"Rogger, Jonas"https://www.zbmath.org/authors/?q=ai:rogger.jonasSummary: The majority of works on modal fuzzy logics consider Kripke-style possible worlds semantics as the principal semantics despite its well known axiomatizability issues when considering fuzzy accessibility relations. The present work offers the first (two) steps towards exploring a more general semantical picture, namely a fuzzified version of the classical neighborhood semantics. First we prove the fuzzy version of the classical relationship between Kripke and neighborhood semantics. Second, for any axiomatic extension of MTL (one of the main fuzzy logics), we define its modal expansion by a \(\Box\)-like modality, and, in the presence of some additional conditions, we prove that the resulting logic can be axiomatized by adding the (E)-rule to the corresponding Hilbert-style calculus of the starting logic.
For the entire collection see [Zbl 1385.68004].The syntax of many-valued relations.https://www.zbmath.org/1455.681952021-03-30T15:24:00+00:00"Eklund, Patrik"https://www.zbmath.org/authors/?q=ai:eklund.patrik-eSummary: In this paper we show how many-valued relations syntactically can be formulated using powertype constructors. This in turn enables to describe the syntax of generalized relations in the starting point sense where the category sets and relations is isomorphic to the Kleisli category of the powerset monad over the category of sets. We can then generalize to work over monoidal closed categories, and thereby description logic, formal concepts and rough sets can be viewed as depending on that powertype constructor, and within a setting of many-valued \(\lambda\)-calculus. In order to achieve this, we will adopt a three-level arrangement of signatures
[the author et al., Fuzzy Sets Syst. 256, 211--235 (2014; Zbl 1334.03022)],
and demonstrate the benefits of using it. Bivalent and untyped relational adaptations typically appear in terminology and ontology, and we will illuminate this situation concerning classifications in health. Extensions to multivalent and typed nomenclatures provides an enrichment that is beneficial in practical use of health classifications and nomenclatures.
For the entire collection see [Zbl 1385.68004].On a category of extensional fuzzy rough approximation \(L\)-valued spaces.https://www.zbmath.org/1455.030692021-03-30T15:24:00+00:00"Eļkins, Aleksandrs"https://www.zbmath.org/authors/?q=ai:elkins.aleksandrs"Šostak, Alexander"https://www.zbmath.org/authors/?q=ai:sostak.alexander-p"Uļjane, Ingrīda"https://www.zbmath.org/authors/?q=ai:uljane.ingridaSummary: We establish extensionality of some upper and lower fuzzy rough approximation operators on an \(L\)-valued set. Taking as the ground basic properties of these operators, we introduce the concept of an (extensional) fuzzy rough approximation \(L\)-valued space. We apply fuzzy functions satisfying certain continuity-type conditions, as morphisms between such spaces, and in the result obtain a category \(\mathcal{FRA}{} \mathbf{SPA}(L)\) of fuzzy rough approximation \(L\)-valued spaces. An interpretation of fuzzy rough approximation \(L\)-valued spaces as \(L\)-fuzzy (di)topological spaces is presented and applied for constructing examples in category \(\mathcal{FRA}{} \mathbf{SPA}(L)\).
For the entire collection see [Zbl 1385.68004].Graded generalized hexagon in fuzzy natural logic.https://www.zbmath.org/1455.030292021-03-30T15:24:00+00:00"Murinová, Petra"https://www.zbmath.org/authors/?q=ai:murinova.petra"Novák, Vilém"https://www.zbmath.org/authors/?q=ai:novak.vilemSummary: In our previous papers, we formally analyzed the generalized Aristotle's square of opposition using tools of fuzzy natural logic. Namely, we introduced general definitions of selected intermediate quantifiers, constructed a generalized square of opposition consisting of them and syntactically analyzed the emerged properties. The main goal of this paper is to extend the generalized square of opposition to graded generalized hexagon.
For the entire collection see [Zbl 1385.68004].A semantical approach to rough sets and dominance-based rough sets.https://www.zbmath.org/1455.682072021-03-30T15:24:00+00:00"D'eer, Lynn"https://www.zbmath.org/authors/?q=ai:deer.lynn"Cornelis, Chris"https://www.zbmath.org/authors/?q=ai:cornelis.chris"Yao, Yiyu"https://www.zbmath.org/authors/?q=ai:yao.yiyuSummary: There exist two formulations of rough sets: the conceptual and computational one. The conceptual or semantical approach of rough set theory focuses on the meaning and interpretation of concepts, while algorithms to compute those concepts are studied in the computational formulation. However, the research on the former is rather limited. In this paper, we focus on a semantically sound approach of Pawlak's rough set model and covering-based rough set models. Furthermore, we illustrate that the dominance-based rough set model can be rephrased using this semantic approach.
For the entire collection see [Zbl 1385.68004].(Ir)relevant t-norm joint distributions in the arithmetic of fuzzy quantities.https://www.zbmath.org/1455.682142021-03-30T15:24:00+00:00"Sgarro, Andrea"https://www.zbmath.org/authors/?q=ai:sgarro.andrea"Franzoi, Laura"https://www.zbmath.org/authors/?q=ai:franzoi.lauraSummary: Irrelevance, a notion put forward in
[the authors, Math. Pannonica 25, No. 1, 93--103 (2014; Zbl 1424.94110); ``Fuzzy arithmetic for fuzzy \(n\)-poles? When is interactivity irrelevant?'', Commun. Comput. Inf. Sci. 299, 1--8 (2012; \url{doi:10.1007/978-3-642-31718-7_1})],
is a convenient tool to speed up computations in the arithmetic of interactive fuzzy numbers, which were first put forward in the seminal paper
[\textit{D. Dubois} and \textit{H. Prade}, ``Additions of interactive fuzzy numbers'', IEEE Trans. Autom. Control 26, 926--936 (1981; Zbl 07327054)].
To make our point, below we deal with standard and less standard binary operations for fuzzy quantities whose interactivity is described by a t-norm joint distribution function.
For the entire collection see [Zbl 1385.68004].Mathematics of multisets: a unified approach.https://www.zbmath.org/1455.030722021-03-30T15:24:00+00:00"Singh, D."https://www.zbmath.org/authors/?q=ai:singh.dasharath"Isah, A. I."https://www.zbmath.org/authors/?q=ai:isah.ahmed-ibrahimSummary: In this paper, a modified and extended version of the extant theory of multisets is presented by developing and applying the concept of \textit{sorts}. It is justified that it is a unified approach. Some metric spaces of multisets and their properties were also described.Projection operators in the Weihrauch lattice.https://www.zbmath.org/1455.030572021-03-30T15:24:00+00:00"Gherardi, Guido"https://www.zbmath.org/authors/?q=ai:gherardi.guido"Marcone, Alberto"https://www.zbmath.org/authors/?q=ai:marcone.alberto"Pauly, Arno"https://www.zbmath.org/authors/?q=ai:pauly.arno-mSummary: In this paper we study, for \( n \geqslant 1\), the projection operators over \( \mathbb{R}^n \), that is the multi-valued functions that associate to \(x \in \mathbb{R}^n \) and \( A \subseteq \mathbb{R}^n\) closed, the points of \(A\) which are closest to \(x\). We also deal with approximate projections, where we content ourselves with points of \(A\) which are almost the closest to \(x\). We use the tools of Weihrauch reducibility to classify these operators dependingon the representation of \(A\) and the dimension \(n\). It turns out that, depending on the representation of the closed sets and the dimension of the space, the projection and approximate projection operators characterize some of the most fundamental computational classes in the Weihrauch lattice.Nonreduction of relations in the Gromov space to Polish actions.https://www.zbmath.org/1455.030612021-03-30T15:24:00+00:00"López, Jesús A. Álvarez"https://www.zbmath.org/authors/?q=ai:alvarez-lopez.jesus-a"Candel, Alberto"https://www.zbmath.org/authors/?q=ai:candel.albertoSummary: We show that in the Gromov space of isometry classes of pointed proper metric spaces, the equivalence relations defined by existence of coarse quasi-isometries or being at finite Gromov-Hausdorff distance cannot be reduced to the equivalence relation defined by any Polish action.Blurring: an approach to conflation.https://www.zbmath.org/1455.030372021-03-30T15:24:00+00:00"Ripley, David"https://www.zbmath.org/authors/?q=ai:ripley.davidSummary: I consider the phenomenon of conflation--treating distinct things as one--and develop logical tools for modeling it. These tools involve a purely consequence-theoretic treatment, independent of any proof or model theory, as well as a four-valued valuational treatment.On superstable expansions of free abelian groups.https://www.zbmath.org/1455.030422021-03-30T15:24:00+00:00"Palacín, Daniel"https://www.zbmath.org/authors/?q=ai:palacin.daniel"Sklinos, Rizos"https://www.zbmath.org/authors/?q=ai:sklinos.rizosSummary: We prove that \((\mathbb{Z},+,0)\) has no proper superstable expansions of finite Lascar rank. Nevertheless, this structure equipped with a predicate defining powers of a given natural number is superstable of Lascar rank \(\omega\). Additionally, our methods yield other superstable expansions such as \((\mathbb{Z},+,0)\) equipped with the set of factorial elements.Algorithmic information theory and its statistical mechanical interpretation.https://www.zbmath.org/1455.680762021-03-30T15:24:00+00:00"Tadaki, Kohtaro"https://www.zbmath.org/authors/?q=ai:tadaki.kohtaroThe paper reviews similarities between statistical mechanics and algorithmic information theory (AIT). It includes a presentation of some elements of AIT, formulations in AIT terms of the partition function, free energy, energy and statistical mechanical entropy. A discussion of the interpretation of temperature as partial randomness is given. No new results in either statistical mechanics or in AIT are proved.
Reviewer: Cristian S. Calude (Auckland)The FAN principle and weak König's lemma in Herbrandized second-order arithmetic.https://www.zbmath.org/1455.030772021-03-30T15:24:00+00:00"Ferreira, Fernando"https://www.zbmath.org/authors/?q=ai:ferreira.fernando-fagundes|ferreira.fernando-m-l|ferreira.fernando-j-t-e|ferreira.fernando|ferreira.fernando-l-sThe work developed in this paper can be seen as an extension of the star calculus from [\textit{F. Ferreira} and \textit{ G. Ferreira}, Arch. Math. Logic 56, No. 5--6, 523--539 (2017; Zbl 1417.03290)] to Heyting arithmetic. The star calculus is a typed combinatory calculus with a type constructor that, to each type \(\tau\), associates the star type \(\tau^*\) corresponding to the nonempty finite subsets of elements of type \(\tau\). The Herbrandization relies on the fact that formulas are considered in a \textit{bounded mixed language} that includes bounded arithmetical quantifiers and bounded structural quantifications of the form \(\forall x^{\tau} \in t^{\tau^*}\,(\dots)\) or of the form \(\exists x^{\tau} \in t^{\tau^*}\,(\dots)\), where \(x\) is a variable of type \(\tau\) and \(t\) is a term of the star type \(\tau^*\).
The present paper introduces a sound functional interpretation of a first-order extension of Heyting arithmetic. This functional interpretation is able to interpret certain principles such as Markov's principle, the bounded independence of the premises principle, the lesser limited principle of omniscience, and the principle of bounded contra-collection, and is therefore considered ``semi-intuitionistic''. The interpretation is indeed ``Herbrandized'' since the witnesses need not to be exact but only contained in a finite set. The interpretation also allows for an extension to second-order arithmetic, interpreting second-order variables as finite sets of natural numbers, which includes a (classically false) formulation of the FAN principle and weak König's lemma.
Herbrandized interpretations were first given in the context of nonstandard arithmetic [\textit{B. van den Berg} et al., Ann. Pure Appl. Logic 163, No. 12, 1962--1994 (2012; Zbl 1270.03121)], which also allows for a treatment of weak König's lemma [\textit{B. Dinis} and \textit{F. Ferreira}, Math. Log. Q. 63, No. 1--2, 114--123 (2017; Zbl 07194869)]. However, according to the author ``It is a quirk of the history of the subject that Herbrandization was first discovered in the nonstandard setting!''. Moreover, the approach using the start calculus is more structural in the sense that it can be used even in theories that are not theories of arithmetic.
Reviewer: Bruno Dinis (Lisboa)Differentiability of continuous functions in terms of Haar-smallness.https://www.zbmath.org/1455.260022021-03-30T15:24:00+00:00"Kwela, Adam"https://www.zbmath.org/authors/?q=ai:kwela.adam"Wołoszyn, Wojciech Aleksander"https://www.zbmath.org/authors/?q=ai:woloszyn.wojciech-aleksanderThe authors give the following description of the present investigations:
``We prove that the set of somewhere differentiable functions (i.e., functions which are differentiable at some point) is not Haar-countable.
We consider functions differentiable on a set of positive Lebesgue's measure and functions differentiable almost everywhere with respect to Lebesgue's measure. Furthermore, we study multidimensional case, i.e., differentiability of continuous functions defined on \([0, 1]^k\). Finally, we pose an open question concerning Takagi's function.''
A brief survey is devoted to Takagi's function, to the notion of Haar-null sets, and to somewhere differentiable functions. The special attention is given to the notions of Haar-countable, Haar-finite, and Haar-\(n\) sets. Also, the notion of Haar-meager sets is briefly considered.
One can note that the special attention also is given to sets of nowhere differentiable functions on \([0, 1]^k\) (i.e., nowhere differentiable functions on \([0, 1]^k\) are ``functions defined on \([0, 1]^k\) which do not have a finite directional derivative at any point along any vector'').
The main results are proven with explanations, the main notions are given with brief surveys. Some open questions related with topics of this research, are noted.
Reviewer: Symon Serbenyuk (Kyïv)Weaker variants of infinite time Turing machines.https://www.zbmath.org/1455.030492021-03-30T15:24:00+00:00"Bianchetti, Matteo"https://www.zbmath.org/authors/?q=ai:bianchetti.matteoThe paper is devoted to infinite time Turing machines (for short: ITTM). ITTM are Turing machines that can halt and provide a result after infinitely many steps. They are far more powerful than ordinary Turing machines. They were introduced by \textit{J. D. Hamkins} and \textit{A. Lewis} [J. Symb. Log. 65, No. 2, 567--604 (2000; Zbl 0963.03064)], In the paper under review, models of infinitary computation whose computational power lies strictly between that of Turing machines and ITTMs are investigated. Four types of weak infinite time Turing machines are defined and some results about their computational power are proved. Special attention is paid to so called weak infinite time Turing machines (wITTM). They are defined by replacing in tye definitione of ITTM the lim sup rule with an `eventually constant' rule: at each limit step, the value of each cell isdefined if and only if the content of that cell has stabilized before that limit step and is then equal to this constant value. The author studies different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. It is shown that some of these models are equivalent to each other concerning their computational strength and that wITTMs decide exactly the arithmetic relations on natural numbers.
Reviewer: Roman Murawski (Poznań)Normality, non-contamination and logical depth in classical natural deduction.https://www.zbmath.org/1455.030132021-03-30T15:24:00+00:00"D'Agostino, Marcello"https://www.zbmath.org/authors/?q=ai:dagostino.marcello"Gabbay, Dov"https://www.zbmath.org/authors/?q=ai:gabbay.dov-m"Modgil, Sanjay"https://www.zbmath.org/authors/?q=ai:modgil.sanjayFor classical logic, with its duality between conjunction and disjunction mediated by negation, as also between the universal and existential quantifiers, one would hope to have corresponding symmetries in whatever recursive apparatus is used to generate the logic. Such symmetry is not only aesthetically pleasing, but also offers prospects of more elegant formulation and proof, and more efficient techniques of automated theorem-proving.
Symmetry in the generative process comes easily for truth-trees, but for Frege-style axiomatizations it appears to be impossible, while for natural deduction and single-conclusion consecution systems it faces difficulties. In the latter context, Gentzen obtained symmetries in the rules by allowing multi-conclusion consecutions. In the former context, however, that move is unattractive as it deviates far from the way human reasoning takes place. For this reason, accounts of natural deduction have hitherto tolerated imperfect symmetry in the rules employed, specifically for contrarian connectives (those that come out false when all components are true; every functionally complete set of primitive connectives must contain at least one of them, usually chosen to be negation or falsum).
Since 1978 there has been a marginal tradition in the philosophical literature of formulating systems of natural deduction that use signed formulae, that is, formulae labelled (say, with 1 or 0) for assertion and rejection. This has generally been done from an inferentialist perspective, according to which propositional connectives should, as a matter of principle, be defined in terms of the intelim rules that they satisfy rather than in terms of their truth conditions. The paper under review takes up the idea of using signed formulae in natural deduction, but without the inferentialist agenda, and gives it a sustained formal elaboration in the context of propositional logic with an eye on computational benefits.
Unlike both the usual unsigned systems as well as previous signed ones, the natural deduction system presented in this paper has the feature that only one of its rules involves discharge of an assumption. That rule, which may be seen as structural rather than intelim, tells us that if we have successfully proven \(v: B \) from each of \(1: A\) and \(0: A\) considered separately (where \(v\) can be \(0\) or \(1\)) then we are entitled to conclude \(v: B\) from whatever other signed hypotheses were used in those two proofs. This parsimony of discharge allows the authors to establish normal form theorems that are unavailable for natural deduction systems in the style of Gentzen and Prawitz. Final sections give an alternative presentation in terms of truth-trees, and show that a notion of the depth of a derivation in normal form provides a hierarchy of computationally tractable approximations to classical propositional logic.
Reviewer: David Makinson (London)Geometric characterization of preduals of injective Banach lattices.https://www.zbmath.org/1455.460222021-03-30T15:24:00+00:00"Kusraev, A. G."https://www.zbmath.org/authors/?q=ai:kusraev.anatolii-georievich|kusraev.anatoly-georgievich"Kutatelatze, S. S."https://www.zbmath.org/authors/?q=ai:kutateladze.semen-sThe paper under review is concerned with preduals of injective Banach lattices, considered in the category of Banach lattices with positive operators. In other words, a Banach lattice \(X\) is injective if, for every Banach lattice \(Y\), every sublattice \(Z\subset Y\) and every positive linear operator \(T:Z\rightarrow X\), there is a positive linear operator \(\tilde T:Y\rightarrow X\) such that the restriction to \(Z\) satsifies \(\tilde T|_Z=T\) and \(\|\tilde T\|=\|T\|\). The study of this class of Banach lattices dates back to the 1970s due to deep works by H. P. Lotz, D. I. Cartwright, R. Haydon, J. Lindenstrauss and L. Tzafriri.
In this paper, the authors provide several characterizations for the dual of a given Banach space to be an injective Banach lattice. Their approach is based on earlier work by the authors on Boolean valued analysis. The reader is referred to this interesting paper for details.
Reviewer: Pedro Tradacete (Madrid)Mathematics and its logics. Philosophical essays.https://www.zbmath.org/1455.030022021-03-30T15:24:00+00:00"Hellman, Geoffrey"https://www.zbmath.org/authors/?q=ai:hellman.geoffreyPublisher's description: In these essays Geoffrey Hellman presents a strong case for a healthy pluralism in mathematics and its logics, supporting peaceful coexistence despite what appear to be contradictions between different systems, and positing different frameworks serving different legitimate purposes. The essays refine and extend Hellman's modal-structuralist account of mathematics, developing a height-potentialist view of higher set theory which recognizes indefinite extendability of models and stages at which sets occur. In the first of three new essays written for this volume, Hellman shows how extendability can be deployed to derive the axiom of Infinity and that of Replacement, improving on earlier accounts; he also shows how extendability leads to attractive, novel resolutions of the set-theoretic paradoxes. Other essays explore advantages and limitations of restrictive systems -- nominalist, predicativist, and constructivist. Also included are two essays, with Solomon Feferman, on predicative foundations of arithmetic.Epsilon substitution for \(ID_1\) via cut-elimination.https://www.zbmath.org/1455.030752021-03-30T15:24:00+00:00"Towsner, Henry"https://www.zbmath.org/authors/?q=ai:towsner.henrySummary: The \(\epsilon \)-substitution method is a technique for giving consistency proofs for theories of arithmetic. We use this technique to give a proof of the consistency of the impredicative theory \({ID}_1\) using a variant of the cut-elimination formalism introduced by Mints.A note on Priest's mereology.https://www.zbmath.org/1455.030042021-03-30T15:24:00+00:00"Cotnoir, Aaron J."https://www.zbmath.org/authors/?q=ai:cotnoir.aaron-jSummary: In the last several years, paraconsistent mereology has begun to be developed and applied to a range of philosophical issues, from puzzles about boundaries, to the Meinongian `problem of nothingness', to the metaphysics of unity. Because these formal systems are fresh out of the package, as it were, there will inevitably be some wrinkles that need ironing out. In this note, I'll point out a problem with the system in \textit{G. Priest} [Australas. J. Log. 11, No. 2, 146--158 (2014; Zbl 1330.03022); One, being an investigation into the unity of reality and of its parts, including the singular object which is nothingness. Oxford: Oxford University Press (2014)], and suggest a natural fix.The boxdot conjecture and the generalized McKinsey axiom.https://www.zbmath.org/1455.030202021-03-30T15:24:00+00:00"Steinsvold, Christopher"https://www.zbmath.org/authors/?q=ai:steinsvold.christopherSummary: The boxdot conjecture is shown to hold for a novel class of modal systems. Each system in this class is K plus an instance of a natural generalization of the McKinsey axiom.Non-analytic tableaux for Chellas's conditional logic CK and Lewis's logic of counterfactuals VC.https://www.zbmath.org/1455.030222021-03-30T15:24:00+00:00"Zach, Richard"https://www.zbmath.org/authors/?q=ai:zach.richardSummary: Priest has provided a simple tableau calculus for Chellas's conditional logic
\textbf{CK}. We provide rules which, when added to Priest's system, result in tableau calculi for Chellas's \textbf{CK} and Lewis's \textbf{VC}. Completeness of these tableaux, however, relies on the cut rule.Logically impossible worlds.https://www.zbmath.org/1455.030122021-03-30T15:24:00+00:00"Tanaka, Koji"https://www.zbmath.org/authors/?q=ai:tanaka.kojiSummary: What does it mean for the laws of logic to fail? My task in this paper is to answer this question. I use the resources that Routley/Sylvan developed with his collaborators for the semantics of relevant logics to explain a world where the laws of logic fail. I claim that the non-normal worlds that Routley/Sylvan (with his collaborators) introduced are exactly such worlds. To disambiguate different kinds of impossible worlds, I call such worlds logically impossible worlds. At a logically impossible world, the laws of logic fail. In this paper, I provide a definition of logically impossible worlds. I then show that there is nothing strange about admitting such worlds.Negation as cancellation, connexive logic, and qLPm.https://www.zbmath.org/1455.030332021-03-30T15:24:00+00:00"Wansing, Heinrich"https://www.zbmath.org/authors/?q=ai:wansing.heinrich-theodor"Skurt, Daniel"https://www.zbmath.org/authors/?q=ai:skurt.danielSummary: In this paper, we shall consider the so-called cancellation view of negation and the inferential role of contradictions. We will discuss some of the problematic aspects of negation as cancellation, such as its original presentation by Richard and Valery Routley and its role in motivating connexive logic. Furthermore, we will show that the idea of inferential ineffectiveness of contradictions can be conceptually separated from the cancellation model of negation by developing a system we call \(qLPm\), a combination of Graham Priest's minimally inconsistent logic of paradox with q-entailment (quasi-entailment) as introduced by Grzegorz Malinowski.Bayesian confirmation, connexivism and an unkindness of ravens.https://www.zbmath.org/1455.030092021-03-30T15:24:00+00:00"Ramírez-Cámara, Elisángela"https://www.zbmath.org/authors/?q=ai:ramirez-camara.elisangelaSummary: Bayesian confirmation theories (BCTs) might be the best standing theories of confirmation to date, but they are certainly not paradox-free. Here I recognize that BCTs' appeal mainly comes from the fact that they capture some of our intuitions about confirmation better than those theories that came before them and that the superiority of BCTs is sufficiently justified by those advantages. Instead, I will focus on Sylvan and Nola's claim that it is desirable that our best theory of confirmation be as paradox-free as possible. For this reason, I will show that, as they respond to different interests, the project of the BCTs is not incompatible with Sylvan and Nola's project of a paradox-free confirmation logic. In fact, it will turn out that, provided we are ready to embrace some degree of non-classicality, both projects complement each other nicely.A note on Goddard and Routley's significance logic.https://www.zbmath.org/1455.030112021-03-30T15:24:00+00:00"Szmuc, Damian"https://www.zbmath.org/authors/?q=ai:szmuc.damian-enrique"Omori, Hitoshi"https://www.zbmath.org/authors/?q=ai:omori.hitoshiSummary: The present note revisits the joint work of \textit{L. Goddard} and \textit{R. Routley} [The logic of significance and context. Vol. 1. Edinburgh - London: Scottish Academic Press (1973; Zbl 0302.02004)]
on signi cance logics (namely, logics able to handle nonsigni cant sentences) with the aim of
shedding new light on their understanding by studying them under the lens of recent semantic
developments, such as the plurivalent semantics developed by Graham Priest. These semantics allow sentences to receive one, more than one, or no truth-value at all from a given carrier set.
Since nonsigni cant sentences are taken to be neither true nor false, i.e. truth-value gaps, in
this essay we show that with the aid of plurivalent semantics it is possible to straightforwardly
instantiate Goddard and Routley's understanding of how the connectives should work within
significance logics.Reflections on Routley's ultralogic program.https://www.zbmath.org/1455.030072021-03-30T15:24:00+00:00"Nolan, Daniel"https://www.zbmath.org/authors/?q=ai:nolan.danielSummary: In this paper, I take up three tasks in turn. The first is to set out what Routley thought we should demand of an all-purpose universal logic, and some of his reasons for those demands. The second is to sketch Routley's own response to those demands. The third is to explore
how else we could satisfy some of the theoretical demands Routley identified, if we are not to follow him in endorsing Routleyan ultralogic as a foundational logic. As part of this third project, I articulate what seems to me a preferable way of going to respond to the challenges Routley correctly identifies: and while I doubt what I will have to say would have convinced Routley himself, I will try to show that the approach I prefer has several advantages over Routley's.On the jumps of the degrees below a recursively enumerable degree.https://www.zbmath.org/1455.030522021-03-30T15:24:00+00:00"Belanger, David R."https://www.zbmath.org/authors/?q=ai:belanger.david-r"Shore, Richard A."https://www.zbmath.org/authors/?q=ai:shore.richard-aSummary: We consider the set of jumps below a Turing degree, given by \(\mathrm{JB}(\mathbf{a})=\{\mathbf{x}':\mathbf{x}\leq\mathbf{a}\}\), with a focus on the problem: Which recursively enumerable (r.e.) degrees \(\mathbf{a}\) are uniquely determined by \(\mathrm{JB}(\mathbf{a})\)? Initially, this is motivated as a strategy to solve the rigidity problem for the partial order \(\mathcal{R}\) of r.e. degrees. Namely, we show that if every high\({}_{2}\) r.e. degree \(\mathbf{a}\) is determined by \(\mathsf{JB}(\mathbf{a})\), then \(\mathcal{R}\) cannot have a nontrivial automorphism. We then defeat the strategy -- at least in the form presented -- by constructing pairs \(\mathbf{a}_{0}\), \(\mathbf{a}_{1}\) of distinct r.e. degrees such that \(\mathrm{JB}(\mathbf{a}_{0})=\mathrm{JB}(\mathbf{a}_{1})\) within any possible jump class \(\{\mathbf{x}:\mathbf{x}'=\mathbf{c}\}\). We give some extensions of the construction and suggest ways to salvage the attack on rigidity.Negation-free and contradiction-free proof of the Steiner-Lehmus theorem.https://www.zbmath.org/1455.030762021-03-30T15:24:00+00:00"Pambuccian, Victor"https://www.zbmath.org/authors/?q=ai:pambuccian.victorSummary: By rephrasing quantifier-free axioms as rules of derivation in sequent calculus, we show that the generalized Steiner-Lehmus theorem admits a direct proof in classical logic. This provides a partial answer to a question raised by Sylvester in 1852. We also present some comments on possible intuitionistic approaches.Classifications of computable structures.https://www.zbmath.org/1455.030442021-03-30T15:24:00+00:00"Lange, Karen"https://www.zbmath.org/authors/?q=ai:lange.karen"Miller, Russell"https://www.zbmath.org/authors/?q=ai:miller.russell-g"Steiner, Rebecca M."https://www.zbmath.org/authors/?q=ai:steiner.rebecca-mSummary: Let \(\mathcal{K}\) be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from \(\mathcal{K}\) such that every structure in \(\mathcal{K}\) is isomorphic to exactly one structure on the list. Such a list is called a computable classification of \(\mathcal{K}\), up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a \(\mathbf{0'}\)-oracle, we can obtain similar classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank \(1\), even though these families are both closely allied with computable algebraic fields.Semantic analysis of entailment and relevant implication. I.https://www.zbmath.org/1455.030252021-03-30T15:24:00+00:00"Routley, Richard"https://www.zbmath.org/authors/?q=ai:routley.richard.1Summary: A transcription of Richard Routley's manuscript, ``Semantic analysis of entailment and relevant implication. I''.Two manuscripts, one by Routley, one by Meyer: the origins of the Routley-Meyer semantics for relevance logics.https://www.zbmath.org/1455.030232021-03-30T15:24:00+00:00"Bimbó, Katalin"https://www.zbmath.org/authors/?q=ai:bimbo.katalin"Dunn, Jon Michael"https://www.zbmath.org/authors/?q=ai:dunn.jon-michael"Ferenz, Nicholas"https://www.zbmath.org/authors/?q=ai:ferenz.nicholasSummary: A \textit{ternary relation} is often used nowadays to interpret an implication connective of a logic, a practice that became dominant in the semantics of relevance logics. This paper examines two early manuscripts -- one by Routley, another by Meyer -- in which they were developing set-theoretic semantics for various relevance logics. A standard presentation of a ternary relational semantics for, let us say, the logic of relevant implication \textbf{R} is quite illuminating, yet the invention of this semantics was fraught with false starts. Meyer's manuscript, in which he builds on some ideas from Routley's manuscript, essentially contains a relational semantics for which \textbf{R}\(^{\circ t}\) is \textit{sound} and \textit{complete}.Paraconsistency and its philosophical interpretations.https://www.zbmath.org/1455.030312021-03-30T15:24:00+00:00"Barrio, Eduardo"https://www.zbmath.org/authors/?q=ai:barrio.eduardo-alejandro"Da Ré, Bruno"https://www.zbmath.org/authors/?q=ai:da-re.brunoSummary: Many authors have considered that the notions of \textit{paraconsistency} and \textit{dialetheism} are intrinsically connected, in many cases, to the extent of confusing both phenomena. However, paraconsistency is a formal feature of some logics that consists in invalidating the rule of explosion, whereas dialetheism is a semantical/ontological position consisting in accepting true contradictions. In this paper, we will argue against this connection and show that it is perfectly possible to adopt a paraconsistent logic and reject dialetheism, and, moreover, that there are examples of non-paraconsistent logics that can be interpreted in a dialetheic way.Bi-modal naive set theory.https://www.zbmath.org/1455.030212021-03-30T15:24:00+00:00"Wigglesworth, John"https://www.zbmath.org/authors/?q=ai:wigglesworth.johnSummary: This paper describes a modal conception of sets, according to which sets are `potential' with respect to their members. A modal theory is developed, which invokes a naive comprehension axiom schema, modified by adding `forward looking' and `backward looking' modal operators. We show that this `bi-modal' naive set theory can prove modalized interpretations of several ZFC axioms, including the axiom of infinity. We also show that the theory is consistent by providing an S5 Kripke model. The paper concludes with some discussion of the nature of the modalities involved, drawing comparisons with noneism, the view that there are some non-existent objects.Sylvan's bottle and other problems.https://www.zbmath.org/1455.030082021-03-30T15:24:00+00:00"Proudfoot, Diane"https://www.zbmath.org/authors/?q=ai:proudfoot.dianeSummary: According to Richard Routley, a comprehensive theory of fiction is impossible, since almost anything is in principle imaginable. In my view, Routley is right: for any purported logic of fiction, there will be actual or imaginable fictions that successfully counterexample the logic. Using the example of `impossible' fictions, I test this claim against theories proposed by Routley's Meinongian contemporaries and also by Routley himself (for what he called `esoteric' works of fiction) and his 21st century heirs. I argue that the phenomenon of impossible fictions challenges even today's modal Meinongians.(In some fictions) everything is true.https://www.zbmath.org/1455.030062021-03-30T15:24:00+00:00"Estrada-González, Luis"https://www.zbmath.org/authors/?q=ai:estrada-gonzalez.luisSummary: I defend the idea that there are universal fictions, and that the Routley-Deutsch-Kapsner way of generating them -- namely, with a story including deliberately and explicitly the proposition Everything is true -- is still the best one. I reconstruct Wildman and Folde's Finean criticisms to universal fictions a la Routley-Deutsch-Kapsner based on the idea that the universal quantifier in such fictions may not target the intended range of quantification, that is, all propositions. I show that Wildman and Folde's argument does not succeed, for they fail to show that every universal sentence has to be understood as involving a restricted quantifier.Formal logical language to set requirements for secure code execution.https://www.zbmath.org/1455.680442021-03-30T15:24:00+00:00"Kozachok, A. V."https://www.zbmath.org/authors/?q=ai:kozachok.a-vSummary: Presently, a special attention is paid to the problem of information security when designing and using objects of critical information infrastructure. One of the most common approaches used to secure the information processed on these objects is the creation of an isolated program environment (sandbox). The security of the environment is determined by its invariability. However, the evolutionary development of data processing systems makes it necessary to implement new components and software in this environment on the condition that the security requirements are met. In this case, the most important requirement is trust in a new program code. This paper is devoted to developing a formal logical language to describe functional requirements for program code that allows one to impose further constraints at the stage of static analysis, as well as to control their fulfillment in dynamics.On the negative disjunction property.https://www.zbmath.org/1455.030352021-03-30T15:24:00+00:00"McKay, Craig Graham"https://www.zbmath.org/authors/?q=ai:mckay.craig-grahamSummary: In the field of intermediate logics, the concept of the disjunction property (DP) plays an important part. Lloyd Humberstone has drawn my attention to an analogious principle called the negative disjunction property (NDP) which applies when the disjuncts involved are negated. The author investigates the NDP in the case of intermediate propositional logics.Notes on some ideas in Lloyd Humberstone's \textit{Philosophical applications of modal logic}.https://www.zbmath.org/1455.030192021-03-30T15:24:00+00:00"Kuhn, Steven T."https://www.zbmath.org/authors/?q=ai:kuhn.steven-t"Weatherson, Brian"https://www.zbmath.org/authors/?q=ai:weatherson.brianSummary: \textit{L. Humberstone} [Philosophical applications of modal logic. London: College Publications (2015; Zbl 1364.03002)] presents a number of new ideas in modal logic as well
explication and critique of recent work of many others. In this note we extend some of these ideas and answer some questions that are left open in the book. Numbers without other identification refer to pages in that book.On testing the existence of universal denominators for partial differential and difference equations.https://www.zbmath.org/1455.350532021-03-30T15:24:00+00:00"Paramonov, S. V."https://www.zbmath.org/authors/?q=ai:paramonov.serge-vSummary: We consider the problem of testing the existence of a universal denominator for partial differential or difference equations with polynomial coefficients and prove its algorithmic undecidability. This problem is closely related to finding rational function solutions in that the construction of a universal denominator is a part of the algorithms for finding solutions of such form for ordinary differential and difference equations.Computational processes and incompleteness.https://www.zbmath.org/1455.681152021-03-30T15:24:00+00:00"Sutner, Klaus"https://www.zbmath.org/authors/?q=ai:sutner.klausSummary: We introduce a formal definition of Wolfram's notion of computational process based on cellular automata, a physics-like model of computation. There is a natural classification of these processes into decidable, intermediate and complete. It is shown that in the context of standard finite injury priority arguments one cannot establish the existence of an intermediate computational process.
For the entire collection see [Zbl 1392.68029].A first-order theory of Ulm type.https://www.zbmath.org/1455.030432021-03-30T15:24:00+00:00"Harrison-Trainor, Matthew"https://www.zbmath.org/authors/?q=ai:harrison-trainor.matthewAuthor's abstract: The class of abelian \(p\)-groups are an example of some very interesting phenomena in computable structure theory. We will give an elementary first-order theory \(T_p\) whose models are each bi-interpretable with the disjoint union of an abelian \(p\)-group and a pure set (and so that every abelian \(p\)-group is bi-interpretable with a model of \(T_p\)) using computable infinitary formulas. This answers a question of Knight by giving an example of an elementary first-order theory of ``Ulm type'': Any two models, low for \(\omega_1^{CK}\), and with the same computable infinitary theory, are isomorphic. It also gives a new example of an elementary first-order theory whose isomorphism problem is \(\mathbf{\Sigma}_1^1\)-complete but not Borel complete.
Reviewer: Andrei S. Morozov (Novosibirsk)A general notion of useful information.https://www.zbmath.org/1455.680752021-03-30T15:24:00+00:00"Moser, Philippe"https://www.zbmath.org/authors/?q=ai:moser.philippeSummary: In this paper we introduce a general framework for defining the depth of a sequence with respect to a class of observers. We show that our general framework captures all depth notions introduced in complexity theory so far. We review most such notions, show how they are particular cases of our general depth framework, and review some classical results about the different depth notions.
For the entire collection see [Zbl 1392.68029].Second-order logic of paradox.https://www.zbmath.org/1455.030322021-03-30T15:24:00+00:00"Hazen, Allen P."https://www.zbmath.org/authors/?q=ai:hazen.allen-p"Pelletier, Francis Jeffry"https://www.zbmath.org/authors/?q=ai:pelletier.francis-jeffrySummary: The logic of paradox, \(LP\), is a first-order, three-valued logic that has been advocated by Graham Priest as an appropriate way to represent the possibility of acceptable contradictory statements. Second-order \(LP\) is that logic augmented with quantification over predicates. As with classical second-order logic, there are different ways to give the semantic interpretation of sentences of the logic. The different ways give rise to different logical advantages and disadvantages, and we canvass several of these, concluding that it will be extremely difficult to appeal to second-order \(LP\) for the purposes that its proponents advocate, until some deep, intricate, and hitherto unarticulated metaphysical advances are made.Busy beavers gone wild.https://www.zbmath.org/1455.030792021-03-30T15:24:00+00:00"Lafitte, Grégory"https://www.zbmath.org/authors/?q=ai:lafitte.gregorySummary: We show some incompleteness results à la Chaitin using the busy beaver functions. Then, with the help of ordinal logics, we show how to obtain a theory in which the values of the busy beaver functions can be provably established and use this to reveal a structure on the provability of the values of these functions.
For the entire collection see [Zbl 1392.68029].Some considerations on universality.https://www.zbmath.org/1455.680552021-03-30T15:24:00+00:00"Kudlek, Manfred"https://www.zbmath.org/authors/?q=ai:kudlek.manfredSummary: The paper puts into discussion the concept of universality, in particular for structures not of the power of Turing computability. The question arises if for such structures a universal structure of the same kind exists or not. For that the construction of universal Turing machines and those with some constraints are presented in some detail.
For the entire collection see [Zbl 1392.68029].On the plurality of spaces in Leibniz.https://www.zbmath.org/1455.010072021-03-30T15:24:00+00:00"Debuiche, Valérie"https://www.zbmath.org/authors/?q=ai:debuiche.valerie"Rabouin, David"https://www.zbmath.org/authors/?q=ai:rabouin.davidAuthors' abstract: ``According to a famous Leibnizian dictum, space is nothing but ``an order of situations, or an order according to which situations are disposed''\(^1\). This so-called ``spatial relationism'' is sometimes understood as a form of relativism (space is relative to the possible dispositions of bodies), which seems to entail the possibility of a spatial pluralism (possible worlds with non-equivalent dispositions of bodies might have non-equivalent spatial structures). An overly exclusive focus on the exchange between Leibniz and Clarke, considered to be the locus classicus for understanding Leibniz's views on space, did much to lend credence to such a conception. In addition, in several passages, Leibniz talked of other possible worlds as lacking this or that spatial property. In the exchange with De Volder, for example, he explained that God could have been pleased with a phenomenal world with gaps in it\(^2\). In this description, as in other passages, it seems that we can imagine without contradiction a world with a geometrical structure different from ours. This stance was supported, as we will see, by influential scholars who concluded, without much trouble, that a plurality of spaces was conceivable for Leibniz. Yet this idea runs counter to two other no less famous Leibnizian dicta: first, that geometrical truths are absolutely necessary (one cannot deny them without contradiction); second, that geometry should be considered as the science of space and that we can specify various properties of geometrical space (such as tridimensionality, homogeneity, isotropy or continuity)\(^3\). Combined together, these last two claims tend to prevent any form of pluralism: space is the object of a science which describes its essential properties and these properties are truths which are absolutely necessary. These eternal truths apply to all possible worlds. Our goal in this paper is to confront this tension in Leibniz's description of space.''
Reviewer's remarks: The abstract is ``verbatin'' identical with the first half of the introduction. In order to give the reader an idea of the correspondent second half, we do quote it as shown below.
``One easy way out of the difficulty, which we study in the first section, consists in distinguishing between an ``abstract'' and a ``real'' space. The first would act as a mathematical framework, identical for all possible worlds, whereas the second would be related to the variable occupations of this framework by real bodies (some of them being ``better'' than others). We study the various forms that this widespread strategy has been able to take in the literature and show that it is either incompatible with Leibniz's relationism, or, in the best case scenario, neutral as regards the question of pluralism. Another solution would be to conceive less strictly the absolute character of geometrical truths and to consider whether such truths might be compatible with a plurality of spaces. This entails studying very closely the specific kind of necessity involved in the description of geometrical space. We recall first that Leibniz relied, on several occasions, on architectonic principles to characterize certain geometrical features such as the unicity of geodesics or, later, the parallel postulate. In addition, he sometimes spoke as if God can create certain mathematical entities belonging to a certain world. These two claims, combined with the fact that he was well aware of the possibility of various metrics not only on surfaces but also in three-dimensional space, lead us to conclude that it is possible to reassess the compatibility of spatial pluralism with the principle of the absolute necessity of mathematical truths. We do so in the last section, by putting particular emphasis on the conditional nature of mathematical truths.''
(Footnotes 1--3 do refer to: 1. Leibniz's fifth paper, see [\textit{G. W. Leibniz}, Philosophical papers and letters. 2nd ed. A selection translated and edited, with an introduction by Leroy E. Loemker. Dordrecht: Kluwer Academic Publishers (1989), p. 714], 2. [\textit{G. W. Leibniz}, The Leibniz-de Volder correspondence. With selections from the correspondence between Leibniz and Johann Bernoulli. Translated, edited, and with an introduction by Paul Lodge. Dual Latin-English text (Latin). New Haven, CT: Yale University Press (2013; Zbl 1300.01007)], 3. [\textit{V. De Risi}, Geometry and monadology. Leibniz's analysis situs and philosophy of space. Basel: Birkhäuser (2007; Zbl 1180.51002)].)
The paper discusses Leibniz's conceivement of ``space'' and notable articles of others about that subject. See the list of references. We do refrain here in typing to give an exposée of the details of the paper. Instead, one should read it.
For the entire collection see [Zbl 1432.01007].
Reviewer: Robert W. van der Waall (Amsterdam)Uncountable trees and Cohen \(\kappa\)-reals.https://www.zbmath.org/1455.030642021-03-30T15:24:00+00:00"Laguzzi, Giorgio"https://www.zbmath.org/authors/?q=ai:laguzzi.giorgioThe author investigates various versions of amoeba forcing and the effects of adding uncountable generic trees over models of ZFC. This is connected with crucial applications concerning cardinal invariants associated with tree-ideals and regularity properties. In the case of \(\omega\), usually one has not pure decision. The situation is completely different for uncountable \(\kappa\) (where \(\kappa\) is regular, and \(\kappa^{<\kappa} = \kappa\)). Here, complete decision gets very often lost.
The author presents some results about regularity properties for tree-forcings at \(\kappa\). He gives \(\boldsymbol{\Sigma}_1^1\)-counterexamples for Mathias and Laver measurability and presents some results concerning generalizations of Ramsey property and the property of Baire.
He solves some questions raised by \textit{S. D. Friedman} et al. [Ann. Pure Appl. Logic 167, No. 4, 408--430 (2016; Zbl 1422.03098)].
Reviewer: Martin Weese (Potsdam)Small Turing universal signal machines.https://www.zbmath.org/1455.680542021-03-30T15:24:00+00:00"Durand-Lose, Jérôme"https://www.zbmath.org/authors/?q=ai:durand-lose.jerome-oSummary: This article aims at providing signal machines as small as possible able to perform any computation (in the classical understanding). After presenting signal machines, it is shown how to get universal ones from Turing machines, cellular-automata and cyclic tag systems. Finally a halting universal signal machine with 13 meta-signals and 21 collision rules is presented.
For the entire collection see [Zbl 1392.68029].On the boundaries of solvability and unsolvability in tag systems. Theoretical and experimental results.https://www.zbmath.org/1455.030482021-03-30T15:24:00+00:00"De Mol, Liesbeth"https://www.zbmath.org/authors/?q=ai:de-mol.liesbethSummary: Several older and more recent results on the boundaries of solvability and unsolvability in tag systems are surveyed. Emphasis will be put on the significance of computer experiments in research on very small tag systems.
For the entire collection see [Zbl 1392.68029].Universally and existentially definable subsets of global fields.https://www.zbmath.org/1455.111672021-03-30T15:24:00+00:00"Eisenträger, Kirsten"https://www.zbmath.org/authors/?q=ai:eisentrager.kirsten"Morrison, Travis"https://www.zbmath.org/authors/?q=ai:morrison.travisThis paper belongs to the area studying definability and decidability in Number Theory. One can arguably call the solution to Hilbert's Tenth Problem by Matiyasevich, building on results of Davis, Putnam and J. Robinson the event that brought the area into being. The solution left open the question whether there was an algorithm for solving diophantine equations over \(\mathbb Q\), and whether there was an existential definition of \(\mathbb Z\) over \(\mathbb Q\) that would imply absence of such an algorithm. Some conjectures by B. Mazur imply that a definition does not exist.
At the same time a definition of \(\mathbb Z\) over \(\mathbb Q\) using both existential and universal quantifiers due to J. Robinson has been known for a long time. More recently, Robinson's definition was simplified in various ways. Poonen produced a first-order definition of algebraic integers over number fields using only two universal quantifiers in the definition. Koenigsmann produced a universal (i.e. using only universal quantifiers) definition of \(\mathbb Z\) over \(\mathbb Q\). He also constructed a definition of \(\mathbb Z\) over \(\mathbb Q\) using only one universal and several existential quantifiers. J. Park generalized the universal definition to number fields, that is she constructed a universal definition of the ring of algebraic integers of a number field \(K\) over \(K\) for all number fields \(K\).
The question posed by Hilbert and related problems of definability make sense over many other rings, such as a global function fields. We know that Hilbert's Tenth problem to be undecidable over all global function fields. R. Rumely constructed the first version of first-order definitions of polynomial rings and rings of \(S\)-integers over global function field. A. Shlapentokh produced an analog of Koenigsmann's one universal quantifier definition for global function fields. The paper under review constructs the analog of the universal definitions of Koenigsmann and Park over these function fields. It also contains other interesting definability results known over number fields. The authors give a Diophantine (existential) definition of non-squares and non-norms.
Many tools used by Park and Koenigsmann to construct their definitions transfer to the global function field setting, but not all. This leads to several technical difficulties successfully handled by the authors. For a student in the area reading side by side the Park paper and the paper under review would make for a very nice introduction to many technical aspects of definability.
Reviewer: Alexandra Shlapentokh (Greenville)Simplicity via provability for universal prefix-free Turing machines.https://www.zbmath.org/1455.030502021-03-30T15:24:00+00:00"Calude, Cristian S."https://www.zbmath.org/authors/?q=ai:calude.cristian-sSummary: Universality is one of the most important ideas in computability theory. There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This criterion is more complex than it may appear at a first glance. In this note we review recent results in Algorithmic Information Theory and propose three new criteria of simplicity for universal prefix-free Turing machines. These criteria refer to the possibility of proving various natural properties of such a machine (its universality, for example) in a formal theory, PA or ZFC. In all cases some, but not all, machines are simple.
For the entire collection see [Zbl 1392.68029].Book review of: M. Wille, Largely unknown. Gottlob Frege und der posthume Ruhm; `alles in den Wind geschrieben'. Gottlob Frege wider den Zeitgeist.https://www.zbmath.org/1455.000102021-03-30T15:24:00+00:00"Klev, Ansten"https://www.zbmath.org/authors/?q=ai:klev.ansten-morchReview of [Zbl 1425.01012; Zbl 1452.03003].Book review of: G. Jäger (ed.) and W. Sieg (ed.), Feferman on foundations. Logic, mathematics, philosophy.https://www.zbmath.org/1455.000092021-03-30T15:24:00+00:00"Kahle, Reinhard"https://www.zbmath.org/authors/?q=ai:kahle.reinhardReview of [Zbl 1394.03005].Book review of: E. H. Reck (ed.) and G. Schiemer (ed.), The prehistory of mathematical structuralism.https://www.zbmath.org/1455.000142021-03-30T15:24:00+00:00"Marquis, Jean-Pierre"https://www.zbmath.org/authors/?q=ai:marquis.jean-pierreReview of [Zbl 1440.03007].Book review of: T. Button and S. Walsh, Philosophy and model theory.https://www.zbmath.org/1455.000062021-03-30T15:24:00+00:00"Halimi, Brice"https://www.zbmath.org/authors/?q=ai:halimi.briceReview of [Zbl 1384.03001].On the uniform computational content of the Baire category theorem.https://www.zbmath.org/1455.030802021-03-30T15:24:00+00:00"Brattka, Vasco"https://www.zbmath.org/authors/?q=ai:brattka.vasco"Hendtlass, Matthew"https://www.zbmath.org/authors/?q=ai:hendtlass.matthew"Kreuzer, Alexander P."https://www.zbmath.org/authors/?q=ai:kreuzer.alexander-pSummary: We study the uniform computational content of different versions of the Baire category theorem in the Weihrauch lattice. The Baire category theorem can be seen as a pigeonhole principle that states that a complete (i.e., ``large'') metric space cannot be decomposed into countably many nowhere dense (i.e., small) pieces. The Baire category theorem is an illuminating example of a theorem that can be used to demonstrate that one classical theorem can have several different computational interpretations. For one, we distinguish two different logical versions of the theorem, where one can be seen as the contrapositive form of the other one. The first version aims to find an uncovered point in the space, given a sequence of nowhere dense closed sets. The second version aims to find the index of a closed set that is somewhere dense, given a sequence of closed sets that cover the space. Even though the two statements behind these versions are equivalent to each other in classical logic, they are not equivalent in intuitionistic logic, and likewise, they exhibit different computational behavior in the Weihrauch lattice. Besides this logical distinction, we also consider different ways in which the sequence of closed sets is ``given.'' Essentially, we can distinguish between positive and negative information on closed sets. We discuss all four resulting versions of the Baire category theorem. Somewhat surprisingly, it turns out that the difference in providing the input information can also be expressed with the jump operation. Finally, we also relate the Baire category theorem to notions of genericity and computably comeager sets.A long pseudo-comparison of premice in \(L[x]\).https://www.zbmath.org/1455.030662021-03-30T15:24:00+00:00"Schlutzenberg, Farmer"https://www.zbmath.org/authors/?q=ai:schlutzenberg.farmerSummary: A significant open problem in inner model theory is the analysis of \(\mathrm{HOD}^{L[x]}\) as a strategy premouse, for a Turing cone of reals \(x\). We describe here an obstacle to such an analysis. Assuming sufficient large cardinals, for a Turing cone of reals \(x\) there are proper class 1-small premice \(M,N\), with Woodin cardinals \(\delta,\varepsilon\), respectively, such that \(M|\delta \text{ and } N|\varepsilon\) are in \(L[x]\), \((\delta^+)^M\) and \((\varepsilon^+)^N\) are countable in \(L[x]\), and the pseudo-comparison of \(M\) with \(N\) succeeds, is in \(L[x]\), and lasts exactly \(\omega_1^{L[x]}\) stages. Moreover, we can take \(M=M_1\), the minimal iterable proper class inner model with a Woodin cardinal, and take \(N\) to be \(M_1\)-like and short-tree-iterable.Refining the taming of the reverse mathematics zoo.https://www.zbmath.org/1455.030152021-03-30T15:24:00+00:00"Sanders, Sam"https://www.zbmath.org/authors/?q=ai:sanders.samSummary: \textit{Reverse mathematics} is a program in the foundations of mathematics. It provides an elegant classification in which the majority of theorems of ordinary mathematics fall into \textit{only five} categories, based on the ``big five'' logical systems. Recently, a lot of effort has been directed toward finding \textit{exceptional} theorems, that is, those which fall \textit{outside} the big five. The so-called reverse mathematics zoo is a collection of such exceptional theorems (and their relations). It was previously shown that a number of \textit{uniform} versions of the zoo theorems, that is, where a functional computes the objects stated to exist, fall in the third big five category, \textit{arithmetical comprehension}, inside Kohlenbach's higher-order reverse mathematics. In this paper, we extend and refine these previous results. In particular, we establish analogous results for recent additions to the reverse mathematics zoo, thus establishing that the latter disappear at the uniform level. Furthermore, we show that the aforementioned equivalences can be proved using only intuitionistic logic. Perhaps most surprisingly, these \textit{explicit} equivalences are extracted from \textit{nonstandard} equivalences in Nelson's \textit{internal set theory}, and we show that the nonstandard equivalence can be recovered from the explicit ones. Finally, the following zoo theorems are studied in this paper: \(\Pi^0_1\mathsf{G}\) (existence of uniformly \(\Pi^0_1\)-generics), \(\mathsf{FIP}\) (finite intersection principle), \(1\)-\(\mathsf{GEN}\) (existence of 1-generics), \(\mathsf{OPT}\) (omitting partial types principle), \(\mathsf{AMT}\) (atomic model theorem), \(\mathsf{SADS}\) (stable ascending or descending sequence), \(\mathsf{AST}\) (atomic model theorem with subenumerable types), \(\mathsf{NCS}\) (existence of noncomputable sets), and \(\mathsf{KPT}\) (Kleene-Post theorem that there exist Turing incomparable sets).On some mistaken beliefs about core logic and some mistaken core beliefs about logic.https://www.zbmath.org/1455.030142021-03-30T15:24:00+00:00"Tennant, Neil"https://www.zbmath.org/authors/?q=ai:tennant.neil-wSummary: This is in part a reply to a recent work of Vidal-Rosset, which expresses various mistaken beliefs about Core Logic. Rebutting these leads us further to identify, and argue against, some mistaken core beliefs about logic.Enumeration 1-genericity in the local enumeration degrees.https://www.zbmath.org/1455.030542021-03-30T15:24:00+00:00"Badillo, Liliana"https://www.zbmath.org/authors/?q=ai:badillo.liliana"Harris, Charles M."https://www.zbmath.org/authors/?q=ai:harris.charles-m"Soskova, Mariya I."https://www.zbmath.org/authors/?q=ai:soskova.mariya-ivanovaSummary: We discuss a notion of forcing that characterizes enumeration 1-genericity, and we investigate the immunity, lowness, and quasiminimality properties of enumeration 1-generic sets and their degrees. We construct an enumeration operator \(\Delta\) such that, for any \(A\), the set \(\Delta^A\) is enumeration 1-generic and has the same jump complexity as \(A\). We deduce from this and other recent results from the literature that not only does every degree \(a\) bound an enumeration 1-generic degree \(b\) such that \(a'=b'\), but also that, if \(a\) is nonzero, then we can find such \(b\) satisfying \(0_e< b< a\). We conclude by proving the existence of both a nonzero low and a properly \(\Sigma_2^0\) nonsplittable enumeration 1-generic degree, hence proving that the class of 1-generic degrees is properly subsumed by the class of enumeration 1-generic degrees.A propositional theory of truth.https://www.zbmath.org/1455.030102021-03-30T15:24:00+00:00"Stephanou, Yannis"https://www.zbmath.org/authors/?q=ai:stephanou.yannisSummary: The liar and kindred paradoxes show that we can derive contradictions if our language possesses sentences lending themselves to paradox and we reason classically from schema (T) about truth:
\[
\mathbf{S}\text{ is true iff } p,
\]
where the letter \(p\) is to be replaced with a sentence and the letter \(\mathbf{S}\) with a name of that sentence. This article presents a theory of truth that keeps (T) at the expense of classical logic. The theory is couched in a language that possesses paradoxical sentences. It incorporates all the instances of the analogue of (T) for that language and also includes other platitudes about truth. The theory avoids contradiction because its logical framework is an appropriately constructed nonclassical propositional logic. The logic and the theory are different from others that have been proposed for keeping (T), and the methods used in the main proofs are novel.Stable forking and imaginaries.https://www.zbmath.org/1455.030412021-03-30T15:24:00+00:00"Casanovas, Enrique"https://www.zbmath.org/authors/?q=ai:casanovas.enrique"Potier, Joris"https://www.zbmath.org/authors/?q=ai:potier.jorisSummary: We prove that a theory \(T\) has stable forking if and only if \(T^{\mathrm{eq}}\) has stable forking.More automorphism groups of countable, arithmetically saturated models of Peano arithmetic.https://www.zbmath.org/1455.030472021-03-30T15:24:00+00:00"Schmerl, James H."https://www.zbmath.org/authors/?q=ai:schmerl.james-hSummary: There is an infinite set \(\mathscr{T}\) of Turing-equivalent completions of Peano Arithmetic (\(\mathsf{PA}\)) such that whenever \(\mathcal{M}\) and \(\mathcal{N}\) are nonisomorphic countable, arithmetically saturated models of \(\mathsf{PA}\) and \(\mathrm{Th}(\mathcal{M})\), \(\mathrm{Th}(\mathcal{N})\in\mathcal{T}\), then \(\mathrm{Aut}(\mathcal{M})\ncong\mathrm{Aut}(\mathcal{N})\).Book review of: G. Hellman and S. Shapiro, Mathematical structuralism.https://www.zbmath.org/1455.000232021-03-30T15:24:00+00:00"Sereni, Andrea"https://www.zbmath.org/authors/?q=ai:sereni.andreaReview of [Zbl 1451.03003].