Dependence of variables construed as an atomic formula

We define a logic D capable of expressing dependence of a variable on designated variables only. Thus D has similar goals to the Henkin quantifiers of [4] and the independence friendly logic of [6] that it much resembles. The logic D achieves these goals by realizing the desired dependence declarations of variables on the level of atomic formulas. By [3] and [17], ability to limit dependence relations between variables leads to existential second order expressive power. Our D avoids some difficulties arising in the original independence friendly logic from coupling the dependence declarations with existential quantifiers. As is the case with independence friendly logic, truth of D is definable inside D. We give such a definition for D in the spirit of [11] and [2] and [1].     

An arithmetical view to first-order logic

A value space is a topological algebra B equipped with a non-empty family of continuous quantifiers :B^∗→B. We will describe first-order logic on the basis of B. Operations of B are used as connectives and its relations are used to define statements. We prove under some normality conditions on the value space that any theory in the new setting can be represented by a classical first-order theory.     

A double arity hierarchy theorem for transitive closure logic

In this paper we prove that thek-ary fragment of transitive closure logic is not contained in the extension of the (k–1)-ary fragment of partial fixed point logic by all (2k–1)-ary generalized quantifiers. As a consequence, the arity hierarchies of all the familiar forms of fixed point logic are strict simultaneously with respect to the arity of the induction predicates and the arity of generalized quantifiers.Although it is known that our theorem cannot be extended to the sublogic deterministic transitive closure logic, we show that an extension is possible when we close this logic under congruence.Supported by a grant from the University of Helsinki. This research was initiated while he was a Junior Researcher at the Academy of FinlandThis article was processed by the author using the LATEX style filepljourlm from Springer-Verlag.     

Spaces of orders and their Turing degree spectra

We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora’s (2004) [28] investigation of orders on groups in topology and Solomon’s (2002) [31] investigation of these orders in computable algebra. Furthermore, we establish that a computable free group F_n of rank n>1 has a bi-order in every Turing degree.     

Vectorization hierarchies of some graph quantifiers

We give a sufficient condition for the inexpressibility of the k-th extended vectorization of a generalized quantifier in , the extension of first-order logic by all k-ary quantifiers. The condition is based on a model construction which, given two -equivalent models with certain additional structure, yields a pair of -equivalent models. We also consider some applications of this condition to quantifiers that correspond to graph properties, such as connectivity and planarity. Received: 15 October 1996     

Capturing k-ary existential second order logic with k-ary inclusion–exclusion logic

In this paper we analyze k-ary inclusion–exclusion logic, INEX[k], which is obtained by extending first order logic with k-ary inclusion and exclusion atoms. We show that every formula of INEX[k] can be expressed with a formula of k-ary existential second order logic, ESO[k]. Conversely, every formula of ESO[k] with at most k-ary free relation variables can be expressed with a formula of INEX[k]. From this it follows that, on the level of sentences, INEX[k] captures the expressive power of ESO[k].We also introduce several useful operators that can be expressed in INEX[k]. In particular, we define inclusion and exclusion quantifiers and so-called term value preserving disjunction which is essential for the proofs of the main results in this paper. Furthermore, we present a novel method of relativization for team semantics and analyze the duality of inclusion and exclusion atoms.     

Inclusion and exclusion dependencies in team semantics — On some logics of imperfect information

We introduce some new logics of imperfect information by adding atomic formulas corresponding to inclusion and exclusion dependencies to the language of first order logic. The properties of these logics and their relationships with other logics of imperfect information are then studied. As a corollary of these results, we characterize the expressive power of independence logic, thus answering an open problem posed in Grädel and Väänänen, 2010 [9].     

Special transformations in algebraically closed valued fields

