[Math] Cardinality of the Domain vs Codomain in Surjective (non-injective) & Injective (non-surjective) functions

elementary-set-theoryfunctions

I'm a student in college just beginning to study the basics of set theory. In studying about Surjective & Injective functions & how they map their domain to their codomain, it came to my mind a question that I really wanted to confirm:

1) Is it possible to build a "surjective non-injective" function that has a domain with the same number of elements as the codomain?

2) Is it possible to build an "injective non-surjective" function that has a domain with the same number of elements as the codomain?

The context of these questions are:

Both the domain & the codomain of the function must have a finite number of elements. They are both finite sets.
Both the domain & the codomain of the function must not be an empty set. It has to have at least one element.
The function must not be a partial function. It has to take all the elements in the domain.
The function must not be a multi-value function. So for one element in the domain, the function can only output one value in the codomain.
The function must be only injective or surjective, but cannot be both (bijective) and cannot be non of those (general function).
I'm not expecting complex answers that explain using axioms, morphisms, complex notations, etc, which I cannot understand as of yet, since I'm just "beginning" to study the basics of set theory.
I already tried building such "function" but never really succeeded. It always has to have a different number of elements between the domain & the codomain in order to be surjective only or injective only. So this post is really just to "make sure" that it's true that building such function is never really possible for finite sets (I already know it's a different story in the case of infinite sets). Unless… umm I am missing something.
As I'm typing this post, I already read all the questions in the "similar questions" and in the "Questions that may already have your answer" panel. I did found some questions that are similar, but not actually detailed enough, requiring specific conditions & using specific context such as those that I'm posting here. I'm still posting this since those are not satisfying enough of a question & answer for me, so not quite what I'm looking for. Hope I don't get marked as duplicate.
- Lastly, since no human is perfect. Just let me know in the comment if there is something in the question that still needs to be cleared out or not in accordance to the rules of this forum. Hope I'm being clear enough.

Regards,

Best Answer

If $f$ is a function $A\to A$ where $A$ is a finite set, then $f$ is injective if and only it it is surjective. It is not possible for such an $f$ to be injective without being surjective or vice versa.

This can be proved by induction on the number of elements in $A$, but the details are slightly tedious. This property carries over to a function $f:A\to B$ where $A$ and $B$ have the same number of elements -- because "the same number of elements" means that there is a bijection $g:A\to B$, and then $f$ is injective/surjective exactly when $g^{-1}\circ f$ is, and $g^{-1}\circ f$ goes from $A$ to $A$ itself.

On the other hand, if $A$ is infinite, then it is possible for a function to be injective without being surjective, or vice versa. Some simple examples for $\mathbb N\to\mathbb N$ is $$ g(n) = n+7 \\ h(n) = \begin{cases} n & \text{if }n\le 42 \\ n-1 & \text{otherwise} \end{cases}$$ where $g$ is injective but not surjective, and $h$ is surjective but not injective.

(Strictly speaking this property of infinite sets is only guaranteed if the axiom of choice holds, but that is a techincal complication that you probably don't want to worry about at this level).

Motivation

When I go hiking, I want to be able to retrace my steps and get back to my starting point.

When I go to a store, I want to be able to return home.

When I swim out from the shore, I want to be able to get back to the shore.

Going somewhere and then coming back to where one started is important in life.

And it is important in mathematics.

And it is important in functional programming.

Domain, Codomain, and Inverse

If a function maps a set of elements (the domain) to a set of values (the codomain) then it is often useful to have another function that can take the elements in the codomain and send them back to their original domain values. The latter is called the inverse function.

In order for a function to have an inverse function, it must possess two important properties, which I explain now.

The Injective Property

Let the domain be the set of days of the week. In Haskell one can create the set using a data type definition such as this:

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday

Let the codomain be the set of breakfasts. One can create this set using a data type definition such as this:

data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage

Now I create a function that maps each element of the domain to a value in the codomain.

Here is one such function. The first line is the function signature and the following lines is the function definition:

f  ::  Day  ->  Breakfast
f  Monday       =  Eggs
f  Tuesday      =  Cereal
f  Wednesday    =  Toast
f  Thursday     =  Oatmeal
f  Friday       =  Pastry
f  Saturday     =  Ham
f  Sunday       =  Grits

An important thing to observe about the function is that no two elements in the domain map to the same codomain value. This function is called an injective function.

[Definition] An injective function is one such that no two elements in the domain map to the same value in the codomain.

Contrast with the following function, where two elements from the domain -- Monday and Tuesday -- both map to the same codomain value -- Eggs.

g  ::  Day  ->  Breakfast
g  Monday       =  Eggs
g  Tuesday      =  Eggs
g  Wednesday    =  Toast
g  Thursday     =  Oatmeal
g  Friday       =  Pastry
g  Saturday     =  Ham
g Sunday        =  Grits

The function is not injective.

Can you see a problem with creating an inverse function for g :: Day -> Breakfast?

Specifically, what would an inverse function do with Eggs? Map it to Monday? Or map it to Tuesday? That is a problem.

[Important] If a function does not have the injective property then it cannot have an inverse function.

In other words, I can't find my way back home.

The Surjective Property

There is a second property that a function must possess in order for it to have an inverse function. I explain that next.

Did you notice in the codomain that there are 8 values:

data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage

So there are more values in the codomain than in the domain.

In function f :: Day -> Breakfast there is no domain element that mapped to the codomain value Sausage.

So what would an inverse function do with Sausage? Map it to Monday? Tuesday? What?

The function is not surjective.

[Definition] A surjective function is one such that for each element in the codomain there is at least one element in the domain that maps to it.

[Important] If a function does not have the surjective property, then it does not have an inverse function.

[Important] In order for a function to have an inverse function, it must be both injective and surjective.

Injective + Surjective = Bijective

One final piece of terminology: a function that is both injective and surjective is said to be bijective. So, in order for a function to have an inverse function, it must be bijective.

Recap

If you want to be able to come back home after your function has taken you somewhere, then design your function to possess the properties of injectivity and surjectivity.

[Math] Can surjective functions map an element from the domain…

No. No surjective function can do that, because no function can do that. By definition, a function is required to map each element of the domain to a unique element of the codomain.

I recommend looking at the Wikipedia articles on functions, so-called "multivalued functions", and relations.