Background domain theory

In the late 1960s, Dana Scott started to develop domain theory (Scott, Reference Scott1970). This theory deals with partial orders that can be regarded as “information orderings”: the elements of the partial order represent pieces of information (or partial results of computations). To describe the information structures that we will use, we start by recapping some notions from domain theory (see, e.g., Abramsky & Jung, Reference Abramsky, Jung, Abramsky, Gabbay and Maibaum1994 or Gierz et al., Reference Gierz, Hofmann, Keimel, Lawson, Mislove and Scott2003).

Given a partial order P, a subset $D \subseteq P$ is directed if $D \neq \emptyset $ and any two elements of D have an upper bound in D. A partial order P is a directed-complete partial order (dcpo) if every directed subset D of P has a least upper bound $\bigvee D$ . One then often says that D converges to $\bigvee D$ . Given a dcpo P and $a,b \in P$ , we say a is way below b ( $a \ll b$ ) if any directed set D that converges to (or beyond) b must explicitly go above a: if $b \leq \bigvee D$ , then there is a $d \in D$ such that $a \leq d$ . (The relation $\ll $ is also called order of approximation and elements $a \in P$ with $a \ll a$ are called compact or finite.) Write . Intuitively, $a \ll b$ means that the much simpler a approximates the complicated b. A basis B of a dcpo P is a subset of P such that for all $a \in P$ , contains a directed subset with supremum a. A dcpo P is continuous if it has a basis, that is, all elements can be obtained as limits of basic or ‘simple’ elements. (A dcpo P is algebraic if it has a basis of compact elements.) A continuous dcpo is called a domain (though the exact meaning of ‘domain’ can vary: sometimes demanding more or less but usually requiring being a dcpo).

A subset C of a dcpo P is called Scott closed if C is a downsetFootnote ¹ and closed under suprema of directed subsets. A subset U is Scott open iff U is an upset and if it contains the supremum of a directed set $D \subseteq P$ , then U already contains an element of D. Write $C(P)$ and $O(P)$ for the Scott closed and opens sets of P, respectively. The topological space $(P , O(P))$ is a $T_0$ -space, not necessarily sober, and it is Hausdorff iff the order on P is trivial. We will make use of the following result. (It is also discussed in Ho & Zhao, Reference Ho and Zhao2009 and Ho et al., Reference Ho, Goubault-Larrecq, Jung and Xi2018.)

The category-theoretic version of this result states that the category of continuous domains and the category of completely distributive lattices are dually equivalent via the ‘open-set’-functor and the ‘points’-functor (Abramsky & Jung, Reference Abramsky, Jung, Abramsky, Gabbay and Maibaum1994, theorem 7.2.28).

States, domains and information

We assume to be given a state space in the general sense, that is, a nonempty set S of entities of which it makes sense to say that they contain some information. These states could be, for example, states of a dynamical system, sequences of observations about a system, states of knowledge about the world, partial possible situations, and so on. We will consider concrete examples below, but for now we can remain general about what exactly these states are.

As mentioned, domains are motivated as reconstructing the structure of collections of pieces of information. Thus, we think of the collection of all the pieces of information of all the states in S as forming a continuous dcpo P. The continuity of the domain says that any piece of information can be approximated by (or, is the limit of) “simple” pieces of information. For the time being, we assume that this is essential for pieces of information. Finally, we regard Scott closed sets of P as positive information and Scott open sets as negative information. The motivation for this is as follows (just heuristics, no formal argument).

Why is positive information a Scott closed set? The (positive) information contained in a state s is a collection C of pieces of information. Loosely speaking, C is what s “asserts” or “affirms” (though, the pieces of information don’t need to be expressible in a language). This collection should be downwards closed: if the piece of information i is in C and j is contained in i, then also $j \in C$ . Moreover, as we will argue next, C should be closed under suprema of directed subsets. Indeed, with limits of directed subsets, domain theory proved to provide a fruitful reconstruction of the general concept of computation: abstract enough to be independent of concrete implementations, but still concrete enough to capture the essential features and intuitions. Thus, the collection C of pieces of information affirmed by a state should be closed under suprema of directed subsets: whatever piece of information that can be computed, deduced, or obtained from only pieces of information in C should already be in C, since it hence also is an information asserted by s.Footnote ⁴

Why is negative information a Scott open set? The negative information contained in a state s is, loosely speaking, the collection U of those pieces of information that the state “denies” or “refutes” (again, these pieces need not be linguistically expressible). This collection should be upwards closed: if the piece of information i is refuted by s, then all stronger versions $j \geq i$ of it are refuted, too. Moreover, U should be inaccessible by directed joins: if one refutes the limit $\bigvee D$ of an approximation, then one shows that, at some point $d \in D$ , the approximation moves in the wrong direction, whence one already refutes d. In other words, if one refutes the limit $\bigvee D$ of a computation, then one shows that one of the resources $d \in D$ which one used had to be false.

Much more could be said about the motivation for modeling positive and negative information of a state in this way—especially if we look at concrete instances of such states. However, to keep to the point, we will take this as a prima facie plausible reconstruction of information in states and move to investigating this framework. (Though, in §5.1 we will say more on this, and, more generally, also see, e.g., Smyth, Reference Smyth1983 and Vickers, Reference Vickers1989 for a ‘logical’ perspective on topological notions.) After all, much of the motivation for a reconstruction comes from the fruitfulness of its application.

Information assignment

The idea of having states that contain positive and negative information can formally be spelled out as follows.

Condition (i) demands that the notion of information reconstructed here is very “fine-grained”: if there is absolutely no difference in the information of two states, then two states are (regarded to be) the same. Condition (ii) is a condition on the state space: It should be rich enough such that for every state s there also is a state $s^*$ which affirms exactly what s doesn’t deny and denies exactly what s doesn’t affirm. In other words, for any state s, the state space should contain the “informational completion” $s^*$ of s.

As a first simple example, we can consider the dynamical system of a classical particle moving on a line as described by classical mechanics.

We will consider more examples in due course.

Information theoretic operations

