Sets and functions

Given the next sets: $A=\{1,2\}$ , $B=\mathbb{N}$,

a) Describe all the functions from $A$ to $B$ that are not injective.

b) Describe all the functions from $B$ to $A$ that are not onto.

c) Prove or disprove the next:

(i) The next functions exist $f\colon A\to B$ and $g\colon B\to A$ if $g\circ f$ reversal

(ii) the next functions exist $f\colon A\to B$ and $g\colon B\to A$ if $f\circ g$ reversal

Need help here. Thanks.

• Where are you stuck? – Aryabhata Dec 29 '10 at 18:53
• What does «if $g\circ f$ reversal» mean? – Mariano Suárez-Álvarez Dec 29 '10 at 18:53
• This seems kind of homework-y to me, but I'll give hints. For (a), what does it mean for something to be injective? We have that f(a) = f(b) implies a = b. Since we only have two elements here, if we send one of them to an element in $N$, then where does the second one have to go? For (b) ON, I guess, means surjective. Surjectivity means that the function "hits" all the elements in A. Where would we have to send elements in B to in order for them to all "miss" one element in A? – user2959 Dec 29 '10 at 19:06
• reversal in like reverse the function the other way i think and im stuck everywhere need some answers here – user5214 Dec 29 '10 at 19:29
• For (c), I think you are trying to ask if there exist functions $f$ and $g$ so that (i) $g \circ f$ is bijective (invertible) or (ii) $f \circ g$ is bijective. Remember, a function is bijective if and only if it is both injective and surjective. – Hans Parshall Dec 29 '10 at 19:36

The first two follow from the definitions, so I'm assuming you're having some difficulty with what injective (or one to one) and surjective (or onto) mean.

Let $f : A \rightarrow B$ be a function.

Our function $f$ is injective if, provided there is some $a$ in $A$ with $f(a) = b$, there is only one such $a$. Put another way, everything in $B$ that is "hit" by $f$ is "hit" only one time. This is why one-to-one is a good term: for every output, there is one input.

Our function $f$ is surjective if, for every $b$ in $B$, there is some $a$ with $f(a) = b$. Essentially, $f$ is surjective if everything in $B$ is "hit" by $f$. This is why onto is a good term: you can picture $B$ being covered by $f$.

For your part (a), think about functions from ${1,2}$ to $\mathbb{N}$ that do not have the property that "for every output, there is one input."

For your part (b), think about functions from $\mathbb{N}$ to ${1,2}$ that do not have the property that "everything is hit" by the function.

You need to reword part (c); it does not make sense as written.

• for a and b i dont understand how can i show all the functions if theres lots of them.. – user5214 Dec 29 '10 at 19:27
• and for part c i hope i translated it correctly: the next functions exist f:A->B and g:B->A if gof reversal i mean reversal in like you can reverse the function or something like that – user5214 Dec 29 '10 at 19:28
• There are lots of functions for part (a), but you need only find the ones that break the rules. For example, is a function injective if $1$ and $2$ both get sent to $17$? What about if $1$ goes to $10$ and $2$ goes to $20$? – Hans Parshall Dec 29 '10 at 19:32
• For part (b), there aren't actually very many functions from $\mathbb{N}$ to $\{1,2\}$ that aren't surjective. You'll see what I mean when you figure it out! – Hans Parshall Dec 29 '10 at 19:33

(a) Since $A$ has only two elements, the only way for a function $f\colon A\to X$ (for any set $X$) to not be injective is if $f(1)=f(2)$. So you want all functions from $A$ to $B$ in which $f(1)=f(2)$. Now, while there are indeed "lots of them" (infinitely many) they all have a very easy description. Hint: the word that describes these functions starts with "con" and ends with "ants".

(b) Again, since $A$ has only two elements, the only way for a function $g\colon X\to A$ to not be onto (surjective) is if either you never get $1$, or you never get $2$ as images of $g$. While there are many, many, functions from $B$ to $A$, there are very few in which this happens. Hint: the word that describes theses functions is the same as in (a).

(c-i) You want to know if you can define functions $A\stackrel{f}{\to} B\stackrel{g}{\to}A$ such that the composition is both one-to-one and onto. Not too hard, since there are only two functions from $A$ to $A$ that are both one-to-one and onto. See if you can come up with some easy functions $f$ and $g$ that do this.

(c-ii) Here you want to know if you can find functions $B\stackrel{g}{\to}A\stackrel{f}{\to}B$ so that the composition is both one-to-one and onto. Again, this is not hard if you think about what these things mean. Can you have a one-to-one map from $B$ to $A$? Can you have an onto map from $A$ to $B$? Think about it. Note that these $f$ and $g$ don't have to be the same as in (c-i), they are only asking you if some such functions exist at all.