The development of the dynamic semantics of natural languagehas put issues of variable control on the agenda of formal semantics. Inthis paper we regard variables as names for stacks of values and makeexplicit several control actions as push and pop actions on stacks. Weapply this idea both to static and dynamic languages and compare theirfinite variable hierarchies, i.e., the relation between the number ofvariable stacks that is available and the expressivity of the language.This can be compared in natural (...) languages with relating the number ofpronouns available to the expressivity of the language.The results are obtained using techniques from static and dynamic modeltheory: model theoretic games, transition systems and bisimulation. (shrink)

Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k variables. The logics Lk are the simplest finite-variable logics. Later, we are going (...) to consider infinitary variants and extensions by so-called counting quantifiers.Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time or polynomial space can be characterized as collections of all classes of finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth. (shrink)

Parity games are combinatorial representations of closed Boolean μ-terms. By adding to them draw positions, they have been organized by Arnold and Santocanale [3] and [27] into a μ-calculus whose standard interpretation is over the class of all complete lattices. As done by Berwanger et al. [8] and [9] for the propositional modal μ-calculus, it is possible to classify parity games into levels of a hierarchy according to the number of fixed-point variables. We ask whether this hierarchy collapses (...) w.r.t. the standard interpretation. We answer this question negatively by providing, for each n≥1, a parity game Gn with these properties: it unravels to a μ-term built up with n fixed-point variables, it is not semantically equivalent to any game with strictly less than n−2 fixed-point variables. (shrink)

We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension n (for finite n > 2) with the additional property that they are one-generated and the set of all n by n atomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments (...) of first order logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic. (shrink)

What precisely are fragments of classical first-order logic showing “modal” behaviour? Perhaps the most influential answer is that of Gabbay 1981, which identifies them with so-called “finite-variable fragments”, using only some fixed finite number of variables (free or bound). This view-point has been endorsed by many authors (cf. van Benthem 1991). We will investigate these fragments, and find that, illuminating and interesting though they are, they lack the required nice behaviour in our sense. (Several new negative results (...) support this claim.) As a counterproposal, then, we define a large fragment of predicate logic characterized by its use of only bounded quantification. This so-called guarded fragment enjoys the above nice properties, including decidability, through an effectively bounded finite model property. (These are new results, obtained by generalizing notions and techniques from modal logic.) Moreover, its own internal finite variable hierarchy turns out to work well. Finally, we shall make another move. The above analogy works both ways. Modal operators are like quantifiers, but quantifiers are also like modal operators. This observation inspires a generalized semantics for first-order predicate logic with accessibility constraints on available assignments (cf. N´emeti 1986, 1992) which moves the earlier quantifier restrictions into the semantics. This provides a fresh look at the landscape of possible predicate logics, including candidates sharing various desirable features with basic modal logic – in particular, its decidability. (shrink)

The author here constructs a system of simple type theory in which the type hierarchy does not extend merely to any finite height, but to an infinite height; this added part allows him to prove the existence of infinite sets within the theory, instead of taking it as an axiom in the usual simple type theory. The system has been presented in such sufficient generality so as to make it able to accommodate current scientific theories; the author has (...) turned in the direction of using type theory rather than set theory as the underlying logic of scientific theories. The system is formalized in Church's lambda-calculus notation; the semantics of the system are treated in great detail and appear to be the most complete study so far in print. The system is shown to contain at each type a "basic logic" somewhat similar to first-order logic; the author also shows that Peano's axioms for arithmetic appear as theorems when cast in suitable form. This book is one of a number of recent studies of type theory; together they represent a revival of interest in the subject, both as a foundation for mathematics and as an object of interest in itself. The book stems from Andrews' Princeton doctoral thesis.—P. J. M. (shrink)

The main result of the present paper is that the variable-free fragment of logic K*, the logic with a single K-style modality and its “reflexive and transitive closure,” is EXPTIMEcomplete. It is then shown that this immediately gives EXPTIME-completeness of variable-free fragments of a number of known EXPTIME-complete logics. Our proof contains a general idea of how to construct a polynomial-time reduction of a propositional logic to its n-variable—and even, in the cases of K*, PDL, CTL, ATL, (...) and some others, variable-free—fragments. Complexity of countermodels for such fragments is considered. (shrink)

