Je cherche une démonstration du lemme des tiroirs.

[invite4b07365d]

Bonjour,

Est-ce un principe ou un lemme ?
Si c'est un lemme une démonstration serait bienvenue.

Merci
-----

[gg0]

Bonjour.

Soient E et F, des ensembles finis, E ayant n éléments, et F ayant p éléments, avec n>p. Considérons une application g de E dans F (*). Comme si f est une application injective d'un ensemble fini E dans un ensemble fini F, alors F a au moins autant d'éléments de E (**), par contraposition, g n'est pas injective. Donc il existe un élément de F qui a deux antécédents.

Cordialement.


(*) placement des n objets dans p tiroirs.
(**) un théorème de base de la théorie des ensembles.

[invite4b07365d]

Il semblerait que en fait c'est un principe : https://fr.wikipedia.org/wiki/Principe_des_tiroirs

[gg0]

Le jour où tu te décideras d'étudier un cours de théorie des ensembles (*), au lieu de papillonner en mélangeant textes de vulgarisation et textes mathématiques, tu verras que le lemme (ou principe - le mot n'a pas de sens en mathématiques) des tiroirs est démontré.

(*) par exemple celui de Dehornoy, disponible sur le net.

[A voir en vidéo sur Futura]

[leon1789]

Bonjour.

Soient E et F, des ensembles finis, E ayant n éléments, et F ayant p éléments, avec n>p. Considérons une application g de E dans F (*). Comme si f est une application injective d'un ensemble fini E dans un ensemble fini F, alors F a au moins autant d'éléments de E (**), par contraposition, g n'est pas injective. Donc il existe un élément de F qui a deux antécédents.

Cordialement.


(*) placement des n objets dans p tiroirs.
(**) un théorème de base de la théorie des ensembles.

gg0, tu démontres le lemme avec une reformulation du lemme. Ce qu'il faut démontrer, c'est justement :
si f : E -> F avec card(E) > card(F) (F ensemble fini) alors il existe au moins deux éléments de E ayant la même image.
Ceci se prouve facilement par récurrence sur le card(F) .

[gg0]

Effectivement,

je n'étais pas entré dans les aspects techniques (*), qui dépendent de la façon dont sont présentés les cardinaux (finis). Je m'étais contenté d'une piste au cas où la question serait sérieuse. Manifestement, le vocabulaire intéresse plus "fin" que la démonstration ...

Cordialement.

(*) récurrence, ou ordinaux par exemple.

[inviteb3412e7c]

Avec la théorie de Cantor c'est immédiat en démontrant ce lemme :

Si et injective
Alors

Démonstration Comme est injective alors et comme on a d'après le Théorème de Cantor-Bernstein.

Le lemme des tiroirs se déduit immédiatement de ce résultat.

La difficulté est de démontrer le Théorème de Cantor-Berstein, mais je suis sûr que tu trouveras une démonstration dans la littérature.

[leon1789]

arttle, tu t'es mélangé dans les sens de toutes les inégalités.

Reste à démontrer que f : E -> F injective implique card(E) <= card(F)

[inviteb3412e7c]

Ah oui, c'est vrai ^^

Pour ce "reste à démontrer", en fait c'est la définition de la relation d'ordre sur les cardinaux dans la théorie de Cantor. En fait c'est pour ça que la théorie de Cantor est révolutionnaire, c'est justement parce qu'elle n'est plus relié au dénombrement des éléments des ensembles, mais qu'elle considère les injection et les bijections entre eux. L'injection détermine une relation d'ordre, et la bijection détermine une relation d'équivalence.

En fait le plus difficile, comme dit plus haut est de prouver le Théorème de Cantor-Bernstein. Mais il existe beaucoup de preuve dans la littérature.

[leon1789]

ok.

Si je comprends bien, en prenant comme définition " Card(E) <= Card(F) lorsqu'il existe une injection de E dans F " (sans avoir prouvée la symétrie de la relation <= , donnée par le Théorème de Cantor-Bernstein) ,
alors il n'y a rien à prouver pour obtenir le lemme des tiroirs : un coup de contraposée : " Card(E) > Card(F) implique qu'il n'existe pas d'injection de E dans F ",
donc " Card(E) > Card(F) implique que pour toute fonction f : E -> F , il existe au moins un élément de F ayant au moins deux antécédents. "

Dans ce cas, on peut même dire que le lemme des tiroirs est quasiment une définition. C'est effectivement efficace et rapide, mais personnellement, ça me laisse sur ma faim car cela ne donne aucun moyen algorithmique pour concrétiser l'existence de cet élément de F (mais ceci est une autre histoire).

[inviteb3412e7c]

En ce qui concerne le côté algorithmique, si E ou F est fini, il reste l'énumération, même si c'est pas très efficace.

[leon1789]

si E ou F est fini, il reste l'énumération,

oui, c'est la preuve par récurrence à laquelle je pensais.

même si c'est pas très efficace.

oui, c'est bien vrai ! Mais comment faire autrement dans un contexte général ?

[inviteb3412e7c]

Dans la théorie de Cantor, on ne parle pas d'énumération. Néanmoins, la relation d'équivalence d'égalité de cardinal permet de parler de la classe d'équivalence de . L'énumération devient l'existence ou non d'une bijection avec .

Pour ce qui est de l'algorithmique, je laisse la parole à d'autres car ce n'est pas mon domaine.

[inviteded0667c]

Vous vous demandez si ce résultat est un principe ou un lemme. Disons que ce sont vos deux tiroirs. L un exclu la nécessité de preuve selon vous.

-Ce resultat, en partie, a des applications a en perdre ses chaussettes telement on s y accroche :

https://www.google.fr/url?sa=t&sourc..._WvP_OmpJAZa_Q

-Ce résultat est, en partie, un point clé dans la géométrie diophantienne

-Ce résultat, en partie, vous doutez de sa rigueur.

Appliquer donc ce résultat pour conclure quant à votre question.

Sur futura science on résout pas les problèmes on donne des indications !

[inviteded0667c]

Indice : mettre les deux résultats bien mathématiques dans un certain tiroir fait de vous un troll