The information assignment $\iota $ induces a partial join function on S: $s \circ _{\iota } s' $ is defined as the $s''$ , if it exists, that contains exactly the information contained in s plus the information contained in $s'$ . Moreover, $\iota $ also induces a notion of incompatibility on S: two states are incompatible iff they disagree on a piece of information. Finally, $\iota $ induces a star-mapping: for $s \in S$ , $s^{*_{\iota }}$ is the informational completion of s. To summarize, we have defined the following.

One might be tempted to additionally demand of information assignments that information fusion always is total, that is, that the set of states is closed under information fusion. However, the position-momentum space example above shows that this is not always possible: any state was informationally complete, so no further information could be fused to it without becoming inconsistent (and the state space didn’t include an inconsistent state). Nonetheless, one might wonder how to obtain information assignments where this (and stronger forms of) information fusion is possible. We will do this in §5.

Here are some basics facts about the induced information structure.

Note that, in (i), there is no reason to expect $\circ _{\iota }$ to be associative (that is a subtlety that will become relevant below). Also note that (ii) shows that $\leq _{\iota }$ is the superposition of two preorders: The positive information preorder $s \leq _+ s'$ given by $\iota _+ (s) \subseteq \iota _+(s')$ and the negative information preorder $s \leq _- s'$ given by $\iota _- (s) \subseteq \iota _-(s')$ . This is reminiscent of the following example.Footnote ⁵

High-level information

We have said that the information described by $\iota $ is very fine-grained and not necessarily expressible in a language. Thus, in a sense, $\iota $ describes the “low-level” information contained in a state. We will now describe an assignment of information that is expressible in a language and high-level.

Let $\mathcal {L}$ be the language built from the propositional variables $p_1 , p _2 , p_3 , \ldots $ using the connectives $\neg , \wedge , \vee , \to , \top $ . We use v as a variable for literals and $\overline {v}$ is the complement of the literal v.Footnote ⁸ Given a set S, a valuation is a function $V : S \to \mathcal {P}(\{p_1 , \overline {p_1}, p_2, \overline {p_2}, \ldots \})$ . The valuation assigns every state $s \in S$ a set of literals which intuitively describes which atomic sentences are made true and/or made false at the state.

Of course, the high-level and low-level information should be related. In the ideal case, the high-level information “arises from” the low-level information. One straightforward way to spell this out is given by the next definition.

Condition (i) says that if we put together the low-level information of two states, we won’t lose any high-level information. (Though, it might be that there is some low-level information in the two states that individually is not expressible in the language yet, but if put together it becomes salient enough to be describable.) Condition (ii) says that a high-level incompatibility only occurs if there also is a low-level incompatibility. Condition (iii) says that, not only on the low-level but also on the high-level, $s^*$ asserts what s doesn’t deny and denies what s doesn’t assert.Footnote ⁹

Summary information structure

Let’s summarize the definitions so far and then sketch an example.

Note that, as mentioned, we don’t assume anything about the set of states S except that it makes sense to speak of information contained in the states in S. Yet, for concrete S, we might make use of its additional structure, as we can see in the following example.

Note how in this example the information structure is closely linked to the dynamics of the system.

Definition of HYPE models

We will work with hype models for the propositional language $\mathcal {L}$ with connectives $\bot , \wedge , \vee , \neg , \to $ . (Hype models also exist for first-order languages.)

Formula satisfaction and logical consequence in hype models is defined as follows.

Leitgeb (Reference Leitgeb2019) provides a sound and complete logic for hype models with this semantics. We will refer to this logic as hype which we repeat for convenience in Figure 1. The logic hype is well-understood and well-behaved. It not only is sound and complete (via a canonical model construction) with respect to the hype models, it also has the deduction theorem, the finite model property, and is decidable. Moreover, it contains first-degree entailment, conservatively extends intuitionistic logic, and the structures of hype models are well-known from ordinary mathematics. (For all these results see Leitgeb, Reference Leitgeb2019.)

Fig. 1

The system hype as presented by Leitgeb (Reference Leitgeb2019).

Facts about HYPE models

Conditions 3(b–d) are just enough to show that the join function defines a partial order (Leitgeb, Reference Leitgeb2019):

Definition 3.12 ( $\leq $ )

Given a hype model $( S , V , \circ , \perp )$ , define for all $s,s' \in S$

$$ \begin{align*} s \leq s' :\Leftrightarrow \big(s \circ s' \text{ exists and } s \circ s' = s' \big). \end{align*} $$

We write $\bigvee _{\leq }$ for the least upper bound, if it exists, with respect to $\leq $ . We drop the subscript $\leq $ if it is clear from context.

In an earlier definition of hype models, condition 3(d) was stronger: it demanded $\circ $ to be associative up to definedness. Formally:

We will mostly deal with associative hype models. But, as far as the logic is concerned, this is not a restriction: completeness was already obtained for the earlier version of hype models. Formally:

One advantage of associative hype models is that fusion and least upper bound go well together.

Lemma 3.16 (Fusion and order)

Let $( S , V , \circ , \perp )$ be an associative hype model. Then for all $s , s' \in S$ , if $s \circ s'$ exists, then

$$ \begin{align*} s \circ s' = \bigvee \{ s , s' \}. \end{align*} $$

Infinite DeMorgan laws

As a first application of an informational perspective on hype models, we show that the star mapping of a hype model satisfies the infinite DeMorgan laws.

