Algebra univers. 57 (2007) 419–453 0002-5240/07/040419 – 35, published online November 5, 2007 DOI 10.1007/s00012-007-2051-z c Birkh¨

auser Verlag, Basel, 2007

Algebra Universalis

Greechie diagrams of orthomodular partial algebras Richard Holzer Abstract. Greechie diagrams are well known graphical representations of orthomodular partial algebras, orthomodular posets and orthomodular lattices. For each hypergraph D a partial algebra JDK = (A; ⊕, ′ , 0) of type (2,1,0) can be defined. A Greechie diagram can be seen as a special hypergraph: different points of the hypergraph have different interpretations in the corresponding partial algebra JDK, and each line in the hypergraph has a maximal Boolean subalgebra as interpretation, in which the points are the atoms. This paper gives some generalisations of the characterisations in [K83] and [D84] of diagrams which represent orthomodular partial algebras (= OMAs), and we give an algorithm how to check whether a given hypergraph D is an OMA-diagram whose maximal Boolean subalgebras are induced by the lines of the hypergraph.

1. Introduction In [K83] and [D84] some characterisations of Greechie diagrams of orthomodular posets and of orthomodular lattices are given under some assumptions, for example, that the family of blocks is pasted, or that the intersection of each pair of blocks contains at most four elements. Now we are going to present a generalisation of these characterisations for orthomodular partial algebras (or equivalently orthomodular posets, see [BM94]). Here we consider, principally, arbitrary hypergraphs with finite lines. A Greechie diagram can be seen as a special hypergraph: different points of the hypergraph have different interpretations in the corresponding partial algebra A := (A; ⊕, ′ , 0) of type (2,1,0) and each line in the hypergraph has a maximal Boolean subalgebra as interpretation, in which the points are the atoms. A diagram is complete if each maximal Boolean subalgebra is induced by a line of the hypergraph. The characterisation theorems in Section 3 provide conditions to check, whether a hypergraph is a complete diagram of an orthomodular partial algebra. This property can be checked without having to compute the interpretation. We just have to consider the lines in the hypergraph.

Presented by S. Pulmannova. Received July 22, 2004; accepted in final form February 1, 2007. 2000 Mathematics Subject Classification: Primary: 08A55, Secondary: 06F99. Key words and phrases: Orthomodular partial algebra, orthomodular poset, Greechie diagram. 419

420

R. Holzer

Algebra univers.

2. Blocks of orthomodular partial algebras e

Definition 2.1. An existence equality s = t holds in a partial algebra A if for every valuation of the variables the interpretations of s and t exist and are equal. The e term existence statement t = t is written as D(t). An orthomodular partial algebra (briefly: OMA) is a partial algebra A := (A; ⊕, ′ , 0) of type (2, 1, 0) such that the following axioms hold in A: (A0) (A1) (A2) (A3) (A4) (A5) (A6) (A7) (A8) (A9)

D (0), e x′′ = x, e x ⊕ x′ = 0′ , e x ⊕ 0 = x, e D (x ⊕ y) ⇒ x ⊕ y = y ⊕ x, e D ((x ⊕ y) ⊕ z) ⇒ (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z), ′ D (x ⊕ y) ∧ D (y ⊕ z) ⇒ D (x ⊕ z), e D (x ⊕ y ′ ) ∧ D (x′ ⊕ y) ⇒ x = y, D (x ⊕ y) ∧ D (y ⊕ z) ∧ D (x ⊕ z) ⇒ D (x ⊕ (y ⊕ z)), e D (x ⊕ y ′ ) ⇒ x ⊕ (x ⊕ y ′ )′ = y.

Note that axioms (A3) and (A6) are consequences of the other axioms (see [Pu94]). When we use different partial algebras A, B, . . . , then sometimes we write the partial algebra as index of the operations (⊕A , ⊕B , . . . ,) to make clear which operation is meant. In an OMA A we define 1 := 0′ . There exists a canonical bijection between the class of all OMAs and the class of all orthomodular posets (see [BM94]): For every OMA A the structure (A, ≤, ′ , 0), with x ≤ y iff x ⊕ y ′ exists, is an orthomodular poset; and for every orthomodular poset (B, ≤, ′ , 0), the structure (B, ⊕, ′ , 0), with x ⊕ y = z iff x ≤ y ′ and z = sup(x, y), is an OMA. These transformations are inverse to each other. We have x ≤ y iff there is an element z ∈ A with x ⊕ z = y. If x ⊕ y exists for some x, y ∈ A then inf(x, y) = 0 (see [BM94]). The induced order ≤B of a subalgebra B (which is always an OMA because the axioms are open formulas) is the restriction of the order ≤A . An OMA A is called Boolean iff the corresponding orthomodular poset (A, ≤, ′ , 0) is a Boolean lattice. For an OMA A, let atoms(A) be the set of all atoms of the induced orthomodular poset (A, ≤,′ , 0). For a set M let P(M ) := (P(M ), ⊕, ′ , Ø) be the Boolean OMA with the powerset of M as carrier set, E ′ = M \E and E ⊕F = G iff G is the disjoint union of E and F cofin ′ for E, F, G ⊆ M . Let Pcofin fin (M ) := (Pfin (M ), ⊕, , Ø) be the Boolean subalgebra of P(M ) with Pcofin fin (M ) = {E ⊆ M | E is finite or M \ E is finite }. If M is finite, then we have Pcofin fin (M ) = P(M ). For a partial algebra A = (A, ⊕,′ , 0) the cardinality |A| of A is defined as the cardinality of the carrierset A: |A| := |A|. A maximal Boolean subalgebra of a

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

421

partial algebra A = (A, ⊕,′ , 0) is called a block. The subalgebra which is generated by a subset E ⊆ A is denoted by hEi. ` For a family (Ai )i∈I of OMAs the coproduct C = i∈I Ai in the category of partial algebras is a “0-1-gluing”; that means all zero elements of the OMAs are identified ini (0Ai ) = 0C = inj (0Aj ) for i, j ∈ I, where ini : Ai → C is the canonical injection into the coproduct, and all units of these OMAs are identified ini (1Ai ) = 1C = inj (1Aj ) for i, j ∈ I. All other elements remain unequal: ini (a) 6= inj (b) for all i, j ∈ I, a ∈ Ai and b ∈ Aj with (i, a) 6= (j, b) and 0Ai 6= a 6= 1Ai . Now we show some properties of OMAs. Lemma 2.2. Let A be a Boolean OMA, a ∈ atoms(A) and b ∈ A. Then a ≤ b or a ≤ b′ . If b is also an atom with a 6= b then a ⊕ b exists. Proof. The first statement is proved by distributing inf(a, sup(b, b′ )). If b is an atom with a 6= b then a 6≤ b and a ≤ b′ , so a ⊕ b exists.  The following theorem is a generalisation of a remark in [BM94]: Theorem 2.3. Let A be an OMA and E ⊆ A. Then the following conditions are equivalent: (1) a ⊕ b exists for all a, b ∈ E with a 6= b. (2) There exists an isomorphism φ : P := Pcofin fin (G) → hEi with φ(F ) = ⊕F and φ(G \ F ) = (⊕F )′ for finite subsets F ⊆ G, where G := (E ∪ {(⊕E)′ }) \ {0} if E is finite and G := E \ {0} if E is infinite. (3) E generates a Boolean subalgebra of A with E ⊆ atoms(hEi) ∪ {0}. Proof. (1) ⇒ (2): Because of the axioms (A4), (A5) and (A8) the sum ⊕F exists and is well defined for all finite subsets F ⊆ E. Therefore the set G in condition (2) is well defined. Let φ : P → hEi be given with φ(F ) := ⊕F and φ(G \ F ) = (⊕F )′ for finite subsets F ⊆ G. The function φ is well defined because if F and G \ F are finite, then

⊕F ⊕ ⊕(G \ F ) = ⊕G = ⊕E ⊕ (⊕E)′ = 1 and therefore ⊕F = (⊕(G \ F ))′ because of the uniqueness of the complement (see [BM94]). Obviosly φ(F ) ∈ hEi for all F ∈ P . The mapping φ is compatible with ′ and 0.

422

R. Holzer

Algebra univers.

Compability with ⊕ : Let F1 , F2 ∈ P be such that F1 ⊕P F2 exists. Then F1 ∩ F2 = Ø and F1 or F2 must be finite. If both are finite then we have φ(F1 ⊕P F2 ) = ⊕A (F1 ∪ F2 ) = φ(F1 ) ⊕A φ(F2 ). Now assume that F1 is finite and F2 is infinite. Then ⊕A F1 ⊕A (⊕A (G \ F2 ))′ exists because of F1 ⊆ G \ F2 , so (φ(F1 ) ⊕A φ(F2 )) ⊕A (φ(F1 ⊕P F2 ))′ = ⊕A F1 ⊕A (⊕A (G \ F2 ))′ ⊕A ⊕A (G \ (F1 ⊕P F2 )) = (⊕A (G \ F2 ))′ ⊕A ⊕A (G \ F2 ) = 1, so we get φ(F1 ) ⊕A φ(F2 ) = φ(F1 ⊕P F2 ) because of the uniqueness of the complement. Analogously for infinite F1 and finite F2 . Therefore φ is a homomorphism. Closedness of φ : Let F1 , F2 ∈ P such that φ(F1 ) ⊕ φ(F2 ) exists. Then we have inf(φ(F1 ), φ(F2 )) = 0. Assume that there exists an element a ∈ F1 ∩ F2 . If F1 is finite then we get a ≤ ⊕F1 = φ(F1 ), and if F1 is infinite then we get a ≤ (⊕(G \ F1 ))′ = φ(F1 ) because of the existence of a ⊕ ⊕(G \ F1 ). Analogously we get a ≤ φ(F2 ), which is a contradiction to inf(φ(F1 ), φ(F2 )) = 0 6= a. Therefore we get F1 ∩ F2 = Ø, and F1 ⊕P F2 exists. Injectivity of φ : Let F1 , F2 ∈ P with φ(F1 ) = φ(F2 ). Case 1 : F1 and F2 are finite. Let a ∈ F1 . Then ⊕F1 ⊕a does not exist and therefore ⊕F2 ⊕a does not exist because of ⊕F2 = φ(F2 ) = φ(F1 ) = ⊕F1 . Therefore a ∈ F2 . So we get F1 ⊆ F2 and analogously F2 ⊆ F1 , so we have F1 = F2 . Case 2 : F1 or F2 is infinite. We may assume that F2 is infinite. If F1 is finite then we get

⊕F1 = φ(F1 ) = φ(F2 ) = (⊕(G \ F2 ))′ , so ⊕F1 ⊕ ⊕(G \ F2 ) = 1. But the set F1 ∪ (G \ F2 ) is finite, so there exists an element a ∈ G with a 6∈ F1 ∪ (G \ F2 ), and with axiom (A8) the sum

⊕(F1 ∪ (G \ F2 ) ∪ {a}) = 1 ⊕ a exists, which is a contradiction to 0 6∈ G. So F1 must be infinite, and because of φ(G \ F1 ) = φ(F1 )′ = φ(F2 )′ = φ(G \ F2 ) we get G \ F1 = G \ F2 as in Case 1. Therefore φ is injective. Surjectivity of φ : φ(P ) is a subalgebra of A because φ is a closed homomorphism. We have E \ {0} ⊆ φ(P ) and therefore hEi ⊆ φ(P ), so φ is surjective and an isomorphism.

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

423

(2) ⇒ (3): {g} is an atom of the Boolean OMA Pcofin fin (G) for g ∈ G, so φ({g}) = g is an atom of the Boolean OMA hEi. Therefore E ⊆ atoms(hEi) ∪ {0}. (3) ⇒ (1): See Lemma 2.2 and axioms (A3) and (A4).  Note that if E = atoms(B) for a Boolean subalgebra B ≤ A which is generated by atoms(B), then we get G = E in this theorem, so B ∼ = Pcofin fin (E). This theorem is useful to find Boolean subalgebras and blocks in an OMA. By setting E := atoms(A), it also provides a characterisation of Boolean OMAs that are generated by the atoms: Corollary 2.4. Every Boolean OMA A which is generated by atoms(A) is (up to isomorphy) of the form Pcofin fin (E) for a set E. In the following theorem we use Theorem 2.3 to show that the atoms of an OMA in which each block is generated by the atoms are exactly the atoms of the blocks occuring in the OMA. Theorem 2.5. Let A be an OMA, such that each block B ≤ A is generated by atoms(B). Then S {atoms(B) | B block of A} = atoms(A).

Proof. “⊆”: Let B be a block of A and x ≤ z ∈ atoms(B). Now we show x ∈ {0, z}. y := (x ⊕ z ′ )′ exists and x ⊕ y = z because of axiom (A9). Let E := (atoms(B) \ {z}) ∪ {x, y}. For e ∈ atoms(B) \ {z} the sums x ⊕ e and y ⊕ e exist because of axioms (A5) and (A4) and the existence (see Lemma 2.2) of z ⊕ e = (x ⊕ y) ⊕ e. So for all a, b ∈ E with a 6= b the sum a ⊕ b exists, and because of Theorem 2.3, E generates a Boolean subalgebra C. We have atoms(B) \ {z} ⊆ C and z = x ⊕ y ∈ C, so B ⊆ C because B is generated by atoms(B). Therefore B = C because B is a maximal Boolean subalgebra. So we have x, y ∈ B and therefore x ∈ {0, z}, and z is an atom of A. “⊇”: Now assume a ∈ atoms(A). Then {0, 1, a, a′ } is a Boolean subalgebra which contains a. By Zorn’s Lemma there exists a maximal Boolean subalgebra B ≤ A which contains a. Of course a ∈ atoms(B) because a is an atom of A. So S we get a ∈ {atoms(B) | B block of A}.  A consequence of this theorem is, that every OMA A in which each block is generated by its atoms, is generated by atoms(A), because each element a ∈ A is in a block B ≤ A and therefore a is generated by atoms(B) ⊆ atoms(A). 3. Greechie diagrams Greechie diagrams are used as graphical representations of OMAs.

424

R. Holzer

Algebra univers.

Definition 3.1. A hypergraph (see [Bg76]) D = (P, R) consists of a set P and a S system R ⊆ P(P ) of sets with R = P and Ø 6∈ R. The elements of P are called points, the elements of R are called lines. The hypergraph is called nontrivial if P 6= Ø. Two points a, b ∈ P are called connected by the line r ∈ R if a, b ∈ r. ` Let C := r∈R Pcofin fin (r) be the coproduct of the Boolean OMAs in the category of partial algebras. For r ∈ R let inr : Pcofin fin (r) → C be the canonical injection into the coproduct. Define ∼D := {(inr ({a}), ins ({a})) | r, s ∈ R and a ∈ r ∩ s}. Let h∼D i be the smallest congruence relation on C that contains ∼D . The interpretation of D is defined by JDK := C /h∼D i. For a ∈ P the interpretation of the point a is defined by JaK := inr ({a})/h∼D i, S where r is a line which contains a. Because of P = R there always exists such a line r, and because of the definition of ∼D the interpretation JaK of a is well defined. For r ∈ R the interpretation of the line r is defined by cofin JrK := inr (Pcofin fin (r))/h∼D i := {inr (E)/h∼D i | E ∈ Pfin (r)}.

