[MUSIC] [SOUND] Hello everybody, welcome to our third session. Last time, we introduce basic mathematical concepts especially relations. Today I want to talk about special type of relation that's called ordering. You have seen orderings before, for example, on the natural numbers, you've seen the ordering less or equal. Or on the integers, you have seen the ordering of divisibility. So these are order ranks and they play an important role in this discrete mathematics, but they don't only exist in actual numbers and integers. Let me actually give you a completely arbitrary example of an ordering. We want to compare apples and oranges, although people tell us that you cannot do this. So these two fruits, there are actually a lot of things we could compare. We could compare the taste, the price, the vitamin A content, the vitamin B content, vitamin C content and so on. So there's a lot of parameters we can compare, for today let's actually focus on two parameters. The first is the vitamin C content, the other is the iron content. So here, we see this is the vitamin C and the iron content of apples and oranges. And to spice things up, let's add some other food items. So how can we represent this data nicely? Well, let's make a two dimensional chart, and let's put our food items into this chart. So now I want to define an ordering, I want to say a is less or equal than b if. It contains at most, as much vitamin C as b does. And at most as much iron as b does. Okay so that's my ordering, let's see how it looks like here. So for example clearly the apple is smaller than the broccoli, it's smaller than the kiwi. The orange is also smaller than the broccoli and both are smaller than the chili, the apple's also smaller than the spinach. But apples and oranges are incomparable, because the orange is rich in vitamin C, but the apple is a little bit richer in iron. So they are actually incomparable in this ordering. And the, well I mean to make it complete you would also have to insert an arc from the orange and from the apple to the chili and from the orange to the chili. Because also the orange is smaller than the chili in this ordering, okay, this is an example of an ordering. Now it deserves a formal mathematical definition, okay? Are you ready for it? Let's go, so you have a set, you have a relation on it. So for example we could depict the relation by use of arrows. Just this means a b is in the relation and so on. And the relation can have certain properties, so for example, we say R is reflexes. If (x,x) is in the relation, for all x, so here basically means we have this little self loops around each vertex. Second, we say R is transitive. If, Let's say you have (x,y), and (y,z) appears in your relation. Then you always have (x,z) in the relation, so let's draw a picture. If you have x arrow y, and y arrow z, then this implies, x arrow z. This is transitive. In R is anti-symmetric, If, well this is a little bit counterintuitive, if x cannot be smaller than y and simultaneously y smaller than x. Unless, They are the same, so basically, it means you don't have such a thing. Okay, so now it works. Okay, great, so something like this doesn't happen, this means anti-symmetric. So let's quickly summarize it, a relation that is reflexive, transitive and anti-symmetric, that's called an ordering. So now you can go back and check that these three properties actually hold for the lesser equal relation on that for numbers. For the divisibility ordering on integers and for our vitamin C and iron ordering on fruit. Some relations have the following bonus property. So, for example, consider the metro numbers together with a less or equal. You always have a less or equal b or b less or equal a. On to the divisibility, well, divisibility we should actually write integers, not natural numbers. It could be that a does not divide b and b does not divide a, so this is possible. So it seems here that the less or equal relation has a bonus property. It means if you have two elements, you can always compare them. But the divisibility ordering doesn't have this, for example, 3 doesn't divide 7 and 7 doesn't divide 3. So this bonus property is called linear, it's called a linear ordering sometimes also a total ordering. Just keep in mind, some orderings have this property, some don't, okay. If it doesn't, then we call it a partial ordering, all right. So here is a summary, reflective, transitive, anti-symmetric, that's an ordering. If in addition it's linear, it's a linear ordering. Cool. So let's look again at our ordering on food items. Let's look at this arc, from the apple to the chili, it's actually redundant, because even without the arc we would know that the chili is larger than the apple, by transitivity, right? It can just go from the apple to the broccoli and then up. So this arc is actually redundant, we can remove it, the same with this arc. And now we're left with number redundant arcs, and this has a name, this is called the Hasse diagram of an ordering. Again, this deserves a formal definition, recall x an immediate predecessor of y if x is smaller than y. And there is nothing in between, so you cannot find anything that is strictly between x and y. So, for example, the kiwi and the chili are immediate predecessors, but the apple is not an immediate predecessor of the chili because the kiwi is in between. The broccoli is in between too, okay, so, now if for every immediate predecessor, you include an arrow xy, then what you get is the Hasse diagram. And there is actually acute lemma, if you have an ordering, in essence, a finite set, then the Hasse diagram uniquely defines your ordering. So if I show you the Hasse diagram, you can reconstruct the ordering. Now this condition, S to be finite, is actually crucial. For infinite sets, this lemma might be false, for example, consider the set ( [0,1] ) the real interval. Together with a smaller equal relation, so what is the Hasse diagram of this ordering? Think about it, okay, we need some further important definitions concerning ordering. The first of all if x is lesser equal than y or vice versa then they are comparable. Otherwise they are incomparable. And if you have an ordered set and you have a subset. And everything in C is mutually comparable, a and b are comparable. For all a, b, and C, then we call C a chain. It's a subset that is linearly ordered. And if you have the opposite, if any elements, all elements are pair wise incomparable. Then A is called an antichain. But it's a subset where nothing is comparable, all right, this is chains and anti chains. Now an element is maximal. If nothing is larger, if there exists no y in S that is larger. And is called minimal if there exist nothing that is smaller. In general this is different from the following definition, x is a maximum, It's a maximum if it is bigger than everything else. And it's called a minimum, it's called minimum, if x is smaller than everything else. So just be aware that these two definitions are not the same in general. If your order is not linear, these might not be the same. Here is a summary where everything is nice and written. And there, here is an exercise for you, you should find the largest chain, largest antichain. Maximum, minimum elements and minimal and maximal elements in our food item ordering. One last thing then we're done for today, here we have an ordering S and this. And I'll suppose I'm only interested in this subset x. Then my ordering induces a sub order, right? I just take the ordering, I restrict it to x, and I get a new ordered set. So every set, every subset of S also inherits the ordering, this is called induced, Suborder. All right, that's it for today. Here are some nice exercises, those without star are quite simple. You should be able to solve them if you have understood the material of today. Those with two stars actually requires some non-trivial truth. So here is the first set, and here are some more exercises. All right, thank you for today. See you next time. [MUSIC]