Proof. Consider the completely distributive complete lattice $L := \mathcal {P}(S)$ and the arbitrary $\bigvee _{\leq }$ -join preserving injective function $f : S \to L, ~ s \mapsto ({\uparrow } s)^c$ . By Theorem 2.1, there is a continuous dcpo P such that L is isomorphic to $C(P)$ , say via isomorphism g. Define $\iota _+ (s) := g \big (\kern1.2pt f (s) \big )$ . By construction, $\iota _+$ preserves existing arbitrary $\bigvee _{\leq }$ - joins. Moreover, $\iota _+$ preserves $\circ $ , since if $s \circ s'$ exists, it equals, by Lemma 3.16, $\bigvee _{\leq } \{s , s'\}$ whose $\iota _+$ -image is $\iota _+ (s) \cup \iota _+(s')$ .

Concerning (1), $(\iota _+ , \iota _-)$ clearly is injective since $\iota _+$ already is injective. Moreover, by definition and since $s^{**} = s$ , we have

$$ \begin{align*} \iota_+ (s^*) = \big( \iota_- (s) \big)^c \text{ and } \iota_- (s^*) = \big( \iota_+ (s^{**}) \big)^c = \big( \iota_+ (s) \big)^c. \end{align*} $$

Hence $(\iota _+ , \iota _-)$ is an information assignment.

Concerning (2), we have by Lemma 3.13 and since $\iota _+$ preserves existing $\bigvee _{\leq }$ -joins that

$$ \begin{align*} \iota_+ (s^*) = \iota_+ \big( {\bigvee}_{\leq} \{ s' : s' \not\perp s \} \big) = \mathsf{Cl} \big( \bigcup_{s' \not\perp s} \iota_+(s') \big). \end{align*} $$

It is a basic fact that the closure $\mathsf {Cl} (A)$ (in the Scott topology) of a downset A in a continuous domain is $\{ \bigvee D : D \subset A \text { directed} \}$ (e.g., Abramsky & Jung, Reference Abramsky, Jung, Abramsky, Gabbay and Maibaum1994, sec. 2, ex. 33). Hence $\iota _- (s) = \big ( \iota _+(s^*) \big )^c$ is the set of $i \in P$ that cannot be reached by a directed subset of $\bigcup _{s' \not \perp s} \iota _+(s')$ .

Concerning (3), for ( $\Rightarrow $ ) we argue by contraposition. Assume $\iota _+ (s) \cap \iota _-(s') = \emptyset $ . Then, by definition, $\iota _+ (s) \cap \big ( \iota _+ ({s'}^{*}) \big )^c = \emptyset $ , so $\iota _+ (s) \subseteq \iota _+({s'}^{*})$ . Hence, by definition of $\iota _+$ as $g \circ f$ , we have $(\uparrow {} s )^c = f(s) \subseteq f({s'}^{*}) = (\uparrow {} {s'}^{*} )^c $ , so $s \leq {s'}^{*}$ . By Lemma 3.13, $s \not \perp s'$ .

( $\Leftarrow $ ). Assume for contraction that there is an $i \in \iota _+ (s) \cap \iota _- (s')$ but $s \not \perp s'$ . Then $\{ i \} \subseteq \iota _+ (s) \subseteq \bigcup _{t' \not \perp s'} \iota _+(t')$ is directed and $i = \bigvee \{ i \}$ . Hence $i \not \in \iota _- (s')$ , contradiction.  □

Theorem 3.18 (Compatibility distributes over fusion)

Let $(S,V, \circ , \perp )$ be an associative hype model. Then for all $s \in S$ and $T \subseteq S$ such that $\bigvee {}_{\leq } T$ exists, we have

$$ \begin{align*} s \not\perp \bigvee T \text{ iff } \forall s' \in T : s \not\perp s'. \end{align*} $$

In particular, for all $t , s, s' \in S$ , if $s \circ s'$ exists, then $t \not \perp s \circ s'$ iff $t \not \perp s$ and $t \not \perp s'$ .

Before continuing, a comment on a recent study of hype (published after the submission of this paper) by Odintsov & Wansing (Reference Odintsov and Wansing2020). Among others, they obtain another, simpler semantics for the logic hype. Instead of hype models, they define models $\mathcal {M}$ over involutive star i-frames: An involutive star i-frame is a triple $\mathcal {W} = (W,\leq ,*)$ where W is a nonempty set partially ordered by $\leq $ and $* : W \to W$ is an involution.Footnote ¹⁴ A model over $\mathcal {W}$ is a pair $\mathcal {M} = (\mathcal {W} , v)$ where v is a function assigning each proposition variable p an upset of W (i.e., a subset of W closed under $\leq $ ). These models can interpret the propositional language $\mathcal {L}$ of hype (negation uses $*$ and implication uses $\leq $ ) and the logic hype is characterized by the class of all involutive star i-frames.

Here is a connection with the present work. Every information assignment $(P , \iota )$ to a nonempty set S induces the involutive i-frame $(S , \leq _{\iota } , *_{\iota })$ . And every involutive i-frame $(W,\leq ,*)$ is induced by some information assignment $(P,\iota )$ to W, that is, $(W,\leq ,*) = (W , \leq _{\iota } , *_{\iota })$ .Footnote ¹⁵ Thus, instead of the idea of a valuation function describing the high-level information supervening on the low-level information, we can consider a valuation function v assigning every propositional variable a $\leq _{\iota }$ -closed subset of S. Then we not only have a representation theorem for hype models using information structures, but we also have a representation theorem for models over involutive star i-frames.

5.1 Notions of information fusion

We collect several notions of information fusion and motivate why to consider (i) and (iii) below as the generic ones.

Given an information assignment $\iota = (\iota _+ , \iota _-)$ to S, we call $\iota $ :

1. (i) poset complete, if $(S, \leq _{\iota } )$ is a complete partial order, that is, for any $T \subseteq S$ there is a state $s''$ that is the least upper bound of T with respect to the information containment ordering.

2. (ii) total, if for all $s , s' \in S$ , there is a $s'' \in S$ such that $\iota _{\pm } (s'') = \iota _{\pm }(s) \cup \iota _{\pm }(s')$ .

3. (iii) join-complete, if for all $T_0 , T \subseteq S$ with $T_0$ being finite, there is a $s'' \in S$ such that $\iota _+ (s'') = \mathsf {Cl} \bigcup _{t \in T} \iota _+ (t)$ and $\iota _- (s'') = \bigcup _{t \in T_0} \iota _- (t)$ . (Recall, $\mathsf {Cl} A$ is the topological closure of A.)

4. (iv) diagonally complete, if for all $T \subseteq S$ , there is a $s'' \in S$ such that $\iota _+ (s'') = \mathsf {Cl} \bigcup _{s \in T} \iota _+ (s)$ and $\iota _- (s'') = \bigcup _{s \in T} \iota _- (s)$ .

5. (v) complete, if for all $T, T' \subseteq S$ , there is a $s'' \in S$ such that $\iota _+ (s'') = \mathsf {Cl} \bigcup _{s \in T} \iota _+ (s)$ and $\iota _- (s'') = \bigcup _{s \in T'} \iota _- (s)$ .

