# functions between sets

• Jan 25th 2009, 07:27 PM
Eagle3
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
• Jan 25th 2009, 07:47 PM
o_O
(1) Let $\displaystyle a, b \in S$ such that: $\displaystyle g (f(a)) = g(f(b))$

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

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

______________

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

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

______________

(3) Try to remember what it means for a function to be bijective.
• Jan 26th 2009, 05:29 PM
Eagle3
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.
• Jan 26th 2009, 06:31 PM
o_O
#1: Yes, because we know $\displaystyle 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 $\displaystyle U$, there exists some element in $\displaystyle S$ such that $\displaystyle u = g(f(s))$.

#3: (Yes) Just go by definition.
• Jan 26th 2009, 06:50 PM
GaloisTheory1
Quote:

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
• Jan 26th 2009, 06:54 PM
Eagle3
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.

• Jan 26th 2009, 07:01 PM
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?
• Jan 26th 2009, 07:03 PM
GaloisTheory1
Quote:

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
• Jan 26th 2009, 07:03 PM
o_O
Some facts:
• If $\displaystyle a \mid b$, then $\displaystyle a \mid kb$ for all $\displaystyle k \in \mathbb{Z}$. (In words, if $\displaystyle a \mid b$, then $\displaystyle a$ divides all of the multiples of $\displaystyle b$ )
• If $\displaystyle a \mid b$ and $\displaystyle a \mid c$, then $\displaystyle a \mid (b + c)$
• If $\displaystyle p \mid ab$ where $\displaystyle p$ is prime, then either $\displaystyle p \mid a$ or $\displaystyle p \mid b$

Since $\displaystyle p \mid a$ and $\displaystyle p \mid (a^2 + b^2)$, then $\displaystyle 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.
• Jan 26th 2009, 07:13 PM
Eagle3
Thanks, I've never seen it written that way.
• Jan 26th 2009, 07:40 PM
Eagle3
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.
• Jan 26th 2009, 07:42 PM
o_O
Using the first bullet, we have that: $\displaystyle p \mid a^2$ (imagine $\displaystyle k = a$).

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

Then the conclusion follows as you have written.
• Jan 26th 2009, 08:10 PM
Eagle3
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?
• Jan 26th 2009, 08:14 PM
o_O
Does it help if I write it like this: $\displaystyle (a^2 + b^2) - a^2 \ = \ (a^2 + b^2) {\color{red} \ + \ } (-a^2)$

We know $\displaystyle p \mid (a^2 + b^2)$ and $\displaystyle p \mid (-a^2)$ (imagine $\displaystyle k = -a$ if that helps).
• Jan 26th 2009, 08:28 PM
Eagle3
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.