>> Hello, and welcome to the first in a series of screencasts on relations. The relation is a mathematical concept that underlies actually a lot of the technology we use today, including social networking software, like Facebook or Twitter. Let's develop the idea of a relation by looking at a very small social network. This network consists of five people, Alice, Bob, Chuck, Dave, and Ed. They're on a social network that allows one person to quote-unquote follow the posts of another. If one person follows another, then the person being followed does not have to follow the other person back. So, let's suppose that the network currently looks like this. Alice follows Bob, Chuck, and Ed. Bob follows Alice, Dave and Ed. Chuck doesn't follow anybody, he's like a celebrity. Dave follows Alice, Bob, Chuck and Ed, and finally Ed follows Dave. So, we have a tangled web of connections here, and if you think about a real person's Twitter stream or Facebook network, it gets hugely more tangled than this in real life. So you might ask; how does the software that manages this network keep track of who is connected to whom in the network. Well, one way could be to use ordered pairs. The social network in this sense would be a set of ordered pairs, and we'll put the put the f pair x, y in the set if x follows y. So, for example, this small social network could be represented as the following set of ordered pairs: Alice, Bob; Alice, Chuck; Alice, Ed; Bob, Alice; Bob, Dave; Bob, Ed; Dave, Alice; Dave, Bob; Dave, Chuck; Dave, Ed; and finally, Ed, Dave. If Bob one day decided to follow Chuck, then we just have to append the pair Bob, Chuck to the set. Or, if Bob unfollowed Dave, we would have to remove the pair Bob, Dave from the set. So, what we have here is the set of ordered pairs. If we let p be the set consisting of people in this network, that would be Alice, Bob, Chuck, Dave, and Ed, then our social network really in this representation is a subset of the Cartesian product p cross p. And in fact it consists of all the ordered pairs x, y, in p cross p such that x follows y. So, if you think this sounds like our ordered pair representation of a function that we saw in earlier screencasts then you'd be on the right track. However, notice that our social network here is definitely not a function, because there's lots of instances where a single person quote-unquote maps to several others, like Dave here who maps to four different people. But that doesn't make this make this set theoretic model of a social network a bad idea, it's just not a function. But that's okay, it's an accurate and pretty handy way of representing and keeping track of relationships between people. So, since this is a handy way of keeping track of relationships, it's no surprise that what we've described here is called a relation. Here's the formal definition, although there's really not much to it. Let's let a and b be sets, and we're going to define a relation from a to b to be just a subset of a cross b. And sometimes, like with our social network, the sets a and b are the same. In that case, we have a relation from a set to itself, which is just a subset of a cross a, we call that just a relation on a. So, in other words, a relation from a to b is just a collection of ordered pairs, where the first coordinate belongs to a, and the second coordinate belongs to b. It may not be all of a cross b, but it's just a subset of ordered pairs from a cross b. This minimalist definition here is really actually useful because relations can model all sorts of interesting and useful things due to the lack of rules that are in the definition. A couple of pieces of terminology before we look at more examples, if r is a relation from a to b, then we say that a is the domain of the relation and b is the range. There is no concept of a codomain for a relation, we only speak of domain and range. So here are a couple of other useful examples of relations besides social networks. Let's consider the relation r from the set of all words in the English language, which we're going to call w here. To the natural numbers defined by r is the set of all ordered pairs in w cross n, such that the length of the first coordinate equals the second coordinate. So, every pair in this relation is an ordered pair, where the first coordinate is a word, and the second coordinate is a natural number. What are some examples of pairs that belong to this relation? Well, one example is dog, three. Because the length of the word dog is three. Another would be cat, three; and another would be Michigan, eight. What this relation really is is like a very simple database where you could look up a word and it tells you how long the word is. And example of the pair that would not belong to this relation would be dog, two, because the length of the word dog is not equal to two. Actually what we have here is a function, not just a relation. This is not only a set of ordered pairs, it's a set of ordered pairs, such that if the first coordinate of any two pairs of the same then the second coordinates must also be the same. So, there's no quote-unquote input splitting. And every word in w is actually paired off with some natural number. So, what this example illustrates is that every function is a relation, but not every relation is a function. Here's another example of a relation. This time it's a relation from the set of real numbers to itself, so we're, it is a relation on the set of real numbers. A pair x, y of real numbers belongs to this relation, if and only if x is less-than or equal to y. So, for example 2, 5 is in the set r and so is 2, 10. And that automatically tells you that this relation is not a function, because 2 is related to two different things. Now, on the other hand, 5, 2 would not be in this relation because of course 5 is not less-than or equal to two. However, 5, 5 would be in that relation 5 is less-than or equal to 5. So, again, this relation is just a set of ordered pairs from r cross r, not the entire set of ordered pairs in r cross r, but just a subset that satisfies a certain condition. So, let's see how well you're getting the concept of relation with a concept check. Let's let w be the set of all English words that we saw earlier and define a relation r on w as follows. R is the set of all pairs of English words w 1, w 2 such that w 1 differs from w 2 by one letter or less. This would be an important relation if you were thinking about spellcheck software or language recognition. Which of the following pairs belongs to r? Select all the ones that apply and come back when you're ready. So, the answer here is all the pairs that the last one belonged to this relation, because for each of the other pairs, the words in the pairs are either equal or else they differ by only one letter. But the last pair differs by two letters, so it does not belong to the relation. So, that is the basic concept behind relations. Thanks for watching.