Séminaire interuniversitaire de logique mathématique (3ème cycle FNRS) Sauf mention contraire, le cours de DEA et les séminaires de l'après-midi ont lieu à l'ULB, Campus de la Plaine, au local 2NO906. Un itinéraire (bilingue) est disponible. Ce programme est accessible à l'adresse http://www.umh.ac.be/math/logic/seminars.htm.

Résumés:

• Arnaud MAES (UMH): Preuve par Chilakamarri, Hamburger et Pippert d'une conjecture de Grünbaum à propos des diagrammes de Venn

  En 1992, Grünbaum a conjecturé que tout diagramme de Venn formé de n courbes peut être étendu en un diagramme de n+1 courbes par l'adjonction d'une courbe simple. Nous présentons quelques aspects de la preuve apportée par Chilakamarri, Hamburger et Pippert en 1996.

• Armin RIGO (ULB) Catégories et Topos (d'après Lawvere)

  Cohen, par l'étude des modèles booléens, a ouvert la porte à l'exploration de l'univers de ZF. Lawvere a réussi à axiomatiser dans le langage des catégories les proprietés de ZF. Les deux approches se rejoignent dans la théorie des topos élémentaires: une large varieté de catégories (dont les catégories de faisceaux sur topologies de Grothendieck) se trouvent “fonctionner comme” ZF. Les topos sont donc une passerelle importante entre l'algèbre et la théorie des ensembles.

  Référence: R. Goldblatt, "Topoi, the categorial analysis of logic", studies in logic 98, North-Holland publishing company.

• Roland HINNION (ULB) Schémas de compréhension “à la Frege”: ensembles partiels, gloutons, positifs, stratifiés, doubles

  Le schéma total de compréhension (même sans axiome d'extensionnalité) est inconsistant. En dehors de la réponse pragmatique classique de Zermelo-Fraenkel aux paradoxes, il existe différentes théories dont le point commun est un principe syntaxique de sélection des formules admises dans le schéma de compréhension;curieusement,la plupart de ces théories sont faciles à modéliser sans extensionnalité, mais particulièrement coriaces avec extensionnalité. Voici une liste (probablement non exhaustive) des “types de compréhension” ou des “principes” concernés:

  • stratification (Quine & C°)
    
  • ensembles partiels (Gilmore & C°)
    
  • ensembles gloutons (ou paraconsistants)
    
  • compréhension positive (Malitz & C°)
    
  • ensembles doubles (Kisielewicz)
  De nombreux travaux récents explorent ces voies.

• Olivier ESSER (ULB) Cardinaux modérément ineffables

  La notion d'ineffabilité modérée que nous considérons dans cet exposé est une généralisation à P_\kappa \gamma de la proprieté de l'arbre pour les cardinaux. Nous verrons quelques applications, concernant notamment la complétion de Cauchy d'espaces \kappa-uniformes ainsi que la construction d'hyperunivers.

• Thierry LIBERT (ULB) Champs super-réels (d'après Woodin & Dales)

  Si E est un ensemble totalement ordonné,

  • le poids de E est, par définition, le plus petit cardinal d'une partie dense dans E;
    
  • E est de type êta-1 si, par définition, pour tout couple (A,B) de parties de E au plus dénombrables, et telles que chaque élément de A soit plus petit que chaque élément de B, il existe un élément de E coincé entre A et B.
  Ainsi, le corps ordonné des réels est de poids aleph O, mais n'est pas de type êta-1.
  Dans ZFC + GCH, je vais décrire les étapes de la construction d'un unique êta-1 corps ordonné réel-clos, Cauchy-complet, de poids aleph 1 (et de cardinalité aleph 2), qui constitue de la sorte une version ‘élargie’ des réels.

  Référence: H.G. Dales et W.H. Woodin: Super-Real Fields, Oxford Science Publications (1996)

• Olivier FRECON (ENS-Lyon) Les sous-groupes localement clos des groupes de rang de Morley fini

  Pour étudier les groupes de rang de Morley fini non nécessairement connexes, nous introduisons la notion de sous-groupe localement clos. Ces sous-groupes permettent de généraliser certains théorèmes connus pour les groupes résolubles connexes, aux groupes résolubles non nécessairement connexes. Par exemple, pour prouver qu'un groupe de rang de Morley fini résoluble possède une unique classe de conjugaison de sous-groupes de Carter (ie. sous-groupes localement nilpotents et autonormalisants), nous utilisons les sous-groupes localement clos

•  Cédric RIVIERE (UMH) Critère de Blum et construction de modèle-complétions de théories de corps différentiels par lifting

  Le critère de Blum est un outil très important pour la construction de la modèle-complétion d'une théorie universelle donnée. Le principe du lifting permet quant à lui d'obtenir la modèle-complétion d´une théorie de corps différentiels à partir de la théorie de corps correspondants. Nous utiliserons ici ces deux concepts afin de retrouver l'axiomatisation "simple" (due à Blum) de la théorie des corps différentiellement clos de caractéristique zéro (DCF0).

• Diderik BATENS (RUG): Extending the Realm of Logic. The Adaptive Logic Programme

  Much interesting actual reasoning cannot be understood in terms of logics of the usual type. The reason is twofold. First, much actual reasoning is non-monotonic. This means that a conclusion may be withdrawn in view of new information. Moreover, much actual reasoning is dynamic: a conclusion may be withdrawn in view of the increased understanding of the premises.

  To put it differently: much actual reasoning is affected by an external dynamics as well as by an internal dynamics. In both cases, a formerly drawn conclusion may be revoked. In the case of the external dynamics, the effect is caused by fact that new information is gained while the reasoning is going on. In the case of the internal dynamics, it is caused by the reasoning process itself: as it proceeds, our insight in the premises increases. The external dynamics (non-monotonicity) is a property of the inference relation. The internal dynamics only affects the actual reasoning, not the inference relation.

  This paper summarizes an approach to such forms of reasoning in strictly formal terms. The approach comprises a semantic characterization as well as a dynamic proof theory. The latter is essential for explicating a person's concrete reasoning processes. There are a number of technical complications, for example the absence of a positive test for derivability, and ways to solve them.

  This paper reports on a development that involves a drastic broadening of the scope of symbolic logic. The central idea concerns dynamic proofs that explicate forms of reasoning for which no positive test is available, but that are nevertheless sound and complete with respect to the the semantic characterization. Another central point is the articulation of a dynamic semantics that is characteristic for proofs at a stage.

• Véronique BRUYÈRE (UMH): Théorème de Kleene sur les ordres linéaires

  Dans cet exposé, on considère des mots indicés par des ordres linéaires, généralisant ainsi les mots finis, les mots infinis, les mots sur les ordinaux. On introduit des automates et des expressions rationnelles adaptés aux mots indicés par des ordres linéaires. Nous présentons un théorème de Kleene affirmant que ces deux concepts sont équivalents pour les ordres dénombrables dispersés.

• Raf CLUCKERS (KUL): Semi-algebraic p-adic Geometry and Presburger Arithmetic

  Recently the concept of the Grothendieck ring of a logical structure is defined; it is essentilally a general abstract Euler Characteristic on the definable sets. In this lecture we try to give a clear definition of this ring and we show that the Grothendieck ring of the p-adic field is a trivial ring. Further we give a criterium for the existence of a definable bijection between two definable sets, both for the p-adic field and the Presburger arithmetic. This leads to a classification of the definable sets up to definable bijection.

• Gunther CORNELISSEN (Max Planck Institute - Bonn): Diophantine sets and abelian varieties

  What is the nature of the set of integral (resp. rational) solutions to a set of polynomial equations when plotted in a suitable real space? For integral points, this question is settled by reinterpreting Matijsevich's result, whereas for rational points, there is only a conjecture of Mazur. A result of C. and Zahidi explains how a model-theoretic construction could be used to contradict this conjecture. It will then be explained how certain conjectures on abelian varieties would allow one to make such a construction.

• Marc DENECKER (KUL): Non-monotone inductive definitions as an epistemological foundation for Logic Programming

  Logic programming is a "logic" that was designed for computational purposes. A prototypical example of a logic program is the following:

  member(X,.(X,T)).
  member(X,.(Y,T))<- member(X,T)

  This may be interpreted as the inductive definition of the membership relationship of lists where lists are represented as e.g. .(a,.(b,.(c,[]))) = [a,b,c]. The first rule represents the primitive case that X is the head of the list, and the second rule represents the recursive case.

  There is a strong relationship between this type of monotone logic programs and standard treatments of monotone inductive definitions. In fact, there is almost an isomorphy (modulo syntactic sugar) between monotone inductive definition logics and the monotone subset of logic programming.

  But logic programming allows also nonmonotone recursion. For example,

  even(0).
  even(s(N)) <- not even(N).

  This can be understood as the inductive definition in the well-founded set of natural numbers:

  0 is even
  if n is not even then n+1 is even (otherwise n+1 is not even)

  Currently, there is no standard, universally accepted theory of non-monotone induction in mathematical logic. Two non-monotone extensions of standard monotone induction that exist are Iterated Inductive Definitions and Inflationary fixpoint logics. These theories are non-compatible. I will discuss the role of both forms of non-monotone induction in mathematics, and argue that the formal semantics that were proposed for logic programming correspond to iterated induction, and actually provide a superior formalisation of this form of induction. So, the "thesis" here is that logic programming with negation can be seen as a logic of generalised nonmonotone iterated induction.

  Another new result is the following. The study of (monotone) induction is strongly related to the study of fixpoints of (monotone) operators. Tarski's least fixpoint theory for monotone operators can be seen as the algebraic study of monotone induction. Recently, based on the work on semantics of logic programming and nonmonotonic logics, we developed Approximation Theory, an algebraic fixpoint theory for general non-monotone operators that extends Tarski's theory and that formalises iterated induction.

• Gregory DUBY (ULB): Automorphismes w-maximaux

  Un automorphisme w-maximal est un automorphisme dont toutes les puissances n'ont pas de points fixes sur les éléments non-algébriques. Dans cet exposé, j'établirai l'existence d'automorphisme w-maximaux dans des structures indénombrables et donnerai une construction explicite de tels automorphismes dans le cas dénombrable.

• Didier MISERCQUE (Institut MEURICE): Problème des mariages

  Une forme du problème des mariages est la suivante : Supposons que B et G soient deux ensembles disjoints dont les éléments sont appelés respectivement "garçons" et "filles". Soit R une relation de "connaissance" dans B U G, c'est-à-dire une relation symétrique telle que deux personnes qui se connaissent soient de sexes distincts. Peut-on marier tous les garçons de manière telle que chacun d'eux épouse une fille qu'il connaît (par R), tout en respectant la règle de monogamie à la fois pour les garçons et pour les filles.

  Nous verrons qu'il existe une condition nécessaire et suffisante pour qu'une réponse positive puisse être apportée à cette question dans les cas où B et G sont finis ou infinis dénombrables et où R est telle que chaque individu ne connaît qu'un nombre fini de personnes. Nous étudierons ensuite quelques variantes de ce problème (si l'on veut que chaque fille trouve un époux, si R est récursive,....) et nous verrons la liaison que l'on peut établir, dans chacun de ces cas et si B et G sont infinis, entre l'existence de solutions au problème des mariages et l'existence de branches infinies de certains arbres.

• Armin RIGO (ULB): Arbres compacts

  Certaines notions d'“assez grands” cardinaux sont reliées à la compacité en topologie générale (les cardinaux faiblement et fortement compacts, notamment). Certains résultats de compacités peuvent être raffinés en étudiant ces proprietés non plus seulement sur des cardinaux mais sur des ensembles ordonnés dirigés (cf Roland Hinnion). On parlera donc de ramifiabilité, ainsi que d'autres critères spécifiques aux ordres non lineaires.

  Quant aux arbres annoncés dans le titre, ils fournissent un point de vue intéressant sur ces notions.

• Michel RIGO (ULg): Systèmes de numération sur un langage régulier et ensembles reconnaissables

  Avec Pierre Lecomte, nous avons récemment introduit des systèmes de numération généralisant notamment les systèmes de numération de position construits sur un nombre de Pisot. Ces systèmes sont obtenus en ordonnant par ordre lexicographique croissant les mots d'un langage régulier infini. Cet ordre fournit une bijection entre l'ensemble des naturels et les mots du langage, un nombre est alors représente par le mot dont il est le numéro dans l'ordre lexicographique. Disposant de tels systèmes, on peut reformuler les questions relatives au systèmes classiques et liées aux ensembles d'entiers reconnaissables (un ensemble est dit reconnaissable si le langage forme des représentations des éléments de l'ensemble dans le système considère est un langage régulier). On passera en revue les premières propriétés de ces systèmes généralisés et on montrera en particulier que les ensembles reconnaissables dans les numérations basées sur un langage régulier et les prédicats morphiques, étudiés par Arnaud Maes, coïncident.

• Robert MEYER (Australian National University): The fools model of combinatory logic, release 2

  The idea is to beef up the old original Fools Model by passing to THEORIES in the restriction to ->& (adding a top Church T) of B+. Unlike Release 1 of the Fools Model, in sets of -> formulas alone, Release 2 verifies ALL PROVABLE EQUALITIES of weak CL and LAMBDA.
   
  My own interest in pressing this topic is that it captures, as you are aware, the Key to the Universe, the marvelous connection between Combinatory and Relevant Logic.
   
  

  ---

  This being not necessarily familiar to everybody, I add some background info on this topic. Abbreviations should be obvious, some are from TeX for some math symbols. Jacques Riche.
   
   One way to elucidate the relations between combinatory and various logics (in earlier investigations, implicationnal logics) is through the use of what Meyer calls the "Fool's model" of Combinatory Logic (CL) which, in itself, is already an interesting way of looking at CL.
   
  Without entering into unnecessary details here, let's say that the logic B+ is the positive part of some basic (and relatively weak) system B.
   
  Let us identify the language of a sentential logic with an appropriate algebra of formulas, a structure F-> = <P, ->, F>, where P is a set of atoms {p, q, r, ...}, -> a binary operation, and F the smallest set closed under -> of which P is a subset.
   
  Curry's Combinatory Logic (CL) is interpreted in F->, more precisely, in the power set of F since each combinator is identified with a set of formulas. The idea of the correspondence is the well-known Curry-Howard isomorphism, which associates with each combinator a corresponding formula of F->.
   
  Let S and T be any sets of formulas and define S o T = {b: a->b \in S and a \in T, for some fml a} So, the fusion SoT of two sets of fmls S and T is the set of all consequences of these fmls by ->E. For example, if S is the set of thms of classical logic and T is any set of fmls, SoT is the set of fmls classically entailed by some member of T.
   
  A Fool's Model of CL is a structure \M = <M, \leq, o> where o is as above, M is a collection of subsets of F s.t., if x, y \in M, then xoy \in M, and \leq is set inclusion.
   
  Certain subsets of F are then chosen as interpreting the well-known combinators. Although the general method of interpretation of combinators as types stays within the class of intuitionistically valid formulas, the Fool's Model has no such limitation. Any formula gives rise to a combinator.
   
  And any given ordinary logic \L = <F, \Sigma, L>, where F is an algebra of fmls, \Sigma a set of fmls, the axioms of \L, and L the set of thms, i.e. the smallest set of fmls that contains \Sigma and is closed under ->E and substitution, can be identified with a Fool's model \M_L = <F_L, \leq, o>.
   
   This may give some feeling and a rough idea of what the topic is about. Still, quoting from R. Meyer & M. Bunder's TR "Condensed Detachment and Combinators" ARP, ANU 1988, note 25, (TR are more interesting that published papers and can be funny as you will read below)
   
  "But why, the reader may wish to know, is it (the model) called the Fool's Model? The reference, obviously, is to St. Anselm, who wished to refute what the fool had said in his heart by furnishing a perfectly clear proof of the existence of God. (Note, by the way, that Meyer is the author of a famous proof of the existence of God based on the axiom of choice. J.R.) Similarly, --at least back in the bad old days-- there were those who had no faith that combinatory logic is intelligible. (This puzzled Curry, who did not find their objections intelligible.) Since there were many weird things that the scoffers did profess to find intelligible (cardinals measurable to man, etc.), this was due to no lack of credulity on their part. What they seemed to want was a simple set-theoretic realization of combinatory logic-- a model in some domain in which they did believe, such as the ZF universe of sets.
   
  So one can't really charge those who said in their hearts, "There is no combinatory logic," with atheism. Or whatever its equivalent is for Logic --acurryism, perhaps? or aSKism? (SK is, in CL terms, the J-> or implic. intuit. logic. JR) At any rate, it is the affliction of those who do not believe in the tachings of A. Church; rather they adhere to another religion. And they have quieted down a lot since Scott provided the sort of model that they --and he, for that matter-- wanted.
   
  Still, in those days Scott's original model was fairly fresh off the drawing board, and sufficiently intricate that not all could yet be said to have been convinced. So there was need of a model that anybody could understand, and use to make some sense of the combinatory ideas. (Meyer started to work ion this in the early 70's. JR) The model with those properties is the Fool's Model; which, though it arose independently and is not intended to capture all of CL, has something of the flavour of the so-called "graph models"."

Pour recevoir ce programme par email lors de ses mises à jour, laissez-nous vos coordonnées à l'adresse http://www.umh.ac.be/math/logic/logicdb/inscription.php
Archive des séminaires passés

Retour à la page de garde / Back to the homepage

Cette page a été consultée fois / This page has been accessed times.