Une petite question à propos des ensembles & applications

[Clark_]

Voilà un problème qui me donne du fil à retordre.

"Soit n appartenant à N. Déterminer le nombre d'applications surjectives de [1...n+1] dans [1...n] (on pourra s'interesser au cardinal de f-1({i}) pour tout i appartenant à [1...n])." (application réciproque hein, pas puissance -1 ;) )

J'ai cherché un peu de mon coté, mes pistes ne m'ont pas amené très loin jusqu'ici. :hein:

[nuage]

Bonsoir,
tu peux remarquer que cardinal(f-1{i})€{1,2} et que sauf pour une valeur de i,
cardinal(f-1{i})=1.

[Clark_]

tu peux remarquer que cardinal(f-1{i})€{1,2} et que sauf pour une valeur de i,
cardinal(f-1{i})=1.

Je comprends pas bien. (je suis encore novice dans ces théories ensemblistes, il va falloir être patient je pense!)
Déjà, est-ce que "Card(f-1({i})€{1,2}" signifie Le nombre d'éléments de l'ensemble f-1({i}) est égal à 1 ou 2. Comment peux-tu faire cette déduction?
"pour une valeur de i, cardinal(f-1{i})=1" Ce qui signifierait qu'il y a une valeur de i pour laquelle le nombre d'éléments de l'ensemble f-1({i}) vaut 1!
Vraiment, je pige pas! :hum:

[SimonB]

Déjà, est-ce que "Card(f-1({i})€{1,2}" signifie Le nombre d'éléments de l'ensemble f-1({i}) est égal à 1 ou 2. Comment peux-tu faire cette déduction?

Première question : la réponse est oui.
Seconde question : si une application est surjective, tous les éléments de l'ensemble d'arrivée (ici, de [|1;n|] sont des images d'un certain élément de l'ensemble de départ...
Pour conclure, tu dois faire intervenir le cardinal de ton ensemble de départ, et donc ton nombre d'images maximales par la fonction.

"pour une valeur de i, cardinal(f-1{i})=1" Ce qui signifierait qu'il y a une valeur de i pour laquelle le nombre d'éléments de l'ensemble f-1({i}) vaut 1!
Vraiment, je pige pas! :hum:

Tu as oublié un "sauf", qui était le truc important. Cela veut dire que pour toutes les valeurs de i sauf une, il y a un élément dans f-1{i}, et pour une, il y a 2 éléments dedans.

[Clark_]

Première question : la réponse est oui.
Seconde question : si une application est surjective, tous les éléments de l'ensemble d'arrivée (ici, de [|1;n|] sont des images d'un certain élément de l'ensemble de départ....

Euh? Tu veux dire "sont des images d'un certain NOMBRE D'élements de l'ensemble de départ non? Parce que ce que tu sembles me dire, c'est que toutes les images sont issues d'un même et unique élément de l'ensemble de départ?!

Pour conclure, tu dois faire intervenir le cardinal de ton ensemble de départ, et donc ton nombre d'images maximales par la fonction.

Eh bien, le cardinal de l'ensemble de départ, c'est n+1, n'est ce pas?
Le nombre d'image maximal est donc n+1 (puisque qu'un élément ne peut avoir 2 images différentes)

Tu as oublié un "sauf", qui était le truc important. Cela veut dire que pour toutes les valeurs de i sauf une, il y a un élément dans f-1{i}, et pour une, il y a 2 éléments dedans.

Quelque chose me turlupine. Quand vous dites que Card(f-1{i})={1;2}, c'est la traduction de " un i quelconque de [1...n] peut avoir 1 ou 2 antécédents pas f-1?"

:hein:

[SimonB]

Euh? Tu veux dire "sont des images d'un certain NOMBRE D'élements de l'ensemble de départ non? Parce que ce que tu sembles me dire, c'est que toutes les images sont issues d'un même et unique élément de l'ensemble de départ?!

Oui. Ma formulation n'est pas claire. Disons : pour tout élément y à l'arrivée, il existe un élément x au départ qui est tel que f(x)=y.

Eh bien, le cardinal de l'ensemble de départ, c'est n+1, n'est ce pas?
Le nombre d'image maximal est donc n+1 (puisque qu'un élément ne peut avoir 2 images différentes)

C'est ça.

Quelque chose me turlupine. Quand vous dites que Card(f-1{i})={1;2}, c'est la traduction de " un i quelconque de [1...n] peut avoir 1 ou 2 antécédents pas f-1?"