A hypergraph D is called an (abstract Greechie) diagram if the following three conditions hold: (C1) a 6= b implies JaK 6= JbK for a, b ∈ P . (C2) nath∼D i ◦ inr : Pcofin fin (r) → JrK is an isomorphism for all r ∈ R. Note that this condition is equivalent to the property that nath∼D i ◦ inr : Pcofin fin (r) → JDK is injective and closed. (C3) JrK is a block of JDK for all r ∈ R. A hypergraph D is called complete if for every block B ≤ JDK there exists a line r ∈ R such that JrK = B. A hypergraph (diagram) D is called OMA-hypergraph (OMA-diagram resp.) if JDK is an OMA. In the graphical representation of a hypergraph each line r ∈ R connects the points a ∈ r. To distinguish between one and two lines in the graphical representation, we consider a line r ∈ R as a line without a corner, that means a differentiable curve. For example the hypergraph in Figure 1 contains only one line (R = {{a, b, c, d, e}}), while Figure 2 contains two lines (R = {{a, b, c}, {c, d, e}}). If two lines intersect in a single point a ∈ P , then these lines have to have different tangents at this point. If two lines intersect in a more than one point, parallel lines can be used between the points in the intersection (see Figure 3). In such a situation the points should be drawn large enough to lie on both lines. The hypergraph in Figure 3 is not a diagram, because condition (C1) is not satified. There is another possibility to define the interpretation of a hypergraph D: instead of the congruence relation h∼D i we can use the congruence relation hσi with cofin σ := {(inr (E), ins (E)) | r, s ∈ R and E ∈ Pcofin fin (r) ∩ Pfin (s)}. If we now define JDK := C/hσi, then we get a different interpretation of the diagram (see Example 2

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

b

a

425

c d e

Figure 1. Hypergraph with one line. a

b

c d e

Figure 2. Hypergraph with two lines.

Figure 3. Another hypergraph with two lines.

in Section 4). If every line of a diagram is finite, then both definitions coincide; we just get a difference if there are infinite lines. All theorems, lemmas and corollaries which are proved in this paper also hold for this new definition, except Theorem 3.18. In this theorem we would have some problems proving the isomorphy JDK ∼ = JComp(D)K. We do not know a counterexample for this isomorphy (with hσi instead of h∼D i), but because of the properties of Example 2 (see Section 4) we think Theorem 3.18 does not hold for this new definition of JDK. In the following, in a diagram D = (P, R) an element a ∈ P is identified with the corresponding element JaK ∈ JDK. Because of condition (C1) and the definition of ∼D we have a = b iff JaK = JbK for a, b ∈ P , so P can be seen as a subset of JDK: P = {JaK | a ∈ P } = {inr ({a})/h∼D i | a ∈ r ∈ R} ⊆ JDK. Note that a diagram is finite iff its interpretation is finite. If the elements of R are disjoint then h∼D i = idC and JDK ∼ = C. The trivial hypergraph D = (Ø, Ø) is the only hypergraph with |JDK| = 0. Obviously this hypergraph is a complete diagram, but not an OMA-diagram. There does not

426

R. Holzer

Algebra univers.

exist a diagram D with |JDK| = 1, because for each hypergraph D = (P, R) with |JDK| = 1 we get R 6= Ø, and with the condition Ø 6∈ R we get the existence of r ∈ R with |r| ≥ 1, so we have |Pcofin fin (r)| ≥ 2 but |JrK| ≤ |JDK| = 1, so condition (C2) does not hold. There exists up to isomorphy exactly one diagram D with |JDK| = 2. This is proved in the following lemma. Lemma 3.2. Let D = (P, R) be a diagram. Then the following conditions are equivalent: (1) (2) (3) (4)

|JDK| = 2. There exists a line r ∈ R with |r| = 1. R = {{a}} for an element a ∈ P . |P | = 1.

Proof. (1) ⇒ (2): Because of R 6= Ø there is a line r ∈ R. Because of the definition of hypergraphs we have r 6= Ø, and because of condition (C2) and |JDK| = 2 we get |r| = 1. (2) ⇒ (3): Let r ∈ R with |r| = 1. Because of condition (C3) the set {0, 1} = JrK is a maximal Boolean subalgebra, but for s ∈ R this subalgebra is contained in JsK, so we get JsK = {0, 1}. With condition (C2) we get |s| = 1 and with condition (C1) we get r = s. S (3) ⇒ (4): P = R = {a}. S (4) ⇒ (1): We have Ø 6∈ R, and because of P = R we have R = {P } and JDK = {0, 1}.  So a line in a diagram with |P | > 1 is not a singelton: |r| > 1 for all r ∈ R. To check whether the interpretation of a hypergraph is an OMA we do not need to test all axioms, because some axioms are satisfied in interpretations of all hypergraphs. Theorem 3.3. Let D = (P, R) be a hypergraph with P 6= Ø. Then in JDK the axioms (A0), (A1), (A2), (A3), (A4) and (A9) hold. If D is a diagram then axiom (A7) holds too. Proof. (A0): Because of R 6= Ø there exists a line r ∈ R, so we get the existence of the constant 0 in Pcofin fin (r) and therefore in JDK, so axiom (A0) holds. (A1): Let x ∈ JDK. Then there exist r ∈ R and E ∈ Pcofin fin (r) with x = inr (E)/h∼D i. Because of the homomorphism nath∼D i ◦ inr we have x = inr (E ′′ )/h∼D i = x′′ , so axiom (A1) holds.

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

427

(A2): Let x ∈ JDK, r ∈ R and E ∈ Pcofin fin (r) with x = inr (E)/h∼D i. Then we have x ⊕ x′ = inr (E)/h∼D i ⊕ inr (E ′ )/h∼D i = inr (E ⊕ E ′ )/h∼D i = inr (r)/h∼D i = 0′ so axiom (A2) holds. (A3): Let x ∈ JDK, r ∈ R and E ∈ Pcofin fin (r) with x = inr (E)/h∼D i. Then we have x ⊕ 0 = inr (E)/h∼D i ⊕ inr (Ø)/h∼D i = inr (E ⊕ Ø)/h∼D i = x so axiom (A3) holds. (A4): Let x, y ∈ JDK such that x ⊕ y exists. Then, by the definition of a coproduct, there exist r ∈ R and E, F ∈ Pcofin fin (r) with x = inr (E)/h∼D i, y = inr (F )/h∼D i such that E ⊕ F exists. Therefore we have x ⊕ y = inr (E ⊕ F )/h∼D i = inr (F ⊕ E)/h∼D i = y ⊕ x so axiom (A4) holds. (A9): Let x, y ∈ JDK such that x ⊕ y ′ exists. Then, as above, there exist r ∈ R and E, F ∈ Pcofin fin (r) with x = inr (E)/h∼D i, y ′ = inr (F )/h∼D i such that E ⊕ F exists. Therefore we have x ⊕ (x ⊕ y ′ )′ = inr (E ⊕ (E ⊕ F )′ )/h∼D i = inr (F ′ )/h∼D i = y because Pcofin fin (r) is an OMA, so axiom (A9) holds. (A7): Now assume that D is a diagram. Let x, y ∈ JDK such that x ⊕ y ′ and x′ ⊕ y exist. Then there exist r ∈ R and E, F ∈ Pcofin fin (r) with x = inr (E)/h∼D i and y ′ = inr (F )/h∼D i such that E ⊕ F exists. Then we have E ∩ F = Ø and x′ = inr (r \ E)/h∼D i and y = inr (r \ F )/h∼D i. Because of condition (C2) and the existence of x′ ⊕ y, we get (r \ E) ∩ (r \ F ) = Ø and E = r \ F , so x = inr (E)/h∼D i = inr (r \ F )/h∼D i = y, and axiom (A7) holds.



Lemma 3.4. Let D = (P, R) be a diagram and r, s ∈ R such that r ∩ s is finite and r 6= s. Then |r \ s| > 1.

428

R. Holzer

Algebra univers.

