Mostrando recursos 1 - 20 de 2.217

  1. Causality, Modality, and Explanation

    White, Graham
    We start with Fodor's critique of cognitive science in "The mind doesn't work that way: The scope and limits of computational psychology": he argues that much mental activity cannot be handled by the current methods of cognitive science because it is nonmonotonic and, therefore, is global in nature, is not context-free, and is thus not capable of being formalized by a Turing-like mental architecture. We look at the use of nonmonotonic logic in the artificial intelligence community, particularly with the discussion of the so-called frame problem. The mainstream approach to the frame problem is, we argue, probably susceptible to Fodor's critique; however, there is an alternative approach, due to McCain and...

  2. Decomposable Ultrafilters and Possible Cofinalities

    Lipparini, Paolo
    We use Shelah's theory of possible cofinalities in order to solve some problems about ultrafilters. Theorem: Suppose that $\lambda$ is a singular cardinal, $\lambda ' \lessthan \lambda$ , and the ultrafilter $D$ is $\kappa$ -decomposable for all regular cardinals $\kappa$ with $\lambda '\lessthan \kappa \lessthan \lambda$ . Then $D$ is either $\lambda$ -decomposable or $\lambda ^+$ -decomposable. Corollary: If $\lambda$ is a singular cardinal, then an ultrafilter is ( $\lambda$ , $\lambda$ )-regular if and only if it is either $\operator{cf} \lambda$ -decomposable or $\lambda^+$ -decomposable. We also give applications to topological spaces and to abstract logics.

  3. Self-implications in BCI

    Kowalski, Tomasz
    Humberstone asks whether every theorem of BCI provably implies $\phi\to\phi$ for some formula $\phi$ . Meyer conjectures that the axiom $\mathbf{B}$ does not imply any such "self-implication." We prove a slightly stronger result, thereby confirming Meyer's conjecture.

  4. Quantifier Elimination for a Class of Intuitionistic Theories

    Ellison, Ben; Fleischmann, Jonathan; McGinn, Dan; Ruitenburg, Wim
    From classical, Fraïissé-homogeneous, ( $\leq \omega$ )-categorical theories over finite relational languages, we construct intuitionistic theories that are complete, prove negations of classical tautologies, and admit quantifier elimination. We also determine the intuitionistic universal fragments of these theories.

  5. Common Knowledge of Rationality in Extensive Games

    de Bruin, Boudewijn
    We develop a logical system that captures two different interpretations of what extensive games model, and we apply this to a long-standing debate in game theory between those who defend the claim that common knowledge of rationality leads to backward induction or subgame perfect (Nash) equilibria and those who reject this claim. We show that a defense of the claim à la Aumann (1995) rests on a conception of extensive game playing as a one-shot event in combination with a principle of rationality that is incompatible with it, while a rejection of the claim à la Reny (1988) assumes a temporally extended, many-moment interpretation of extensive games in combination with...

  6. The Logic of Conditional Negation

    Cantwell, John
    It is argued that the "inner" negation $\mathord{\sim}$ familiar from 3-valued logic can be interpreted as a form of "conditional" negation: $\mathord{\sim}$ is read ' $A$ is false if it has a truth value'. It is argued that this reading squares well with a particular 3-valued interpretation of a conditional that in the literature has been seen as a serious candidate for capturing the truth conditions of the natural language indicative conditional (e.g., "If Jim went to the party he had a good time"). It is shown that the logic induced by the semantics shares many familiar properties with classical negation, but is orthogonal to both intuitionistic and...

  7. Classifying the Branching Degrees in the Medvedev Lattice of $\Pi^0_1$ Classes

    Alfeld, Christopher P.
    A $\Pi^0_1$ class can be defined as the set of infinite paths through a computable tree. For classes $P$ and $Q$ , say that $P$ is Medvedev reducible to $Q$ , $P \leq_M Q$ , if there is a computably continuous functional mapping $Q$ into $P$ . Let $\mathcal{L}_M$ be the lattice of degrees formed by $\Pi^0_1$ subclasses of $2^\omega$ under the Medvedev reducibility. In "Non-branching degrees in the Medvedev lattice of $\Pi \sp{0}\sb{1} classes," I provided a characterization of nonbranching/branching and a classification of the nonbranching degrees. In this paper, I present a similar classification of the branching degrees. In particular, $P$ is separable...

  8. Uniform Continuity Properties of Preference Relations

    Bridges, Douglas S.
    The anti-Specker property, a constructive version of sequential compactness, is used to prove constructively that a pointwise continuous, order-dense preference relation on a compact metric space is uniformly sequentially continuous. It is then shown that Ishihara's principle BD-ℕ implies that a uniformly sequentially continuous, order-dense preference relation on a separable metric space is uniformly continuous. Converses of these two theorems are also proved.

  9. Reflexive Intermediate First-Order Logics

    Carter, Nathan C.
    It is known that the set of intermediate propositional logics that can prove their own completeness theorems is exactly those which prove every instance of the principle of testability, ¬ϕ ∨ ¬¬ϕ. Such logics are called reflexive. This paper classifies reflexive intermediate logics in the first-order case: a first-order logic is reflexive if and only if it proves every instance of the principle of double negation shift and the metatheory created from it proves every instance of the principle of testability.

  10. Anderson's Relevant Deontic and Eubouliatic Systems

    Lokhorst, Gert-Jan C.
    We present axiomatizations of the deontic fragment of Anderson's relevant deontic logic (the logic of obligation and related concepts) and the eubouliatic fragment of Anderson's eubouliatic logic (the logic of prudence, safety, risk, and related concepts).

  11. Decidability of ∃*∀∀-sentences in HF

    Bellè, D.; Parlamento, F.
    Let HF be the collection of the hereditarily finite well-founded sets and let the primitive language of set theory be the first-order language which contains binary symbols for equality and membership only. As announced in a previous paper by the authors, "Truth in V for ∃*∀∀-sentences is decidable," truth in HF for ∃*∀∀-sentences of the primitive language is decidable. The paper provides the proof of that claim.

  12. Topological Models for Extensional Partial Set Theory

    Hinnion, Roland; Libert, Thierry
    We state the consistency problem of extensional partial set theory and prove two complementary results toward a definitive solution. The proof of one of our results makes use of an extension of the topological construction that was originally applied in the paraconsistent case.

  13. Self-Embeddings of Computable Trees

    Binns, Stephen; Kjos-Hanssen, Bjørn; Lerman, Manuel; Schmerl, James H.; Solomon, Reed
    We divide the class of infinite computable trees into three types. For the first and second types, 0' computes a nontrivial self-embedding while for the third type 0'' computes a nontrivial self-embedding. These results are optimal and we obtain partial results concerning the complexity of nontrivial self-embeddings of infinite computable trees considered up to isomorphism. We show that every infinite computable tree must have either an infinite computable chain or an infinite Π01 antichain. This result is optimal and has connections to the program of reverse mathematics.

  14. Interval Orders and Reverse Mathematics

    Marcone, Alberto
    We study the reverse mathematics of interval orders. We establish the logical strength of the implications among various definitions of the notion of interval order. We also consider the strength of different versions of the characterization theorem for interval orders: a partial order is an interval order if and only if it does not contain 2 \oplus 2. We also study proper interval orders and their characterization theorem: a partial order is a proper interval order if and only if it contains neither 2 \oplus 2 nor 3 \oplus 1.

  15. Rumely Domains with Atomic Constructible Boolean Algebra. An Effective Viewpoint

    Sureson, Claude
    The archetypal Rumely domain is the ring \widetildeZ of algebraic integers. Its constructible Boolean algebra is atomless. We study here the opposite situation: Rumely domains whose constructible Boolean algebra is atomic. Recursive models (which are rings of algebraic numbers) are proposed; effective model-completeness and decidability of the corresponding theory are proved.

  16. Propositional Proof Systems and Fast Consistency Provers

    Joosten, Joost J.
    A fast consistency prover is a consistent polytime axiomatized theory that has short proofs of the finite consistency statements of any other polytime axiomatized theory. Krajíček and Pudlák have proved that the existence of an optimal propositional proof system is equivalent to the existence of a fast consistency prover. It is an easy observation that NP = coNP implies the existence of a fast consistency prover. The reverse implication is an open question. In this paper we define the notion of an unlikely fast consistency prover and prove that its existence is equivalent to NP = coNP. Next it is proved...

  17. Ages of Expansions of ω-Categorical Structures

    Ivanov, A.; Majcher, K.
    The age of a structure M is the set of all isomorphism types of finite substructures of M. We study ages of generic expansions of ω-stable ω-categorical structures.

  18. Cuppability of Simple and Hypersimple Sets

    Kummer, Martin; Schaefer, Marcus
    An incomplete degree is cuppable if it can be joined by an incomplete degree to a complete degree. For sets fulfilling some type of simplicity property one can now ask whether these sets are cuppable with respect to a certain type of reducibilities. Several such results are known. In this paper we settle all the remaining cases for the standard notions of simplicity and all the main strong reducibilities.

  19. Order-Computable Sets

    Hirschfeldt, Denis; Miller, Russell; Podzorov, Sergei
    We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.

  20. The Complexity of Bounded Quantifiers in Some Ordered Abelian Groups

    Scowcroft, Philip
    This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.