I'm a college student just beginning to study the very basic 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 want to confirm:

1) Is it possible to build a "surjective non-injective" function with a domain which has a "lower" cardinality than it's codomain?

2) Is it possible to build an "injective non-surjective" function with a domain which has a "higher" cardinality than it's codomain?

The context of these questions are:

  • This post is a related (but different) question to this post here (which is also posted by myself) but I was asked to open a new question (read the comments in the related post)

  • Both the domain & the codomain of the function must have a finite number of elements. They are both finite sets. And also, both must not be an empty set.

  • The function must not be a partial function & must not be a multi-valued function.
  • The function must be injective only or surjective only.
  • 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. The result is always the "reverse" of what my question is asking. And this post is really just to "make sure" that it's true that building such function is never really possible (for "finite" sets only). 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.
  • Since I'm just a newbie, 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. I hope the context is clear enough.

Best Regards,

  • 2
    $\begingroup$ Not a complete answer (so, just a comment), but briefly: (1) There are no surjections $X\to Y$ when $|X| < |Y|$. Similarly, (2) there are no injections $X\to Y$ when $|Y| < |X|$ (this is pretty much the "pigeonhole principle"). $\endgroup$ – BrianO Jun 18 '16 at 21:42

Let $X,Y$ be sets and $f:X\rightarrow Y$ a function. The idea of a function is, that every $x\in X$ is mapped to only one $y\in Y$. If $X$ and $Y$ are now finite (as you are looking for, right?), then there are no functions which can fulfill 1.) or 2.).

Maybe this will help for better understanding. Try to understand for $|X|=|Y|$:

If $f$ is surjective then it is also injective (thus bijective) and vice versa.


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.