Question

We have`f:{1,2,3}->{1,2}` and `g:{1,2,3}->{1,2,3,4}`.How many injective `f` and `g` funtions exist?

Answer 1

`f` can't be injective.

`g` can be injective in `24` ways.

Explanation:

A function is injective if no two inputs provide the same output. In other words, something like

`f(x)=f(y),\quad x \ne y`

can't happen.

This means that, in the case of finite domain and codomain, a function can be injective if and only if the domain is smaller than the codomain (or, at most, equal), in terms of cardinality.

This is why `f` can never be injective. In fact, you can fix `f(1)` as you like. Say `f(1)=1`, for example. When choosing `f(2)`, we can't say again that `f(2)=1`, or `f` wouldn't be injective. But when it comes to `f(3)` we have no choice, if we say `f(3)=1` we have `f(1)=f(3)`, and if we say `f(3)=2` we have `f(2)=f(3)`.

In other words, we must assing one of two possible ouputs to each of the three inputs. It should be evident that the inputs can't provide different outputs.

On the other hand `g` can be injective, since there is "enough space": each of the three inputs can choose one of the four outputs in such a way that no different inputs provide the same output.

But in how many ways? Well, suppose we start again with `f(1)`. We can choose any of the four ouputs for this input, so we can choose `f(1)` in four ways.

When it comes to `f(2)`, we lose some freedom: we can assign any value to `f(2)`, except for the one we assigned to `f(1)`, so we're left with two choices. For example, if we fixed `f(1)=2`, then `f(2)` can either be `1`, `3` or `4`.

By the same logic, we have two choices for `f(3)`: from the four possible choices, we rule out those already assigned to `f(1)` and `f(3)`.

So, we can define `g` in `4*3*2 = 24` ways such that `g` is injective.