Proof. The set JrK cannot be a subset of JsK, because then (C3) would imply JrK = JsK, and (C2) together with (C1) would then imply r = s. So we have |r \ s| > 0. Now assume |r \ s| = 1. Let a be the only element of r \ s. Then we get {JbK | a 6= b ∈ r} ⊆ JsK, JaK = (inr (r ∩ s)/h∼D i)′ = (ins (r ∩ s)/h∼D i)′ ∈ JsK, JrK ⊆ JsK. This is a contradiction to what was mentioned above.



So in a diagram with finite lines a line cannot contain all but one element of another line; in particular no line is contained in another line. The following lemma gives an easier condition than (C2) to check whether a hypergraph is a diagram: Lemma 3.5. Let D = (P, R) be a hypergraph that satisfies (C1) and (C3). Then D is a diagram iff for each a ∈ r ∈ R the element JaK is an atom of the block JrK. Proof. Assume that JaK is an atom of the block JrK for all a ∈ r ∈ R. Let r ∈ R. Then JrK is a Boolean OMA because of condition (C3). The element inr ({a})/h∼D i is an atom of this OMA for a ∈ r, and all these elements are different because of condition (C1). Therefore 0 6∈ {inr ({a})/h∼D i | a ∈ r} =: E. Note that if r is finite then (⊕E)′ = 1′ = 0. With Theorem 2.3 the function φ := nath∼D i ◦ inr : Pcofin fin (r) → JrK is an isomorphism, so (C2) holds and D is a diagram. The converse is trivial.



So in a diagram D = (P, R) the interpretation JrK of each line r ∈ R is a block in which the points are the atoms and all points have different interpretations. These conditions are sufficient and necessary for the property that a hypergraph is a diagram. Another method to prove that a hypergraph is a diagram is given in Theorem 3.7. First we need a lemma: Lemma 3.6. Let D = (P, R) be a hypergraph such that (inr ({a}), ins (E)) ∈ h∼D i implies E = {a} for all a ∈ r ∈ R and s ∈ R and E ∈ Pcofin fin (s). Let B a Boolean subalgebra of JDK and inr ({a})/h∼D i ∈ B for some a ∈ r ∈ R. Then inr ({a})/h∼D i ∈ atoms(B). Proof. Let y ∈ B with y ≤ inr ({a})/h∼D i. Then there exists an element z ∈ B with y ⊕ z = inr ({a})/h∼D i. There exist s ∈ R and E, F ∈ Pcofin fin (s) with y = ins (E)/h∼D i, z = ins (F )/h∼D i, E ∩ F = Ø.

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

429

We get (inr ({a}), ins (E ∪ F )) ∈ h∼D i, E ∪ F = {a}, y ∈ {0, inr ({a})/h∼D i}. Therefore inr ({a})/h∼D i is an atom of B.



Theorem 3.7. Let D = (P, R) be a hypergraph such that each line of D is finite and (inr ({a}), ins (E)) ∈ h∼D iimplies E = {a} for a ∈ r ∈ R and E ⊆ s ∈ R. Then the following conditions are equivalent: (1) D is a diagram. (2) Condition (C2) holds. (3) Condition (C3) holds. Proof. (1) ⇒ (2): Trivial (2) ⇒ (3): Let r ∈ R. Because of (C2) the set JrK is a Boolean subalgebra of JDK. Let B be another Boolean subalgebra of JDK with JrK ⊆ B and let x ∈ B. The line r is finite, so there exists a finite Boolean subalgebra C ≤ B which contains JrK and x (take for example the sublattice of B which is generated by JrK∪{x, x′ } with respect to the lattice operations). For all a ∈ r the element inr ({a})/h∼D i is an atom of C because of Lemma 3.6. We have ⊕{inr ({a})/h∼D i | a ∈ r} = inr (r)/h∼D i = 1, so atoms(C) = {inr ({a})/h∼D i | a ∈ r} and x ∈ C = JrK which proves B = JrK, so (C3) holds. (3) ⇒ (1): (C1) is satisfied because inr ({a})/h∼D i = ins ({b})/h∼D i implies a = b for a ∈ r ∈ R and b ∈ s ∈ R. Let r ∈ R. Then JrK is a Boolean subalgebra of JDK because of (C3) and the function φ := nath∼D i ◦ inr : Pcofin fin (r) → JrK is an OMA-homomorphism between Boolean OMAs and therefore a Boolean lattice homomorphism (see [BM98]). Of course φ is surjective. Because of (inr ({a}), inr (Ø)) 6∈ h∼D i for a ∈ r the equivalence class 0/ ker(φ) in Pcofin fin (r) cannot contain an atom of Pcofin (r), so φ is injective. A bijective lattice homomorphism between Boolean fin OMAs is an OMA-isomorphism, so (C2) holds and D is a diagram. 

430

R. Holzer

Algebra univers.

This theorem states that for every hypergraph D = (P, R) with finite lines in which no point a ∈ P is equivalent to a different set E ∈ Pcofin fin (s) of points, we only have to check condition (C2) (which is easier than (C3)) to decide whether D is a diagram. Later it will be shown that for every OMA-diagram in which each block is generated by its atoms (inr ({a}), ins (E)) ∈ h∼D i implies E = {a} for all a ∈ r ∈ R and s ∈ R with E ∈ Pcofin fin (s) (see Theorem 3.13). Lemma 3.8. Let (Di )i∈I = (Pi , Ri )i∈I be a directed family of hypergraphs; that means for each i, j ∈ I there exists k ∈ I with Ri ∪ Rj ⊆ Rk . S S Let D := (P, R) := ( i∈I Pi , i∈I Ri ). Then the following properties hold: S (1) h∼D i = i∈I h∼Di i cofin (2) For all r, s ∈ R and E ∈ Pcofin fin (r) and F ∈ Pfin (s) we have inr (E)/h∼D i = ins (F )/h∼D i iff there exists i ∈ I with inr (E)/h∼Di i = ins (F )/h∼Di i. cofin cofin (3) For all r, s, t ∈ R and E ∈ Pcofin fin (r), F ∈ Pfin (s), G ∈ Pfin (t) we have

inr (E)/h∼D i ⊕ ins (F )/h∼D i = int (G)/h∼D i iff there exists i ∈ I with inr (E)/h∼Di i ⊕ ins (F )/h∼Di i = int (G)/h∼Di i. Proof. (1): For Ri ⊆ Rj we have

