Many efforts have been made in recent years to construct formal systems for mechanizing general mathematical reasoning. Most of these systems are based on logics which are stronger than first-order logic. However, there are good reasons to avoid using full second-order logic for this task. In this work we investigate a logic which is intermediate between FOL and SOL, and seems to be a particularly attractive alternative to both: ancestral logic. This is the logic which is obtained from FOL by (...) augmenting it with the transitive closure operator. While the study of this logic has so far been mostly model-theoretical, this work is devoted to its proof theory. Two natural Gentzen-style proof systems for ancestral logic are presented: one for the reflexive transitive closure, and one for the non-reflexive one. We show that these systems are sound for ancestral logic and provide evidence that they indeed encompass all forms of reasoning for this logic that are used in practice. The two systems are shown to be equivalent by providing translation algorithms between them. We end with an investigation of two main proof-theoretical properties: cut elimination and constructive consistency proof. (shrink)

We introduce quantificational modal operators as dynamic modalities with (extensions of) Henkin quantifiers as indices. The adoption of matrices of indices (with action identifiers, variables and/or quantified variables as entries) gives an expressive formalism which is here motivated with examples from the area of multi-agent systems. We study the formal properties of the resulting logic which, formally speaking, does not satisfy the normality condition. However, the logic admits a semantics in terms of (an extension of) Kripke structures. As a consequence, (...) standard techniques for normal modal logic become available. We apply these to prove completeness and decidability, and to extend some standard frame results to this logic. (shrink)

We show that a coherent theory of partially ordered connectives can be developed along the same line as partially ordered quantification. We estimate the expressive power of various partially ordered connectives and use methods like Ehrenfeucht games and infinitary logic to get various undefinability results.

Logics in which a relation R is semantically incomplete in a particular universe E, i.e. the union of the extension of R with its anti-extension does not exhaust the whole universe E, have been studied quite extensively in the last years. (Cf. van Benthem (1985), Blamey (1986), and Langholm (1988), for partial predicate logic; Muskens (1996), for the applications of partial predicates to formal semantics, and Doherty (1996) for applications to modal logic.) This is not so with semantically incomplete generalized (...) quantifiers which constitute the subject of the present paper. The only systematic study of these quantifiers from a purely logical point of view, is, to the best of my knowledge, that by van Eijck (1995). We shall take here a different approach than that of van Eijck and mention some of the abstract properties of the resulting logic. Finally we shall prove that the two approaches are interdefinable. (shrink)

Connections between partially ordered connectives and Henkin quantifiers are considered. It is proved that the logic with all partially ordered connectives and the logic with all Henkin quantifiers coincide. This implies that the hierarchy of partially ordered connectives is strongly hierarchical and gives several nondefinability results between some of them. It is also deduced that each Henkin quantifier can be defined by a quantifier of the form equation imagewhat is a strengthening of the Walkoe result. MSC: 03C80.

Dependence logic and its many variants are new logics that aim at establishing a unified logical theory of dependence and independence underlying seemingly unrelated subjects. The area of dependence logic has developed rapidly in the past few years. We will give a short introduction to dependence logic and review some of the recent developments in the area.

For deductive reasoning to be justified, it must be guaranteed to preserve truth from premises to conclusion; and for it to be useful to us, it must be capable of informing us of something. How can we capture this notion of information content, whilst respecting the fact that the content of the premises, if true, already secures the truth of the conclusion? This is the problem I address here. I begin by considering and rejecting several accounts of informational content. I (...) then develop an account on which informational contents are indeterminate in their membership. This allows there to be cases in which it is indeterminate whether a given deduction is informative. Nevertheless, on the picture I present, there are determinate cases of informative (and determinate cases of uninformative) inferences. I argue that the model I offer is the best way for an account of content to respect the meaning of the logical constants and the inference rules associated with them without collapsing into a classical picture of content, unable to account for informative deductive inferences. (shrink)

Henkin quantifiers have been introduced in Henkin (1961). Walkoe (1970) studied basic model-theoretical properties of an extension $L_{*}^{1}$ (H) of ordinary first-order languages in which every sentence is a first-order sentence prefixed with a Henkin quantifier. In this paper we consider a generalization of Walkoe's languages: we close $L_{*}^{1}$ (H) with respect to Boolean operations, and obtain the language L¹(H). At the next level, we consider an extension $L_{*}^{2}$ (H) of L¹(H) in which every sentence is an L¹(H)-sentence prefixed with (...) a Henkin quantifier. We repeat this construction to infinity. Using the (un)definability of truth - in - N for these languages, we show that this hierarchy does not collapse. In addition, we compare some of the present results to the ones obtained by Kripke (1975), McGee (1991), and Hintikka (1996). (shrink)