We extend some theoretical results in the frame of concurrency theory, which were presented in [1]. In particular, we focus on partially ordered sets (posets) as models of nonsequential processes [2] and we apply the same construction as in [1] of a lattice of subsets of points of the poset via a closure operator defined on the basis of the concurrency relation, viewed as lack of causal dependence. The inspiring idea is related to works by C. A. Petri [6]. Petri proposed a theory of systems based on abstract models to represent the behaviour and the properties of concurrent and distributed systems, which takes into account the principles of the special relativity. A crucial difference between the standard physical theories and the framework in which Petri develops his own theory comes from the use of the continuum as the underlying model in physics. In the combinatorial model proposed by Petri, the usual notion of density of the continuum model is replaced by two properties strictly related and required for the posets modelling a discrete space-time: the so-called K-density and a weaker form called N-density. K-density is based on the idea that any maximal antichain (or cut ) in a poset and any maximal chain (or line) have a nonempty intersection. A line can be interpreted as a sequential subprocess, while a cut corresponds to a time instant and K-density requires that, at any time instant, any sequential subprocess must be in some state or changing its state. N-density can be viewed as a sort of local density and was introduced by Petri as an axiom for posets modelling nonsequential processes. Occurrence nets, a fundamental model of such processes, are indeed N-dense, whereas for example event structures [5] are in general not N-dense. In [1] we have considered as model of non sequential processes a class of locally finite posets and shown that the closed subsets, obtained via a closure operator defined on the basis of concurrency, correspond in general to subprocesses which result to be 'closed' with respect to the Petri net firing rule. Moreover, we have shown that if the poset is N-dense, then the lattice of closed subsets is orthomodular. Orthomodular lattices are families of partially overlapping Boolean algebras and have been studied as the algebraic model of quantum logic [7].
In this paper we generalize our previous results for combinatorial posets and we show that the N-density of the poset is a sufficient and necessary condition for the orthomodularity of the lattice of closed subsets.
In an orthomodular lattice, each element is associated to its orthocomplement. We show that under K-density, given a closed set, any line intersects the closed set or its orthocomplement. Starting from this result we define the characteristic map of the family of closed sets that cross the given line and show that this map is a two-valued state of the lattice of closed sets of the poset. The notion of two-valued state over orthomodular lattices is used in quantum logic, where the elements of the lattice are interpreted as propositions of a language, and the two-valued states on a lattice as consistent assignments of truth values to these propositions. This suggests to look at the closed sets as propositions in a logic language, where orthocomplementation corresponds to negation and any line induces a logical interpretation. Following the same idea, we propose to consider the dual relation between cuts and Boolean algebras, on the fact that any cut of a K-dense poset generates a Boolean subalgebra of the lattice.
Finally, we extend to combinatorial posets the relation between the K-density
of a poset and the algebraicity of the lattice of its closed sets, as given in [
In this section, we recall basic definitions and notations for partially ordered sets, lattices and orthomodular lattices, and closure operators.
A partially ordered set (poset for short) is a set P , together with a reflexive, anti-symmetric, and transitive relation ≤ ⊆ P × P . By < we denote the related strict partial order.
For x, y ∈ P , we write x l y if x < y and no z ∈ P satisfies x < z < y. Let •x = { y | y l x }, and x• = { y | x l y }. A poset P = (P, ≤) is combinatorial iff ≤ = (l)∗, where (l)∗ is the transitive and reflexive closure of l. A poset P = (P, ≤) is of finite degree iff ∀x ∈ P : |•x| ∈ N and |x•| ∈ N.
Given a partial order relation ≤ on a set P , we can derive the relations li = ≤ ∪ ≥, and co = (P × P ) \ li. Intuitively, in our framework x li y means that x and y are connected by a causal relation, and x co y means that x and y are causally independent. The relations li and co are symmetric but, in general, non transitive. Note that li is a reflexive relation, while co is irreflexive.
A clique of a binary relation is a set of pairwise related elements; a clique of co ∪ idP will be called antichain, or co-set, whereas a clique of li will be called chain or li-set. Maximal cliques of co ∪ idP and li are called, respectively, cuts and lines: cuts(P) = {c ⊆ P | c is a maximal clique of co ∪ idP }, lines(P) = { λ ⊆ P | λ is a maximal clique of li} Definition 1. P = (P, ≤) is K-dense ⇔ ∀c ∈ cuts(P), ∀λ ∈ lines(P) : c ∩ λ 6= ∅. Obviously, in general |c ∩ λ| ≤ 1.
In the following we are interested in a weaker form of density, called Ndensity, strictly related to K-density and which can be viewed as a sort of local density. Definition 2. P = (P, ≤) is N-dense ⇔ ∀ x, y, v, w ∈ P : (y < v and y < x and w < v and (y co w co x co v)) ⇒ ∃z ∈ P : (y < z < v and (w co z co x)). Definition 3. An orthocomplemented poset P = hP, ≤, 0, 1, (.)0i is a partially ordered set P = (P, ≤), equipped with a minimum and a maximum element, respectively denoted by 0 and 1, and with a map (.)0 : P → P , such that the following conditions are satisfied (where ∨ and ∧ denote, respectively, the least upper bound and the greatest lower bound with respect to ≤, when they exist): ∀x, y ∈ P , (i) (x0)0 = x, (ii) x ≤ y ⇒ y0 ≤ x0, (iii) x ∧ x0 = 0 and x ∨ x0 = 1. The map (.)0 : P → P is called an orthocomplementation in P. In an orthocomplemented poset, ∧ and ∨, when they exist, are not independent: in fact, the so-called De Morgan laws hold: (x ∨ y)0 = x0 ∧ y0, (x ∧ y)0 = x0 ∨ y0. In the following, we will sometimes use meet and join to denote, respectively, ∧ and ∨.
Two elements x, y ∈ P are orthogonal, denoted x ⊥ y, iff x ≤ y0. Definition 4. A two-valued state on a poset P is a mapping s : P 7→ {0, 1} such that (i) s(1) = 1, (ii) if {ai : i ∈ N} is a sequence of mutually orthogonal elements in P, then s(Wi∈N ai) = Pi∈N s(ai).
A poset P is called orthocomplete when it is orthocomplemented and every pairwise orthogonal countable subset of P has a least upper bound.
A lattice L = (L, ≤) is a poset in which, for any pair of elements, meet and join exist. A lattice L is complete when the meet and the join of any subset of L exist.
Definition 5. An orthomodular poset P = hP, ≤, 0, 1, (.)0i is an orthocomplete poset which satisfies the condition: x ≤ y ⇒ y = x ∨ (y ∧ x0), which is usually referred to as the orthomodular law.
Let X be a set, and α ⊆ X × X be a symmetric relation. Given A ⊆ X
we can define an operator (.)⊥ on the powerset of X: A⊥ = {x ∈ X | ∀y ∈
A : (x, y) ∈ α}. By applying twice the operator (.)⊥, we get a new operator
C(.) = (.)⊥⊥ = ((.)⊥)⊥. The map C on the powerset of X is a closure operator
on X; i.e.: for all A, B ⊆ X, (i) A ⊆ C(A); (ii) A ⊆ B ⇒ C(A) ⊆ C(B); (iii)
C(C(A)) = C(A) [
When α is also irreflexive, the operator (.)⊥, applied to elements of L(X),
is an orthocomplementation; the structure L(X) = hL(X), ⊆, ∅, X, (.)⊥i then
forms an orthocomplemented complete lattice [
A complete lattice L is algebraic if, for each a ∈ L, a = W{k ∈ K(L) : k ≤ a},
where K(L) is the set of compact elements, and k ∈ L is compact if, for every
subset S in L, k ≤ W S ⇒ k ≤ W T , for some finite subset T of S, (see [
In this section we consider the closed sets induced by the concurrency relation in partially ordered sets by applying the construction recalled in the previous section. We study the resulting properties of closed sets, investigating in particular the relations with N-density and K-density of the poset.
Let P = (P, ≤) be a poset. We can define an operator on subsets of P , which corresponds to an orthocomplementation, since co is irreflexive, and by this operator we define closed sets.
Definition 6. Let S ⊆ P , then (i)
S⊥ = {x ∈ P | ∀y ∈ S : x co y} is the orthocomplement of S; (ii) if S = (S⊥)⊥, then S is a closed set of P = (P, ≤).
The set S⊥ contains the elements of P which are not in causal relation with any element of S. Obviously, S ∩ S⊥ = ∅ for any S ⊆ P , however in general S ∪ S⊥ 6= P . In the following, we sometimes denote (S⊥)⊥ by S⊥⊥. Note that: ∀c ∈ cuts(P), c⊥ = ∅ and c⊥⊥ = P .
We call L(P ) the collection of closed sets of P = (P, ≤). By the results on closure operators recalled in the previous section and since the relation co is irreflexive, we know that L(P ) = hL(P ), ⊆, ∅, P, (.)⊥i is an orthocomplemented complete lattice, in which the meet is just set intersection, while the join of a family of elements is given by set union followed by closure.
Now we present our principal result for combinatorial posets: N-density is necessary and sufficient for the orthomodularity of L(P ).
Theorem 1. If P = (P, ≤) is combinatorial, then L(P ) is orthomodular if and only if P = (P, ≤) is N-dense.
Note that the orthomodular law requires that, if an element is strictly bigger than another one, then the meet between the first element and the orthocomplement of the second one should be different from the minimum element. Hence, if A ⊂ B then B contains at least an element x concurrent with A.
The orthomodular law is weaker than the distributive law. Orthocomplemented distributive lattices are called Boolean algebras. Orthomodular lattices can therefore be considered as a generalization of Boolean algebras.
Now we characterize the K-density of a poset P = (P, ≤) by a property of the closed sets. In particular, we show that the combinatorial N-dense posets are K-dense if and only if, given a closed set, any line intersects either the closed set or its orthocomplement.
Theorem 2. If P = (P, ≤) is combinatorial and N-dense, then
P = (P, ≤) is K-dense ⇔ ∀S ∈ L(P ), ∀λ ∈ lines(P), λ ∩ (S ∪ S⊥) 6= ∅ From Theorem 2 it follows a crucial relation between lines and closed sets; namely, given a closed set S, a line λ crosses either S or S⊥ (λ ∩ S 6= ∅ ⇐⇒ λ ∩ S⊥ = ∅).
We now define a map associated to a line of P = (P, ≤): the characteristic map of the family of closed sets that cross the given line.
Definition 7. Let λ ∈ lines(P). Define Δ(λ) = {S ∈ L(P ) | S ∩ λ 6= ∅}, and δλ : L(P ) → {0, 1} such that: for each S ∈ L(P ), δλ(S) = 1 if S ∈ Δ(λ), δλ(S) = 0 otherwise. Theorem 3. Let P = (P, ≤) be a K-dense poset. The map δλ is a two-valued state of the lattice L(P ).
This result allows to state that any line in a combinatorial and K-dense poset P = (P, ≤) identifies a two-valued state in the lattice of closed sets L(P ).
There is a dual relation between the cuts of P = (P, ≤) and the Boolean
subalgebras in the lattice of closed sets L(P ): any cut τ ∈ cuts(P) generates a
Boolean subalgebra of L(P ) [
The next theorem states that, for combinatorial posets, K-density and degree finiteness are sufficient for the algebraicity of the lattice of closed sets. Theorem 4. The family L(P ) of the closed sets of a combinatorial, K-dense and degree finite poset forms an algebraic lattice.
In conclusion, we have proved that for combinatorial posets, N-density implies
the orthomodularity of the lattice of closed sets defined on the basis of
concurrency. An orthomodular lattice is always regular ([
Moreover, we have shown that for combinatorial posets the K-density determines a crucial relation between lines and closed sets: given a closed set a line crosses either the closed set or its orthocomplement. This suggests to look at the family of closed sets as the set of propositions in a logic language and at the lines as two-valued states and hence as interpretations (models) of the propositions. In general, the lattice of closed sets is not a Boolean algebra, so that the resulting logic is non-classical; we point to the cuts of the combinatorial poset as the Boolean substructures of the overall lattice.
Finally, we proved that K-density, together with degree finiteness, is a sufficient condition for the algebraicity of the lattice.
Acknowledgement This work was partially supported by MIUR and by MIUR-PRIN 2010/2011 grant code H41J12000190001.