October 19th, 2011, 10:36 PM  #1 
Senior Member Joined: Feb 2010 Posts: 199 Thanks: 0  Onetoone and onto
Ok so with this one i have absolutely no idea what to do ... Suppose that g is a function from A to B and f is a function from B to C a) show that if both f and g are onetoone functions, then f ? g is onetoone b) show that is bot f and g are onto functions, then f ? g is also onto i know that onetoone looks like ?x ? I ?y ? P [x ? y ? f(x) ? f(y)] and onto looks like ?x ? P ?y ? I [f(x) = y] and also that (f ? g)(a) = f[g(a)] if it's even relevant ... i have no clue how to tie it all together <:\ ... the book explains those two concepts separately, but i don't know what to do with this problem how can i find out if they're onetoone or onto if i don't even know what elements are in those sets? sorry if i post too much ... it is homework but it's not graded so it's not like im cheating or anything, i just really don't wanna fail this class 
October 19th, 2011, 10:51 PM  #2 
Global Moderator Joined: Nov 2009 From: Northwest Arkansas Posts: 2,766 Thanks: 4  Re: Onetoone and onto
fog is onto if, for every c in C, there exists as a in A such that fog(a) = c. But since f is onto, we have that f(b) = c for some b in B, and since g is onto, we have that b = g(x) for some x in A (I changed the letters to avoid confusion). So g(x) = b f(g(x)) = f(b) = c So this value of x exists, which is what we wanted to show. You can formalize this ad nausuem. 
October 20th, 2011, 09:53 AM  #3  
Senior Member Joined: Feb 2010 Posts: 199 Thanks: 0  Re: Onetoone and onto Quote:
i can conjure up something like: a) If ?x,y ? A [x ? y ? f(x) ? f(y)] and ?x,y ? B [x ? y ? f(x) ? f(y)], then (f ? g) : ?x,y ? C [x ? y ? f(x) ? f(y)] b) If ?a ? A ?b ? B [f(a) = b] and ?b ? B ?c ? C [f(b) = c], then (f ? g) : ?a ? A ?c ? C [f(a) = c] but that just looks like a bunch of stuff slapped together ... cuz it is >.< .. nor is it proof ... How do you know how to write it up nicely?  
October 20th, 2011, 10:28 AM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Onetoone and onto Quote:
Once you have these written out (rather than just generic definitions) "all" that you need to do is combine the ones that you have and manipulate until you get to the desired one. In this case the symbolmoving is the whole point, because the proof (formalism aside) is 'obvious'.  
October 20th, 2011, 10:48 AM  #5  
Senior Member Joined: Feb 2010 Posts: 199 Thanks: 0  Re: Onetoone and onto Quote:
g(a) = b and f(b) = c and ?a ? A ?b ? B [g(a) = b] and ?b ? B ?c ? C [f(b) = c] and ?x,y ? A [x ? y ? f(x) ? f(y)] and ?x,y ? B [x ? y ? f(x) ? f(y)] and blah blah blah ... ? so that's not right then?  
October 20th, 2011, 05:14 PM  #6  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Onetoone and onto Quote:
 
October 20th, 2011, 05:59 PM  #7  
Senior Member Joined: Feb 2010 Posts: 199 Thanks: 0  Re: Onetoone and onto Quote:
 
October 21st, 2011, 06:35 AM  #8  
Senior Member Joined: Jun 2011 Posts: 298 Thanks: 0  Re: Onetoone and onto Quote:
1. Given 2. Assumption 3. Definition 4. Definition of 11 5. Definition of 11 6. since function 7. Prove 8. From 2,5 9. From 3, and 8 Q.E.D By 6 & 10, For part b you must know that and . Since it's an existential statement, you need only an example.  

Tags 
onetoone 
Thread Tools  
Display Modes  
