# Thread: Equivalence Relations and Functions

1. ## Equivalence Relations and Functions

Need help on the following problem:
Let A={1,2,3,4,5,6}. In each case, give an example of a function f:A->A with the indicated properties, or explain why no such function exists.
a) f is bijective, but not 1A.
b) f is one-to-one, but not onto

Now set A=N (natural numbers)
a) f is bijective, but not 1A.
b) f is one-to-one, but not onto

2. Originally Posted by kturf
Need help on the following problem:
Let A={1,2,3,4,5,6}. In each case, give an example of a function f:A->A with the indicated properties, or explain why no such function exists.
a) f is bijective, but not 1A.
b) f is one-to-one, but not onto

Now set A=N (natural numbers)
a) f is bijective, but not 1A.
b) f is one-to-one, but not onto
What is 1A?

For the first one b) it is impossible

Theorem: If $f:A\mapsto A$ is injective and $A$ is finite then it is surjective.

Proof: By definition $\left|\text{Im }f\right|\le\left|\text{CoDom }f\right|$ where $\text{Im}$ is the image and $\text{CoDom}$ is the codomain. But for the case of injective functions $\left|\text{Im }f\right|=\left|\text{Dom }f\right|$, which implies then that $\left|\text{Dom }f\right|\le\left|\text{CoDom }f\right|$. In our case we have that $\left|\text{Dom }f\right|=\left|A\right|$. Now suppose that $f$ was not surjective, then $\left|A\right|<\left|\text{CoDom }f\right|=\left|A\right|$ which is a contradiction.

For the second one b) what about $f(n)=n+1$?

3. The notation should be $1_A$, the identity mapping of A.

4. Originally Posted by kturf
Need help on the following problem:
Let A={1,2,3,4,5,6}. In each case, give an example of a function f:A->A with the indicated properties, or explain why no such function exists.
a) f is bijective, but not 1A.
b) f is one-to-one, but not onto

Now set A=N (natural numbers)
a) f is bijective, but not 1A.
b) f is one-to-one, but not onto
a) Uhh....yeah? You tell me why.

a) Samesies

Originally Posted by Shanks
The notation should be $1_A$, the identity mapping of A.
Good eye! I usually see it as $i_A$ or $\iota_A$