Is it possible to create a function that's onto but not 1-1 between two sets with the same cardinality?

309 Views Asked by At

Given two sets, $S = \{1, 2, 3\}$ and $T = \{a, b, c\}$ is it possible to create a function $F:S\rightarrow T$ that is onto but not one to one? It seems like the only way to do this would be not to use all the elements in $S$, but then it wouldn't be a function.

2

There are 2 best solutions below

0
On BEST ANSWER

If the two sets have infinite cardinality, then yes; Take for example the function that sends each natural number to its half, rounded down. The function is clearly onto, because we know the number $2k$ will be mapped to $k$, for any $k$ you pick. But it is not 1-1 because $3$ and $2$ are mapped to $1$, for example.

In the case of finite sets, such a function would not be possible, as a function $f: S \to T$ onto can only exist iff $|S| \geq |T|$ and a function that is 1-1 can only exist iff $|T| \geq |S|$. If $|T| = |S|$ then a function that is onto is automatically 1-1

0
On

A mapping between two finite sets of same cardinality is onto if and only if it's $1-1$. This is a well-known property, so in your case such a function doesn't exist.