Conjecture des familles stables par unions
Bonjour, je propose ici à la critique une solution de la conjecture des familles stables par unions. Merci de me signaler l'erreur, tellement ça a été rapidement résolue.
$Introduction$
En mathématiques, et plus particulièrement en combinatoire, la conjecture des familles stables par unions est un problème d'énoncé élémentaire posé par Péter Frankl en 1979 et toujours ouvert.
$Introduction$
En mathématiques, et plus particulièrement en combinatoire, la conjecture des familles stables par unions est un problème d'énoncé élémentaire posé par Péter Frankl en 1979 et toujours ouvert.
Une famille d'ensembles est dite stable par unions, si l'union de deux ensembles quelconque de la famille est encore un ensemble de la famille.
La conjecture affirme que pour toute famille finie d'ensembles finis (non vides), stable par unions, il existe un élément appartenant à au moins la moitié des ensembles de la famille.
C'est ce que nous allons ici démontrer en utilisant une méthode par récurrence.
$Preuve$
Soit une famille $(F_{i})_{1\leq i\leq n}$ d'ensembles non vides stable par unions de cardinal $n$. Il nous faut montrer qu'il existe un élément $x\in\cup_{i=1}^{n}F_{i}$ appartenant à au moins $\dfrac{n}{2}$ ensembles de la famille des $F_{i}$.
Il est évident que pour $n = 1$ et $n = 2$ la conjecture est vraie.
Soit $P_{n}$ la propriété : ''la conjecture est vraie pour toute famille d'ensemble stable par unions de cardinal $n$.''
On vient de dire qu'on a $P_{1}$ et $P_{2}$. Supposons qu'on ait $P_{n}$ et montrons que cela implique qu'on a $P_{n+1}.
$\bullet$ Pour $n$ impair, avoir $P_{n}$ signifie qu'il existe un élément $x$ appartenant à au moins $\dfrac{n + 1}{2}$ ensembles de la famille à $n$ ensembles, ce qui implique qu'on a $P_{n+1}$.
$\bullet$ Si $n$ est pair, alors il existe un entier $m$ tel que $n = 2m$.
Soit alors une famille à $n + 1 = 2m + 1$ ensembles stable par unions. Montrer que $P_{n+1}$ est vraie équivaut à montrer qu'il existe un élément appartenant à $m + 1$ ensembles de la famille stable par unions de cardinal $2m + 1$.
On part de la famille stable par unions à $n + 1 = 2m + 1$ ensembles. Chaque fois qu'on lui enlève un ensemble, on a une famille à $n = 2m$ ensembles, et il est clair que si on lui enlève un ensemble non vide $F_{j}$ de cardinal minimal (il existe car le nombre d'ensembles $n + 1$, est fini) on obtient une famille stable par unions (car la famille à $n + 1$ ensembles était stable par unions) de cardinal $n = 2m$ ensembles. Donc il existe d'après l'hypothèse de récurrence, dans cette dernière famille, un élément $x$ appartenant à au moins $m$ ensembles (On peut supposer que l'élément $x$ appartient à exactement $m$ ensembles ; sinon c'est fini).
Mais $F_{j}$ union chacun des $m$ ensembles contenant l'élément $x$ donne $m$ ensembles de la famille à $n + 1 = 2m + 1$ ensembles contenant chacun l'élément $x$. On a donc dans la famille à $n + 1 = 2m + 1$ ensembles stable par unions, $m$ ensembles (contenant l'élément $x$) qui contiennent tous, l'ensemble $F_{j}$. Ces $m$ ensembles et $F_{j}$ constituent $m + !$ ensembles de la famille stable par unions de cardinal $n + 1 = 2m +1$ contenant $F_{j}$ qui est non vide. D'où $P_{n+1}$
$P_{1}$ et $P_{2}$ sont vraies $P_{n}\implies P_{n+1}$ pour $n\geq 3$, alors la conjecture est vraie pour toute famille stable par unions de cardinal fini.
$Théorème$ :
Pour toute famille finie d'ensembles finis (non vides), stable par unions, il existe un élément appartenant à au moins la moitié des ensembles de la famille.
Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Le problème est que tu supposes implicitement que ta famille d'ensembles ne contient que des ensembles deux à deux distincts, or ce n'est pas forcément la cas.
Plus précisément, notons $A_1,...,A_m$ les $m$ ensembles de ta famille qui contiennent l'élément $x$. Toi tu dis que $A_1\cup F_j, A_2\cup F_j,..., A_m\cup F_j$ sont $m$ ensembles de la famille mais ce n'est pas forcément le cas car si $A_1=A_2=...=A_m$ alors il se peut très bien que ta famille ne contienne qu'une copie de $A_1\cup F_j$ et pas $m$ copies.
Edit : d'ailleurs même avec des ensembles $A_i$ deux à deux distincts ça ne marche pas. Par exemple si $F_j=\{1,2\}$ que $A_1=\{1,3,4\}$ et que $A_2=\{2,3,4\}$ alors $A_1\cup F_j=A_2\cup F_j=\{1,2,3,4\}$ et il se peut très bien que ta famille ne contienne qu'une copie de l'ensemble $\{1,2,3,4\}$.
Mais je pense quand même que les ensembles en question sont deux a deux distincts, sinon pourquoi parler de dénombrement.
Je vous reviendrai certainement.
Merci.
Cordialement.
PS. Une fois la prochaine preuve pondue, tu pourras faire l'exercice qui consiste à démontrer toutes les affirmations que tu n'as pas démontrées dans ta démonstration.
Ensuite, veille à ce que ta famille d'ensembles soit stable par unions.
Cette affirmation est fausse en général comme je l'ai montré. Si tu prétends qu'en complétant la famille ça fonctionne alors c'est à toi de le prouver. C'est ta démonstration pas la mienne.
Idem, ici, tu as beaucoup de paragraphes qui commencent par MAIS ... c'est bizarre.
Mais, ça indique plus ou moins un changement de direction, une nouvelle idée qui vient contredire la précédente. C'est illogique de voir tous ces 'Mais' dans une démonstration.
Les mots de liaisons sont importants, c'est très bien d'en mettre, mais ici, tous ces mots de liaison ne présagent rien de bon.
En général, dans une démonstration, on avance par petits pas (des lemmes) des petits pas qui vont tous dans la même direction.
@lourrran parfois je dis ''Mais'' juste pour rappeler une propriété qu'on a déjà. (IL se peut quand même que j'en abuse).
Je dois peut-être essayer de démontrer rigoureusement la dernière affirmation de la page, avant de conclure (mais bon...!)
Mais tu ne peux pas la démontrer vu qu'elle est fausse. Allez un dernier contre-exemple pour le fun :
On considère la famille suivante : $(F_1=\{1,2,4\}, F_2=\{1,3,5\}, F_3=\{1,2,3,4,5\}, F_4=\{2,4\},F_5=\{3,5\},F_6=\{2,3,4,5\},F_7=\{1\})$. Cette famille est stable par unions et son cardinal est de 7, donc $m=3$. L'élément $x=1$ appartient à chaque ensemble de la famille $(F_1,F_2,F_3)$ et pourtant ces ensembles ne sont pas emboîtés.
On considère la famille $(F_1=\{1\}, F_2=\{2\}, F_3=\{1,2\}, F_4=\{1,3\},F_5=\{1,2,3\},F_6=\{1,4\},F_7=\{1,2,4\},F_8=\{1,3,4\},F_9=\{1,2,3,4\})$. Cette famille est stable par unions et son cardinal est de 9, donc $m=4$. L'élément $x=3$ appartient exactement à 4 ensembles qui sont $(F_4,F_5,F_8,F_9)$ et pourtant ces ensembles ne sont pas emboîtés.
@babsgueye si j'ai bien compris tu veux que je trouve un contre-exemple qui ne contient pas d'éléments appartenant à $m+1$ ensembles ou plus ??? Tu te rends compte que trouver un tel contre-exemple signifie avoir démontré que la conjecture est fausse... ?
Bref tu n'as toujours pas fourni de preuve que tes ensembles sont emboîtés. Si tu veux démontrer une conjecture en déclarant vraie des affirmations non prouvées alors ne perds pas de temps et déclare directement que la conjecture est vraie...