A simple example: Let A = {a, b} and let B = {1, 2}, then A × B = {(a, 1), (a, 2), (b, 1), (b, 2)}.
From two sets, S and T, we can construct two Cartesian Products - S × T and T × S. These are distinct, but obviously related, sets.
Problem 20: Show that there exists a one-to-one correspondence (a mapping that is both one-to-one and onto) between S × T and T × S.
Before I go, I just wanted to throw out an example involving the Cartesian Product and mappings that relates to a discussion about operators in the comments of an earlier post.
If we let Z be the set of integers, then we can define a mapping, a: Z × Z → Z, such that a(x, y) = x + y. So each ordered pair of integers is mapped to their sum. In this way, things that are normally considered binary operations, like addition, can be seen as mappings.
Alex, I think something about being in Mulberry, AR makes thinking about math much more difficult. I wonder why?
ReplyDeleteI'm sorry, Alex. It was hard to think earlier because Barry was walking around without his shirt on and then Justin and I had some nostalgic adventures in Dover and Ozark for old times sake (I'm using "adventures" super loosely here) and then we don't have the internet out at the farm, and then I also got confused about the problem itself. But like John Edwards, I am persevering. I'm including all the confused mumblings I did to myself at the beginning as well because I'm still not 100% clear on these issues.
ReplyDeleteProblem 20:
I'm just supposed to show that this one-to-one correspondence exists without defining exactly what it is? So you're just asking me to prove that such a thing is possible, or are you asking something else? I'm a little confused. Also, I'm not sure whether you're talking about a mapping between those two Cartesian Products that would send an ordered pair (s, t) in S x T to its inverse (t, s) in T x S.....or a mapping that would send an ordered pair (s, t) in S x T to some other ordered pair (y, x) in T x S. (Probably using the word "inverse" wrong above, but you get the picture.)
Oh. Or maybe the point is that there does exist a mapping that would send (s, t) to (t, s) because I can define a mapping as such, and I should prove that THIS mapping in particular is a one-to-one correspondence. I'll just try to bumble through this.
Imagine a mapping that sends sends (s, t) in S x T to (t, s) in T x S where s is in S and t is in T. In other words (to use my almost certainly incorrect vocabulary earlier), the ordered pair is inverted. To show the mapping is onto, we must show that for every (t, s) there exists a corresponding (s, t). To show it is one-to-one, we must show that every (s, t) is matched to (t, s) and no other element in T x S.
Onto: since s is in S and t is in T, then if (t, s) exists in T x S then (s, t) also exists in S x T by the definition of a Cartesian Product. So every element in T x S, there exists a corresponding element in S x T and the mapping is onto.
One-to-one: imagine the mapping is not one-to-one. Then there is an element (s, t) that maps to both (t, s) and another element (y, x) where y is in T and x is in S. If this is the case, then s=x and t=y by the definition of the mapping...but this means that (t, s) = (x, y) by the definition you gave originally. Thus, given this mapping, there can't be two distinct elements in T x S that are mapped to by (s, t), and the mapping is one-to-one.
Is he up there because he just couldn't manage a "one-to-one correspondence" in his personal life?
ReplyDeleteOk, I have good news and bad news.
ReplyDeleteThe good news is that overall, you figured out exactly what I was asking. "Showing" that there is a one-to-one correspondence between two sets involves no more than coming up with a mapping between them and then demonstrating that is one-to-one and onto. I'm glad that you were able to clear through the brush on this part. Whether or not two sets have a one-to-one correspondence between them is pretty important when it comes to describing the different "levels" of infinity. If two sets are finite, then they would need to have the same number of elements as each other (their size or orders or cardinalities must be equal) for there to exist a one-to-one correspondence between them. I think that you can verify that this is true, and this may actually be a problem that I already have coming up - I don't remember right now. When sets are infinite in size, then usually we use one-to-one correspondences as a proxy for their orders. So two infinite sets might have no mappings between them that are onto and one-to-one, and we use this fact to indicate that one of the sets must be larger than the other even though both are infinite. We definitely have problems about this coming up, and they are very exciting.
But back to the problem. You also identified the right mapping that demonstrates that there exists a one-to-one correspondence between the two sets. "Inverting" (s, t) to (t, s) (by the way, inverting is a perfectly valid thing to say here so long as we all know what you mean and we do) is the the natural choice to answer this problem, and you're definitely right about why it is onto.
The bad news is that instead of showing why it is one-to-one, you have shown me that it is well-defined - that an element in the domain maps to only one element in the range. You should have shown that no two elements in the domain map to the same element in the range. I think that you just made a mistake because of all of the shirtless partying going on in Arkansas these days, but please let me know if there is some deeper misunderstanding about this point.
John Edwards had his difficulties with regard to one-to-oneness, that's for sure. I mean, whoa!
I'm back. And I've spent awhile looking over the last few posts to try to reacquaint myself with everything. So in regards to this problem, is this the right way to show that the mapping is one-to-one?
ReplyDeleteImagine the mapping is not one-to-one. Then there is some element (t, s) in T x S that is mapped to by two (or more) elements in S x T. Let (s, t) and (x, y) be those two elements. Then s=x and t=y by the definition of the mapping...but that means (x, y) = (s, t). So, there are not two distinct elements in S x T that map to the same element in T x S.
Yes, exactly. In fact, this is more or less the standard way that we always show that something is one-to-one - by assuming that two elements map to the same element and then showing that this implies that these two elements must be equal. So, in shorthand, you show that f(x) = f(y) implies that x = y. There are times when going about it in a different way is better, but usually this is what you'll try first. At least in my book.
ReplyDeleteSo this is kinda a proof by contradiction, right? If you start out by assuming that there are two distinct elements that are mapped to the same thing and then showing that they cannot be distinct. Thus, this is a contradiction, and it must be one-to-one.
By the way, would you like me to do a post on the different types of standard proofs like direct proof, proof by contradiction, contraposition, and induction? This was something that I thought to do at the beginning, but decided against since categorizing types of proofs was always something that limited my thinking about things in college. But I see now that addressing them head on, rather than letting them seep in over time might have been better.
I think that would be helpful, yeah. Proof by contradiction is really the only one that's fully clear to me, so it's what I always tend towards. (I think induction is awfully neat too, especially if it's called "the method of infinite descent" as I recall someone (Fermat?) calling it, but I only grasp the logic if I spend a good while thinking about it. I'm never sure whether that constitutes "getting it" or not, but I have a laundry list of math topics that are like that.)
ReplyDeleteOk, I will work on one. It might be a little bit though, and I'm not sure that it'll have any problems to go with it.
ReplyDelete