I came a crossed a cograph similar to the one below, and it asks if there exists an surjective mappping from $B$ to $A$, and if there are any injective mapping from $B$ to $A$.

I know that there are definitely surjective mappings, but I am not so sure about injective mapping if we restricted the domain to a subset of $B$ then we could find an injective mapping. But, there is no way to map every element in $B$ to $A$ in a one-to-one manner. So, I don't know exactly what to conclude, are there any injective mappings $B \longrightarrow A$?

enter image description here

  • $\begingroup$ Your intuition is correct. There does not exist an injective function from $B$ to $A$. $\endgroup$ – A.E Aug 31 '13 at 1:33
  • $\begingroup$ @AEdwards Thanks, I was kind of unsure about it so I figured I would ask for a second opinion. $\endgroup$ – JimmyJackson Aug 31 '13 at 1:37

If there is an injective mapping from a set $C$ to a set $D$, then $D$ is at least as big as $C$. Hence there is no such mapping from your set $B$ to your $A$.

You can view finding an injective mapping from $C$ to $D$ as finding a subset of $D$ that looks like $C$, or, to be more precise, that you can label unambiguously with elements of $C$. In this interpretation it's clear that somehow $C$ "fits inside" $D$ so must be smaller (or at least, not bigger).

In the theory of infinite sets, we even define "smaller" and "bigger" in this way: writing $|X|$ the cardinality of a set $X$, we define $|X| \le |Y|$ to be true whenever there is an injection from $X$ to $Y$.


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.