`

r∈Ri

Pcofin fin (r)

∼Di ⊆∼Dj ⊆∼D , ` cofin ` cofin ⊆ Pfin (r) ⊆ Pfin (r). r∈Rj

r∈R

Therefore we get h∼Di i ⊆ h∼Dj i ⊆ h∼D i. The union of a directed family of congruence relations is a congruence relation and we have S S ∼D = ∼Di ⊆ h∼Di i, i∈I

i∈I

so we get

h∼D i =

S

h∼Di i.

i∈I

(2): (2) follows from (1). cofin cofin (3): ⇐: Let i ∈ I and r, s, t ∈ Ri and E ∈ Pcofin fin (r), F ∈ Pfin (s), G ∈ Pfin (t) with inr (E)/h∼Di i ⊕ ins (F )/h∼Di i = int (G)/h∼Di i.

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

431

Then there exist u ∈ Ri and E2 , F2 , G2 ∈ Pcofin fin (u) with E2 ∩ F2 = Ø, E2 ∪ F2 = G2 , (inr (E), inu (E2 )) ∈ h∼Di i ⊆ h∼D i, (ins (F ), inu (F2 )) ∈ h∼Di i ⊆ h∼D i, (int (G), inu (G2 )) ∈ h∼Di i ⊆ h∼D i. Therefore inr (E)/h∼D i ⊕ ins (F )/h∼D i = int (G)/h∼D i. cofin cofin ⇒: Let r, s, t ∈ Ri and E ∈ Pcofin fin (r), F ∈ Pfin (s), G ∈ Pfin (t) with

inr (E)/h∼D i ⊕ ins (F )/h∼D i = int (G)/h∼D i. Then there exist u ∈ R and E2 , F2 , G2 ∈ Pcofin fin (u) with E2 ∩ F2 = Ø, E2 ∪ F2 = G2 , S (inr (E), inu (E2 )) ∈ h∼D i = h∼Di i, i∈I S (ins (F ), inu (F2 )) ∈ h∼D i = h∼Di i, i∈I S (int (G), inu (G2 )) ∈ h∼D i = h∼Di i. i∈I

The family is directed, so there is an element i ∈ I with

inr (E)/h∼Di i = inu (E2 )/h∼Di i, ins (F )/h∼Di i = inu (F2 )/h∼Di i, int (G)/h∼Di i = inu (G2 )/h∼Di i, and therefore inr (E)/h∼Di i ⊕ ins (F )/h∼Di i = int (G)/h∼Di i.



These properties are helpful to analyse infinite hypergraphs: The finite subhypergraphs form a directed family of hypergraphs, so we can use the properties of Lemma 3.8 to get some information about the structure of the whole hypergraph while only considering finite subhypergraphs. These properties are used in the following theorem to show that a union of a directed family of diagrams with finite lines is again a diagram. Theorem 3.9. Let (Di )i∈I = (Pi , Ri )i∈I be a directed family of diagrams in which S S each line is finite. Then D := (P, R) := ( i∈I Pi , i∈I Ri ) is a diagram.

432

R. Holzer

Algebra univers.

Proof. (C1): Condition (C1) follows from (2) of Lemma 3.8 because (C1) holds for Di . (C2): For r ∈ R the injectivity of nath∼D i ◦ inr follows from (2) of Lemma 3.8. The closedness follows from (3) of Lemma 3.8. (C3): Let r ∈ R. Because of (C2) the set JrK is a Boolean subalgebra of JDK. Let B be another Boolean subalgebra of JDK with JrK ⊆ B and let x ∈ B. The line r is finite, so there exists a finite Boolean subalgebra C ≤ B which contains JrK and x. The family is directed, so because of Lemma 3.8 and the finiteness of C there exists k ∈ I such that the set A := {ins (E)/h∼Dk i | s ∈ Rk , E ∈ Pcofin fin (s) with ins (E)/h∼D i ∈ C} is a subalgebra of JDk K which is isomorphic to C. The Boolean OMA A contains cofin inr (Pcofin fin (r))/h∼Dk i and we get A = inr (Pfin (r))/h∼Dk i because Dk is a diagram, therefore x ∈ JrK. So we get B = JrK and (C3) holds in D.  The union of a directed family of OMA-hypergraphs is an OMA-hypergraph: Theorem 3.10. Let (Di )i∈I = (Pi , Ri )i∈I be a directed family of OMA-hyperS S graphs. Then D := (P, R) := ( i∈I Pi , i∈I Ri ) is an OMA-hypergraph.

Proof. The axioms (A0)–(A4) and (A9) hold in JDK because of Theorem 3.3. (A8): Let x = inr (E)/h∼D i ∈ JDK, y = ins (F )/h∼D i ∈ JDK, z = int (G)/h∼D i ∈ JDK such that x ⊕ y, y ⊕ z and x ⊕ z exist. The family is directed, so with Lemma 3.8 there exists i ∈ I such that inr (E)/h∼Di i ⊕ ins (F )/h∼Di i, ins (F )/h∼Di i ⊕ int (G)/h∼Di i, inr (E)/h∼Di i ⊕ int (G)/h∼Di i exist, so inr (E)/h∼Di i ⊕ (ins (F )/h∼Di i ⊕ inr (E)/h∼Di i) exists because JDi K is an OMA. With Lemma 3.8 we get the existence of inr (E)/h∼D i ⊕ (ins (F )/h∼D i ⊕ inr (E)/h∼D i). (A5) and (A7): Analogously to (A8). (A6) follows from the other axioms, so D is an OMA-hypergraph.



The following theorem shows, that in an OMA-diagram, in which each block is generated by its atoms the interpretation of the set of points P is the set of the atoms, which occur in a block of JDK. Theorem 3.11. Let D = (P, R) be an OMA-diagram such that each block of JDK S is generated by its atoms. Then P = {atoms(B) | B block of JDK} = atoms(JDK).

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

433

S Proof. {atoms(B) | B block of JDK} = atoms(JDK) follows from Theorem 2.5. Because of the conditions (C2) and (C3) each equivalence class inr ({a})/h∼D i for a ∈ r ∈ R is an atom of the block JrK, so we have S P ⊆ {atoms(B) | B block of JDK}.

For x = inr (E)/h∼D i ∈ atoms(JDK) we get |E| = 1, because 0 = inr (Ø)/h∼D i 6∈ atoms(JDK) holds, and |E| > 1 would imply that x = y ⊕ z for some y, z ∈ JDK with y 6= 0 6= z, which is a contradiction to x ∈ atoms(JDK). Therefore x ∈ P , so atoms(JDK) ⊆ P .  For every complete diagram D = (P, R) we also get the equality S P = {atoms(B) | B block of JDK},

because each block B is induced by a line r, so the atoms of B are exactly the elements of r. If the diagram is not an OMA-diagram then we do not always have an order on JDK, so it does not make sense to ask whether P = atoms(JDK). Corollary 3.12. If D is a complete OMA-diagram then each block B ≤ JDK is generated by its atoms, and we have atoms(B) ⊆ P = atoms(JDK). Proof. Each block B of JDK is induced by a line r ∈ R, so B = JrK is generated by  atoms(JrK), and atoms(B) ⊆ P = atoms(JDK) follows from Theorem 3.11. Theorem 3.13. Let D = (P, R) be an OMA-diagram such that each block of JDK is generated by its atoms. Let a ∈ r ∈ R and s ∈ R and E ∈ Pcofin fin (s) with (inr ({a}), ins (E)) ∈ h∼D i. Then E = {a}. Proof. ins (E)/h∼D i = inr ({a})/h∼D i ∈ P = atoms(JDK), so |E| = 1 as in the proof of Theorem 3.11, and with condition (C1) we get E = {a}.  This theorem shows that a point of an OMA-diagram in which each block is generated by its atoms cannot be equivalent to another set of points. Together with the following lemma this theorem can be used to prove that every two points a, b ∈ P for which the sum a ⊕ b exists are connected by a line. Lemma 3.14. Let D = (P, R) be a hypergraph such that (inr ({a}), ins (E)) ∈ h∼D i implies E = {a} for all a ∈ r ∈ R and s ∈ R and E ∈ Pcofin fin (s). Let a, b ∈ P with a 6= b. Then JaK ⊕ JbK exists iff there exists a line t ∈ R with a, b ∈ t. Proof. ⇒: Assume that JaK ⊕ JbK exists. Let r, s ∈ R with a ∈ r and b ∈ s. Because of the existence of the sum inr ({a})/h∼D i ⊕ ins ({b})/h∼D i,

434

R. Holzer

Algebra univers.

there exist t ∈ R and E, F ∈ Pcofin fin (t) with E ∩ F = Ø such that (inr ({a}), int (E)) ∈ h∼D i and (ins ({b}), int (F )) ∈ h∼D i, so we have E = {a} and F = {b}. ⇐: The function nath∼D i ◦ int is a homomorphism.



This leads to the following theorem. Theorem 3.15. Let D = (P, R) be an OMA-diagram such that each block of JDK is generated by its atoms. For E ⊆ P the following conditions are equivalent: (1) E generates a Boolean subalgebra B ≤ JDK with E ⊆ atoms(B). (2) For all a, b ∈ E with a 6= b the sum JaK ⊕ JbK exists in JDK. (3) For all a, b ∈ E there exists a line r ∈ R with a, b ∈ r. Proof. (1) ⇒ (2): See Lemma 2.2. (2) ⇒ (1): With Theorem 2.3, E generates a Boolean subalgebra B with E ⊆ atoms(B) ∪ {0}, and with condition (C2) we get E ⊆ atoms(B). (2) ⇔ (3): See Theorem 3.13 and Lemma 3.14.  In a hypergraph D = (P, R), a maximal subset E ⊆ P in which each pair of points is connected by a line is called a clique. Theorem 3.16. If D is an OMA-diagram, such that each block of JDK is generated by its atoms, then the blocks of JDK are exactly the subalgebras that are induced by a clique. E = atomshEi for every clique E. Proof. ⇒: For a block B ≤ JDK take E := atoms(B) ⊆ P . Then Theorem 3.15 implies that each pair of points in E is connected by a line. Let E ⊆ F ⊆ P such that each pair of points in F is connected by a line. Then with Theorem 3.15, F generates a Boolean subalgebra C ≤ JDK with B ⊆ C. The Boolean subalgebra B is maximal, so B = C and F ⊆ atoms(C) = atoms(B) = E, which proves that E is a clique. ⇐: Let E be a clique. With Theorem 3.15, E generates a Boolean subalgebra B with E ⊆ atoms(B). The partial algebra B is contained in a block C. With Theorem 3.11 the set F := atoms(C) is contained in P , and with Theorem 3.15 each pair of points of F is connected by a line. For e ∈ E we have e ∈ atoms(B) ⊆ C and with Theorem 3.11, e is an atom of JDK and therefore e ∈ atoms(C) = F . So we have E ⊆ F and therefore E = F because E is maximal. So B = C is a block  and E = F = atoms(C) = atomshEi.

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

435

For a diagram D = (P, R) the completion of D is defined by Comp(D) := (P, Rc ) where Rc := {E ⊆ P | {JeK | e ∈ E} is the set of all atoms of a block of JDK} = {atoms(B) | B block of JDK with atoms(B) ⊆ P }. Corollary 3.17. If D is an OMA-diagram, such that each block of JDK is generated by its atoms then Rc = {E ⊆ P | E is a clique}. Proof. The atoms of each block are contained in P because of Theorem 3.11 and the cliques are exactly the atoms of blocks because of Theorem 3.16.  To analyse a Greechie diagram with respect to some properties (for example whether it is an OMA-diagram) it is sometimes better if the diagram is complete. There exists a canonical isomorphism between a diagram in which each block is generated by its atoms and the completion of the diagram, which is shown in the next theorem. Theorem 3.18. Let D = (P, R) be a diagram such that each block of JDK is generated by its atoms. Then (P, Rc ) := Comp(D) is a diagram with R ⊆ Rc and JDK ∼ = JComp(D)K, where the isomorphism is defined by φ : JDK → JComp(D)K, inr (E)/h∼D i 7→ inr (E)/h∼Comp(D) i. If atoms(B) ⊆ P for each block B ≤ JDK then Comp(D) is complete. Proof. We have Ø 6∈ Rc , because each block of D is generated by its atoms. D is a diagram, so the set {JaK | a ∈ r} for r ∈ R is the set of all atoms of the block JrK, S and we have R ⊆ Rc . First we prove the isomorphy JDK ∼ = J( (R ∪ T ), R ∪ T )K for every finite set T ⊆ Rc . Define {r1 , r2 , . . . , rn } := T \ R with ri 6= rj for i 6= j, Rj := R ∪ {r1 , r2 , . . . , rj } and Dj := (P, Rj ) for 0 ≤ j ≤ n. The conditions (C1), (C2), (C3) for Dj and the isomorphy JDK ∼ = JDj K are proved by induction: Let 0 < j ≤ n such that Dj−1 is a diagram and φj−1 : JDK → JDj−1 K, inr (E)/h∼D i 7→ inr (E)/h∼Dj−1 i is an isomorphism. For a ∈ P let sa ∈ R with a ∈ sa . For r ∈ Rc the set {insa ({a})/h∼D i | a ∈ r} is the set of all atoms of a block in JDK, and because of the isomorphism φj−1 the set {insa ({a})/h∼Dj−1 i | a ∈ r} is the set of all atoms of a block in JDj−1 K. For r ∈ Rc define τr : Pcofin fin (r) → JDj−1 K with τr (E) := ⊕{inse ({e})/h∼Dj−1 i | e ∈ E} and τr (r \ E) := (⊕{inse ({e})/h∼Dj−1 i | e ∈ E})′ for finite sets E ⊆ r. This function is well defined and an embedding because of Theorem 2.3 (with A :=

{insa ({a})/h∼Dj−1 i a ∈ r} as Boolean OMA), so E 6= F iff τr (E) 6= τr (F ) for E, F ∈ Pcofin fin (r).

436

R. Holzer

Algebra univers.

Define ψ : JDj−1 K → JDj K, inr (E)/h∼Dj−1 i 7→ inr (E)/h∼Dj i and φj := ψ ◦ φj−1 . These functions are well defined and compatible with the operations because of Rj−1 ⊆ Rj and ∼Dj−1 ⊆∼Dj , so they are homomorphisms. Surjectivity of ψ : Let x ∈ JDj K. Then there exist r ∈ Rj ⊆ Rc and E ∈ Pcofin fin (r) with inr (E)/h∼Dj i = x. ψ is a homomorphism, so if E is finite, then ψ(τr (E)) = ψ(⊕{inse ({e})/h∼Dj−1 i | e ∈ E}) = ⊕{ψ(inse ({e})/h∼Dj−1 i) | e ∈ E} = ⊕{inse ({e})/h∼Dj i | e ∈ E} = ⊕{inr ({e})/h∼Dj i | e ∈ E} = inr (E)/h∼Dj i = x, and if E is infinite, then r \ E is finite so we get ψ(τr (E)) = ψ(τr ((r \ E)′ )) = (inr (r \ E)/h∼Dj i)′ = x. Therefore ψ is surjective. In the following, each equivalence class τrj (E) for E ∈ Pcofin fin (rj ) is used as a ` Define ρ := ρ ∪ ρ ∪ ρ ∪ ρ , where (r). subset of r∈Rj Pcofin 1 2 3 4 fin ρ1 := h∼Dj−1 i, S ρ2 := {{inrj (E)} × τrj (E) | E ∈ Pcofin fin (rj )}, S cofin ρ3 := {τrj (E) × {inrj (E)} | E ∈ Pfin (rj )},