We present two of the three major steps in the construction of motivic integration, that is, a homomorphism between Grothendieck semigroups that are associated with a first-order theory of algebraically closed valued fields, in the fundamental work of Hrushovski and Kazhdan (2006) [8]. We limit our attention to a simple major subclass of V-minimal theories of the form ACV F_S(0,0), that is, the theory of algebraically closed valued fields of pure characteristic 0 expanded by a (V F,Γ)-generated substructure S in the language L_RV. The main advantage of this subclass is the presence of syntax. It enables us to simplify the arguments with many different technical details while following the major steps of the Hrushovski-Kazhdan theory.     

The expressive power of k-ary exclusion logic

In this paper we study the expressive power of k-ary exclusion logic, EXC[k], that is obtained by extending first order logic with k-ary exclusion atoms. It is known that without arity bounds exclusion logic is equivalent with dependence logic. By observing the translations, we see that the expressive power of EXC[k] lies in between k-ary and ($k+1$)-ary dependence logics. We will show that, at least in the case when $k=1$, both of these inclusions are proper.In a recent work by the author it was shown that k-ary inclusion-exclusion logic is equivalent with k-ary existential second order logic, ESO[k]. We will show that, on the level of sentences, it is possible to simulate inclusion atoms with exclusion atoms, and in this way express ESO[k]-sentences by using only k-ary exclusion atoms. For this translation we also need to introduce a novel method for “unifying” the values of certain variables in a team. As a consequence, EXC[k] captures ESO[k] on the level of sentences, and we obtain a strict arity hierarchy for exclusion logic. It also follows that k-ary inclusion logic is strictly weaker than EXC[k].Finally we use similar techniques to formulate a translation from ESO[k] to k-ary inclusion logic with an alternative strict semantics. Consequently, for any arity fragment of inclusion logic, strict semantics is strictly more expressive than lax semantics.     

The eskolemization of universal quantifiers

This paper is a sequel to the papers Baaz and Iemhoff (2006, 2009) [4] and [6] in which an alternative skolemization method called eskolemization was introduced that, when restricted to strong existential quantifiers, is sound and complete for constructive theories. In this paper we extend the method to universal quantifiers and show that for theories satisfying the witness property it is sound and complete for all formulas. We obtain a Herbrand theorem from this, and apply the method to the intuitionistic theory of equality and the intuitionistic theory of monadic predicates.     

Model theoretic dynamics in Galois fashion

We fix a monster model $\mathfrak{D}$ of some stable theory and investigate substructures of $\mathfrak{D}$ which are existentially closed within the class of substructures equipped with an action of a fixed group G. We describe them as PAC substructures of $\mathfrak{D}$ and obtain results related to Galois theory.Assuming that the class of these existentially closed substructures is elementary, we show that, under the assumption of having bounded models, its theory is simple and eliminates quantifiers up to some existential formulas. Moreover, this theory codes finite sets and allows a geometric elimination of imaginaries, but not always a weak elimination of imaginaries.     

Linear orderings and powers of characterizable cardinals

We say that a countable model M completely characterizes an infinite cardinal κ, if the Scott sentence of M has a model in cardinality κ, but no models in cardinality κ⁺. If a structure M completely characterizes κ, κ is called characterizable. In this paper, we concern ourselves with cardinals that are characterizable by linearly ordered structures (cf. Definition 2.1).Under the assumption of GCH, Malitz completely resolved the problem by showing that κ is characterizable if and only if κ=ℵ_α, for some α<ω₁ (cf. Malitz (1968) [7] and Baumgartner (1974) [1]). Our results concern the case where GCH fails.From Hjorth (2002) [3], we can deduce that if κ is characterizable, then κ⁺ is characterizable by a densely ordered structure (see Theorem 2.4 and Corollary 2.5).We show that if κ is homogeneously characterizable (cf. Definition 2.2), then κ is characterizable by a densely ordered structure, while the converse fails (Theorem 2.3).The main theorems are (1) If κ>2^λ is a characterizable cardinal, λ is characterizable by a densely ordered structure and λ is the least cardinal such that κ^λ>κ, then κ^λ is also characterizable (Theorem 5.4) and (2) if ℵ_α and κ^ℵ_α are characterizable cardinals, then the same is true for κ^ℵ_α+β, for all countable β (Theorem 5.5).Combining these two theorems we get that if κ>2^ℵ_α is a characterizable cardinal, ℵ_α is characterizable by a densely ordered structure and ℵ_α is the least cardinal such that κ^ℵ_α>κ, then for all β<α+ω₁, κ^ℵ_β is characterizable (Theorem 5.7). Also if κ is a characterizable cardinal, then κ^ℵ_α is characterizable, for all countable α (Corollary 5.6). This answers a question of the author in Souldatos (submitted for publication) [8].     

