We show that the bounded fragment of first-order logic and the hybrid language with ‘downarrow’ and ‘at’ operators are equally expressive even with polyadic modalities, but that their ‘positive’ fragments are equally expressive only for unary modalities.

The concept of the (full) unfolding of a schematic system is used to answer the following question: Which operations and predicates, and which principles concerning them, ought to be accepted if one has accepted ? The program to determine for various systems of foundational significance was previously carried out for a system of nonfinitist arithmetic, ; it was shown that is proof-theoretically equivalent to predicative analysis. In the present paper we work out the unfolding notions for a basic schematic system of finitist arithmetic, , and for an extension of that by a form of the so-called Bar Rule. It is shown that and are proof-theoretically equivalent, respectively, to Primitive Recursive Arithmetic, , and to Peano Arithmetic, .

Finitism is given an interpretation based on two ideas about strings (sequences of symbols): a replacement principle extracted from Hilbert’s work and a counting principle inspired by Tait. These principles are used to justify an equational arithmetic based on the algebra of lower elementary functions. The extension of this algebra to Grzegorczyk’s class ɛ2 can be justified by means of an additional finitistic choice principle, thus obtaining a second equational theory . It is unknown whether is strictly stronger than since ɛ2 may coincide with the class of lower elementary functions.

If the objects of arithmetic are taken to be binary numerals instead of tally numerals, then it becomes possible to provide a finitistic justification for a theory that may be incomparable to (neither of the two includes the other). I conclude by suggesting that the equational theory of Kalmar elementary functions is a strict upper bound for finitistic arithmetic.

We study a generalization of the standard syntax and game-theoretic semantics of logic, which is based on a duality between two players, to a multiplayer setting. We define propositional and modal languages of multiplayer formulas, and provide them with a semantics involving a multiplayer game. Our focus is on the notion of equivalence between two formulas, which is defined by saying that two formulas are equivalent if under each valuation, the set of players with a winning strategy is the same in the two respective associated games. We provide a derivation system which enumerates the pairs of equivalent formulas, both in the propositional case and in the modal case. Our approach is algebraic: We introduce multiplayer algebras as the analogue of Boolean algebras, and show, as the corresponding analog to Stone’s theorem, that these abstract multiplayer algebras can be represented as concrete ones which capture the game-theoretic semantics. For the modal case we prove a similar result. We also address the computational complexity of the problem whether two given multiplayer formulas are equivalent. In the propositional case, we show that this problem is co-NP-complete, whereas in the modal case, it is PSPACE-hard.

We study the logical structure of ‘real’ relations, and in particular the notion of occurrences of objects in a state. We start with formulating a number of principles for occurrences and defining corresponding mathematical models. These models are analyzed to get more insight in the formal properties of occurrences. In particular, we prove uniqueness results that tell us more about the possible logical structures relations might have.

Modern categorical logic as well as the Kripke and topological models of intuitionistic logic suggest that the interpretation of ordinary “propositional” logic should in general be the logic of subsets of a given universe set. Partitions on a set are dual to subsets of a set in the sense of the category-theoretic duality of epimorphisms and monomorphisms—which is reflected in the duality between quotient objects and subobjects throughout algebra. If “propositional” logic is thus seen as the logic of subsets of a universe set, then the question naturally arises of a dual logic of partitions on a universe set. This paper is an introduction to that logic of partitions dual to classical subset logic. The paper goes from basic concepts up through the correctness and completeness theorems for a tableau system of partition logic.