This article defines a hierarchy on the hereditarily finite sets which reflects the way sets are built up from the empty set by repeated adjunction, the addition to an already existing set of a single new element drawn from the already existing sets. The structure of the lowest levels of this hierarchy is examined, and some results are obtained about the cardinalities of levels of the hierarchy.

We consider Borel sets of finite rank $A \subseteq\Lambda^\omega$ where cardinality of Λ is less than some uncountable regular cardinal K. We obtain a "normal form" of A, by finding a Borel set Ω, such that A and Ω continuously reduce to each other. In more technical terms: we define simple Borel operations which are homomorphic to ordinal sum, to multiplication by a countable ordinal, and to ordinal exponentiation of base K, under the map which sends every Borel set (...) A of finite rank to its Wadge degree. (shrink)

We consider two‐variable, first‐order logic in which a single distinguished predicate is required to be interpreted as a transitive relation. We show that the finite satisfiability problem for this logic is decidable in triply exponential non‐deterministic time. Complexity falls to doubly exponential non‐deterministic time if the transitive relation is constrained to be a partial order.

Shoenfield [8] has shown that a hierarchy for the functions recursive in a type-2 object can be set up whenever E2 (the type-2 object that introduces numerical quantification) is recursive in that type-2 object. With a restriction that we will discuss in the next paragraph, Moschovakis [4, pp. 254–259] has solved the analogous problem for type-3 objects. His method seems to generalize for any type-n object, where n ≥ 2. We will solve this same problem of finding hierarchies based (...) on type-n objects by a different method. Instead of using ordinal notations for indexing stages of hierarchies, as do Shoenfield and Moschovakis, we will define notation-independent stages. (shrink)

For every finite n ≥ 4 there is a logically valid sentence φ n with the following properties: φ n contains only 3 variables (each of which occurs many times); φ n contains exactly one nonlogical binary relation symbol (no function symbols, no constants, and no equality symbol): φ n has a proof in first-order logic with equality that contains exactly n variables, but no proof containing only n - 1 variables. This result was first proved using the machinery (...) of algebraic logic developed in several research monographs and papers. Here we replicate the result and its proof entirely within the realm of (elementary) first-order binary predicate logic with equality. We need the usual syntax, axioms, and rules of inference to show that φ n has a proof with only n variables. To show that φ n has no proof with only n - 1 variables we use alternative semantics in place of the usual, standard, set-theoretical semantics of first-order logic. (shrink)

We show that the structure R of recursively enumerable degrees is not a Σ₁-elementary substructure of Dn, where Dn (n > 1) is the structure of n-r.e. degrees in the Ershov hierarchy.

We prove that the existence of atomic models for countable atomic theories does not hold for Ln the first order logic restricted to n variables for finite n > 2. Our proof is algebraic, via polyadic algebras. We note that Lnhas been studied in recent times as a multi-modal logic with applications in computer science. 2000 MATHEMATICS SUBJECT CLASSIFICATION. 03C07, 03G15.

J. D. Monk has shown that for first order languages with finitely many variables there is no finite set of schema which axiomatizes the universally valid formulas. There are such finite sets of schema which axiomatize the formulas valid in all structures of some fixed finite size.

Traditional portfolio selection models mainly obtain the optimized portfolio ratio by focusing on the prices of financial products. However, investors’ multiple preferences and risk appetites are also significant factors that should be taken into account. In consideration of these two factors simultaneously, we propose a double-hierarchy model in this paper. Specifically, the first hierarchy quantifies investors’ risk appetite based on a historical simulation method and probabilistic preference theory. This hierarchy can be utilized to describe investors’ variable (...) risk appetites and ensure the obtained investment ratios meet investors’ immediate risk requirements. Then, using the cross-efficiency evaluation principle, the optimal investment ratios can be derived by fusing investors’ multiple preferences and risk appetites in the second hierarchy. Lastly, an illustrative example about evaluating the 10 largest capitalized stocks on the Shenzhen Stock Exchange is given to verify the feasibility and effectiveness of our newly proposed model. We make the theoretical contribution to improve the traditional portfolio selection model, especially considering investors’ subjective preferences and risk appetite. Moreover, the proposed model can be practical for assisting investors with their investment strategies in real life. (shrink)

