Introduction

In [5] the notion of an affine ordered set enables us to understand a many-valued context in order-theoretic and geometric terms. In [4] affine ordered sets were specialized to complete affine ordered sets to allow an algebraic interpretation. Here, we relate complete affine ordered sets to two other known types of general geometric structures, that is,

• π-lattices and • equivalence class geometries (or short class geometries).

In [6], π-lattices were introduced as an abstraction of affine geometries over rings and modules, yielding the possibility to study geometry in a very general setup. They will turn out to be a well describable specialization of complete affine 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. [7]. The weak parallelism of class geometries can be related to the parallelism of complete affine ordered sets by applying a rather abstract result -a residuated pair of mappings between atomic complete lattices where one carries a weak parallelism induces a weak parallelism on the other. As a first step, we will provide the necessary basic definitions. The second step will lead to an elaboration on the connection between complete affine ordered 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. Throughout the paper we assume that the reader is knowledgeable of the basic concepts of order theory and formal concept analysis, as provided, for instance, in [2] and [1].

Attribute-complete Many-valued Contexts and Complete Affine Ordered Sets

We recall the relevant definitions from [5] and [4]. For a mapping f : A −→ B between sets A and B, the kernel of f is defined as

ker(f ) := {(a 1 , a 2 ) | f (a 1 ) = f (a 2 )}. 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 m 1 , m 2 ∈ M are not functionally equiv-

alent, that is, ker(m 1 ) = ker(m 2 ) implies m 1 = m 2 , and • for all N ⊆ M there exists an attribute m ∈ M such that m and N are functionally equivalent, that is, ker(m) = n∈N ker(n).

A system of equivalence relations (SER) is a pair (G, E) where G is a set and E is a set of equivalence relations on G which contains the identity relation. A SER is called closed if its set of equivalence relations forms a closure system.

Let be the symbol for the disjoint union. Then the lifting of an ordered set (P, ≤) is given by (P {⊥}, ≤ ({⊥} × P {⊥})) and denoted as (P, ≤) ⊥ . Since the following notion is central in this paper we provide it as Definition 1 ((atomistic, complete) affine ordered set). We call a triple

A := (Q, ≤, ) affine ordered set, if (Q, ≤) is a partially ordered set, is an equivalence rela- tion (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) = ∅ (A2) ∀x ∈ Q ∀a ∈ A(Q) ∃!t ∈ Q : a ≤ t x (A3) ∀x, y, x , y ∈ Q : x x ≤ y y & A(x ) ∩ A(y ) = ∅ ⇒ x ≤ y (A4) ∀x, y ∈ Q ∃x , y ∈ Q : x y & A(x) ⊆ A(y) ⇒ x x & y y & A(x ) ∩ A(y ) = ∅ & A(x ) A(y ).

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.

For a point a and a subspace x we denote by π(a|x) the subspace which contains 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.

We introduce the following condition for affine ordered sets:

(A34) ∀x, y ∈ Q : x ≤ y ⇐⇒ A(x) ⊆ A(y) & θ(x) ⊆ θ(y)

If we assume that only (A1) and (A2) hold in Definition 1 the axioms (A3) and (A4) are equivalent to (A34).

In [4] it was shown that the notions of

• attribute-complete many-valued contexts,

• closed SERs, and • complete affine ordered sets with their respective morphisms form categories which are equivalent. We recall how the objects of these equivalent categories can be translated into 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}, ≤, )

where ≤ is defined by

([x]θ 1 , θ 1 ) ≤ ([y]θ 2 , θ 2 ) : ⇐⇒ [x]θ 1 ⊆ [y]θ 2 & θ 1 ⊆ θ 2

and is defined by

([x]θ 1 , θ 1 ) ([y]θ 2 , θ 2 ) : ⇐⇒ θ 1 = θ 2 .

π-Lattices and Complete Affine Ordered Sets

The notion of a π-lattice stems from [6] where it is situated as an abstraction of a geometry over rings. For a complete lattice L, we define

L + := L \ L.

