preuve d'existence d'une fonction (finie)

Mouha1 · January 2012

Salut, SVP si quelqu'un peut m'aider à démontrer le résutat suivant:
Soit une fonction (mapping) f : X -> A, avec X une ensemble infini de variables, et A un ensemble infini,
et soit un ensemble infini de contarintes sur les variables de la forme x=y,
Je veux montrer qu'il existe une fonction g: X -> B telle que:
- B est un sous ensemble fini de A
- et pour toute contrainte x=y, on a f(x)=f(y) ssi g(x)=g(y),

En fait je suis un informaticien, c'est pour cela jet trouve une difficulté de prouver ça,
Merci d'avance,

remarque · January 2012

Ce n'est pas possible : on peut avoir $f$ injective, alors que $g$ ne peut pas l'être.

nicolas.patrois · January 2012

Si x=y, f(x)=f(y) et g(x)=g(y), non ?

gerard0 · January 2012

Bonjour.

On considère $X=\{x_1,y_1,x_2,y_2,...\}$, avec $x_1=y_1=1$ (ou si tu préfères, on a affecté 1 à $x_1$ et à $y_1$), $x_2=y_2=2$, etc.
Donc $A=\mathbb N^*$

Alors ta condition "pour toute contrainte x=y, on a f(x)=f(y) ssi g(x)=g(y)" fait que si B est fini, il y a une infinité de valeurs possibles pour y pour au moins un x bien choisi (les valeurs de g(x) étant en nombre fini, il y a au moins un cas où une infinité de valeurs dans X ont la même image). donc on peut trouver trois valeurs distinctes x, y et z dans X telles que g(x)=g(y)=g(z) ce qui devrait donner f(x)=f(y)=f(z) avec x, y et z distincts. Ce n'est pas possible par définition de f.

Conclusion : Il est possible que dans certains cas, g existe, mais il faut des conditions supplémentaires sur f.

Cordialement.

remarque · January 2012

Ah oui, c'est vrai que la signification de la « contrainte » $x=y$ est assez floue...

Je n'avais pas vu ça comme n.p mais formellement, il a raison.

gerard0 · January 2012

C'est pourquoi, Remarque,

j'avais interprété cela en écriture "informaticien" : $x=y$ signifiant que le contenu de la "mémoire" $x$ est le même que celui de la mémoire $y$.
Mais j'attendrai la réponse de Mouha.

Cordialement.

skysurf3000 · January 2012

Sans prendre en compte le fait que $B$ doit être fini, c'est vrai si et seulement si la relation sur $X$ (que je notterai $\sim$ ) est une relation d'équivalence non?

En tout cas ça marche si $\sim$ est une relation d'équivalence. En effet on peut transporter $\sim$ en une relation $\sim'$ sur $f(X)$ en posant: $f(x) \sim' f(y)$ ssi $x \sim y$. Et alors en prenant pour B un représentant pour chaque classe d'équivalence sur $f(X)$, on obtient bien ce qu'on veut.

remarque · January 2012

Je ne comprends pas de quelle relation d'équivalence tu parles (mais à la réflexion, je ne comprends pas la question initiale non plus), mais néanmoins puisque $B$ est censé être fini, où est la finitude des classes d'équivalence sur $f(X)$ ?

gerard0 · January 2012

Skysurf,

applique ta "preuve" à mon exemple.

Cordialement.

skysurf3000 · January 2012

Hmmm... Eh bien j'avoue que j'ai totalement oublié ce que je voulais dire, mais que ça me paraissait très logique ^^
Je reviendrai vous dire si ça me revient ^^

Je crois quand même pouvoir dire que l'exemple de gerard0 ne me contredisait pas car je ne m'occupais pas de l'hypothèse "B fini"...

gerard0 · January 2012

Salut Skysurf.

Effectivement, si tu ne traitais pas le problème de Mouha, mon objection tombe. mais reconnais que tu aurais pu être plus clair :
"Sans prendre en compte le fait que $ B$ doit être fini,....
En tout cas ça marche si ..."
J'ai compris le "en tout cas" comme éliminant l'hypothèse de départ. Du coup, je n'ai plus rien à redire.
D'ailleurs, si on l'élimine, il suffit de prendre $B=A$ et $g=f$. Le problème n'a plus aucun intérêt.

Cordialement.

preuve d'existence d'une fonction (finie)

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 32