Local sentences and the formal languages they define were introduced by Ressayre in. We prove that locally finite ω‐languages and effective analytic sets have the same topological complexity: the Borel and Wadge hierarchies of the class of locally finite ω‐languages are equal to the Borel and Wadge hierarchies of the class of effective analytic sets. In particular, for each non‐null recursive ordinal there exist some ‐complete and some ‐complete locally finite ω‐ (...) class='Hi'>languages, and the supremum of the set of Borel ranks of locally finite ω‐languages is the ordinal, which is strictly greater than the first non‐recursive ordinal. This gives an answer to the question of the topological complexity of locally finite ω‐languages, which was asked by Simonnet and also by Duparc, Finkel, and Ressayre in. Moreover we show that the topological complexity of a locally finite ω‐language defined by a local sentence φ may depend on the models of the Zermelo‐Fraenkel axiomatic system. Using similar constructions as in the proof of the above results we also show that the equivalence, the inclusion, and the universality problems for locally finite ω‐languages are ‐complete, hence highly undecidable. (shrink)

Locally finite omega languages were introduced by Ressayre [Formal languages defined by the underlying structure of their words. J Symb Log 53(4):1009–1026, 1988]. These languages are defined by local sentences and extend ω-languages accepted by Büchi automata or defined by monadic second order sentences. We investigate their topological complexity. All locally finite ω-languages are analytic sets, the class LOC ω of locally finite ω-languages meets all finite levels (...) of the Borel hierarchy and there exist some locally finite ω-languages which are Borel sets of infinite rank or even analytic but non-Borel sets. This gives partial answers to questions of Simonnet (Automates et Théorie Descriptive, Ph.D. Thesis. Université Paris 7, March 1992) and of Duparc et al. [Computer science and the fine structure of Borel sets. Theor Comput Sci 257(1–2):85–105, 2001]. (shrink)

We modify the semantics of topological modal logic, a language due to Moss and Parikh. This enables us to study the corresponding theory of further classes of subset spaces. In the paper we deal with spaces where every chain of opens fulfils a certain finiteness condition. We consider both a local finiteness condition relevant to points and a global one concerning the whole frame. Completeness of the appearing logical systems, which turn out to be generalizations of the well-known modal system (...) G, can be obtained in the same manner as in the case of the general subset space logic. It is our main purpose to show that the systems differ with regard to the finite model property. (shrink)

The tangle modality is a propositional connective that extends basic modal logic to a language that is expressively equivalent over certain classes of finite frames to the bisimulation-invariant fragments of both first-order and monadic second-order logic. This paper axiomatises several logics with tangle, including some that have the universal modality, and shows that they have the finite model property for Kripke frame semantics. The logics are specified by a variety of conditions on their validating frames, including local and (...) global connectedness properties. Some of the results have been used to obtain completeness theorems for interpretations of tangled modal logics in topological spaces. (shrink)

We introduce and discuss a concept of approximation of a topological algebraic system A by finite algebraic systems from a given class K. If A is discrete, this concept agrees with the familiar notion of a local embedding of A in a class K of algebraic systems. One characterization of this concept states that A is locally embedded in K iff it is a subsystem of an ultraproduct of systems from K. In this paper we obtain a similar (...) characterization of approximability of a locally compact system A by systems from K using the language of nonstandard analysis. In the signature of A we introduce positive bounded formulas and their approximations; these are similar to those introduced by Henson [14] for Banach space structures (see also [15, 16]). We prove that a positive bounded formula φ holds in A if and only if all precise enough approximations of φ hold in all precise enough approximations of A. We also prove that a locally compact field cannot be approximated arbitrarily closely by finite (associative) rings (even if the rings are allowed to be non-commutative). Finite approximations of the field R can be considered as possible computer systems for real arithmetic. Thus, our results show that there do not exist arbitrarily accurate computer arithmetics for the reals that are associative rings. (shrink)

