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.

In this paper, we concentrate on finite quasivarieties (i.e. classes of finite algebras defined by quasi-identities). We present a motivation for studying finite quasivarieties. We introduce a new type of conditions that is well suited for defining finite quasivarieties and compare these new conditions with quasi-identities.

In this paper, we concentrate on finite quasivarieties (i.e. classes of finite algebras defined by quasi-identities). We present a motivation for studying finite quasivarieties. We introduce a new type of conditions that is well suited for defining finite quasivarieties and compare these new conditions with quasi-identities.

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)

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)

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)

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.

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.

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)

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 ω‐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)

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.

The logic RM and its basic fragments (always with implication) are considered here as entire consequence relations, rather than as sets of theorems. A new observation made here is that the disjunction of RM is definable in terms of its other positive propositional connectives, unlike that of R. The basic fragments of RM therefore fall naturally into two classes, according to whether disjunction is or is not definable. In the equivalent quasivariety semantics of these fragments, which consist of subreducts (...) of Sugihara algebras, this corresponds to a distinction between strong and weak congruence properties. The distinction is explored here. A result of Avron is used to provide a local deduction-detachment theorem for the fragments without disjunction. Together with results of Sobociski, Parks and Meyer (which concern theorems only), this leads to axiomatizations of these entire fragments — not merely their theorems. These axiomatizations then form the basis of a proof that all of the basic fragments of RM with implication are finitely axiomatized consequence relations. (shrink)

Let be a finite collection of finite algebras of finite signature such that SP( ) has meet semi-distributive congruence lattices. We prove that there exists a finite collection 1 of finite algebras of the same signature, , such that SP( 1) is finitely axiomatizable.We show also that if , then SP( 1) is finitely axiomatizable. We offer new proofs of two important finite basis theorems of D. Pigozzi and R. Willard. Our actual results are somewhat more general than this abstract (...) indicates. (shrink)

Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathcal{K}$$ \end{document} be a finite collection of finite algebras of finite signature such that SP(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathcal{K}$$ \end{document}) has meet semi-distributive congruence lattices. We prove that there exists a finite collection \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathcal{K}$$ \end{document}1 of finite algebras of the same signature, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathcal{K}_1 \supseteq (...) \mathcal{K}$$ \end{document}, such that SP(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathcal{K}$$ \end{document}1) is finitely axiomatizable.We show also that if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$HS(\mathcal{K}) \subseteq SP(\mathcal{K})$$ \end{document}, then SP(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\mathcal{K}$$ \end{document}1) is finitely axiomatizable. We offer new proofs of two important finite basis theorems of D. Pigozzi and R. Willard. Our actual results are somewhat more general than this abstract indicates. (shrink)

Logics that do not have a deduction-detachment theorem (briefly, a DDT) may still possess a contextual DDT —a syntactic notion introduced here for arbitrary deductive systems, along with a local variant. Substructural logics without sentential constants are natural witnesses to these phenomena. In the presence of a contextual DDT, we can still upgrade many weak completeness results to strong ones, e.g., the finite model property implies the strong finite model property. It turns out that a finitary system has a contextual (...) DDT iff it is protoalgebraic and gives rise to a dually Brouwerian semilattice of compact deductive filters in every finitely generated algebra of the corresponding type. Any such system is filter distributive, although it may lack the filter extension property. More generally, filter distributivity and modularity are characterized for all finitary systems with a local contextual DDT, and several examples are discussed. For algebraizable logics, the well-known correspondence between the DDT and the equational definability of principal congruences is adapted to the contextual case. (shrink)

In classes of algebras such as lattices, groups, and rings, there are finite algebras which individually generate quasivarieties which are not finitely axiomatizable (see [2], [3], [8]). We show here that this kind of algebras also exist in Heyting algebras as well as in topological Boolean algebras. Moreover, we show that the lattice join of two finitely axiomatizable quasivarieties, each generated by a finite Heyting or topological Boolean algebra, respectively, need not be finitely axiomatizable. Finally, we solve problem 4 asked (...) in Rautenberg [10]. (shrink)

Entanglement and non-locality are non-classical global characteristics of quantum states important to the foundations of quantum mechanics. Recent investigations have shown that environmental noise, even when it is entirely local in influence, can destroy both of these properties in finite time despite giving rise to full quantum state decoherence only in the infinite time limit. These investigations, which have been carried out in a range of theoretical and experimental situations, are reviewed here.

The main question of this article is whether there is a family closed under finite differences (i.e., if A belongs to the family and B=∗A, then B also belongs to the family) that can be enumerated by any noncomputable c.e. degree, but which cannot be enumerated computably. This question was formulated by Greenberg et al. (2020) in their recent work in which families that are closed under finite differences, close to the Slaman–Wehner families, are deeply studied.

Finitary quasivarieties are characterized categorically by the existence of colimits and of an abstractly finite, regularly projective regular generator G. Analogously, infinitary quasivarieties are characterized: one drops the assumption that G be abstractly finite. For (finitary) varieties the characterization is similar: the regular generator is assumed to be exactly projective, i.e., hom(G, –) is an exact functor. These results sharpen the classical characterization theorems of Lawvere, Isbell and other authors.

For quasivarieties of algebras, we consider the property of having definable relative principal subcongruences, a generalization of the concepts of definable relative principal congruences and definable principal subcongruences. We prove that a quasivariety of algebras with definable relative principal subcongruences has a finite quasiequational basis if and only if the class of its relative (finitely) subdirectly irreducible algebras is strictly elementary. Since a finitely generated relatively congruence-distributive quasivariety has definable relative principal subcongruences, we get a new proof of (...) the result due to D. Pigozzi: a finitely generated relatively congruence-distributive quasivariety has a finite quasi-equational basis. (shrink)

