Conjecture des familles stables par unions

babsgueye

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.

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.

raoul.S

L'erreur est ici : 

babsgueye a dit :

Mais $F_j$ union chacun des $m$ ensembles contenant l'élément $x$ donne $m$ ensembles de la famille...

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\}$.

babsgueye

Tu as raison, Je me disais qu'il y a quelque chose qui m' échappé.
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.

gerard0

le dénombrement est justement l'activité qui consiste à ne compter que pour 1 des objets de noms différents mais égaux.

babsgueye

@raoul.S j'ai retouché ma 

PREUVE

Soit une famille $(F_{i})_{1\leq i\leq n}$ d'ensembles non vides stable par unions de cardinal $n\in \mathbb{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.

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 $(F_{i})_{1\leq i\leq n+1}$ à $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 d'ensembles $(F_{i})_{1\leq i\leq n+1}$ 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}$ minimal au sens qu'il n'est pas réunion de deux ensembles (il existe car le nombre d'ensembles $2m + 1$ est fini) on obtient une famille stable par unions (car la famille à $2m + 1$ ensembles était stable par unions) de cardinal $n = 2m$ ensembles (à savoir $(F_{i})_{1\leq i\leq n+1, i\neq j}$) . 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).

On peut sans perte de généralité, supposer que les $m$ ensembles contenant $x$ sont $F_{1}, F_{2}, \cdots , F_{m}$.

Mais comme $x$ est contenu dans exactement $m$ ensembles et pas plus, les $m$ ensembles sont emboités. On peut donc les nommer $F_{1}\subsetneq F_{2}\subsetneq \cdots \subsetneq F_{m}$.

Mais alors les $m + 1$ autres ensembles de la familles $(F_{i})_{1\leq i\leq 2m+1}$ seront au pire des cas donnés par les ensembles, à l'ordre des indices près, suivant : $F_{m+1} = F_{2}\setminus F_{1}, F_{m+2} = F_{3}\setminus F_{1}, \cdots , F_{2m-1} = F_{m}\setminus F_{1}$ et forcément, $F_{2m} = F_{3}\setminus F_{2}$ et $F_{2m+1} = F_{2m}\cup F_{1}$ ou vice versa.

Dans ce cas $x$ appartient aussi à $F_{2m+1}$, donc à $m + 1$ ensembles.

Il est aisé de voir que toute autre construction de ces $m + 1$ ensembles, sera telle que $x$ appartienne à au moins $m + 2$ ensembles de la famille d'ensembles $(F_{i})_{1\leq i\leq 2m+1}$ stable par unions.

$P_{1}$ et $P_{2}$ sont vraies, et $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.

raoul.S

babsgueye a dit : 

Mais comme $x$ est contenu dans exactement $m$ ensembles et pas plus, les $m$ ensembles sont emboités. On peut donc les nommer $F_{1}\subsetneq F_{2}\subsetneq \cdots \subsetneq F_{m}$.

Ça c'est faux. Par exemple $F_1=\{1,3\}, F_2=\{1,2\}, F_3=\{1,2,3\}$.

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.

babsgueye

@raoul.S j'ai pas bien compris ton contre-exemple. C'est quoi que tu appelles $x$, et c'est quoi la valeur de $m$ ?
Ensuite, veille à ce que ta famille d'ensembles soit stable par unions.

raoul.S

Dans mon contre-exemple $x=1$ et $m=3$.

babsgueye

Tu dois alors compléter ta famille à $2m + 1 = 7$ ensembles et veiller à qu'elle soit stable par unions.

raoul.S

Non, je me limite à ce que tu as dit. Tu as dit : 

babsgueye a dit :
Mais comme $x$ est contenu dans exactement $m$ ensembles et pas plus, les $m$ ensembles sont emboités. On peut donc les nommer $F_{1}\subsetneq F_{2}\subsetneq \cdots \subsetneq F_{m}$.

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.

lourrran

Dans une démonstration,  les phrases comme 'il est clair que' ou 'il est aisé de voir que' cachent souvent des arnaques. A éviter.
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.

babsgueye

@raoul.S je te dis tout simplement que ton soi-disant contre -exemple n'en est pas un.

@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...!)

raoul.S

@babsgueye c'est ta façon de me dire que tu ne sais pas démontrer ton affirmation ?

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.

babsgueye

@raoul.S $x = 1$ appartient à $F_{7}$ aussi, donc ton $m = 4$ et non $3$.

raoul.S

Ok ce n'est pas un contre-exemple qui marche mais ton affirmation n'est pas non plus démontrée.

babsgueye

J'essayerai d'être plus clair.

raoul.S

En voici un autre : 

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

@raoul.S peut-être que j'ai pas été très clair, Mais quand on suppose qu'il y a un élément $x$ qui est dans $m$ ensembles exactement et pas plus, on sous entend qu'il n'y a pas d'élément qui soit dans $m + 1$ ensembles ou plus. Sinon c'est fini et ça ne vaut pas la peine de faire d'étude car c'est ce qu'on cherche à démontrer. Dans ton soi-disant contre-exemple l'élément $1$ est dans $8$ ensembles ; de ce fait, c'en n'est pas un.

Math Coss

Bla bla bla.

gerard0

Babsgueye est nettement plus doué pour rejeter les critiques des autres que pour rédiger une preuve. Il est très vite satisfait de ce qu'il a écrit; trop vite !

C'est au moins la quinzième conjecture qu'il prétend avoir prouvée, toujours avec des preuves fausses ou incomplètes voire incompréhensibles.

raoul.S

babsgueye a dit :

@raoul.S peut-être que j'ai pas été très clair, Mais quand on suppose qu'il y a un élément $x$ qui est dans $m$ ensembles exactement et pas plus, on sous entend qu'il n'y a pas d'élément qui soit dans $m + 1$ ensembles ou plus.

@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...