cours-ctad

Description

Concurrence et Topologie Algebrique DirigeeEmmanuel Haucourt8 decembre 2009Table des matieres1 Pourquoi et Comment 31.1 Produit Cartesien et Parallelisme . . . . . . . . . . . . . . . . . . 41.1.1 Categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.2 Produit Cartesien . . . . . . . . . . . . . . . . . . . . . . 51.1.3 La syntaxe du langage PV . . . . . . . . . . . . . . . . . 81.1.4 Une semantique ensembliste du langage PV . . . . . . . . 91.1.5 Une autre semantique ensembliste du langage PV . . . . . 101.2 Espaces Ordonnes . . . . . . . . . . . . . . . . . . . . . . . . . . 131.2.1 Espaces Topologiques . . . . . . . . . . . . . . . . . . . . 131.2.2 La categorie des espaces ordonnes . . . . . . . . . . . . . 142 La Categorie Fondamentale 182.1 Foncteurs et Transformations Naturelles . . . . . . . . . . . . . . 182.2 The category of graphs . . . . . . . . . . . . . . . . . . . . . . . . 242.3 Homotopie de chemins . . . . . . . . . . . . . . . . . . . . . . . . 293 Categories sans boucle 393.1 Origine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2 Le theoreme de Seifert -Van Kampen . . . . . . . . . . . . . . . . 423.3 Le mono de des categories nies, connexes, sans boucle et non vide 454 Categorie des Composantes 524.1 A quoi ca sert ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.2 Morphismes de Yoneda . . . . . . . . . . . . . . . . . . . . . . . . 534.3 Systemes de ...

Informations

• Publié par: Orgio
• Nombre de lectures: 29
• Langue: Français

Extrait

Concurrence

et

Topologie

Alge´brique

Emmanuel Haucourt

8

de´cembre

2009

Dirig´ee

Tabledesmatie`res

1 Pourquoi et Comment 3 1.1ProduitCarte´sienetParall´elisme..................4 1.1.1Cat´egories...........................4 1.1.2ProduitCart´esien......................5 1.1.3 La syntaxe du langage PV . . . . . . . . . . . . . . . . . 8 1.1.4Unese´mantiqueensemblistedulangagePV........9 1.1.5Uneautres´emantiqueensemblistedulangagePV.....10 1.2EspacesOrdonne´s..........................13 1.2.1 Espaces Topologiques . . . . . . . . . . . . . . . . . . . . 13 1.2.2Lacat´egoriedesespacesordonne´s.............14 2LaCat´egorieFondamentale18 2.1 Foncteurs et Transformations Naturelles . . . . . . . . . . . . . . 18 2.2 The category of graphs . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Homotopie de chemins . . . . . . . . . . . . . . . . . . . . . . . . 29 3Cat´egoriessansboucle39 3.1 Origine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2Leth´eor`emedeSeifert -Van Kampen 42. . . . . . . . . . . . . . . . 3.3Lemono¨ıdedescate´goriesfinies,connexes,sansboucleetnonvide45 4Cate´goriedesComposantes52 4.1Aquoi¸casert?............................52 4.2 Morphismes deYoneda 53. . . . . . .. . . . . . . . . . . . . . . . . 4.3Syste`mesdeYoneda. . . . . . .. . . . . . . . . . . . . . . . . .  55 4.4 Quotient et Localisation . . . . . . . . . . . . . . . . . . . . . . . 58 4.5Descriptiondelacate´goriedescomposantes............59 5Alge`brecubique62 5.1 Cubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.2Re´gionscubiques...........................62 5.3Aspectthe´oriqueducalculdelaformenormale..........64 5.4 Un peu de topologie . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.5Alg`ebredeBoole.....seu76.....desr´egionscubiqrgda´uee

1

6

Ce 6.1 6.2

dont on a pas parle ´ Ou`sontpass´eeslesboucles?. Quepourrait-ˆetreunecate´gorie “localement sans boucle” ? . . .

2

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

68 68

70

Chapitre 1

Pourquoi et Comment

