We prove that the two-variable fragment of first-order logic has the weak Beth definability property. This makes the two-variable fragment a natural logic separating the weak and the strong Beth properties since it does not have the strong Beth definability property.

It is a classical result of Mortimer that $L^2$ , first-order logic with two variables, is decidable for satisfiability. We show that going beyond $L^2$ by adding any one of the following leads to an undecidable logic:– very weak forms of recursion, viz.¶(i) transitive closure operations¶(ii) (restricted) monadic fixed-point operations¶– weak access to cardinalities, through the Härtig (or equicardinality) quantifier¶– a choice construct known as Hilbert's $\epsilon$ -operator.In fact all these extensions of $L^2$ prove to be undecidable both (...) for satisfiability, and for satisfiability in finite structures. Moreover most of them are hard for $\Sigma^1_1$ , the first level of the analytical hierachy, and thus have a much higher degree of undecidability than first-order logic. (shrink)

We show that the existential preservation theorem fails for two-variable first-order logic FO2. It is known that for all k ≥ 3, FOk does not have an existential preservation theorem, so this settles the last open case, answering a question of Andreka, van Benthem, and Németi. In contrast, we prove that the homomorphism preservation theorem holds for FO2.

The satisfiability problem for the two-variable fragment of first-order logic is investigated over finite and infinite linearly ordered, respectively wellordered domains, as well as over finite and infinite domains in which one or several designated binary predicates are interpreted as arbitrary wellfounded relations. It is shown that FO 2 over ordered, respectively wellordered, domains or in the presence of one well-founded relation, is decidable for satisfiability as well as for finite satisfiability. Actually the complexity of these decision problems (...) is essentially the same as for plain unconstrained FO 2 , namely non-deterministic exponential time. In contrast FO 2 becomes undecidable for satisfiability and for finite satisfiability, if a sufficiently large number of predicates are required to be interpreted as orderings, wellorderings, or as arbitrary wellfounded relations. This undecidability result also entails the undecidability of the natural common extension of FO 2 and computation tree logic CTL. (shrink)

We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n -universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n-universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

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.

Consider the bounded variable logics $L^k_{\infty\omega}$ (with k variable symbols), and $C^k_{\infty\omega}$ (with k variables in the presence of counting quantifiers $\exists^{\geq m}$ ). These fragments of infinitary logic $L_{\infty\omega}$ are well known to provide an adequate logical framework for some important issues in finite model theory. This paper deals with a translation that associates equivalence of structures in the k-variable fragments with bisimulation equivalence between derived structures. Apart from a uniform and intuitively appealing treatment of (...) these equivalences, this approach relates some interesting issues for the case of an arbitrary number of variables to the case of just three variables. Invertibility of the invariants for $\equiv_{C^3}$ , in particular, would imply a positive answer to the tempting conjecture that fixed-point logic with counting captures $\bigcup_k$ Ptime $\cap C^k_{\infty\omega}$. (shrink)

Controlled languages are regimented fragments of natural languagedesigned to make the processing of natural language more efficient andreliable. This paper defines a controlled language, E2V, whose principalgrammatical resources include determiners, relative clauses, reflexivesand pronouns. We provide a formal syntax and semantics for E2V, in whichanaphoric ambiguities are resolved in a linguistically natural way. Weshow that the expressive power of E2V is equal to that of thetwo-variable fragment of first-order logic. It follows that the problemof determining the satisfiability of (...) a set of E2V sentences is NEXPTIMEcomplete. We show that E2V can be extended in various ways withoutcompromising these complexity results; however, relaxing our policy onanaphora resolution renders the satisfiability problem for E2Vundecidable. Finally, we argue that our results have a bearing on thebroader philosophical issue of the relationship between natural andformal languages. (shrink)

The satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when counting quantifiers are coded succinctly.

