Click Here ">
« October 2006 »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
You are not logged in. Log in
Entries by Topic
All topics  «
Cognition & Epistemology
Notes on Pirah?
Ontology&possible worlds
Syn-Sem Interface
Temporal Logic
Blog Tools
Edit your Blog
Build a Blog
RSS Feed
View Profile
Translate this
LINGUISTIX&LOGIK, Tony Marmo's blog
Thursday, 26 October 2006

Topic: Interconnections

The complexity of theorem-proving procedures

By Stephen A. Cook

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be "reduced" to the problem of determining whether a given propositional formula is a tautology. Here "reduced" means, roughly speaking, that the first problem can be solved deterministically in polynomial time provided an oracle is available for solving the second. From this notion of reducible, polynomial degrees of difficulty are defined, and it is shown that the problem of determining tautologyhood has the same polynomial degree as the problem of determining whether the first of two given graphs is isomorphic to a subgraph of the second. Other examples are discussed. A method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed.

In Proceedings of the 3rd ACM Symposium on Theory of Computing, pages 151--158, 1971
Author's link (a compressed pdf file of a scanned version)
Other link


Posted by Tony Marmo at 18:37 BST
Friday, 20 October 2006

Topic: Interconnections

The Concept of Mathematical Elucidation:
theory and problems

By José Seoane

There is a contrast between concepts which may be treated in accordance with the criteria of mathematical rigor and concepts which are not susceptible of such a treatment. We will call theoretical concepts to the former and pre-theoretical to the latter. In mathematical world, sentences which relate theoretical and pre-theoretical concepts (in a determinated way) are denominated thesis; sentences which relate only theoretical concepts (in a determinated way) are denominated theorems. Elucidatory processes in mathematics have thesis as their principal output. I intend to establish in this paper that the introduction of the concept of mathematical elucidation has an important theoretical value to the effects of studying a certain special type of intended conceptual relation and a certain type of justificatory argumentation for it. The analysis of the contrast between thesis and theorems will allow us to construct a context where the interest for those conceptual relations and their supporting justificatory mechanisms arises naturally. Then, I will attempt to offer some structural features of mathematical elucidation qua conceptual relation and their impact on the strategies of elucidatory justification. This is what I grandiloquently call theory in the heading. I will suggest also a classification of the problems which a theoretical reflexion as the one proposed may contribute to clarify and I will make some brief observations on some paradigmatic examples of each one of the categories of the classification constructed. This work should be considered as a modest definition of a sort of research program.

Source: CLE e-prints

Posted by Tony Marmo at 18:27 BST
Friday, 6 October 2006


Worlds and Times

By Ulrich Meyer

There are many parallels between the role of possible worlds in modal logic and that of times in tense logic. But the similarities only go so far, and it is important to note where the two come apart. This paper argues that even though worlds and times play similar roles in the model theories of modal and tense logic, there is no tense analogue of the possible-worlds analysis of modal operators. An important corollary of this result is that presentism cannot be the tense analogue of actualism.

Keywords: tense logic; modal logic; times; possible worlds; actuality operator; presentism; actualism

Published in The Notre Dame Journal of Formal Logic
An unpublished version may be downloaded from the Author's page

Posted by Tony Marmo at 19:09 BST
Friday, 29 September 2006


Induction and Comparison

By Paul Pietroski

Logical induction may be important for theoretical linguistics, even if children do not induce languages from experience. Either our human capacities for inductive reasoning lie near the heart of our capacity to generate and understand expressions of a human language, or not. If they do, then theoretically minded linguists should try to understand human inductive capacities and the kinds of understanding they make possible, independent of other cognitive capacities. If not, then we should be clear about this, and not pretend otherwise-say, by adopting semantic theories that exploit the full resources of the logic that Frege used to reduce arithmetic to Hume's Principle. But suppose our best theories of language do presuppose that speakers have inductive capacities. Then considerations of theoretical parsimony suggest that we theorists should squeeze as much as we can from our representations of human inductive capacities, before adding controversial assumptions about how speakers understand expressions. This leaves room for hypotheses according to which speakers understand certain sentences in terms of covert quantification over abstracta.

Source: Semantics Archive


Posted by Tony Marmo at 14:58 BST

Now Playing: Reposted

Quantification and Second-Order Monadicity