We study the expansion of stable structures by adding predicates for arbitrary subsets. Generalizing work of Poizat-Bouscaren on the one hand and Baldwin-Benedikt-Casanovas-Ziegler on the other we provide a sufficient condition (Theorem 4.7) for such an expansion to be stable. This generalization weakens the original definitions in two ways: dealing with arbitrary subsets rather than just submodels and removing the 'small' or 'belles paires' hypothesis. We use this generalization to characterize in terms of pairs, the 'triviality' of the geometry on (...) a strongly minimal set (Theorem 2.5). Call a set A benign if any type over A in the expanded language is determined by its restriction to the base language. We characterize the notion of benign as a kind of local homogenity (Theorem 1.7). Answering a question of [8] we characterize the property that M has the finite cover property over A (Theorem 3.9). (shrink)

The paper deals with pp formulas in the language of reduced special groups, and the question of when the validity of a pp formula on each finite subspace of a space of orderings implies its global validity [18]. A large new class of pp formulas is introduced for which this is always the case, assuming the space of orderings in question has finite stability index. The paper also considers pp formulas of the special type $b\in \Pi _{i=1}^{n}\,D\langle 1,a_{i}\rangle (...) $. Formulas of this type with n = 3 are the simplest sort of pp formula not covered by the result, and are also the source of the recent counterexamples in [9] and [19]. (shrink)

We present numerous natural algebraic examples without the so-called Canonical Base Property (CBP). We prove that every commutative unitary ring of finite Morley rank without finite-index proper ideals satisfies the CBP if and only if it is a field, a ring of positive characteristic or a finite direct product of these. In addition, we construct a CM-trivial commutative local ring with a finite residue field without the CBP. Furthermore, we also show that finite-dimensional non-associative algebras (...) over an algebraically closed field of characteristic [Formula: see text] give rise to triangular rings without the CBP. This also applies to Baudisch’s [Formula: see text]-step nilpotent Lie algebras, which yields the existence of a [Formula: see text]-step nilpotent group of finite Morley rank whose theory, in the pure language of groups, is CM-trivial and does not satisfy the CBP. (shrink)

Journal of Mathematical Logic, Ahead of Print. We present numerous natural algebraic examples without the so-called Canonical Base Property (CBP). We prove that every commutative unitary ring of finite Morley rank without finite-index proper ideals satisfies the CBP if and only if it is a field, a ring of positive characteristic or a finite direct product of these. In addition, we construct a CM-trivial commutative local ring with a finite residue field without the CBP. Furthermore, we (...) also show that finite-dimensional non-associative algebras over an algebraically closed field of characteristic [math] give rise to triangular rings without the CBP. This also applies to Baudisch’s [math]-step nilpotent Lie algebras, which yields the existence of a [math]-step nilpotent group of finite Morley rank whose theory, in the pure language of groups, is CM-trivial and does not satisfy the CBP. (shrink)

Results from a crowdsourced audio questionnaire show that inflected infinitives in Galician are still acceptable in a broad range of contexts, different from those described for European Portuguese. Crucially, inflected infinitives with referential subjects are widely accepted only inside strong islands in Galician (complements of nouns, adjunct clauses). They are widely rejected in non-islands, notably in the complements of epistemic/factive verbs, in contrast with Portuguese and older varieties of Galician (Gondar 1978, Raposo 1987). Statistical analysis shows, however, that, in the (...) complements of epistemic/factive (and desiderative) verbs, inflected infinitives are significantly more acceptable in instances of control, whether partial or exhaustive. In fact, there is no significant difference between these two types of control in Galician, unlike in Portuguese, where inflection is generally better in instances of partial control and is not acceptable in instances of exhaustive local subject control (Modesto 2010, Sheehan 2018). We propose an analysis of this pattern in terms of phase theory. The inflectional domain of non-finite clauses remains visible to the thematic domain of the next clause up, according to the less strict version of the Phase Impenetrability Condition (Chomsky 2001), allowing control to take place. Pronouns/or pronominal inflections in the inflectional domain of visible non-finite clauses therefore get controlled. In islands, however, material in the inflectional domain remains free/referential. Despite this basic pattern, the data are characterized by substantial interspeaker variation. Statistical analysis shows that gender, urban/rural birthplace and mother tongue are all significant factors in this variation, while age and region of birth are not. Most notably, urban-born male bilinguals with Spanish as their mother tongue consistently rate the sentences higher on the Likert scale. Overall, the results show that crowdsourcing can lead to empirically robust syntactic descriptions of minority languages which are likely to be subject to substantial sociolinguistic variation and where judgements from a single social group may be misrepresentative of the general picture. The study also highlights, however, the challenges associated with using crowd-sourced audio-questionnaires of this kind in languages of this kind and the need for statistical analysis of results to control for substantial amounts of variation. (shrink)

i) We show for each context-free language L that by considering each word of L as a structure in a natural way, one turns L into a finite union of classes which satisfy a finitary analog of the characteristic properties of complete universal first order classes of structures equipped with elementary embeddings. We show this to hold for a much larger class of languages which we call free local languages. ii) We define local languages, a class (...) of languages between free local and context-sensitive languages. Each local language L has a natural extension L ∞ to infinite words, and we prove a series of "pumping lemmas", analogs for each local language L of the "uvxyz theorem" of context free languages: they relate the existence of large words in L or L ∞ to the existence of infinite "progressions" of words included in L, and they imply the decidability of various questions about L or L ∞ . iii) We show that the pumping lemmas of ii) are independent from strong axioms, ranging from Peano arithmetic to ZF + Mahlo cardinals. We hope that these results are useful for a model-theoretic approach to the theory of formal languages. (shrink)

This paper connects the following four topics: a class of generalized graphs whose relations do not have fixed arities called hypergraphs, a family of non-normal modal logics rejecting the aggregative axiom, an epistemic framework fighting logical omniscience, and the classical group knowledge modality of ‘someone knows’. Through neighborhood frames as their meeting point, we show that, among many completeness results obtained in this paper, the limit of a family of weakly aggregative logics is both exactly the modal logic of hypergraphs (...) and also the epistemic logic of local reasoning with veracity and positive introspection, and upon adding a single combinatorial axiom, it is also the logic of ‘someone knows’ for a fixed finite number of positively introspective agents. At the core of all these completeness results is a new canonical neighborhood model construction for monotone modal logics that is capable of dealing with all these diverse cases. We also provide an axiomatization for the logic of all non-n-colorable hypergraphs based on a filtration argument that also shows the decidability of the logics of hypergraphs we study. (shrink)

We present an axiomatic approach for a class of finite, extensive form games of perfect information that makes use of notions like “rationality at a node” and “knowledge at a node.” We distinguish between the game theorist's and the players' own “theory of the game.” The latter is a theory that is sufficient for each player to infer a certain sequence of moves, whereas the former is intended as a justification of such a sequence of moves. While in general (...) the game theorist's theory of the game is not and need not be axiomatized, the players' theory must be an axiomatic one, since we model players as analogous to automatic theorem provers that play the game by inferring (or computing) a sequence of moves. We provide the players with an axiomatic theory sufficient to infer a solution for the game (in our case, the backwards induction equilibrium), and prove its consistency. We then inquire what happens when the theory of the game is augmented with information that a move outside the inferred solution has occurred. We show that a theory that is sufficient for the players to infer a solution and still remains consistent in the face of deviations must be modular. By this we mean that players have distributed knowledge of it. Finally, we show that whenever the theory of the game is group-knowledge (or common knowledge) among the players (i.e., it is the same at each node), a deviation from the solution gives rise to inconsistencies and therefore forces a revision of the theory at later nodes. On the contrary, whenever a theory of the game is modular, a deviation from equilibrium play does not induce a revision of the theory. (shrink)

Default logic is computationally expensive. One of the most promising ways of easing this problem and developing powerful implementations is to split a default theory into smaller parts and compute extensions in a modular, local way. This paper compares two recent approaches, Turner's splitting and Cholewinski's stratification. It shows that the approaches are closely related – in fact the former can be viewed as a special case of the latter.

In this paper I offer an explanation for the fact that QR tends to be more local than other types of A-bar movement (i.e., in typical cases, QR cannot take place out of a finite clause). My explanation assumes (and offers evidence for) the Phase Impenetrability Condition (cf. Chomsky 2001a, b) and an Economy Condition that requires that each step of (possibly successive cyclic) QR be motivated (cf. Fox 1999). After showing why QR is local in typical cases, I (...) consider new evidence, involving a counterpart of ACD in Italian, which indicates that QR takes place long distance, as other types of A-bar movement do, whenever each step is independently motivated. It follows that it can be maintained that the locality conditions on QR are not construction specific, as expected given the general format of the theory. (shrink)