A π-lattice is defined as follows:

Definition 2 (π-lattice). Let V be a complete atomistic lattice with set of atoms A(V ). Then an equivalence relation ⊆ V + × V + is called parallelism if it satisfies the following axioms

(E) ∀p ∈ A(V ) ∀x ∈ V + ∃!y ∈ V + : p ≤ y x (M) ∀p ∈ A(V ) ∀x, y ∈ V + : x ≤ y =⇒ π(p|x) ≤ π(p|y).

We call an atomistic complete lattice with parallelism π-lattice.

It turns out that complete affine ordered sets are a natural generalization of π-lattices.

Proposition 1. Let V be a π-lattice. Then (V + , ≤ V , ) forms a complete affine ordered set.

Proof. Since V is a π-lattice, is an equivalence relation. We have to show that (A1) -(A4) hold for (V \ {0}, ≤ V , ). Since V is atomistic (A1) holds. (E) directly implies (A2). For showing (A34), let x ≤ y for x, y ∈ V + . Obviously A(x) ⊆ A(y) follows directly from x ≤ y. Furthermore, θ(x) ⊆ θ(y) by (M). For the other direction, already A(x) ⊆ A(y) implies x ≤ y since we have

x = A(x) ≤ A(y) = y because V is atomistic. By construction (V + ) ⊥ = V is a complete lattice.

The notion of parallelism for affine ordered sets fulfills the criteria of a parallelism from the definition of π-lattices without problems. Proposition 2. Let A := (Q, ≤, ) be an affine ordered set. Then (E) and (M) hold in L(A).

Proof. (E) follows directly from (A2).

To show (M) let x ≤ y for x, y ∈ L(A) + and p ∈ A(L(A)). We have to show that π(p | x) ≤ π(p | y). By (A34) we have

θ(π(p | x)) = θ(x) ⊆ θ(y) = θ(π(p | y)).

Additionally, it follows directly thatA(π(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).

Propositions 1 and 2 yield the following characterization of π-lattices in terms 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.

We will illuminate what it means for a complete affine ordered set to be 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 = 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, A(x) = (X, θ(X)) = (X, θ) and hence A(E) is atomistic. "⇐": Let A := (Q, ≤,

) 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 that θ(x) = θ(y). Since A is atomistic we have

x = [p]θ(x) = [p]θ(y) = y. Hence E(A) is regular.

The subclass of atomistic complete affine ordered sets can be related to concept lattices arising in a certain fashion from the many-valued context corresponding to the affine ordered set. To be able to formulate this connection, we need the following Definition 3 (derived context via nominal scaling). Let K := (G, M, W, I) be a complete many-valued context. Then the formal context

K nom := (G, N, J) is called derived context via nominal scaling of K if N := {(m, w) ∈ M × W | ∃g ∈ G : m(g) = w} and J := {(g, (m, w)) ∈ G × N | (g, m, w) ∈ I}.

Now we explain the connection between atomicity of complete affine ordered sets and conceptual scaling. 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 K nom be the derived context of K via plain nominal scaling. Let ϕ : A → B(K nom ) be a mapping where (C, θ) → (C, C J ). Then ϕ is an order-preserving mapping which is

• surjective if and only if A is complete and • injective if and only if A is atomistic.

Proof. To see that (C, C J ) ∈ B(K nom ) we have to show that C = C JJ , that is that C is an extent of a formal concept of the concept lattice of K nom . It is obvious that C ⊆ C JJ since • JJ is a closure operator. By construction of A we know that there exists a h ∈ G and a m ∈ M such that

C = [h]ker(m) = {g ∈ G | m(g) = m(h)} = {g ∈ G | (g, (m, m(h))) ∈ J}.

Hence, (m, m(h)) ∈ C J . But then for all g ∈ C JJ we have gJ(m, m(h)) which shows that if g ∈ C JJ then g ∈ C. Therefore C = C JJ . It is obvious that ϕ is order-preserving. "⇒": Let A be complete. We show that ϕ is surjective. Since the extents of B(K nom ) are exactly the meets of equivalence classes induced by K, and the set 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 ϕ(C 1 , θ 1 ) = ϕ(C 2 , θ 2 ). Then (C 1 , C 1 J ) = (C 2 , C 2 J ) which implies C 1 = C 2 .

But since we know by Proposition 3 that E(A) is regular we have θ 1 = θ 2 . "⇐": Let ϕ be surjective. Then every extent of B(K nom ) is an image of ϕ. But since the extents of B(K nom ) are exactly the meets of equivalence classes induced by K, we know that the set of equivalence classes is meet-closed and therefore A is complete. Let ϕ be injective. Then whenever

(C 1 , C 1 J ) = ϕ(C 1 , θ 1 ) = ϕ(C 2 , θ 2 ) = (C 2 , C 2 J ) which is equivalent to C 1 = C 2 we have θ 1 = θ 2 . That means, E(A) is regular.

Again, by Proposition 3 we know that A is atomistic.

The proof of the previous proposition yields the following 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 K nom be the derived context of K via plain nominal scaling. Then

B(K nom ) ∼ = L(A) if and only if A is atomistic.

The combination of Propositions 2 and 3 and Corollary 1 can be cast as: Theorem 2. Let K := (G, M, W, I) be an attribute-complete many-valued context. Then the following conditions are equivalent:

• E(K) is regular • A(K) is atomistic • A(K) induces a π-lattice • L(A(K)) ∼ = B(K nom )

Example 1. We get a nice example of an attribute-complete many-valued context 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.

Weak Parallelisms and Affine Ordered Sets

In this section, we will derive insights about trace parallelisms induced by residuated mappings between atomic lattices. An application of these abstract results in the next section will lead to a better understanding of the connection between affine ordered sets and class geometries.

In the following let L and M denote complete lattices. For a lattice L, let A(L) 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) = ∅.