By Paul M. Pietroski

Once we grant that grammatical structure can be as complicated as logical structure, and just as distant from audible features of word strings, we can approach the study of human cognition by combining the insights of modern logic (and not just its first-order fragment) and linguistics. Those deciding where to invest might want to compare this project, in terms of the results it has delivered and its potential for delivering more in the foreseeable future, with alternative projects that philosophers of language and mind have been pursuing. My bias in this regard will be evident. Though a more dispassionate assessment might lead to much the same conclusion: for now, our best hope of learning something important about the structure of thought-and giving substance to the ancient idea of language as a mirror of the mind-lies with figuring out how Frege, Chomsky, Montague, Davidson, and many others could each be importantly right, and no doubt wrong, about the same thing: namely, the shared syntactic/semantic structure of our sentences/thoughts. My suggestion is that this structure is more conjunctive, monadic, and second-order than one might think.

Source: Semantics Archive


Posted by Tony Marmo at 00:01 BST
Updated: Friday, 29 September 2006 15:00 BST
Friday, 1 September 2006

Topic: Interconnections

Truth and the Unprovability of Consistency

By Hartry Field

It might be thought that we could argue for the consistency of a mathematical theory T within T, by giving an inductive argument that all theorems of T are true and inferring consistency. By Gödel's second incompleteness theorem any such argument must break down, but just how it breaks down depends on the kind of theory of truth that is built into T. The paper surveys the possibilities, and suggests that some theories of truth give far more intuitive diagnoses of the breakdown than do others. The paper concludes with some morals about the nature of validity and about a possible alternative to the idea that mathematical theories are indefinitely extensible.

Under review

Professor Field is one of the leading advocates of the Deflationary Theory of Truth and his views are among the most challenging ones at the turn of the century. This papers tries to tackle one of the most difficult and most important Philosophical issues of the XXth century.

Posted by Tony Marmo at 00:01 BST
Updated: Thursday, 31 August 2006 23:22 BST
Thursday, 24 August 2006

Topic: Interconnections

Semantic computations of truth, based on associations already learned 

By Patrick Suppes & Jean-Yves Beziau

In this article we try to give an account of how one determines the truth or falsity of sentences like: Paris is the capital of France, Paris is not the capital of France, Rome is the capital of France. We want to describe the computations underlying the answers given, taking into account, at least in a qualitative way, the time factor what psychologists call the latency of a response. Our theory should be able to explain the data gathered by experimentation, for example, why it takes more time to give a negative answer than a positive one, be it true or false. But the important theoretical question is what is the actual method of computation, a problem not ordinarily considered in philosophical theories of truth, but also not subject to direct empirical observation.

Posted by Tony Marmo at 04:01 BST
Updated: Thursday, 24 August 2006 04:06 BST
Wednesday, 9 August 2006

Topic: Interconnections

Intensional Models for the Theory of Types

By Reinhard Muskens

In this paper we define intensional models for the classical theory of types, thus arriving at an intensional type logic ITL. Intensional models generalize Henkin's general models and have a natural definition. As a class they do not validate the axiom of Extensionality. We give a cut-free sequent calculus for type theory and show completeness of this calculus with respect to the class of intensional models via a model existence theorem. After this we turn our attention to applications. Firstly, it is argued that, since ITL is truly intensional, it can be used to model ascriptions of propositional attitude without predicting logical omniscience. In order to illustrate this a small fragment of English is defined and provided with an ITL semantics. Secondly, it is shown that ITL models contain certain objects that can be identified with possible worlds. Essential elements of modal logic become available within classical type theory once the axiom of Extensionality is given up.

Source: Semantics Archive, To appear in the The Journal of Symbolic Logic


Posted by Tony Marmo at 18:08 BST
Updated: Thursday, 24 August 2006 04:07 BST
Wednesday, 26 July 2006

Topic: Cognition & Epistemology


By Peter Murphy

This paper looks at an argument strategy for assessing the epistemic closure principle. This is the principle that says knowledge is closed under known entailment; or (roughly) if S knows p and S knows that p entails q, then S knows that q. The strategy in question looks to the individual conditions on knowledge to see if they are closed. According to one conjecture, if all the individual conditions are closed, then so too is knowledge. I give a deductive argument for this conjecture. According to a second conjecture, if one (or more) condition is not closed, then neither is knowledge. I give an inductive argument for this conjecture. In sum, I defend the strategy by defending the claim that knowledge is closed if, and only if, all the conditions on knowledge are closed. After making my case, I look at what this means for the debate over whether knowledge is closed.

