I am stuck with proving this statement for a while.
Prop. If $A,B$ are sets and $B$ is finite, and there is an injection $f:A \to B$, then $A$ is finite and $\operatorname{card}(A) \leq \operatorname{card}(B)$
This is my proof:
Let $A,B$ sets. Suppose that $B$ is a finite set, and there is an injection $f:A \to B$.
If $A=\emptyset$ then $A$ is a finite set and $\operatorname{card}(A) \leq \operatorname{card}(B)$.
If $A \neq \emptyset$, since $B$ is a finite set, there exists a bijection $g: B \to [n]$ for $n \in \mathbb{N}$ and $\operatorname{card}(B) = n$.
Also because we suppose there is an injection $f:A \to B$ we have an injection $g \circ f : A \to [n]$. So $A$ is also a finite set and $\operatorname{card}(A) \leq n$, and hence $\operatorname{card}(A) \leq \operatorname{card}(B)$.
The part I am confused is: If I can argue that $A$ is a finite set just because I have an injection $g \circ f : A \to [n]$.
Any help would be appreciated!
Best Answer
Since The function $f:A\to B$ is an injection then $f^{-1}$ exists for this function (because each value of $B$ has been mapped via only one value of A) and B is finite so the mapping $B \to A$ and so $A$ is definitely finite.
Now the second part Since $f$ is an injection each element of A has been mapped to only one element of B and that's true for the reverse mapping also then suppose if Cardinality($A$)$>$Cardinality($B$); According to function definition ,each element of $A$ has to be mapped to something so more than one element are mapped to the same element which is against the fact in question($f$ is an injection) so Cardinality($A$) $\le$ Cardinality($B$)