les "non-ensembles"

[MissJenny]

bonjour,

j'ai quelques questions à poser à propos de ces "ensembles qui ne sont pas des ensembles". Je pense au fameux "ensemble de tous les ensembles" et variantes. Ce qui me préoccupe c'est la théorie des graphes mais j'ai quelques question plus générales.

1) est-ce qu'il existe un "ensemble de tous les ensembles finis" ?

2) quand on n'a pas d'ensemble, est-ce qu'on peut quand-même parler d'un "ensemble vérifiant telle propriété et qui soit de cardinal minimal parmi tous les ensembles qui vérifient cette propriété" ?

3) même question si on se restreint aux ensembles finis.

4) est-ce qu'il existe un ensemble de tous les graphes finis? (pour les graphes quelconques je pense que c'est non puisqu'il y a "plus de graphes que d'ensembles")

je pose ces questions parce que dans plusieurs démonstrations de théorie des graphes on postule l'existence d'un graphe de taille minimale (au sens du nombre d'arêtes par exemple), etc.
-----

[Deedee81]

Salut,

Je ne connais pas assez pour répondre du tac au tac à chacune des questions. Mais je présume que tu fais référence à ça :
https://fr.wikipedia.org/wiki/Classe...C3%A9matiques)

Si oui tu devrais y trouver des réponses (enfin une partie)

[Médiat]

Les ensembles qui ne sont pas des ensembles sont appelés des classes

1) est-ce qu'il existe un "ensemble de tous les ensembles finis" ?

Non, s'il existait, l'ensemble de ses parties contiendrait l'ensemble de tous les enesmbles

2) quand on n'a pas d'ensemble, est-ce qu'on peut quand-même parler d'un "ensemble vérifiant telle propriété et qui soit de cardinal minimal parmi tous les ensembles qui vérifient cette propriété" ?

3) même question si on se restreint aux ensembles finis.

Je ne comprends pas ces questions, pour raisonner en théorie des ensembles, il faut des ensembles.

4) est-ce qu'il existe un ensemble de tous les graphes finis? (pour les graphes quelconques je pense que c'est non puisqu'il y a "plus de graphes que d'ensembles")

Non, pour la même raison

[MissJenny]

Non, s'il existait, l'ensemble de ses parties contiendrait l'ensemble de tous les enesmbles

ah mince, ça ne me paraît pas du tout évident...

pour la question sur l'objet minimal dans un "non-ensemble", elle vient de ma tentative de compréhension de la démonstration du théorème des quatre couleurs. Cette démonstration procède par l'absurde : elle dit que si le théorème est faux alors il existe des graphes planaires non-4-coloriables et en particulier qu'il en existe au moins un qui a un nombre de sommets minimal. Je me demandais s'il n'y avait pas une difficulté ici.

[A voir en vidéo sur Futura]

[MissJenny]

ah, ça y est, je crois que j'ai compris pour l'ensemble des parties. Si j'ai bien compris il ne peut pas y avoir un "ensemble de tous les singletons".

[Médiat]

Si on a disposition tous les singletons (finis donc), on peut construire tous les ensembles.

Pour les graphes, est-ce que l'on ne peut pas définir les graphes finis (à isomorphisme près) à partir de n'importe quel ensemble dénombrable IN par exemple ?

EDIT : oui

[MissJenny]

Un graphe (simple non orienté) est souvent défini par la donnée de deux ensembles : l'ensemble des sommets, a priori quelconque, et une partie de l'ensemble des paires d'éléments du premier ensemble (les arêtes). Mais en réalité on ne s'intéresse pas aux noms des sommets et on pourrait se contenter d'un ensemble de sommets pour chaque cardinal. Et de plus le plus souvent tout est supposé fini. Donc je pense qu'en réalité il n'y a pas de problème.

Mais pour ma culture mathématique, est-ce que j'ai raison de me méfier quand on suppose l'existence d'un objet extrêmal parmi des objets qui ne forment pas un ensemble?

[Médiat]

Mais pour ma culture mathématique, est-ce que j'ai raison de me méfier quand on suppose l'existence d'un objet extrêmal parmi des objets qui ne forment pas un ensemble?

Incontestablement, beaucoup (mais pas tous) de problèmes de ce type d'existence (base d'un ev par exemple), se résout avec axiome du choix.

[gg0]

Bonjour MissJenny.

Une question me vient. La classe des graphes planaires non-4-coloriables ne serait-elle pas un ensemble ? Car elle est bien plus restreinte que la classe des graphes.
D'autre part, la minimalité est-elle générale, ou bien l'idée est, connaissant un graphe planaire non-4-coloriable, de trouver un sous-graphe non-4-coloriable de taille minimale ?

Cordialement.

[MissJenny]

Dans la démonstration, l'extrêmalité est globale : on suppose un graphe non-4-coloriable de nombre de sommets minimal. On enlève un sommet et on sait que le graphe restant est 4-coloriable puisqu'il a moins de sommets, et le reste de la démonstration revient à montrer comment on peut étendre le coloriage au graphe initial, quitte à échanger les couleurs de certains sous-graphes.

mais tu as certainement raison, les graphes planaires sont particuliers. D'ailleurs on peut montrer que le contre-exemple minimal est nécessairement une triangulation (une classe de graphes encore plus restreinte).

[MissJenny]

J'ai une dernière question sur ce thème : quand on pense à une catégorie d'objets (j'emploie le mot catégorie dans un sens non technique, disons "les groupes" ou 'les graphes", etc), est-ce que la question de savoir s'ils forment un ensemble ou pas est toujours évidente, ou bien il faut parfois le démontrer et ça n'est pas trivial?

[Médiat]

C'est bien un problème de la théorie des catégories, et plus précisément des "petites catégories".

[MissJenny]

ok merci. Je vais essayer d'apprendre un peu ce que sont les catégories. Ca fait partie de mes plans depuis longtemps...

[GBZM]

Bonsoir,

Après la bataille : ce qui est intéressant pour les graphes, ce sont leurs classes d'isomorphismes. Et il y a bien un ensemble (dénombrable) de représentants des classes d'isomorphismes de graphes finis. Aucun souci, donc.

[Deedee81]

SAlut,

Après la bataille : ce qui est intéressant pour les graphes, ce sont leurs classes d'isomorphismes. Et il y a bien un ensemble (dénombrable) de représentants des classes d'isomorphismes de graphes finis. Aucun souci, donc.

Les graphes peuvent-ils être infinis ? Et peut-on avoir des graphes avec un infini non dénombrable de noeuds ? (il me semble avoir vu ça, mais je présume qu'on sort de la théorie des graphes stricto sensus là ???)

[GBZM]

Oui, un graphe peut être infini, il peut avoir une infinité non dénombrable de sommets, chaque sommet peut avoir une infinité d'arêtes adjacentes etc.
Mais on ne parlait ici que des graphes finis.

[Deedee81]

Oui, un graphe peut être infini, il peut avoir une infinité non dénombrable de sommets, chaque sommet peut avoir une infinité d'arêtes adjacentes etc.
Mais on ne parlait ici que des graphes finis.

D'accord, merci pour ton explication (et la précision sur les graphes finis, ma question était surtout par curiosité)

[MissJenny]

L'ensemble des sommets peut être quelconque, mais parfois il y a des restrictions sur l'ensemble des arêtes. Il me semble que Ore dans son livre demande qu'un sommet soit adjacent au plus à une infinité dénombrable d'arêtes.

[Deedee81]

parfois il y a des restrictions sur l'ensemble des arêtes

Je suppose pour des raisons pratiques (pour pouvoir appliquer certains théorèmes ou certains outils) ?
Ceci dit une infinité dénombrable de noeuds adjacents, c'est déjà pas si mal

[GBZM]

Il est pas beau le graphe dont l'ensemble des sommets est , et où il y a une arête entre et quand est transcendant ? (je n'ai pas voulu prendre le graphe complet, ça faisait too much).

[Médiat]

Et le graphe de l'appartenance d'un modèle (supposé exister) de ZF ?

[Deedee81]

Ah oui, bien vu (l'un comme l'autre d'ailleurs). Je connaissais ce genre d'usage des graphes et j'aurais dû y penser. Mais n'étant pas mathématicien faut parfois du temps pour que les impulsions parcourent tous les neurones nécessaires (c'est pourtant un graphe fini pour le coup )

[Médiat]

La notion de graphe pour l'appartenance est bien pratique pour banaliser certains points, par exemple certains ont du mal à accepter l'idée d'un ensemble qui se contient lui-même, alors qu'en termes de graphe, c'est juste une boucle.

[Deedee81]

La notion de graphe pour l'appartenance est bien pratique pour banaliser certains points, par exemple certains ont du mal à accepter l'idée d'un ensemble qui se contient lui-même, alors qu'en termes de graphe, c'est juste une boucle.

Ah et bien voilà par contre un usage que je ne connaissais pas Il est vrai que j'ai "l'abstraction facile" et donc j'ai parfois du mal à voir ce qu'on a du mal à comprendre/accepter.

J'ai déjà utilisé les graphes d"'applications, ça peut être utile pour discuter de certaines propriétés.

Mais je suis en train de tirer le sujet HS là. Désolé, j'arrête