Question on injective-surjective functions, regarding cardinality of domain, codomain

Question

Ok so we know that if A, B are finite sets and f: A to B is injective, then cardinality(A)≤cardinality(B), and that the opposite inequality holds for a surjection. My question is, if we know that f is not injective, can we assume that cardinality(A)>cardinality(B) (and similarly for a surjection)? I'm asking this because I need to prove that there is no f:A to A that is either (injective but not surjective) or (surjective but not injective), with A finite. Thanks! (Sorry for my bad typing, I can't figure out how to use the symbols)

Answer 1

Nope. Let $X=\mathbb{R}$ and $Y=\mathbb{Z}$ $|\mathbb{Z}| < |\mathbb{R}|$. Consider the function $f:X \to Y$ defined $f(x)=1$ for all $x$. This map is not injective, but, as stated, $|X|<|Y|$.

If you want an example with finite sets $X=\{1,2,3\}$ and $Y=\{1,2,3,4,5,6,7,8,9\}$ and define the same map. The same issue arises. It is similar when a map fails to be surjective.

As a hint for your problem. Suppose $f:A \to A$ is injective but surjective. So there is in $a \in A$ which does not have a partner. But what happens to $f(a)$?. The idea is similar for the surjective case.

Answer 2

Unfortunately, knowing that you have a non-injective function $f$ from $A$ to $B$ doesn't tell you that $|A| > |B|$. For a counterexample with finite sets, consider the function

$f : \{1, 2, 3\} \rightarrow \{1, 2, 3, 4\}$

defined by:

$f(x) = 1, \forall x \in \{1,2,3\}$.

This function is not injective, since $f(1) = f(2) = f(3)$, but $1 \neq 2$, $2 \neq 3$, and $1 \neq 3$, but $|\{1,2,3\}| < |\{1,2,3,4\}|$.

A good point to keep in mind when thinking about questions like this is that for most sets $A$ and $B$, there are many different possible functions from $A$ to $B$. Just because you have one particular function from $A$ to $B$ that isn't injective, doesn't mean that no function from $A$ to $B$ is injective. In the above example, we can see that while $f$ is not injective, we can define $g : \{1, 2, 3\} \rightarrow \{1, 2, 3, 4\}$ by $g(x) = x$, and $g$ is in fact injective, showing that $|\{1,2,3\}| \leq |\{1,2,3,4\}|$.

I hope this helps!