[MUSIC] But if you have two sets, you often want to talk about a certain relation that holds between the elements of this set. [INAUDIBLE] Product I am portioned, because they allow you to talk about relations that the elements of two different sets might have. For example here, we have three fruits and three people and we might want to ask who likes what. The answer could look like this. Alice only likes the kiwi, Bob likes the orange and the apple and so on. Mathematically, what this relation is, it's a subset of the Cartesian product, right?. So this subset is called a relation. Actually, because here we are only talking about two sets, it's called a binary relation. If you know the game Cluedo for example. You want to find out who killed whom with which weapon in which room. And an answer to this would be a relation, a four area relation. So for example, is A is the set of murder of potential suspects, B is the set of murder victims, C is a set of murder weapons. And D is the set of crime scenes, then R the subset of the set describes who killed whom using what at which location. Right, this would be a four area relation. Of course, in real life, in [INAUDIBLE] mathematics, we don't use the set [INAUDIBLE] notation, we often just say Alice likes kiwis, of course. And if you have a binary relation, you can easily depict it by just drawing an edge from an element to the other in which if it is in this relationship. All right, there are actually some relations we have already seen in mathematics. So for example a < b, so for example 2 < 3. You could define it as a subset of pairs of let's say natural numbers. And a is less than b if there exist an x in the natural number such that a + x equals b. You also might have seen this notation that's called a divides b and you could define it as the set of all pairrs of integers. Let's say there exist an x, an integer such as a times x equals b. So all these, you can think of as relations, subsets of Cartesian products. One of the most important concepts or functions, what is a function? Well, in Calculus I guess you have seen stuff like this. F of x is x squared or f of x is e to the x. These are functions obviously. But let's try to be a little bit more formal. So, a function has a set A where it takes as input and it outputs elements in B. You can think of it as an input, output machine. And with these two functions we can write down explicitly. But often, if we were talking about less standard functions, we have to define them in kind of a more involved way. So here is an example, if you have a set A and some fixed element little a in it, I define a function from the power set into the power set. Do the following if you give me a subset of a, I check whether it contains the element a and if it does, I remove it and if it doesn't, then I add it to it. So this is a function of two to the a, two to the a. So actually the functions we will encounter in discrete mathematics often look much more like this than something like e to the x or x squared. These are also functions. All right, actually you can think about functions as being special relations. For example, supposed there are different fruits and now all of them have been eaten. And we can ask who has eaten the kiwi and so on. And the answer would be something like this. So every item has been eaten by exactly one person. And you see again, this is a subset of the Cartesian product. It's a function, but it's a special function. What makes it special is that for every A there exists exactly one B, such as A B is in the relation. And this special relation we call a function. A function can have certain properties that are important, so I want to quickly introduce them. Injective means if you have A to B, so suppose you have a function A, f from A to B. Injective means the two elements can never collide. So if you have two different inputs, they must give a different output. Surjective means that you reach every element in B. So formally, for every B there exists an A, such as f of a equals b. And bijective just means injective plus surjective. And these concepts are important for the following reasons. If A and B are finite sets, and you have an injective function from A to B, it should be pretty clear that A cannot be larger than B. If it's surjective, if you read every element in B, it's clear that A must be at least as large as B. And finally, if they are bijective it means that they have the same size. Even some people take the existence of a bijection as a definition of what it means to have the same size. All right, so here let's go back to our example which is a function of 2 to the A times 2 to the A, it is actually a bijection. You should invest some minutes to figure this out. So a bijection from a set to itself. Now I use the set builder notation to build the set E and the set O. E is the set of even subsets of A and O is the set of odd subsets of A. And actually now you see that F, if you fitted an element of E and outputs an element of O. So you can think of f O as a function from E to O. And it's also kind of easy to see that it's bijective. And therefore, E equals O. So there are as many odd subsets as there are even subsets, right? And we prove it by giving a bijection. So we have proved something that is maybe not completely obvious. The last thing for today, I want to show you some beautiful results from set theory. And this is not of course, about set theory but I think this is remarkable and it's also easy, so I should talk about it a little bit. The surprising fact is N times N has the same size as N. So recall, if you have two finite sets, that A times B is A times B which means say for example A times A is A squared. Which is larger than A if A has at least two elements. But now N has infinitely many elements. In theory there is a paradoxical surprising fact, actually N times N has the same size as N and here's the proof. Actually what does it mean to have the same size? Well, I will show you that there is a bijection between these two sets. So here of the natural numbers and here other natural numbers, so their Cartesian product looks like these, like this infinite grid. And I will show you a bijective function from N times N into N by this. One, two, three. So next to each element of N square, I write to which number in N I want to map it. So I go like this. And you see no number appears twice. And I will reach all numbers. So this a bijective function. And therefore in this sense, they actually do have the same size, although this set appears to be much bigger than this. All right, that's actually as far as we go into set theory. Now in real stage is strictly within discrete math. All right, that's it for today. Thanks. [MUSIC]
