Search

We introduce a restricted second-order logic |$\textrm{SO}^{\textit{plog}}$| for finite structures where second-order quantification ranges over relations of size at most poly-logarithmic in the size of the structure. We demonstrate the relevance of this logic and complexity class by several problems in database theory. We then prove a Fagin's style theorem showing that the Boolean queries which can be expressed in the existential fragment of |$\textrm{SO}^{\textit{plog}}$| correspond exactly to the class of decision problems that can be computed by a non-deterministic Turing machine with random access to the input in time |$O((\log n)^k)$| for some |$k \ge 0$|⁠ , i.e. to the class of problems computable in non-deterministic poly-logarithmic time. It should be noted that unlike Fagin's theorem which proves that the existential fragment of second-order logic captures NP over arbitrary finite structures, our result only holds over ordered finite structures, since |$\textrm{SO}^{\textit{plog}}$| is too weak as to define a total order of the domain. Nevertheless, |$\textrm{SO}^{\textit{plog}}$| provides natural levels of expressibility within poly-logarithmic space in a way which is closely related to how second-order logic provides natural levels of expressibility within polynomial space. Indeed, we show an exact correspondence between the quantifier prefix classes of |$\textrm{SO}^{\textit{plog}}$| and the levels of the non-deterministic poly-logarithmic time hierarchy, analogous to the correspondence between the quantifier prefix classes of second-order logic and the polynomial-time hierarchy. Our work closely relates to the constant depth quasipolynomial size AND/OR circuits and corresponding restricted second-order logic defined by David A. Mix Barrington in 1992. We explore this relationship in detail. [ABSTRACT FROM AUTHOR]

The property of being true in almost all finite, initial segments of the standard model of arithmetic is ∑20 -complete. Thus, it admits a kind of a truth definition. We define such an arithmetical predicate. Then, we define its modal logic SL and prove a completeness theorem with respect to finite models semantics. The proof that SL is the modal logic of the approximate truth definition for finite arithmetical models is based on an extension of SL by a fixed-point construction. [ABSTRACT FROM AUTHOR]

We consider the notion of everyday language. We claim that everyday language is semantically bounded by the properties expressible in the existential fragment of second-order logic. Two arguments for this thesis are formulated. First, we show that Barwise's so-called test of negation normality works properly only when assuming our main thesis. Second, we discuss the argument from practical computability for finite universes. Everyday language sentences are directly or indirectly verifiable. We show that in both cases they are bounded by second-order existential properties. Moreover, there are known examples of everyday language sentences that are the most difficult in this class (NPTIME-complete). [ABSTRACT FROM AUTHOR]

We consider first order modal logic C firstly defined by Carnap in “Meaning and Necessity” [1]. We prove elimination of nested modalities for this logic, which gives additionally the Skolem-Löwenheim theorem for C. We also evaluate the degree of unsolvability for C, by showing that it is exactly 0′. We compare this logic with the logics of Henkin quantifiers, Σ11 logic, and SO. We also shortly discuss properties of the logic C in finite models. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decid ability results can be transferred from the infinite model into the finite models. On the contrary we show that the σ2-theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the σ2-theory of multiplication and order is decidable in finite models as well as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation. We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication. [ABSTRACT FROM AUTHOR]