1. ## functions between sets

I need help with the following proof,

Let f: maps S to T and g: maps T to U.
1. If f and g are injective then g•f (composition) is injective
2. If f and g are surjective then g•f is surjective
3. If f and g are bijective then g*f is bijective.

Thanks

2. (1) Let $a, b \in S$ such that: $g (f(a)) = g(f(b))$

Since $g$ is injective, this implies: $f(a) = f(b)$

Since $f$ is injective, ... you get the idea?

______________

(2) Let $u \in U$. Since $g$ is surjective, we know that $\exists t \in T$ such that $g(t) = u$. Also, since $f$ is surjective, we know that $\exists s \in S$ such that $f(s) = t$

Now consider $g(f(s))$.

______________

(3) Try to remember what it means for a function to be bijective.

3. So on #1, the next logical step would be a=b, which should prove #1.

On #2, then g(f(s))=g(t)=u. So all I had to do was prove that g(f(s))=u?

On #3, so if I've proved that it is injective and surjective then it is bijective by definition? If this is true, them I'm making this way more difficult than it needs to be. If not I guess I still do not get it.

Thanks for your help, I have quite a few more questions. I'm just starting the class and I'm just not getting some of this.

4. #1: Yes, because we know $f$ is injective.

#2: Isn't that what it means for a function to be surjective by definition? We've shown that for an arbitrary element in $U$, there exists some element in $S$ such that $u = g(f(s))$.

#3: Just go by definition.

5. Originally Posted by Eagle3
I need help with the following proof,

Let f: maps S to T and g: maps T to U.
1. If f and g are injective then g•f (composition) is injective
2. If f and g are surjective then g•f is surjective
3. If f and g are bijective then g*f is bijective.

Thanks
rename sets A, B , C for simplicity:
for 1, let a1, a2 in A. since f is 1-1 => f(a1)=/=f(a2) and g is 1-1 => g(f(a1))=/=g(f(a2)). therefore, gf(a1)=/= gf(a2). QED

for 2, we show forall c in C there exists a in A s.t. gf(a)=c. let c in C. g is onto => there exists b in B s.t. g(b)=c. f is onto => there exists a in A s.t. f(a)=b => therefore gf(a)=g(b)=c. therefore gof is onto. QED

6. Here is what I was trying to do for #1.
f:A to B and g:B to C
x an element of A, y an element of B, and z an element of C
if f is injective, then f(x)=f(y) which means x=y
if g is injective, then g(y)=g(z) which means y=z
based on the transitive property if x=y and y=z, then x=z
therefore, g(f(x)) would also be an injection because f(x)=g(z) and x=z which has been shown to be true.

This is why I was having so much trouble with surjective and bijective.

Can you help me get started with this one?
if p is prime and p|a and p|(a^2+b^2) prove or disprove p|b
I have looked for a counterexample and can not find one, I'm going to assume it is true.

Thanks again, trying to do this course on-line my be more than I bargained for.

7. Thanks for your help, it never ceases to amaze me how many different ways there are to do this and how much more difficult I can make it without really trying. What does =/= mean?

8. Originally Posted by Eagle3
Thanks for your help, it never ceases to amaze me how many different ways there are to do this and how much more difficult I can make it without really trying. What does =/= mean?

not equal

9. Some facts:
• If $a \mid b$, then $a \mid kb$ for all $k \in \mathbb{Z}$. (In words, if $a \mid b$, then $a$ divides all of the multiples of $b$ )
• If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$
• If $p \mid ab$ where $p$ is prime, then either $p \mid a$ or $p \mid b$

Since $p \mid a$ and $p \mid (a^2 + b^2)$, then $p \mid (a^2 + b^2 - a^2) \Leftrightarrow p \mid b^2$ (try to see how the first two facts apply here).

Then finish it off with the third fact.

10. Thanks, I've never seen it written that way.

11. ## o_O

The part I do not understand now is are you using the second bullet to justify subtracting a^2. That is the step I would have never thought to do. Since, p|b^2 then p|bb and therefore p|b since p must divide one of the two.

Thank you very much.

12. Using the first bullet, we have that: $p \mid a^2$ (imagine $k = a$).

Using the second bullet, since we know $p \mid (a^2 + b^2)$ and $p \mid a^2$, then $p$ divides their difference.

Then the conclusion follows as you have written.

13. Ok, I now understand how to prove that p|(a+b) and p|(a-b), what I'm still having trouble with is how I would know that p divides the difference. Is if merely because if it divides the sum it will divide the difference?

14. Does it help if I write it like this: $(a^2 + b^2) - a^2 \ = \ (a^2 + b^2) {\color{red} \ + \ } (-a^2)$

We know $p \mid (a^2 + b^2)$ and $p \mid (-a^2)$ (imagine $k = -a$ if that helps).

15. Ok, now I really understand what you meant by a|b and a|c, then a|(b+c). I had to go back and read it a second time before it clicked.

Thanks again you are a great teacher.