Definition 4 (residuated maps). A map ϕ : L −→ M is called residuated if it is -preserving. For a residuated map, there exists a map ϕ + : M −→ L, called residual, which is -preserving with

ϕ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.

Definition 5 (weak parallelism). Let L be an atomic complete lattice. We call a relation on L + weak parallelism if the following holds for arbitrary r, s, t, u ∈ L + and arbitrary p ∈ A(L).

(P1) r r (P2) r s ≥ t u ⇒ r ≥ u (P3) r s ≥ p ⇒ r ∨ p ≥ s (P4) ∃!s : r s ≥ p

We say for r, s ∈ L + with r ≥ s that s is part-parallel to r. If is an equivalence relation the weak parallelism is called pre-parallelism.

We will investigate the connection between affine ordered sets and the introduced weak parallelism. Proposition 5. Let A be a complete affine ordered set. Then L(A) is an atomic complete lattice whith pre-parallelism.

Proof. Obviously, L(A) is atomic (by (A1)) and complete. It remains to verify the 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. To show (P2), let r s ≥ t u. Let p ≤ u be a point. By (A3) we know that from u t ≤ s π(p|r) we get u ≤ π(p|r)). Therefore we have r π(p|r) ≥ u.

To show (P3), let r s ≥ p. Let q ≤ s be an arbitrary point of s. By Proposition 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.

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

x x a a a Fig. 1. Complete atomic lattice with trivial pre-parallelism As in the case of π-lattices -where it was enough to require an affine ordered set to be atomistic to let the concepts coincide -for atomistic lattices a preparallelism is already a parallelism.

We will show that a residuated pair between two complete atomic lattices where the latter carries a weak parallelism yields a weak parallelism on the former. This parallelism will also be called trace parallelism. Theorem 3. Let M and L be complete atomic lattices and let L be a weak parallelism on L. Furthermore, let ϕ : M → L be a -preserving, injective mapping with ϕA(M ) ⊆ A(L) and let (ϕ, ϕ + ) form a residuated pair. Then we define a relation on M + as follows

r M s :⇔ ∃y ∈ L : ϕr L y & ϕ + y = s.

