[MUSIC] >> In the previous video, we've defined suprema and infima for concepts. But they can be defined for an arbitrary, a partially ordered set. So let's say that we have a partially ordered set S and let a and b be elements of this partially ordered set. P.o.s. set, as it's called sometimes. The infimum of a and b Is the element c, Such that, This c is less than or equal to a, it's less than or equal to b. And for all elements d, That are smaller than a, and, simultaneously, smaller than b. We have that d is also smaller than c. Well, less than or equal to c. So c is the greatest among elements that are smaller than both a and b. And the supremum Is defined similarly. So we denote it like this. And it's an element c, such that it's Bigger or equal to than a and than b. And whenever we have another element, let's say d, which is also greater than or equal to a and b. In this case, c is less than d. It turns out that the [INAUDIBLE] concept, it's not just any partial order. It has some additional properties which allow us to call it a lattice. I'm now going to define a lattice in general, irrespective of contexts, concepts, and so on. So a lattice Is a certain algebraic structure. It's a partially ordered set In which suprema and infima exist for every two of its elements. Let me give you an example. So let's say that we have five elements in our partial ordered set. So these are the elements and they're ordered like this. So these are the greatest elements, these are smaller, but they're incomparable with each other. And these are also smaller and incomparable with each other, and these are the smallest elements. Now, is it a lattice? Well, no. Because if we take, for example, these two elements, what's their infinum? Well the infinum is an element which is more than both these elements. So it might be this one or this one or this one. But for one of them to be the infimum of these two, we need it to be greater than the others. So you see whenever we have an element d which is smaller than both a and b, and in this case this is a, and this is b. So whenever some d is smaller than a or b it must also be smaller than c, that infimum of a and b. But now we have three elements smaller than a and b, and none of them is greater then the other two. So a and b here don't have any infimum. And similarly these two elements, let's call them a1 and b1, they don't have a supremum. On the other hand, if we take A set that contains just one more element, this one. And this element is smaller than both a and b, but bigger than both a1 and b1. In this case, this is a lattice. This is a lattice because if we take these two elements the infimum is this one. It's bigger than all the other elements that are smaller than a and b. And similarly, it is also a supremum of these two elements, a1 and b1. And you can easily check that for every two elements, you can find a unique supremum and infimum. All right, so let me give you a very simple example of a lattice which is infinite. It's easy to check if you have just five or six elements whether it's a lattice or not. But how can you check if you have an infinite number of elements? Well let's look at the set of all natural numbers ordered with their usual relation less than or equal to. So, we have that 1 is less than or equal to 1 and also less than or equal to 3 and to 5 and so on. Now, this is a lattice. Well first of all it's a partially ordered set, because every number is smaller or equal to itself, so this relation is reflexive. It's also antisymmetric, because whenever you have two numbers a and b. And a is less than or equal to b and b is less than or equal to a, it just means that a and b are the same. And this relation is also transitive. If a is less than or equal to b which is less than or equal to c then a is less than or equal to c. So this is a partially ordered set but what's more, it's a lattice. And it's very easy in this case to define the infimum and the supremum. So if I have two elements x and y, then their supremum is just their maximum, the one that is bigger. On the other hand, the infimum is just their minimum. It is also possible to generalize the definitions of infimum and supremum so that they apply not to pairs of elements. But to any set of elements of our partially ordered set. If infima and suprema exist for any subset of a partially ordered set then this partially ordered set is called a complete lattice. We're going to explore complete lattices in the next video. [SOUND]