ρ4 := {(inrj (E), inrj (E)) | E ∈ Pcofin fin (rj )}. ` Now we prove that ρ is a congruence relation on r∈Rj Pcofin fin (r):

Reflexivity : ρ is reflexive because every pair (inr (E), inr (E)) with r ∈ Rj and E ∈ Pcofin fin (r) is an element of ρ1 or ρ4 . Symmetry : ρ is symmetrical because ρ1 , ρ2 ∪ ρ3 and ρ4 are symmetrical. Transitivity : Let (inr (E), ins (F )) ∈ ρ and (ins (F ), int (G)) ∈ ρ cofin cofin with r, s, t ∈ Rj and E ∈ Pcofin fin (r), F ∈ Pfin (s), G ∈ Pfin (t). If (inr (E), ins (F )) ∈ ρ4 or (ins (F ), int (G)) ∈ ρ4 then we have (inr (E), int (G)) ∈ ρ so we just have to consider the relations ρ1 , ρ2 and ρ3 .

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

437

Case 1 : (inr (E), ins (F )) ∈ ρ1 . If (ins (F ), int (G)) ∈ ρ1 , then (inr (E), int (G)) ∈ ρ1 ⊆ ρ because ρ1 is transitive. If (ins (F ), int (G)) ∈ ρ2 then ins (F ) ∈ ` cofin ( u∈Rj−1 Pcofin fin (u)) ∩ inrj (Pfin (rj )) = {0, 1}. For ins (F ) = 0 we get F = Ø and int (G) ∈ τrj (F ) = {0} because condition (C2) holds for Dj−1 . If ins (F ) = 1 then F = s and we have int (G) ∈ τrj (F ) = {1}. So ins (F ) = int (G) and (inr (E), int (G)) ∈ ρ. If (ins (F ), int (G)) ∈ ρ3 , then (inr (E), int (G)) ∈ ρ3 ⊆ ρ. Case 2 : (inr (E), ins (F )) ∈ ρ2 . If (ins (F ), int (G)) ∈ ρ1 then (inr (E), int (G)) ∈ ρ2 ⊆ ρ. If (ins (F ), int (G)) ∈ ρ2 then ins (F ) = int (G) ∈ {0, 1}, so we get (inr (E), int (G)) ∈ ρ. If (ins (F ), int (G)) ∈ ρ3 then (inr (E), int (G)) ∈ ρ4 ⊆ ρ because τrj is injective. Case 3 : (inr (E), ins (F )) ∈ ρ3 . If (ins (F ), int (G)) ∈ ρ1 ∪ ρ3 then ins (F ) = int (G) ∈ {0, 1} and therefore we get (inr (E), int (G)) ∈ ρ. If (ins (F ), int (G)) ∈ ρ2 then (inr (E), int (G)) ∈ ρ1 ⊆ ρ. Therefore ρ is transitive. Compatibility with ′ : ρ1 and ρ4 are compatible with ′ . Let (inr (E), ins (F )) ∈ ρ2 . Then r = rj and ins (F ) ∈ τrj (E) and therefore ins (F )′ ∈ τrj (r \ E) because τrj is a homomorphism. So we have (inr (E)′ , ins (F )′ ) = (inr (r \ E), ins (F )′ ) ∈ ρ2 ⊆ ρ and analogously for ρ3 , so ρ is compatible with the operation ′ . Compatibility with ⊕ : Let (inr (E), ins (F )) ∈ ρ and (int (G), inu (H)) ∈ ρ such that inr (E) ⊕ int (G) and ins (F ) ⊕ inu (H) exist. If E = Ø then with (inr (E), ins (F )) ∈ ρ1 ∪ ρ2 ∪ ρ3 ∪ ρ4 we get F = Ø, because (C2) holds in JDj−1 K, so we have (inr (E) ⊕ int (G), ins (F ) ⊕ inu (H)) = (int (G) ⊕ inu (H)) ∈ ρ. Analogously we get (inr (E) ⊕ int (G), ins (F ) ⊕ inu (H)) ∈ ρ if F = Ø or G = Ø or H = Ø. Now assume Ø 6∈ {E, F, G, H}.

(3.1)

r = t, s = u.

(3.2)

Then we have We get E ∩ G = Ø and F ∩ H = Ø. Let k ∈ {1, 2, 3, 4} with (inr (E), ins (F )) ∈ ρk . Then with (3.1) and (3.2) and the definition of ρ we get (int (G), inu (H)) ∈ ρk . Case 1 : k = 1. Then (inr (E) ⊕ int (G), ins (F ) ⊕ inu (H)) ∈ ρ1 ⊆ ρ. Case 2 : k = 2 or k = 3. We may assume k = 2. Then r = rj = t and ins (F ) ∈ τrj (E) and inu (H) ∈ τrj (G). The map τrj is a homomorphism, so we get ins (F ) ⊕ inu (H) ∈ τrj (E ⊕ G), (inr (E) ⊕ int (G), ins (F ) ⊕ inu (H)) ∈ ρ2 ⊆ ρ. Case 3 : k = 4. Then (inr (E) ⊕ int (G), ins (F ) ⊕ inu (H)) ∈ ρ4 ⊆ ρ. ` So ρ is a congruence relation on r∈Rj Pcofin fin (r). Let (inr ({a}), ins ({a})) ∈∼Dj .

438

R. Holzer

If r 6= rj If r = rj If r 6= rj If r = rj So we have

6= s, then (inr ({a}), ins ({a})) ∈ ρ1 6= s, then (inr ({a}), ins ({a})) ∈ ρ2 = s, then (inr ({a}), ins ({a})) ∈ ρ3 = s, then (inr ({a}), ins ({a})) ∈ ρ4 ∼Dj ⊆ ρ and therefore h∼Dj i ⊆ ρ.

Algebra univers.

⊆ ρ. ⊆ ρ. ⊆ ρ. ⊆ ρ.

Injectivity of ψ : Let inr (E)/h∼Dj−1 i, ins (F )/h∼Dj−1 i ∈ JDj−1 K with ψ(inr (E)/h∼Dj−1 i) = ψ(ins (F )/h∼Dj−1 i). Then (inr (E), ins (F )) ∈ h∼Dj i ⊆ ρ and r 6= rj 6= s, so we get (inr (E), ins (F )) ∈ ρ1 = h∼Dj−1 i and inr (E)/h∼Dj−1 i = ins (F )/h∼Dj−1 i, which proves the injectivity. Closedness of ψ : Let inr (E)/h∼Dj−1 i, ins (F )/h∼Dj−1 i ∈ JDj−1 K such that ψ(inr (E)/h∼Dj i) ⊕ ψ(ins (F )/h∼Dj i) exists. Then there exist t ∈ Rj , G, H ∈ Pcofin fin (t) with G ∩ H = Ø, (inr (E), int (G)) ∈ h∼Dj i and (ins (F ), int (H)) ∈ h∼Dj i. The sum τt (G) ⊕ τt (H) exists because τt is a homomorphism. Also, ψ(τt (G)) = int (G)/h∼Dj i = inr (E)/h∼Dj i = ψ(inr (E)/h∼Dj−1 i) and ψ(τt (H)) = int (H)/h∼Dj i = ins (F )/h∼Dj i = ψ(ins (F )/h∼Dj−1 i), and because of the injectivity of ψ we get τt (G) = inr (E)/h∼Dj−1 i and τt (H) = ins (F )/h∼Dj−1 i, and therefore ψ is closed. This proves, that ψ and φj = ψ ◦ φj−1 are isomorphisms. Dj is a diagram : Let a ∈ r ∈ Rj , b ∈ s ∈ Rj with a 6= b. Then inr ({a})/h∼Dj i = φj (inr ({a}/h∼D i)) 6= φj (ins ({b})/h∼D i) = ins ({b})/h∼Dj i, so (C1) is satisfied for the hypergraph Dj . Let r ∈ Rj . Then r = atoms(B) for a block B ≤ JDK. B is generated by atoms(B) and φj (B) is a block of JDj K, so with Theorem 2.3 we get inr (Pcofin fin (r))/h∼Dj i = φj (B), which proves condition (C3). For a ∈ r ∈ Rj the element inr ({a})/h∼D i is an atom of inr (Pcofin fin (r))/h∼D i, so cofin inr ({a})/h∼Dj i is an atom of inr (Pfin (r))/h∼Dj i because of the isomorphism φj . With Lemma 3.5, Dj is a diagram. So DT := (P, R ∪ T ) is a diagram, and the map φT : JDK → JDT K, inr (E)/h∼D i 7→ inr (E)/h∼DT i

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

439

is an isomorphism for all finite subsets T ⊆ Rc . Now we prove that φ : JDK → JComp(D)K is an isomorphism. φ is compatible with ⊕, ′ and 0 because of Rj ⊆ Rc and ∼D ⊆∼Comp(D) . Surjectivity of φ : Let x ∈ JComp(D)K. Then there exist r ∈ Rc , E ∈ Pcofin fin (r) with inr (E)/h∼Comp(D) i = x. For T := {r} there exists an element y = ins (F )/h∼D i ∈ JDK with φT (y) = inr (E)/h∼DT i, because φT is surjective. Therefore ins (F )/h∼DT i = φT (y) = inr (E)/h∼DT i and φ(y) = ins (F )/h∼Comp(D) i = inr (E)/h∼Comp(D) i = x, which proves the surjectivity. Injectivity of φ : Let inr (E)/h∼D i, ins (F )/h∼D i ∈ JDK with φ(inr (E)/h∼D i) = φ(ins (F )/h∼D i). Then (inr (E), ins (F )) ∈ h∼Comp(D) i, and because of Lemma 3.8 there is a finite set T ⊆ Rc with (inr (E), ins (F )) ∈ h∼DT i, and because of the injectivity of φT we get inr (E)/h∼D i = ins (F )/h∼D i, which proves the injectivity of φ. Closedness of φ : This proof is analogous to the proof of the injecivity. Therefore φ is an isomorphism. Comp(D) is a diagram : This proof is the same as the proof for Dj (see above). Completeness of Comp(D) : Now assume atoms(B) ⊆ P for each block B ≤ JDK. Let B be a block of JComp(D)K. Then C := φ−1 (B) is a block of JDK and C is generated by r := atoms(C) ∈ Rc , so inr (Pcofin fin (r))/h∼Comp(D) i = B and therefore Comp(D) is complete.  For a diagram D in which each block is generated by its atoms this theorem states that we can compute the completion without changing the interpretation. The completion is again a diagram, and the interpretation of the completion is isomorphic to the interpretation of D. If atoms(B) ⊆ P for each block B ≤ JDK, then every block of Comp(D) is induced by a line r ∈ Rc . Corollary 3.19. Let D be a diagram such that each block of JDK is generated by its atoms. Then Comp(D) is an OMA-diagram iff D is an OMA-diagram. If these diagrams are OMA-diagrams then Comp(D) is a complete diagram with JDK ∼ = JComp(D)K and the lines of Comp(D) are exactly the cliques of D. Proof. See Theorems 3.11 and 3.18 and Corollary 3.17.



440

R. Holzer

Algebra univers.

Definition 3.20. Let A be a nontrivial OMA (|A| > 1) such that each block of A is generated by its atoms. Define Diag(A) := (P, R) with P = atoms(A) and R = {atoms(B) | B block of A}. S Note that for Diag(A) = (P, R) we get P = R because of Theorem 2.5. We have Ø 6∈ R because the Boolean subalgebra {0, 1} is contained in a block which is generated by its atoms. Therefore Diag(A) is a hypergraph. Lemma 3.21. Let D = (P, R) be a hypergraph in which each line is finite. Let E ⊆ r ∈ R and F ⊆ s ∈ R. Let t ∈ R such that t is the disjoint union of E and s \ F . Then (inr (E), ins (F )) ∈ h∼D i. cofin Proof. Because t is finite we get E ∈ Pcofin fin (t) and s \ F ∈ Pfin (t) and therefore ′ ′ ins (F ) = (ins (s \ F )) h∼D i(int (s \ F )) = int (E)h∼D i inr (E). 

In the following theorem we use this lemma to prove that every nontrivial OMA in which each block is finite is induced by a complete OMA-diagram. Theorem 3.22. Let A be an nontrivial OMA in which each block is finite. Then D := (P, R) := Diag(A) is a complete OMA-diagram with A ∼ = JDK. Proof. Every line r ∈ R is finite because of the finiteness of the blocks. Let ` cofin ψ: Pfin (r) → A, r∈R

inr (E) 7→ ⊕E,

for E ⊆ r ∈ R. Then ψ is a well defined homomorphism because of Theorem 2.3. For r ∈ R the restriction τr := ψ|inr (Pcofin : inr (Pcofin fin (r)) → hri fin (r)) is an isomorphism because of Theorem 2.3. For (inr ({a}), ins ({a})) ∈∼D we have ψ(inr ({a})) = a = ψ(ins ({a})) so we get ∼D ⊆ ker(ψ) and therefore h∼D i ⊆ ker(ψ). Let φ : JDK → A be the induced homomorphism with φ(inr (E)/h∼D i) = ψ(inr (E)) for E ⊆ r ∈ R. Now we prove e ≤ φ(inr (E)/h∼D i) in A for all e ∈ E ⊆ r ∈ R. For e ∈ E we have inr ({e}) ≤ inr (E) in the Boolean OMA inr (Pcofin fin (r)), and because of the isomorphism τr we get e = τr (inr ({e})) ≤ τr (inr (E)) = φ(inr (E)/h∼D i). Surjectivity of φ : Let a ∈ A. Then a is in a block B ≤ A, so a is generated by atoms(B) =: r and with Theorem 2.3 we get a ∈ φ(JrK). Therefore φ is surjective. Injectivity of φ : Let inr (E)/h∼D i and ins (F )/h∼D i ∈ JDK with φ(inr (E)/h∼D i) = φ(ins (F )/h∼D i).

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

