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.
(1) Let such that:
Since is injective, this implies:
Since is injective, ... you get the idea?
(2) Let . Since is surjective, we know that such that . Also, since is surjective, we know that such that
Now consider .
(3) Try to remember what it means for a function to be bijective.
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.
#1: Yes, because we know 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 , there exists some element in such that .
#3: (Yes) Just go by definition.
rename sets A, B , C for simplicity:
Originally Posted by Eagle3
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
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.
I really appreciate your help
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?
Originally Posted by Eagle3
- If , then for all . (In words, if , then divides all of the multiples of )
- If and , then
- If where is prime, then either or
Since and , then (try to see how the first two facts apply here).
Then finish it off with the third fact.
Thanks, I've never seen it written that way.
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.
Using the first bullet, we have that: (imagine ).
Using the second bullet, since we know and , then divides their difference.
Then the conclusion follows as you have written.
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?
Does it help if I write it like this:
We know and (imagine if that helps).
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.