2

I just want to make sure my reasoning is correct. I will express the part that I am confused about.

Let $A,B,C$ be sets where $|A|<|B|$ and $|A|=|C|$, show $|C|<|B|$.

My Work

Because $|A|<|B|$ there is an injective but not surjective function $ f:A\rightarrow B$.

Because $|A|=|C|$ there is a bijective function $g:A\rightarrow C$.

Because $g$ is bijective it has an inverse: $g^{-1}: C\rightarrow A$ that is bijective.

$\Rightarrow f\circ g^{-1}: C\rightarrow A$; because $f,g^{-1}$ are both injective, $f\circ g^{-1}$ is injective.

Question

Can I assume that $f\circ g^{-1}$ is not surjective because one of its composites are not surjective?

Community
  • 1
Tsangares
  • 797

1 Answers1

1

No, in general, if $f (g(x))$ is surjective, $g$ need not be surjective. Try to imagine a counterexample yourself.

In this case, the composition is not surjective because of the conditions $|A| \lt |B|$ and $|A|=|C|$.

PROOF:

suppose $f(g^{-1}(x)) : C \to B$ is surjective. This implies that $|B| \le |C|$. We also know that $|A| =|C|$ whiich implies $|B| \le |A|$ (from the last 2 inequalities.) But we already know $|A|\lt |B|$. Contradiction. So $f(g^{-1}(x))$ is not surjective here.

Lelouch
  • 724
  • I you can't find the counterexample in thefirst case, let me know. I can edit it into the answer. – Lelouch Mar 10 '17 at 04:22
  • I think you dropped some "not"s in your first sentence, because $f \circ g$ surjective does imply $f$ surjective. – JonathanZ Mar 10 '17 at 04:41
  • Thanks, i actually meant g need not be surjective, for the composition to be surjective. So the OP's assumption is generally untrue,i.e 'if any of the function is not surjective, the composition will be not surjective.' This claim is not true. – Lelouch Mar 10 '17 at 04:54