Forthcoming in Erkenntnis

Posted by Tony Marmo at 17:41 BST
Saturday, 8 July 2006


Scopal Independence:

A Note on Branching and Wide Scope Readings of Indefinites and Disjunctions

By Philippe Schlenker

Hintikka claimed in the 1970s that indefinites and disjunctions give rise to 'branching readings' that can only be handled by a 'game-theoretic' semantics as expressive as a logic with (a limited form of) quantification over Skolem functions. Due to empirical and methodological difficulties, the issue was left unresolved in the linguistic literature. Independently, however, it was discovered in the 1980s that, contrary to other quantifiers, indefinites may scope out of syntactic islands. We claim [here] that branching readings and the island-escaping behavior of indefinites are two sides of the same coin: when the latter problem is considered in full generality, a mechanism of 'functional quantification' (Winter 2004) must be postulated which is strictly more expressive than Hintikka's, and which predicts that his branching readings are indeed real, although his own solution was insufficiently general. Furthermore, we suggest that, as Hintikka had seen, disjunctions share the behavior of indefinites, both with respect to island-escaping behavior and (probably) branching readings. The functional analysis can thus naturally be extended to them.

Source: Institut Jean-Nicod.
To appear in Journal of Semantics.

Posted by Tony Marmo at 03:43 BST
Updated: Saturday, 8 July 2006 03:56 BST
Friday, 30 June 2006


Logic Inference in Polynomial Format

By Walter Carnielli

The methods described in this paper have a promising potential to any truth-functional multi-valued logic: there is an exciting area of research in designing new proof theory techniques for such logics, and simplifying applications to multi-valued logics in decision tables and discovering patterns, as in several other fields (it is well-known that multi-valued logics find applications in artificial intelligence, database theory and data mining, modeling reasoning and model checking, for instance). It is important to emphasize that the method is also plainly applicable to non-finite valued logics, and also to represent binary semantics for many-valued logics5 (cf. [13]) and even to quantum circuits and quantum gates (cf. [1]). The arguments advanced here try to conceptualize this approach, in particular when extended to quantification and non-finite valued logics, as inheritance of an admirable legacy in the mathematical thinking, which may have been disregarded by logicians.

Source: CLE e-prints

Posted by Tony Marmo at 02:41 BST
Updated: Friday, 30 June 2006 02:42 BST
Thursday, 15 June 2006


Meaning and Dialogue Coherence: A Proof-theoretic Investigation

By Paul Piwek

This paper presents a novel proof-theoretic account of dialogue coherence. It focuses on cooperative information-oriented dialogues and describes how the structure of such dialogues can be accounted for in terms of a multi-agent hybrid inference system that mixes natural deduction with information transfer and observation. We show how the structure of dialogue arises out of the interplay between the inferential roles of logical connectives (i.e., sentence semantics), a rule for transferring information between agents, and rules for information flow between agents and their environment. Our order of explanation is opposite in direction to that adopted in the game-theoretic semantics tradition, where sentence semantics (or a notion of valid inferences) is derived from (winning) dialogue strategies. The approaches may, however, be reconcilable, since we focus on cooperative dialogues, whereas the latter concentrates on adversarial dialogue.

Keywords: natural deduction, dialogue, coherence, hybrid inference

In: Proceedings of ESSLLI Workshop on Coherence in Generation and Dialogue, M'alaga, Spain, 2006, pp. 57-64.
Source: Semantics Archive

Posted by Tony Marmo at 16:31 BST
Saturday, 10 June 2006


Modal Deduction in Second-Order Logic and Set Theory-I

By Johan van Benthem, Giovanna D'Agostino, Angelo Montanari, Alberto Policriti