441

Let e ∈ E and g ∈ s \ F . Then g ≤ φ(ins (s \ F )/h∼D i) = φ(ins (F )/h∼D i)′ , so we get the existence of φ(ins (F )/h∼D i) ⊕ g = φ(inr (E)/h∼D i) ⊕ g = φ(inr (E \ {e})/h∼D i ⊕ inr ({e})/h∼D i) ⊕ g = (φ(inr (E \ {e})/h∼D i) ⊕ e) ⊕ g, and with axiom (A5) we get the existence of e ⊕ g. With Theorem 2.3 the set E ∪ (s \ F ) generates a Boolean OMA which is contained in a block B of A. Let t := atoms(B) ∈ R. Each element a ∈ E ∪ (s \ F ) ⊆ P = atoms(A) is an atom of B. Therefore E ∪ (s \ F ) ⊆ atoms(B) = t. The union E ∪ (s \ F ) is disjoint because of the existence of e ⊕ g for all e ∈ E and g ∈ s \ F . We have

⊕(E ∪ (s \ F )) =⊕E ⊕ ⊕(s \ F ) = φ(int (E)/h∼D i) ⊕ ⊕(s \ F ) = φ(inr (E)/h∼D i) ⊕ ⊕(s \ F ) = φ(ins (F )/h∼D i) ⊕ ⊕(s \ F ) = ⊕s = 1. Therefore E ∪˙ (s \ F ) = atoms(B) = t. With Lemma 3.21 we get inr (E)/h∼D i = ins (F )/h∼D i, which proves the injectivity. Closedness of φ : Let E ⊆ r ∈ R and F ⊆ s ∈ R, such that φ(inr (E)/h∼D i) ⊕ φ(ins (F )/h∼D i) exists. With Theorem 2.3 the set H := {φ(inr (E)/h∼D i), φ(ins (F )/h∼D i)} generates a Boolean subalgebra of A which is contained in a block B ≤ A. Let t := atoms(B) ∈ R. The function τt is surjective, so there exist E2 , F2 ⊆ t with τt (int (E2 )) = φ(inr (E)/h∼D i) and τt (int (F2 )) = φ(ins (F )/h∼D i). The function τt is closed, so we get the existence of int (E2 ) ⊕ int (F2 ) and because of the homomorphism nath∼D i we get the existence of int (E2 )/h∼D i ⊕ int (F2 )/h∼D i. We have φ(int (E2 )/h∼D i) = τt (int (E2 )) = φ(inr (E)/h∼D i) and φ(int (F2 )/h∼D i) = τt (int (F2 )) = φ(ins (F )/h∼D i), and because of the injectivity of φ we get int (E2 )/h∼D i = inr (E)/h∼D i and int (F2 )/h∼D i = ins (F )/h∼D i, so φ is closed. Therefore φ is an isomorphism. D is a diagram : For a ∈ r ∈ R and b ∈ s ∈ R with a 6= b we get φ(inr ({a})/h∼D i) = a 6= b = φ(ins ({b})/h∼D i),

442

R. Holzer

Algebra univers.

so inr ({a})/h∼D i = 6 ins ({b})/h∼D i which proves (C1). For r ∈ R the function nath∼D i ◦ inr = φ−1 ◦ τr ◦ inr is closed and injective, so (C2) holds. Let r ∈ R and B ≤ A be the block generated by r = atoms(B). Then φ−1 (B) = JrK is a block of JDK, which proves (C3). Completeness of D : Each block B ≤ JDK is induced by the line atoms(φ(B)) =: r ∈ R.  Corollary 3.23. The mappings Diag and J · K are bijective functions (up to isomorphy) between the class of all nontrivial OMAs with finite blocks and all complete OMA-diagrams with finite lines. For every nontrivial OMA A with finite blocks JDiag(A)K ∼ = A. For every complete OMA-diagram D with finite lines we have Diag(JDK) ∼ = D. Proof. JDiag(A)K ∼ = A was proved in Theorem 3.22, and Diag(JDK) = (atoms(JDK), {atoms(B) | B block of JDK}) ∼ = (P, R) = D follows from Theorem 3.11 and the completeness of D.



