PARTIALLY ORDERED CONNECTIVES

We show that a coherent theory of partially ordered connectives can be developed along the same line as partially ordered quantification. We estimate the expressive power of various partially ordered connectives and use methods like Ehrenfeucht games and infinitary logic to get various undefinability results.     

The quantifier complexity of polynomial‐size iterated definitions in first‐order logic

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)     

Homomorphism-Homogeneous Partially Ordered Sets

A structure is called homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this paper we characterize homomorphism-homogeneous partially ordered sets (where a homomorphism between partially ordered sets A and B is a mapping f : A →B satisfying ). We show that there are five types of homomorphism-homogeneous partially ordered sets: partially ordered sets whose connected components are chains; trees; dual trees; partially ordered sets which split into a tree and a dual tree; and X ₅-dense locally bounded partially ordered sets. Supported by the Ministry od Science and Environmental Protection of the Republic of Serbia, Grant No. 144017.     

Complexity of syntactical tree fragments of Independence-Friendly logic

A dichotomy result of Sevenster (2014) [29] completely classified the quantifier prefixes of regular Independence-Friendly (IF) logic according to the patterns of quantifier dependence they contain. On one hand, prefixes that contain “Henkin” or “signalling” patterns were shown to characterize fragments of IF logic that capture NP-complete problems; all the remaining prefixes were shown instead to be essentially first-order.In the present paper we develop the machinery which is needed in order to extend the results of Sevenster to non-prenex, regular IF sentences. This involves shifting attention from quantifier prefixes to a (rather general) class of syntactical tree prefixes.We partially classify the fragments of regular IF logic that are thus determined by syntactical trees; in particular, a) we identify four classes of tree prefixes that are neither signaling nor Henkin, and yet express NP-complete problems and other second-order concepts; and b) we give more general criteria for checking the first-orderness of an IF sentence.     

On vectorizations of unary generalized quantifiers

Vectorization of a class of structures is a natural notion in finite model theory. Roughly speaking, vectorizations allow tuples to be treated similarly to elements of structures. The importance of vectorizations is highlighted by the fact that if the complexity class PTIME corresponds to a logic with reasonable syntax, then it corresponds to a logic generated via vectorizations by a single generalized quantifier (Dawar in J Log Comput 5(2):213–226, 1995). It is somewhat surprising, then, that there have been few systematic studies of the expressive power of vectorizations of various quantifiers. In the present paper, we consider the simplest case: the cardinality quantifiers C _S . We show that, in general, the expressive power of the vectorized quantifier logic ${{\rm FO}(\{{\mathsf C}_S^{(n)}\, | \, n \in \mathbb{Z}_+\})}$ is much greater than the expressive power of the non-vectorized logic FO(C _S ).     

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.     

Elimination of algorithmic quantifiers for ordered differential algebra

In [2], Singer proved that the theory of ordered differential fields has a model completion, i.e, the theory of closed ordered differential fields, CODF. As a result, CODF admits elimination of quantifiers. In this paper we give an algorithm to eliminate the quantifiers of CODF-formulas. Received: 29 May 1996     

An Ehrenfeucht‐Fraïssé game for

In this paper we develop an Ehrenfeucht‐Fraïssé game for . Unlike the standard Ehrenfeucht‐Fraïssé games which are modeled solely after the behavior of quantifiers, this new game also takes into account the behavior of connectives in logic. We prove the adequacy theorem for this game. We also apply the new game to prove complexity results about infinite binary strings.     

An Alternative Definition of Quantifiers on Four-Valued Łukasiewicz Algebras

An alternative notion of an existential quantifier on four-valued ?ukasiewicz algebras is introduced. The class of four-valued ?ukasiewicz algebras endowed with this existential quantifier determines a variety which is denoted by \(\mathbb {M}_{\frac{2}{3}}\mathbb {L}_4\). It is shown that the alternative existential quantifier is interdefinable with the standard existential quantifier on a four-valued ?ukasiewicz algebra. Some connections between the new existential quantifier and the existential quantifiers defined on bounded distributive lattices and Boolean algebras are given. Finally, a completeness theorem for the monadic four-valued ?ukasiewicz predicate calculus corresponding to the dual of the alternative existential quantifier is proven.     

Convergence Laws for Very Sparse Random Structures with Generalized Quantifiers

We prove convergence laws for logics of the form , where is a properly chosen collection of generalized quantifiers, on very sparse finite random structures. We also study probabilistic collapsing of the logics , where is a collection of generalized quantifiers and k ∈ ℕ₊, under arbitrary probability measures of finite structures.     

Coupled fixed point results for mappings without mixed monotone property in partially ordered G-metric spaces