Ladirig´ee´ebriqueoligaeglotopitnoe´ucesacexd’elqutresi’leee´dntsedee´ d’un programme peuvent etre vues comme des chemins sur un espace topologique ˆ dontlespointsrepr´esententles´etatsdusyst`eme(potentiellement)atteintsen ion.Onpassealorsd’une´tat`aunaut¸ coursd’exe´cutredefacon“continue”en visitantuneinifinite´d’autres´etats. Desmod`elesdelaconcurrenceplus“classiques”envisagentces´etatscomme unensemble.Unetraced’exe´cutionestalorsunesuite(potentiellementinfinie) de“fl`eches 1 ¸ysusemt`aue`astnapssre’dnue´”fai tat d n autre de facon “atom- ique”.Dansdetelsmode`les,letempsestenuncertainsens“discret. ” Cependantlase´mantiquedulangagedeprogrammationconsid´ere´impose descontraintesde“causalite´”entrelese´tats.Ellessont,parexempledanslecas dessy`estdsemartetisnsnoi[Win95],formalise´seapurentsurtcehpargederu e´tiquete´dontlessommetssontlese´tats,tandisquedanslecasdestraces de Mazurkiewicz[Win95] elles se traduisent par des relations (sur l’ensemble des e´tats)soumisesa`desaxiomesquie´voquentlestracesd’ex´ecution.Danslecadre delatopologiquealg´ebriquedirige´e,chaqueespacetopologiquesera´egalement pourvud’unestructurequirepre´sentecescontraintes.Selonlanaturedecette structure, on aura desescredpsaoen´son[Nac65], desespace localement ordonn´es, descourants(oustreams[Kri07]) ou desd-espaces[Gra03]. Chacunedecesnotionsdonnelieua`unecategorieainsiqu’a`uned´efinition ´ deac´tgeroeifondamentale. Ces differentes approches s’inscrivent dans un ´ cadrequipermetded´ecrirecetteconstructiondefac¸onge´ne´rale.Enpartic- ulier,lacate´goriefondamentaled’unespacetopologiquen’estautrequeson groupoı¨defondamental[Hig71,Spa95]:cetteconstructione´le´mentairedela topologiealge´briqueestpourl’essentiellaseulea`laquelleilsoitfaitre´f´erence dans ces notes qui, pour autant, ne supposent aucune connaissance en topologie 1 “actionstions”ou.”airrustaoounprt“eisnae´isrirc

3

alge´brique“classique”. Levocabulairedelath´eoriedescat´egoriesetquelquesunsdesesconceptsde basesontindispensables.Ilssontdistille´s,selonlesbesoins,toutaulongdece coursainsiquequelquesrappelsdetopologiee´l´ementaire.Encequiconcernela the´oriedescate´gories,desouvragestels[Awo06],[Bor94a]ou[Mac98]couvrent (largement) le spectre des concepts dont nous aurons besoin, celui deSteve Awodeyble.essisacculpeletuodsnastnta´e 1.1ProduitCarte´sienetParalle´lisme 1.1.1Cat´egories Unege´taceiroCeltcoidn’tseepniefid´olecunarobjetsot´eenOb(C), une collection demorphismest´noesMo(C), trois “applications”id,sett s Mo(C) oo id // Ob(C) t ainsiqueparune“application”appel´ee(loi de) compositiondeCniefiuresd´ la collection des paires (γ, δ) de morphismes deCtelles ques(γ) =t(δ). L’image de la paire (γ, δontitnes´eoterap)ttecppaeacilγ◦δtepaep´lee´eeocpmsodeδ suivi deγ. Les objetss(γ) ett(γ) sont lasourceet lebutdu morphismeγ. Le morphismeid(xe´tveounont,p)ssluid x , est l’neditit´ede l’objetxees.eCdsno´n formentunecate´gorielorsqu’ellesv´erifientlesaxiomessuivants: La loi de composition est associative Pour tout morphismeγon aid t(γ) ◦γ=γ=γ◦id s(γ) Pour tout objetxon as(id x ) =x=t(id x ) Pour tous morphismesγetδtels ques(γ) =t(δ) XX.on as(γ◦δ) =s(δ) ett(γ◦δ) =t(γ) Uneso´eat-cuseirogdeCnodaltseecllontiuoseoc-see´nnu’dMdeMo(C) et d’une sous-collectionOdeOb(C) telles que sixtrappa`antieO, alorsid x tna`treipaapM siγntde´emen´elestuM, alorss(γ) ett(γppa)itraennea`tnOet siδemtnedestun´el´eMtel ques(γ) =t(δee´sopm,a)colarsloδ◦γappar- tient`aM. Les restrictions des applicationsid,s,tet◦aux collectionsOetMfournissent alorsunestructuredecat´egorie. On dit qu’un morphismeγdexversyest unisomorphismelorsqu’il existe un morphismeδdeyversxtel queδ◦γ=id x etγ◦δ=id y . On dit alors que δ(respectivementγ) est l’inversedeγ(respectivementδ) et on noteδ=γ −1 etγ=δ −1 easmhirpmouttoueqefiire´vno(it.Ondrse)nievsunuualpmdte aussi que deux objetsxetysontisomorphes, ce que l’on notex ∼ = y, lorsqu’il 4