Hilary Putnam has argued that computational functionalism cannot serve as a foundation for the study of the mind, as every ordinary open physical system implements every finite-state automaton. I argue that Putnam's argument fails, but that it points out the need for a better understanding of the bridge between the theory of computation and the theory of physical systems: the relation of implementation. It also raises questions about the class of automata that can serve as a basis for understanding (...) the mind. I develop an account of implementation, linked to an appropriate class of automata, such that the requirement that a system implement a given automaton places a very strong constraint on the system. This clears the way for computation to play a central role in the analysis of mind. (shrink)
Formal learning theory constitutes an attempt to describe and explain the phenomenon of learning, in particular of language acquisition. The considerations in this domain are also applicable in philosophy of science, where it can be interpreted as a description of the process of scientific inquiry. The theory focuses on various properties of the process of hypothesis change over time. Treating conjectures as informational states, we link the process of conjecture-change to epistemic update. We reconstruct and analyze the temporal aspect of (...) learning in the context of dynamic and temporal logics of epistemic change. We first introduce the basic formal notions of learning theory and basic epistemic logic. We provide a translation of the components of learning scenarios into the domain of epistemic logic. Then, we propose a characterization of finite identifiability in an epistemic temporal language. In the end we discuss consequences and possible extensions of our work. (shrink)
We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept of almost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, if L, L ′ are two logics and μ is an asymptotic measure on finite structures, then $\scr{L}\equiv _{\text{a.e.}}\scr{L}^{\prime}(\mu)$ means that there is a class C of finite structures (...) with μ (C)=1 and such that L and L ′ define the same queries on C. We carry out a systematic investigation of $\equiv _{\text{a.e.}}$ with respect to the uniform measure and analyze the $\equiv _{\text{a.e.}}$ -equivalence classes of several logics that have been studied extensively in finite model theory. Moreover, we explore connections with descriptive complexity theory and examine the status of certain classical results of model theory in the context of this new framework. (shrink)
This book is a rich collection of philosophical essays radically interrogating key notions and preoccupations of the phenomenological tradition. While using Heidegger’s Being and Time as its permanent point of reference and dispute, this collection also confronts other important philosophers, such as Kant, Nietzsche, and Derrida. The projects of these pivotal thinkers of finitude are relentlessly pushed to their extreme, with respect both to their unexpected horizons and to their as yet unexplored analytical potential. A Finite Thinking shows that, (...) paradoxically, where the thought of finitude comes into its own it frees itself, not only to reaffirm a certain transformed and transformative presence, but also for a non-religious reconsideration and reaffirmation of certain theologemes, as well as of the body, heart, and love. This book shows the literary dimension of philosophical discourse, providing important enabling ideas for scholars of literature, cultural theory, and philosophy. (shrink)
Recently, Paul Horwich has developed the minimalist theory of truth, according to which the truth predicate does not express a substantive property, though it may be used as a grammatical expedient. Minimalism shares these claims with Quine’s disquotationalism; it differs from disquotationalism primarily in holding that truth-bearers are propositions, rather than sentences. Despite potential ontological worries, allowing that propositions bear truth gives Horwich a prima facie response to several important objections to disquotationalism. In section I of this paper, disquotationalism is (...) given a careful exegesis, in which seven known objections are traced to the disquotational schema, and two new objections are raised. A version of disquotationalism which avoids two of the seven known objections is recommended. In section II, an examination of minimalism shows that it faces eight of the nine objections facing disquotationalism, plus a new objection. In section III, a finite formulation of minimalism proposed by Ernest Sosa is shown to meet five of the nine objections facing disquotationalism as well as the objection new to minimalism, though it faces another new objection. (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)
A system of semigroup identities is hereditarily finitely based if it defines a variety all semigroups of which are finitely based. Two new types of hereditarily finitely based identity systems are presented. Two of these systems, together with eight existing systems, establish the hereditary finite basis property of every semigroup of order five or less with one possible exception.
In this paper, I suggest that infinite numbers are large finite numbers, and that infinite numbers, properly understood, are 1) of the structure omega + (omega* + omega)Ө + omega*, and 2) the part is smaller than the whole. I present an explanation of these claims in terms of epistemic limitations. I then consider the importance, part of which is demonstrating the contradiction that lies at the heart of Cantorian set theory: the natural numbers are too large to be (...) counted by any finite number, but too small to be counted by any infinite number – there is no number of natural numbers. (shrink)
According to finite frequentism, the probability of an attribute A in a finite reference class B is the relative frequency of actual occurrences of A within B. I present fifteen arguments against this position.
We introduce insertion domains that support the placement of new, higher, vertices into finite trees. We prove that every nonincreasing insertion domain has an element with simple structural properties in the style of classical Ramsey theory. This result is proved using standard large cardinal axioms that go well beyond the usual axioms for mathematics. We also establish that this result cannot be proved without these large cardinal axioms. We also introduce insertion rules that specify the placement of new, higher, (...) vertices into finite trees. We prove that every insertion rule greedily generates a tree with these same structural properties; and every decreasing insertion rule generates (or admits) a tree with these same structural properties. It is also necessary and sufficient to use the same large cardinals (in the precise sense of Corollary D.25). The results suggest new areas of research in discrete mathematics called "Ramsey tree theory" and "greedy Ramsey theory" which demonstrably require more than the usual axioms for mathematics. (shrink)
Like many of his contemporaries, Hegel considered Spinoza a modern reviver of ancient Eleatic monism, in whose system “all determinate content is swallowed up as radically null and void”. This characterization of Spinoza as denying the reality of the world of finite things had a lasting influence on the perception of Spinoza in the two centuries that followed. In this article, I take these claims of Hegel to task and evaluate their validity. Although Hegel’s official argument for the unreality (...) of modes in Spinoza’s system will turn out to be unsound, I do believe there is one crucial line in Spinoza’s system – Spinoza’s rather weak and functional conception of individuality – which provides some support for Hegel’s reading of Spinoza. (shrink)
In this paper, I pursue such a logical foundation for arithmetic in a variant of Zermelo set theory that has axioms of subset separation only for quantifier-free formulae, and according to which all sets are Dedekind finite. In section 2, I describe this variant theory, which I call ZFin0. And in section 3, I sketch foundations for arithmetic in ZFin0 and prove that certain foundational propositions that are theorems of the standard Zermelian foundation for arithmetic are independent of ZFin0.<br><br>An (...) equivalent theory of sets and an equivalent foundation for arithmetic was introduced by John Mayberry and developed by the current author in his doctoral thesis. In that thesis, the independence results mentioned above are proved using proof-theoretic methods. In this paper, I offer model-theoretic proofs of the central independence results using the technique of cumulation models, which was introduced by Steve Popham, a doctoral student of Mayberry<br>from the early 1980s. (shrink)
The prospects and limitations of defining truth in a finite model in the same language whose truth one is considering are thoroughly examined. It is shown that in contradistinction to Tarskirs undefinability theorem for arithmetic, it is in a definite sense possible in this case to define truth in the very language whose truth is in question.
A system of finite mathematics is proposed that has all of the power of classical mathematics. I believe that finite mathematics is not committed to any form of infinity, actual or potential, either within its theories or in the metalanguage employed to specify them. I show in detail that its commitments to the infinite are no stronger than those of primitive recursive arithmetic. The finite mathematics of sets is comprehensible and usable on its own terms, without appeal (...) to any form of the infinite. That makes it possible to, without circularity, obtain the axioms of full Zermelo-Fraenkel Set Theory with the Axiom of Choice (ZFC) by extrapolating (in a precisely defined technical sense) from natural principles concerning finite sets, including indefinitely large ones. The existence of such a method of extrapolation makes it possible to give a comparatively direct account of how we obtain knowledge of the mathematical infinite. The starting point for finite mathematics is Mycielski's work on locally finite theories. (shrink)
According to finite frequentism, the probability of an attribute A in a finite reference class B is the relative frequency of actual occurrences of A within B. I present fifteen arguments against this position.
The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to the problem of (...) computational complexity of the Ramsey quantifier for which the phrase “A is big relatively to the universe” is interpreted as containing at least one representative of each equivalence class, for some given equvalence relation. In this work we consider quantifiers Rf, for which “A is big relatively to the universe” means “card(A) > f (n), where n is the size of the universe”. Following [Blass, Gurevich 1986] we call R mighty if Rx, yH(x, y) defines N P – complete class of finite models. Similarly we say that Rf is N P –hard if the corresponding class is N P –hard. We prove the following theorems. (shrink)
A geometrical interpretation of independence and exchangeability leads to understanding the failure of de Finetti's theorem for a finite exchangeable sequence. In particular an exchangeable sequence of length r which can be extended to an exchangeable sequence of length k is almost a mixture of independent experiments, the error going to zero like 1/k.
This article offers two commentaries on two of Félix Guattari's essays from Chaosmosis: ‘The New Aesthetic Paradigm’ and ‘Schizoanalytic Metamodelisation’. The first commentary attends specifically to how Guattari figures the infinite/finite relation in relation to what he calls the three Assemblages (pre-, extant, and post-capitalism) and then even more specifically to the mechanics of this relation – or folding – within the third ‘processual’ Assemblage or new aesthetic paradigm of the essay's title. The second commentary looks at what Guattari (...) has to say about this paradigm in relation to subjectivity, that is, the schizoanalytic programme or practice of metamodelling. Here the focus is on the turn to asignifying semiotics – but also the importance of signifying material and indeed the actual material scene of encounter – in any programme for the production of subjectivity (it is here also that the symptom makes its appearance). (shrink)
The paper concerns interpretations of the paraconsistent logic LP which model theories properly containing all the sentences of first order arithmetic. The paper demonstrates the existence of such models and provides a complete taxonomy of the finite ones.
Extending the ideas from (Hofer-Szabó and Rédei [2006]), we introduce the notion of causal up-to-n-closedness of probability spaces. A probability space is said to be causally up-to-n-closed with respect to a relation of independence R_ind iff for any pair of correlated events belonging to R_ind the space provides a common cause or a common cause system of size at most n. We prove that a finite classical probability space is causally up-to-3-closed w.r.t. the relation of logical independence iff its (...) probability measure is constant on the set of atoms of non-0 probability. (The latter condition is a weakening of the notion of measure uniformity.) Other independence relations are also considered. (shrink)
We study a class of finite models for the Lambek Calculus with additive conjunction and with and without empty antecedents. The class of models enables us to prove the finite model property for each of the above systems, and for some axiomatic extensions of them. This work strengthens the results of [3] where only product-free fragments of these systems are considered. A characteristic feature of this approach is that we do not rely on cut elimination in opposition to (...) e.g. [5], [9]. (shrink)
In [9] we introduced a new framework for asymptotic probabilities, in which a $\sigma-additive$ measure is defined on the sample space of all sequences $A = $ of finite models, where the universe of An is {1, 2, .., n}. In this framework we investigated the strong 0-1 law for sentences, which states that each sentence either holds in An eventually almost surely or fails in An eventually almost surely. In this paper we define the strong convergence law for (...) formulas, which carries over the ideas of the strong 0-1 law to formulas with free variables, and roughly states that for each formula φ(x), the fraction of tuples a in An, which satisfy the formula φ(x), almost surely has a limit as n tends to infinity. We show that the infinitary logic with finitely many variables has the strong convergence law for formulas for the uniform measure, and further characterize the measures on random graphs for which the strong convergence law holds. (shrink)
The partial cooperation displayed by subjects in the Centipede Game deviates radically from the predictions of traditional game theory. Even standard, infinite population, evolutionary settings have failed to provide an explanation for this behavior. However, recent work in finite population evolutionary models has shown that such settings can produce radically different results from the standard models. This paper examines the evolution of partial cooperation in finite populations. The results reveal a new possible explanation that is not open to (...) the standard models and gives us reason to be cautious when employing these otherwise helpful idealizations. *Received January 2007; revised November 2007. †To contact the author, please write to: Department of Logic and Philosophy of Science, University of California, 3151 Social Science Plaza A, Irvine, CA 92697-5100; e-mail: rsmead@uci.edu. (shrink)
We introduce CE- cell decomposition , a modified version of the usual o-minimal cell decomposition. We show that if an o-minimal structure $\mathcal{R}$ admits CE-cell decomposition then any definable open set in $\mathcal{R}$ may be expressed as a finite union of definable open cells. The dense linear ordering and linear o-minimal expansions of ordered abelian groups are examples of such structures.
Abstract Robert Stern's Understanding Moral Obligation is a remarkable achievement, representing an original reading of Kant's contribution to modern moral philosophy and the legacy he bequeathed to his later-eighteenth- and early-nineteenth-century successors in the German tradition. On Stern's interpretation, it was not the threat to autonomy posed by value realism, but the threat to autonomy posed by the obligatory nature of morality that led Kant to develop his critical moral theory grounded in the concept of the self-legislating moral agent. Accordingly, (...) Stern contends that Kant was a moral realist of sorts, holding certain substantive views that are best characterized as realist commitments about value. In this paper, I raise two central objections to Stern's reading of Kant. The first objection concerns what Stern identifies as Kant's solution to the problem of moral obligation. Whereas Stern sees the distinction between the infinite will and the finite will as resolving the problem of moral obligation, I argue that this distinction merely explains why moral obligations necessarily take the form of imperatives for us imperfect human beings, but does not solve the deeper problem concerning the obligatory nature of morality?why we should take moral norms to be supremely authoritative laws that override all other norms based on our non-moral interests. The second objection addresses Stern's claim that Kantian autonomy is compatible with value realism. Although this is an idea with which many contemporary readers will be sympathetic, I suggest that the textual evidence actually weighs in favor of constructivism. (shrink)
This paper develops a formal system, consisting of a language and semantics, called serial logic ( SL ). In rough outline, SL permits quantification over, and reference to, some finite number of things in an order , in an ordinary everyday sense of the word “order,” and superplural quantification over things thus ordered. Before we discuss SL itself, some mention should be made of an issue in philosophical logic which provides the background to the development of SL , and (...) with respect to which I wish to contend that the system permits progress. (shrink)
This paper examines Leibniz’s views on the theistic doctrine of continual creation and considers their implications for his theory of finite substance. Three main theses are defended: (1) that Leibniz takes the traditional account of continual creation to involve the literal re-creation of all things in a successive series of instantaneous states, (2) that a straightforward commitment to the traditional account would give rise to serious problems within Leibniz’s theory of finite substance and his metaphysics more generally, and (...) (3) that Leibniz does not straightforwardly affirm the continual creation doctrine, despite certain texts that initially seem to suggest otherwise. I also present a more speculative interpretive hypothesis about what Leibniz’s considered view of creation might have been, namely that in a single act, God creates and conserves substances that are non-spatial and atemporal at the deepest level of reality. (shrink)
Finite spirits can be plausibly viewed as entities postulated by a theory, comparable to the position on mental states and processes developed in the latter part of the twentieth century. This position is developed here by reference to the account in the synoptic gospels of the exorcism of the Gadarene demoniacs. The role played by specifying causal relationships between postulated entities and objects whose existence is not in doubt is examined. Also, various features of theories are discussed in relation (...) to this example, viz. theory-laden description, classifying theories as naturalistic or supernaturalistic, kinds of evidence, and the importance of the method of hypothesis (or abduction) in critically scrutinizing the claims of religion. (Published Online August 11 2004). (shrink)
The “surge in use of finite-state methods” ([10]) in computational linguistics has largely, if not completely, left semantics untouched. The present paper is directed towards correcting this situation. Techniques explained in [1] are applied to a fragment of temporal semantics through an approach we call finite-state temporality. This proceeds from the intuition of an event as “a series of snapshots” ([15]; see also [12]), equating snapshots with symbols that collectively form our alphabet. A sequence of snapshots then becomes (...) a string over that alphabet, evoking comic/film strips. Jackendoff has, among others, objected to conceptualizing events in terms of snapshots ([8]). To counter these objections, we step up from events-as-strings to event-typesas-regular languages ([5, 6]), recognizing the need for variable granularity. Beyond the introduction of disjunction implicit in the step from a single string up to a set of strings, we obtain a useful logic from the regular operations and a careful choice of the snapshots (constituting our alphabet). (shrink)
We prove the Finite Model Property (FMP) for Distributive Full Lambek Calculus ( DFL ) whose algebraic semantics is the class of distributive residuated lattices ( DRL ). The problem was left open in [8, 5]. We use the method of nuclei and quasi–embedding in the style of [10, 1].
In some recent papers, the authors and Peter Gärdenfors have defined and studied two different kinds of formal operation, conceived as possible representations of the intuitive process of contracting a theory to eliminate a proposition. These are partial meet contraction (including as limiting cases full meet contraction and maxichoice contraction) and safe contraction. It is known, via the representation theorem for the former, that every safe contraction operation over a theory is a partial meet contraction over that theory. The purpose (...) of the present paper is to study the relationship more finely, by seeking an explicit map between the component orderings involved in each of the two kinds of contraction. It is shown that at least in the finite case a suitable map exists, with the consequence that the relational, transitively relational, and antisymmetrically relational partial meet contraction functions form identifiable subclasses of the safe contraction functions, over any theory finite modulo logical equivalence. In the process of constructing the map, as the composition of four simple transformations, mediating notions of bottom and top contraction are introduced. The study of the infinite case remains open. (shrink)
In classes of algebras such as lattices, groups, and rings, there are finite algebras which individually generate quasivarieties which are not finitely axiomatizable (see [2], [3], [8]). We show here that this kind of algebras also exist in Heyting algebras as well as in topological Boolean algebras. Moreover, we show that the lattice join of two finitely axiomatizable quasivarieties, each generated by a finite Heyting or topological Boolean algebra, respectively, need not be finitely axiomatizable. Finally, we solve problem (...) 4 asked in Rautenberg [10]. (shrink)
Discusses Frege's formal definitions and characterizations of infinite and finite sets. Speculates that Frege might have discovered the "oddity" in Dedekind's famous proof that all infinite sets are Dedekind infinite and, in doing so, stumbled across an axiom of countable choice.
We introduce a new framework for asymptotic probabilities of sentences, in which we have a σ-additive measure on the sample space of all sequences A = {A n } of finite models, where the universe of A n is {1,2... n}, and use this framework to strengthen 0-1 laws for logics.
I discuss a difficulty concerning the justification of the Axiom of Choice in terms of such informal notions such as that of iterative set. A recent attempt to solve the difficulty is by S. Lavine, who claims in his Understanding the Infinite that the axioms of set theory receive intuitive justification from their being self-evidently true in Fin(ZFC), a finite counterpart of set theory. I argue that Lavine's explanatory attempt fails when it comes to AC: in this respect Fin(ZFC) (...) is no better off than the iterative notion. (shrink)
We investigate properties of propositional modal logic over the classof finite structures. In particular, we show that certain knownpreservation theorems remain true over this class. We prove that aclass of finite models is defined by a first-order sentence and closedunder bisimulations if and only if it is definable by a modal formula.We also prove that a class of finite models defined by a modal formulais closed under extensions if and only if it is defined by a -modal (...) formula. (shrink)
In [Ono 1987] H. Ono put the question about axiomatizing the intermediate predicate logicLFin characterized by the class of all finite Kripke frames (Problem 4,P41). It was established in [Skvortsov 1988] thatLFin is not recursively axiomatizable. One can easily show that for any finite posetM, the predicate logic characterized byM is recursively axiomatizable, and its axiomatization can be constructed effectively fromM. Namely, the set of formulas belonging to this logic is recursively enumerable, since it is embeddable in (...) the two-sorted classical predicate calculusCPC 2 (the definition of the truth in a Kripke model may be expressed by a formula ofCPC 2). Thus the logicLFin is II 2 0 -arithmetical.Here we give a more explicit II 2 0 -description ofLFin: it is presented as the intersection of a denumerable sequence of finitely axiomatizable Kripke-complete logics. Namely, we give an axiomatization of the logicLB n P m + characterized by the class of all posets of the finite height m and the finite branching n. A finite axiomatization of the predicate logicLP m + characterized by the class of all posets of the height m is known from [Yokota 1989] (this axiomatics is essentially first-order; the standard propositional axiom of the height m is not sufficient [Ono 1983]). We prove thatLB n P m + =(LP m + +B n),B n being the propositional axiom of the branching n (see [Gabbay, de Jongh 1974]). (shrink)
In this paper we show the adequacy of tense logic with unary operators for dealing with finite trees. We prove that models on finite trees can be characterized by tense formulas, and describe an effective method to find an axiomatization of the theory of a given finite tree in tense logic. The strength of the characterization is shown by proving that adding the binary operators "Until" and "Since" to the language does not result in a better description (...) than that given by unary tense logic; although the greater expressive power of "Until" and "Since" can be exploited by using the semantics of e-frames instead of traditional Kripke semantics. (shrink)
Finite-state methods are applied to the Russell-Wiener-Kamp notion of time (based on events) and developed into an account of interval relations and semi-intervals. Strings are formed and collected in regular languages and regular relations that are argued to embody temporal relations in their various underspecified guises. The regular relations include retractions that reduce computations by projecting strings down to an appropriate level of granularity, and notions of containment for partiality within and across such levels.
We present some formal systems in the language of linearly ordered rings with finite sets whose nonlogical axioms are strictly mathematical, which correspond to polynomially bounded arithmetic. With an additional strictly mathematical axiom, the systems correspond to exponentially bounded arithmetic.
The main purpose of this paper is to introduce a class of algebraic structures related to many-valued ukasiewicz algebras. They are symmetrical Heyting algebras with a set of modal operators indexed by a finite completely symmetric poset. A representation theorem is given for these (not functionally complete) algebras.
There is no known syntactic characterization of the class of finite definitions in terms of a set of basic definitions and a set of basic operators under which the class is closed. Furthermore, it is known that the basic propositional operators do not preserve finiteness. In this paper I survey these problems and explore operators that do preserve finiteness. I also show that every definition that uses only unary predicate symbols and equality is bound to be finite.
We present a theory that copes with the dynamics of inconsistent information. A method is set forth to represent possibly inconsistent information by a finite state. Next, finite operations for expansion and contraction of finite states are given. No extra-logical element — a choice function or an ordering over (sets of) sentences — is presupposed in the definition of contraction. Moreover, expansion and contraction are each other's duals. AGM-style characterizations of these operations follow.
Let (L; f) be a finite simple Ockham algebra and let (X;g) be its dual space. We first prove that every connected component of X is either a singleton or a generalised crown (i.e. an ordered set that is connected, has length 1, and all vertices of which have the same degree). The representation of a generalised crown by a square (0,1)-matrix in which all line sums are equal is used throughout, and a complete description of X, including the (...) number of connected components and the degree of the vertices, is given. We then examine the converse problem of when a generalised crown can be made into a connected component of (X; g). We also determine the number of non-isomorphic finite simple Ockham algebras that belong properly to a given subvariety P 2n,0. Finally, we show that the number of fixed points of (L; f) is 0,1, or 2 according to the nature of X. (shrink)
Robert Adams’s Finite and Infinite Goods is one of the most important and innovative contributions to theistic ethics in recent memory. This article identifies two major flaws at the heart of Adams’s theory: his notion of intrinsic value and his claim that ‘excellence’ or finite goodness is constituted by resemblance to God. I first elucidate Adams’s complex, frequently misunderstood claims concerning intrinsic value and Godlikeness. I then contend that Adams’s notion of intrinsic value cannot explain what it could (...) mean for countless finite goods to be intrinsically valuable. Next, I articulate a criticism of his Godlikeness thesis altogether unlike those he has previously addressed: I show that, on Adams’s own account of Godlikeness, a diverse myriad of excellences could not possibly count as resembling God. His theory thus fails to account for a whole world of finite goods. I defend my two criticisms against objections and briefly sketch a more Aristotelian and Christian way forward. (shrink)
Finite-state methods are applied to the Russell-Wiener notion of time (based on events) and developed into an account of interval relations and temporal propositions. Strings are formed and collected in regular languages and regular relations that are argued to embody temporal relations in their various underspecified guises. The regular relations include retractions that reduce computations by projecting strings down to an appropriate level of granularity, and non-deterministic relations defining notions of partiality within and across such levels.
The aim of this paper is to characterize varieties of Heyting algebras with decidable theory of their finite members. Actually we prove that such varieties are exactly the varieties generated by linearly ordered algebras. It contrasts to the result of Burris [2] saying that in the case of whole varieties, only trivial variety and the variety of Boolean algebras have decidable first order theories.
An infinite structure is said to be minimal if each of its definable subset is finite or cofinite. Modifying Hrushovski's method we construct minimal, non strongly minimal structures with arbitrary finite dimensions. This answers negatively to a problem posed by B. I Zilber.
This paper explores lexicographically additive representations of multi-attribute preferences on finite sets. Lexicographic additivity combines a lexicographic feature with local value tradeoffs. Tradeoff structures are governed by either transitive or nontransitive additive conjoint measurement. Alternatives are locally traded off when they are close enough within threshold associated with a dominant subset of attributes.
There are properties of finite structures that are expressible with the use of Hilbert's ε-operator in a manner that does not depend on the actual interpretation for ε-terms, but not expressible in plain first-order. This observation strengthens a corresponding result of Gurevich, concerning the invariant use of an auxiliary ordering in first-order logic over finite structures. The present result also implies that certain non-deterministic choice constructs, which have been considered in database theory, properly enhance the expressive power of (...) first-order logic even as far as deterministic queries are concerned, thereby answering a question raised by Abiteboul and Vianu. (shrink)
The method of Quasi-Analysis used by Carnap in his program of theconstitution of concepts from finite observations has the following twogoals: (1) Given unsharp observations in terms of similarity relations thetrue properties of the observed objects shall be obtained by a suitablelogical construction. (2) From a single relation on a finite domain,different dimensions of qualities shall be reconstructed and identified. Inthis article I show that with a slight modification Quasi-Analysis iscapable of fulfilling the first goal for a single (...) observable dimension. Weobtain a partition of the so-called Quality Classes representing thepairwise disjoint and exhaustive extensions associated to the ``values'''' ofthe observable. On the other hand, an example demonstrates that the methodfails, as Goodman has pointed out, for a relation expressing similarity withregard to at least one out of many properties.Since it seems to be impossible in general to reconstruct more-dimensionalqualities from a single similarity relation, the constitution of at least asmany similarity relations as there are qualities have to be presumed. Thenit is possible to state adequate sufficient conditions for the dimension ofthe observable space, even if some of the similarity relations might dependon others. The concept of topological dimension cannot be used for thispurpose on finite sets of observations. We replace it by a set-algebraicalcondition on the Quality Classes. (shrink)
We explore a network architecture introduced by Elman (1988) for predicting successive elements of a sequence. The network uses the pattern of activation over a set of hidden units from time-step 25-1, together with element t, to predict element t + 1. When the network is trained with strings from a particular finite-state grammar, it can learn to be a perfect finite-state recognizer for the grammar. When the network has a minimal number of hidden units, patterns on the (...) hidden units come to correspond to the nodes of the grammar, although this correspondence is not necessary for the network to act as a perfect finite-state recognizer. We explore the conditions under which the network can carry information about distant sequential contingencies across intervening elements. Such information is maintained with relative ease if it is.. (shrink)
In the first part of this paper, two arguments, one by Chomsky, and one by Bar-Hillel and Shamir, are examined in detail and rejected. Both arguments purport to show that the structure of English precludes its having a finite state grammar which correctly enumerates just the well formed sentences of English. In the latter part of the paper I consider the problem of supporting claims about the structure and properties of a natural language when no grammar for the language (...) has yet been accepted. (shrink)
We prove that an intermediate predicate logic characterized by a class of finite partially ordered sets is recursively axiomatizable iff it is "finite", i.e., iff it is characterized by a single finite partially ordered set. Therefore, the predicate logic LFin of the class of all predicate Kripke frames with finitely many possible worlds is not recursively axiomatizable.
We prove that each intermediate or normal modal logic is strongly complete with respect to a class of finite Kripke frames iff it is tabular, i.e. the respective variety of pseudo-Boolean or modal algebras, corresponding to it, is generated by a finite algebra.
Finite-state methods are applied to determine the consequences of events, represented as strings of sets of fluents. Developed to flesh out events used in natural language semantics, the approach supports reasoning about action in AI, including the frame problem and inertia. Representational and inferential aspects of the approach are explored, centering on conciseness of language, context update and constraint application with bias.
There are numerous occasions on which we need to reason about a finite number of events. And we often need to consider only those events which are given or which we perceive. These give rise to the Criteria of Finiteness and Closedness. Allen's logic provides a way of reasoning about events. In this paper I examine Allen and Hayes' axiomatisation of this logic, and develop two other axiomatisations based on the work by Russell and Thomason. I shall show that (...) these three axiomatisations are weakly equivalent, and that only the last two meet the Criteria of Finiteness and Closedness (to different degrees). I shall then examine two ways of constructing instants of time in a finite and closed world, i.e. the Russell construction and the Thomason construction. I shall prove that these two constructions are equivalent under certain conditions. (shrink)
. In this paper, the significance of using general logic-systems and finite consequence operators defined on non-organized languages is discussed. Results are established that show how properties of finite consequence operators are independent from language organization and that, in some cases, they depend only upon one simple language characteristic. For example, it is shown that there are infinitely many finite consequence operators defined on any non-organized infinite language L that cannot be generated from any finite logic-system. (...) On the other hand, it is shown that for any nonempty language L, a set map is a finite consequence operator if and only if it is defined by a general logic-system. Simple logic-system examples that determine specific consequence operator properties are given. (shrink)
The traditional model theory of first-order logic assumes that the interpretation of a formula can be given without reference to its deductive context. This paper investigates an interpretation which depends on a formula's location within a derivation. The key step is to drop the assumption that all quantified variables must have the same range and to require only that the ranges of variables in a derivation must be related in such way as to preserve the soundness of the inference rules. (...) With each (consistent) derivation there is associated a Buridan-Volpin (orBV) structure [M, {r(x)}] which is simply a Tarski structureM for the language and a map giving the ranger(x) of each variablex in the derivation. IfLK* is (approximately) the classical sequent calculusLK of Gentzen from which the structural contraction rules have been dropped, then our main result reads: If a set of first-ordered formulas has a Tarski modelM, then from any normal derivationD inLK* of can be constructed aBV modelM D=[M, {r(x)}] of where each ranger(x) is finite. (shrink)
The paper discusses the notion of finite model truth definitions (or FM-truth definitions), introduced by M. Mostowski as a finite model analogue of Tarski's classical notion of truth definition. We compare FM-truth definitions with Vardi's concept of the combined complexity of logics, noting an important difference: the difficulty of defining FM-truth for a logic ᵍ does not depend on the syntax of L, as long as it is decidable. It follows that for a natural ᵍ there exist FM-truth (...) definitions whose evaluation is much easier than the combined complexiy of ᵍ would suggest. We apply the general theory to give a complexity-theoretical characterization of the logics for which the $\Sigma_{m}^{d}$ classes (prenex classes of higher order logics) define FM-truth. For any $d \geq 2.m \geq 1$ we construct a family $\{[\Sigma_{m}^{d}]^{\leg\kappa}\}\kappa\in\omega$ of syntactically defined fragments of $\Sigma_{m}^{d}$ which satisfy this characterization. We also use the $[\Sigma_{m}^{d}]\leg\kappa$ classes to give a refinement of known results on the complexity classes captured by $\Sigma_{m}^{d}$ . We close with a few simple corollaries, one of which gives a sufficient condition for the existence, given a vocabulary $\sigma$ , of a fixed number $\kappa$ such that model checking for all first order sentences over $\sigma$ can be done in deterministic time $n^{\kappa}$. (shrink)
We prove: Theorem. A complete first order theory in a countable language which is strictly stable, trivial and which admits finite coding has 2 ℵ 0 nonisomorphic countable models. Combined with the corresponding result or superstable theories from [4] our result confirms the Vaught conjecture for trivial theories which admit finite coding.
Neo-Ftegeanism contends that knowledge of arithmetic may be acquired by second-order logical reflection upon Hume's principle. Heck argues that Hume's principle doesn't inform ordinary arithmetical reasoning and so knowledge derived from it cannot be genuinely arithmetical. To suppose otherwise, Heck claims, is to fail to comprehend the magnitude of Cantor's conceptual contribution to mathematics. Heck recommends that finite Hume's principle be employed instead to generate arithmetical knowledge. But a better understanding of Cantor's contribution is achieved if it is supposed (...) that Hume's principle really does inform arithmetical practice. More generally, Heck's arguments misconceive the epistemological character of neo-Fregeanism. (shrink)
This paper shows that both implicational logicsBCK andBCIW have the finite model property. The proof of the finite model property forBCIW, which is equal to the relevant logicR , was originally given by the first author in his unpublished paper [6] in 1973. The finite model property forBCK can be obtained by modifying the proof of that forBCIW. Here, both of these proofs will be given in a (...) unified form and the difference between them will be clarified. Further discussions will be given in the last section. (shrink)
Assume T is a superstable theory with $ countable models. We prove that any *-algebraic type of M-rank > 0 is m-nonorthogonal to a *-algebraic type of M-rank 1. We study the geometry induced by m-dependence on a *-algebraic type p* of M-rank 1. We prove that after some localization this geometry becomes projective over a division ring F. Associated with p* is a meager type p. We prove that p is determined by p* up to nonorthogonality and that F (...) underlies also the geometry induced by forking dependence on any stationarization of p. Also we study some *-algebraic *-groups of M-rank 1 and prove that any *-algebraic *-group of M-rank 1 is abelian-by-finite. (shrink)
Recently Lafont [6] showed the finite model property for the multiplicative additive fragment of linear logic (MALL) and for affine logic (LLW), i.e., linear logic with weakening. In this paper, we shall prove the finite model property for intuitionistic versions of those, i.e. intuitionistic MALL (which we call IMALL), and intuitionistic LLW (which we call ILLW). In addition, we shall show the finite model property for contractive linear logic (LLC), i.e., linear logic with contraction, and for its (...) intuitionistic version (ILLC). The finite model property for related substructural logics also follow by our method. In particular, we shall show that the property holds for all of FL and GL - -systems except FL c and GL - c of Ono [11], that will settle the open problems stated in Ono [12]. (shrink)
We give a complete characterization of Priest's Finite Inconsistent Arithmetics observing that his original putative characterization included arithmetics which cannot in fact be realized.
We consider modal logics whose intermediate fragments lie between the logic of infinite problems [20] and the Medvedev logic of finite problems [15]. There is continuum of such logics [19]. We prove that none of them is finitely axiomatizable. The proof is based on methods from [12] and makes use of some graph-theoretic constructions (operations on coverings, and colourings).
The aim of this paper is to show that the implicational fragment BKof the intuitionistic propositional calculus (IPC) without the rules of exchange and contraction has the finite model property with respect to the quasivariety of left residuation algebras (its equivalent algebraic semantics). It follows that the variety generated by all left residuation algebras is generated by the finite left residuation algebras. We also establish that BKhas the finite model property with respect to a class of structures (...) that constitute a Kripke-style relational semantics for it. The results settle a question of Ono and Komori [OK85]. (shrink)
A decision problem in which the values of the decision variables must sum to a fixed positive real number s is called an "allocation problem," and the problem of aggregating the allocations of n experts the "allocation aggregation problem." Under two simple axiomatic restrictions on aggregation, the only acceptable allocation aggregation method is based on weighted arithmetic averaging (Lehrer and Wagner, Rational Consensus in Science and Society, 1981). In this note it is demonstrated that when the values assigned to the (...) variables are restricted to a finite set (as is always the case in practice), the aforementioned axioms allow only dictatorial aggregation. (shrink)
We derive a Mal'cev condition for congruence meet-semidistributivity and then use it to prove two theorems. Theorem A: if a variety in a finite language is congruence meet-semidistributive and residually less than some finite cardinal, then it is finitely based. Theorem B: there is an algorithm which, given $m and a finite algebra in a finite language, determines whether the variety generated by the algebra is congruence meet-semidistributive and residually less than m.
A general class of labeled sequent calculi is investigated, and necessary and sufficient conditions are given for when such a calculus is sound and complete for a finite-valued logic if the labels are interpreted as sets of truth values (sets-as-signs). Furthermore, it is shown that any finite-valued logic can be given an axiomatization by such a labeled calculus using arbitrary "systems of signs," i.e., of sets of truth values, as labels. The number of labels needed is logarithmic in (...) the number of truth values, and it is shown that this bound is tight. (shrink)
We classify actions of groups of finite Morley rank on abelian groups of Morley rank 2: there are essentially two, namely the natural actions of SL(V) and GL(V) with V a vector space of dimension 2. We also prove an identification theorem for the natural module of SL₂ in the finite Morley rank category.
Gödel's dialectica interpretation of Heyting arithmetic HA may be seen as expressing a lack of confidence in our understanding of unbounded quantification. Instead of formally proving an implication with an existential consequent or with a universal antecedent, the dialectica interpretation asks, under suitable conditions, for explicit 'interpreting' instances that make the implication valid. For proofs in constructive set theory CZF-, it may not always be possible to find just one such instance, but it must suffice to explicitly name a set (...) consisting of such interpreting instances. The aim of eliminating unbounded quantification in favor of appropriate constructive functionals will still be obtained, as our ∧-interpretation theorem for constructive set theory in all finite types CZFω- shows. By changing to a hybrid interpretation ∧q, we show closure of CZFω- under rules that – in stronger forms – have already been studied in the context of Heyting arithmetic. In a similar spirit, we briefly survey modified realizability of CZFω- and its hybrids. Central results of this paper have been proved by Burr 2000a and Schulte 2006, however, for different translations. We use a simplified interpretation that goes back to Diller and Nahm 1974. A novel element is a lemma on absorption of bounds which is essential for the smooth operation of our translation. (shrink)
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)
In [2] A. Wroski proved that there is a strongly finite consequence C which is not finitely based i.e. for every consequence C + determined by a finite set of standard rules C C +. In this paper it will be proved that for every strongly finite consequence C there is a consequence C + determined by a finite set of structural rules such that C(Ø)=C +(Ø) and = (where , are consequences obtained by adding to (...) the rules of C, C + respectively the rule of substitution). Moreover it will be shown that under certain assumptions C=C +. (shrink)
Finite-state descriptions for temporal semantics are outlined through which to distinguish soft inferences reflecting manners of conceptualization from more robust semantic entailments defined over models. Just what descriptions are built (before being interpreted model-theoretically) and how they are grounded in models of reality explain (upon examination) why some inferences are soft.
Let k be a positive integer. There is a longest finite sequence x1,...,xn in k letters in which no consecutive block xi,...,x2i is a subsequence of any other consecutive block xj,...,x2j. Let n(k) be this longest length. We prove that n(1) = 3, n(2) = 11, and n(3) is incomprehensibly large. We give a lower bound for n(3) in terms of the familiar Ackerman hierarchy. We also give asymptotic upper and lower bounds for n(k). We view n(3) as a (...) particularly elemental description of an incomprehensibly large integer. Related problems involving binary sequences (two letters) are also addressed. We also report on some recent computer explorations of R. Dougherty which we use to raise the lower bound for n(3). (shrink)
In the current paper we consider theories with vocabulary containing a number of binary and unary relation symbols. Binary relation symbols represent labeled edges of a graph and unary relations represent unique annotations of the graph’s nodes. Such theories, which we call annotation theories , can be used in many applications, including the formalization of argumentation, approximate reasoning, semantics of logic programs, graph coloring, etc. We address a number of problems related to annotation theories over finite models, including satisfiability, (...) querying problem, specification of preferred models and model checking problem. We show that most of considered problems are NPT ime - or co-NPT ime -complete. In order to reduce the complexity for particular theories, we use second-order quantifier elimination. To our best knowledge none of existing methods works in the case of annotation theories. We then provide a new second-order quantifier elimination method for stratified theories, which is successful in the considered cases. The new result subsumes many other results, including those of [2, 28, 21]. (shrink)
We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show that this is not (...) always true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures L C . These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L NP . This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993]. (shrink)
The main result of this paper is a probabilistic construction of finite rigid structures. It yields a finitely axiomatizable class of finite rigid structures where no L ω ∞,ω formula with counting quantifiers defines a linear order.
A conjecture of Gabbay (1981) states that any class of flows of time having the property known as finite H-dimension admits a finite set of expressively complete one-dimensional temporal connectives. Here we show that the class of circular structures refutes the generalisation of this conjecture to Kripke frames. We then construct from this class, by a general method, a new class of irreflexive transitive flows of time that refutes the original (...) conjecture.Our paper includes full descriptions of a method for establishing finite H-dimension for a class of structures and of the technique for extending finite H-dimension to other classes, and an introduction surveying the area of expressive completeness. (shrink)
We show that the loosely guarded and packed fragments of first-order logic have the finite model property. We use a construction of Herwig and Hrushovski. We point out some consequences in temporal predicate logic and algebraic logic.
A countably infinite relational structure M is called absolutely ubiquitous if the following holds: whenever N is a countably infinite structure, and M and N have the same isomorphism types of finite induced substructures, there is an isomorphism from M to N. Here a characterisation is given of absolutely ubiquitous structures over languages with finitely many relation symbols. A corresponding result is proved for uncountable structures.
We consider the existence of coherent families of finite-to-one functions on countable subsets of an uncountable cardinal κ. The existence of such families for κ implies the existence of a winning 2-tactic for player TWO in the countable-finite game on κ. We prove that coherent families exist on κ = ωn, where n ∈ ω, and that they consistently exist for every cardinal κ. We also prove that iterations of Axiom A forcings with countable supports are Axiom A.
We prove a finite model theorem and infinitary completeness result for the propositional -calculus. The construction establishes a link between finite model theorems for propositional program logics and the theory of well-quasi-orders.
We define a characteristic and definable subgroup F*(G) of any group G of finite Morley rank that behaves very much like the generalized Fitting subgroup of a finite group. We also prove that semisimple subnormal subgroups of G are all definable and that there are finitely many of them.
We show that two abelian-by-finite groups are elementarily equivalent if and only if they satisfy the same sentences with two alternations of quantifiers. We also prove that abelian-by-finite groups satisfy a quantifier elimination property. On the other hand, for each integer n, we give some examples of nilpotent groups which satisfy the same sentences with n alternations of quantifiers and do not satisfy the same sentences with n + 1 alternations of quantifiers.
We show that a finitely generated protoalgebraic strict universal Horn class that is filter-distributive is finitely based. Equivalently, every protoalgebraic and filter-distributive multidimensional deductive system determined by a finite set of finite matrices can be presented by finitely many axioms and rules.
The complexity of aII 4 set of natural numbers is encoded into a linear order to show that the finite condensation of a recursive linear order can beII 2–II 1. A priority argument establishes the same result, and is extended to a complete classification of finite condensations iterated finitely many times.
A structure has a (finite-string) automatic presentation if the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability.
Every ℵ 0 -categorical partially ordered set of finite width has a finitely axiomatizable theory. Every ℵ 0 -categorical partially ordered set of finite weak width has a decidable theory. This last statement constitutes a major portion of the complete (with three exceptions) characterization of those finite partially ordered sets for which any ℵ 0 -categorical partially ordered set not embedding one of them has a decidable theory.
In a previous paper-[17]-we characterized strong measure zero sets of reals in terms of a Ramseyan partition relation on certain subspaces of the Alexandroff duplicate of the unit interval. This framework gave only indirect access to the relevant sets of real numbers. We now work more directly with the sets in question, and since it costs little in additional technicalities, we consider the more general context of metric spaces and prove: 1. If a metric space has a covering property of (...) Hurewicz and has strong measure zero, then its product with any strong measure zero metric space is a strong measure zero metric space (Theorem 1 and Lemma 3). 2. A subspace X of a σ-compact metric space Y has strong measure zero if, and only if, a certain Ramseyan partition relation holds for Y (Theorem 9). 3. A subspace X of a σ-compact metric space Y has strong measure zero in all finite powers if, and only if, a certain Ramseyan partition relation holds for Y (Theorem 12). Then 2 and 3 yield characterizations of strong measure zeroness for σ-totally bounded metric spaces in terms of Ramseyan theorems. (shrink)
Schutz’s references to literature and arts in his theoretical works are manifold. But literature and theory are both a certain kind of a finite province of meaning, that means they are not easily accessible from the paramount reality of everyday life. Now there is another kind of referring to literature: metaphorizing it. Using it, as may be said with Lakoff and Johnson, to understand and to experience one kind of thing in terms of another. Literally metapherein means “to carry (...) over”. Metaphorizing in this view is then a specific kind of border-crossing between different provinces of meaning. That poses two questions: 1. What means finiteness of those provinces of meaning, what kind of border crossings are possible? What is the ground for metaphorizing meaning? 2. Could this concept used for founding a theory of the constitution of the societal and of society, that overcomes the dichotomy of structure/agency? These questions will be answered with one example in view: Schutz’ report to Kaufmann of his first visit of Husserl describing his experience as feeling like Wilhelm Meister at the Society of the Tower. In a first step this metaphor is presented together with some crumbs of metaphor theory. In a second step these crumbs will be connected to Husserl’s concept of experience. After developing a short overview over Schutz’ “finite provinces of meaning,” the relation of experience, metaphors to the intersubjectivity of these provinces in their dependence from writing and printing is discussed. (shrink)
An intermediate predicate logic L is called finite iff it is characterized by a finite partially ordered set M, i.e., iff L is the logic of the class of all predicate Kripke frames based on M. In this paper we study axiomatizability of logics of this kind. Namely, we consider logics characterized by finite trees M of a certain type (levelwise uniform trees) and establish the finite axiomatizability criterion for this case.
Using a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms.
We characterize pairs of monotone generalized quantifiers Q1 and Q2 over finite domains that give rise to an entailment relation between their two relative scope construals. This relation between quantifiers, which is referred to as scope dominance, is used for identifying entailment relations between the two scopal interpretations of simple sentences of the form NP1-V- NP2. Simple numerical or set-theoretical considerations that follow from our main result are used for characterizing such relations. The variety of examples in which they (...) hold are shown to go far beyond the familiar existentialuniversal type. (shrink)
