We study the connection between certain many-valued contexts and general geometric structures. The known one-to-one correspondence between attribute-complete many-valued contexts and complete affine ordered sets is used to extend the investigation to π-lattices and class geometries. The former are identified as a subclass of complete affine ordered sets, which exhibit a close relation to concept lattices which are closely tied to the corresponding context. The latter can be related to complete affine ordered sets using residuated mappings and the notion of a weak parallelism.
Introduction
context in order-theoretic and geometric terms. In [
• π-lattices and • equivalence class geometries (or short class geometries).
and modules, yielding the possibility to study geometry in a very general setup.
ordered sets, which opens up an intimate connection to the concept lattices
arising from plain conceptual scaling of the corresponding context.
Class geometries are a generalization of congruence class geometries. They carry
a certain type of parallelism – called weak parallelism– arising naturally in the
context of coordinatizing geometric closure structures via the congruence classes
of an algebra (in the sense of universal algebra), cf. [
sets and π-lattices. In a third step, we will show how a weak parallelism on an atomic lattice can induce a weak parallelism on another atomic lattice via an adjunction. The results will be applied in the concluding step to describe a connection between complete affine ordered sets and class geometries. Finally, we will give a summary of what we achieved.
2
Attribute-complete Many-valued Contexts and Complete Affine Ordered Sets
A many-valued context K := (G, M, W, I) is called attribute-complete if it • is complete, that is, every m ∈ M can be regarded as a map m : G → W , • has a key attribute, that is, there exists an attribute m ∈ M with ker(m) = ΔG := {(g, g) | g ∈ G}, • is simple, that is, different attributes m1, m2 ∈ M are not functionally equivalent, that is, ker(m1) = ker(m2) implies m1 = m2, and • for all N ⊆ M there exists an attribute m ∈ M such that m and N are functionally equivalent, that is, ker(m) = Tn∈N ker(n).
set (P, ≤) is given by (P ] {⊥}, ≤ ] ({⊥} × P ] {⊥})) and denoted as (P, ≤)⊥.
Definition 1 ((atomistic, complete) affine ordered set). We call a triple
A := (Q, ≤, k) affine ordered set, if (Q, ≤) is a partially ordered set, k is an equivalence relation (called parallelism) on Q, and the axioms (A1) - (A4) hold. Let A(Q) := Min(Q, ≤) denote the set of all minimal elements in (Q, ≤) and A(x) := {a ∈ A(Q) | a ≤ x}. (A1) ∀x ∈ Q : A(x) 6= ∅ (A2) ∀x ∈ Q ∀a ∈ A(Q) ∃!t ∈ Q : a ≤ t k x (A3) ∀x, y, x0, y0 ∈ Q : x0 k x ≤ y k y0 & A(x0) ∩ A(y0) 6= ∅ ⇒ x0 ≤ y0 (A4) ∀x, y ∈ Q ∃x0, y0 ∈ Q : x y & A(x) ⊆ A(y)
⇒ x0 k x & y0 k y & A(x0) ∩ A(y0) 6= ∅ & A(x0) * A(y0).
The elements of A(Q) are called points and, in general, elements of Q are called subspaces. We say that a subspace x is contained in a subspace y if x ≤ y. If the lifting of (Q, ≤) forms a complete lattice L(A), the affine ordered set A is called complete affine ordered set. We call a complete affine ordered set A atomistic if the corresponding complete lattice L(A) is atomistic.
tains a and is parallel to x. Axiom (A2) guarantees that there is exactly one such subspace. For every x ∈ Q we observe that θ(x) := {(a, b) ∈ A(Q)2 | π(a|x) = π(b|x)} is an equivalence relation on the set of points.
(A34) ∀x, y ∈ Q : x ≤ y ⇐⇒ A(x) ⊆ A(y) & θ(x) ⊆ θ(y)
• attribute-complete many-valued contexts, • closed SERs, and • complete affine ordered sets with their respective morphisms form categories which are equivalent.
each other. To an attribute-complete many-valued context K := (G, M, W, I) we can assign a closed system of equivalence relations via
E(K) := (G, {ker(m) | m ∈ M }).
To a closed system of equivalence relations E := (G, E) we can assign a complete affine ordered set – the ordered set of its labeled equivalence classes – via
A(E) := ({([x]θ, θ) | θ ∈ E}, ≤, k) where ≤ is defined by and k is defined by ([x]θ1, θ1) ≤ ([y]θ2, θ2) : ⇐⇒ [x]θ1 ⊆ [y]θ2 & θ1 ⊆ θ2
([x]θ1, θ1) k ([y]θ2, θ2) : ⇐⇒ θ1 = θ2. 3
π-Lattices and Complete Affine Ordered Sets
L+ := L \ ^ L.
if it satisfies the following axioms Definition 2 (π-lattice). Let V be a complete atomistic lattice with set of atoms A(V ). Then an equivalence relation k ⊆ V+ × V+ is called parallelism (E) ∀p ∈ A(V ) ∀x ∈ V+∃!y ∈ V+ : p ≤ y k x (M) ∀p ∈ A(V ) ∀x, y ∈ V+ : x ≤ y =⇒ π(p|x) ≤ π(p|y).
We call an atomistic complete lattice with parallelism π-lattice.
π-lattices. ordered set.
Proposition 1. Let V be a π-lattice. Then (V+, ≤V , k) forms a complete affine
that (A1) - (A4) hold for (V \ {0}, ≤V , k). Since V is atomistic (A1) holds. (E) directly implies (A2). For showing (A34), let x ≤ y for x, y ∈ V+. Obviously
x = _ A(x) ≤ _ A(y) = y because V is atomistic. By construction (V+)⊥ = V is a complete lattice. tu
allelism from the definition of π-lattices without problems. hold in L(A).
Proposition 2. Let A := (Q, ≤, k) be an affine ordered set. Then (E) and (M)
A(π(p | x)) = [p]θ(x) ⊆ [p]θ(y) = A(π(p | y)) and therefore by applying the equivalence in (A34) from right to left we get
π(p | x) ≤ π(p | y) which shows (M). of complete affine ordered sets: Theorem 1. The atomistic complete affine ordered sets are in one-to-one correspondence with π-lattices. More precisely, moving between the two structures requires only attaching or respectively removing the bottom element while the parallelism can be reused. tu
atomistic. We call a system of equivalence relations E := (D, E) regular if its set of equivalence relations E is regular, that is, if there do not exist two different equivalence relations sharing an equivalence class.
Proposition 3. Let A be a complete affine ordered set and let E be a closed system of equivalence relations with
A ∼= A(E) & E(A) ∼= E.
Then A is atomistic if and only if E is regular.
Proof. “⇒”: Let E := (D, E) be a regular closed system of equivalence relations and let A(E) be the associated complete affine ordered set. Then we have to show for a subspace x from A(E) that x = W A(x). But since the subspaces of A(E) are the labeled equivalence classes of E we know that x = (X, θ) for an equivalence class X of an equivalence relation θ ∈ E. Then we have _ A(x) = _({p}, Δ) | p ∈ X} = (X, θ(X)).
But θ(X) = θ since E is regular. Therefore, W A(x) = (X, θ(X)) = (X, θ) and hence A(E) is atomistic. that θ(x) = θ(y). Since A is atomistic we have “⇐”: Let A := (Q, ≤, k) be an atomistic complete affine ordered set and let E(A) be the associated closed system of equivalence relations. We have to show that E(A) is regular, that is, for a point p ∈ A(Q) where [p]θ(x) = [p]θ(y) it follows x = _[p]θ(x) = _[p]θ(y) = y.
Definition 3 (derived context via nominal scaling). Let K := (G, M, W, I) be a complete many-valued context. Then the formal context Knom := (G, N, J ) is called derived context via nominal scaling of K if tu N := {(m, w) ∈ M × W | ∃g ∈ G : m(g) = w} and
J := {(g, (m, w)) ∈ G × N | (g, m, w) ∈ I}.
is Proposition 4. Let K := (G, M, W, I) be a simple many-valued context with key attribute, let A := A(K) be the associated affine ordered set and let Knom be the derived context of K via plain nominal scaling. Let ϕ : A → B(Knom) be a mapping where (C, θ) 7→ (C, CJ ). Then ϕ is an order-preserving mapping which • surjective if and only if A is complete and • injective if and only if A is atomistic. know that there exists a h ∈ G and a m ∈ M such that Proof. To see that (C, CJ ) ∈ B(Knom) we have to show that C = CJJ , that is that C is an extent of a formal concept of the concept lattice of Knom. It is obvious that C ⊆ CJJ since ·JJ is a closure operator. By construction of A we
C = [h]ker(m) = {g ∈ G | m(g) = m(h)} = {g ∈ G | (g, (m, m(h))) ∈ J }. order-preserving.
shows that if g ∈ CJJ then g ∈ C. Therefore C = CJJ . It is obvious that ϕ is “⇒”: Let A be complete. We show that ϕ is surjective. Since the extents of
of equivalence classes induced by K is already meet-closed it is immediate that ϕ is surjective.
Let A be atomistic. We show that ϕ is injective. Let ϕ(C1, θ1) = ϕ(C2, θ2). Then (C1, C1J ) = (C2, C2J ) which implies C1 = C2. But since we know by Proposition 3 that E(A) is regular we have θ1 = θ2. “⇐”: Let ϕ be surjective. Then every extent of B(Knom) is an image of ϕ. But since the extents of B(Knom) are exactly the meets of equivalence classes induced by K, we know that the set of equivalence classes is meet-closed and therefore
Let ϕ be injective. Then whenever (C1, C1J ) = ϕ(C1, θ1) = ϕ(C2, θ2) = (C2, C2J ) which is equivalent to C1 = C2 we have θ1 = θ2. That means, E(A) is regular.
Corollary 1. Let K := (G, M, W, I) be an attribute-complete many-valued context, let A := A(K) be the associated complete affine ordered set and let Knom be the derived context of K via plain nominal scaling. Then
B(Knom) =∼ L(A) if and only if A is atomistic.
Theorem 2. Let K := (G, M, W, I) be an attribute-complete many-valued context. Then the following conditions are equivalent: tu tu • E(K) is regular • A(K) is atomistic • A(K) induces a π-lattice • L(A(K)) =∼ B(Knom) tu
if we consider a K-vector space V. Let
K(V) := (V, End(V), V, I) where V is the set of vectors of V, End(V) is the set of endomorphisms of V, and I is defined as
(v, ϕ, w) ∈ I : ⇐⇒ ϕ(v) = w.
Since for vector spaces, every congruence relation is already representable as the kernel of an endomorphism (and the kernels of endomorphisms are always congruence relations), we know that E(K(V)) is closed. The lattice of the corresponding complete affine ordered set is isomorphic to the lattice of affine subspaces of the vector space V. Since E(K(V)) is regular we know by Theorem 2 that A(K(V)) is atomistic, its lattice is isomorphic to the concept lattice derived by nominal scaling, and it induces a π-lattice. 4
Weak Parallelisms and Affine Ordered Sets
denote the set of the atoms of L and for s ∈ L let A(s) := { p ∈ A(L) | p ≤ s} denote the atoms less than or equal to s. A lattice L is called atomic if for every s ∈ L+ we have A(s) 6= ∅. called residual, which is V– preserving with Definition 4 (residuated maps). A map ϕ : L −→ M is called residuated if it is W– preserving. For a residuated map, there exists a map ϕ+ : M −→ L, ϕm ≤ l ⇔ m ≤ ϕ+l The maps uniquely determine each other. If one of the maps is surjective, the other is injective, and vice versa. The maps are called adjoint to each other. We call (ϕ, ϕ+) a residuated pair or an adjunction (this is sometimes also called a covariant Galois connection).
Note, that for a residuated pair (ϕ, ϕ+) where ϕ is injective, we have ϕ+ϕ = Δ, since ϕϕ+ϕ = ϕ. In general ϕ+ϕ is a closure operator and ϕϕ+ is a kernel operator. call a relation k on L+ r, s, t, u ∈ L+ and arbitrary p ∈ A(L). (P1) r k r (P4) ∃!s : r k s ≥ p (P2) r k s ≥ t k u ⇒ r k≥ u (P3) r k s ≥ p ⇒ r ∨ p ≥ s Definition 5 (weak parallelism). Let L be an atomic complete lattice. We weak parallelism if the following holds for arbitrary equivalence relation the weak parallelism is called pre-parallelism.
Proposition 5. Let A be a complete affine ordered set. Then L(A) is an atomic complete lattice whith pre-parallelism.
axioms (P1)–(P4) for L(A). Axiom (P1) follows from the fact that the parallelism of A is an equivalence relation. Axiom (A2) grants us that (P4) holds.
from u k t ≤ s k π(p|r) we get u ≤ π(p|r)). Therefore we have r k π(p|r) ≥ u.
2 we know that (M) holds. Therefore r ≤ r ∨ p yields s = π(q|r) ≤ π(q|r ∨ p). But p ≤ s ≤ π(q|r ∨ p) implies π(q|r ∨ p) = r ∨ p. Hence, s ≤ r ∨ p. tu Example 2. The converse of the previous proposition does not hold: In general, atomic complete lattices with pre-parallelism do not induce a complete affine ordered set. If we remove the bottom element of the lattice in Figure 1 we can not consider the resulting structure as an affine ordered set since θ(a) = θ(x) would imply a = x. x a x k x a k a Fig. 1. Complete atomic lattice with trivial pre-parallelism
set to be atomistic to let the concepts coincide – for atomistic lattices a preparallelism is already a parallelism.
parallelism on L. Furthermore, let ϕ : M , Theorem 3. Let M and L be complete atomic lattices and let kL be a weak → L be a W– preserving, injective define a relation on M+ as follows mapping with ϕA(M ) ⊆ A(L) and let (ϕ, ϕ+) form a residuated pair. Then we r k
M s :⇔ ∃y ∈ L : ϕr kL y & ϕ+y = s. y := ϕ+ϕr in the definition of kM .
The relation k M is a weak parallelism.
M is reflexive. Since ϕϕ+ϕr = ϕr and ϕ is injective, we have ϕ+ϕr = r. Since ϕr k
M s ≥ t kM u. We have to show the existence of an element v ∈ M y ∈ L such that ϕr k such that ϕt k ϕr kL y ≥ ϕt k q ≥ z and ϕr k with v ≥ u and r k
L q. We have v := ϕ+q ≥ ϕ+z = u and r k M v.
L y and ϕ+y = s. From t k
L z and ϕ+z = u. But since ϕ+y ≥ t implies y ≥ ϕt we have
which implies s = ϕ+y ≤ ϕ+ϕ(r ∨ p) = r ∨ p as required.
such that ϕr k
L y and ϕ+y = s. Since s = ϕ+y ≥ p implies y ≥ ϕp and ϕ maps atoms to atoms we can apply (P3) in M . This yields y ≤ ϕr ∨ ϕp = ϕ(r ∨ p) have to show that there exists exactly one s ∈ M+ with r k
M s ≥ p. We can ϕr k apply (P4) for ϕp and ϕr which yields the existence of exactly one y ∈ L+ with
L y ≥ ϕp. We set s := ϕ+y. Since y ≥ ϕp implies s = ϕ+y ≥ p and by construction of s we have r k we have an element s0 ∈ M+ with r k element y0 ∈ L+ with ϕr k yields y0 = y we have s = s0.
L y0 and ϕ+y0 = s0. But since ϕr k L y0 ≥ ϕp (P4)
Theorem 4. Let M and L be complete atomic lattices and let kL be a weak parallelism on L, furthermore, let (ϕ, ϕ+) be a residuated pair for M and L and let k
M be defined as in the previous theorem. Then we have r k
M
≥ s ⇔ ϕr kL≥ ϕs.
M Proof. Since r k
≥ s there exists an u ∈ M+ with r k of k
part-parallel to ϕs. The proof is finished since the argument is symmetric. Since ϕϕ+ is a kernel operator we have ϕs = ϕϕ+y ≤ y which yields that ϕr is
L y and ϕ+y = s. 5
Class Geometries and Affine Ordered Sets Throughout this section, let E := (D, E) be a closed system of equivalence relations. We know that we can assign a complete affine ordered set, denoted tu tu by A(E), to E. Alternatively, we can also assign the ordered set of equivalence classes ({[x]θ | θ ∈ E}, ⊆) to E. It is convenient to attach a bottom element to get a lattice
G(E) := (S ∪ {∅}, ⊆)
which we call class geometry of E. If the equivalence relations can be regarded
as the congruence relations of an algebra (in the sense of universal algebra) we
call their class geometry congruence class geometry. Congruence class geometries
were introduced and characterized geometrically via their closure operators in [
Now, we want to relate the class geometry G := G(E) and the lattice of the affine ordered set L := L(A(E)) of a closed system of equivalence relations to each other. Let ϕ+ : L → G be defined by ϕ+(C, θ) := C. Since we have ^(Ci, θi) = (\ Ci, \ θi), i∈I i∈I
i∈I ϕ+ ^ si = \ Ci = ^ ϕ+si i∈I i∈I i∈I for si = (Ci, θi). Note that ϕ+ is surjective.
ϕs := ^{l | s ≤ ϕ+l}.
relation containg M ⊆ D as
θ(M ) := \{θ ∈ E | M × M ⊆ θ} the above definition of the residual yields in our context that ϕ : S ,→ L is defined by
ϕC := (C, θ(C)).
kernel system in L. We summarize the results of the argumentation in Theorem 5. Let E := (D, E) be a closed system of equivalence relations. Let G := G(E) be its class geometry and let L := L(A(E)) be the lattice of its affine ordered set. Then (ϕ, ϕ+) (as defined above) forms an adjunction between G and L, where ϕ is injective and ϕ+ is surjective. This implies that G is embedded in L as a kernel system via ϕ.
shows the lattice of congruence relations of N5. Figure 4 shows the congruence class geometry of N5 embedded as a kernel system into the lattice of the affine ordered set of (the congruence relations of) N5. The kernel system is marked by black dots in Figure 4. Δ
Fig. 3. The congruence lattice of N5
It is easily observable that both, the class geometry G and the lattice L of the complete affine ordered set, form atomic lattices. By Proposition 5 we know that the parallelism of the affine ordered set constitutes a weak parallelism (even a pre-parallelism) in the sense of Definition 5. We use the residuated pair (ϕ, ϕ+) to apply Theorem 3. Since ϕ maps atoms to atoms, Theorem 3 yields that r kS s :⇔ ∃l ∈ L : ϕr k l & ϕ+l = s defines a weak parallelism on S+.
C kS D ⇔ ∃(P, ψ) ∈ L : θ(C) = ψ & P = D ⇔ D is a class of θ(C).
closed sets of a closure operator to be able to characterize this closure operator as assigning to a set M the smallest congruence class of a suitable algebra containing M . 6
Conclusion
yielded the fruitful characterization of π-lattices as atomistic affine ordered sets and opened up the possibility to interpret these structures as concept lattices.
ing class geometry we could view the class geometry as a kernel system in the affine ordered set and were able to recognize the induced parallelism as known from congruence class spaces, where it is used to coordinatize geometric spaces.
'&!•%"$# (∅,∅)