Three comments. First, the logical relationship is as follows: (v) implies (iii) and (iv); (iv) implies (i) and (ii); (iii) implies (ii). Second, note that the difference between (i) and (ii)–(v) is the following. In (i) we demand a state to exists that is minimal in containing the information of the states to be fused. In the other notions we demand, in various forms, that the information in that minimal state is actually the fusion of the information in the states to be fused. Note that this subtle distinction is not available if one only works with a poset of states and not with an information assignment. Accordingly, we will speak of poset fusion and assignment fusion. Third, closely related to the notions of fusion are the notions of substructure of $ C(P) \times O(P) $ that the image of the information assignment constitutes. For example, if $\iota (S) \subseteq C(P) \times O(P)$ is a sub-join-semi-lattice, then $\iota = (\iota _+ , \iota _-)$ is total. If $\iota (S)$ is a complete sublattice of $C(P) \times O(P)$ , then $\iota $ is diagonally complete. If $\iota $ is surjective, $\iota $ is complete.

What notion of information fusion is the correct one very much depends on the particular state space. Still, we motivate why to consider (i) as the generic poset fusion and (iii) as the generic assignment fusion.

We have mentioned at the beginning of this section that it is intuitive and often required that any collection of information states can be fused into a new state. Reflecting the difference between poset- and assignment fusion, the weak reading of this is (i) and the strong reading is (iv). Hence a state space that is closed under information fusion should at least satisfy (i). Though, we will argue next that the strong reading is too strong. That is, we will argue that as far as assignment fusion is concerned, there is an asymmetry between positive and negative information: In general, we can plausibly expect that the informational fusion of the positive information of arbitrarily many states is again possessed by some state. However, for negative information we should only expect this for finitely many states. As a consequence, (iii) is the generic assignment fusion.

To argue for this asymmetry between positive and negative information, we will first discuss two rough and intuitive ways of categorizing various notions of fusion.

One distinction between notions of fusions concerns whether (positive) information and fusion is understood conjunctively or disjunctively.

The conjunctive way to understand that a piece of information i is part of the positive information of a state s is that i obtains at s or that s has or makes-true the property i. Dually, if i is among the negative information of s, i is a property that the state falsifies. Thus, states are assumed to be given, and pieces of information are properties of states (that is, sets of states). This is in line with the classic view that information containment is just the dual of implication: the information in p is contained in the information in q iff q implies p. On this view, it is natural to interpret information fusion as conjunction: $s''$ is the state having all the properties that the states in $T \subseteq S$ have.Footnote ^{17 ,} Footnote ¹⁸

The disjunctive way to understand that a piece of information i is part of the positive information of a state s is as follows. The states are regarded as stages of a process of, say, recognizing an object in a messy collection of data or assessing a situation. The positive information of a state is a collection of hypotheses about how the object might look like or what the correct evaluation of the situation is. Dually, the negative information is a collection of hypotheses about what the object or situation is not. On this view, it is natural to interpret information fusion as disjunction: $s''$ contains all the hypotheses that are contained in one of the states to be fused.Footnote ¹⁹

Another distinction between notions of fusions concerns whether or not the positive and negative information of a state are dependent on each other. This could range from fully dependent (one determining the other) to entirely independent. If the latter is the case, both positive and negative information of a state are just some unrelated collections of properties or hypotheses, which suggests that they behave structurally similarly, whence a symmetric notion of fusion seems appropriate (unlike join-complete fusion). However, in many concrete examples it is natural to assume that the positive information of a state has some implications for the negative information and vice versa.

Let’s now show how the fact that positive and negative information are related motivates the asymmetry between positive and negative information.

Concerning the disjunctive case, if $\iota _+ (s)$ are all the hypotheses entertained about the object or situation at state s, a natural choice for $\iota _-(s)$ is as the set of hypotheses that are already falsified at state s. Thus, negative information has a conjunctive reading (all the hypotheses in $\iota _-(s)$ are falsified) and positive information has a disjunctive reading (one conjectures that some hypothesis in $\iota _+(s)$ is true). If we assume that information can be phrased as affirmative assertion (true iff affirmable), then only finite negative but arbitrary positive information can be fused (see, e.g., Vickers, Reference Vickers1989).

Concerning the conjunctive case, we will consider the following example. It provides a state space with an information assignment understanding information conjunctively and where the positive and negative information determine each other. The informational fusion of the positive information of (essentially) arbitrarily many states is again possessed by some state, but for negative information this is only true for finitely many states.

Example 5.25 (State space of open sets)

We consider a set S of open sets of some topological space X as state space and an information assignment $(P , \iota )$ to S that allows for (directed) fusion of positive information but only finite fusion of negative information.

Let X be a spectral space (a topological space that is homeomorphic to the spectrum of a commutative ring or, equivalently, to the spectrum of a bounded distributive lattice). In fact, for this example it will be enough that X is a topological space with a basis of compact open sets.

We obtain the domain P as follows. We write $f : X \rightharpoonup X$ for a partial function on X and $\mathrm{dom} (\,f)$ for the domain of f. As usual, f is continuous, if for all open U, $f^{-1} U$ is open. Define $P := \{\kern1.2pt f : X \rightharpoonup X : f \text { continuous} \}$ ordered by extension: $f \leq g$ iff $f \subseteq g$ (considering the functions as sets of pairs). One can then show that D is an algebraic domain.Footnote ²⁰ The compact elements are those $f \in D$ with $\mathrm{dom} (\,f)$ compact-open. This generalizes the well-known example that the set of partial functions on the positive integers ordered by extension forms an algebraic domain (equip $X := \mathbb {N}$ with the discrete topology).

Let $S \subseteq O(X)$ be a filter (a nonempty upset closed under meets). Considering such subsets of opens as state space is motivated by the fact that they can be regarded as ‘models’ in a general sense. According to the usual ‘logical’ interpretation of Stone duality, prime filters are models: If L is the Lindenbaum–Tarski algebra of a distributive logic (using the connectives $\bot , \top , \wedge , \vee $ ), a model is a lattice homomorphism $M : L \to 2$ which, in turn, corresponds to the prime filter $M^{-1} (1)$ . Generalizing, if X is the spectrum of a distributive lattice L, we may view a prime filter $S \subseteq O(X) \cong L$ as a model.

One can then define $\iota _+ : S \to C(P)$ and $\iota _- : S \to O(P)$ by

