Search

We provide two proofs of the compactness theorem for extensions of first‐order logic based on team semantics. First, we build upon Lück's [16] ultraproduct construction for team semantics and prove a suitable version of Łoś' Theorem. Second, we show that by working with suitably saturated models, we can generalize the proof of Kontinen and Yang [13] to sets of formulas with arbitrarily many variables. [ABSTRACT FROM AUTHOR]

Interpretability logic is a modal formalization of relative interpretability between first‐order arithmetical theories. Verbrugge semantics is a generalization of Veltman semantics, the basic semantics for interpretability logic. Bisimulation is the basic equivalence between models for modal logic. We study various notions of bisimulation between Verbrugge models and develop a new one, which we call w‐bisimulation. We show that the new notion, while keeping the basic property that bisimilarity implies modal equivalence, is weak enough to allow the converse to hold in the finitary case. To do this, we develop and use an appropriate notion of bisimulation games between Verbrugge models. [ABSTRACT FROM AUTHOR]

There is an extensive literature related to the algebraization of first‐order logic. But the algebraization of full second‐order logic, or Henkin‐type second‐order logic, has hardly been researched. The question arises: what kind of set algebra is the algebraic version of a Henkin‐type model of second‐order logic? The question is investigated within the framework of the theory of cylindric algebras. The answer is: a kind of cylindric‐relativized diagonal restricted set algebra. And the class of the subdirect products of these set algebras is the algebraization of Henkin‐type second‐order logic. It is proved that the algebraization of a complete calculus of the Henkin‐type second‐order logic is a class of a kind of diagonal restricted cylindric algebras. Furthermore, the connection with the non‐standard enlargements of standard complete second‐order structures is investigated. [ABSTRACT FROM AUTHOR]

