$|A| \leq |B|$ iff there is an injective map from A to B

682 Views Asked by At

We have two non-empty finite sets $A$ and $B$.

I want to show that $| A | \leq | B |$ iff there is an injective map $f$ from $A$ to $B$.

$$$$

I have done the following:

If $f$ is injective then for each element $b\in B$ there is at most one element $a\in A$ such that $b=f(a)$.

We suppose that $|A|>|B|$. So since at the domain there are more elements that in the image, it follows that at least two elements of the domain must be mapped to the same element of the image. That means that the function is not injective and so we get a contradiction.

Is the proof of the direction $\Leftarrow$ correct?

Could you give me a hint for the direction $\Rightarrow$ ?

1

There are 1 best solutions below

3
On BEST ANSWER

Your proof is correct, we see that you get it. If you want to refer to a mathematical result, you may want to check the piegeonhole principle. In fact, this is what you use, implicitely, in your proof.

As for the second direction, let $\{ a_1,\ldots ,a_r\}=A$ and $\{ b_1,\ldots ,b_s\}=B$ be enumerations of $A$ and $B$, with $r=|A|$, $s=|B|$.

Because $r\leq s$, we may define $f:A \rightarrow B$ a map which sends $a_i$ to $b_i$ for every $i=1,\ldots ,r$. Now, this function clearly is injective.

NB: Depending on the exact definition of $|\cdot |$, one may need to change the redaction of my proof a little. That is, I may have to justify that $A$ and $B$ can be written like thise, for instance. If this redaction does not suit you, please let me know.

NB2: Generally speaking, when we are not talking only about finite sets anymore, your statement is in fact taken as a definition of the relation $|A| \leq |B|$