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

  • 3
    $\begingroup$ Since in 99.998% of cases that is the definition of $|A|\leq|B|$, you should at least provide definitions. $\endgroup$ – Asaf Karagila Jun 14 '18 at 23:14
  • $\begingroup$ If |A|<|B| there should be a subset of B which has the same cardinality of A, maybe you can send all elements in A to that subset $\endgroup$ – Trux Jun 14 '18 at 23:14
  • $\begingroup$ Are you assuming that $A$ and $B$ are finite? Usually that is the very definition of $|A| \le |B|$ for infinite sets. $\endgroup$ – fleablood Jun 14 '18 at 23:33
  • 1
    $\begingroup$ This still requires a definition for $|A| \le |B|$. Or maybe we only need a definition of $n = |A|$, and that we assume all known properties of the natural numbers? $\endgroup$ – GEdgar Jun 15 '18 at 0:17
  • 2
    $\begingroup$ It is impossible to prove much about $|A| \le |B|$ unless you know a definition for $|A| \le |B|$. $\endgroup$ – GEdgar Jun 15 '18 at 0:44

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

  • $\begingroup$ I understand!! Thank you very much!! :-) $\endgroup$ – Mary Star Jun 15 '18 at 0:11
  • $\begingroup$ Do you maybe have also an idea for my ither question: math.stackexchange.com/questions/2820140/… ? $\endgroup$ – Mary Star Jun 15 '18 at 0:11
  • $\begingroup$ Mary Star, you already received a really good answer from Fleablood for your other question now, so it's all right I think. Good luck with your studies ! $\endgroup$ – Suzet Jun 15 '18 at 1:52

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.