Natural deduction with general elimination rules

The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates. Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001     

Distributive-Lattice Semantics of Sequent Calculi with Structural Rules

The goal of the paper is to develop a universal semantic approach to derivable rules of propositional multiple-conclusion sequent calculi with structural rules, which explicitly involve not only atomic formulas, treated as metavariables for formulas, but also formula set variables (viz., metavariables for finite sets of formulas), upon the basis of the conception of model introduced in (Fuzzy Sets Syst 121(3):27–37, 2001). One of the main results of the paper is that any regular sequent calculus with structural rules has such class of sequent models (called its semantics) that a rule is derivable in the calculus iff it is sound with respect to each model of the semantics. We then show how semantics of admissible rules of such calculi can be found with using a method of free models. Next, our universal approach is applied to sequent calculi for many-valued logics with equality determinant. Finally, we exemplify this application by studying sequent calculi for some of such logics.      

A normalizing system of natural deduction for intuitionistic linear logic

 The main result of this paper is a normalizing system of natural deduction for the full language of intuitionistic linear logic. No explicit weakening or contraction rules for -formulas are needed. By the systematic use of general elimination rules a correspondence between normal derivations and cut-free derivations in sequent calculus is obtained. Normalization and the subformula property for normal derivations follow through translation to sequent calculus and cut-elimination. Received: 10 October 2000 / Revised version: 26 July 2001 / Published online: 2 September 2002 Mathematics Subject Classification (2000): 03F52, 03F05 Keywords or phrases: Linear logic – Natural deduction – General elimination rules     

Ploucquet’s “Refutation” of the Traditional Square of Opposition

In the 18th century, Gottfried Ploucquet developed a new syllogistic logic where the categorical forms are interpreted as set-theoretical identities, or diversities, between the full extension, or a non-empty part of the extension, of the subject and the predicate. With the help of two operators ‘O’ (for “Omne”) and ‘Q’ (for “Quoddam”), the UA and PA are represented as ‘O(S) – Q(P)’ and ‘Q(S) – Q(P)’, respectively, while UN and PN take the form ‘O(S) > O(P)’ and ‘Q(S) > O(P)’, where ‘>’ denotes set-theoretical disjointness. The use of the symmetric operators ‘–’ and ‘>’ gave rise to a new conception of conversion which in turn lead Ploucquet to consider also the unorthodox propositions O(S) – O(P), Q(S) – O(P), O(S) > Q(P), and Q(S) > Q(P). Although Ploucquet’s critique of the traditional theory of opposition turns out to be mistaken, his theory of the “Quantification of the Predicate” is basically sound and involves an interesting “Double Square of Opposition”. My thanks are due to Hanno von Wulfen for helpful discussions and for transforming the word-document into a Latex-file.     

Normal deduction in the intuitionistic linear logic

We describe a natural deduction system NDIL for the second order intuitionistic linear logic which admits normalization and has a subformula property. NDIL is an extension of the system for !-free multiplicative linear logic constructed by the author and elaborated by A. Babaev. Main new feature here is the treatment of the modality !. It uses a device inspired by D. Prawitz' treatment of S4 combined with a construction introduced by the author to avoid cut-like constructions used in -elimination and global restrictions employed by Prawitz. Normal form for natural deduction is obtained by Prawitz translation of cut-free sequent derivations. Received: March 29, 1996     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.     

Basic Propositional Calculus II. Interpolation

Let ℒ and ? be propositional languages over Basic Propositional Calculus, and ℳ = ℒ∩?. Weprove two different but interrelated interpolation theorems. First, suppose that Π is a sequent theory over ℒ, and Σ∪ {C⇒C′} is a set of sequents over ?, such that Π,Σ⊢C⇒C′. Then there is a sequent theory Φ over ℳ such that Π⊢Φ and Φ, Σ⊢C⇒C′. Second, let A be a formula over ℒ, and C ₁, C ₂ be formulas over ?, such that A∧C ₁⊢C ₂. Then there exists a formula B over ℳ such that A⊢B and B∧C ₁⊢C ₂. Received: 7 January 1998 / Published online: 18 May 2001     

The Lagrange-D’Alembert-Poincaré equations and integrability for the Euler’s disk

Nonholonomic systems are described by the Lagrange-D’Alembert’s principle. The presence of symmetry leads, upon the choice of an arbitrary principal connection, to a reduced D’Alembert’s principle and to the Lagrange-D’Alembert-Poincaré reduced equations. The case of rolling constraints has a long history and it has been the purpose of many works in recent times. In this paper we find reduced equations for the case of a thick disk rolling on a rough surface, sometimes called Euler’s disk, using a 3-dimensional abelian group of symmetry. We also show how the reduced system can be transformed into a single second order equation, which is an hypergeometric equation.     

