|
|||
Séminaire interuniversitaire de
|
|
||
|
Programme de 2000-2001
2001 |
Cours du matin (11h - 12h30) |
Exposés de l'après-midi (14h30 - 16h) |
5 Juil |
|
Robert MEYER (Australian National University) |
2000 |
Cours du matin (11h - 12h30) |
Exposés de l'après-midi (14h30 - 16h) |
28 Sept |
|
Réunion d'organisation
Arnaud MAES (UMH) |
5 Oct |
|
|
12 Oct |
Françoise POINT (UMH) |
Armin RIGO (ULB) |
19 Oct |
Christian MICHAUX (UMH) |
Roland HINNION (ULB) |
26 Oct |
Françoise POINT (UMH) |
Olivier ESSER (ULB) |
2 Nov |
|
|
9 Nov |
Françoise POINT (UMH) |
Thierry LIBERT (ULB) |
16 Nov |
Christian MICHAUX (UMH) |
Grégory DUBY (ULB) |
23 Nov |
Françoise POINT (UMH) |
Olivier FRECON (ENS-Lyon) |
30 Nov |
Christian MICHAUX (UMH) |
Armin RIGO (ULB) |
7 Déc |
Françoise POINT (UMH) |
Cédric RIVIERE (UMH) |
14 Déc |
Christian MICHAUX (UMH) |
Armin RIGO (ULB) |
21 Déc |
Françoise POINT (UMH) |
|
2001 |
Cours du matin (11h - 12h30) |
Exposés de l'après-midi (14h30 - 16h) |
11 Jan |
Groupe de Contact en
Logique Mathématique |
|
1 Fév |
Françoise POINT (UMH) |
Véronique BRUYÈRE (UMH) |
8 Fév |
Christian MICHAUX (UMH) |
Raf CLUCKERS (KUL) |
15 Fév |
Françoise POINT (UMH) |
Armin RIGO (ULB) |
22 Fév |
Françoise POINT (UMH) |
PAS DE SÉMINAIRE à l'ULB, mais exposé de Christian
MICHAUX (UMH) à l'UCL
à 16h30 |
1 Mars |
Christian MICHAUX (UMH) |
Gunther CORNELISSEN (Max Planck
Institute - Bonn) |
8 Mars |
Françoise POINT (UMH) |
Marc DENECKER (KUL) |
15 Mars |
Christian MICHAUX (UMH) |
Michel RIGO (ULg) |
22 Mars |
Françoise POINT (UMH) |
Didier MISERCQUE (Institut MEURICE) |
29 Mars |
Journées de Mathématique et de Sciences à Mons |
|
5 Avril |
|
|
12 Avril |
|
|
19 Avril |
Christian MICHAUX (UMH) |
Gregory DUBY (ULB) |
26 Avril |
|
Diderik BATENS (RUG) |
3 Mai |
|
|
10 Mai |
Groupe de Contact en
Logique Mathématique |
|
17 Mai |
|
|
24 Mai |
|
|
31 Mai |
|
Cédric RIVIÈRE (UMH) |
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:
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é,
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.