0
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ Protip for future questions: sometimes too much text will turn off potential answer-ers. Keep it short and sweet, and happy posting. $\endgroup$ – parsiad Jun 14 '16 at 23:22
  • $\begingroup$ Thanks. I'm just trying to avoid getting my question on hold or closed for being not clear enough.. Like in the previous post I had.. $\endgroup$ – Gin99 Jun 15 '16 at 4:18
  • $\begingroup$ I was also avoiding that later on I would try to explain in great detail in the comments below about what actually the opening question was talking about, which will just be a waste of time for other people and a waste of time for myself.. Thus resulting in the opening being such a long text.. $\endgroup$ – Gin99 Jun 15 '16 at 4:38
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Ok. so it's solved then. It's not possible for finite sets. Actually this answer leads to another question that I have in mind which is related to the opening question but different, should I go and ask it here in the comment or should I open a new topic question? $\endgroup$ – Gin99 Jun 15 '16 at 11:01
  • $\begingroup$ @Gin99: Unless it is purely a clarifying question about the answer, it is generally better to ask it as a separate question. (Use common sense, though). $\endgroup$ – Henning Makholm Jun 15 '16 at 11:08
1
$\begingroup$

Yes to both:

  1. Consider $f\colon\mathbb{N}\rightarrow\mathbb{N}$ defined by $f(n)=\left\lfloor n/2\right\rfloor $.

  2. Consider $g\colon\mathbb{N}\rightarrow\mathbb{N}$ defined by $g(n)=2n$.

To see that (1) is not injective, note that $f(0)=f(1)$. To see that it is surjective, let $n\in\mathbb{N}$ and note that $f(2n)=n$.

To see that (2) is injective, note that $g(n)=2n=2n^{\prime}=g(n^{\prime})$ implies $n=n^{\prime}$. To see that it is not surjective, consider $g(n)=1$.

$\endgroup$
  • $\begingroup$ The OP was explicitly asking about finite sets. $\endgroup$ – Henning Makholm Jun 15 '16 at 0:22
  • $\begingroup$ Woops. I'll leave this here in case they're interested anyways. $\endgroup$ – parsiad Jun 15 '16 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.