The relation M is a weak parallelism.

Proof. In the following, let r, s, t, u ∈ M and p ∈ A(M ). For (P1), we have to show that M is reflexive. Since ϕϕ + ϕr = ϕr and ϕ is injective, we have ϕ + ϕr = r. Since ϕr L ϕr we have r M r via setting y := ϕ + ϕr in the definition of M . For (P2), let us assume that r M s ≥ t M u. We have to show the existence of an element v ∈ M with v ≥ u and r M v. From r M s we know there exists y ∈ L such that ϕr L y and ϕ + y = s. From t M u we know there exists z ∈ L such that ϕt L z and ϕ + z = u. But since ϕ + y ≥ t implies y ≥ ϕt we have ϕr L y ≥ ϕt L z. Applying (P2) yields the existence of an element q ∈ L with q ≥ z and ϕr L q. We have v := ϕ + q ≥ ϕ + z = u and r M v. For (P3), let us assume r M s ≥ p. From r M s we know there exists y ∈ L such that ϕr 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) which implies s = ϕ + y ≤ ϕ + ϕ(r ∨ p) = r ∨ p as required. For (P4), we have an atom p ∈ A(M ) and an arbitrary element r ∈ M + . We have to show that there exists exactly one s ∈ M + with r M s ≥ p. We can apply (P4) for ϕp and ϕr which yields the existence of exactly one y ∈ L + with ϕr L y ≥ ϕp. We set s := ϕ + y. Since y ≥ ϕp implies s = ϕ + y ≥ p and by construction of s we have r M s it remains to show that s is unique. Assume we have an element s ∈ M + with r M s ≥ p. This means that there exists an element y ∈ L + with ϕr L y and ϕ + y = s . But since ϕr L y ≥ ϕp (P4) yields y = y we have s = s .

In the following theorem we characterize relations which arise from weak parallelisms in the manner described in Theorem 3 by "part-parallelity". This result can be used to see how the two weak parallelisms in Theorem 3 are connected. Theorem 4. Let M and L be complete atomic lattices and let L be a weak parallelism on L, furthermore, let (ϕ, ϕ + ) be a residuated pair for M and L and let M be defined as in the previous theorem. Then we have r M ≥ s ⇔ ϕr L ≥ ϕs.

Proof. Since r M ≥ s there exists an u ∈ M + with r M u ≥ s. By definition of M we have the existence of an element y ∈ L with ϕr L y and ϕ + y = s. Since ϕϕ + is a kernel operator we have ϕs = ϕϕ + y ≤ y which yields that ϕr is part-parallel to ϕs. The proof is finished since the argument is symmetric.

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

(C i , θ i ) = ( i∈I C i , i∈I θ i ), we have ϕ + i∈I s i = i∈I C i = i∈I ϕ + s i for s i = (C i , θ i ). Note that ϕ + is surjective.

From Proposition 9 in [2], p. 14, we know that for any residual map its residuated is given by ϕs := {l | s ≤ ϕ + l}. Since ϕ + is surjective, it follows that ϕ is injective. This implies that ϕS is a 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 ϕ.

As an illustration of the previous theorem we provide Example 3. Figure 2 shows the well-known non-modular lattice N 5 . Figure 3 shows the lattice of congruence relations of N 5 . Figure 4 shows the congruence class geometry of N 5 embedded as a kernel system into the lattice of the affine ordered set of (the congruence relations of) N 5 . The kernel system is marked by black dots in Figure 4. 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 Surprisingly, this is exactly the same weak parallelism as is used in [7] on the 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 .

Conclusion

Studying the connection between complete affine ordered sets and π-lattices yielded the fruitful characterization of π-lattices as atomistic affine ordered sets and opened up the possibility to interpret these structures as concept lattices. Through an adjunction between a complete affine ordered set and its corresponding 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. We conclude that the findings in this paper support the thesis that affine ordered sets are a conceptually useful paradigm to connect different notions arising when studying geometric structures abstractly.