# Surjective and injective mappings between two abstract sets (cograph)

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$?

• Your intuition is correct. There does not exist an injective function from $B$ to $A$. – A.E Aug 31 '13 at 1:33
• @AEdwards Thanks, I was kind of unsure about it so I figured I would ask for a second opinion. – 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$.