Composition of 2 functions

  • Thread starter TomMe
  • Start date
  • #1
TomMe
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:

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,426
4
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.
 
  • #3
TomMe
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?
 
  • #4
matt grime
Science Advisor
Homework Helper
9,426
4
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.
 
  • #5
TomMe
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.
 
  • #6
matt grime
Science Advisor
Homework Helper
9,426
4
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?
 
  • #7
TomMe
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 <=> ?
 

Suggested for: Composition of 2 functions

  • Last Post
Replies
7
Views
917
Replies
3
Views
529
Replies
4
Views
707
Replies
2
Views
509
Replies
1
Views
436
  • Last Post
Replies
2
Views
365
Replies
1
Views
372
Replies
0
Views
425
Replies
19
Views
1K
  • Last Post
Replies
6
Views
1K
Top