So every nontrivial OMA A in which each block is finite is induced by a complete OMA-diagram Diag(A) = (atoms(A), {atoms(B) | B block of A}) with finite lines. For every complete OMA-diagram D with finite lines each block of JDK is finite because the block is induced by a line. For complete diagrams D1 and D2 with finite lines with JD1 K ∼ = JD2 K we have D1 ∼ = D2 , = Diag(JD2 K) ∼ = Diag(JD1 K) ∼ and for two OMAs A1 and A2 in which each block is finite with Diag(A1 ) ∼ = Diag(A2 ) we have A1 ∼ = JDiag(A1 )K ∼ = JDiag(A2 )K ∼ = A2 . So these operators are bijections between the isomorphy classes of all complete OMA-diagrams with finite lines and the isomorphy classes of all nontrivial OMAs in which each block is finite. Lemma 3.24. Let D = (P, R) be a hypergraph in which each line is finite. Let ˙ ˙ ρ := {(inr (E), ins (F )) | there exist t, u ∈ R with t = E ∪(s\F ) and u = F ∪(r\E)}. Then ∼D ⊆ ρ ⊆ h∼D i, and the relation ρ is reflexive, symmetrical and compatible ` with ′ in the partial algebra C := r∈R Pcofin fin (r).

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

443

Proof. For (inr ({a}), ins ({a})) ∈∼D we have (inr ({a}), ins ({a})) ∈ ρ with t := s and u := r. So we have ∼D ⊆ ρ. Because of Lemma 3.21, ρ is a subset of h∼D i. Reflexivity of ρ : For r ∈ R and E ∈ Pcofin fin (r) take t := r =: u, so that we have (inr (E), inr (E)) ∈ ρ. Symmetry of ρ : For (inr (E), ins (F )) ∈ ρ we have the existence of t, u ∈ R with t = E ∪˙ (s \ F ) and u = F ∪˙ (r \ E), so (ins (F ), inr (E)) ∈ ρ. Compatibility with ′ : Let (inr (E), ins (F )) ∈ ρ. Then there exist t, u ∈ R with t = E ∪˙ (s \ F ) and u = F ∪˙ (r \ E). So (inr (E)′ , ins (F )′ ) = (inr (r \ E), ins (s \ F )) ∈ ρ, and this proves that ρ is compatible with ′ .  The following theorem shows, that the congruence relation h∼D i can easily be computed if the diagram satisfies some conditions. Later it will be shown that these conditions allways hold for complete OMA-diagrams with finite lines. Theorem 3.25. Let D = (P, R) be a diagram in which each line is finite such that the following two conditions hold: (1) For every r, s, t ∈ R there exists a line u ∈ R with (r ∩ s) ∪ (s ∩ t) ∪ (r ∩ t) ⊆ u. (2) For every r, s, t ∈ R with s ⊆ r ∪ t there exists a line u ∈ R with (r \ s) ∪ (t \ s) ∪ (r ∩ t) ⊆ u. Let ρ := {(inr (E), ins (F )) | there exist t, u ∈ R with t = E ∪˙ (s \ F ) and u = F ∪˙ (r \ E)}. Then ρ = h∼D i. Proof. With Lemma 3.24 we have ∼D ⊆ ρ ⊆ h∼D i, and ρ is reflexive, symmetrical and compatible with ′ . Transitivity of ρ : Let (inr (E), ins (F )) ∈ ρ and (ins (F ), int (G)) ∈ ρ. Then we get ˙ ˙ the existence of v, q ∈ R with v = F ∪(r\E) and q = G∪(s\F ). So we have s ⊆ q∪v, and because of condition (2) we get a line w ∈ R with (q\s)∪(v\s)∪(q∩v) ⊆ w. Now we show r\E ⊆ w and G ⊆ w: Let a ∈ r\E. If a 6∈ s then a ∈ v\s ⊆ w, and if a ∈ s then a ∈ s\F because of (r \E)∩F = Ø, so we have a ∈ (s\F )∩(r \E) ⊆ q ∩v ⊆ w. Therefore r \ E ⊆ w. Let a ∈ G. If a 6∈ s then a ∈ q \ s ⊆ w, and if a ∈ s then a ∈ F because of G ∩ (s \ F ) = Ø, so we have a ∈ G ∩ F ⊆ q ∩ v ⊆ w. Therefore G ⊆ w. Because of ρ ⊆ h∼D i we have (inr (E), int (G)) ∈ h∼D i because h∼D i is

444

R. Holzer

Algebra univers.

transitive, so we get inw (G)/h∼D i = int (G)/h∼D i = inr (E)/h∼D i = (inr (r \ E)/h∼D i)′ = (inw (r \ E)/h∼D i)′ = inw (w \ (r \ E))/h∼D i, and because of condition (C2) we have G = w \ (r \ E), so w = G ∪˙ (r \ E). Analogously we get a line u = E ∪˙ (t \ G) ∈ R, and therefore (inr (E), int (G)) ∈ ρ. This proves the transitivity. Compatibility with ⊕ : Let (inr1 (E1 ), ins1 (F1 )) ∈ ρ and (inr2 (E2 ), ins2 (F2 )) ∈ ρ such that inr1 (E1 ) ⊕ inr2 (E2 ) and ins1 (F1 ) ⊕ ins2 (F2 ) exist. Then we have r1 = r2 (or E1 = Ø or E2 = Ø, but in that case we can redefine r1 or r2 to get the same situation because inr1 (Ø) = 0 = inr2 (Ø)) and s1 = s2 . Because of the existence of the sums we have E1 ∩ E 2 = Ø = F 1 ∩ F 2 . From the definition of ρ we get the existence of elements t, u ∈ R with t = E1 ∪˙ (s1 \ F1 ) and u = E2 ∪˙ (s2 \ F2 ) = E2 ∪˙ (s1 \ F2 ). With condition 1 we get a line v ∈ R with E1 ∪ E2 ∪ (s1 \ (F1 ∪ F2 )) ⊆ (r1 ∩ t) ∪ (r1 ∩ u) ∪ (t ∩ u) ⊆ v. Because of (inr1 (E1 ), ins1 (F1 )) ∈ ρ ⊆ h∼D i and (inr2 (E2 ), ins2 (F2 )) ∈ ρ ⊆ h∼D i we have inv (s1 \ (F1 ⊕ F2 ))/h∼D i = ins1 (s1 \ (F1 ⊕ F2 ))/h∼D i = (ins1 (F1 ⊕ F2 )/h∼D i)′ = (inr1 (E1 ⊕ E2 )/h∼D i)′ = (inv (E1 ⊕ E2 )/h∼D i)′ = inv (v \ (E1 ⊕ E2 ))/h∼D i, and because of condition (C2) we get s1 \ (F1 ⊕ F2 ) = v \ (E1 ⊕ E2 ), and therefore v = (E1 ⊕ E2 ) ∪˙ (s1 \ (F1 ⊕ F2 )). Analogously we get a line w = (F1 ⊕ F2 ) ∪˙ (r1 \ (E1 ⊕ E2 )) ∈ R, so (inr1 (E1 ) ⊕ inr2 (E2 ), ins1 (F1 ) ⊕ ins2 (F2 )) ∈ ρ. Therefore ρ is a congruence relation with ∼D ⊆ ρ ⊆ h∼D i, so h∼D i = ρ. 

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

445

In this theorem condition (1) says, that for every triangle of D there exists a line which contains the corners of the triangle, where the corner of two lines is defined as their intersection. Condition (2) says, that for every line which is covered by two other lines there exists a line containing the rest of the other lines and their intersection. With these two conditions we can directly see the congruence relation h∼D i in the diagram: Two elements inr (E) and ins (F ) are equivalent iff E ∪˙ (s \ F ) and F ∪˙ (r \ E) are lines of the diagram. The following lemma gives sufficient conditions for the property that a nontrivial diagram is an OMA-diagram. Lemma 3.26. Let D = (P, R) be a nontrivial diagram such that the following three conditions hold: (1) For every r, s, t ∈ R there exists a line u ∈ R with (r ∩ s) ∪ (s ∩ t) ∪ (r ∩ t) ⊆ u. cofin (2) For every r, s ∈ R and E ∈ Pcofin fin (r) and F ∈ Pfin (s) with (inr (E), ins (F )) ∈ h∼D i there exists t ∈ R with E ∪ (s \ F ) ⊆ t. (3) For every r, s ∈ R and E ∈ Pcofin fin (r) with E ⊆ s 6= r the set E is finite. Then D is an OMA-diagram. Proof. The axioms (A0)–(A4), (A7) and (A9) hold because of Theorem 3.3. (A5): Let x, y, z ∈ JDK such that (x ⊕ y) ⊕ z exists. Then there exist r, s ∈ R and cofin G, H ∈ Pcofin fin (r) and E, F ∈ Pfin (s) with x = inr (G)/h∼D i, y = inr (H)/h∼D i, z = ins (E)/h∼D i and x ⊕ y = ins (F )/h∼D i such that G ∩ H = Ø = F ∩ E. Then we have (inr (G ∪ H), ins (F )) ∈ h∼D i, and with condition (2) we get a line t ∈ R with G ∪ H ∪ (s \ F ) ⊆ t, so E, G, H ⊆ t because of F ∩ E = Ø. With condition (3) we get x = int (G)/h∼D i, y = int (H)/h∼D i, z = int (E)/h∼D i. Because of condition (C2) and the existence of (x ⊕ y) ⊕ z = (int (G)/h∼D i ⊕ int (H)/h∼D i) ⊕ int (E)/h∼D i, we get the existence of (G ⊕ H) ⊕ E in Pcofin fin (t) and therefore G ⊕ (H ⊕ E) exists, and (G ⊕ H) ⊕ E = G ⊕ (H ⊕ E), because Pcofin fin (t) is an OMA. So (x ⊕ y) ⊕ z = (int (G)/h∼D i ⊕ int (H)/h∼D i) ⊕ int (E)/h∼D i = int (G ⊕ H ⊕ E)/h∼D i = x ⊕ (y ⊕ z) which proves (A5). (A8): Let x, y, z ∈ JDK such that x ⊕ y, y ⊕ z and x ⊕ z exist. cofin Then there exist r, s, t ∈ R and Ex , Ey ∈ Pcofin fin (r) and Fy , Fz ∈ Pfin (s) and

446

R. Holzer

Algebra univers.

Gx , Gz ∈ Pcofin fin (t) with inr (Ex )/h∼D i = x = int (Gx )/h∼D i, inr (Ey )/h∼D i = y = ins (Fy )/h∼D i, ins (Fz )/h∼D i = z = int (Gz )/h∼D i, such that Ø = Ex ∩Ey = Fy ∩Fz = Gx ∩Gz . Because of (inr (Ex ), int (Gx )) ∈ h∼D i, condition (2) implies the existence of u ∈ R with Ex ∪ (t \ Gx ) ⊆ u. Because of Gx ∩Gz = Ø, we have Ex , Gz ⊆ u. Analogously we get v, w ∈ R with Fy , Gz ⊆ v and Ex , Fy ⊆ w. Condition (1) implies the existence of a line q ∈ R with Ex ∪ Fy ∪ Gz ⊆ (u ∩ w) ∪ (v ∩ w) ∪ (u ∩ v) ⊆ q. With condition (3) we get x = inq (Ex )/h∼D i, y = inq (Fy )/h∼D i, and z = inq (Gz )/h∼D i. Because of condition (C2), Ex ⊕ Fy and cofin Fy ⊕ Gz and Ex ⊕ Gz exist in Pcofin fin (q), so Ex ⊕ (Fy ⊕ Gz ) exists because Pfin (q) satisfies axiom (A8). So we have the existence of inq (Ex )/h∼D i ⊕ (inq (Fy )/h∼D i ⊕ inq (Gz )/h∼D i) = x ⊕ (y ⊕ z), which proves (A8). Axiom (A6) follows from the other axioms, so JDK is an OMA.



In the following characterisation theorem we use Theorem 3.25 and Lemma 3.26 to get some conditions which are equivalent to the property that a complete diagram with finite lines is an OMA-diagram. Theorem 3.27. Let D = (P, R) be a nontrivial complete diagram in which each line is finite. The following conditions are equivalent: (1) D is an OMA-diagram. (2) (a) For every r, s, t ∈ R there exists a line u ∈ R with (r ∩ s) ∪ (s ∩ t) ∪ (r ∩ t) ⊆ u, and (b) for every r, s, t ∈ R with s ⊆ r ∪ t there exists a line u ∈ R with (r \ s) ∪ (t \ s) ∪ (r ∩ t) ⊆ u. (3) (a) For every r, s, t ∈ R there exists a line u ∈ R with (r ∩ s) ∪ (s ∩ t) ∪ (r ∩ t) ⊆ u, and cofin (b) for every r, s ∈ R and E ∈ Pcofin fin (r) and F ∈ Pfin (s) with (inr (E), ins (F )) ∈ h∼D i there exists t ∈ R with E ∪ (s \ F ) ⊆ t. Proof. (1) ⇒ (2): With Corollary 3.12 each block of JDK is generated by its atoms. Let r, s, t ∈ R and E := (r ∩ s) ∪ (s ∩ t) ∪ (r ∩ t). For all a, b ∈ E there exists v ∈ {r, s, t} ⊆ R with a, b ∈ v. So because of Theorem 3.15, E generates a Boolean subalgebra, which is contained in a block. D is complete, so there exists a line u ∈ R with E ⊆ JuK and therefore E ⊆ u because of Theorem 3.13, which proves condition (2a).

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

447

Now let r, s, t ∈ R with s ⊆ r ∪ t. For a ∈ r \ s and b ∈ t \ s we have a ∈ r \ (s \ t) and b 6∈ s ∩ t so ⊕(s ∩ t) ⊕ b exists, s \ t ⊆ r, and

⊕(s ∩ t) ⊕ b = (⊕(s \ t))′ ⊕ b = ⊕(r \ (s \ t)) ⊕ b = (⊕(r \ ({a} ∪ (s \ t))) ⊕ a) ⊕ b. With axiom (A5) we get the existence of a ⊕ b. Define E := (r \ s) ∪ (t \ s) ∪ (r ∩ t). Then for all a, b ∈ E with a 6= b the sum a ⊕ b exists, and therefore E generates a Boolean subalgebra which is contained in a block. D is complete, so there exists a line u ∈ R with E ⊆ u, which proves condition (2b). (2) ⇒ (3): See Theorem 3.25. (3) ⇒ (1): See Lemma 3.26.  The implication (1) ⇒ (2) of Theorem 3.27 may not hold if D is contains infinite lines. This will be proved in the next section; see Example 1. The characterisation of the congruence relation in Theorem 3.25 also holds for complete OMA-diagrams with finite lines: Corollary 3.28. Let D = (P, R) be a complete OMA-diagram in which each line cofin is finite, r, s ∈ R and E ∈ Pcofin fin (r) and F ∈ Pfin (s). Then (inr (E), ins (F )) ∈ h∼D i iff E ∪˙ (s \ F ) ∈ R and F ∪˙ (r \ E) ∈ R. Proof. See Theorems 3.25 and 3.27.



In Theorem 3.31 we will give a characterisation of complete OMA-diagrams with a weaker precondition than in Theorem 3.27. First we need the following lemma: Lemma 3.29. Let D = (P, R) be a hypergraph in which each clique is a line. Then condition (2a) of Theorem 3.27 is satisfied. Proof. Let r, s, t ∈ R. In E := (r ∩ s) ∪ (s ∩ t) ∪ (r ∩ t), each pair of points is connected by a line (for example a ∈ r ∩ s is connected to b ∈ s ∩ t by the line s), so E is contained in a clique, and there exists a line u ∈ R with E ⊆ u.  Note that the property that each clique is a line is equivalent to the property that each clique is contained in a line: a clique can not be a proper subset of a line because of the maximality. For nontrivial finite hypergraphs the two conditions of this lemma are equivalent: Lemma 3.30. Let D = (P, R) be a nontrivial finite hypergraph. Each clique is a line iff condition (2a) of Theorem 3.27 is satisfied.

448

R. Holzer

Algebra univers.

Proof. Assume that condition (2a) holds and that there exists a clique which is not a line. Because of the finiteness of P there exists a minimal subset E ⊆ P , in which each pair of points is connected by a line, but E is not contained in a line. We have |E| > 1 because of P 6= Ø, so there exist a, b ∈ E with a 6= b. Because of the minimality of E, the set E \ {a} is contained in a line r ∈ R and E \ {b} is contained in a line s ∈ R. The set {a, b} is also contained in a line t ∈ R because a is connected to b. With condition (2a) we get a line u ∈ R with E = (E \{a, b})∪{b}∪{a} ⊆ (r∩s)∪(r∩t)∪(s∩t) ⊆ u, which is a contradiction.  For infinite hypergraphs this lemma may not hold. In Section 4 we show that there exists an OMA-diagram with finite lines, such condition (2a) of Theorem 3.27 is satisfied, but there exists a clique which is not contained in a line (see Example 4). Theorem 3.31. Let D = (P, R) be a diagram in which each line is finite such that every block of JDK is generated by its atoms. The following conditions are equivalent: (1) D is a complete OMA-diagram. (2) (a) Every clique is a line, and (b) for every r, s, t ∈ R with s ⊆ r ∪ t there exists a line u ∈ R with (r \ s) ∪ (t \ s) ∪ (r ∩ t) ⊆ u. (3) (a) Every clique is a line, and cofin (b) for every r, s ∈ R and E ∈ Pcofin fin (r) and F ∈ Pfin (s) with (inr (E), ins (F )) ∈ h∼D i there exists t ∈ R with E ∪ (s \ F ) ⊆ t. Proof. (1) ⇒ (2): See Theorem 3.16 and Theorem 3.27. (2) ⇒ (3): See Lemma 3.29 and Theorem 3.25. (3) ⇒ (1): We have R 6= Ø because otherwise the empty set would be a clique which is not a line. Lemma 3.29 and Lemma 3.26 imply that D is an OMA-diagram. Let B be a block of JDK. With Theorem 3.16 B is induced by a clique E ⊆ P , so with condition (3), E is a line: E = r ∈ R. We get B = JrK, and D is complete.  This theorem characterises complete OMA-diagrams under the assumption that each block of JDK for a diagram D with finite lines is generated by its atoms: D is a complete OMA-diagram iff every clique is a line and for every line which is covered by two other lines there exists a line containing the rest of the other lines and their intersection. In the following characterisation theorem the assumption that D is a diagram is not needed, so the theorem holds for every hypergraph with finite lines, such that each block is generated by its atoms Theorem 3.32. Let D = (P, R) be a hypergraph in which each line is finite such that each block of JDK is generated by its atoms. D is a complete OMA-diagram iff the following conditions are satisfied:

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

449

(1) |r \ s| > 1 for all r, s ∈ R with r 6= s, (2) the relation ρ := {(inr (E), ins (F )) | there exist t, u ∈ R with t = E ∪˙ (s \ F ) and u = F ∪˙ (r \ E)} is transitive and compatible with ⊕ (in the coproduct ` cofin r∈R Pfin (r)), (3) every clique is a line, (4) for every r, s, t ∈ R with s ⊆ r ∪ t there exists a line u ∈ R with (r \ s) ∪ (t \ s) ∪ (r ∩ t) ⊆ u. Proof. ⇒: If D is a complete OMA-diagram then the conditions (1)–(4) follow from Lemma 3.4, Theorem 3.31 and Theorem 3.25. ⇐: Let the four conditions be satisfied. With condition (2) and Lemma 3.24 we have ρ = h∼D i. Now we use Theorem 3.7 to show that D is a diagram. Let ˙ (inr ({a}), ins (E)) ∈ h∼D i = ρ. Then there exists a line u ∈ R with u = {a} ∪(s\E), so with condition (1) we get u = s. Therefore E = {a}. (C2): Let (inr (E), inr (F )) ∈ h∼D i = ρ. Then by the definition of ρ we have E ∩ (r \ F ) = Ø = F ∩ (r \ E), so E ⊆ F and F ⊆ E. Therefore nath∼D i ◦ inr is injective. Let E, F ⊆ r ∈ R such that inr (E)/h∼D i ⊕ inr (F )/h∼D i exists. Then there exist G, H ⊆ s ∈ R with (inr (E), ins (G)) ∈ h∼D i = ρ, (inr (F ), ins (H)) ∈ h∼D i = ρ, G ∩ H = Ø. Then there exist t, u ∈ R with t = E ∪˙ (s \ G) and u = F ∪˙ (s \ H). With condition (3) and Lemma 3.29 we get the existence of v ∈ R with (s ∩ t) ∪ (t ∩ u) ∪ (s ∩ u) ⊆ v. We have s = G ∪ H ∪ (s \ (G ∪ H)) ⊆ (u ∩ s) ∪ (t ∩ s) ∪ (u ∩ t) ⊆ v, so with condition (1) we get s = v. We have E ∩ F ⊆ t ∩ u ⊆ v = s. The union E ∪˙ (s \ G) is disjoint, so we get (E ∩ F ) ∩ (s \ G) = Ø and analogously (E ∩ F ) ∩ (s \ H) = Ø. Therefore E ∩ F = (E ∩ F ) ∩ s = (E ∩ F ) ∩ ((s \ G) ∪ (s \ H)) = Ø and nath∼D i ◦ inr is closed. So D is a diagram because of Theorem 3.7. D is a complete OMA-diagram because of Theorem 3.31.  If D is a hypergraph with finite lines and each block of JDK is generated by its atoms, the four conditions of this theorem are useful to check whether D is a complete OMA-diagram. If D is finite then all lines of D are finite and each block is generated by its atoms, so for finite diagrams it can be easily checked whether D is a complete OMA-diagram. We need not compute the interpretation JDK, we just have to check the conditions of Theorem 3.32.

