We consider an example of a sentence which according to Hintikka's claim essentially requires for its logical form a Henkin quantifier. We show that if Hintikka is right then recognizing the truth value of the sentence in finite models is an NP-complete problem. We discuss also possible conclusions from this observation.

We prove that the finite-model version of arithmetic with the divisibility relation is undecidable . Additionally we prove FM-representability theorem for this class of finite models. This means that a relation R on natural numbers can be described correctly on each input on almost all finite divisibility models if and only if R is of degree ≤0′. We obtain these results by interpreting addition and multiplication on initial segments of finite models with divisibility only.

The aim of this paper is to give a geometric interpretation of quantifiers in the intutionistic predicate calculus. We obtain it treating formulae withn free variables as functions withn arguments which run over an abstract set whereas the values of functions are open subsets of a suitable topological space.

We provide a computational model of semantic alignment among communicating agents constrained by social and cognitive pressures. We use our model to analyze the effects of social stratification and a local transmission bottleneck on the coordination of meaning in isolated dyads. The analysis suggests that the traditional approach to learning—understood as inferring prescribed meaning from observations—can be viewed as a special case of semantic alignment, manifesting itself in the behaviour of socially imbalanced dyads put under mild pressure of a local (...) transmission bottleneck. Other parametrizations of the model yield different long-term effects, including lack of convergence or convergence on simple meanings only. (shrink)

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.

Krynicki, M. and M. Mostowski, Decidability problems in languages with Henkin quantifiers, Annals of Pure and Applied Logic 58 149–172.We consider the language L with all Henkin quantifiers Hn defined as follows: Hnx1…xny1…yn φ iff f1…fnx1. ..xn φ, ...,fn). We show that the theory of equality in L is undecidable. The proof of this result goes by interpretation of the word problem for semigroups.Henkin quantifiers are strictly related to the function quantifiers Fn defined as follows: Fnx1…xny1…yn φ iff fx1…xn (...) φ,...,f). In contrast with the first result we show that the theory of equality with all quantifiers Fn is decidable.We also consider decidability problems for other theories in languages L and L. (shrink)

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. Firstly, we show that so–called Barwise's test of negation normality works properly only when assuming our main thesis. Secondly, 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 which are the most difficult in this class (NPTIME–complete). (shrink)

The famous theory of undecidable sentences created by Kurt Godel in 1931 is presented as clearly and as rigorously as possible. Introductory explanations beginning with the necessary facts of arithmetic of integers and progressing to the theory of representability of arithmetical functions and relations in the system (S) prepare the reader for the systematic exposition of the theory of Godel which is taken up in the final chapter and the appendix.

The paper gives a survey of known results related to computational devices (finite and push–down automata) recognizing monadic generalized quantifiers in finite models. Some of these results are simple reinterpretations of descriptive—feasible correspondence theorems from finite–model theory. Additionally a new result characterizing monadic quantifiers recognized by push down automata is proven.

ABSTRACT This paper gives a survey of known results related to computational devices recognising monadic generalised quantifiers infinite models. Some of these results are simple reinterpretations of descriptive-feasible correspondence theorems from finite-model theory. Additionally a new result characterizing monadic quantifiers recognized by push down automata is proven.