Topic overview

math.LO

Map preview

Topic at a glance

1661works

1796authors indexed

preprint2017arXiv

Logic and linear algebra: an introduction

We give an introduction to logic tailored for algebraists, explaining how proofs in linear logic can be viewed as algorithms for constructing morphisms in symmetric closed monoidal categories with additional structure. This is made explicit by showing how to represent proofs in linear logic as linear maps between vector spaces. The interesting part of this vector space semantics is based on the cofree cocommutative coalgebra of Sweedler.

preprint2017arXiv

Operational Meanings of Orders of Observables Defined through Quantum Set Theories with Different Conditionals

In quantum logic there is well-known arbitrariness in choosing a binary operation for conditional. Currently, we have at least three candidates, called the Sasaki conditional, the contrapositive Sasaki conditional, and the relevance conditional. A fundamental problem is to show how the form of the conditional follows from an analysis of operational concepts in quantum theory. Here, we attempt such an analysis through quantum set theory (QST). In this paper, we develop quantum set theory based on quantum logics with those three conditionals, each of which defines different quantum logical truth value assignment. We show that those three models satisfy the transfer principle of the same form to determine the quantum logical truth values of theorems of the ZFC set theory. We also show that the reals in the model and the truth values of their equality are the same for those models. Interestingly, however, the order relation between quantum reals significantly depends on the underlying conditionals. We characterize the operational meanings of those order relations in terms of joint probability obtained by the successive projective measurements of arbitrary two observables. Those charact

preprint2016arXiv

On statistical learning via the lens of compression

This work continues the study of the relationship between sample compression schemes and statistical learning, which has been mostly investigated within the framework of binary classification. The central theme of this work is establishing equivalences between learnability and compressibility, and utilizing these equivalences in the study of statistical learning theory. We begin with the setting of multiclass categorization (zero/one loss). We prove that in this case learnability is equivalent to compression of logarithmic sample size, and that uniform convergence implies compression of constant size. We then consider Vapnik's general learning setting: we show that in order to extend the compressibility-learnability equivalence to this case, it is necessary to consider an approximate variant of compression. Finally, we provide some applications of the compressibility-learnability equivalences: (i) Agnostic-case learnability and realizable-case learnability are equivalent in multiclass categorization problems (in terms of sample complexity). (ii) This equivalence between agnostic-case learnability and realizable-case learnability does not hold for general learning problems: Ther

preprint2017arXiv

$\text{VC}_{\ell}$ -dimension and the jump to the fastest speed of a hereditary $\mathcal{L}$ -property

In this paper we investigate a connection between the growth rates of certain classes of finite structures and a generalization of $\text{VC}$ -dimension called $\text{VC}_{\ell}$ -dimension. Let $\mathcal{L}$ be a finite relational language with maximum arity $r$ . A hereditary $\mathcal{L}$ -property is a class of finite $\mathcal{L}$ -structures closed under isomorphism and substructures. The \emph{speed} of a hereditary $\mathcal{L}$ -property $\mathcal{H}$ is the function which sends $n$ to $|\mathcal{H}_n|$ , where $\mathcal{H}_n$ is the set of elements of $\mathcal{H}$ with universe $\{1,\ldots, n\}$ . It was previously known there exists a gap between the fastest possible speed of a hereditary $\mathcal{L}$ -property and all lower speeds, namely between the speeds $2^{Θ(n^r)}$ and $2^{o(n^r)}$ . We strengthen this gap by showing that for any hereditary $\mathcal{L}$ -property $\mathcal{H}$ , either $|\mathcal{H}_n|=2^{Θ(n^r)}$ or there is $ε>0$ such that for all large enough $n$ , $|\mathcal{H}_n|\leq 2^{n^{r-ε}}$ . This improves what was previously known about this gap when $r\geq 3$ . Further, we show this gap can be characterized in terms of $\text{VC}_{\ell}$ -dimension, therefore draw

preprint2017arXiv

A classification of the cofinal structures of precompacta

We provide a complete classification of the possible cofinal structures of the families of precompact (totally bounded) sets in general metric spaces, and compact sets in general complete metric spaces. Using this classification, we classify the cofinal structure of local bases in the groups $\C(X,\bbR)$ of continuous real-valued functions on complete metric spaces $X$ , with respect to the compact-open topology.

