A,B nonempty finite sets f is a bijection from A to B. Prove if $g:A\rightarrow B$ is injective then it's surjective. Is this true for infinite sets?

If f is a bijection from A to B all we can say is that A and B have the same cardinality because bijection means every element in A has a unique element in B and all elements in both are mapped.

If g is injective then that means every element in A has a unique element in B that it's mapped to, but because A and B are the same cardinality that means that every element in B must have an element it's mapped to in A, therefore it is surjective.

Let me know if any of the above proof is incorrect.

I don't know if this holds true for infinite sets though. I want to say no? Because if they're both infinite sets does that mean they have the same cardinality?

  • $\begingroup$ Well in this case it must it be, because A and B have the same cardinality? If something is injective then all elements in A have a unique element in B so if it's injective it must be surjective no? $\endgroup$ – Dylan Y Nov 28 '19 at 11:45
  • $\begingroup$ O sorry I edited it. Yes g is from A to B $\endgroup$ – Dylan Y Nov 28 '19 at 11:49
  • $\begingroup$ There is bijection $\mathbb N\to\mathbb N$ (e.g. the identity). Let $g$ be defined as $n\mapsto2n$. Is it injective? Is it surjective? $\endgroup$ – drhab Nov 28 '19 at 11:53
  • $\begingroup$ It's injective but it's not surjective because 1 in the range isn't mapped to anything in the domain $\endgroup$ – Dylan Y Nov 28 '19 at 11:54
  • 1
    $\begingroup$ You better say: no element is mapped to $1$ (so not surjective). So this makes clear that the statement is not true for infinite sets, doesn't it? $\endgroup$ – drhab Nov 28 '19 at 11:56

Your reasoning for $g$ being injective then it's surjective is intutiively fine, but formally it's a bit lacking, since the (essential) assumption of finiteness isn't used anywhere in the proof. This is a red flag, because you need $A$ and $B$ to be finite for this to be true!

You can piece together a more rigorous proof using the following two lemmas:

Lemma 1. Let $A$ and $B$ be sets and let $g : A \to B$ be an injection. Then $|A| = |g[A]|$, where $g[A]$ is the image of $g$.

Lemma 2. Let $B$ be a finite set and let $V \subseteq B$. If $|V| = |B|$, then $V=B$.

These lemmas together imply that $g$ is a bijection: Lemma 1 implies that $|g[A]| = |B|$ since $|A| = |g[A]|$ and there is a bijection $A \to B$. Lemma 2 is where the assumption of finiteness is used: setting $V = g[A]$ tells you that $g[A]=B$, which is equivalent to saying that $g$ is surjective.

Now, of course, you need to worry about whether you can use Lemmas 1 and 2 in your proof. Lemma 1 has an easy proof, but Lemma 2 is more fiddly: you can prove it by induction on $|B|$.

P.S. As drhab mentioned in the comments, this does indeed fail when $A$ and $B$ are not assumed to be (Dedekind-)finite.

| cite | improve this answer | |

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.