$$ \begin{align*} \iota_+ ( U ) := \{\kern1.2pt f \in D : \mathrm{dom} (\,f) \subseteq U \} ~~ \text{ and } ~~ \iota_- (s) := \big( \iota_+ (s) \big)^c. \end{align*} $$

and show that $(P,\iota )$ is an information assignment such that

1. (i) For $T \subseteq S \subseteq $ -directedFootnote ²¹ , we have $s'' := \bigcup T \in S$ and $\iota _+ (s'') = \mathsf {Cl} \bigcup _{t \in T} \iota _+ (t)$ .

2. (ii) For $T_0 \subseteq S$ finite, we have $s'' := \bigcap T_0 \in S$ and $\iota _- (s'') = \bigcup _{t \in T_0} \iota _- (t)$ .

3. (iii) If S is a nonprincipal filterFootnote ²² , then for $T := S \subseteq S$ , there cannot be $s'' \in S$ with $\iota _- (s'') = \bigcup _{t \in T} \iota _- (t)$ .

It’s worth putting this example into perspective by realizing that $\iota _+$ is a presheaf. After all, the general motivation of (pre)sheaves is that they assign information to the open sets of a space. A paradigm example of a sheaf assigns to each open subset U of X the ring of continuous real-valued functions on U. This is usually applied to rather well-behaved geometric spaces X like manifolds. But in case of, e.g., a spectral space X, we can give this a domain-theoretic twist: For $U \in O(X)$ , define $F (U) := \iota _+ (U) = \{\kern1.2pt f \in D : \mathrm{dom} (\,f) \subseteq U \}$ , and, for open $V \subseteq U$ , define the restriction morphism $\mathsf {res}_{V,U} : F(U) \to F(V)$ by function restriction. Then F is a presheaf on X with values in the category of dcpos and Scott-continuous functions (which is cocomplete so stalks can be defined). We leave it to future work to further explore this perspective.

Another example may be obtained from considering the set S of computably enumerable sets of natural numbers as state space. Ignoring matters of effectiveness (e.g., by working in an effective background theory), S is closed under arbitrary union (by running in parallel the Turing machines enumerating the sets) but only under finite intersection.

To summarize, there are many notions of fusion found in various state spaces (from none to complete). Poset complete and join-complete fusion can be motivated as being the generic ones. Thus, we will focus on closing a state space under these two notions of fusion. The overview of the construction is the following:

1. 1. Start with a state space and an information assignment and consider the induced hype model $\mathfrak {M}$ . Alternatively, start with an associative hype model and consider its informational representation (so it makes sense to speak of information fusion).

2. 2. On this informational understanding, it is natural to demand $\mathfrak {M}$ to have a certain groundedness property (see §5.2).

3. 3. If it does, we can form the Dedekind–MacNeille completion $\mathfrak {M}'$ of $\mathfrak {M}$ , which extends $\mathfrak {M}$ by exactly the states needed to make it poset complete (see §5.3).

4. 4. Again, on an informational understanding, it is natural to demand $\mathfrak {M}'$ to have a certain separation property (see §5.2).

5. 5. If it does, we can form the skew model $\mathfrak {M}''$ of $\mathfrak {M}'$ , which extends $\mathfrak {M}'$ by the states needed to make it join-complete while remaining poset complete (see §5.3 and Theorem 5.37).

6. 6. Thus, $\mathfrak {M}''$ is the closure of $\mathfrak {M}$ under the two generic kinds of information fusion.

We will now do this in detail.

5.2 Structural properties of HYPE models

We describe two properties of hype models each defining a subclass of hype models. On an informational understanding of states (which is justified by the representation Theorem 4.22), it is well-motivated to demand hype models to have these properties.

Separation property

Roughly, the separation property states that if two states differ, there is a “simple” state that accounts for this. Let’s first state this formally and then motivate it.

Definition 5.27 (Meet-prime separation property)

Let $(S,\leq )$ be a poset. An element $a \in S$ is meet-prime if for all $s,s' \in S$ such that $s \wedge s'$ exists,

$$ \begin{align*} \text{if } s \wedge s' \leq a \text{, then } s \leq a \text{ or } s' \leq a. \end{align*} $$

We say that $(S, \leq )$ has the meet-prime separation property if for all $s,s' \in S$ ,

$$ \begin{align*} \text{if } s \not\leq s' \text{, then there is meet-prime } a \in S: s \not\leq a \text{ and } s' \leq a. \end{align*} $$

A hype model is said to have the meet-prime separation property if the underlying poset of states $(S,\leq )$ has this separation property.

Using the representation theorem to represent states by the information that they contain, we can understand meet-prime states as informationally prime states: whenever a meet-prime state a contains the information (exactly) shared by two states s and $s'$ , then the reason for this is that a already contains the information of (at least) one of the states. So a is, in a sense, indecomposable or complete, whence a has a simple information structure.

Thus, the separation property says that state difference is tracked by the simple (informationally prime) states: If two states s and $s'$ are not identical, then one is not below the other, say $s \not \leq s'$ , and the separation property ensures that we can find a prime state a that contains $s'$ but still doesn’t contain s.Footnote ²³ In other words, if $s \neq s'$ , we find a “simple” reason for this.

This separation property is well-known from pointless topology:

Proposition 5.28. Let $(S,\leq )$ be a join-complete partial order that has the meet-prime separation property. Then $(S,\leq )$ is a spatial locale (i.e., the poset of opens of some topological space).

Proof. We show that S is a locale. Since a join-complete partial order in fact already is complete, it remains to show that $(S,\leq )$ satisfies the infinite distributive law $x \wedge \bigvee Y = \bigvee _{y \in Y} x \wedge y$ . The $\geq $ direction is standard, so assume for contradiction that $\leq $ wouldn’t hold. Then, by the separation property, there is a meet-prime $a \in S$ such that $x \wedge \bigvee Y \not \leq a$ and $\bigvee _{y \in Y} x \wedge y \leq a$ . By the former, $x \not \leq a$ . By the latter, for all $y \in Y$ , $x \wedge y \leq a$ . Since a is meet-prime, $x \leq a$ or $y \leq a$ . Since $x \not \leq a$ , $y \leq a$ . Hence a is an upper bound of Y, so $\bigvee Y \leq a$ . This is a contradiction to $x \wedge \bigvee Y \not \leq a$ .

