2

Prove if an injective map $f:A\longrightarrow B$ exists there is also a surjective map from $A$ to a subset of $B$.

Say we are given an injective map $f: S \longrightarrow N$. It is easy to see that $f$ is surjective to some subset of $N$. Does it even need proving, or it enough to say, 'it simply follows'?

Ben Grossmann
  • 225,327
1125122970
  • 85
  • 1
    Well, some would say that it simply follows from addition laws that $1+1=2$. And then there's Russell & Whitehead's "Principia Mathematica", that takes a few hundred pages to get $1+1=2$. – Shaun Mar 28 '20 at 01:33
  • Can you be specific about the largest subset of $N$ for which $f$ is surjective? – Eric Towers Mar 28 '20 at 01:36
  • It wouldn't hurt to say explicitly what subset of $N$ (or $B$) you mean, rather than just saying "some subset". – Andreas Blass Mar 28 '20 at 01:36
  • For a set $P \subset N$, what do you mean by "$f$ is surjective to $N$"? Note that the map $f:S \to P$ is not defined unless you define it. – Ben Grossmann Mar 28 '20 at 01:37
  • I see your concerns, in fact after reading them I fear my question doesn't make sense. @user758469 did a good job of interpreting what I was trying to say. – 1125122970 Mar 28 '20 at 02:08
  • @Omnomnomnom, yes I meant to define a new function the same as the old however defined over a smaller codomain. – 1125122970 Mar 28 '20 at 02:08
  • @Eric Towers yes, the largest subset would simply be the range of $f$. – 1125122970 Mar 28 '20 at 02:09
  • @Andreas Blass, you are right, in fact it doesn't work for some general subset. Since I could simply define the subset as the set of elements not mapped by f. – 1125122970 Mar 28 '20 at 02:09
  • Cheers for all the comments, you have really interrogated my logic and made my question more clear. – 1125122970 Mar 28 '20 at 02:10

2 Answers2

1

Well, it depends. If is is for a class, then saying it simply follows is not enough (if you are doing it for fun, then yes that is enough). So I will assume this is for a class. If f is an injection, then each element in S is mapped to a distinct element in N. Call the set of these distinct elements of N, call it N'--- this is the range. Consider the map f' from S to N'. It is a surjection (in fact it is a bijection) because for each point n in N', there exists a point x in S such that f'(x) = n --- definition of range. Hope this proof helps if this is for a class.

Debbie
  • 840
1

Since $f:A\rightarrow B$ is injective so $|A|\le |B|$.

If $|A|=|B|$ then $f$ is surjective as well and the result follows trivially.

If $|A|<|B|$ then there must exist $B'\subset B$ with the property $B'=f(A)$ s.t. $f:A\rightarrow B'$ is surjective.

Nitin Uniyal
  • 7,946