We prove that the two-variable fragment of first-order intuitionistic logic is undecidable, even without constants and equality. We also show that the two-variable fragment of a quantified modal logic L with expanding first-order domains is undecidable whenever there is a Kripke frame for L with a point having infinitely many successors (such are, in particular, the first-order extensions of practically all standard modal logics like K, K4, GL, S4, S5, K4.1, S4.2, GL.3, etc.). For many quantified (...) modal logics, including those in the standard nomenclature above, even the monadic two-variable fragments turn out to be undecidable. (shrink)

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.

We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a (...) finite model. Moreover, Mortimer showed that every satisfiable FO 2 -sentence has a model whose size is at most doubly exponential in the size of the sentence. In this paper, we improve Mortimer's bound by one exponential and show that every satisfiable FO 2 -sentence has a model whose size is at most exponential in the size of the sentence. As a consequence, we establish that the satisfiability problem for FO 2 is NEXPTIME-complete. (shrink)

We prove that the positive fragment of first-order intuitionistic logic in the language with two individual variables and a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable. This holds true regardless of whether we consider semantics with expanding or constant domains. We then generalise this result to intervals \ and \, where QKC is the logic of the weak law of the excluded middle and QBL and QFL are first-order counterparts of Visser’s basic and (...) formal logics, respectively. We also show that, for most “natural” first-order modal logics, the two-variable fragment with a single monadic predicate letter, without functional symbols, constants, and equality, is undecidable, regardless of whether we consider semantics with expanding or constant domains. These include all sublogics of QKTB, QGL, and QGrz—among them, QK, QT, QKB, QD, QK4, and QS4. (shrink)

We study first-order logic with two variables FO² and establish a small substructure property. Similar to the small model property for FO² we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be infinite. We apply this technique to analyse the satisfiability problem for FO² under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO² has the finite model property and is complete for (...) non-deterministic exponential time, just as for plain FO² With two equivalence relations, FO² does not have the finite model property, but is shown to be decidable via a construction of regular models that admit finite descriptions even though they may necessarily be infinite. For three or more equivalence relations, FO² is undecidable. (shrink)

The aim of this paper is to give a new proof for the decidability and finite model property of first-order logic with two variables (without function symbols), using a combinatorial theorem due to Herwig. The results are proved in the framework of polyadic equality set algebras of dimension two (Pse 2 ). The new proof also shows the known results that the universal theory of Pse 2 is decidable and that every finite Pse 2 can be represented on a (...) finite base. Since the class Cs 2 of cylindric set algebras of dimension 2 forms a reduct of Pse 2 , these results extend to Cs 2 as well. (shrink)

The aim of this paper is to give a new proof for the decidability and finite model property of first-order logic with two variables, using a combinatorial theorem due to Herwig. The results are proved in the framework of polyadic equality set algebras of dimension two. The new proof also shows the known results that the universal theory of Pse$_2$ is decidable and that every finite Pse$_2$ can be represented on a finite base. Since the class Cs$_2$ of cylindric (...) set algebras of dimension 2 forms a reduct of Pse$_2$, these results extend to Cs$_2$ as well. (shrink)

A constructive proof is given which shows that every nonrecursive r.e. many-one degree is represented by the family of decision problems for partial implicational propositional calculi whose well-formed formulas contain at most two distinct variable symbols.

We consider infinitary logic with only two variable symbols, both with and without counting quantifiers, i.e. L2 L∞ω2 and C2 L∞ω2mεω. The main result is that finite relational structures admit canonization with respect to L2 and C2: there are polynomial time com putable functors mapping finite relational structures to unique representatives of their equivalence class with respect to indistinguishability in either of these logics. In fact we exhibit in verses to the natural invariants that characterize structures up to (...) L2- or C2-equivalence, respectively. As a corollary we obtain recursive presentations of the classes of all boolean queries that are closed with respect to L2- or C2-equivalence. (shrink)

