Comment montrer la composition d'une fonction à sens unique est pas une telle?

Question

Je me demandais comment dois-je procéder pour montrer que la composition de (par exemple) deux fonctions à sens unique (faibles ou forts, ou les deux ensemble) ne sont pas une fonction à sens unique?

Plus précisément: Say $ f $ et $ g $ sont des fonctions à sens unique (faible ou forte). Comment puis-je prouver que leur composition $ g (f (x)) $ est pas nécessairement une fonction à sens unique?

Answer 1

Vous venez avec un exemple: deux fonctions $ f, g $ qui sont des fonctions à sens unique, mais $ f \ circ g $ est pas. Pour montrer que ce dernier n'est pas une fonction à sens unique, vous venez avec un algorithme cassant.

Voici un exemple. Choisissez une véritable fonction à sens unique $ h $. Soit $ f (x) = h (x) 0 ^ {| x |} $ et soit $ g (x, y) = h (x) $ si $ y \ neq 0 ^ {| x |} $, et $ g (x, y) = 0 ^ {| x |} $ si $ y = 0 ^ {| x |} $ (nous rompons l'entrée de telle sorte que $ | x | = | y | $). Notez que la composition est juste la fonction zéro.