Locality notions in logic say that the truth value of a formula can be determined locally, by looking at the isomorphism type of a small neighbourhood of its free variables. Such notions have proved to be useful in many applications. They all, however, refer to isomorphisms of neighbourhoods, which most local logics cannot test. A stronger notion of locality says that the truth value of a formula is determined by what the logic itself can say about that small neighbourhood. Since (...) the expressiveness of many logics can be characterized by games, one can also say that the truth value of a formula is determined by the type, with respect to a game, of that small neighbourhood. Such game-based notions of locality can often be applied when traditional isomorphism-based notions of locality cannot.Our goal is to study game-based notions of locality. We work with an abstract view of games that subsumes games for many logics. We look at three, progressively more complicated locality notions. The easiest requires only very mild conditions on the game and works for most logics of interest. The other notions, based on Hanf’s and Gaifman’s theorems, require more restrictions. We state those restrictions and give examples of logics that satisfy and fail the respective game-based notions of locality. (shrink)

A quasivariety of algebras has the joint embedding property (JEP) if and only if it is generated by a single algebra A. It is structurally complete if and only if the free ℵ0‐generated algebra in can serve as A. A consequence of this demand, called ‘passive structural completeness’ (PSC), is that the nontrivial members of all satisfy the same existential positive sentences. We prove that if is PSC then it still has the JEP, and if it has the JEP (...) and its nontrivial members lack trivial subalgebras, then its relatively simple members all belong to the universal class generated by one of them. Under these conditions, if is relatively semisimple then it is generated by one ‐simple algebra. We also prove that a quasivariety of finite type, with a finite nontrivial member, is PSC if and only if its nontrivial members have a common retract. The theory is then applied to the variety of De Morgan monoids, where we isolate the sub(quasi)varieties that are PSC and those that have the JEP, while throwing fresh light on those that are structurally complete. The results illuminate the extension lattices of intuitionistic and relevance logics. (shrink)

In this paper we establish the - and -transfer principles for finitely decidable locally finite varieties, where a class of structures is finitely decidable if the first order theory of its finite members is recursive. The transfer principles deal with the local structure of finite algebras and have strong global consequences.

We investigate finitarity of unification types in locally finite varieties of Heyting algebras, giving both positive and negative results. We make essential use of finite dualities within a conceptualization for E-unification theory 733–752) relying on the algebraic notion of a projective object.

Let FΛ be a finite dimensional path algebra of a quiver Λ over a field F. Let L and R denote the varieties of all left and right FΛ-modules respectively. We prove the equivalence of the following statements. • The subvariety lattice of L is a sublattice of the subquasivariety lattice of L. • The subquasivariety lattice of R is distributive. • Λ is an ordered forest.

Many known tools for proving expressibility bounds for first-order logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of (...) the easiest tools for proving expressibility bounds. These results apply beyond the first-order case. We use them to derive expressibility bounds for first-order logic with unary quantifiers and counting. We also characterize the notions of locality on structures of small degree. (shrink)

Let S denote the variety of Sugihara algebras. We prove that the lattice (K) of subquasivarieties of a given quasivariety K S is finite if and only if K is generated by a finite set of finite algebras. This settles a conjecture by Tokarz [6]. We also show that the lattice (S) is not modular.

A system of finite mathematics is proposed that has all of the power of classical mathematics. I believe that finite mathematics is not committed to any form of infinity, actual or potential, either within its theories or in the metalanguage employed to specify them. I show in detail that its commitments to the infinite are no stronger than those of primitive recursive arithmetic. The finite mathematics of sets is comprehensible and usable on its own terms, without appeal to any form (...) of the infinite. That makes it possible to, without circularity, obtain the axioms of full Zermelo-Fraenkel Set Theory with the Axiom of Choice (ZFC) by extrapolating (in a precisely defined technical sense) from natural principles concerning finite sets, including indefinitely large ones. The existence of such a method of extrapolation makes it possible to give a comparatively direct account of how we obtain knowledge of the mathematical infinite. The starting point for finite mathematics is Mycielski's work on locally finite theories. (shrink)

In this paper we study some questions concerning Łukasiewicz implication algebras. In particular, we show that every subquasivariety of Łukasiewicz implication algebras is, in fact, a variety. We also derive some characterizations of congruence permutable algebras. The starting point for these results is a representation of finite Łukasiewicz implication algebras as upwardly-closed subsets in direct products of MV-chains.

We provide a new proof of the following Pałasińska's theorem: Every finitely generated protoalgebraic relation distributive equality free quasivariety is finitely axiomatizable. The main tool we use are ${\mathcal{Q}}$ Q -relation formulas for a protoalgebraic equality free quasivariety ${\mathcal{Q}}$ Q . They are the counterparts of the congruence formulas used for describing the generation of congruences in algebras. Having this tool in hand, we prove a finite axiomatization theorem for ${\mathcal{Q}}$ Q when it has definable principal ${\mathcal{Q}}$ Q (...) -subrelations. This is a property obtained by carrying over the definability of principal subcongruences, invented by Baker and Wang for varieties, and which holds for finitely generated protoalgebraic relation distributive equality free quasivarieties. (shrink)

We prove a local normal form theorem of the Gaifman type for the infinitary logic L∞ωω whose formulas involve arbitrary unary quantifiers but finite quantifier rank. We use a local Ehrenfeucht-Fraïssé type game similar to the one in [9]. A consequence is that every sentence of L∞ωω of quantifier rank n is equivalent to an infinite Boolean combination of sentences of the form ψ, where ψ has counting quantifiers restricted to the -neighborhood of y.

Finitely axiomatizable ℵ 1 categorical theories are locally modular.