The complexity of cover graph recognition for some varieties of finite lattices

We address the following decision problem: Instance: an undirected graphG. Problem: IsG a cover graph of a lattice? We prove that this problem is NP-complete. This extends results of Brightwell [5] and Ne?et?il and Rödl [12]. On the other hand, it follows from Alvarez theorem [2] that recognizing cover graphs of modular or distributive lattices is in P. An important tool in the proof of the first result is the following statement which may be of independent interest: Given an integerl, l?3, there exists an algorithm which for a graphG withn vertices yields, in time polynomial inn, a graphH with the number of vertices polynomial inn, and satisfying girth(H)?l and χ(H)=χ(G).     

Light Dialectica revisited

We upgrade the light Dialectica interpretation (Hernest, 2005) [6] by adding two more light universal quantifiers, which are both semi-computational and semi-uniform and complement each other. An illustrative example is presented for the new light quantifiers and a new application is given for the older uniform quantifier. The realizability of new light negative formulations for the Axiom of Choice and for the Independence of Premises is explored in the new setting.     

The Whitney embedding theorem for tropical torsion modules: Classification of tropical modules

We prove here a tropical version of the well-known Whitney embedding theorem [32] stating that a smooth connected m-dimensional compact differential manifold can be embedded into R^2m+1.The tropical version of this theorem states that a tropical torsion module with m generators can always be embedded into the free tropical module , where p (equals to 2 for m=2, and otherwise) is the number of rows supporting the torsion, when the generators are given by the (independent) columns of a matrix of size n×m.As a corollary, we get that tropical m-dimensional torsion modules are classified by a (m-1)(m(m-1)-1)-parameter family.     

The prolific backbone for supercritical superprocesses

We develop an idea of Evans and O’Connell (1994) [13], Engländer and Pinsky (1999) [10] and Duquesne and Winkel (2007) [4] by giving a pathwise construction of the so-called ‘backbone’ decomposition for supercritical superprocesses. Our results also complement a related result for critical (1+β)-superprocesses given in Etheridge and Williams (2003) [11]. Our approach relies heavily on the use of Dynkin-Kuznetsov N-measures.     

Note on witnessed Gödel logics with Delta

Witnessed Gödel logics are based on the interpretation of ∀ (∃) by minimum (maximum) instead of supremum (infimum). Witnessed Gödel logics appear for many practical purposes more suited than usual Gödel logics as the occurrence of proper infima/suprema is practically irrelevant. In this note we characterize witnessed Gödel logics with absoluteness operator △ w.r.t. witnessed Gödel logics using a uniform translation.     

Equivalence in Finite-Variable Logics is Complete for Polynomial Time

of first-order logic whose formulas contain at most k variables (for some ). We show that for each , equivalence in the logic is complete for polynomial time. Moreover, we show that the same completeness result holds for the powerful extension of with counting quantifiers (for every ). The k-dimensional Weisfeiler–Lehman algorithm is a combinatorial approach to graph isomorphism that generalizes the naive color-refinement method (for ). Cai, Fürer and Immerman [6] proved that two finite graphs are equivalent in the logic if, and only if, they can be distinguished by the k-dimensional Weisfeiler-Lehman algorithm. Thus a corollary of our main result is that the question of whether two finite graphs can be distinguished by the k-dimensional Weisfeiler–Lehman algorithm is P-complete for each . Received: March 23, 1998