Journal of Mathematical Logic, Ahead of Print. We initiate the study of a generalization of Kim-independence, Conant-independence, based on the notion of strong Kim-dividing of Kaplan, Ramsey and Shelah. A version of Conant-independence was originally introduced to prove that all [math] theories are [math]. We introduce an axiom on stationary independence relations, essentially generalizing the “freedom” axiom in some of the free amalgamation theories of Conant, and show that this axiom provides the correct setting for carrying out arguments of Chernikov, (...) Kaplan and Ramsey on [math] theories relative to a stationary independence relation. Generalizing Conant’s results on free amalgamation to the limits of our knowledge of the [math] hierarchy, we show using methods from Conant as well as our previous work that any theory where the equivalent conditions of this local variant of [math] holds is either [math] or [math] and is either simple or [math]. We observe that these theories give an interesting class of examples of theories where Conant-independence is symmetric. This includes all of Conant’s examples, the small cycle-free random graphs of Shelah, and the (finite-language) [math]-categorical Hrushovski constructions of Evans and Wong. We then answer Conant’s question on the existence of non-modular free amalgamation theories. We show that the generic functional structures of Kruckman and Ramsey are examples of non-modular free amalgamation theories. We also show that any free amalgamation theory is [math] or [math], while an [math] free amalgamation theory is simple if and only if it is modular. Finally, we show that every theory where Conant-independence is symmetric is [math]. Therefore, symmetry for Conant-independence gives the next known neostability-theoretic dividing line on the [math] hierarchy beyond [math]. We explain the connection to some established open questions. (shrink)

Neural circuits linking local operations in the cortex and the basal ganglia confer reiterative capacities, expressed in seemingly unrelated human traits such as speech, syntax, adaptive actions to changing circumstances, dancing, and music. Reiteration allows the formation of a potentially unbounded number of sentences from a finite set of syntactic processes, obviating the need for the hypothetical.

The variety of Heyting algebras has two well-behaved locally finite reducts, the variety of bounded distributive lattices and the variety of implicative semilattices. The variety of bounded distributive lattices is generated by the →-free reducts of Heyting algebras, while the variety of implicative semilattices is generated by the ∨-free reducts. Each of these reducts gives rise to canonical formulas that generalize Jankov formulas and provide an axiomatization of all superintuitionistic logics. The ∨-free reducts of Heyting algebras give rise (...) to the -canonical formulas that we studied in an earlier work. Here we introduce the -canonical formulas, which are obtained from the study of the →-free reducts of Heyting algebras. We prove that every si-logic is axiomatizable by -canonical formulas. We also discuss the similarities and differences between these two kinds of canonical formulas. One of the main ingredients of these formulas is a designated subset D of pairs of elements of a finite subdirectly irreducible Heyting algebra A. When D=A2, we show that the -canonical formula of A is equivalent to the Jankov formula of A. On the other hand, when D=∅, the -canonical formulas produce a new class of si-logics we term stable si-logics. We prove that there are continuum many stable si-logics and that all stable si-logics have the finite model property. We also compare stable si-logics to splitting and subframe si-logics. (shrink)

The author has previously shown that for a certain class of structures $\mathcal {I}$, $\mathcal {I}$-indexed indiscernible sets have the modeling property just in case the age of $\mathcal {I}$ is a Ramsey class. We expand this known class of structures from ordered structures in a finite relational language to ordered, locally finite structures which isolate quantifier-free types by way of quantifier-free formulas. This result is applied to give new proofs that certain classes of trees are Ramsey. (...) To aid this project we develop the logic of EM-types. (shrink)

In this paper we study a notion of HL-extension for a structure in a finite relational language $\mathcal {L}$. We give a description of all finite minimal HL-extensions of a given finite $\mathcal {L}$ -structure. In addition, we study a group-theoretic property considered by Herwig–Lascar and show that it is closed under taking free products. We also introduce notions of coherent extensions and ultraextensive $\mathcal {L}$ -structures and show that every countable $\mathcal {L}$ -structure can be extended (...) to a countable ultraextensive structure. Finally, it follows from our results that the automorphism group of any countable ultraextensive $\mathcal {L}$ -structure has a dense locally finite subgroup. (shrink)

We give strengthened versions of the Herwig–Lascar and Hodkinson–Otto extension theorems for partial automorphisms of finite structures. Such strengthenings yield several combinatorial and group-theoretic consequences for homogeneous structures. For instance, we establish a coherent form of the extension property for partial automorphisms for certain Fraïssé classes. We deduce from these results that the isometry group of the rational Urysohn space, the automorphism group of the Fraïssé limit of any Fraïssé class that is the class of all ${\cal F}$-free structures, (...) and the automorphism group of any free homogeneous structure over a finite relational language all contain a dense locally finite subgroup. We also show that any free homogeneous structure admits ample generics. (shrink)

Dynamic topological logic combines topological and temporal modalities to express asymptotic properties of dynamic systems on topological spaces. A dynamic topological model is a triple 〈X ,f , V 〉, where X is a topological space, f : X → X a continuous function and V a truth valuation assigning subsets of X to propositional variables. Valid formulas are those that are true in every model, independently of X or f. A natural problem that arises is to identify the logics (...) obtained on familiar spaces, such as . It [9] it was shown that any satisfiable formula could be satisfied in some for n large enough, but the question of how the logic varies with n remained open.In this paper we prove that any fragment of DTL that is complete for locally finite Kripke frames is complete for . This includes DTL○; it also includes some larger fragments, such as DTL1, where “henceforth” may not appear in the scope of a topological operator. We show that satisfiability of any formula of our language in a locally finite Kripke frame implies satisfiability in by constructing continuous, open maps from the plane into arbitrary locally finite Kripke frames, which give us a type of bisimulation. We also show that the results cannot be extended to arbitrary formulas of DTL by exhibiting a formula which is valid in but not in arbitrary topological spaces. (shrink)

We say that a first order theoryTislocally finiteif every finite part ofThas a finite model. It is the purpose of this paper to construct in a uniform way for any consistent theoryTa locally finite theory FIN which is syntactically isomorphic toT.Our construction draws upon the main idea of Paris and Harrington [6] and generalizes the syntactic aspect of their result from arithmetic to arbitrary theories. The first mathematically strong locally finite theory, called FIN, was (...) defined in [1]. Now we get much stronger ones, e.g. FIN.From a physicalistic point of view the theorems of ZF and their FIN-counterparts may have the same meaning. Therefore FIN is a solution of Hilbert's second problem. It eliminates ideal objects from the proofs of properties of concrete objects.In [4] we will demonstrate that one can develop a direct finitistic intuition that FIN is locally finite. We will also prove a variant of Gödel's second incompleteness theorem for the theory FIN and for all its primitively recursively axiomatizable consistent extensions.The results of this paper were announced in [3]. (shrink)

Let \(\textbf{K}\) and \(\textbf{M}\) be locally finite quasivarieties of finite type such that \(\textbf{K}\subset \textbf{M}\). If \(\textbf{K}\) is profinite then the filter \([\textbf{K},\textbf{M}]\) in the quasivariety lattice \(\textrm{Lq}(\textbf{M})\) is an atomic lattice and \(\textbf{K}\) has an independent quasi-equational basis relative to \(\textbf{M}\). Applications of these results for lattices, unary algebras, groups, unary algebras, and distributive algebras are presented which concern some well-known problems on standard topological quasivarieties and other problems.

Suppose T is a weakly minimal theory and p a strong 1-type having locally finite but nontrivial geometry. That is, for any M [boxvR] T and finite Fp, there is a finite Gp such that acl∩p = gεGacl∩pM; however, we cannot always choose G = F. Then there are formulas θ and E so that θεp and for any M[boxvR]T, E defines an equivalence relation with finite classes on θ/E definably inherits the structure of either (...) a projective or affine space over some finite field. We then specify what other structure θ/E may inherit: there is some collection of definable subspaces of finite codimension and some set of algebraic points, which in the affine case may be in the canonically associated vector space, Up to acl, no further structure is possible. If we assume T is weakly minimal and has a strong type p as above, and also that T is unidimensional, we obtain a global description of any model of T in terms of those structures mentioned in the previous paragraph. (shrink)

