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

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?

• 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? – Dylan Y Nov 28 '19 at 11:45
• O sorry I edited it. Yes g is from A to B – Dylan Y Nov 28 '19 at 11:49
• 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? – drhab Nov 28 '19 at 11:53
• It's injective but it's not surjective because 1 in the range isn't mapped to anything in the domain – Dylan Y Nov 28 '19 at 11:54
• 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? – 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.