preprint2017arXiv

Relative e-spectra and relative closures for families of theories

We define the notions of relative $e$ -spectra, with respect to $E$ -operators, relative closures, and relative generating sets. We study properties connected with relative $e$ -spectra and relative generating sets.

preprint2017arXiv

Combinations related to classes of finite and countably categorical structures and their theories

We consider and characterize classes of finite and countably categorical structures and their theories preserved under $E$ -operators and $P$ -operators. We describe $e$ -spectra and families of finite cardinalities for structures belonging to closures with respect to $E$ -operators and $P$ -operators.

preprint2017arXiv

On semilattices and lattices for families of theories

We define and study semilattices and lattices for $E$ -closed families of theories. Properties of these semilattices and lattices are investigated. It is shown that lattices for families of theories with least generating sets are distributive.

preprint2016arXiv

Dynamic Logics of Imperfect Information: from Teams and Games to Transitions

We introduce a new semantical formalism for logics of imperfect information, based on Game Logic (and, in particular, on van Benthem, Ghosh and Lu's Concurrent Dynamic Game Logic). This new kind of semantics combines aspects from game theoretic semantics and from team semantics, and demonstrates how logics of imperfect information can be seen as languages for reasoning about games. Finally we show that, for a very expressive fragment of our language, a simpler semantics is available.

preprint2017arXiv

Proof search in multi-succedent sequent calculi for intuitionistic logic under the Schuette's schema

Following G. Mints(Kluwer 2000 and draft 2013), we present terminating and bicomplete proof searches in multi-succedent sequent calculi for intuitionistic propositional logic, fragments of intuitionistic predicate logic and full intuitionistic predicate logic in the spirit of Schuette's schema.

preprint2017arXiv

Products of general Menger spaces

We study products of general topological spaces with Menger's covering property, and its refinements based on filters and semifilters. To this end, we extend the projection method from the classic real line topology to the Michael topology. Among other results, we prove that, assuming \CH{}, every productively Lindelöf space is productively Menger, and every productively Menger space is productively Hurewicz. None of these implications is reversible.

preprint2013arXiv

Cluster expansion and the boxdot conjecture

The boxdot conjecture asserts that every normal modal logic that faithfully interprets T by the well-known boxdot translation is in fact included in T. We confirm that the conjecture is true. More generally, we present a simple semantic condition on modal logics $L_0$ which ensures that the largest logic where $L_0$ embeds faithfully by the boxdot translation is $L_0$ itself. In particular, this natural generalization of the boxdot conjecture holds for S4, S5, and KTB in place of T.

preprint2016arXiv

We belong together? A plea for modesty in modal plural logic

A sceptical examination of the motivations for strong modal plural logics.

preprint2016arXiv

Nonstandard Measure Spaces with Values in non-Archimedean Fields

The aim of this contribution is to bring together the areas of $p$ -adic analysis and nonstandard analysis. We develop a nonstandard measure theory with values in a complete non-Archimedean valued field $K$ , e.g. the $p-$ adic numbers $\mathbb{Q}_p$ . The corresponding theory for real-valued measures is well known by the work of P. A. Loeb, R. M. Anderson and others. We first review some of the standard facts on non-Archimedean measures and briefly sketch the prerequisites from nonstandard analysis. Then internal measures on rings and algebras with values in a nonstandard field ${^*K}$ are introduced. We explain how an internal measure induces a $K$ -valued Loeb measure. The standard-part map between a Loeb space and the underlying standard measure space is measurable almost everywhere. We establish liftings from measurable functions to internal simple functions. Furthermore, we prove that standard measure spaces can be described as push-downs of hyperfinite internal measure spaces. This result is an analogue of a well-known Theorem on hyperfinite representations of Radon spaces. Then standard integrable functions are related to internal $S$ -integrable functions and integrals are repre

preprint2016arXiv

Lattice Logic Properly Displayed

We introduce a proper display calculus for (non-distributive) Lattice Logic which is sound, complete, conservative, and enjoys cut-elimination and sub-formula property. Properness (i.e. closure under uniform substitution of all parametric parts in rules) is the main interest and added value of the present proposal, and allows for the smoothest Belnap-style proof of cut-elimination. Our proposal builds on an algebraic and order-theoretic analysis of the semantic environment of lattice logic, and applies the guidelines of the multi-type methodology in the design of display calculi.

preprint2016arXiv

The "paradox" of computability and a recursive relative version of the Busy Beaver function

In this article, we will show that uncomputability is a relative property not only of oracle Turing machines, but also of subrecursive classes. We will define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function which we will call Busy Beaver Plus function. Therefore, we will prove that the computable Busy Beaver Plus function defined on any Turing submachine is not computable by any program running on this submachine. We will thereby demonstrate the existence of a "paradox" of computability a la Skolem: a function is computable when "seen from the outside" the subsystem, but uncomputable when "seen from within" the same subsystem. Finally, we will raise the possibility of defining universal submachines, and a hierarchy of negative Turing degrees.

preprint2016arXiv

Second order intuitionistic propositional logic of the real line is decidable

It is known that the set of tautologies of second order intuitionistic propositional logic, $\mathrm{IPC} 2$ , is undecidable. Here, we prove that the sets of formulas of $\mathrm{IPC} 2$ which are true in the algebra of open subsets of reals or rationals are decidable.

preprint2016arXiv

Probability functions in the context of signed involutive meadows

The Kolmogorov axioms for probability functions are placed in the context of signed meadows. A completeness theorem is stated and proven for the resulting equational theory of probability calculus. Elementary definitions of probability theory are restated in this framework.

preprint2016arXiv

Varieties of Metric and Quantitative Algebras

Metric algebras are metric variants of $Σ$ -algebras. They are first introduced in the field of universal algebra to deal with algebras equipped with metric structures such as normed vector spaces. Recently a similar notion of quantitative algebra is used in computer science to formulate computational effects of probabilistic programs. In this paper we show that varieties of metric algebras (classes defined by a set of metric equations) are exactly classes closed under (metric versions of) subalgebras, products and quotients. This result implies the class of normed vector spaces cannot be defined by metric equations, differently from the classical case where the class of vector spaces is equational. This phenomenon suggests that metric equations are not a very natural class of formulas since they cannot express such a typical class of metric algebras. Therefore we need a broader class of formulas to acquire an appropriate metric counterpart of the classical variety theory.

preprint2016arXiv

SPM Bulletin 40

This issue surveys some of the activities in the field since the previous issue, and announces a conference fully dedicated to the topic of selection principles.

preprint2016arXiv

One Henkin Quantifier in the empty vocabulary suffices for undecidability

We prove that there are single Henkin quantifiers such that first order logic augmented by one of these quantifiers is undecidable in the empty vocabulary. Examples of such quantifiers are given.

preprint2016arXiv

On a strengthening of Kotlarski's theorem

Kotlarski's theorem (see H. Kotlarski. Bounded Induction and Satisfaction Classes. Mathematical Logic Quarterly, vol. 32, 31-34, 1986, P. 531--544.) formalized in $WKL_0$ .

preprint2016arXiv

Supercritical Space-Width Trade-offs for Resolution

We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben-Sasson '09]}, and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov '16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordstrom '08].

preprint2016arXiv

Downward categoricity from a successor inside a good frame

We use orthogonality calculus to prove a downward transfer from categoricity in a successor in abstract elementary classes (AECs) that have a good frame (a forking-like notion for types of singletons) on an interval of cardinals: $\mathbf{Theorem}$ Let $K$ be an AEC and let $\text{LS} (K) \le λ< θ$ be cardinals. If $K$ has a type-full good $[λ, θ]$ -frame and $K$ is categorical in both $λ$ and $θ^+$ , then $K$ is categorical in all $λ' \in [λ, θ]$ . We deduce improvements on the threshold of several categoricity transfers that do not mention frames. For example, the threshold in Shelah's transfer can be improved from $\beth_{\beth_{\left(2^{\text{LS} (K)}\right)^+}}$ to $\beth_{\left(2^{\text{LS} (K)}\right)^+}$ assuming that the AEC is $\text{LS} (K)$ -tame. The successor hypothesis can also be removed from Shelah's result by assuming in addition either that the AEC has primes over sets of the form $M \cup \{a\}$ or (using an unpublished claim of Shelah) that the weak generalized continuum hypothesis holds.