1
$\begingroup$

Let $X$ be a set and let $A \subseteq X$ be a subset of $X$. Asume that there is an injective function $f: X \rightarrow A$. Show that $A$ and $X$ have the same cardinality. Show that any two sets have the same cardinality $\iff$ there are injective functions $f: Y \rightarrow Z$ and $g: Z \rightarrow Y$.

Since $f: X \rightarrow A$ is injective, $\operatorname{card} X \leq \operatorname{card} A$. But since $A$ is a subset of $X$, we have the inclusion map $g: A \rightarrow X$, which is also injective. So $\operatorname{card} A \leq \operatorname{card} X \implies \operatorname{card} A= \operatorname{card} X$.

Similarly, we have $\operatorname{card} Y \leq \operatorname{card} Z$ and $\operatorname{card} Z \leq \operatorname{card} Y \implies \operatorname{card} Y = \operatorname{card} Z$.

I was just wondering if my answer was correct, because it is really short so I thought that I might be missing something...is it ok for me to assume that if we have an injective function $f: X \rightarrow Y$, then $\operatorname{card} X \leq \operatorname{card}$? Or is that what the question wants me to prove?

Thanks in advance

$\endgroup$
  • 2
    $\begingroup$ The question is asking you to prove that if $\operatorname{card}X\le\operatorname{card}Y$ is defined to mean that there is an injection $f:X\to Y$, then this $\le$ is antisymmetric, meaning that if $\operatorname{card}X\le\operatorname{card}Y$ and $\operatorname{card}Y\le\operatorname{card}X$ by this definition, then we really do have $\operatorname{card}X=\operatorname{card}Y$ in the sense that there is a bijection between the two. You are in effect assuming the desired conclusion. There are several proofs of this result, none of them trivial. $\endgroup$ – Brian M. Scott Sep 19 '13 at 19:05
  • 2
    $\begingroup$ I do not think that this should be closed as a duplicate - it is a "check my proof" question, so cannot be a duplicate! $\endgroup$ – user1729 Sep 19 '13 at 19:21
  • $\begingroup$ The part of this question that is of interest to future visitors is fully dealt with on the duplicate. I vote against reopening. $\endgroup$ – Lord_Farin Sep 23 '13 at 12:02
  • $\begingroup$ Here is a question about the same statement. (In fact, this question is closed as a duplicate as of this moment; I am posting this comment so that the link is not lost if it is reopened. There are already 4 votes to reopen.) $\endgroup$ – Martin Sleziak Sep 23 '13 at 14:35
1
$\begingroup$

Actually this is where you need to prove the implication.

$$ |A|\leq|B|\text{ and }|B|\leq|A|\,\implies|A|=|B| $$

The symbol $\leq$ is just a notation for the existence of an injective function, and $=$ is a symbol for the existence of a bijection.

Indeed, this notation suggest the above implication, just as much as it suggest that $$ |A|\leq|B|\text{ and }|B|\leq|C|\,\implies|A|\leq|C| $$

but this needs proof that if there if the assumed injections exist then so is the implied injection from $A$ to $C$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy