My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
October 19th, 2011, 10:36 PM   #1
Senior Member
 
Solarmew's Avatar
 
Joined: Feb 2010

Posts: 199
Thanks: 0

One-to-one 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 one-to-one functions, then f ? g is one-to-one
b) show that is bot f and g are onto functions, then f ? g is also onto

i know that one-to-one 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 one-to-one 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
Solarmew is offline  
 
October 19th, 2011, 10:51 PM   #2
Global Moderator
 
The Chaz's Avatar
 
Joined: Nov 2009
From: Northwest Arkansas

Posts: 2,766
Thanks: 4

Re: One-to-one 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.
The Chaz is offline  
October 20th, 2011, 09:53 AM   #3
Senior Member
 
Solarmew's Avatar
 
Joined: Feb 2010

Posts: 199
Thanks: 0

Re: One-to-one and onto

Quote:
Originally Posted by The Chaz
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.
how to formalize it is exactly the part i'm having trouble with X.X ... so the last part is f(g(a)) = f(b) = c?

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?
Solarmew is offline  
October 20th, 2011, 10:28 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: One-to-one and onto

Quote:
Originally Posted by Solarmew
how to formalize it is exactly the part i'm having trouble with
In cases like that, start by writing out the definitions involved with your variables substituted in. So you have a function g from A to B and a function f from B to C and you want to show that if f and g are one-to-one that f composed with g is one-to-one. So what is the definition of one-to-one for g (using g, A, and B), what is the definition of one-to-one for f (using f, B, and C), what is the definition of one-to-one for the composition (using the composition, A, and C), and what is the definition of the composition f ? g?

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 symbol-moving is the whole point, because the proof (formalism aside) is 'obvious'.
CRGreathouse is offline  
October 20th, 2011, 10:48 AM   #5
Senior Member
 
Solarmew's Avatar
 
Joined: Feb 2010

Posts: 199
Thanks: 0

Re: One-to-one and onto

Quote:
Originally Posted by CRGreathouse
So what is the definition of one-to-one for g (using g, A, and B), what is the definition of one-to-one for f (using f, B, and C), what is the definition of one-to-one for the composition (using the composition, A, and C), and what is the definition of the composition f ? g?
i thought those things i wrote were them if they're not then i don't know

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?
Solarmew is offline  
October 20th, 2011, 05:14 PM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: One-to-one and onto

Quote:
Originally Posted by Solarmew
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?
Well, I asked for the same property for three different functions (f, g, and fog) so if it was right I'd see the same thing, three times, except with different functions and sets. But I don't. In fact, I don't see fog (or f(g(...))) anywhere.
CRGreathouse is offline  
October 20th, 2011, 05:59 PM   #7
Senior Member
 
Solarmew's Avatar
 
Joined: Feb 2010

Posts: 199
Thanks: 0

Re: One-to-one and onto

Quote:
Originally Posted by CRGreathouse
Quote:
Originally Posted by Solarmew
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?
Well, I asked for the same property for three different functions (f, g, and fog) so if it was right I'd see the same thing, three times, except with different functions and sets. But I don't. In fact, I don't see fog (or f(g(...))) anywhere.
Aaaaand you lost me I don't understand what you're saying at all I give up
Solarmew is offline  
October 21st, 2011, 06:35 AM   #8
Senior Member
 
Joined: Jun 2011

Posts: 298
Thanks: 0

Re: One-to-one and onto

Quote:
Originally Posted by Solarmew
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 one-to-one functions, then f ? g is one-to-one
b) show that is bot f and g are onto functions, then f ? g is also onto

i know that one-to-one looks like
?x ? I ?y ? P [x ? y ? f(x) ? f(y)]
and onto looks like
?x ? P ?y ? I [f(x) = y]
Proof of Part (a)
1. Given
2. Assumption
3. Definition
4. Definition of 1-1
5. Definition of 1-1
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.
Math Dreamer is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
onetoone



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes






Copyright © 2018 My Math Forum. All rights reserved.