[MUSIC] Now, let's see what happens if we apply the two derivation operators, one after the other. Depending on which operator we start with, we obtain two double prime operators. One maps object subsets to object subsets, and the other does the same with attribute subsets. Let's prove some statements about the first one. Of course, similar statements can be proved about the second one. First, the double prime operator is monotonic. If A is a subset of C, A'' is going to be a subset of C''. Why? Let A be a subset of C and take any object g from A''. We want to show that g belongs to C''. Then, since this holds for an arbitrary object from A'', we'll conclude that A'' is a subset of C''. By definition of the derivation operator, g has all elements from A'. But A' is the set of all attributes shared by all objects from A. So this is the same as saying that if an attribute is shared by all objects from A, then g has it. Since A is a subset of C, every attribute M shared from all objects from C is shared by all objects from A. And therefore, g has every such M. In other words, g has all attributes from C', and thus belongs to C'', which is what we wanted to prove. The second property is extensivity. An application of double-prime to set A only adds attributes to A. So A is always a subset of A''. Well, let's take an arbitrary object g from A, and show that it belongs to A''. A' must be a subset of g' because A' is the set of attributes shared by all objects from A, and g is among these objects. So these shared attributes are among the attributes of g. This also follows from the first property of the derivation operators, we've proved earlier. A' being a subset of g' is the same as g having all attributes from A'. And this is the same as g being a member of A''. Which completes the proof. The double prime operator is also idempotent. It immediately takes the set to a fix point, so that no further application of the operator can change anything. Applying double prime to A'' gives A'' as the result. A'' is a subset of A'''' by extensivity, which we've just proved. So it remains to prove that A'''' is a subset A'', then the two sets are equal. Let's take some object g from A''''. It has all attributes from A'''. But then, it has all attributes from A', because A' is a subset of A'''. Which is the same as A'''. We know this since the second double prime operator, the one that maps attribute subsets to attribute subsets is extensive by similar reasoning that we use to prove the extensivity of the first double prime operator. And then g is in A'', which proves the property. Every operator that maps subsets of some universal set S to subsets of S and has these three properties is called a closure operator. So we have two closure operators here. One, acts on object subsets, and the other on attribute subsets. We say that a set A is closed if A = A''. This terminology is used for both object and attribute subsets. Let's look at some closure operators not related to formal contexts. Let's fix some set S, and look at the set of all pairs of its elements. Any subset of such pairs is a binary relation on S. We can define a closure operator ϕ, mapping binary relations to binary relations as follows. If R is a binary relation, let ϕ(R) be the smallest transitive relation containing R, which always exists and is unique. So, if R contains pairs X, Y, and Y, Z, ϕ(R) must contain a pair X, Z. This is necessary for it to be transitive. Here is an example. We have three pairs in R, but we have to add the fourth one (3,2) to make the relation transitive, because R contains pairs (3,4) and (4,2). So why ϕ is a closure operator? First of all, it is monotonic. Suppose that R1 is a subset of R2 and take a pair (a, b) from ϕ(R1). For monotonicity to hold, we need it to belong to ϕ(R2). Two cases are possible. If (a, b) is in R1, it is also in R2 since R1 is a subset of R2. But then it is also in ϕ(R2), because ϕ never removes any pair from the relation to which it is applied. If (a, b) is not in R1, but is in ϕ(R1), then R1 must contain a chain of pairs starting from (a, x1) for some x1, and ending with (xn, b) for some xn. Such that the second element of each pair in the chain isn't the first element of the next pair in the chain. If there is such a chain, any transitive relation containing R1 must include the pair (a, b). But if there is not such a chain, (a, b) is not necessary to enforce transitivity. So if there is such a chain, it must also belong to R2. And then for ϕ(R2) to be transitive, it must contain (a, b). The second property of closure operators, extensivity, is satisfied by ϕ because of how we define it. It only adds pairs to R, but never removes any. What about idempotency? By definition of ϕ, ϕ(ϕ(R)) is the smallest transitive relation containing ϕ(R). But ϕ(R) is already transitive. And so ϕ(ϕ(R)) is the same as ϕ(R). Another example of a closure operator, this time on trees. More precisely, it maps a set X of vertices of a tree to the smallest vertex set of a subtree containing X. For example, if X is the set consisting of the two blue nodes, ϕ(X) must also include two additional light blue nodes. Try to prove that this operator is correctly defined. That is, for every X, there is always a unique, smallest subtree containing X. And then prove that it is indeed a closure operator. [MUSIC]