My Math Forum One-to-one and onto

 Applied Math Applied Math Forum

 October 19th, 2011, 10:36 PM #1 Senior Member     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
 October 19th, 2011, 10:51 PM #2 Global Moderator     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.
October 20th, 2011, 09:53 AM   #3
Senior Member

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?

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: 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'.

October 20th, 2011, 10:48 AM   #5
Senior Member

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?

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: 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.

October 20th, 2011, 05:59 PM   #7
Senior Member

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

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. $G: A\rightarrow B \quad F: B\rightarrow C$ Given
2. $s,t \in A\; \& \; s\neq t$ Assumption
3. $\forall s\in A,F\circ G (s)=F(G(s))$ Definition
4. $\forall x,y \in B [x\neq y\Rightarrow F(x)\neq F(y)]$ Definition of 1-1
5. $\forall s,t \in A [s\neq t\Rightarrow G(s)\neq G(t)]$ Definition of 1-1
6. $\text{ran }G= \text{dom }F$ since $F\circ G=$ function
7. Prove $\forall x,y \in B\forall s,t \in A[x\neq y\Rightarrow G(s)\neq G(t)]$
8. $G(s)\neq G(t)$ From 2,5
9. $F\circ G(s) \neq F\circ G(t)$ From 3, and 8
Q.E.D

By 6 & 10, $F\circ G(s) \neq F\circ G(t) \quad \Leftrightarrow \quad F(G(s))\neq F(G(t))\quad \Leftrightarrow \quad F(x)\neq F(y)$

For part b you must know that $\text{ran }G=B$ and $\text{ran F}=C$. Since it's an existential statement, you need only an example.

 Tags onetoone

,
,
,

,

,

,

,

,

,

,

,

,

,

,

prove that if fog is onto, then f is onto

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Contact - Home - Forums - Cryptocurrency Forum - Top