4. Examples The first example is a counterexample to Theorem 3.27 with infinite lines.

450

R. Holzer

Algebra univers.

r A1

t

A4

A2

s

A3

Figure 4. Hypergraph in Example 1. Example 1. Let R = {r, s, t} with r = A1 ∪ A2 , s = A2 ∪ A3 , t = A3 ∪ A4 , A1 := N × {1}, A2 := N × {2}, A3 := N × {3}, A4 := N × {4}. S Let P = R and D = (P, R) (see Figure 4). Then D is a complete OMA-diagram (see [Ho01]), but condition (2b) of Theorem 3.27 is not satisfied. The next example shows that there exist OMAs which are not induced by diagrams, so Theorem 3.22 does not hold for OMAs with infinite blocks. We also show that there exist two different OMAs (with infinite blocks) for which the operator Diag of Definition 3.20 produces isomorphic diagrams. S Example 2. Let D = (P, R) with P = R and R = {r, s} with r = N ∪ {−1, −2},

s = N ∪ {−3, −4}. ` This hypergraph is shown in Figure 5. Let C := r∈R Pcofin fin (r) and

σ := {(inr (E), ins (E)) | E ∈ Pcofin fin (N)}∪  (inr ({−1, −2} ∪ E), ins ({−3, −4} ∪ E)) E ∈ Pcofin fin (N) .

Then the congruence relation hσi generated by σ is the reflexive symmetrical closure of σ: hσi = ref (sym(σ)).

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

451

−4 −3 0

1

2 •

•

•

•

•

−1 −2 Figure 5. Hypergraph in Example 2.

Then D is an complete OMA-diagram, the partial algebra A := C/hσi is an OMA which is not induced by a diagram, and Diag(A) ∼ = Diag(JDK) and JDK ∼ = =D ∼ JDiag(A)K 6∼ = A. For a proof of these properties see [Ho01]. The following example shows that there exists a diagram D in which each block is generated by its atoms such that the atoms of a block B ≤ JDK are not contained in P . So Theorem 3.11 does not hold for diagrams which are not OMA-diagrams. This example also shows that there may exist blocks in the interpretation of a diagram which are not generated by its atoms. Example 3. Let M be a set with |M | > 3 and N := P(M ) \ {Ø, M }. Let D = (P, R) with P = {aTi | 1 ≤ i ≤ 4, T ∈ N }  1 ≤ i ≤ 6, T, U ∈ N, T ∩ U = Ø, T ∪ U 6= M ∪ bT,U i  1 ≤ i ≤ 4, T, U ∈ N, T ∩ U = Ø, T ∪ U = M ∪ bT,U i

with aTi = (i, T ) and bT,U = (i, T, U ), and i R = {rT | T ∈ N }

∪ {sT,U | T, U ∈ N, T ∩ U = Ø} ∪ {uT,U | T, U ∈ N, T ∩ U = Ø} ∪ {v T,U | T, U ∈ N, T ∩ U = Ø} ∪ {wT,U | T, U ∈ N, T ∩ U = Ø, T ∪ U 6= M }

452

R. Holzer

Algebra univers.

with rT = {aT1 , aT2 , aT3 , aT4 }, T,U uT,U = {aT3 , aT4 , bT,U 1 , b2 }, U T,U T,U v T,U = {aU 3 , a4 , b3 , b4 }, T,U T ∪U wT,U = {bT,U , aT2 ∪U }, 5 , b6 , a1 ( T,U T,U T,U T,U T,U {bT,U 1 , b2 , b3 , b4 , b5 , b6 }, T,U s = T,U T,U T,U {bT,U 1 , b2 , b3 , b4 },

if T ∪ U 6= M, if T ∪ U = M.

Then D is a diagram. Define xØ := 0, xM := 1 and xT := inrT ({aT1 , aT2 })/h∼D i for T ∈ N . Let B := {xT | T ⊆ M } ⊆ JDK. Then B is a block of JDK with B ∼ = P(M ). The atoms of B are not contained in P . If M is finite, then each block of JDK is finite, and therefore each block is generated by its atoms. So Theorem 3.11 does not hold for diagrams which are not OMA-diagrams. If M is infinite, then the block B is not generated by atoms(B). For a proof of these properties see [Ho01]. The following example shows that there exists an OMA-diagram with finite lines, such that condition (2a) of Theorem 3.27 is satisfied, but there exists a clique which is not contained in a line. Example 4. Let D = (P, R) with R = {rn | n ≥ 3},

rn = {a0 , a1 , a2 , . . . , an , bn , cn } for n ≥ 3,

S and an = (0, n) for n ∈ N and bn = (1, n) and cn = (2, n) for n ≥ 3 and P = R. Then D is an OMA-diagram; see [Ho01]. The set A = {an | n ∈ N} is a clique which is not contained in a line. Condition (2a) of Theorem 3.27 is satisfied. The diagram D is not complete because with Theorem 2.3 the set A = {Jan K | n ∈ N} generates an infinite Boolean subalgebra, but D contains only finite lines, so every block would be finite if D is complete. 5. Conclusion With the theorems of Section 3 we get an algorithm to check whether the interpretation of a finite hypergraph is a complete OMA-diagram: Input: finite hypergraph D = (P, R) Output: “yes” if D is a complete OMA-diagram, “no” otherwise Algorithm: If there exist r, s ∈ R with r 6= s and |r \ s| ≤ 1 then the algorithm ends with output “no”. If the relation ρ := {(inr (E), ins (F )) | there exist t, u ∈ R with t = E ∪˙ (s \ F ) and u = F ∪˙ (r \ E)} is not transitive or not compatible with ⊕ then output “no”. If there exists a triangle but no line containing the corners of

Vol. 57, 2007

Greechie diagrams of orthomodular partial algebras

453

the triangle then output “no”. If there exists a line s ∈ R which is covered by two other lines but there does not exist a line containing the rest of the two other lines and their intersection, then output “no”. Otherwise output “yes”. This algorithm has been implemented by the author in the program “omacheck”. The correctness of the algorithm follows from Theorem 3.32 and Lemma 3.30. References [Bg76] C. Berge, Graphs and Hypergraphs, North-Holland Publ. Co., Amsterdam-London, 1976. [Be85] L. Beran, Orthomodular Lattices. Algebraic Approach, D. Reidel Publ. Company, 1985. [B82] P. Burmeister, Partial algebras — survey of a unifying approach towards a two-valued model theory for partial algebras, Algebra Universalis 15 (1982), 306–358. [B93] P. Burmeister, Partial Algebras — An Introductory Survey, in: Algebras and Orders: Proceedings of the NATO Advanced Study Institute and S´ eminaire des Math´ ematiques, Montreal, Canada, G. Sabidussi and I. Rosenberg, eds., Kluwer Publ. Co., Dordrecht, 1993. [BM94] P. Burmeister and M. M¸ aczy´ nski, Orthomodular (partial) algebras and their representations, Demonstratio Math. 27 (1994), 701–722. [B98] P. Burmeister, Subdirect representations by epimorphisms in quasivarieties of partial algebras, Preprint No. 2010 of the Department of Mathematics of the Darmstadt University of Technology, 1998. [BM98] P. Burmeister and M. M¸ aczy´ nski, Quasi-rings and congruences in the theory of orthomodular algebras, Preprint No. 2014 of the Department of Mathematics of the Darmstadt University of Technology, 1998. [D84] M. Dichtl, Astroids and Pastings, Algebra Universalis 18 (1984), 380–385. [Go80] R. Godowski, Commutativity in orthomodular posets, Reports on Mathematical Physics 18 (1980), 347–351. [Ho01] R. Holzer, Greechie diagrams of orthomodular partial algebras, Preprint Nr. 2165, TU-Darmstadt, FB Mathematik, 2001. http://wwwbib.mathematik.tu-darmstadt.de/ Math-Net/Preprints/Listen/files/2165.ps.gz [K83] G. Kalmbach, Orthomodular Lattices, Academic Press, 1983. [MT73] M. M¸ aczy´ nski and T. Traczyk, A characterization of orthomodular partially ordered sets admitting a full set of states, Bull. Polon. Acad. Ser. Sci. Math. Astr. Phys. 21 (1973), 3–9. [Pu94] S. Pulmannov´ a, A remark on orthomodular partial algebras, Demonstratio Math. 27 (1994), 687–699. Richard Holzer University of Passau, Faculty of Informatics and Mathematics, Innstr. 43, 94032 Passau, Germany e-mail: [email protected]