Composition of 2 functions

  • Thread starter TomMe
  • Start date
51
0
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.
 
Last edited:

matt grime

Science Advisor
Homework Helper
9,394
3
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.
 
51
0
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

Science Advisor
Homework Helper
9,394
3
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.
 
51
0
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. :rofl:

Guess I'll stick to the "arrows" explanation then, I understand that one best.
 

matt grime

Science Advisor
Homework Helper
9,394
3
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?
 
51
0
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 <=> ?
 

Related Threads for: Composition of 2 functions

  • Posted
Replies
8
Views
11K
  • Posted
Replies
4
Views
1K
Replies
3
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top