This text is an outgrowth of notes prepared by J. Y. Girard for a course at the University of Paris VII. It deals with the mathematical background of the application to computer science of aspects of logic (namely the correspondence between proposition & types). Combined with the conceptual perspectives of Girard's ideas, this sheds light on both the traditional logic material & its prospective applications to computer science. The book covers a very active & exciting research area, & it will (...) be essential reading for all those working in logic & computer science. (shrink)

We present a single sequent calculus common to classical, intuitionistic and linear logics. The main novelty is that classical, intuitionistic and linear logics appear as fragments, i.e. as particular classes of formulas and sequents. For instance, a proof of an intuitionistic formula A may use classical or linear lemmas without any restriction: but after cut-elimination the proof of A is wholly intuitionistic, what is superficially achieved by the subformula property and more deeply by a very careful treatment of structural rules. (...) This approach is radically different from the one that consists in “changing the rule of the game” when we want to change logic, e.g. pass from one style of sequent to another: here, there is only one logic, which—depending on its use—may appear classical, intuitionistic or linear. (shrink)

These lectures on logic, more specifically proof theory, are basically intended for postgraduate students and researchers in logic. The question at stake is the nature of mathematical knowledge and the difference between a question and an answer, i.e., the implicit and the explicit. The problem is delicate mathematically and philosophically as well: the relation between a question and its answer is a sort of equality where one side is ``more equal than the other'': one thus discovers essentialist blind spots. Starting (...) with Godel's paradox --so to speak, the incompleteness of answers with respect to questions--the book proceeds with paradigms inherited from Gentzen's cut-elimination. Various settings are studied: sequent calculus, natural deduction, lambda calculi, category-theoretic composition, up to geometry of interaction, all devoted to explicitation, which eventually amounts to inverting an operator in a von Neumann algebra. Mathematical language is usually described as referring to a preexisting reality. Logical operations can be given an alternative procedural meaning: typically, the operators involved in GoI are invertible, not because they are constructed according to the book, but because logical rules are those ensuring invertibility. Similarly, the durability of truth should not be taken for granted: one should distinguish between imperfect and perfect modes. The procedural explanation of the infinite thus identifies it with the unfinished, i.e., the perennial. But is perenniality perennial? This questioning yields a possible logical explanation for algorithmic complexity. This highly original course on logic by one of the world's leading proof theorists challenges mathematicians, computer scientists, physicists, and philosophers to rethink their views and concepts on the nature of mathematical knowledge in an exceptionally profound way. (shrink)

Go back to An-fang, the Peace Square at An-Fang, the Beginning Place at An-Fang, where all things start (… ) An-Fang was near a city, the only living city with a pre-atomic name (… ) The headquarters of the People Programmer was at An-Fang, and there the mistake happened: A ruby trembled. Two tourmaline nets failed to rectify the laser beam. A diamond noted the error. Both the error and the correction went into the general computer. Cordwainer SmithThe Dead Lady (...) of Clown Town, 1964. (shrink)

Ludics [1] is a novel approach to logic—especially proof-theory. The present introduction emphasises foundational issues.For ages, not a single disturbing idea in the area of “foundations”: the discussion is sort of ossified—as if everything had been said, as if all notions had taken their definite place, in a big cemetery of ideas. One can still refresh the flowers or regild the stone, e.g., prove technicalities, sometimes non-trivial; but the real debate is still: this paper begins with an autopsy, the autopsy (...) of the foundational project.Up to say 1900, the realist/dualist approach to science was dominant; during the last century some domains like physics evolved so as to become completely anti-realist; but this evolution hardly concerned logic.By the turn of the XXth century mathematics was jeopardised by paradoxes, the most famous of them being due to Russell. Hilbert's reaction was to focus on consistency. But the reduction of paradoxes—and therefore of foundations—to solely the antinomies is highly questionable: indeed, the typical paradoxical artifacts are secret sharers, objects satisfying the formal definitions but far astray from the intended meaning, typically the Peano “curve” which contradicts our perception of dimension. Fortunately, topology has been able to show that dimension m is not the same as dimension n … but just for a second, forget this and imagine consistent mathematics in which balls in any dimension are homeomorphic: what a disaster! This exclusive focus on consistency—not to speak of the strategic failure of the Programme—should explain why logic, especially foundations lost contact with other sciences during last century. (shrink)

Linear logic, introduced in 1986 by J.-Y. Girard, is based upon a fine grain analysis of the main proof-theoretical notions of logic. The subject develops along the lines of denotational semantics, proof nets and the geometry of interaction. Its basic dynamical nature has attracted computer scientists, and various promising connections have been made in the areas of optimal program execution, interaction nets and knowledge representation. This book is the refereed proceedings of the first international meeting on linear logic held at (...) Cornell University, in June 1993. Survey papers devoted to specific areas of linear logic, as well as an extensive general introduction to the subject by J.-Y. Girard, have been added, so as to make this book a valuable tool both for the beginner and for the advanced researcher. (shrink)

We study increasing F-sequences, where F is a dilator: an increasing F-sequence is a sequence (indexed by ordinal numbers) of ordinal numbers, starting with 0 and terminating at the first step x where F(x) is reached (at every step x + 1 we use the same process as in decreasing F-sequences, cf. [2], but with "+ 1" instead of "- 1"). By induction on dilators, we shall prove that every increasing F-sequence terminates and moreover we can determine for every dilator (...) F the point where the increasing F-sequence terminates. We apply these results to inverse Goodstein sequences, i.e. increasing (1 + Id) (ω) -sequences. We show that the theorem every inverse Goodstein sequence terminates (a combinatorial theorem about ordinal numbers) is not provable in ID 1 . For a general presentation of the results stated in this paper, see [1]. We use notions and results concerning the category ON (ordinal numbers), dilators and bilators, summarized in [2, pp. 25-31]. (shrink)

L'expérience de la connaissance nous enseigne qu'il n'y a pas de Réalité Dernière, que tout train en cache un autre. Une évidence qu'il n'est pas facile d'accepter, d'où l'idée de ce train ultime, celui qui ne cacherait plus rien. La transparentisme postule l'existence, au-delà de la perception immédiate, d'un monde, d'un niveau de lecture, complètement intelligible, i.e, explicite et immédiat. D'où cette croyance en de prétendus "rayons X du savoir" qui nous dévoileraient l'envers de l'Univers.

L'expérience de la connaissance nous enseigne qu'il n'y a pas de Réalité Dernière, que tout train en cache un autre. Une évidence qu'il n'est pas facile d'accepter, d'où l'idée de ce train ultime, celui qui ne cacherait plus rien. La transparentisme postule l'existence, au-delà de la perception immédiate, d'un monde, d'un niveau de lecture, complètement intelligible, i.e, explicite et immédiat. D'où cette croyance en de prétendus "rayons X du savoir" qui nous dévoileraient l'envers de l'Univers.

Dans cet article, on utilise la théorie des dilatateurs pour décrire les premiers récursivement inaccessible et Mahlo.