Question about functions
December 23, 2008 5:57 AM Subscribe
Question about functions. Probably pretty easy for those who know something about math.
How would I describe the relation between two functions that have the same, um, structure, but have completely different elements in their range and domain? So, for example:
F has 1, 2, 3, and 4 in both its range and domain.
F(1) = 4
F(2) = 4
F(3) = 3
F(4) = 3
G has A, B, C, and D in both its range and domain.
G(A) = D
G(B) = D
G(C) = C
G(D) = C
There is obviously a structural similarity between these two functions but I don't know how to describe it. I got a little lost reading about morphisms and stuff on wikipedia and thought someone here could help.
How would I describe the relation between two functions that have the same, um, structure, but have completely different elements in their range and domain? So, for example:
F has 1, 2, 3, and 4 in both its range and domain.
F(1) = 4
F(2) = 4
F(3) = 3
F(4) = 3
G has A, B, C, and D in both its range and domain.
G(A) = D
G(B) = D
G(C) = C
G(D) = C
There is obviously a structural similarity between these two functions but I don't know how to describe it. I got a little lost reading about morphisms and stuff on wikipedia and thought someone here could help.
Oops, "starting with the 2 in the top left, I can go rightwards under F (getting 4)" should have been "starting with the 2 in the top left, I can go rightwards under F (getting D)".
posted by gleuschk at 7:10 AM on December 23, 2008
posted by gleuschk at 7:10 AM on December 23, 2008
Gleuschk, forgive me if I'm mistaken, but I think your commutative diagram is a touch wrong. You should have your upper-right and your lower-left switched. F acting on {1,2,3,4} gives elements in {1,2,3,4}, whereas you have it in {A,B,C,D}. The reverse is the case for \phi. This then means that your correct at 7:10 was wrong, and that your original writing of that sentence was correct. Although in the second part of that sentence you want or down first (getting D) and then rightwards (getting D).
But painquale, favourite his comment if any. That was a wonderful answer.
posted by Lemurrhea at 7:24 AM on December 23, 2008
But painquale, favourite his comment if any. That was a wonderful answer.
posted by Lemurrhea at 7:24 AM on December 23, 2008
Oh, barf. Sorry, painquale, I totally screwed that up, trying to do too many things at once. Here's another try.
posted by gleuschk at 7:34 AM on December 23, 2008
{1,2,3,4} -----F-----> {1,2,3,4}
| |
\phi \psi
| |
V V
{A,B,C,D} -----G-----> {A,B,C,D}Now, if I start with 2 at the top left, I go east getting 4 and south getting D; or I go south getting D and then east getting D.posted by gleuschk at 7:34 AM on December 23, 2008
Response by poster: Yeah, I could tell what you were trying to do the first time!
That was very interesting, thanks. I was hoping there was a nice terse little word to describe the relation. Oh well. Commutative diagrams seem pretty interesting. I'm gonna try to read up on them a bit.
posted by painquale at 7:49 AM on December 23, 2008
That was very interesting, thanks. I was hoping there was a nice terse little word to describe the relation. Oh well. Commutative diagrams seem pretty interesting. I'm gonna try to read up on them a bit.
posted by painquale at 7:49 AM on December 23, 2008
I should point out that there can be commutative diagrams like the square above without F and G being "structurally the same." The fact that the downward arrows are both bijections is a critical part of that sameness. If they're not bijections, you only know that F and G are related in some weaker way.
posted by gleuschk at 7:57 AM on December 23, 2008
posted by gleuschk at 7:57 AM on December 23, 2008
Isn't it a type of isomorphism? I'm a bit rusty on this, though!
posted by handee at 8:13 AM on December 23, 2008
posted by handee at 8:13 AM on December 23, 2008
Yes, you could say that the functions are isomorphic (in the category of functions). Here's how this works:
Consider gleuschk's function \phi:{1,2,3,4}-->{A,B,C,D} and \psi:{1,2,3,4}-->{A,B,C,D}. Both of these functions are invertible, which means we have functions \phi':{A,B,C,D}-->{1,2,3,4} and \psi':{A,B,C,D}-->{1,2,3,4} so that if you compose \phi and \phi' you get the identity function on either {A,B,C,D} or {1,2,3,4} (depending on which function you do first). Similarly the compositions of \psi and \psi' give the identity function. The existence of these functions just means that the sets {A,B,C,D} and {1,2,3,4} are in bijection.
Now, we can extend gleuschk's commuatative diagram like so:
{1,2,3,4} -----F-----> {1,2,3,4}
| |
\phi \psi
| |
V V
{A,B,C,D} -----G-----> {A,B,C,D}
| |
\phi' \psi'
| |
V V
{1,2,3,4}-----F-------->{A,B,C,D}
and also:
{A,B,C,D}-----G----->{A,B,C,D}
| |
\phi' \psi'
| |
V V
{1,2,3,4} -----F-----> {1,2,3,4}
| |
\phi \psi
| |
V V
{A,B,C,D} -----G-----> {A,B,C,D}
Note that if we compose the vertical arrows in either diagram, we get the identity. Now, painquale's question is asking about how to describe the "structure" of the functions F and G, so we have to think about functions as mathematical objects in their own right, not just as ways of relating sets. Thinking about functions this way, the relations between them should be commutative squares (like the one gleuschk drew). In fact, we can think of his commutative square as a "map" between the two functions F and G. That is, \phi and \psi together determine a map from F to G. Similarly, \phi' and \psi' determine a map from G to F. Composing these maps gives us the two commutative diagrams I've drawn above, depending on which order you compose.
Since we've said that composing the vertical arrows gives us the identity maps on {1,2,3,4} and {A,B,C,D}, we can see that no matter which way we trace through the first diagram I've drawn, we end up doing the function F. And no matter which way we trace through the second diagram, we do the function G. In fact, thinking of our commutative squares as maps from F to G or G to F, we'd say that composing the map \phi,\psi with \phi',\psi' gives us the identity on F. And composing \phi',\psi' with \phi,\psi (in the other order) gives us the identity on G. This means that F and G are isomorphic as maps.
To be really abstract, an "isomorphism" of mathematical things means I have two maps of things whose composite in either order gives the identity. For example, our bijection of sets given by \phi,\phi' is in fact an isomorphism of sets. And for the functions F and G, the maps \phi,\psi and \phi',\psi, give an isomorphism between them. This is all rather abstract, but I think it captures the whole of the structural similarity that painquale is asking about. If you find this sort of abstraction interesting, read up on category theory. This is what it's all about.
On preview: I can't draw commutative diagrams! If someone could fix them, I'd appreciate it!
posted by matematichica at 8:47 AM on December 23, 2008
Consider gleuschk's function \phi:{1,2,3,4}-->{A,B,C,D} and \psi:{1,2,3,4}-->{A,B,C,D}. Both of these functions are invertible, which means we have functions \phi':{A,B,C,D}-->{1,2,3,4} and \psi':{A,B,C,D}-->{1,2,3,4} so that if you compose \phi and \phi' you get the identity function on either {A,B,C,D} or {1,2,3,4} (depending on which function you do first). Similarly the compositions of \psi and \psi' give the identity function. The existence of these functions just means that the sets {A,B,C,D} and {1,2,3,4} are in bijection.
Now, we can extend gleuschk's commuatative diagram like so:
{1,2,3,4} -----F-----> {1,2,3,4}
| |
\phi \psi
| |
V V
{A,B,C,D} -----G-----> {A,B,C,D}
| |
\phi' \psi'
| |
V V
{1,2,3,4}-----F-------->{A,B,C,D}
and also:
{A,B,C,D}-----G----->{A,B,C,D}
| |
\phi' \psi'
| |
V V
{1,2,3,4} -----F-----> {1,2,3,4}
| |
\phi \psi
| |
V V
{A,B,C,D} -----G-----> {A,B,C,D}
Note that if we compose the vertical arrows in either diagram, we get the identity. Now, painquale's question is asking about how to describe the "structure" of the functions F and G, so we have to think about functions as mathematical objects in their own right, not just as ways of relating sets. Thinking about functions this way, the relations between them should be commutative squares (like the one gleuschk drew). In fact, we can think of his commutative square as a "map" between the two functions F and G. That is, \phi and \psi together determine a map from F to G. Similarly, \phi' and \psi' determine a map from G to F. Composing these maps gives us the two commutative diagrams I've drawn above, depending on which order you compose.
Since we've said that composing the vertical arrows gives us the identity maps on {1,2,3,4} and {A,B,C,D}, we can see that no matter which way we trace through the first diagram I've drawn, we end up doing the function F. And no matter which way we trace through the second diagram, we do the function G. In fact, thinking of our commutative squares as maps from F to G or G to F, we'd say that composing the map \phi,\psi with \phi',\psi' gives us the identity on F. And composing \phi',\psi' with \phi,\psi (in the other order) gives us the identity on G. This means that F and G are isomorphic as maps.
To be really abstract, an "isomorphism" of mathematical things means I have two maps of things whose composite in either order gives the identity. For example, our bijection of sets given by \phi,\phi' is in fact an isomorphism of sets. And for the functions F and G, the maps \phi,\psi and \phi',\psi, give an isomorphism between them. This is all rather abstract, but I think it captures the whole of the structural similarity that painquale is asking about. If you find this sort of abstraction interesting, read up on category theory. This is what it's all about.
On preview: I can't draw commutative diagrams! If someone could fix them, I'd appreciate it!
posted by matematichica at 8:47 AM on December 23, 2008
If you want a little terse phrase, I'd go with "when seen as graphs, F and G are graph-isomorphic". I guess "graph-isomorphic" would do in a hurry too. If you prefer formulas (though notation and exact definitions might vary), Gr(F) (isomorphism symbol) Gf(G). The iso symbol is an equals with a ~ on top.
(Some explanations: a function is a relation, and a relation is a directed graph. Graph isomorphism is equivalent to the commutation of compositions mentioned so nicely above by other posters, including the bijectivity conditions.)
posted by Iosephus at 10:35 AM on December 23, 2008
(Some explanations: a function is a relation, and a relation is a directed graph. Graph isomorphism is equivalent to the commutation of compositions mentioned so nicely above by other posters, including the bijectivity conditions.)
posted by Iosephus at 10:35 AM on December 23, 2008
Meh. Gr(F) (iso symb) Gr(G).
You'd think that working with algebra for a living I would have learnt to avoid the typos already, heh.
posted by Iosephus at 10:37 AM on December 23, 2008
You'd think that working with algebra for a living I would have learnt to avoid the typos already, heh.
posted by Iosephus at 10:37 AM on December 23, 2008
This thread is closed to new comments.
The function \phi above could be defined by sending 1 -> A, 2 -> B, 3 -> C, and 4 -> D. (There are lots of other ways to define a bijection between the two sets, but let's use this one. There's also a bijection between the ranges: \psi: {3,4} --> {C,D} defined by sending 3 to C and 4 to D. We could also define \psi on the whole codomains {1,2,3,4} and {A,B,C,D} by 1 -> A and 2 -> B. Let's do that, for esthetics.
Now here's the way to say that F and G are "structurally the same". There is a commutative diagram:
{1,2,3,4} -----F-----> {A,B,C,D} | | \phi \psi | | V V {1,2,3,4} -----G-----> {A,B,C,D}meaning that, starting at the top left, either way you go around the square gets you the same thing. For example, starting with the 2 in the top left, I can go rightwards under F (getting 4), then downward under \psi (getting D), or down first (getting 4) and then rightwards (getting D). And so on for the other three elements.posted by gleuschk at 7:03 AM on December 23, 2008