This article argues that the English-language nonsense words “foo,” “bar,” “baz,” and others in a more or less standardized sequence of so-called metasyntactic variables commonly used in computer programming ought to be understood as meta-abstractive, re-representing a linguistically derived code’s abstraction of language and the abstraction of the programming language hierarchy itself, making it legible in a manner that rewards culturally oriented study: for example, of programming as a culture and of cultures of software development or engineering.

This article argues that the English-language nonsense words “foo,” “bar,” “baz,” and others in a more or less standardized sequence of so-called metasyntactic variables commonly used in computer programming ought to be understood as meta-abstractive, re-representing a linguistically derived code’s abstraction of language and the abstraction of the programming language hierarchy itself, making it legible in a manner that rewards culturally oriented study: for example, of programming as a culture and of cultures of software development or engineering.

This article argues that the English-language nonsense words “foo,” “bar,” “baz,” and others in a more or less standardized sequence of so-called metasyntactic variables commonly used in computer programming ought to be understood as meta-abstractive, re-representing a linguistically derived code’s abstraction of language and the abstraction of the programming language hierarchy itself, making it legible in a manner that rewards culturally oriented study: for example, of programming as a culture and of cultures of software development or engineering.

This article argues that the English-language nonsense words “foo,” “bar,” “baz,” and others in a more or less standardized sequence of so-called metasyntactic variables commonly used in computer programming ought to be understood as meta-abstractive, re-representing a linguistically derived code’s abstraction of language and the abstraction of the programming language hierarchy itself, making it legible in a manner that rewards culturally oriented study: for example, of programming as a culture and of cultures of software development or engineering.

We prove that if f is a partial Borel function from one Polish space to another, then either f can be decomposed into countably many partial continuous functions, or else f contains the countable infinite power of a bijection that maps a convergent sequence together with its limit onto a discrete space. This is a generalization of a dichotomy discovered by Solecki for Baire class 1 functions. As an application, we provide a characterization of functions which are countable unions of (...) continuous functions with domains of type Πn0, for a fixed n<ω. For Baire class 1 functions, this generalizes analogous characterizations proved by Jayne and Rogers for n=1 and Semmes for n=2. (shrink)

The question whether Frege’s theory of indirect reference enforces an infinite hierarchy of senses has been hotly debated in the secondary literature. Perhaps the most influential treatment of the issue is that of Burge (1979), who offers an argument for the hierarchy from rather minimal Fregean assumptions. I argue that this argument, endorsed by many, does not itself enforce an infinite hierarchy of senses. I conclude that whether or not the theory of indirect reference can avail itself (...) of only finitely many senses is pending further theoretical development. (shrink)

We introduce and study hierarchies of extensions of the propositional modal and temporal languages with pairs of new syntactic devices: point of reference-reference pointer which enable semantic references to be made within a formula. We propose three different but equivalent semantics for the extended languages, discuss and compare their expressiveness. The languages with reference pointers are shown to have great expressive power (especially when their frugal syntax is taken into account), perspicuous semantics, and simple deductive systems. For instance, Kamp's and (...) Stavi's temporal operators, as well as nominals (names, clock variables), are definable in them. Universal validity in these languages is proved undecidable. The basic modal and temporal logics with reference pointers are uniformly axiomatized and a strong completeness theorem is proved for them and extended to some classes of their extensions. (shrink)