Pas =, € (appartient à). Le cardinal de l'ensemble considéré est soit 1, soit 2. C'est ce que ça signifie.

[Clark_]

Pas =, € (appartient à). Le cardinal de l'ensemble considéré est soit 1, soit 2. C'est ce que ça signifie.

Oui, d'accord, on considère i comme un ensemble à un élément. Donc le cardinal de f-1({1}) appartient à {1,2}, car s'il appartenait à {1,2,3} par exemple, on aurait un élément de l'ensemble d'arrivé qui ne pourrait avoir d'antécédent (et donc une surjectivité non vérifiée au final).
Je commence à cerner un peu mieux les idées introduites dans ce topic.
La procédure du raisonnement me laisse encore un peu perplexe. Je vais essayer de vous faire part de mes idées de démonstraton:

Je partirais approximativement comme ça:

Sois i € [1...n]. On a Card(f-1({i})) € {1,2}.
On sait Card([1...n+1]) = n+1. Le nombre d'images maximum par f est donc n+1.
Je sais pas trop comment terminer la démonstration de manière rigoureuse et formelle, mais j'ai l'intuition qu'il n'y aura que 2 applications surjectives qui vérifieront les conditions du problème. A savoir:

1) Pour la première on va considerer qu'aucun élément de l'ensemble d'arrivé aura 2 antécédents, autrement dit on considère Card(f-1({i}))=1 pour tout i de l'ensemble d'arrivé. On aura ainsi une application surjective, mais il resteront un élément de [1...n+1] qui restera sans image dans [1...n] par f. Tous les autres éléments de l'ensemble de départ auront une image distinct.

2) Pour la deuxième, on va considerer qu'un unique élément de l'ensemble d'arrivé aura 2 antécédents, autrement dit, on considère Card(f-1({i})=2 pour un unique i de l'ensemble d'arrivé. On aura ainsi une application surjective, et tous les élements de [1...n+1] auront une image dans [1...n] par f. Un unique couple d'élements de l'ensemble de départ aura ainsi la même image i par f.

:id: ? ou :--: ?

[Dysklain]

salut,
supposons qu'une fonction soit surjective de [1 n+1] dans [1 n]
deux images ont le même antécédent: 2 parmis n choix.
un antécédent a deux images: n+1 choix.
puis tu complètes l'application par une surjection de n-1 vers n-1, soit une bijection: (n-1)! choix.
Il y a donc (n+1)!(n-1)/2.

A priori c'est bon... à qqs erreurs près.

[Clark_]

Ah oui zut, j'avais compris qu'il y avait 2 types de surjections possibles, mais je les avais pas toutes dénombrées... :mur:
Merci à toi pour cette piste :++:

[ThSQ]

(n+1)!(n-1)/2.

C'est bizarre ça fait 0 pour n=1. :hum:

Pour moi c'est

: choix des 2 éléments avec la même image
n : choix de la valeur de cette image
(n-1)! : on distribue les n-1 restant de manière bijective.

[Dysklain]

euh oui j'ai mélangé ensemble de départ et d'arrivée...
donc n à la place de n-1
mais sinon, le principe est bon, je voulais juste montrer qu'en dénombrant point par point, on arrive à simplifier pas mal l'idée du truc.

par contre si deux élements ont la même image, c'est 2 parmis n+1 nan ?
tu te serais pas gouré toi aussi ?

[ThSQ]

euh oui j'ai mélangé ensemble de départ et d'arrivée...
donc n à la place de n-1
mais sinon, le principe est bon, je voulais juste montrer qu'en dénombrant point par point, on arrive à simplifier pas mal l'idée du truc.

par contre si deux élements ont la même image, c'est 2 parmis n+1 nan ?
tu te serais pas gouré toi aussi ?

Oui c'est

[Clark_]

OULA!
Je suis pas bon en dénombrement, la dernière fois que j'en ai fait, c'était en terminale. Je vais avoir besoin d'un peu d'aide pour décortiquer ces résultats.
Pour le dénombrement, j'aurais procédé de la manière suivante:

1) primo, je cherche toutes les surjections possibles dans l'hypothèse ou f-1({i})=1
Alors là euh. Pour moi il y en aurait (n+1)n

2) segundo, je cherche toutes les surjections possibles dans l'hypothèse f-1({i})=2
Là, il y aurait combinaisons possibles.

3) et puis tout bêtement le nombre de surjections: n(n+1) +

ça sent l'énormité :doh:

[Clark_]

ou pas? :hein: