On the Consistency of the Δ1 1-CA Fragment of Frege's Grundgesetze

It is well known that Frege's system in the Grundgesetze der Arithmetik is formally inconsistent. Frege's instantiation rule for the second-order universal quantifier makes his system, except for minor differences, full (i.e., with unrestricted comprehension) second-order logic, augmented by an abstraction operator that abides to Frege's basic law V. A few years ago, Richard Heck proved the consistency of the fragment of Frege's theory obtained by restricting the comprehension schema to predicative formulae. He further conjectured that the more encompassing ¹ ₁-comprehension schema would already be inconsistent. In the present paper, we show that this is not the case.     

Sea lions and equivalence: expanding classes by exclusion

Experiments have shown that human and nonhuman subjects are capable of performing new arbitrary stimulus-stimulus relations without error. When subjects that are experienced with matching-to-sample procedures are presented with a novel sample, a novel comparison, and a familiar comparison, most respond by correctly selecting the novel comparison in the presence of the new sample. This exclusion paradigm was expanded with two California sea lions that had previously formed two 10-member equivalence classes in a matching-to-sample procedure. Rather than being presented with a novel sample on a given trial, the sea lions were presented with a randomly selected familiar member of one class as the sample. One of the comparisons was a randomly selected familiar member of the alternative class, and the other was a novel stimulus. When required to choose which comparison matched the sample, the subjects reliably rejected the familiar comparison, and instead selected the unfamiliar one. Next, the sea lions were presented with transfer problems that could not be solved by exclusion; they immediately grouped the new stimuli into the appropriate classes. These findings show that exclusion procedures can rapidly generate new stimulus relations that can be used to expand stimulus classes.     

Classical Non-Associative Lambek Calculus

We introduce non-associative linear logic, which may be seen as the classical version of the non-associative Lambek calculus. We define its sequent calculus, its theory of proof-nets, for which we give a correctness criterion and a sequentialization theorem, and we show proof search in it is polynomial.     

A Tale of Four Grammars

In this paper we consider the relations existing between four deductive systems that have been called categorial grammars and have relevant connections with linguistic investigations: the syntactic calculus, bilinear logic, compact bilinear logic and Curry's semantic calculus.     

Entailment with Near Surety of Scaled Assertions of High Conditional Probability

An assertion of high conditional probability or, more briefly, an HCP assertion is a statement of the type: The conditional probability of B given A is close to one. The goal of this paper is to construct logics of HCP assertions whose conclusions are highly likely to be correct rather than certain to be correct. Such logics would allow useful conclusions to be drawn when the premises are not strong enough to allow conclusions to be reached with certainty. This goal is achieved by taking Adams" (1966) logic, changing its intended application from conditionals to HCP assertions, and then weakening its criterion for entailment. According to the weakened entailment criterion, called the Criterion of Near Surety and which may be loosely interpreted as a Bayesian criterion, a conclusion is entailed if and only if nearly every model of the premises is a model of the conclusion. The resulting logic, called NSL, is nonmonotonic. Entailment in this logic, although not as strict as entailment in Adams" logic, is more strict than entailment in the propositional logic of material conditionals. Next, NSL was modified by requiring that each HCP assertion be scaled; this means that to each HCP assertion was associated a bound on the deviation from 1 of the conditional probability that is the subject of the assertion. Scaling of HCP assertions is useful for breaking entailment deadlocks. For example, it it is known that the conditional probabilities of C given A and of ¬ C given B are both close to one but the bound on the former"s deviation from 1 is much smaller than the latter"s, then it may be concluded that in all likelihood the conditional probability of C given A B is close to one. The resulting logic, called NSL-S, is also nonmonotonic. Despite great differences in their definitions of entailment, entailment in NSL is equivalent to Lehmann and Magidor"s rational closure and, disregarding minor differences concerning which premise sets are considered consistent, entailment in NSL-S is equivalent to entailment in Goldszmidt and Pearl"s System-Z ⁺. Bacchus, Grove, Halpern, and Koller proposed two methods of developing a predicate calculus based on the Criterion of Near Surety. In their random-structures method, which assumed a prior distribution similar to that of NSL, it appears possible to define an entailment relation equivalent to that of NSL. In their random-worlds method, which assumed a prior distribution dramatically different from that of NSL, it is known that the entailment relation is different from that of NSL.     

The "Natural" and the "Formal"

The paper presents an argument against a metaphysical conception of logic according to which logic spells out a specific kind of mathematical structure that is somehow inherently related to our factual reasoning. In contrast, it is argued that it is always an empirical question as to whether a given mathematical structure really does captures a principle of reasoning. (More generally, it is argued that it is not meaningful to replace an empirical investigation of a thing by an investigation of its a priori analyzable structure without paying due attention to the question of whether it really is the structure of the thing in question.) It is proposed to elucidate the situation by distinguishing two essentially different realms with which our reason must deal: the realm of the natural, constituted by the things of our empirical world, and the realm of the formal, constituted by the structures that we use as prisms to view, to make sense of, and to reconstruct the world. It is suggested that this vantage point may throw light on many foundational problems of logic.     

Partiality and Its Dual

This paper explores allowing truth value assignments to be undetermined or "partial" (no truth values) and overdetermined or "inconsistent" (both truth values), thus returning to an investigation of the four-valued semantics that I initiated in the sixties. I examine some natural consequence relations and show how they are related to existing logics, including ukasiewicz's three-valued logic, Kleene's three-valued logic, Anderson and Belnap's (first-degree) relevant entailments, Priest's "Logic of Paradox", and the first-degree fragment of the Dunn-McCall system "R-mingle". None of these systems have nested implications, and I investigate twelve natural extensions containing nested implications, all of which can be viewed as coming from natural variations on Kripke's semantics for intuitionistic logic. Many of these logics exist antecedently in the literature, in particular Nelson's "constructible falsity".     

Investigation into Combinatory Systems with Dual Combinators

Combinatory logic is known to be related to substructural logics. Algebraic considerations of the latter, in particular, algebraic considerations of two distinct implications (, ), led to the introduction of dual combinators in Dunn & Meyer 1997. Dual combinators are "mirror images" of the usual combinators and as such do not constitute an interesting subject of investigation by themselves. However, when combined with the usual combinators (e.g., in order to recover associativity in a sequent calculus), the whole system exhibits new features. A dual combinatory system with weak equality typically lacks the Church-Rosser property, and in general it is inconsistent. In many subsystems terms "unexpectedly" turn out to be weakly equivalent. The paper is a preliminary attempt to investigate some of these issues, as well as, briefly compare function application in symmetric -calculus (cf. Barbanera & Berardi 1996) and dual combinatory logic.