Hierarchies abound to help us organize our world. A hierarchy places items into a general order, where more ‘general’ is also more ‘abstract’. The etymology of hierarchy is grounded in notions of religious and social rank. This article, after a historical review, focuses on knowledge systems, an interloper of the term hierarchy since at least the 1800s. Hierarchies in knowledge systems include taxonomies, classification systems, or thesauri in information science, and systems for representing information and knowledge to (...) computers, notably ontologies and knowledge representation languages. Hierarchies are the logical underpinning of inference and reasoning in these systems, as well as the scaffolding for classification and inheritance. Hierarchies in knowledge systems express subsumption relations that have flexible variants, which we can represent algorithmically, and thus computationally. This article dissects that variability, leading to a proposed typology of hierarchies useful to knowledge systems. The article argues through a perspective informed by Charles Peirce that natural hierarchies are real, can be logically determined, and are the appropriate basis for knowledge systems. Description logics and semantic language standards reflect this perspective, importantly through their open-world logic and vocabularies for generalized subsumption hierarchies. Recent research suggests possible mechanisms for the emergence of natural hierarchies. (shrink)

The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity type t there is a generalized quantifier of type t which is not definable in the extension of first order logic by all generalized quantifiers of type smaller than t. This was proved for unary similarity types by Per Lindström [17] (...) with a counting argument. We extend his method to arbitrary similarity types. (shrink)

We establish a general hierarchy theorem for quantifier classes in the infinitary logic L∞ωωon finite structures. In particular, it is shown that no infinitary formula with bounded number of universal quantifiers can express the negation of a transitive closure.This implies the solution of several open problems in finite model theory: On finite structures, positive transitive closure logic is not closed under negation. More generally the hierarchy defined by interleaving negation and transitive closure operators is strict. (...) This proves a conjecture of Immerman.We also separate the expressive power of several extensions of Datalog, giving new insight in the fine structure of stratified Datalog. (shrink)

Many logics considered in finite model theory have a natural notion of an arity. The purpose of this article is to study the hierarchies which are formed by the fragments of such logics whose formulae are of bounded arity.Based on a construction of finite graphs with a certain property of homogeneity, we develop a method that allows us to prove that the arity hierarchies are strict for several logics, including fixed-point logics, transitive closure logic and its deterministic version, (...) variants of the database language Datalog, and extensions of first-order logic by implicit definitions.Furthermore, we show that all our results already hold on the class of finite graphs. (shrink)

We continue the exploration of various aspects of divisibility of ultrafilters, adding one more relation to the picture: multiplicative finite embeddability. We show that it lies between divisibility relations \ and \. The set of its minimal elements proves to be very rich, and the \-hierarchy is used to get a better intuition of this richness. We find the place of the set of \-maximal ultrafilters among some known families of ultrafilters. Finally, we introduce new notions of largeness (...) of subsets of \, and compare it to other such notions, important for infinite combinatorics and topological dynamics. (shrink)

The problem of adaptive finite-time fault-tolerant control and output constraints for a class of uncertain nonlinear half-vehicle active suspension systems are investigated in this work. Markovian variables are used to denote in terms of different random actuators failures. In adaptive backstepping design procedure, barrier Lyapunov functions are adopted to constrain vertical motion and pitch motion to suppress the vibrations. Unknown functions and coefficients are approximated by the neural network. Assisted by the stochastic practical finite-time theory and FTC theory, (...) the proposed controller can ensure systems achieve stability in a finite time. Meanwhile, displacement and pitch angle in systems would not violate their maximum values, which imply both ride comfort and safety have been enhanced. In addition, all the signals in the closed-loop systems can be guaranteed to be semiglobal finite-time stable in probability. The simulation results illustrate the validity of the established scheme. (shrink)

Our concern is the axiomatisation problem for modal and algebraic logics that correspond to various fragments of two-variable first-order logic with counting quantifiers. In particular, we consider modal products with Diff, the propositional unimodal logic of the difference operator. We show that the two-dimensional product logic $Diff \times Diff$ is non-finitely axiomatisable, but can be axiomatised by infinitely many Sahlqvist axioms. We also show that its ‘square’ version (the modal counterpart of the substitution and equality free fragment of two- (...) class='Hi'>variable first-order logic with counting to two) is non-finitely axiomatisable over $Diff \times Diff$ , but can be axiomatised by adding infinitely many Sahlqvist axioms. These are the first examples of products of finitely axiomatisable modal logics that are not finitely axiomatisable, but axiomatisable by explicit infinite sets of canonical axioms. (shrink)

Social workers frequently encounter ethical dilemmas in their daily practice. This paper examines the utility of hierarchies of ethical principles as tools for ethical decision making. Because of limited research on this topic, the degree of agreement on ordering of ethical principles is unknown. This paper presents illustrative data that suggest variability in individual hierarchies and priorities, which may depend on the circumstances of a situation. Recommendations for using hierarchies of ethical principles in social work education and practice are discussed (...) and a detailed example of how different hierarchies may lead to making different decisions is provided. (shrink)

The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity typetthere is a generalized quantifier of typetwhich is not definable in the extension of first order logic by all generalized quantifiers of type smaller thant. This was proved for unary similarity types by Per Lindström [17] with a counting argument. We (...) extend his method to arbitrary similarity types. (shrink)

A previous work by Friedman et al. (Theory and Decision, 61:305–318, 2006) introduces the concept of a hierarchy of a simple voting game and characterizes which hierarchies, induced by the desirability relation, are achievable in linear games. In this paper, we consider the problem of determining all hierarchies, conserving the ordinal equivalence between the Shapley–Shubik and the Penrose–Banzhaf–Coleman power indices, achievable in simple games. It is proved that only four hierarchies are non-achievable in simple games. Moreover, it is also (...) proved that all achievable hierarchies are already obtainable in the class of weakly linear games. Our results prove that given an arbitrary complete pre-ordering defined on a finite set with more than five elements, it is possible to construct a simple game such that the pre-ordering induced by the Shapley–Shubik and the Penrose–Banzhaf–Coleman power indices coincides with the given pre-ordering. (shrink)

The present study addresses the fluid transport behaviour of the flow of gold -copper /biomagnetic blood hybrid nanofluid in an inclined irregular stenosis artery as a consequence of varying viscosity and Lorentz force. The nonlinear flow equations are transformed into dimensionless form by using nonsimilar variables. The finite-difference technique is involved in computing the nonlinear transport dimensionless equations. The significant parameters like angle parameter, the Hartmann number, changing viscosity, constant heat source, the Reynolds number, and nanoparticle volume fraction on (...) the flow field are exhibited through figures. Present results disclose that the Lorentz force strongly lessens the hybrid nanofluid velocity. Elevating the Grashof number values enhances the rate of blood flow. Growing values of the angle parameter cause to reduce the resistance impedance on the wall. Hybrid nanoparticles have a superior wall shear stress than copper nanoparticles. The heat transfer rate is amplifying at the axial direction with the growing values of nanoparticles concentration. The applied Lorentz force significantly reduces the hybrid and unitary nanofluid flow rate in the axial direction. The hybrid nanoparticles expose a supreme rate of heat transfer than the copper nanoparticles in a blood base fluid. Compared to hybrid and copper nanofluid, the blood base fluid has a lower temperature. (shrink)

For a Euclidean space , let L n denote the modal logic of chequered subsets of . For every n 1, we characterize L n using the more familiar Kripke semantics, thus implying that each L n is a tabular logic over the well-known modal system Grz of Grzegorczyk. We show that the logics L n form a decreasing chain converging to the logic L of chequered subsets of . As a result, we obtain that L is also a logic (...) over Grz, and that L has the finite model property. We conclude the paper by extending our results to the modal language enriched with the universal modality. (shrink)

This book gives a comprehensive overview of central themes of finite model theory – expressive power, descriptive complexity, and zero-one laws – together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of and hierarchies within first-order, second-order, fixed-point, and (...) infinitary logics to gain insight into phenomena in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissé pebble game, as a powerful way to analyze the expressive power of such logics, and illustrates how deep notions from model theory and combinatorics, such as o-minimality and treewidth, arise naturally in the application of finite model theory to database theory and AI. Students of logic and computer science will find here the tools necessary to embark on research into finite model theory, and all readers will experience the excitement of a vibrant area of the application of logic to computer science. (shrink)