Preferential model is one of the important semantical structures in nonmonotonic logic. This paper aims to establish an isomorphism theorem for preferential models, which gives us a purely algebraic characterization of the equivalence of preferential models. To this end, we present the notions of local similarity and local simulation. Based on these notions, two operators Δ(·) and μ(·) over preferential models are introduced and explored respectively. Together with other two existent operators ρ(·) and ΠD(·), we introduce an operator ∂D(·). Then (...) the isomorphism theorem is obtained in terms of ∂D(·), which asserts that for any two preferential models M₁ and M₂, they generate the same preferential inference if and only if ∂D(M₁) and ∂D(M₂) are isomorphic. Based on ∂D(·), we also get an alternative model-theoretical characterization of the well-known postulate "Weaken Disjunctive Rationality". Moreover, in the finite language framework, we show that Δ(μ(·)) is competent for the task of eliminating redundancy, and provide a representation result for k-relations. (shrink)

It is shown that given any finite system of monoid identities, it is decidable if the class of locally finite monoids that satisfy the system is a variety. This answers an open problem of Mark V. Sapir.

We initiate the study of a generalization of Kim-independence, Conant-independence, based on the notion of strong Kim-dividing of Kaplan, Ramsey and Shelah. A version of Conant-independence was originally introduced to prove that all [Formula: see text] theories are [Formula: see text]. We introduce an axiom on stationary independence relations, essentially generalizing the “freedom” axiom in some of the free amalgamation theories of Conant, and show that this axiom provides the correct setting for carrying out arguments of Chernikov, Kaplan and Ramsey (...) on [Formula: see text] theories relative to a stationary independence relation. Generalizing Conant’s results on free amalgamation to the limits of our knowledge of the [Formula: see text] hierarchy, we show using methods from Conant as well as our previous work that any theory where the equivalent conditions of this local variant of [Formula: see text] holds is either [Formula: see text] or [Formula: see text] and is either simple or [Formula: see text]. We observe that these theories give an interesting class of examples of theories where Conant-independence is symmetric. This includes all of Conant’s examples, the small cycle-free random graphs of Shelah, and the (finite-language) [Formula: see text]-categorical Hrushovski constructions of Evans and Wong. We then answer Conant’s question on the existence of non-modular free amalgamation theories. We show that the generic functional structures of Kruckman and Ramsey are examples of non-modular free amalgamation theories. We also show that any free amalgamation theory is [Formula: see text] or [Formula: see text], while an [Formula: see text] free amalgamation theory is simple if and only if it is modular. Finally, we show that every theory where Conant-independence is symmetric is [Formula: see text]. Therefore, symmetry for Conant-independence gives the next known neostability-theoretic dividing line on the [Formula: see text] hierarchy beyond [Formula: see text]. We explain the connection to some established open questions. (shrink)

Matter interacting classically with gravity in 3+1 dimensions usually gives rise to a continuum of degrees of freedom, so that, in any attempt to quantize the theory, ultraviolet divergences are nearly inevitable. Here, we investigate matter of a form that only displays a finite number of degrees of freedom in compact sections of space-time. In finite domains, one has only exact, analytic solutions. This is achieved by limiting ourselves to straight pieces of string, surrounded by locally flat (...) sections of space-time. Globally, however, the model is not finite, because solutions tend to generate infinite fractals. The model is not (yet) quantized, but could serve as an interesting setting for analytical approaches to classical general relativity, as well as a possible stepping stone for quantum models. Details of its properties are explained, but some problems remain unsolved, such as a complete description of the most violent interactions, which can become quite complex. (shrink)

We identify the locally finite graphs that are quantifier-eliminable and their first order theories in the signature of distance predicates. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

We show that for an arbitrary logic being locally tabular is a strictly weaker property than being locally finite. We describe our hunt for a logic that allows us to separate the two properties, revealing weaker and weaker conditions under which they must coincide, and showing how they are intertwined. We single out several classes of logics where the two notions coincide, including logics that are determined by a finite set of finite matrices, selfextensional logics, (...) algebraizable and equivalential logics. Furthermore, we identify a closure property on models of a logic that, in the presence of local tabularity, is equivalent to local finiteness. (shrink)

In the paper it will be shown that Reichenbach’s Weak Common Cause Principle is not valid in algebraic quantum field theory with locally finite degrees of freedom in general. Namely, for any pair of projections A, B supported in spacelike separated double cones ${\mathcal{O}}_{a}$ and ${\mathcal{O}}_{b}$ , respectively, a correlating state can be given for which there is no nontrivial common cause (system) located in the union of the backward light cones of ${\mathcal{O}}_{a}$ and ${\mathcal{O}}_{b}$ and commuting with (...) the both A and B. Since noncommuting common cause solutions are presented in these states the abandonment of commutativity can modulate this result: noncommutative Common Cause Principles might survive in these models. (shrink)

