Register to reply

Composition of 2 functions

by TomMe
Tags: composition, functions
Share this thread:
TomMe
#1
Aug3-05, 03:31 AM
P: 51
Can anyone show me how to prove exactly that the composition of 2 function is again a function, by using the following 3 formulas?

Suppose f: A -> B and g: B -> C are functions, then

(1)[tex]\forall \ a \ \epsilon \ A : \exists ! \ b \ \epsilon \ B : (a,b) \ \epsilon \ f[/tex]
(2)[tex]\forall \ b \ \epsilon \ B : \exists ! \ c \ \epsilon \ C : (b,c) \ \epsilon \ g[/tex].

And by definition the composition of relations f and g is

(3)[tex] g \ o \ f = \{(a,c) \ | \ \exists \ b \ \epsilon \ B : (a,b) \ \epsilon \ f \ and \ (b,c) \ \epsilon \ g \}[/tex].

I should be getting [tex]\forall \ a \ \epsilon \ A : \exists ! \ c \ \epsilon \ C : (a,c) \ \epsilon \ g \ o \ f[/tex] but I'm not sure how to combine the givens. I can do it in words, no problem, but I'm not that good in the use of quantifiers.

Thanks in advance.
Phys.Org News Partner Science news on Phys.org
Bees able to spot which flowers offer best rewards before landing
Classic Lewis Carroll character inspires new ecological model
When cooperation counts: Researchers find sperm benefit from grouping together in mice
matt grime
#2
Aug3-05, 03:49 AM
Sci Advisor
HW Helper
P: 9,396
for a in A there is a unique b in B such that f(a)=b, and for b in B there is a unique c in C such that g(b)=c, hence there is a unique c in C such that gf(a)=c, so gf is a function.
TomMe
#3
Aug3-05, 04:59 AM
P: 51
Well, yes that's what I meant by explaining in words. But is there a way to do this using formulas and laws of logic?

matt grime
#4
Aug3-05, 06:19 AM
Sci Advisor
HW Helper
P: 9,396
Composition of 2 functions

that is a formula and uses logic. it isn't a hand wavy "idea" of the proof. if you want use the formula for f being a f****ion AND the formula for g being a function IMPLIES the formula for gf being a fucntin then, but in order to prove that the law is true you still need to think abuot it not purely in terms of formulae.
TomMe
#5
Aug3-05, 07:53 AM
P: 51
So I can't write down

[tex]\forall \ a \ \epsilon \ A : \exists ! \ b \ \epsilon \ B : (a,b) \ \epsilon \ f[/tex] and [tex]\forall \ b \ \epsilon \ B : \exists ! \ c \ \epsilon \ C : (b,c) \ \epsilon \ g[/tex]

and use the laws of logic to move around some quantifiers to get

[tex]=>[/tex] [tex]\forall \ a \ \epsilon \ A : \exists ! \ c \ \epsilon \ C : (a,c) \ \epsilon \ g \ o \ f[/tex]

without really thinking about it? That's too bad, because I already spent a lot of time trying to figure it out that way.

Guess I'll stick to the "arrows" explanation then, I understand that one best.
matt grime
#6
Aug3-05, 08:02 AM
Sci Advisor
HW Helper
P: 9,396
this is one of my big problems with teaching people logic without explaining to them that knowing whent o show something is a tautology, or that (A implies B) and (B implies C) implies (A implies C) doesn't actually help us ever prove anything about, say continuous functions. it does tell me that in order to show A implies C i can go via an intermediate step B but doesn't tell me how (if it is even possible) to make that deduction. moving quantifiers aroud will produce (hopefully) equivalent statements and what you are aiming to do is get to one that is "more obviously true", but i ask you what can be more obviously true than the one you have written down?
TomMe
#7
Aug5-05, 09:41 AM
P: 51
I'm not really well versed in the use of logic, so forgive me if I don't fully understand your explanation above. I know the basic concepts of propositional logic, which is extremely useful when doing proofs.

But in this case I seem to have a problem of interpretation. Trying to unite both pairs [tex](a,b) \ \epsilon \ f[/tex] and [tex](b,c) \ \epsilon \ g[/tex] in (3) gives me a headache.
Maybe because that is not the way to do it then? I should focus on those intermediate steps instead?

Then, just bear with me, can I say that if [tex](a,c) \ \epsilon \ g \ o \ f \ => \exists \ b \ \epsilon \ B : \ (a,b) \ \epsilon \ f \ => \forall \ a \ \epsilon \ A : \exists! \ b \ \epsilon \ B[/tex] ?

Or in other words, can I interpret the | and : in (1), (2) and (3) as => or <=> ?


Register to reply

Related Discussions
Mineral and their composition Chemistry 12
Law of Composition of Velocities Advanced Physics Homework 1
Percentage composition Biology, Chemistry & Other Homework 1
Composition and Identity of functions Calculus 3
Me sci-fi composition Science Fiction & Fantasy 6