We investigate modal deduction through translation into standard logic and set theory. Derivability in the minimal modal logic is captured precisely by translation into a weak, computationally attractive set theory \Omega. This approach is shown equivalent to working with standard first-order translations of modal formulas in a theory of general frames. Next, deduction in a more powerful second?order logic of general frames is shown equivalent with set?theoretic derivability in an `admissible variant' of \Omega. Our methods are mainly model?theoretic and set?theoretic, and they admit extension to richer languages than that of basic modal logic. Read more [1] [2]; [3]

Appeared in Journal of Logic and Computation 1997 7(2):251-265

Modal Deduction in Second-Order Logic and Set Theory - II

By Johan van Benthem, Giovanna D'Agostino, Angelo Montanari, Alberto Policriti

In this paper, we generalize the set-theoretic translation method for poly-modal logic introduced in [11] to extended modal logics. Instead of devising an ad-hoc translation for each logic, we develop a general framework within which a number of extended modal logics can be dealt with. We first extend the basic set-theoretic translation method to weak monadic second-order logic through a suitable change in the underlying set theory that connects up in interesting ways with constructibility; then, we show how to tailor such a translation to work with specific cases of extended modal logics.

Keywords: Modal Logic; Modal Deduction; Translation Methods; Second-Order Logic; Set Theory

Appeared in Studia Logica, Volume 60, Number 3, May 1998, pp. 387-420(34)

Modal Logic and Set Theory: a Set-Theoretic Interpretation of Modal Logic

Giovanna D’Agostino, Angelo Montanari, and Alberto Policriti

In this paper, we describe a novel set-theoretic interpretation of modal logic and show how it allows us to build promising bridges between modal deduction and set -theoretic reasoning. More specifically, we describe a translation technique that maps modal formulae into set-theoretic terms, thus making it possible to successfully exploit derivability in first-order set theories to implement derivability in modal logic.

Appeared in JFAK, a collection of essays dedicated to Johan van Benthem on the occasion of his 50th birthday, on June 12, 1999 (Edited by Jelle Gerbrandy et al.)

Posted by Tony Marmo at 00:01 BST
Updated: Saturday, 10 June 2006 03:38 BST
Monday, 5 June 2006


On Aristotle and Baldness- Topic, Reference, Presupposition, and Negation

By Johan Brandtler

This paper is a contribution to the never settled debate on reference, negation and presupposition of existence in the linguistic/philosophical literature. Based on Swedish and English data, the discussion is an attempt to present a unified account of the opposing views put forward in the works of Aristotle, Frege (1892), Russell (1905) and Strawson (1950). The starting point is the observed asymmetry in Swedish (and English) that negation may precede a quantified subject NP in the first position, but not a definite subject NP or a proper name. This asymmetry is argued to be due to semantic, rather than syntactic, restrictions. In the model proposed here, negating a topic NP affects the “topic selection”. This is allowed with quantified NPs, since negating a quantifier leads only to a modification of the topic selection. For definite/generic subject NPs this cannot be allowed, since negating a definite NP equals cancelling the topic selection. This leads to a ‘crash’ at the semantic level.

keywords: negation, presupposition, reference, topic, aristotle, frege, russell, strawson, quantifiers, semantics

Published in: Working Papers in Scandinavian Syntax, volume 77 (2006), 177-204. Lund University, Sweden.

Source: LingBuzz/000281

Posted by Tony Marmo at 18:32 BST
Thursday, 25 May 2006

Topic: Ontology&possible worlds

Eventism and Pointism

By Zdzislaw Augustynek

The domain of contemporary physics consists of two different classes of objects:
a) physical objects ? point events (shortly ? events), elementary particles (and their aggregates), and fields;
b) spatio-temporal objects ? space-time points (shortly ? points), moments, space points, and their corresponding sets: space-time, time and physical space.

If objects of some kind (physical or spatio-temporal) are treated as individuals, i.e. nonsets, then it is possible to define the remaining kinds of objects from both above-mentioned classes. In this way one can construct two alternative monistic ontologies of physics: eventism founded on events, and pointism founded on points. It is also possible to establish a dualistic ontology of physics, based both on events and points treated as individuals.
In this paper these three ontologies are presented with particular emphasis on some extreme versions of monistic ontologies. I shall compare them considering both their respective advantages and difficulties and trying to justify my own choice of eventistic ontology.

Source: Logic and Logical Philosophy, No. 1, 1993, pp. 169

Posted by Tony Marmo at 17:19 BST
Updated: Thursday, 25 May 2006 17:22 BST

Newer | Latest | Older