Since meet-prime elements of a locale can equivalently be regarded as completely prime filters (or frame homomorphisms into the 2-point frame, or as principal prime ideals), the separation property is equivalent to the property of a locale being spatial (Johnstone, Reference Johnstone1982, chap. 2).  □

An important feature of a poset with the meet-prime separation property is the following embedding property.

Theorem 5.29 (Meet-prime separation and embeddability)

Let $(S,\leq )$ be a poset with the meet-prime separation property. Then there is a completely distributive complete lattice L and an injective function $f : S \to L$ such that f is an order embedding ( $a \leq b$ iff $f(a) \leq f(b)$ ) and preserves existing finite meets and arbitrary joins.

Proof. See appendix.  □

Since, by Theorem 2.1, L is isomorphic to $C(P)$ for some continuous dcpo P, this theorem allows for information assignments with strong preservation properties.

5.3 Closure properties of the class of HYPE models

If one defines a class of mathematical structures, it is important to check under which model constructions this class is closed. Here we consider two such constructions.

Dedekind-MacNeille completion

Given a hype model, it is natural to ask: is there a smallest hype model that contains the original model and where the containment ordering is complete? Informationally speaking, is there a way to add exactly those new states that are needed such that for any set of states A there is a state $s''$ that is the least upper bound of A in the information containment order? We will answer this question positively thus: If a hype model is grounded, we can take the Dedekind–MacNeille completion of its underlying poset (which is its smallest completion) and naturally build a hype model on this completion.

To state this formally, we recall the Dedekind–MacNeille completion of a poset $(P, \leq )$ .Footnote ²⁴ Given a subset $A \subseteq P$ , define $\Uparrow A$ to be the set of upper bounds of A and $\Downarrow A$ to be the set of lower bounds of A. The Dedekind–MacNeille completion P is the set $\mathsf {DM}(P) := \{ A \subseteq S : A = \Downarrow \Uparrow A \} $ ordered by inclusion. This is the smallest completion of P: $\mathsf {DM}(P)$ is a complete lattice containing P (via the embedding $p \mapsto {\downarrow } p := \{q \in P : q \,{\leq}\, p \}$ ) and any complete lattice containing P will contain $\mathsf {DM}(P)$ .

Definition 5.30 (Dedekind–MacNeille model)

Let $\mathfrak {M} = (S, V , \circ , \perp )$ be a hype model. Define the Dedekind–MacNeille or DM model $\mathsf {DM} (\mathfrak {M}) := (S' , V' , \circ ' , \perp ')$ as follows:

1. (i) $S' := \mathsf {DM}( S ) = \{ A \subseteq S : A = \Downarrow \Uparrow A \} $

2. (ii) $V'(A) := \bigcup _{a \in A} V (a)$

3. (iii) $A \circ ' B := \Downarrow \Uparrow (A \cup B)$

4. (iv) $A \perp ' B :\Leftrightarrow \exists a \in A \exists b \in B : a \perp b$

