[SOUND] In this video, we are going to define one particular kind of implication bases, the canonical basis. But to define it, we'll need another notion, a new notion, a notion of a pseudo-closed set. Well, a pseudo-closed set is a set that is not closed, but, in some ways, it behaves like a closed set. It has some properties which make it similar to a closed set. In particular, every closed set contains the closure of every its proper subset. This is not precisely true about pseudo-closed sets. But something similar holds. A pseudo-closed set must contain the closure of every its pseudo-closed proper subset. And actually this is the definition of a pseudo-closed set. So let's say we have a closure operator that maps X to X''. It's defined on a finite set M. In this case, we say that an attribute subset P is called pseudo-closed if it is not closed, that is, P doesn't equal P'', and also, for every pseudo-closed proper subset Q of P, we have that the closure of Q, Q'', must be a subset of P. Well, this definition looks kind of circular, because we define pseudo-closed sets using the notion of a pseudo-closed set. But this is okay. Note that here we refer to only pseudo-closed proper subsets of set P. So if P has no subsets at all, then the second part of the definition holds vacuously. Or it may happen that P has subsets, but all its subsets are closed. Then they cannot be pseudo-closed because of the first part of the definition. And then, the second part of the definition holds vacuously again. To put it another way, if all subsets of P, all proper subsets of P, are closed and P is not closed itself then it's a pseudo-closed set. And that's how we can get the minimal pseudo-closed sets. And then the definition works inductively. Okay, so we are talking about pseudo-closed sets with respect to a closure operator, but, in some cases, we'll be talking about pseudo-closed sets with respect to a formal context. In this case, we will call them pseudo-intents. So a pseudo-intent is a pseudo-closed attribute set. And similarly, we're going to say that a pseudo-extent is a pseudo-closed object set, because, remember, we have a closure operator defined not only on attributes, but we have another closure operator defined on objects. And so, both definitions, pseudo-intent and pseudo-extent, make sense. We'll need mainly the first one, at least in this lecture. So a pseudo-intent is a pseudo-closed attribute set. And now we can define the Duquenne-Guigues or the canonical basis. So this is the canonical basis of a formal context, the canonical basis of implications, and it's often called the Duquenne-Guigues basis, because Duquenne and Guigues are two people who invented it. Before defining the canonical basis, let's extend the notion of soundness and completeness to an arbitrary closure operator. We have defined it only for a formal context. And now, we're going to say that an implication set L is sound or complete with respect to a closure operator '' if it is sound or complete with respect to the following formal context. Here, the attributes are the same attributes M on which our closure operator is defined. The set of objects is just the set of all subsets of M closed with the respect to this closure operator. So the set G, the set of objects, is the set of all sets of the form A'', where A is an arbitrary subset of M; and we put a cross between a set, which is an object in our case, and an attribute m if this attribute m is part of this set. So that's how we define the formal context. And we say that L is sound and complete with respect to a closure operator if it's sound and complete, or sound or complete with respect to this formal context derived from this closure operator. Now, this is a theorem which says that, for finite M and a closure operator '', the following set of implications is sound, complete and non-redundant. Now, it contains implications of the form P → P'', where P is a pseudo-closed attribute set. And this is the theorem we're going to prove now. First of all, let's prove soundness. Well, soundness is easy. Soundness means that all these implications must, indeed, hold for our closure operator. But, yes, if we take a set P, then this set P implies P'', so this holds for any P which is a subset of M. Completeness. Well, let's assume that our set of implications L is not complete. Then, there must be at least one implication X → Y respected by every object intent of the context we defined in the previous slide, so, respected by set A''. And at the same time this implication, X → Y, doesn't follow from L. That's the meaning of incompleteness. So I have a valid implication which doesn't follow from our set L. But then if it doesn't follow from our set L, we have that Y is not a subset of L(X). And on the other hand, because X really implies Y, Y is a subset of X''. But this means that L(X) is not closed. Let's check pseudo-closed proper subsets of L(X). Let's take one such pseudo-closed subset; let's call it Q. Now, because Q is pseudo-closed, the implication Q → Q'' must be part of L by the definition of L. L includes all implications whose premise is pseudo-closed; so it must include this one, too. But then, Q'' must be a subset of L(X). Q is a subset of L(X), and we have an implication that Q implies Q''. So Q'' must be included in L(X). It follows that L(X) is pseudo-closed itself, because it is not closed and it contains the closure of all its pseudo-closed proper subsets. But then, L must contain the implication L(X) → L(X)'', because L contains all the implications with pseudo-closed premises. Okay, so this means that L(X) = L(X)'', but L(X)'' is closed, which means that L(X) is also closed, and this gives us a contradiction. So our initial assumption that L is not complete was incorrect. L is indeed complete. What remains is to show non-redundancy. So non-redundant means that, whenever you remove one of the implications, let's say P → P'', you cannot infer it, or it doesn't semantically follow from what remains in L. So let's denote what remains by L-. L- is L without this implication, P → P''. We know that P respects all implications of the form Q → Q'' in L-, because P is pseudo-closed and a pseudo-closed subset must contain the closures of all its pseudo-closed proper subsets. So if Q is a proper subset of P, then Q'' must also be part of P. And L- contains only implications of the form Q → Q'' such that Q is pseudo-closed. So P respects all of them. This means that L-(P) = P. But then, because of this, the implication P → P'' doesn't follow from L-. Otherwise, L-(P) would include P'', and it doesn't. This means that once we remove the implication P → P'' from L, we can't get it back, and therefore we can't remove any such implication from our set L, and this means that L is indeed non-redundant. Okay, so this set of implications, which is sound, complete and non-redundant, is a basis. But it's not just any basis. This is called the canonical basis, or the Duquenne-Guigues basis of the corresponding closure operator, ''. It is sometimes given in the abbreviated form, as written below. So we can say that P implies P'', or we can say that P implies P''\P. That's the same. An interesting property of this canonical basis is that it is minimal in the number of implications among all equivalent implication sets. There may be several implication bases corresponding to the same closure operator, several implication sets that are sound, complete, and non-redundant, but it's not possible to get an implication set, a basis, that has fewer implications than the canonical basis. Nevertheless, even though it's the minimal possible basis, it can still content a lot of implications. The number of implications can be exponential in the size of M, in the number of attributes, and we'll see an example later. [SOUND]