Injection from finite set to equally sized set is surjection

[Bipolarity]

This is a rather simple question, so it has been rattling my brain recently.
Consider a surjective map $f : S \rightarrow T$ where both $S$ and $T$ are finite sets of equal cardinality. Then is $f$ necessarily injective? I proved the converse, which turned out to be quite trivial, but this is giving me some trouble indeed. Any initial thoughts on whether it's true (pretty sure it is true!) and how I might go about proving it?

Thanks!

BiP

 

[PeroK]

This is a rather simple question, so it has been rattling my brain recently.
Consider an injective map $f : S \rightarrow T$ where both $S$ and $T$ are finite sets of equal cardinality. Then is $f$ necessarily surjective? I proved the converse, which turned out to be quite trivial, but this is giving me some trouble indeed. Any initial thoughts on whether it's true (pretty sure it is true!) and how I might go about proving it?

Thanks!

BiP

The truth of this is actually the basis for counting!

 

[WWGD]

For an overkill, try inclusion/exclusion . Still, an issue with this question is the set of starting definitions.
My working definition is that, for finite sets S,T , they have the same cardinality iff there is a bijection between them.
What is yours, OP?

 

[Bipolarity]

P.S. Slight mistake, I meant to prove that surjection implies injection, not the other way around.

I agree with the definition that two sets have equal cardinality if a bijection exists between them. But how does that prove that every surjection from $S$ to $T$ is also a bijection?

So far, it is clear that $|S| = |f(S)|$ since $f$ is a surjection. But what next?

 

[PeroK]

P.S. Slight mistake, I meant to prove that surjection implies injection, not the other way around.

I agree with the definition that two sets have equal cardinality if a bijection exists between them. But how does that prove that every surjection from $S$ to $T$ is also a bijection?

So far, it is clear that $|S| = |f(S)|$ since $f$ is a surjection. But what next?

Imagine there are 30 students in a class and 30 desks. Where the students sit is a mapping from the set of students to the set of desks.

If every desk is occupied (surjection) then every desk must have only one student (injection). How could there be two students sharing a desk unless one desk is unoccupied?

This is simply counting, surely?

 

[WWGD]

P.S. Slight mistake, I meant to prove that surjection implies injection, not the other way around.

I agree with the definition that two sets have equal cardinality if a bijection exists between them. But how does that prove that every surjection from $S$ to $T$ is also a bijection?

So far, it is clear that $|S| = |f(S)|$ since $f$ is a surjection. But what next?

You don't like the inclusion/exclusion argument? It is high-powered, but I think it does the job: what is the size of f(S): it is $|S|-| t \in T : t= f(s_k)=f(s_j), s_j, s_k \in S, s_j \neq s_j |+ |t \in T: t=f(s_j)=f(s_k)=f(s_t): s_j \neq s_k , s_j \neq s_t |+...$

i.e., |f(S)\= size of S minus the number of elements of T that are "hit" twice +.. number. of elemets hit 3 times - ...

 

[wabbit]

You don't like the inclusion/exclusion argument? It is high-powered, but I think it does the job: what is the size of f(S): it is $|S|-| t \in T : t= f(s_k)=f(s_j), s_j, s_k \in S, s_j \neq s_j |+ |t \in T: t=f(s_j)=f(s_k)=f(s_t): s_j \neq s_k , s_j \neq s_t |+...$

i.e., |f(S)\= size of S minus the number of elements of T that are "hit" twice +.. number. of elemets hit 3 times - ...

One issue with this is that is I can't imagine the same person asking the question and understanding your answer. Can you ?

 

[WWGD]

One issue with this is that is I can't imagine the same person asking the question and understanding your answer.

Yes, it is too high tech for the situation, but I can't think of anything else at this point.

 

[wabbit]

The easiest way as suggested by PeroK is just counting. But if we want an abstract version with no counting, that can be applied as soon as we define "finite set" etc, maybe the following :

Since S and T have the same cardinality, there is a bijection $\phi: T \rightarrow S$. Let's use that and set $g=\phi\circ f$.

(1) g is a surjective function from S onto itself.

Now assume f is not injective so that there exist $x\neq y, g(x)=g(y)$, and consider the restriction h of g to $S-\{x\}$

(2) h has the same image as g.

So h is a surjective function from a strict subset of S onto S.

(3) This means that S is infinite.

OP should check (1), (2), and (3)

Actually (3) is kinda cheating, I am assuming that is the definition given for a finite set. If a different definition is used, proving (3) may or may not be easy. @Bipolarity, what is your definition of a finite set?

 

[PeroK]

Let $|S| = |T| = n \ (n \ge 1)$ and $f:S \ \rightarrow \ T$

Proposition: $f$ is a surjection iff it is an injection.

Let $S = \lbrace s_1 \dots s_n \rbrace$ and $T = \lbrace t_1 \dots t_n \rbrace$

You can do this from the definition of a finite set of order $n$

Assume $f$ is a surjection but not a injection. $\exists i \ne j$ such that $f(s_i) = f(s_j)$

Now the restriction of $f: S-s_j \ \rightarrow T$ is a surjection, hence $|T| \le n-1$, which is a contradiction.

Assume $f$ is an injection but not a surjection. $\exists i$ such that $t_i$ is not mapped to by $f$

Hence $f$ is an injection from $S$ to $T-t_i$ and $|S| \le n-1$ which is also a contradiction.

 

[jk22]

I think you can find a surjective map that is not an injection (in fact i cheat on the word map):

Let S={a,b} T={1,2}

Pose f(a)=1 f(b)={1,2} a multivalued map it is clearly surjective but not injective since one image of b is the same as of a.

 

[wabbit]

I think you can find a surjective map that is not an injection (in fact i cheat on the word map):

Let S={a,b} T={1,2}

Pose f(a)=1 f(b)={1,2} a multivalued map it is clearly surjective but not injective since one image of b is the same as of a.

No. This is not a map from S to T but from S to something else - you did not define it but whatever you choose must be a set X such that $\{1,\{1,2\}\}\subset X$.

It is clearly injective in any case since $f(a)\neq f(b)$, in fact $f(a)\in f(b)$. It may or may not be surjective depending on what target space you decide upon.

 

[jk22]

Yes the notation is not good but we can clearly see in a Venn diagram. Maybe if we write f(b)=1,2 ?

 

[wabbit]

Not quite, f(b)=1,2 doesn't mean much. You can define multivalued functions but they are not functions from S to T here but functions from S to 2^T. Of course you can define a notion of "multivalued surjectivity" too and derive its properties, but since this doesn't have a lot to do with the topic of this thread, perhaps a new thread would be more appropriate.