5. (v) $(A^{*'} = \Downarrow \{ a^* : a \in A \})$

For any hype model $\mathfrak {M}$ , $\mathsf {DM}(\mathfrak {M})$ is almost a hype model: only $V(A^*) \supseteq \{ \overline {v} : v \not \in V(A) \}$ is not guaranteed. It is, if $\mathfrak {M}$ is grounded.

Proposition 5.31 (DM model is a hype model)

If $\mathfrak {M}$ is a grounded hype model, then $\mathsf {DM} (\mathfrak {M})$ is an associative hype model.

Proof. See appendix.  □

Note that by the representation theorem and since $\mathsf {DM} (\mathfrak {M})$ is associative, there is an information assignment to $\mathsf {DM} (\mathfrak {M})$ .

How is truth in $\mathcal {M}$ related to truth $\mathsf {DM}(\mathfrak {M})$ ? A partial answer is the following observation.

Proposition 5.32 (DM-completion preserves $\to $ -free formulas)

Fix a grounded hype model $\mathfrak {M}$ and its Dedekind–MacNeille completion $\mathsf {DM}(\mathfrak {M})$ . Then for all $\to $ -free formulas $\varphi $ , we have for all states $s \in \mathfrak {M}$ that

$$ \begin{align*} \mathfrak{M} , s \models \varphi ~ ~ \text{ iff } ~ ~ \mathsf{DM}(\mathfrak{M}) , {\downarrow} s \models \varphi. \end{align*} $$

Proof. By induction on $\varphi $ . For literals, conjunctions and disjunctions this is straightforward. For negation, we first show that $({\downarrow } a )^* = {\downarrow } (a^*)$ . Indeed, we have

$$ \begin{align*} b \in {\downarrow} (a^*) &\Leftrightarrow b \leq a^* \Leftrightarrow a \leq b^* \Leftrightarrow \forall c \in {\downarrow} a : c \leq b^* \\ &\Leftrightarrow b \in \Downarrow \{ c^* : c \in {\downarrow} a \} \Leftrightarrow b \in ({\downarrow} a)^*. \end{align*} $$

Hence we have $s \models \neg \varphi $ iff (Leitgeb, Reference Leitgeb2019) $s^* \not \models \varphi $ iff (by induction hypothesis) ${\downarrow } (s^*) \not \models \varphi $ iff (above claim) $({\downarrow } s )^* \not \models \varphi $ iff (Leitgeb, Reference Leitgeb2019) ${\downarrow } s \models \neg \varphi $ . □

Skew model

Given a hype model with state space S, we construct a hype model on $S \times S$ that, in a way, reverses $\perp $ and $\cdot ^*$ . We mention how to think of the new model (similar to a fiber bundle), and show that truth in the old model is closely related to truth in the new model.

Definition 5.33 (Reversed product or skew model)

Let $\mathfrak {M} = (S, V , \circ , \perp )$ be a hype model. Define the reversed product or skew model $\mathfrak {M} \otimes \mathfrak {M} := (S' , V' , \circ ' , \perp ')$ as follows:

1. (i) $S' := S \times S$

2. (ii) $V'(s,t) := V (s) \cap V(t)$

3. (iii) $(s , t) \circ ' (s' , t' ) := (s \circ s' , t \circ t')$ whenever $s \circ s'$ and $t \circ t'$ are defined

4. (iv) $(s , t ) \perp ' (s' , t') :\Leftrightarrow s \perp t' \text { or } t \perp s'$

5. (v) $((s,t)^* = (t^* , s^*))$

Although $\mathfrak {M} \otimes \mathfrak {M}$ is built on the product $S \times S$ , it is not the product model because of the twist or reversal of $\perp $ and $\cdot ^*$ . Rather, the idea is to take the original model $\mathfrak {M}$ and replace every state s with a copy of the state space S. That is, we replace a state with a “fiber” or “cluster” of states. Accordingly, an element $(s,t)$ of $\mathfrak {M} \otimes \mathfrak {M}$ is not to be thought of as an element of the product $S \times S$ but rather as point t in fiber s.

Comparing this model construction to existing ones, fiber spaces from topology immediately come to mind. Picturesquely speaking, they consist of a base space and out of every point b of the base space grows a fiber such that the points in the neighborhood of b and their fibers look like a product space although globally the base space with its fibers is not a product.Footnote ²⁵ In our setting, the original model $\mathfrak {M}$ would be the base space and a fiber out of a point s of $\mathfrak {M}$ is $\{(s , t) : t \in S \}$ . We leave it as an open question how a nontrivial topology would look like that satisfies the additional topological condition of a fiber bundle.Footnote ²⁶

Proposition 5.34 (Reversed product is a hype model)

If $\mathfrak {M}$ is a hype model, then $\mathfrak {M} \otimes \mathfrak {M}$ is a hype model.

Proof. See appendix.  □

In the remainder of this subsection, we want to show that truth in $\mathfrak {M} \otimes \mathfrak {M}$ is closely related to truth in $\mathfrak {M}$ . Similarly to the Dedekind–MacNeille completions, we note that states in $\mathfrak {M}$ and the diagonal states of $\mathfrak {M} \otimes \mathfrak {M}$ agree on $\to $ -free formulas.

Proposition 5.35 (Reversed product and $\to $ -free formulas)

Let $\mathfrak {M}$ be a hype model. Then for all $\to $ -free formulas $\varphi $ , we have for all states s in $\mathfrak {M}$ that

$$ \begin{align*} \mathfrak{M} , s \models \varphi ~ ~ \text{ iff } ~ ~ \mathfrak{M} \otimes \mathfrak{M} , (s,s) \models \varphi. \end{align*} $$

Proof. Immediate by induction on $\varphi $ (for negation again use that $s \models \neg \varphi $ iff $s^* \not \models \varphi $ ).  □

We would also like to know how formulas containing $\to $ behave in $\mathfrak {M}$ and $\mathfrak {M} \otimes \mathfrak {M}$ . For this we need two definitions. First, a hype model $\mathfrak {M}$ is exact, if for all $s,s' \in \mathfrak {M}$ , $V(s \circ s') = V(s) \cup V(s')$ (rather than just $\supseteq $ ).Footnote ²⁷ Second, a hype model $\mathfrak {M}$ is a distributive lattice, if the state space S of $\mathfrak {M}$ with the order induced by $\circ $ is a distributive lattice.

Proposition 5.36 (Reversed product and $\neg $ -free formulas)

Let $\mathfrak {M} $ be a hype model that is exact and a distributive lattice. Let $\varphi $ be a formula where $\neg $ only occurs in literals. Then for all states s and t in $\mathfrak {M}$ ,

$$ \begin{align*} \mathfrak{M} \otimes \mathfrak{M} , (s,t) \models \varphi ~ ~ \text{ iff } ~ ~ \mathfrak{M} , s \wedge t \models \varphi. \end{align*} $$

In particular, $(s,s) \models \varphi $ iff $s \models \varphi $ . Moreover,

$$ \begin{align*} \mathfrak{M} \otimes \mathfrak{M} , (s,t) \models \neg \varphi ~ ~ \text{ iff } ~ ~ \mathfrak{M} , s \vee t \models \neg \varphi. \end{align*} $$

Proof. By induction on $\varphi $ . For $\varphi = v$ , it suffices to show $V(s \wedge t) = V(s) \cap V(t)$ . Indeed, by the DeMorgan laws in hype models (Theorem 3.19), we have, since $s^* \circ t^*$ is defined (S is a lattice), that $s \wedge t = (s^* \circ t^*)^*$ . Hence, since $\mathfrak {M}$ is exact,

$$ \begin{align*} V\big( s \wedge t \big) &= V \big( ( s^* \circ t^* )^* \big) \\ &= \big\{ \overline{v} : v \not\in V(s^* \circ t^*) \big\} \\ &= \big\{ \overline{v} : v \not\in V(s^*) \cup V(t^*) \big\} \\ &= \big\{ \overline{v} : v \not\in V(s^*) \big\} \cap \big\{ \overline{v} : v \not\in V(t^*) \big\} \\ &= V(s^{* *}) \cap V(t^{* *}) = V(s) \cap V(t). \end{align*} $$

Again, $\wedge $ and $\vee $ are immediate by induction hypothesis.

For $\varphi \to \psi $ , we show $(s,t) \models \varphi \to \psi $ iff $s \wedge t \models \varphi \to \psi $ .

( $\Rightarrow $ ). Assume $(s,t) \models \varphi \to \psi $ . Let $s'' \models \varphi $ . We have to show $s'' \circ (s \wedge t) \models \psi $ . Indeed, by induction hypothesis, $(s'' , s'') \models \varphi $ . Since $(s,t) \models \varphi \to \psi $ , we have $(s'' , s'') \circ ' (s,t) = (s'' \circ s , s'' \circ t) \models \psi $ . By induction hypothesis and distributivity, $ (s'' \circ s) \wedge ( s'' \circ t) = s'' \circ (s \wedge t) \,{\models}\, \psi $ .

( $\Leftarrow $ ). Assume $s \wedge t \models \varphi \to \psi $ . Let $(s' , t') \models \varphi $ . We have to show $(s',t') \circ ' (s , t) \models \psi $ . Indeed, by induction hypothesis, $s' \wedge t' \models \varphi $ . Since $s \wedge t \models \varphi \to \psi $ , $(s' \wedge t') \circ (s \wedge t) \models \psi $ . By distributivity,

$$ \begin{align*} (s' \wedge t') \circ (s \wedge t) = \big( (s' \wedge t') \circ s \big) \wedge \big( (s' \wedge t') \circ t \big) \leq (s' \circ s) \wedge (t' \circ t). \end{align*} $$

It is a basic fact that $\models $ is monotone (Leitgeb, Reference Leitgeb2019), that is, in any hype model, if $s \models \varphi $ and $s \leq s'$ , then $s' \models \varphi $ . Hence $(s' \circ s) \wedge (t' \circ t) \models \psi $ . By induction hypothesis, $(s' \circ s , t' \circ t) = (s',t') \circ ' (s , t) \models \psi $ .

For the “moreover” part, we have now shown that $(t^* , s^*) \not \models \varphi $ iff $t^* \wedge s^* \not \models \varphi $ . By the lemma “ $s \models \neg \varphi $ iff $s^* \not \models \varphi $ ” we hence have

$$ \begin{align*} (t^* , s^*)^* \models \neg \varphi \text{ iff } (t^* \wedge s^*)^* \models \neg \varphi. \end{align*} $$

The claim follows by applying $(t^* , s^*)^* = (s,t)$ on the left-hand side and $(t^* \wedge s^*)^* = s \circ t$ (Theorem 3.19) on the right-hand side.  □

5.4 Closing under information fusion

We have said that, given an informational hype model, we would like to build an extension with an information assignment that is poset complete and join-complete.

Poset completeness is achieved by the Dedekind–MacNeille completion. Join-completeness is achieved via the next theorem.

Proof. Write $\mathfrak {M} = ( S , V , \circ , \perp ) $ . We start by constructing $(\iota _+ , \iota _-)$ . By Theorem 5.29, we use the separation property to find a frame order embedding of S into a completely distributive complete lattice which in turn is isomorphic to $C(P)$ for some continuous domain by Theorem 2.1. Hence we have an injective function $f : S \to C(P)$ preserving arbitrary joins and finite meets. We define

$$ \begin{align*} \begin{array}{c@{\qquad}c} \iota_+ : S \times S \to C(P) & \iota_- : S \times S \to O(P) \\ (s,t) \mapsto f(s) & (s,t) \mapsto \big(\kern1.2pt f(t^*) \big)^c. \end{array}\end{align*} $$

(Note that $\iota _-$ is well-defined, since $\iota _-(s,t)$ is the complement of a Scott-closed set and hence open.) We need to show:

1. (1) $\mathfrak {M} \otimes \mathfrak {M}$ is complete (as partial order).

2. (2) $(\iota _+ , \iota _-)$ is injective.

3. (3) $\iota _+ \big ( (s,t)^* \big ) = \big ( \iota _- (s,t) \big )^c$ and $\iota _- \big ( (s,t)^* \big ) = \big ( \iota _+ (s,t) \big )^c$ .

4. (4) $(\iota _+ , \iota _-)$ is join-complete.

5. (5) $\iota _+$ preserves arbitrary joins, and $\iota _-$ preserves finite joins.

Ad (1). By definition, $(s,t) \leq (s' , t')$ iff $s \leq s'$ and $t \leq t'$ . Hence, given $A \times B \subseteq \mathfrak {M} \otimes \mathfrak {M}$ , $(\bigvee A , \bigvee B)$ is the least upper bound of $A \times B$ .

Ad (2). Immediate, since f is injective.

Ad (3). We have

$$ \begin{align*} \iota_+ \big( (s,t)^* \big) &= \iota_+ (t^* , s^* ) = f(t^*) = \big(\kern1.2pt f(t^*)^c \big)^c = \big( \iota_- (s,t) \big)^c \\ \iota_- \big( (s,t)^* \big) &= \iota_- (t^* , s^* ) = \big(\kern1.2pt f(s^{**}) \big)^c = \big(\kern1.2pt f(s) \big)^c = \big( \iota_+ (s,t) \big)^c. \end{align*} $$

Ad (4). Let $A \times B , A_0 \times B_0 \subseteq \mathfrak {M} \otimes \mathfrak {M}$ where $A_0 \times B_0$ is finite. Since $\mathfrak {M}$ is complete (as partial order), we can choose $s'' := \bigvee A$ and $t'' := \bigvee B_0$ . Then we have

$$ \begin{align*} \iota_+ (s'', t'') = f(\bigvee A) = \mathsf{Cl} \bigcup\limits_{s \in A} f(s) = \mathsf{Cl} \bigcup\limits_{(s , t) \in A \times B} \iota_+ (s,t). \end{align*} $$

Moreover, we have

$$ \begin{align*} \iota_- (s'', t'') &= \big(\kern1.2pt f \big( (\bigvee B_0)^* \big) \big)^c \overset{{Theorem}~{3.19.}}{=} \big(\kern1.2pt f \big( \bigwedge \{ t^* : t \in B_0 \} \big) \big)^c \\[3pt] &= \big( \bigcap \big\{\kern1.2pt f(t^*) : t \in B_0 \big\} \big)^c = \bigcup\limits_{t \in B_0} \big(\kern1.2pt f(t^*) \big)^c \\[3pt] &= \bigcup\limits_{(s , t) \in A_0 \times B_0} \iota_- (s,t). \end{align*} $$

Ad (5). Using this reasoning, we have for $A \times B , A_0 \times B_0 \subseteq \mathfrak {M} \otimes \mathfrak {M}$ with $A_0 \times B_0$ finite, that

$$ \begin{align*} \iota_+ \big( \bigvee A \times B \big) &= \iota_+ \big( \bigvee A , \bigvee B \big) = \mathsf{Cl} \bigcup\limits_{(a , b) \in A \times B} \iota_+ (a,b) \\ \iota_- \big( \bigvee A_0 \times B_0 \big) &= \iota_- \big( \bigvee A_0 , \bigvee B_0 \big) = \bigcup\limits_{(a , b) \in A_0 \times B_0} \iota_+ (a,b), \end{align*} $$

as needed.  □

Thus, the procedure outlined at the end of §5.1 does indeed yield a way of closing a state space under the two generic kinds of fusion.