Vtgyjfy

Suppose $X$ is a set and $f : X to X$ is a function. If $X$ is a finite set, prove that $f$ is injective if and only if $f$ is surjective.
Show that when $X$ is an infinite set, the statement is not true in general.

For that, let $X = mathbb{R}$ and find a function $f: mathbb{R} to mathbb{R}$ which is injective but not surjective, and a function $g: mathbb{R} to mathbb{R}$ which is surjective but not injective

My attempt at the first part

Suppose that the function is surjective but not injective. Let $a,b in X$ such that $f(a)=f(b)$ but $a not =b$. Now since this is a finite set mapping to itself then there are not enough elements in $X$ to map to $X$ since two elements were used to map to one element, thus the function can't be surjective. Therefore if the function is surjective it is also injective.

Now suppose that the function is injective but not surjective. Let $a in X$ such that $f(b)not =a$ for all $b in X$. Since the function was assusmed to be injective each $a in X$ must map to an element of $X$, thus must have two elemetns in $X$ mapping to the same element in $X$. Hence the function can't be injective, therefore if the function is injective it must be surjective.

Would an exponetial function work for injective but not surjective since can't map to negative numbers. And an example of a function that is surjective but not injective could be a log function since none of the negative numbers get mapped to anything?

Also I'm having trouble seeing why it has to be finite for the first part to work. I understand it has something to do with the pigeonhole principle but its not that clear to me.

Your proof is a little informal. Normally this wouldn't be a problem, but the issue is that the formal version of your "counting" argument is precisely what you wish to prove. The proof is not as simple as one would initially be lead to believe.

Let's prove the following statement. Your desired statement will follow.

Let $ninmathbb{N}$ and let $f:{1,ldots,n}to{1,ldots,n}$ be a function. Then $f$ is injective iff $f$ is surjective.

Proof:

We use induction. This clearly holds whenever $n=1$. Fix $ninmathbb{N}$ and suppose that every function from ${1,ldots,n}$ into ${1,ldots,n}$ is injective iff it is surjective. Let $f:{1,ldots,n+1}to{1,ldots,n+1}$ be a function.

Suppose $f$ is injective. Denote $m:=f(n+1)$, and observe that since $f$ is injective, the function $g:{1,ldots,n}to{1,ldots,n+1}setminus{m}$ given by $g(k)=f(k)$ is well-defined and one-to-one. Define the injection $h:{1,ldots,n+1}setminus{m}to{1,ldots,n}$ by
$$
h(k) = begin{cases}
k & text{if} k<m, \
k-1 & text{if} k>m.
end{cases}
$$
Due to the fact that the composition of injective functions is injective, we have that $hcirc g:{1,ldots,n}to{1,ldots,n}$ is one-to-one. By the induction hypothesis, $hcirc g$ is onto and hence $h$ is onto. Therefore $g=h^{-1}circ(hcirc g)$ is a composition of surjective functions, which means that it is surjective. Consequently $f$ is surjective.

(I'll leave the converse to you). $square$

As far as the examples go, the exponential function works perfectly. However, a logarithmic function doesn't work because it isn't defined on all of $mathbb{R}$ (and it is injective). To fix this, you could define $f:mathbb{R}tomathbb{R}$ by $f(x)=ln|x|$ if $xne0$ and $f(0)=0$.

Edit: Actually, one can prove that this statement never holds whenever $X$ is infinite. Suppose $X$ is an infinite set. Then there is a countably infinite subset ${d_1,d_2,ldots}$ of $X$. (Caution: This uses the axiom of choice.) Define $f_i,f_s:Xto X$ by
$$
f_i(x)=begin{cases}
d_{i+1} & text{if} x=d_i text{for some} i, \
x & text{otherwise},
end{cases}
quadtext{and}quad
f_s(x)=begin{cases}
d_{i-1} & text{if} x=d_i text{for some} i>1, \
x & text{otherwise}.
end{cases}
$$
Then $f_i$ is an injection and $f_s$ is a surjection, but neither is a bijection.

The idea of the proof you gave is correct, although it is written slightly informal.

An exponential function would indeed work: define $f: mathbb{R} to mathbb{R}: x mapsto e^x$. This function is clearly injective (it is strictly increasing), but $e^x > 0$ where $x in mathbb{R}$, so the mapping is not surjective.

For the other example you have to provide, define $g: mathbb{R} to mathbb{R}: x mapsto x^3 - x$. Clearly, this function is not injective ($f(0) = f(1)$), but it is surjective

Your proof is correct. It uses pigeonhole principle. Your example of exp is also correct.

For a function to be surjective but not injective, you cannot use log, as log is not DEFINED for negative numbers. However, you can easily design a function such as $f(x) = x sin(x)$, which is surjective, but not injective.