The essay introduces a non-Diodorean, non-Kantian temporal modal semantics based on part-whole, rather than class, theory. Formalizing Edmund Husserl’s theory of inner time consciousness, §3 uses his protention and retention concepts to define a relation of self-awareness on intentional events. §4 introduces a syntax and two-valued semantics for modal first-order predicate object-languages, defines semantic assignments for variables and predicates, and truth for formulae in terms of the axiomatic version of Edmund Husserl’s dependence ontology (viz. the Calculus [CU] of Urelements) introduced (...) by The Ontology of Intentionality I & II. It then uses the §3 results to define the modalities of truth, and §5 extends the semantics to identity claims. §6 defines and contrasts synthetic a priori truths to analytic a priori truths, and §7 compares Brentano School noetic semantic and Leibnizian possible-world semantic perspectives on modality. The essay argues that the modal logics it defines semantically are two-valued, first-order versions of the type of language which Husserl viewed as the language of any ontology of experience (i.e. of any science), and conceived as the logic of intentionality. (shrink)

Here I show that the one-variable fragment of several first-order relevant logics corresponds to certain S5ish extensions of the underlying propositional relevant logic. In particular, given a fairly standard translation between modal and one-variable languages and a permuting propositional relevant logic L, a formula $$\mathcal {A}$$ A of the one-variable fragment is a theorem of LQ (QL) iff its translation is a theorem of L5 (L.5). The proof is model-theoretic. In one direction, semantics based on (...) the Mares-Goldblatt [15] semantics for quantified L are transformed into ternary (plus two binary) relational semantics for S5-like extensions of L (for a general presentation, see Seki [26, 27]). In the other direction, a valuation is given for the full first-order relevant logic based on L into a model for a suitable S5 extension of L. I also discuss this work’s relation to finding a complete axiomatization of the constant domain, non-general frame ternary relational semantics for which RQ is incomplete [11]. (shrink)

Jörg Hansen, John Horty, and Xavier Parent and Leendert van der Torre have all recently described some sort of nonmonotonic logic to model reasons and their interactions. Horty’s framework is broader in scope than the other two, encompassing both reasoning about the relative strengths of reasons and reasoning about which reasons to consider in the first place. Hansen discusses a plethora of approaches and examples, including Horty’s, arguing that his preferred system best captures our intuitions. And Parent and van (...) der Torre present a family of systems of input/output logic, which are in some ways the most flexible. In this paper, I aim to combine these features. Without attempting to answer the question of which intuitions are the best to capture, I first argue that there are good reasons to explore systems that behave more like Hansen’s than Horty’s. I then show that Parent and van der Torre’s framework of input/output logic can exactly duplicate Hansen’s system but is flexible enough to produce other results as well. Finally, I extend their framework to include the additional kinds of reasoning Horty discusses, showing that the resulting theory can handle a wider range of cases than Horty’s. (shrink)