In recent years, model theory has widened its scope to include metric structures by considering real-valued models whose underlying set is a complete metric space. We show that it is possible to carry out this work by giving presentation theorems that translate the two main frameworks (continuous first order logic and Metric Abstract Elementary Classes) into discrete settings (a nice fragment of [ABSTRACT FROM AUTHOR]

Quasiminimal structures play an important role in non-elementary categoricity. In this paper we explore possibilities of constructing quasiminimal models of a given first-order theory. We present several constructions with increasing control of the properties of the outcome using increasingly stronger assumptions on the theory. We also establish an upper bound on the Hanf number of the existence of arbitrarily large quasiminimal models. [ABSTRACT FROM AUTHOR]

We study the Borel reducibility of isomorphism relations in the generalized Baire space [ABSTRACT FROM AUTHOR]

We show how to build prime models in classes of saturated models of abstract elementary classes (AECs) having a well-behaved independence relation: Let [ABSTRACT FROM AUTHOR]

In this paper [ABSTRACT FROM AUTHOR]

We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable. [ABSTRACT FROM AUTHOR]

A structure [ABSTRACT FROM AUTHOR]

We introduce reduced products in continuous logic, and provide ways to establish satisfaction in the reduced product based on the satisfaction in its fibers, and conversely, on the lines that Horn and Chang did for reduced products in classical logic. We also consider a definition of a sheaf of metric structures, endow its stalks with a metric prestructure, and determine what filters can be used so that a collection of reduced products of arbitrary structures forms a sheaf on a given index space. [ABSTRACT FROM AUTHOR]

Using Butz and Moerdijk's topological groupoid representation of a topos with enough points, a 'syntax-semantics' duality for geometric theories is constructed. The emphasis is on a logical presentation, starting with a description of the semantic topological groupoid of models and isomorphisms of a theory. It is then shown how to extract a theory from equivariant sheaves on a topological groupoid in such a way that the result is a contravariant adjunction between theories and groupoids, the restriction of which is a duality between theories with enough models and semantic groupoids. Technically a variant of the syntax-semantics duality constructed in 1 for first-order logic, the construction here works for arbitrary geometric theories and uses a slice construction on the side of groupoids-reflecting the use of 'indexed' models in the representation theorem-which in several respects simplifies the construction and the characterization of semantic groupoids. [ABSTRACT FROM AUTHOR]

We refine the constructions of Ferrante-Rackoff and Solovay on iterated definitions in first-order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier-free case and in the case of purely existential or universal quantifiers, we show that Ω( n /log n) quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao-Håstad switching lemma (© 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

The classical notion of Lévy process is generalized to one that takes as its values probabilities on a first or-der model equipped with a commutative semigroup. This is achieved by applying a convolution product on definable probabilities and the infinite divisibility with respect to it (© 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

There are several ways for defining the notion submodel for Kripke models of intuitionistic first-order logic. In our approach a Kripke model A is a submodel of a Kripke model B if they have the same frame and for each two corresponding worlds Aα and Bα of them, Aα is a subset of Bα and forcing of atomic formulas with parameters in the smaller one, in A and B, are the same. In this case, B is called an extension of A. We characterize theories that are preserved under taking submodels and also those that are preserved under taking extensions as universal and existential theories, respectively. We also study the notion elementary submodel defined in the same style and give some results concerning this notion. In particular, we prove that the relation between each two corresponding worlds of finite Kripke models A ≤ B is elementary extension (in the classical sense) (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

In this note we give an interpretation of cylindric algebras as algebras of sentences (rather than formulas) of first order logic. We show that the isomorphism types of such algebras of sentences coincide with the class of neat reducts of cylindric algebras. Also we show how this interpretation sheds light on some recent results. This is done by likening Henkin's Neat Embedding Theorem to his celebrated completeness proof. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

This paper is concerned with techniques for identifying simple and quantified lattice points in 2SAT polytopes. 2SAT polytopes generalize the polyhedra corresponding to Boolean 2SAT formulas, Vertex-Packing (Covering, Partitioning) and Network flow problems; they find wide application in the domains of Program verification (Software Engineering) and State-Space search (Artificial Intelligence). Our techniques are based on the symbolic elimination strategy called the Fourier-Motzkin elimination procedure and thus have the advantages of being extremely simple (from an implementational perspective) and incremental. We also provide a characterization of a 2SAT polytope in terms of its extreme points and derive some interesting hardness results for associated optimization problems. Finally, we provide a brief discussion on the maximum size of a subdeterminant of the linear system representing a 2SAT polytope; this parameter plays a vital role in deriving analytical bounds on the size of the search space for checking whether the polyhedron includes a lattice point. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We study the class of Sperner spaces, a generalized version of affine spaces, as defined in the language of pointline incidence and line parallelity. We show that, although the class of Sperner spaces is a pseudo-elementary class, it is not elementary nor even ℒ∞ω-axiomatizable. We also axiomatize the first-order theory of this class. [ABSTRACT FROM AUTHOR]

In this paper we provide quantifier-free, constructive axiomatizations for 2-dimensional absolute, Euclidean, and hyperbolic geometry. The main novelty consists in the first-order languages in which the axiom systems are formulated. [ABSTRACT FROM AUTHOR]

The article focuses on the role of preservation theorems in the study of fragments of first-order logic such as finite variable fragments, modal fragment, and the guarded fragment. It mentions the failure of existential preservation theorem for two-variable first order logic (FO2). It states that homomorphism preservation theorem applies for FO2. Meanwhile, it discusses the partial isomorphism between structure in the n-round two-pebble game.

The article discusses an extension of the Lemma of Rasiowa and Sikorski. It proves an extension of the Lemma of Rasiowa and Sikorski and provides some applications through several cases in the omitting types such as fixing a first-order theory T. It also analyzes the relationship corresponding results on the omission of types.

The article discusses the definability in monadic ∑1/1 and monadic II1/1 of the problems REGk. It says that REGk/k and XREGk/k are logspace equivalence to REACH and CONN wherein REACH is the problem of whether a given graph has a path joining two given vertices and CONN is the problem of whether a given graph is connected. It mentions the use of monadic first-order reductions and monadic ∑1/1 games. It also compares their definability with their computational complexity.

The article discusses constructive sheaf theory semantics. It says that sheaf semantics was derived from a predicative and constructive model framework and Martin-Löf type theory. Furthermore, sheaf semantics has constructive proofs on its completeness in first order institutionistic logic through the use provable functional relations.

The article focuses on the consistency of first-order fragment with regards to Frege's logical system in the Grundgesetze der Arithmetic. It discusses some formulation and proof for the arbitrary first-order theories using the Fregean theory, abstraction scheme, and conservative extension. It states the inconsistency of second-order quantification and functional dependence of extensions in the Grundgesetze der Arithmetic due to the Russell's paradox and Cantor's diagonalization argument.

The article focuses on the constructive axiomatization for Euclidean planes in a first-order language with two ternary operation symbols. It says that the language for constructive Eucliden planes includes the three non-collinear points and R, U which are ternary operation symbols. It adds that the axiom system for Euclidean planes was obtained through the constructive expression of the axioms proposed in first-order logic for the theory of congruence in Euclidean planes.

The article discusses some classical logic's interpretations. It highlights various single-negation embeddings and describes some types of superintuitionistic first-order predicate logics, wherein the classical first-order calculus can be interpreted. It explores the Heyting's logic's minimal extensions wherein the embedding of the classical predicate logic is possible through these translations.

The article discusses the axiomatization of the first-order intermediate logics through the use of contextual distinction between the internal and external use of logic symbols in solving bounded Kripkean heights equation. The author relates that proving the theorem about Kripke frame being the determinant of a first-order logic will be the focus of the article. He presents the three conditions that will satisfy a Kripke frame without domain equation.

The article offers information on the general class of free-variable theories, and semantic analysis. It states that logical axioms should be propositional axioms, and in identity axioms, formulas have the form x=x. It presents theorems, which express two forms of the semantic completeness theorem, which was discussed for first-order theories by J. R. Shoenfield.

The article provides notes regarding H. Friedman's theorem. It states the improvement of H. Friedman's theorem results using usual first-order language of arithmetic. It highlights the mathematical proofs expressed in countable models of Peano's ax ioms that are isomorphic to initial segments. Moreover, it stresses the representation of countable non-standard models in the theorem.

The article discusses first-order formulas presented in conjunctive quantificational form. It notes the application of satisfiability test to examine the complexity of mathematical problems with identity symbols in the formulas. It compares the use of formulas with monadic predicate symbols to the propositional formulas applied in conjunctive forms. Moreover, it mentions the dyadic predicates in the mathematical form.

The article presents a reprint of the article "A Free-Variable Theory of Primitive Recursive Arithmetic," by Daniel G. Schwartz, which appeared in the previous issue of the journal. It discusses a free-variable theory, which is a first-order theory that allows nonlogical rules of proof, of primitive recursive arithmetic. It proposes that a free-variable theory postulates primitive recursive functions' defining equations as nonlogical axioms.

The article offers information on some restricted collection schemata and some restricted comprehension schemata, that are provable in weak set theories. It states that it denotes a first order theory, where S consists of =, ∈ and constants, and the axiom of extensionality. It presents theorems for on-bounded formula with parameters from a finite set.

The article discusses the first-order theory of the degrees of non-constructibility of reals or c-degrees. It proves the theorem that first-order theory of the c-degrees is recursively isomorphic to the truth set of analysis. It introduces the facts on the use of Adamovicz's construction in the initial sections of the degrees and carry out the translation of analysis into the language of c-degrees.

The article discusses the extension method for partial isomorphism and the post-language representation theorem. It attempts to present an analogous result for the first order modal language against a post algebra. It explores the functorial aspect of the first order logic languages and their relevance in the analysis of logical languages.

The article presents a study which discusses the possible formulations of Löwenheim-Skolem Theorem to finite structures. It mentions the possible formulations which include having an arbitrary large model, considering function f, and trying some fragments if no positive result for whole first-order logic. Furthermore, a counterexample that refutes the possible formulations is presented.

The article offers information on certain sets of parallel first-order theories constitute Boolean algebras. It states that there may be finite or infinite number of premises, besides the axioms of a system of first-order logic. It mentions that in scientific praxis, obtaining a consistent theory can be complicated, because the choice of premises that should be weakened or sacrificed may be a result of hard work.