Tenemos f: {1,2,3} -> {1,2} y g: {1,2,3} -> {1,2,3,4}. ¿Cuántas funciones inyectables f y g existen?

Responder:

#F# no puede ser inyectivo.

#sol# puede ser inyectivo en #24# formas.

Explicación:

Una función es inyectiva si no hay dos entradas que proporcionen la misma salida. En otras palabras, algo como

#f (x) = f (y), quad x ne y #

no puede suceder

Esto significa que, en el caso de dominio finito y codominio, una función puede ser inyectiva si y solo si el dominio es más pequeño que el codominio (o, a lo sumo, igual), en términos de cardinalidad.

Esta es la razón por #F# nunca puede ser inyectivo De hecho, puedes arreglar #f (1) # como quieras. Decir #f (1) = 1 #, por ejemplo. Al elegir #f (2) #, no podemos decir de nuevo que #f (2) = 1 #o #F# no sería inyectivo Pero cuando se trata de #f (3) # No tenemos otra opción, si decimos. #f (3) = 1 # tenemos #f (1) = f (3) #, y si decimos #f (3) = 2 # tenemos #f (2) = f (3) #.

En otras palabras, debemos asignar una de las dos posibles salidas a cada una de las tres entradas. Debe ser evidente que las entradas no pueden proporcionar salidas diferentes.

Por otra parte #sol# puede ser inyectivo, ya que hay "espacio suficiente": cada una de las tres entradas puede elegir una de las cuatro salidas de manera que ninguna entrada diferente proporcione la misma salida.

¿Pero de cuántas maneras? Bueno, supongamos que comencemos de nuevo con #f (1) #. Podemos elegir cualquiera de las cuatro salidas para esta entrada, por lo que podemos elegir #f (1) # de cuatro maneras.

Cuando se trata de #f (2) #, perdemos algo de libertad: podemos asignar cualquier valor a #f (2) #, excepto el que asignamos a #f (1) #, así que nos quedamos con dos opciones. Por ejemplo, si arreglamos #f (1) = 2 #, entonces #f (2) # puede ser #1#, #3# o #4#.

Por la misma lógica, tenemos dos opciones para #f (3) #: de las cuatro opciones posibles, descartamos aquellas ya asignadas a #f (1) # y #f (3) #.

Entonces, podemos definir #sol# en #4*3*2 = 24# formas tales que #sol# es inyectivo.