We are used to the idea that computers operate on numbers, yet another kind of data is equally important: the syntax of formal languages, with variables, binding, and alpha-equivalence. The original application of nominal techniques, and the one with greatest prominence in this paper, is to reasoning on formal syntax with variables and binding. Variables can be modelled in many ways: for instance as numbers (since we usually take countably many of them); as links (since they may `point' to a (...) binding site in the term, where they are bound); or as functions (since they often, though not always, represent `an unknown'). None of these models is perfect. In every case for the models above, problems arise when trying to use them as a basis for a fully formal mechanical treatment of formal language. The problems are practical—but their underlying cause may be mathematical. The issue is not whether formal syntax exists, since clearly it does, so much as what kind of mathematical structure it is. To illustrate this point by a parody, logical derivations can be modelled using a Gödel encoding (i.e., injected into the natural numbers). It would be false to conclude from this that proof-theory is a branch of number theory and can be understood in terms of, say, Peano's axioms. Similarly, as it turns out, it is false to conclude from the fact that variables can be encoded e.g., as numbers, that the theory of syntax-with-binding can be understood in terms of the theory of syntax-without-binding, plus the theory of numbers (or, taking this to a logical extreme, purely in terms of the theory of numbers). It cannot; something else is going on. What that something else is, has not yet been fully understood. In nominal techniques, variables are an instance of names, and names are data. We model names using urelemente with properties that, pleasingly enough, turn out to have been investigated by Fraenkel and Mostowski in the first half of the 20th century for a completely different purpose than modelling formal language. What makes this model really interesting is that it gives names distinctive properties which can be related to useful logic and programming principles for formal syntax. Since the initial publications, advances in the mathematics and presentation have been introduced piecemeal in the literature. This paper provides in a single accessible document an updated development of the foundations of nominal techniques. This gives the reader easy access to updated results and new proofs which they would otherwise have to search across two or more papers to find, and full proofs that in other publications may have been elided. We also include some new material not appearing elsewhere. (shrink)

The aim of this paper is to apply a general methodology for constructing statistical methods, which is based on decision theory, to give a statistical description of preferential rankings, with a focus on the rankings’ dependence on categorical variables. In the paper, I use functions of description errors that are based on the Kemeny and Hamming distances between preferential orderings, but the proposed methodology can also be applied to other methods of estimating description errors.

As is well known, the variable-sharing property (vsp) is, according to Anderson and Belnap, a necessary property of any relevant logic. In this paper, we shall consider two versions of the vsp, what we label the "weak vsp" (wvsp) and the "strong vsp" (svsp). In addition, the "no loose pieces property," a property related to the wvsp and the svsp, will be defined. Each one of these properties shall generally be characterized by means of a class of logical (...) matrices. In this way, any logic verified by an actual matrix in one of these classes has the property the class generally represents. Particular matrices (and so, logics) in each class are provided. (shrink)

A common reaction to Hegel’s suggestion that we collapse Kant’s distinction between form and content is that, since such a move would also deprive us of any way of distinguishing the merely logical from the real possibility of our concepts, it is incoherent and ought to be rejected. It is true that these two distinctions are intimately related in Kant, such that if one goes, the other does as well. But it is less obvious that giving them up as Kant (...) conceives them is as incoherent a proposal as many of Hegel’s critics think. It has been the point of a recent account of Hegel’s idealism to demonstrate that his critique of Kant’s dichotomy between form and content or concept and intuition does not commit him to the view that human cognition is materially creative of its content in the manner of a God-like or intuitive intellect—does not, in other words, signify a return to a pre-Critical metaphysics. This is the interpretative stance I adopt here as well, in hope of giving defenders of Kant reasons for taking Hegel more seriously. (shrink)

We show the first examples of recursively enumerable (even decidable) two-dimensional products of finitely axiomatisable modal logics that are not finitely axiomatisable. In particular, we show that any axiomatisation of some bimodal logics that are determined by classes of product frames with linearly ordered first components must be infinite in two senses: It should contain infinitely many propositional variables, and formulas of arbitrarily large modal nesting-depth.

In [60] N. Belnap presented an 8-element matrix for the relevant logic R with the following property: if in an implication A → B the formulas A and B do not have a common variable then there exists a valuation v such that v(A → B) does not belong to the set of designated elements of this matrix. A 6-element matrix of this kind can be found in: R. Routley, R.K. Meyer, V. Plumwood and R.T. Brady [82]. Below (...) we prove that the logics generated by these two matrices are the only maximal extensions of the relevant logic R which have the relevance property: if A → B is provable in such a logic then A and B have a common propositional variable. (shrink)

We argue that some sign language loci (i.e. positions in signing space that realize discourse referents) are both formal variables and simplified representations of what they denote; in other words, they are simultaneously logical symbols and pictorial representations. We develop a 'formal semantics with iconicity' that accounts for their dual life; the key idea ('formal iconicity') is that some geometric properties of signs must be preserved by the interpretation function. We analyze in these terms three kinds of iconic effects in (...) American and French Sign Language (ASL and LSF): (i) structural iconicity, where relations of inclusion and complementation among loci are directly reflected in their denotations; (ii) locus-external iconicity, where the high or low position of a locus in signing space has a direct semantic reflex, akin to the semantic contribution of gender features of pronouns; and (iii) locus-internal iconicity, where different parts of a structured locus are targeted by different directional verbs, as was argued by Liddell and Kegl. The resulting semantics combines insights of two traditions that have been sharply divided by recent debates. In line with the 'formalist camp' (e.g. Lillo-Martin and Klima, Neidle, and Sandler and Lillo-Martin), our theory treats loci as variables, and develops an explicit formal analysis of their behavior. But we also incorporate insights of the 'iconic camp', which emphasized the role of iconic constraints in sign language in general and in pronominals in particular (e.g. Cuxac, Taub, Liddell). However, this synthesis is only possible if formal semantics makes provisions for iconic requirements at the very core of its interpretive procedure. (An Appendix discusses relevant data from Italian Sign Language [LIS].). (shrink)

We argue that the extant evidence for Stoic logic provides all the elements required for a variable-free theory of multiple generality, including a number of remarkably modern features that straddle logic and semantics, such as the understanding of one- and two-place predicates as functions, the canonical formulation of universals as quantified conditionals, a straightforward relation between elements of propositional and first-order logic, and the roles of anaphora and rigid order in the regimented sentences that express multiply (...) general propositions. We consider and reinterpret some ancient texts that have been neglected in the context of Stoic universal and existential propositions and offer new explanations of some puzzling features in Stoic logic. Our results confirm that Stoic logic surpasses Aristotle’s with regard to multiple generality, and are a reminder that focusing on multiple generality through the lens of Frege-inspired variable-binding quantifier theory may hamper our understanding and appreciation of pre-Fregean theories of multiple generality. (shrink)

This paper discusses the problems of an ontological value of the variable in Russell’s philosophy. The variable is essential in Russell’s theory of denotation, which among other things, purports to prove Meinongian being outside of subsistence and existence to be logically unnecessary. I argue that neither Russell’s epistemology nor his ontology can account for the ontological value of the variable without running into qualities of Meinongian being that Russell disputed. The problem is that the variable cannot (...) be logically grounded by Russell’s theory of denotation. As such, in so far as being is concerned, Meinong and Russell’s theories are much closer than is typically thought. The arguments are supported with concerns raised by Russell, Frege, and Moore regarding the ontological value of the variable. The problem can be summarised as follows: the variable is the fundamental denoting-position of a formal theory that is meant to explain the structure of the ontological. If such a formal theory is meant to ground the ontological, then the formal must also represent the actual structure of the ontological. Yet the variable, the fundamental symbol of denotation in a theory that defines objects, is ontologically indefinable. (shrink)

We analyze the logical form of the domain knowledge that grounds analogical inferences and generalizations from a single instance. The form of the assumptions which justify analogies is given schematically as the "determination rule", so called because it expresses the relation of one set of variables determining the values of another set. The determination relation is a logical generalization of the different types of dependency relations defined in database theory. Specifically, we define determination as a relation between schemata of first (...) order logic that have two kinds of free variables: (1) object variables and (2) what we call "polar" variables, which hold the place of truth values. Determination rules facilitate sound rule inference and valid conclusions projected by analogy from single instances, without implying what the conclusion should be prior to an inspection of the instance. They also provide a way to specify what information is sufficiently relevant to decide a question, prior to knowledge of the answer to the question. (shrink)

In the propositional modal treatment of two-variable first-order logic equality is modelled by a ‘diagonal’ constant, interpreted in square products of universal frames as the identity relation. Here we study the decision problem of products of two arbitrary modal logics equipped with such a diagonal. As the presence or absence of equality in two-variable first-order logic does not influence the complexity of its satisfiability problem, one might expect that adding a diagonal to product logics in general (...) is similarly harmless. We show that this is far from being the case, and there can be quite a big jump in complexity, even from decidable to the highly undecidable. Our undecidable logics can also be viewed as new fragments of first-order logic where adding equality changes a decidable fragment to undecidable. We prove our results by a novel application of counter machine problems. While our formalism apparently cannot force reliable counter machine computations directly, the presence of a unique diagonal in the models makes it possible to encode both lossy and insertion-error computations, for the same sequence of instructions. We show that, given such a pair of faulty computations, it is then possible to reconstruct a reliable run from them. (shrink)

For companies involved in the supply chain, proper warehousing management is crucial. Warehouse layout arrangement and operation play a critical role in a company’s ability to maintain and improve its competitiveness. Reducing costs and increasing efficiency are two of the most crucial warehousing goals. Deciding on the best warehouse layout is a remarkable optimization problem. This paper uses an optimization method to set bin allocations within an automated warehouse with particular characteristics. The warehouse’s initial layout and the automated platforms limit (...) the search and define the time required to move goods within the warehouse. With the help of historical data and the definition of the time needed to move goods, a mathematical model of warehouse operation was created. An optimization procedure based on the well-known Variable Neighbourhood Search algorithm is defined and applied to the problem. Experimental results demonstrate increments in the efficiency of warehousing operations. (shrink)

We consider a new fragment of first-order logic with two variables. This logic is defined over interval structures. It constitutes unary predicates, a binary predicate and a function symbol. Considering such a fragment of first-order logic is motivated by defining a general framework for event-based interval temporal logics. In this paper, we present a sound, complete and terminating decision procedure for this logic. We show that the logic is decidable, and provide a NEXPTIME complexity bound (...) for satisfiability. This result shows that even a simple decidable fragment of first-order logic has NEXPTIME complexity. (shrink)

Francesco Berto proposed a logic for imaginative episodes. The logic establishes certain (in)validities concerning episodic imagination. They are not all equally plausible as principles of episodic imagination. The logic also does not model that the initial input of an imaginative episode is deliberately chosen.Stit-imagination logic models the imagining agent’s deliberate choice of the content of their imagining. However, the logic does not model the episodic nature of imagination. The present paper combines the two logics, thereby (...) modelling imaginative episodes with deliberately chosen initial input. We use a combination ofstit-imagination logic and a content-sensitive variably strict conditional à la Berto, for which we give a Chellas–Segerberg semantics. The proposed semantics has the following advantages over Berto’s: (i) we model thedeliberate choiceof initial input of imaginative episodes (in a multi-agent setting), (ii) we showframe correspondencesfor axiomatic analogues of Berto’s validities, which (iii) allows thepossibility to disregard axiomsthat might be considered not plausible as principles concerning imaginative episodes. We do not take a definite stance on whether theseshouldbe disregarded but give reasons for why one might want to disregard them. Finally, we compare our semantics briefly with recent work, which aims to model voluntary imagination, and argue that our semantics models different aspects. (shrink)

Connectionist attention to variables has been too restricted in two ways. First, it has not exploited certain ways of doing without variables in the symbolic arena. One variable-avoidance method, that of logical combinators, is particularly well established there. Secondly, the attention has been largely restricted to variables in long-term rules embodied in connection weight patterns. However, short-lived bodies of information, such as sentence interpretations or inference products, may involve quantification. Therefore short-lived activation patterns may need to achieve the effect (...) of variables. The paper is mainly a theoretical analysis of some benefits and drawbacks of using logical combinators to avoid variables in short-lived connectionist encodings without loss of expressive power. The paper also includes a brief survey of some possible methods for avoiding variables other than by using combinators. (shrink)

This book constitutes the strictly refereed post-workshop proceedings of the 11th International Workshop on Computer Science Logic, CSL '97, held as the 1997 Annual Conference of the European Association on Computer Science Logic, EACSL, in Aarhus, Denmark, in August 1997. The volume presents 26 revised full papers selected after two rounds of refereeing from initially 92 submissions; also included are four invited papers. The book addresses all current aspects of computer science logics and its applications and thus presents (...) the state of the art in the area. (shrink)