Can the composition of 2 functions be proven using 3 formulas?

[TomMe]

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)$$\forall \ a \ \epsilon \ A : \exists ! \ b \ \epsilon \ B : (a,b) \ \epsilon \ f$$
(2)$$\forall \ b \ \epsilon \ B : \exists ! \ c \ \epsilon \ C : (b,c) \ \epsilon \ g$$.

And by definition the composition of relations f and g is

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

I should be getting $$\forall \ a \ \epsilon \ A : \exists ! \ c \ \epsilon \ C : (a,c) \ \epsilon \ g \ o \ f$$ 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.

 

[matt grime]

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]

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]

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]

So I can't write down

$$\forall \ a \ \epsilon \ A : \exists ! \ b \ \epsilon \ B : (a,b) \ \epsilon \ f$$ and $$\forall \ b \ \epsilon \ B : \exists ! \ c \ \epsilon \ C : (b,c) \ \epsilon \ g$$

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

$$=>$$ $$\forall \ a \ \epsilon \ A : \exists ! \ c \ \epsilon \ C : (a,c) \ \epsilon \ g \ o \ f$$

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]

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]

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 $$(a,b) \ \epsilon \ f$$ and $$(b,c) \ \epsilon \ g$$ 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 $$(a,c) \ \epsilon \ g \ o \ f \ => \exists \ b \ \epsilon \ B : \ (a,b) \ \epsilon \ f \ => \forall \ a \ \epsilon \ A : \exists! \ b \ \epsilon \ B$$ ?

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