| Home / lib / M_Mathematics / | ||
Antonini et al. Les Mathematiques pour l'agregation (lectures, 2002)(fr)(680s).pdf |
|
Size 3.5Mb Date Jul 15, 2004 |
133 136 136 139 143 143 145 146 147 147 147 148 150 150 152 152 153 154 154 156 157 160 160 160 162 162 162 163 165 165 166 167 170 171 171 172 172 172 173 174 174 175...
214 214 215 215 218 219 220 220 225 226 228 228 228 229 229 230 230 230 231 232 233 233 234 235 238 239 239 240 242 246 252 253 253 253 253 254 255 256 256 256 256 257 259 261 261 261 262...
313 313 313 318 320 321 326 326 330 331 335 336 336 336 338 338 339 340 340 341 342 342 345 345 345 346 347 348 348 350 350 350 351 352 355 356 356 357 358 359 361 361 362 365 365 365...
445 446 449 450 450 451 452 453 454 454 456 461 467 469 469 469 470 471 471 472 472 472 473 473 475 477 480 481 483 486 487 487 488 492 496 496 496 497 499 500 500 504 504 505 505 507 507...
608 608 608 609 609 611 611 612 613 614 616 616 616 617 617 617 618 618 618 620 621 626 626 626 628 628 630 631 632 632 632 632 633 634 634 634 635 636 637 637 637 639 639 639 640 641...
Définition 5 On définit maintenant le diagramme de Hasse pour un ensemble fini partiellement ordonné. A chaque élément de E on associe un point du plan, et on trace une ligne de x à y si x y. On veille à ce que ces lignes n’intersectent pas les autres points, et on veille à ce que x y implique que l’ordonnée du point associé à x soit inférieure à l’ordonnée du point associé à y....
• Pour k variant de 1 à n faire • • Pour i variant de 1 à n faire • • • Pour j variant de 1 à n faire • • • • ai,j ← ai,j ∨ (ai,k ∧ ak,j ) On peut constater que l’on n’applique pas exactement le lemme, car les ai,j ne sont pas les bons, mais l’on peut aussi montrer que l’algorithme fonctionne tout de même. La complexité de l’algorithme de Roy-Warshall est O(n3 ). Soit G = (X, U ) un graphe orienté, Gr = (X, Ur ) est une réduction transitive de G si Ur ⊂ U , Gr n’a pas de transitivité et (Gr )f = Gf . La réduction transitive n’est pas toujours unique. Si G = (X, U ) est un graphe orienté sans circuit, il a une unique réduction transitive appelé graphe de Hasse. Algorithme général de calcul d’une fermeture transitive (pas seulement dans le cas d’un graphe sans circuit). • Pour x ∈ X faire • • marque(x) ← faux • • Γ+ (x) ← ∅ f • Pour tout x ∈ X faire • • file ← {x} • • tant que file = ∅ faire • • • y ← premier(file) • • • supprimer (y ,file) • • • Pour tout z ∈ Γ+ (y ) faire • • • • Si marque(y )=faux alors • • • • • marque(z ) ← vrai • • • • • marque(Γ+ (x) ← Γ+ (x) ∪ {z }) f f • • • • • file ← file ∪ { z } • • Pour tout z ∈ Gamma+ (x) faire f • • • marque(x) ← f aux Le coût de cet algorithme est O(n|U | + |Uf |). On cherche maintenant à déterminer à la fois la fermeture et la réduction transitive dans un graphe sans circuit. L’algorithme employé est l’algorithme de Goralcicova-Koubek. • Pour tout x ∈ X faire • • Γ+ (x) ← ∅ f • • Γ+ (x) ← ∅ r • • marque(x) ← faux • On classe les points dans l’ordre d’un tri topologique τ = (x1 , x2 , ..., xn ) • Pour i variant de n à 1 faire • • S ← Γ+ (xi ) • • Tant que S = ∅ • • • x ← minτ (S )...
On notera que toutes les opérations intuitives sur les ensembles sont possibles, enfin presque. On peut en tout cas utiliser les intersections, définir l’ensemble des éléments d’un ensemble donné qui vérifient une propriété donnée, on peut travailler sur l’ensemble des parties d’un ensemble, on peut travailler sur un produit cartésien d’ensembles, bref toutes ces choses sans lesquelles les maths prendraient vraiment la tête. On peut aussi montrer l’existence et l’unicité de l’ensemble vide....
Démonstration : • Il suffit de constater comme on l’a vu plus haut que le segment initial engendré par O est O. • Il est clair que E doit appartenir à un tel élément, ainsi qu’être inclus dedans ; réciproquement l’ensemble E ∪ {E }. • FacDe. il éfinition 25 Etant donné E un ordinal, E ∪ {E } est appelé le successeur de E . On le note E + 1. E est dit le prédécesseur de E + 1....
Théorème 30 (Théorème de Cantor-Bernstein) Soit E et F deux ensembles, f une injection de E dans F , et g une injection de F dans E ; alors il existe une bijection de E dans F . Démonstration : • On considère l’ensemble des parties X de E telles que g (f (X )c )∩ X = ∅. • On montre que cet ensemble admet un élément maximal (car il est stable par réunion) • On montre que le maximum X vérifie g (f (X )c ) ∪ X = E • On montre que la fonction qui à x associe f (x) si x ∈ X et l’unique y tel que g (y ) = x si x ∈ X est une bijection L...
Théorème 37 (Consistance relative de AC et de ¬AC ) (AC désigne l’axiome du choix) Si la théorie axiomatique de Zermelo-Fraenkel avec axiome de fondation est consistante, alors la théorie de Zermelo-Fraenkel avec axiome de fondation et axiome du choix est consistante. Si la théorie axiomatique de Zermelo-Fraenkel est consistante, alors la théorie de Zermelo-Fraenkel avec axiome du choix est consistante. D’autre part si la théorie de Zermelo-Fraenkel est consistante, alors la théorie de Zermelo-Fraenkel avec la négation de l’axiome du choix est consistante. Enfin, si la théorie de Zermelo-Fraenkel avec axiome de fondation est consistante, alors la théorie de Zermelo-Fraenkel avec axiome de fondation et avec la négation de l’axiome du choix (i.e. en supposant qu’il existe un ensemble sur lequel on ne peut pas construire une relation de bon ordre) est consistante....
F I G . 4.3 – Z F désigne la théorie de Zermelo-Fraenkel. Z F \ inf ini désigne la même théorie mais privée de l’axiome de l’infini et muni de sa négation. AC désigne l’axiome du choix. not(AC ) désigne la négation de AC . C OH désigne l’axiome selon lequel les parties de ω ne peuvent pas être bien ordonnes. AF désigne l’axiome de fondation. AC C désigne l’axiome d’accessibilité. C H désigne l’hypothèse du continu, et GC H l’hypothèse du continu généralisée. Une flèche relie une théorie T à une théorie T si T est plus forte que T , c’est-à-dire que tous les théorèmes de T sont des théorèmes de T . Notez bien que toutes les théories présentes sur la figure sont consistantes si et seulement si Z F est consistante. Notez bien aussi que si Z F est consistante, alors il est impossible de le prouver ; mais que par contre si elle ne l’est pas, on dispose d’un algorithme théorique permettant en temps fini de le prouver......
Définition 67 (Isométrie) Etant donnés deux espaces métriques E et F , une application f de E dans F est une isométrie si ∀(x, y ) dF (f (x), f (y )) = dE (x, y )....
| © 2007 eKnigu | ||