We consider all combinatorially possible systems corresponding to subsets of finite set theory (i.e., Zermelo-Fraenkel set theory without the axiom of infinity) and for each of them either provide a well-founded locally finite graph that is a model of that theory or show that this is impossible. To that end, we develop the technique of _axiom closure of graphs_.

We take Carnap’s problem to be to what extent standard consequence relations in various formal languages fix the meaning of their logical vocabulary, alone or together with additional constraints on the form of the semantics. This paper studies Carnap’s problem for basic modal logic. Setting the stage, we show that neighborhood semantics is the most general form of compositional possible worlds semantics, and proceed to ask which standard modal logics (if any) constrain the box operator to be interpreted as (...) in relational Kripke semantics. Except when restricted to finite domains, no modal logic characterizes all the Kripkean interpretation of P. Moreover, we show that, in contrast with the case of first-order logic, the obvious requirement of permutation invariance is not adequate in the modal case. After pointing out some known facts about modal logics that nevertheless force the Kripkean interpretation, we focus on another feature often taken to embody the gist of modal logic: locality. We show that invariance under point-generated subframes (properly defined) does single out the Kripkean interpretations, but only among topological interpretations, not in general. Finally, we define a notion of bisimulation invariance — another aspect of locality — that, together with a reasonable closure condition, gives the desired general result. Along the way, we propose a new perspective on normal neighborhood frames as filter frames, consisting of a set of worlds equipped with an accessibility relation, and a free filter at every world. (shrink)

We describe strongly minimal theories Tn with finite languages such that in the chain of countable models of Tn, only the first n models have recursive presentations. Also, we describe a strongly minimal theory with a finite language such that every non-saturated model has a recursive presentation.

We study complexity of the index set of countably categorical theories and Ehrenfeucht theories in finite languages.

For each class in the piecewise-local subregular hierarchy, a relativized (tier-based) variant is defined. Algebraic as well as automata-, language-, and model-theoretic characterizations are provided for each of these relativized classes, except in cases where this is provably impossible. These various characterizations are necessarily intertwined due to the well-studied logic-automaton connection and the relationship between finite-state automata and (syntactic) semigroups. Closure properties of each class are demonstrated by using automata-theoretic methods to provide constructive proofs for the closures that do (...) hold and giving language-theoretic counterexamples for those that do not. The net result of all of this is that, rather than merely existing as an operationally-defined parallel set of classes, these relativized variants integrate cleanly with the other members of the piecewise-local subregular hierarchy from every perspective. Relativization may even prove useful in the characterization of star-free, as every star-free stringset is the preprojection of another (also star-free) stringset whose syntactic semigroup is not a monoid. (shrink)

ABSTRACT The paper studies propositional logics in a bimodal language, in which the first modality is interpreted as the local truth, and the second as the universal truth. The logic S4UC is introduced, which is finitely axiomatizable, has the f.m.p. and is determined by every connected separable metric space.

Given a classical theory T, a Kripke model K for the language L of T is called T-normal or locally PA just in case the classical L-structure attached to each node of K is a classical model of T. Van Dalen, Mulder, Krabbe, and Visser showed that Kripke models of Heyting Arithmetic (HA) over finite frames are locally PA, and that Kripke models of HA over frames ordered like the natural numbers contain infinitely many PA-nodes. We show (...) that Kripke models of the latter sort are in fact PA-normal. This result is extended to a somewhat larger class of frames. (shrink)

We prove completeness for some language-theoretic models of the full Lambek calculus and its various fragments. First we consider syntactic concepts and syntactic concepts over regular languages, which provide a complete semantics for the full Lambek calculus \. We present a new semantics we call automata-theoretic, which combines languages and relations via closure operators which are based on automaton transitions. We establish the completeness of this semantics for the full Lambek calculus via an isomorphism theorem for the syntactic (...) concepts lattice of a language and a construction for the universal automaton recognizing the same language. Finally, we use automata-theoretic semantics to prove completeness of relation models of binary relations and finite relation models for the Lambek calculus without and with empty antecedents and \), thus solving a problem left open by Pentus. (shrink)