In this paper, we prove coupled fixed point results for mappings without mixed monotone property in partially ordered G-metric spaces. Also we showed that if $(X\text{,}G)$ is regular, these fixed point results holds.     

On probabilistic elimination of generalized quantifiers

Let ?? be a collection of generalized quantifiers. We give a convenient characterization for the cases where the logic ??(??) has quantifier elimination for an arbitrary class of structures. The results provide a method to prove zero‐one and convergence laws for such logics with arbitrary sequences of probability measures of finite structures. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 1–36, 2001     

Fractional weak discrepancy and interval orders

The fractional weak discrepancywd_F(P) of a poset P=(V,?) was introduced in [A. Shuchat, R. Shull, A. Trenk, The fractional weak discrepancy of a partially ordered set, Discrete Applied Mathematics 155 (2007) 2227-2235] as the minimum nonnegative k for which there exists a function satisfying (i) if a?b then f(a)+1≤f(b) and (ii) if a∥b then |f(a)−f(b)|≤k. In this paper we generalize results in [A. Shuchat, R. Shull, A. Trenk, Range of the fractional weak discrepancy function, ORDER 23 (2006) 51-63; A. Shuchat, R. Shull, A. Trenk, Fractional weak discrepancy of posets and certain forbidden configurations, in: S.J. Brams, W.V. Gehrlein, F.S. Roberts (Eds.), The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, Springer, New York, 2009, pp. 291-302] on the range of the wd_F function for semiorders (interval orders with no induced ) to interval orders with no , where n≥3. In particular, we prove that the range for such posets P is the set of rationals that can be written as r/s, where 0≤s−1≤r<(n−2)s. If wd_F(P)=r/s and P has an optimal forcing cycle C with and , then r≤(n−2)(s−1). Moreover when s≥2, for each r satisfying s−1≤r≤(n−2)(s−1) there is an interval order having such an optimal forcing cycle and containing no.     

Degrees of logics with Henkin quantifiers in poor vocabularies

We investigate some logics with Henkin quantifiers. For a given logic L, we consider questions of the form: what is the degree of the set of L–tautologies in a poor vocabulary (monadic or empty)? We prove that the set of tautologies of the logic with all Henkin quantifiers in empty vocabulary L* is of degree 0. We show that the same holds also for some weaker logics like L(H) and L(E). We show that each logic of the form L^(k)(Q), with the number of variables restricted to k, is decidable. Nevertheless – following the argument of M. Mostowski from [Mos89] – for each reasonable set theory no concrete algorithm can provably decide L^(k)(Q), for some (Q). We improve also some results related to undecidability and expressibility for logics L(H₄) and L(F₂) of Krynicki and M. Mostowski from [KM92].Mathematics Subject Classification (2000): 03C80, 03D35, 03B25Revised version: 28 August 2003     

Directed ideals in partially ordered vector spaces

For a linear subspace I$I$ of a Riesz space there are various well-known properties that are equivalent to I$I$ being an ideal, such as I$I$ is a full Riesz subspace, I$I$ is a solid subspace, I$I$ is a Riesz subspace and the kernel of a positive linear map, I$I$ is the kernel of a Riesz homomorphism. Generalizations of these properties to partially ordered vector spaces are considered and their relations are investigated. It is shown that for directed subspaces all these generalizations are equivalent, just as in the case of Riesz spaces.     

Beth’s theorem in cardinality logics

We prove that the Beth definability theorem fails for a comprehensive class of first-order logics with cardinality quantifiers. In particular, we give a counterexample to Beth’s theorem forL(Q), which is finitary first-order logic (with identity) augmented with the quantifier “there exists uncountably many”. This research was partially supported by NSF GP29254.     

The model theory of m‐ordered differential fields

In his Ph.D. thesis [7], L. van den Dries studied the model theory of fields (more precisely domains) with finitely many orderings and valuations where all open sets according to the topology defined by an order or a valuation is globally dense according with all other orderings and valuations. Van den Dries proved that the theory of these fields is companionable and that the theory of the companion is decidable (see also [8]). In this paper we study the case where the fields are expanded with finitely many orderings and an independent derivation. We show that the theory of these fields still admits a model companion in the language L = {+, –, ·, D, <₁, …, <_m, 1, 0}. We denote this model companion by CODF_m and give a geometric axiomatization of this theory which uses basic notions of algebraic geometry and some generalized open subsets which appear naturally in this context. This axiomatization allows to recover (just by putting m = 1) the one given in [4] for the theory CODF of closed ordered differential fields. Most of the technics we use here are already present in [2] and [4]. Finally, we prove that it is possible to describe the completions of CODF_m and to obtain quantifier elimination in a slightly enriched (infinite) language. This generalizes van den Dries' results in the “derivation free” case. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)