On generalized Ekeland’s variational principle and equivalent formulations for set-valued mappings

We propose a very weak type of generalized distances called a weak τ-function and use it to weaken the assumptions about lower semicontinuity in existing versions of Ekeland’s variational principle and equivalent formulations.     

Theories with constants and three countable models

We prove that a countable, complete, first-order theory with infinite dcl() and precisely three non-isomorphic countable models interprets a variant of Ehrenfeucht’s or Peretyatkin’s example.     

A generalization of Müller’s iteration method based on standard information

For finding a root of a function f, Müler’s method is a root-finding algorithm using three values of f in every step. The natural values available are values of f and values of its first number of derivatives, called standard information. Based on standard information, we construct an iteration method with maximal order of convergence. It is a natural generalization of Müller’s iteration method. This work was partially supported by National Natural Science Foundation of China (Grant No. 10471128), NSFC (Grant No. 10731060).     

Heterogeneous cost sharing, the directional serial rule

The directional serial rule is introduced as a natural serial extension, generalizing the Moulin–Shenker cost sharing rule to heterogeneous cost sharing models. It is the unique regular rule compatible with the radial serial principle. In particular, this shows the incompatibility of the serial principle with differentiability of a cost sharing rule as a function of the individual demands.I would like to thank the editor and the referee for their comments which have been most useful.     

Strong normalization results by translation

We prove the strong normalization of full classical natural deduction (i.e. with conjunction, disjunction and permutative conversions) by using a translation into the simply typed λμ-calculus. We also extend Mendler’s result on recursive equations to this system.     

On Ha＇s Version of Set-valued Ekeland＇s Variational Principle

By using the concept of cone extensions and Dancs-Hegedus-Medvegyev theorem, Ha [Some variants of the Ekeland variational principle for a set-valued map. J. Optim. Theory Appl., 124, 187–206 (2005)] established a new version of Ekeland’s variational principle for set-valued maps, which is expressed by the existence of strict approximate minimizer for a set-valued optimization problem. In this paper, we give an improvement of Ha’s version of set-valued Ekeland’s variational principle. Our proof is direct and it need not use Dancs-Hegedus-Medvegyev theorem. From the improved Ha’s version, we deduce a Caristi-Kirk’s fixed point theorem and a Takahashi’s nonconvex minimization theorem for set-valued maps. Moreover, we prove that the above three theorems are equivalent to each other.     

Towards a More General Concept of Inference

The main objective of this paper is to sketch unifying conceptual and formal framework for inference that is able to explain various proof techniques without implicitly changing the underlying notion of inference rules. We base this framework upon the so-called two-dimensional, i.e., deduction to deduction, account of inference introduced by Tichý in his seminal work The Foundation’s of Frege’s Logic (1988). Consequently, it will be argued that sequent calculus provides suitable basis for such general concept of inference and therefore should not be seen just as technical tool, but philosophically well-founded system that can rival natural deduction in terms of its “naturalness”.     

A nonalgebraic patchwork

Itenberg and Shustin’s pseudoholomorphic curve patchworking is in principle more flexible than Viro’s original algebraic one. It was natural to wonder if the former method allows one to construct nonalgebraic objects. In this paper we construct the first examples of patchworked real pseudoholomorphic curves in Σ _n whose position with respect to the pencil of lines cannot be realized by any real algebraic curve of the same bidegree. Both authors are very grateful to the Max Planck Institute für Mathematik in Bonn for its financial support and excellent working conditions.     

Fourier Inversion Formulas in Option Pricing and Insurance

Several authors have used Fourier inversion to compute prices of puts and calls, some using Parseval’s theorem. The expected value of max (S – K, 0) also arises in excess-of-loss or stop-loss insurance, and we show that Fourier methods may be used to compute them. In this paper, we take the idea of using Parseval’s theorem further: (1) formulas requiring weaker assumptions; (2) relationship with classical inversion theorems for probability distributions; (3) formulas for payoffs which occur in insurance. Numerical examples are provided.      

On Preserving

This paper examines the underpinnings of the preservationist approach to characterizing inference relations. Starting with a critique of the ‘truth-preservation’ semantic paradigm, we discuss the merits of characterizing an inference relation in terms of preserving consistency. Finally we turn our attention to the generalization of consistency introduced in the early work of Jennings and Schotch, namely the concept of level. The authors wish to acknowledge the support of SSHRCC under research grant 410-2005-1088.     

<Emphasis Type="Italic">V</Emphasis>-semirings

We investigate the semirings over which all simple semimodules are injective. In ring and module theory, the rings with an analogous condition are called V-rings. Therefore it is natural to call the semirings under consideration V-semirings. We obtain the semiring analogs of some well-known results on V-rings, including an analog of Kaplansky’s theorem on commutative V-rings.