2

Prove the following:

LEMMA

If $B$ is a subset $A$, and if an injection (one-to-one) $f: A \rightarrow B$ exists, then there is a bijection (one-to-one and onto) $g: A \rightarrow B$.

Since $f$ is a function, every $a \in A$ is sent to exactly one $b \in B$. Since $f$ is injective, we know that $a_1 \not= a_2 \implies f(a_1) \not=f(a_2)$ $\forall a_1,a_2 \in A$. This means that every $a \in A$ is sent to a unique $b \in B$ $\implies$ $|A| = |im f|$.

But since $B$ is a subset of $A$ and $im f$ is a subset of $B$, we have $|imf| \leq |B| \leq |A| \implies |imf|=|B|=|A|$ from above. But $imf=B$ implies surjectivity by definition.

Finally, since $imf \subseteq B \subseteq A$ and $|imf|=|B|=|A|$, we know that $imf=A=B$.

Do you think my answer is correct?

Thank you in advance

Community
  • 1
  • 3
    Pay attention that $B \subseteq A$ and $\lvert B \rvert = \lvert A \rvert$ do not imply $B = A$. For example, take $A = \mathbb{N}$ and $B = \mathbb{N} \setminus { 0 }$. – Luca Bressan Sep 06 '13 at 19:50

2 Answers2

1

Your answer is not quite correct. The problem is

Finally, since $\text{im } f \subseteq B \subseteq A$ and $|\text{im } f| = |B| = |A|$, we know that $\text{im } f = A = B$.

Suppose by way of example that $A = \mathbb{N}$, $f(n) = 4n \;\, \forall n$, and $B = 2\mathbb{N}$ (the even integers). Certainly $f: A \to B$ is one-to-one. Also, $\text{im } f \subseteq B \subseteq A$ since $\text{im } f = 4\mathbb{N}$, and $|\text{im } f| = |B| = |A| = |\mathbb{N}|$ as desired. But from this we cannot conclude $\text{im } f = A = B$. (We would only be able to conclude this if the sets involved were finite.)

Caleb Stanford
  • 45,895
0

If $B\subset A$, then $|B|\le |A|$, and if there is an injection from $A$ to $B$, then $|A|\le|B|$, hence $|A|=|B|$, so there is a bijection between them.

JLA
  • 6,442
  • 2
  • 24
  • 40