Cardinaux de E et f(E)

[Marmus1021]

Bonsoir !
Soit E un ensemble fini.
Je cherchais une façon rigoureuse de prouver que Card(f(E)) était inférieure ou égale à Card(E).
J’ai lu que c’était évident par le principe des tiroirs, mais donc avec quels ensembles faudrait-il l’utiliser pour prouver cette inégalité ?

Merci d’avance et bon week end !
-----

[gg0]

Bonjour.

Avec le principe des tiroirs, E et f(E), évidemment.
Sinon, si les k éléments de E sont a,b,c, ...n, alors f(E) ne contient que les éléments f(a), f(b), .. f(n). Je viens de donner k éléments distincts ou confondus, il y en a donc au plus k..

Cordialement.

[Marmus1021]

D’accord, je comprends la deuxième partie.
Mais au début, pour utiliser le principe des tiroirs, il faudrait avoir une fonction qui va de f(E) dans E et qui doit injective, et alors on pourrait conclure que Card(f(E)) <= Card(E), non ?

[gg0]

Ben non,

les tiroirs sont les éléments de E et tu y mets les f(x).

Pour une preuve précise, il faut un théorème "principe des tiroirs" précis, que je n'ai pas.

[A voir en vidéo sur Futura]

[Marmus1021]

Ok merci beaucoup, donc ça suffirait d’expliquer cela en parlant de «*tiroirs*» pendant une colle de maths ?
Et sinon voici le théorème «*principe des tiroirs*» de mon cours : «*Soit E et F deux ensembles finis, et f:E —> F injective. Alors nécessairement, Card(E) <= Card(F).*»

[gg0]

Effectivement, ce théorème (qui ne recouvre pas tout à fait le principe des tiroirs : "si on met plus de n objets dans n tiroirs il y a un tiroir qui en contient 2") est un peu juste pour prouver seul ce que tu veux. Mais tu peux t'en servir en définissant une injection de f(E) dans E par exclusion : On ordonne E, puis on prend comme image de l'élément y de f(E) le plus petit x de E tel que f(x)=y.

Cordialement.

Nb : Le principe des tiroirs donne une "évidence", mais ce sont souvent les évidences qui sont les plus difficiles à prouver.

[MissJenny]

Bonjour, j'ai l'impression que la clause "E fini" n'est pas nécessaire. Est-ce que l'axiome du choix ne dit pas qu'il existe une injection de f(E) dans E ?

[gg0]

Effectivement,

mais j'avais soigneusement évité d'utiliser l'axiome du choix !

Cordialement.

[pm42]

Pour une preuve précise, il faut un théorème "principe des tiroirs" précis, que je n'ai pas.

Sans le théorème, on doit pouvoir montrer avec une récurrence très rapide sur le cardinal je pense ?

[gg0]

Effectivement,

c'est une bonne idée.

[Médiat]

S'il existe une surjection de dans alors Quant à l'axiome du choix, il est nécessaire pour définir correctement les cardinaux (infinis)