CONDITIONAL LOGIC IS COMPLETE FOR CONVEXITY IN THE PLANE

Abstract

We prove completeness of preferential conditional logic with respect to convexity over finite sets of points in the Euclidean plane. A conditional is defined to be true in a finite set of points if all extreme points of the set interpreting the antecedent satisfy the consequent. Equivalently, a conditional is true if the antecedent is contained in the convex hull of the points that satisfy both the antecedent and consequent. Our result is then that every consistent formula without nested conditionals is satisfiable in a model based on a finite set of points in the plane. The proof relies on a result by Richter and Rogers showing that every finite abstract convex geometry can be represented by convex polygons in the plane.

1. Introduction

Preferential conditional logic was introduced by Burgess [9] and Veltman [41] to axiomatize the validities of the conditional with respect to a semantics in models based on ordering relations. In this semantics a conditional $\varphi \leadsto \psi $ is true with respect to an order over a finite set of worlds if the consequent $\psi $ is true at all worlds that are minimal in the order among the worlds at which the antecedent $\varphi $ is true. Preferential conditional logic is sound and complete in this semantics with respect to models that are based on arbitrary preorders. But both Burgess and Veltman note that for completeness it suffices to consider partial orders. The axioms of preferential conditional logic are a weakening of the axioms in Lewis’ conditional logic [27] that is sound and complete for models that are based on strict weak orders, which are in bijective correspondence with total preorders.

Similar semantic clauses as in conditional logic, and thus analogous axiomatic systems, have later also been used in default reasoning [25, 36], in belief revision theory [18, 34] and in dynamic epistemic logic [7, 37]. It should also be mentioned that the axiomatizations of conditional logics with respect to their order semantics are similar to the characterizations of choice functions that are rationalizable by some preference relation [5, 35]. Moreover, the semantic clause for the conditional in orders, which is often attributed to [27], goes back to an earlier semantic clause for conditional obligations in deontic logic [19].

Preferential conditional logic has also been shown to be complete with respect to semantic interpretations that are quite different from the semantics in terms of partial orders. Most notable are the interpretation of validity of inferences between conditionals as preservation of high conditional probability [1, 15] and premise semantics, where the conditional is interpreted relative to a premise set. A premise set is a family of sets of worlds, thought of as propositions that encode relevant background information from the linguistic context [24, 40]. In this paper we provide yet another interpretation to preferential conditional logic. We show that it is complete with respect to convexity over finite sets of points in the Euclidean plane. This places conditional logic into the tradition of modal logics with a natural spatial or geometric semantics [38], most famous of which is the completeness result for S4 with respect to the topology of the real line by McKinsey and Tarski [8, 31].

To illustrate our semantics consider the finite set of points in Figure 1. Think of these points as satisfying propositional letters as indicated in their label. For instance the point $\bar {p}qr$ in the upper right corner satisfies q and r but not p. Our semantics is such that a conditional $\varphi \leadsto \psi $ is true relative to such a set of points if the set of points at which $\varphi $ is true is completely contained in the convex hull of the set of points at which both $\varphi $ and $\psi $ are true. Recall that a convex set is a set that for any two points in the set also contains the complete line segment between these points. Intuitively, these are the sets without holes or dents. The convex hull of a set is the least convex set that contains the set. As an example of a convex hull we have in Figure 1 that the shaded area is the convex hull of the three points $pqr$ , $\bar {p}qr$ and $p\bar {q}r$ . In this example the conditional $(p \lor q) \leadsto r$ is true because all points at which $p \lor q$ is true are contained in the convex hull of the points where $p \lor q$ and r are both true. The conditional $p \leadsto r$ is however not true in the example because the point $pq\bar {r}$ satisfies p but is not contained in the convex hull of the points $pqr$ and $p\bar {q}r$ , which are all the points that satisfy p and r.

Fig. 1 A finite set of points in the plane and examples of conditionals that are true or false relative to this set of points.

An equivalent formulation of our semantic clause is that a conditional $\varphi \leadsto \psi $ is true if the consequent $\psi $ is true at all the extreme points of the set of points where the antecedent $\varphi $ is true. An extreme point of some set is a point in the set that is not in the convex hull of all the other points from the set. Intuitively, the extreme points of some set are the outermost points of that set. In the example from Figure 1 we have that $pqr$ , $\bar {p}qr$ and $p\bar {q}r$ are the extreme points of the set that is shaded. On the other hand $pq \bar {r}$ is not an extreme point of the shaded set because it is in the convex hull of the points $pqr$ , $\bar {p}qr$ and $p\bar {q}r$ . Note that in this formulation of the semantic clause for a conditional $\varphi \leadsto \psi $ the extreme points of the set of points satisfying the antecedent $\varphi $ play a role that is analogous to the minimal $\varphi $ -worlds in the order semantics. Conversely, we will see later that the upward closed sets in an order play a role that is analogous to the convex sets in the geometric semantics.

In this paper we focus on a semantics that is only defined for formulas that do not contain nested conditionals and in which all propositional letters occur in the scope of a conditional. It is possible to overcome this restriction but this has no significant influence on the axiomatic questions that we are concerned with.

The main result of our paper can be formulated as follows: All finite constellation of points in the plane of the kind as shown in Figure 1 satisfy all the theorems in preferential conditional logic and every formula that is not a theorem of the logic is false in some such constellation.

The completeness proof from this paper consists of two steps:

1. 1. We first observe that preferential conditional logic is complete for a semantics in models based on convex geometries.

2. 2. We then show that every finite convex geometry can be represented by a finite set of points in the plane in such a way that all true formulas of conditional logic are preserved.

From these two steps we obtain our completeness result because by the first step every consistent formula $\varphi $ is true in some finite model based on a convex geometry and by the second step this model can be transformed into a concrete model of $\varphi $ that is based on a finite set of points in the plane. We now describe these two steps in greater detail.

In the first step we make use of the notion of a convex geometry [3, 14, 22]. Formally, convex geometries are families of sets that are closed under arbitrary intersections and have the anti-exchange property, which is a separation property that is reminiscent of the $T_0$ separation property in topology. Convex geometries are a combinatorial abstraction of the notion of a convex set in Euclidean spaces, such as the Euclidean plane. This is somewhat analogous to how topological spaces are an abstraction from the notions of open and closed sets in Euclidean spaces. The convex sets in any subspace of an Euclidean space form a convex geometry. But it is not the case that every convex geometry, or even every finite convex geometry, is isomorphic to a subspace of some Euclidean space. An easy way to see this is to observe that in any Euclidean space all singleton sets are convex, which is not enforced by the definition of a convex geometry.

One can view the semantics in convex geometries as a generalization of the order semantics over partial orders. The family of upward closed sets in any partial order form a convex geometry. Moreover, a conditional is true relative to a given partial order if and only if it is also true in the convex geometry of all upward closed sets in the order. Note that this especially means that the completeness of the order semantics entails the completeness of the semantics in convex geometries.

To understand the relation between the order semantics, the semantics in convex geometries and the semantics for convexity between finitely many points in the plane it might be helpful to think of an analogy with the different semantics for the modal logic S4. Both, preferential conditional logic and S4, have a relatively concrete relational semantics in terms of partial orders for preferential conditional logic and in terms of preorders, that are transitive and reflexive relations, for S4. Both logics have an abstract spatial or geometric semantics, the semantics in convex geometries for preferential conditional logic and the semantics in topological spaces for S4. In both cases the abstract semantics generalizes the relational semantics. For preferential conditional logic this is done by considering the upward closed sets in the partial order as a convex geometry. For S4 one can also consider the upward closed sets in a preorder, which form a so-called Alexandroff topology. Both logics additionally have a concrete spatial or geometric semantics, over a finite set of points in the plane for preferential conditional logic, and over the whole real line for S4. In both cases proving completeness for the concrete spatial or geometric semantics requires extra work. For preferential conditional logic this is the construction mentioned in the second step above and in the case of S4 it is the theorem of McKinsey and Tarski.

The semantics in convex geometries can also be seen as a further development of premise semantics. The convex sets in our semantics play the role of the complements of the sets of worlds in the premise set of premise semantics. There is, however, a crucial difference in the semantic clause with which a conditional is interpreted in a family of sets of worlds. Motivated by linguistic considerations premise semantics uses a quite sophisticated semantic clause that is insensitive to closing the family of sets under intersections. In [17, 32] it is observed that for developing proof systems for preferential conditional logic it is beneficial to lift the implicit assumption that the family of sets of worlds, relative to which the conditional is evaluated, is closed under intersections. To achieve this they use a simplified semantic clause from [29] that is sensitive to closure under intersections. When one uses the conditional with this semantic clause relative to a family of sets of worlds that is not closed under intersection different formulas turn out to be true than would be true relative to the same family of sets of worlds using the semantic clause from premise semantics. Hence, it is helpful to distinguish this new setting from premise semantics and call it neighborhood semantics, following the terminology form [32].

This neighborhood semantics is also the starting point for the categorical correspondence in [30]. Based on earlier work on the theory of choice functions [20, 23] this paper establishes a correspondence between finite Boolean algebras with additional structure that encodes non-nested preferential conditional logic and families of subsets of the set of atoms of these algebras. To obtain a well-behaved correspondence it is necessary to allow for families of sets that are not closed under intersections. However, one can require closure under unions and a separation property that is dual to the anti-exchange property mentioned above. If one then considers the complements of all the sets in a such a family of sets then one obtains a new family that is closed under arbitrary intersections and that has the anti-exchange property. Thus, one gets a convex geometry.

The second step of the proof is to show that for every finite convex geometry there is a finite subspace of the plane that satisfies the same formulas in conditional logic. This step is not trivial because, as we already explained above, not every finite convex geometry is isomorphic to a subspace of some Euclidean space. However, following [21], there has recently been a lot of literature on representing finite convex geometries inside of Euclidean spaces by some more intricate construction than just selecting an isomorphic subspace [2, 11, 12, 33]. The main result of [21], for which [33] give a much shorter proof, is that every finite convex geometry is isomorphic to the convex geometry on a finite set of points in some Euclidean space, if we use an alternative notion of convex set that is slightly different from the standard notion of convex set. Moreover, [33] shows that every finite convex geometry is isomorphic to the convexity over a set of polygons in the plane, using the standard notion of convexity, but now every point in the original convex geometry corresponds to a whole polygon in the plane. The papers [2, 11, 12] investigate to what extent it is possible to prove the same result using circles instead of polygons.

In the second step of the completeness proof we make use of the representation by [33], where a finite convex geometry is represented by a set of polygons. This construction is such that the extreme points of any two polygons in the set are disjoint. One can thus define a function that maps an extreme point of some polygon in the set to the point in the original convex geometry that the polygon is representing. The domain of this function can be considered to be the finite subspace of the plane consisting of all the points that are an extreme point of one of the polygons. The crucial insight is then that this function is a strong morphism of convex geometries in a sense defined in [30], which guarantees the preservation of true formulas in conditional logic.

The structure of this paper is as follows: In Section 2 we review the notion of a convex geometry and fix the necessary terminology. In Section 3 we present the syntax of preferential conditional logic and define its semantics in convex geometries. Section 4 contains a self-contained completeness result for preferential conditional logic with respect to its semantics in convex geometries. In Section 5 we discuss the notion of morphism between finite convex geometries from [30] that preserves the truth of all formulas in conditional logic. In Section 6 we show that the representation of finite convex geometries in the plane from [33] yields such a morphism. In Section 7 we put the results from the previous sections together to prove the completeness of preferential conditional logic with respect to convexity between finite sets of points in the plane. Moreover, we show that this result cannot be improved to a completeness result with respect to sets of points on the real line.

2. Convex geometries

In this section we recall some basic terminology and results related to abstract convex geometries. For a more thorough introduction see [3, 14] or [22, Chapter 3]

2.1. Basic definitions

A convex geometry $(W,\mathcal {C})$ is a set W together with a family $\mathcal {C} \subseteq \mathcal {P} W$ of convex sets that has the following properties:

1. 1. $\mathcal {C}$ is closed under arbitrary intersections, that is, $\bigcap \mathcal {X} \in \mathcal {C}$ for all $\mathcal {X} \subseteq \mathcal {C}$ .

2. 2. $\mathcal {C}$ has the anti-exchange property that for every $C \in \mathcal {C}$ and all $x,y \in W$ with $x,y \notin C$ and $x \neq y$ there is a $D \in \mathcal {C}$ with $C \subseteq D$ such that $x \in D$ and $y \notin D$ , or $x \notin D$ and $y \in D$ .

We sometimes use just W, or just $\mathcal {C}$ , to denote the convex geometry $(W,\mathcal {C})$ consisting of both W and $\mathcal {C}$ . Thereby it is assumed that the identity of the other component is understood from the context.

Most authors require that $\emptyset \in \mathcal {C}$ . We do not require this because, as we explain in Remark 3.4, it is convenient for the semantics of conditional logic to allow for convex geometries in which the empty set is not convex.

We call the complements of convex sets feasible, following the literature on antimatroids [22, Chapter 3]. The family of all feasible sets is denoted by $\mathcal {F} = \{W \setminus C \mid C \in \mathcal {C}\}$ . We use the notation $\overline {X} = W \setminus X$ to denote the complement of some $X \subseteq W$ .

Given any subset $X \subseteq W$ its convex hull $\mathrm {co}({X}) \subseteq W$ is defined as

$$ \begin{align*} \mathrm{co}({X}) = \bigcap \{C \in \mathcal{C} \mid X \subseteq C\}. \end{align*} $$

Because convex sets are closed under intersection the convex hull $\mathrm {co}({X})$ is a convex set. In fact it is the least convex set containing X. One can also show that as an operation on $\mathcal {P} W$ the convex hull $\mathrm {co} : \mathcal {P} W \to \mathcal {P} W$ defines a closure operator, meaning that $X \subseteq Y$ implies $\mathrm {co}({X}) \subseteq \mathrm {co}({Y})$ , $X \subseteq \mathrm {co}({X})$ , and $\mathrm {co}({\mathrm {co}({X})}) \subseteq \mathrm {co}({X})$ for all $X,Y \subseteq W$ . The relation between the family of convex sets and the convex hull is an instance of the well-known correspondence between complete meet-semilattices and closure operators.

For every subset $X \subseteq W$ , where $(W,\mathcal {C})$ is a convex geometry, we define the relative convexity on X as follows: A set $C \subseteq X$ is convex in the relative convexity if there is some set $C'$ that is convex in W such that $C = C' \cap X$ . It is not hard to see that the relative convexity is a convex geometry.

The prime examples of a convex geometry are the families of convex sets in the Euclidean space $\mathbb {R}^n$ for every dimension n. A set $C \subseteq \mathbb {R}^n$ is convex if it contains the complete line segment between any two of its points. This means that for all $x,y \in C$ we need $\{\lambda x + (1 - \lambda )y \mid \lambda \in [0,1]\} \subseteq C$ . We call the family of convex sets defined in this way the standard convexity. It is well known that the convex hull of a set $X \subseteq \mathbb {R}^n$ in the standard convexity is the set of all convex combinations of points in X, where a convex combination of $x_1,\dots ,x_k \in X$ is any point that can be written as $\sum _{i = 1}^k \lambda _i x_i$ , for $\lambda _1,\dots ,\lambda _k \geq 0$ with $\sum _{i = 1}^k \lambda _i = 1$ .

Another example of convex geometries are partially ordered sets. Because the standard semantics of conditional logic is usually defined over partially ordered sets this example provides the link between convex geometries and conditional logic. Recall that a partially ordered set, or just poset, is a set W together with a partial order $\leq $ on W, where a partial order is a binary relation that is reflexive, transitive and anti-symmetric. Given a partial order $\leq $ on W we define the upset convexity $\mathcal {U}({\leq })$ on W to consist of all the upward closed sets in $\leq $ , that is, all the sets C such that $x \in C$ and $x \leq y$ implies $y \in C$ . The convex hull of a set $X \subseteq W$ is then identical to the set ${{X}\!\!\uparrow } = \{y \in W \mid x \leq y \mbox { for some } x \in X\}$ , which is the upward closure of X. Note that $\mathcal {U}({\leq })$ is just the Alexandroff topology associated to the order $\leq $ . Closure under arbitrary intersections is thus obvious. The anti-exchange property follows from the $T_0$ separation property of any Alexandroff topology that is defined from a poset. The reason that in this paper we assume that the order semantics of conditional logic is based on posets instead of just preorders is that the Alexandroff topology of a preorder that is not anti-symmetric does not have the $T_0$ separation property and thus it is not a convex geometry.

2.2. Extreme points

A point $x \in X$ in some set $X \subseteq W$ in a convex geometry $(W,\mathcal {C})$ is an extreme point of X if $x \notin \mathrm {co}({X \setminus \{x\}})$ . The intuition is that an extreme point of X is an outermost point of the set X. The extreme points of a set in the upset convexity of a poset are precisely the minimal elements of the set. We write $\mathrm {ex}({X}) \subseteq X$ for the set of all of its extreme points of X. The following proposition yields an alternative characterization for the set of extreme points.

Proposition 2.1. For every $X \subseteq W$ we have $\mathrm {ex}({X}) = \bigcap \{Y \subseteq X \mid X \subseteq \mathrm {co}({Y})\}$ .

Proof. For the contrapositive of the $\subseteq $ -inclusion take $x \in X$ such that there is some $Y \subseteq X$ with $x \notin Y$ and $X \subseteq \mathrm {co}({Y})$ . Then $x \in \mathrm {co}({Y}) \subseteq \mathrm {co}({X \setminus \{x\}})$ and so x is not an extreme point of X.

For the contrapositive of the $\supseteq $ -inclusion consider an $x \in X$ with $x \in \mathrm {co}({X \setminus \{x\}})$ . Set $Y = X \setminus \{x\}$ , and observe that $X \subseteq \mathrm {co}({Y})$ but $x \notin Y$ . □

For finite sets one has the following relation between extreme points and the convex hull operator.

Theorem 2.2. The following are equivalent for every finite set $K \subseteq W$ in a convex geometry $\mathcal {C}$ on W:

$$ \begin{align*} \mathrm{ex}({K}) \subseteq X \quad \mbox{iff} \quad K \subseteq \mathrm{co}({K \cap X}) \qquad \mbox{ for all } X \subseteq W. \end{align*} $$

Proof. This follows from item 3 of Theorem 1 in [30] and the observation that every finite set is smooth in the terminology of that paper. Note that the proof of this theorem uses the characterization from Proposition 2.1 as the definition of the extreme points. □

Lastly, we define the notion of a polygon. A polygon $P \subseteq W$ in a convex geometry $(W,\mathcal {C})$ is any set that can be written of the form $P = \mathrm {co}({P'})$ for a finite set $P' \subseteq P$ . Clearly every such polygon has only a finite number of extreme points because for any $x \in P$ with $x \notin P'$ we have that $x \in \mathrm {co}({P'}) \subseteq \mathrm {co}({P \setminus \{x\}})$ .

3. Conditional logic

In this section we discuss the syntax of preferential conditional logic that we use in this paper and explain its semantics in convex geometries.

3.1. Syntax of one-step preferential conditional logic

Conditional logics are commonly formulated in a classical propositional modal language with one binary modality $\leadsto $ , which forms the conditional $\varphi \leadsto \psi $ with antecedent $\varphi $ and consequent $\psi $ [10, 27]. That $\leadsto $ is a modality means that one can nest conditionals, as for example in the formula $(((p \leadsto q) \leadsto r) \land q) \rightarrow r$ . In this paper we choose not to deal with the complications arising from nested conditionals and instead just work with one-step formulas that are Boolean combination of conditionals over propositional formulas. This is not a substantial restriction for most conditional logics, because the axiomatizations of these logics constrain only one layer of conditionals and then are extended freely to formulas of larger conditional depth. Readers familiar with coalgebraic modal logic might recognize this as the one-step setup that is common in coalgebraic logic [26]. We sketch in Remarks 3.3 and 7.2 below how one would extend our semantics and completeness result to formulas with nested conditionals.

To be more precise about our setting fix a set $\mathsf {Prop}$ of propositional letters and consider the grammar

$$ \begin{align*} \varphi_0 & ::= p \mid \neg \varphi_0 \mid \varphi_0 \land \varphi_0, & \mbox{where } p \in \mathsf{Prop}, \\ \varphi_1 & ::= \varphi_0 \leadsto \varphi_0 \mid \neg \varphi_1 \mid \varphi_1 \land \varphi_1. \end{align*} $$

Let $\mathcal {L}_0$ be the set of formulas generated from $\varphi _0$ and $\mathcal {L}_1$ the set of formulas generated from $\varphi _1$ . Note that $\mathcal {L}_0$ is just the language of classical propositional logic. In both $\mathcal {L}_0$ and $\mathcal {L}_1$ we use further Boolean connectives, such as $\lor $ , $\rightarrow $ , and $\leftrightarrow $ , as abbreviations with their usual meaning in classical logic. To omit parenthesis we assume that $\neg $ binds stronger than $\land $ and $\lor $ , which in turn bind stronger than $\leadsto $ , $\rightarrow $ and $\leftrightarrow $ .

In our axiomatization of preferential conditional logic we follow the one-step setup in that we only consider proofs in which all formulas are either from $\mathcal {L}_0$ or from $\mathcal {L}_1$ . Hence, proofs are not allowed to contain nested conditionals or formulas with conditionals that contain propositional letters that are not in the scope of a conditional.

As axioms we allow all instances of propositional tautologies in $\mathcal {L}_0$ plus the following axioms that are in $\mathcal {L}_1$ :

$$ \begin{align*} \mbox{(Id)} \ & p \leadsto p, & \mbox{(And)} \ & (p \leadsto q) \land (p \leadsto r) \rightarrow (p \leadsto q \land r), \\ \mbox{(CM)} \ & (p \leadsto q) \land (p \leadsto r) \rightarrow (p \land r \leadsto q), & \mbox{(Or)} \ & (p \leadsto q) \land (r \leadsto q) \rightarrow (p \lor r \leadsto q). \end{align*} $$

We have the following inference rules: First, modus ponens, where the premises are either both in $\mathcal {L}_0$ or both in $\mathcal {L}_1$ ; second, uniform substitution $\varphi /\varphi [\sigma ]$ , where either $\varphi \in \mathcal {L}_0$ and $\sigma : \mathsf {Prop} \to \mathcal {L}_i$ for some $i \in \{0,1\}$ , or $\varphi \in \mathcal {L}_1$ and $\sigma : \mathsf {Prop} \to \mathcal {L}_0$ ; and third, we have the following two inference rules, with premises in $\mathcal {L}_0$ and conclusions in $\mathcal {L}_1$ :

$$ \begin{align*} \mbox{(LLE)} \ \frac{\varphi \leftrightarrow \chi}{(\varphi \leadsto \psi) \leftrightarrow (\chi \leadsto \psi)}, \qquad \mbox{and} \qquad \mbox{(RW)} \ \frac{\psi \rightarrow \chi}{(\varphi \leadsto \psi) \rightarrow (\varphi \leadsto \chi)}. \end{align*} $$

As is common in Hilbert-style axiomatizations we understand these rules such that the conclusion is derivable whenever the premises are derivable. In the derivation system given here there is no notion of a proof with open assumptions, and the rules (LLE) and (RW) would no longer be sound for proofs with open assumptions.

We use the standard notions of derivability and consistency for formulas in either $\mathcal {L}_0$ or $\mathcal {L}_1$ with respect to the above axiomatic system. We also write $\vdash \varphi $ if some $\varphi \in \mathcal {L}_i$ for some $i \in \{0,1\}$ is derivable

The axioms and rules given here and their names closely follow the rules of System P in the literature on nonmonotonic consequence relations [25]. It is however easy to show that these rules and axioms are interderivable with the rules and axioms from [9] or [41].

The following proposition gathers examples of derivable formulas and rules.

Proposition 3.1. The following formulas are derivable in preferential conditional logic:

$$ \begin{align*} \mbox{(WCM)} \ & (p \leadsto q \land r) \rightarrow (p \land q \leadsto r), & \mbox{(CCut)} \ & (p \leadsto q) \land (p \land q \leadsto r) \rightarrow (p \leadsto r), \\ \mbox{(S)} \ & (p \land q \leadsto r) \rightarrow (p \leadsto \neg q \lor r), & \mbox{(CCut')} \ & (p \leadsto q) \land (q \leadsto r) \rightarrow (p \lor q \leadsto r). \end{align*} $$

The following rule is derivable in preferential conditional logic:

$$ \begin{align*} \mbox{(R)} \ \frac{\psi \rightarrow \chi}{(\varphi \leadsto \psi) \rightarrow ((\varphi \land \chi) \lor \psi \leadsto \psi)}. \end{align*} $$

Proof. Derivation of (WCM): With (RW) we obtain that $(p \leadsto q \land r) \rightarrow (p \leadsto q)$ and $(p \leadsto q \land r) \rightarrow (p \leadsto r)$ are derivable. Because by (CM) the formula $(p \leadsto q) \land (p \leadsto r) \rightarrow (p \land r \leadsto q)$ is an axiom we can then use propositional reasoning to derive $(p \leadsto q \land r) \rightarrow (p \land q \leadsto r)$ .

In the remaining derivations we omit the steps that are propositional and focus on the axioms or rules involving the conditional. We are confident that the reader is able to supply the missing details. As an example a short description of the above derivation of (WCM) would be as follows: From $p \leadsto q \land r$ we can derive with the help of (RW) that $p \leadsto q$ and that $p \leadsto r$ . With (CM) it follows that $p \land q \leadsto q$ .

Derivation of (S): First observe that from (Id) we get that $p \land \neg q \leadsto p \land \neg q$ and with (RW) we obtain $p \land \neg q \leadsto \neg q \lor r$ . Then use (RW) again to obtain $p \land q \leadsto \neg q \lor r$ from $p \land q \leadsto r$ . We can use (Or) to get $(p \land q) \lor (p \land \neg q) \leadsto \neg q \lor r$ . By (LLE) we obtain $p \leadsto \neg q \lor r$ .

Derivation of (CCut): From $p \land q \leadsto r$ it follows by (S) that $p \leadsto \neg q \lor r$ . Combining this with the assumption $p \leadsto q$ using (And) we obtain $p \leadsto (\neg q \lor r) \land q$ . By (RW) follows that $p \leadsto r$ because $(\neg q \lor r) \land q \rightarrow r$ is a theorem of classical propositional logic.

Derivation of (CCut’): First derive $p \lor q \leadsto q$ using (Or), (Id) and the assumption $p \leadsto q$ . Then observe that by (LLE) we obtain $(p \lor q) \land q \leadsto r$ from the assumption $q \leadsto r$ . Then apply (CCut) to $p \lor q \leadsto q$ and $(p \lor q) \land q \leadsto r$ , substituting the letter p in (CCut) with $p \lor q$ . This yields $p \lor q \leadsto r$ .

Derivation of (R): Because of the premise that $\psi \rightarrow \chi $ we obtain $\psi \leadsto \chi $ because of (RW) and the instance $\psi \leadsto \psi $ of (Id). Applying (CM) to $\varphi \leadsto \psi $ and $\psi \leadsto \chi $ yields $\varphi \land \chi \leadsto \psi $ . Because $\psi \leadsto \psi $ holds by (Id) we can use (Or) to get $(\varphi \land \chi ) \lor \psi \leadsto \psi $ . □

3.2. Semantics of the conditional in convex geometries

To give a semantics to the conditional we are using models that are based on abstract convex geometries as defined in Section 2. Thus, we define a model $M = (W,\mathcal {C},V)$ to consist of

• • a set W, whose elements are called points or worlds,

• • a convex geometry $\mathcal {C} \subseteq \mathcal {P} W$ over W, and

• • a function $V : \mathsf {Prop} \to \mathcal {P} W$ that is called the valuation function.

As is usual in modal logics the valuation function V is used to assign meanings to the propositional letters in $\mathsf {Prop}$ . This assignment of meanings is extended to propositional formulas from $\mathcal {L}_0$ in the standard way with the recursive clauses

$$ \begin{align*} {[\kern-1.2pt[ {p} ]\kern-1.2pt]}_V = V(p), \qquad {[\kern-1.2pt[ {\neg \varphi} ]\kern-1.2pt]}_V = W \setminus {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]}_V, \qquad \mbox{and} \qquad {[\kern-1.2pt[ {\varphi \land \psi} ]\kern-1.2pt]}_V = {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]}_V \cap {[\kern-1.2pt[ {\psi} ]\kern-1.2pt]}_V. \end{align*} $$

We often write ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ for ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_V$ if V is clear from the context.

We use the standard clauses for the propositional connectives over $\mathcal {L}_1$ relative to the model $M = (W,\mathcal {C},V)$ :

$$ \begin{align*} M \models \neg \varphi \quad \mbox{iff} \quad \mbox{not } M \models \varphi, \qquad \mbox{and} \qquad M \models \varphi \land \psi \quad \mbox{iff} \quad M \models \varphi \mbox{ and } M \models \psi. \end{align*} $$

The conditional has the following semantics:

$$ \begin{align*} &M \models \varphi \leadsto \psi \quad \text{iff} \quad \text{for all}\ C \in \mathcal{C}\ \text{with}\ {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]} \nsubseteq C\ \text{there is a}\ D \in \mathcal{C} \\ &\qquad\qquad\qquad\qquad \> \text{with}\ C \subseteq D\ \text{and}\ {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]} \nsubseteq D\ \text{such that} {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]} \subseteq D \cup {[\kern-1.2pt[ {\psi} ]\kern-1.2pt]}. \end{align*} $$

The truth of formulas in $\mathcal {L}_1$ is only relative to the model M and does not need to be relativized to a world of evaluation. This is possible because we do not nest conditionals and all propositional letters that occur in a formula from $\mathcal {L}_1$ need to be in the scope of some conditional.

We use the standard notion of validity, calling a formula $\varphi \in \mathcal {L}_1$ valid iff $M \models \varphi $ for all models M. As usual in modal logic we also call a formula valid over a class of models or convex geometries if it is true in all models from this class or it is true in all models that are based on a convex geometry from the class.

Preferential conditional logic is sound for this semantics. Note that the proof of soundness never uses the special properties of the convex geometry $\mathcal {C} \subseteq \mathcal {P} W$ . Soundness already holds for arbitrary families of sets.

Proposition 3.2. If $\varphi \in \mathcal {L}_1$ is derivable in preferential conditional logic then $\varphi $ is valid.

Proof. One first shows, analogous to the soundness of propositional logic, that if $\vdash \varphi $ for some $\varphi \in \mathcal {L}_0$ then ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_V = W$ for all valuations $V : \mathsf {Prop} \to \mathcal {P} W$ . Using this one can show the statement of the proposition with a routine induction on the length of derivations in the axiomatic system. Here we only treat the case of the axiom (Or) and leave all other cases, which are easier, to the reader.

Consider any model $M = (W,\mathcal {C},V)$ . We want to show that $M \models (p \leadsto q) \land (r \leadsto q) \rightarrow (p \lor r \leadsto q)$ . Assume that $M \models p \leadsto q$ and that $M \models r \leadsto q$ . To show $M \models p \lor r \leadsto q$ consider any convex $C \in \mathcal {C}$ such that ${[\kern -1.2pt[ {p \lor r} ]\kern -1.2pt]}_V \nsubseteq C$ . We need to find a convex $D \in \mathcal {C}$ with $C \subseteq D$ , ${[\kern -1.2pt[ {p \lor r} ]\kern -1.2pt]}_V \nsubseteq D$ and ${[\kern -1.2pt[ {p \lor r} ]\kern -1.2pt]}_V \subseteq D \cup {[\kern -1.2pt[ {q} ]\kern -1.2pt]}_V$ . Because ${[\kern -1.2pt[ {p \lor r} ]\kern -1.2pt]}_V \nsubseteq C$ it follows that either ${[\kern -1.2pt[ {p} ]\kern -1.2pt]}_V \nsubseteq C$ or ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_V \nsubseteq C$ . Consider the case where ${[\kern -1.2pt[ {p} ]\kern -1.2pt]}_V \nsubseteq C$ . The reasoning in the other case where ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_V \nsubseteq C$ is completely analogous. Because $M \models p \leadsto q$ it follows from ${[\kern -1.2pt[ {p} ]\kern -1.2pt]}_V \nsubseteq C$ that there is some $C' \in \mathcal {C}$ with $C \subseteq C'$ , ${[\kern -1.2pt[ {p} ]\kern -1.2pt]}_V \nsubseteq C'$ and ${[\kern -1.2pt[ {p} ]\kern -1.2pt]}_V \subseteq C' \cup {[\kern -1.2pt[ {q} ]\kern -1.2pt]}_V$ . Then distinguish cases depending on whether ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_V \subseteq C'$ .

If ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_V \subseteq C'$ then we can let $D = C'$ because ${[\kern -1.2pt[ {p \lor r} ]\kern -1.2pt]}_V \nsubseteq C'$ follows from ${[\kern -1.2pt[ {p} ]\kern -1.2pt]}_V \nsubseteq C'$ and ${[\kern -1.2pt[ {p \lor r} ]\kern -1.2pt]}_V \subseteq C' \cup {[\kern -1.2pt[ {q} ]\kern -1.2pt]}_V$ follows from ${[\kern -1.2pt[ {p} ]\kern -1.2pt]}_V \subseteq C' \cup {[\kern -1.2pt[ {q} ]\kern -1.2pt]}_V$ together with ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_v \subseteq C'$ .

If ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_V \nsubseteq C'$ then we can apply the assumption $M \models r \leadsto q$ to obtain a $C'' \in \mathcal {C}$ with $C' \subseteq C''$ , ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_V \nsubseteq C''$ and ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_V \subseteq C'' \cup {[\kern -1.2pt[ {q} ]\kern -1.2pt]}_V$ . We can let $D = C''$ . It clearly holds that $C \subseteq C''$ . That ${[\kern -1.2pt[ {p \lor r} ]\kern -1.2pt]}_V \nsubseteq C''$ follows from ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_V \nsubseteq C''$ . Lastly, it holds that ${[\kern -1.2pt[ {p \lor r} ]\kern -1.2pt]}_V \subseteq C'' \cup {[\kern -1.2pt[ {q} ]\kern -1.2pt]}_V$ because ${[\kern -1.2pt[ {p} ]\kern -1.2pt]}_V \subseteq C' \cup {[\kern -1.2pt[ {q} ]\kern -1.2pt]}_V$ , $C' \subseteq C''$ and ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}_V \subseteq C'' \cup {[\kern -1.2pt[ {q} ]\kern -1.2pt]}_V$  □

If we allow $\mathcal {C} \subseteq \mathcal {P} W$ to be an arbitrary family of sets then our semantics is equivalent to the neighborhood semantics that has already been used in the literature [17, 29, 32]. Thus the semantics in convex geometries specializes the neighborhood semantics for preferential conditional logic. To see why our semantics specializes neighborhood semantics let us dualize the semantic clause such that it is expressed in terms of the family $\mathcal {F}$ of feasible sets. It then becomes the clause

$$ \begin{align*} &M \models \varphi \leadsto \psi \quad \text{iff} \quad \text{for all}\ F \in \mathcal{F}\ \text{with}\ F \cap {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]} \neq \emptyset\ \text{there is a}\ G \in \mathcal{F} \\ &\qquad\qquad\qquad\qquad \> \text{with}\ G \subseteq F\ \text{and}\ G \cap {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]} \neq \emptyset\ \text{such that}\ G \cap {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]} \subseteq {[\kern-1.2pt[ {\psi} ]\kern-1.2pt]}. \end{align*} $$

This clause is precisely the same as the clause that is used for arbitrary families $\mathcal {F} \subseteq \mathcal {P} W$ in [17, 29, 32]. It can be traced back to much earlier approaches in premise semantics [24, 39, 40] and can also be seen as the generalization of the clause from [16] to the infinite case.

Remark 3.3. By making the convex geometry in a model depending on the world of evaluation, one can extend our semantics to deal with nested conditionals. This means that we would consider models of the form $M = (W,\mathcal {C},V)$ , where $\mathcal {C} : W \to \mathcal {P} \mathcal {P} W$ is such that $\mathcal {C}(w)$ is a convex geometry for all $w \in W$ . The conditional is then evaluated relative to a world w by using the above clause relative to the convex geometry $\mathcal {C}(w)$ . In [17, 32] this kind of semantics is used, however, with the dualized semantic clause and without requiring that $\mathcal {C}(w)$ is a convex geometry.

Remark 3.4. Observe that if in some model $M = (W,\mathcal {C},V)$ we have that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \subseteq C$ for all $C \in \mathcal {C}$ then $M \models \varphi \leadsto \bot $ . In this sense the worlds in $\bigcap \mathcal {C}$ can be thought of as impossible worlds. We do not require that $\emptyset \in \mathcal {C}$ because we want to allow W to contain such impossible worlds. For the results of this paper this is not crucial because, as we argue in Proposition 5.1 below, impossible worlds can always be eliminated from W, without changing the set of true conditionals. In more complex settings, such as the nested semantics from Remark 3.3 or the duality results from [30], it is however convenient to allow for impossible worlds.

If the antecedent of a conditional $\varphi \leadsto \psi $ evaluates to a finite set ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ then the semantic clause for the conditional can be simplified.

Proposition 3.5. For any model $M = (W,\mathcal {C},V)$ and $\varphi , \psi \in \mathcal {L}_0$ such that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \subseteq W$ is finite the following are equivalent:

1. 1. $M \models \varphi \leadsto \psi $ ,

2. 2. $\mathrm {ex}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}}) \subseteq {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}$ , and

3. 3. ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \subseteq \mathrm {co}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}})$ .

Proof. The equivalence of items (2.) and (3.) follows from Theorem 2.2. Hence, it suffices to show that items (1.) and (3.) are equivalent.

Assume that $M \models \varphi \leadsto \psi $ and consider any $C \in \mathcal {C}$ such that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]} \subseteq C$ . We want to show that then ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \subseteq C$ . If this was not the case then it would follow from $M \models \varphi \leadsto \psi $ that there is some $D \in \mathcal {C}$ with $C \subseteq D$ such that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \nsubseteq D$ and ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \subseteq D \cup {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}$ . These latter two inclusions entail that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]} \nsubseteq D$ , contradicting ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]} \subseteq C \subseteq D$ .

For the other direction assume that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \subseteq \mathrm {co}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}})$ . We derive a contradiction from the assumption that not $M \models \varphi \leadsto \psi $ . The goal is to construct an infinite, strictly increasing chain $C_0 \subset C_1 \subset \dots $ of convex sets such that $C_i \nsubseteq {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ and $(C_{i + 1} \setminus C_i) \cap {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \neq \emptyset $ for all $i \in \mathbb {N}$ . This then contradicts the assumption that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ is finite.

Because we assume that not $M \models \varphi \leadsto \psi $ there is some $C \in \mathcal {C}$ with $C \nsubseteq {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ such that for every $D \in \mathcal {C}$ with $C \subseteq D$ and $D \nsubseteq {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ we have that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \nsubseteq D \cup {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}$ . Let $C_0 = C$ .

To construct $C_{i + 1}$ from $C_i$ assume that we have a $C_i \in \mathcal {C}$ such that $C_i \nsubseteq {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ . From the assumption that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \subseteq \mathrm {co}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}})$ it follows that there is some $x \in {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}$ such that $x \notin C_i$ . Because $C = C_0 \subseteq C_i$ we obtain from the choice of C that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \nsubseteq D \cup {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}$ . Thus, there is some $y \in {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ such that $y \notin C_i$ and $y \notin {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}$ . Because $x \in {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}$ it follows that $x \neq y$ and thus we can apply the anti-exchange property to obtain a convex set $C^+$ with $C_i \subseteq C^+$ that contains precisely one of x and y. We set $C_{i + 1} = C^+$ . Since both x and y are in ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ , but none of them is in $C_i$ , it follows that $C_{i + 1} \nsubseteq {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}$ and $(C_{i + 1} \setminus C_i) \cap {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \neq \emptyset $ . □

Example 3.6. The picture in Figure 1 can be taken to show the model $M = (W,\mathcal {C},V)$ with

• • $W = \{x,y,z,u,v\} \subseteq \mathbb {R}^2$ with $x = (0,5)$ , $y = (4,5)$ , $z = (2.4,3)$ , $u = (1.9,4.3)$ , $v = (1.2,1.5)$ ,

• • $\mathcal {C}$ is the relative convexity of W in $\mathbb {R}^2$ , and

• • $V(p) = \{x,z,u\}$ , $V(q) = \{x,y,u\}$ and $V(r) = \{x,y,z\}$ .

Example 3.7. As the running example for our completeness proof we use the following formula:

$$ \begin{align*} \alpha &= (\top \leadsto p) \land (q \leadsto p) \land (\neg (p \leftrightarrow q) \leadsto p) \land \neg (\neg q \leadsto p) \land \neg ((p \leftrightarrow q) \leadsto p) \\&\quad \land \neg (\neg p \leadsto \neg q). \end{align*} $$

A relatively simple model $M = (W,\mathcal {C},V)$ in which $\alpha $ is true is as follows:

• • $W = \{pq,p\bar {q},\bar {p}q,\bar {p}\bar {q}\}$ is a four-element set,

• • $\mathcal {C} = \{\emptyset ,\{\bar {p}q\},\{\bar {p}\bar {q}\},\{pq,\bar {p}q\},\{p\bar {q},\bar {p}q\},\{\bar {p}q,\bar {p}\bar {q}\},W \setminus \{p\bar {q}\},W \setminus \{pq\},W\}$ , and

• • $V(p) = \{pq,p\bar {q}\}$ and $V(q) = \{pq,\bar {p}q\}$ .

Example 3.8. Every model in the order semantics of the form $M = (W,\leq ,V)$ , where $\leq $ is a partial order over W, yields a model $M' = (W,\mathcal {U}({\leq }),V)$ in the sense defined here. In fact M and $M'$ satisfy the same conditionals. In the finite case this follows from the reformulation of our semantic clause in Proposition 3.5 and the observation that the minimal elements of some set in a poset are precisely its extreme points in the upset convexity. In the infinite case we leave it to the reader to check that the semantic clause for the conditional relative to an infinite partial order $\leq $ from [9, 41]

$$ \begin{align*} &M \models \varphi \leadsto \psi \quad \text{iff} \quad \text{for all}\ w \in {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]}\ \text{there is a}\ v \leq w\ \text{with}\ v \in {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]} \\ &\quad\quad\quad\quad\quad\quad\> \text{such that for all}\ u \leq v\ \text{if}\ u \in {[\kern-1.2pt[ {\varphi} ]\kern-1.2pt]}\ \text{then}\ u \in {[\kern-1.2pt[ {\psi} ]\kern-1.2pt]} \end{align*} $$

is equivalent to the semantic clause given above with respect to the upset convexity $\mathcal {U}({\leq })$ . This connection between the order semantics and the semantics in abstract convex geometries has as a precursor the connection between the order semantics and premise semantics that was already observed in [28, 29, 39].

4. Completeness for abstract convex geometries

This section contains a completeness result for preferential conditional logic with respect to the models from Section 3.2 that are based on abstract convex geometries. It reads as follows:

Theorem 4.1. Every one-step formula $\varphi \in \mathcal {L}_1$ that is consistent in preferential conditional logic is true in a model of the form $(W,\mathcal {C},V)$ , where W is a finite set and $\mathcal {C}$ a convex geometry over W.

This theorem is a consequence of at least two results that already exist in the literature:

1. 1. Theorem 4.1 can be obtained from the well-known completeness with respect to the semantics in posets [9, 41] together with the observation from Example 3.8 that every model based on a poset gives rise to a model based on a convex geometry that satisfies the same formulas. However, it needs to be checked that the necessary formal proofs go through with our more restrictive one-step proof system and that the completeness construction yields a finite model with an anti-symmetric ordering.

2. 2. An alternative approach is to connect to the nonmonotonic consequence relations from [25] and then apply the duality result from [30]. Observe that every consistent formula $\varphi \in \mathcal {L}_1$ gives rise to a nonmonotonic consequence relation satisfying the axioms of System P, by taking iff $\vdash \varphi \rightarrow (\alpha \leadsto \beta )$ . If one then moves to the free Boolean algebra over $\mathsf {Prop}$ , which we can assume to be finite, then one is precisely on the algebraic side of the dual correspondence from [30]. On the spatial side of this duality one then obtains a convex geometry over the atoms of the free Boolean algebra on $\mathsf {Prop}$ .

For readers who are not comfortable with adapting these existing results we give a direct proof of Theorem 4.1.

To prove Theorem 4.1 we need to define a finite model $M = (W,\mathcal {C},V)$ such that $M \models \varphi $ . We first discuss the definition of the domain W and the valuation $V : \mathsf {Prop} \to \mathcal {P} W$ . We let W be the set of all assignments $a : \mathsf {Prop} \to \{0,1\}$ in the sense of classical propositional logic. This set is finite because we can assume $\mathsf {Prop}$ to be finite since there are only finitely many propositional letters occurring in $\varphi $ . The valuation $V : \mathsf {Prop} \to \mathcal {P} W$ is defined such that $V(p) = \{a \in W \mid a(p) = 1\}$ for all $p \in \mathsf {Prop}$ . By the completeness theorem for classical propositional logic we have that ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]}_V \subseteq {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]}_V$ iff $\vdash \alpha \rightarrow \beta $ for all $\alpha ,\beta \in \mathcal {L}_0$ . We use this fact in the continuation of this proof without explicitly mentioning it. We also need that for every set $Y \subseteq W$ there is a characteristic formula ${\chi ({Y})} \in \mathcal {L}_0$ such that ${[\kern -1.2pt[ {{\chi ({Y})}} ]\kern -1.2pt]}_V = Y$ . Because $\mathsf {Prop}$ and W are finite we can define ${\chi ({Y})} = \bigvee _{a \in Y} {\chi ({a})}$ , where ${\chi ({a})} = \bigwedge \{p \mid a(p) = 1\} \land \bigwedge \{\neg p \mid a(p) = 0\}$ .

To define the convex geometry $\mathcal {C}$ we first fix a maximally consistent set $\Sigma \subseteq \mathcal {L}_1$ with $\varphi \in \Sigma $ . Because $\varphi $ is consistent such a set exists by Lindenbaum’s Lemma. Below we are implicitly going to make use of the fact that $\Sigma $ is closed under provable implications, that is, if $\vdash \bigwedge \Sigma ' \rightarrow \rho $ for some finite $\Sigma ' \subseteq \Sigma $ then $\rho \in \Sigma $ . We then define the family of convex sets as follows:

$$ \begin{align*} \mathcal{C} = \{C \subseteq W \mid {[\kern-1.2pt[ {\alpha} ]\kern-1.2pt]} \cap {[\kern-1.2pt[ {\beta} ]\kern-1.2pt]} \subseteq C \mbox{ implies } {[\kern-1.2pt[ {\alpha} ]\kern-1.2pt]} \subseteq C \mbox{ for all } \alpha,\beta \in \mathcal{L}_0 \mbox{ with } \alpha \leadsto \beta \in \Sigma \}. \end{align*} $$

Define the model $M = (W,\mathcal {C},V)$ . To finish the proof of Theorem 4.1 we need to verify that $\mathcal {C}$ is a convex geometry and that $M \models \varphi $ . It is straightforward to check that $\mathcal {C}$ is closed under intersections. Thus it follows from Lemma 4.3 below, which states that $\mathcal {C}$ has the anti-exchange property, that $\mathcal {C}$ is a convex geometry. That $M \models \varphi $ follows from Lemma 4.4, which states that $M \models \theta $ iff $\theta \in \Sigma $ for all $\theta \in \mathcal {L}_1$ .

To prove Lemmas 4.3 and 4.4 we need the following syntactic characterization of the convex hull operator in $\mathcal {C}$ :

$$ \begin{align*} h : \mathcal{P} W & \to \mathcal{P} W, \\ Y & \mapsto \bigcup \{{[\kern-1.2pt[ {\delta} ]\kern-1.2pt]} \subseteq W \mid \delta \leadsto {\chi({Y})} \in \Sigma\}. \end{align*} $$

It is possible to show that h is the closure operator associated to the meet semilattice $\mathcal {C} \subseteq \mathcal {P} W$ . We do not do this here because the completeness proof only needs the following weaker properties of h:

Lemma 4.2. For all $Y \subseteq W$ it holds that

1. 1. $Y \subseteq {h({Y})}$ , and

2. 2. ${h({Y})} \in \mathcal {C}$ .

Proof. For item 1. observe that by (Id) we have that $\vdash {\chi ({Y})} \leadsto {\chi ({Y})}$ . Thus $\vdash \varphi \rightarrow ({\chi ({Y})} \leadsto {\chi ({Y})})$ and ${\chi ({Y})} \leadsto {\chi ({Y})} \in \Sigma $ , which entails $Y = {[\kern -1.2pt[ {{\chi ({Y})}} ]\kern -1.2pt]} \subseteq {h({Y})}$ by the definition of h.

For item 2. take any $\alpha ,\beta \in \mathcal {L}_0$ such that $\alpha \leadsto \beta \in \Sigma $ and ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]} \subseteq {h({Y})}$ . We need to show that then ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \subseteq {h({Y})}$ . Because W is finite it follows from ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]} \subseteq {h({Y})}$ that there are finitely many $\delta _1,\dots ,\delta _n \in \mathcal {L}_0$ with ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]} \subseteq {[\kern -1.2pt[ {\delta _1} ]\kern -1.2pt]} \cup \dots \cup {[\kern -1.2pt[ {\delta _n} ]\kern -1.2pt]}$ and $\delta _i \leadsto {\chi ({Y})} \in \Sigma $ for all $i \in \{1,\dots ,n\}$ . From the former we get that $\vdash (\alpha \land \beta ) \rightarrow (\delta _1 \lor \dots \lor \delta _n)$ . Using (RW) we obtain $\alpha \leadsto (\delta _1 \lor \dots \lor \delta _n) \in \Sigma $ because by (Id) and (And) we have that $\alpha \leadsto \alpha \land \beta \in \Sigma $ . From the latter, that $\delta _i \leadsto {\chi ({Y})} \in \Sigma $ for all $i \in \{1,\dots ,n\}$ , it follows with finitely many applications of (Or) that $\delta _1 \lor \dots \lor \delta _n \leadsto {\chi ({Y})} \in \Sigma $ . Because of the (CCut’) from Proposition 3.1 we get that $\alpha \lor \delta _1 \lor \dots \lor \delta _n \leadsto {\chi ({Y})} \in \Sigma $ . By the definition of h this entails ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \subseteq {h({Y})}$ . □

Lemma 4.3. $\mathcal {C}$ has the anti-exchange property.

Proof. Consider any $C \in \mathcal {C}$ and $x \neq y$ with $x,y \notin C$ . We derive a contradiction from the assumption that for all $D \in \mathcal {C}$ with $C \subseteq D$ we have $x \in D$ iff $y \in D$ .

If this assumption was true then it follows that $y \in {h({{\chi ({C \cup \{x\}})}})}$ because $x \in {h({{\chi ({C \cup \{x\}})}})}$ , $C \subseteq {h({{\chi ({C \cup \{x\}})}})}$ and ${h({{\chi ({C \cup \{x\}})}})} \in \mathcal {C}$ . Thus there is some $\delta _y \in \mathcal {L}_0$ such that $y \in {[\kern -1.2pt[ {\delta _x} ]\kern -1.2pt]}$ and $\delta _y \leadsto {\chi ({C \cup \{x\}})} \in \Sigma $ . Because $\vdash {\chi ({C \cup \{x\}})} \rightarrow {\chi ({C \cup \{x,y\}})}$ it follows from the derived rule (R) in Proposition 3.1 that $(\delta _y \land {\chi ({C \cup \{x,y\}})}) \lor {\chi ({C \cup \{x\}})} \leadsto {\chi ({C \cup \{x\}})} \in \Sigma $ . One can check that $({[\kern -1.2pt[ {\delta _y} ]\kern -1.2pt]} \cap (C \cup \{x,y\})) \cup (C \cup \{x\}) = C \cup \{x,y\}$ . Thus it follows with (LLE) that ${\chi ({C \cup \{x,y\}})} \leadsto {\chi ({C \cup \{x\}})} \in \Sigma $ .

If we interchange the roles of x and y in the reasoning from the previous paragraph we obtain that also ${\chi ({C \cup \{x,y\}})} \leadsto {\chi ({C \cup \{y\}})} \in \Sigma $ . Thus with the help of (And) we can deduce ${\chi ({C \cup \{x,y\}})} \leadsto ({\chi ({C \cup \{x\}})} \land {\chi ({C \cup \{y\}})}) \in \Sigma $ from which we get ${\chi ({C \cup \{x,y\}})} \leadsto {\chi ({C})} \in \Sigma $ by (RW). This contradicts $C \in \mathcal {C}$ because ${[\kern -1.2pt[ {{\chi ({C \cup \{x,y\}})}} ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {{\chi ({C})}} ]\kern -1.2pt]} \subseteq C$ but ${[\kern -1.2pt[ {{\chi ({C \cup \{x,y\}})}} ]\kern -1.2pt]} \nsubseteq C$ . □

Lemma 4.4. For all $\theta \in \mathcal {L}_1$ it holds that

$$ \begin{align*} M \models \theta \quad \mbox{iff} \quad \theta \in \Sigma. \end{align*} $$

Proof. The proof of this lemma is an induction on the complexity of $\mathcal {L}_1$ . The cases for the Boolean operators are straightforward. Thus we only treat the base case where $\theta = \alpha \leadsto \beta $ .

For the right-to-left direction assume that $\alpha \leadsto \beta \in \Sigma $ . To prove $M \models \alpha \leadsto \beta $ we show that ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \subseteq \mathrm {co}({{[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]}})$ , where $\mathrm {co}$ denotes the convex hull operator of the convex geometry $\mathcal {C}$ . Thus we need to show that ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \subseteq C$ for every convex set $C \in \mathcal {C}$ with ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]} \subseteq C$ . This follows directly from the definition of $\mathcal {C}$ .

For the other direction assume that $M \models \alpha \leadsto \beta $ . This means that ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \subseteq \mathrm {co}({{[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]}})$ . Because by Lemma 4.2 ${h({{[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]}})}$ is a convex set containing ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]}$ it follows that $\mathrm {co}({{[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]}}) \subseteq {h({{[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]}})}$ . Thus ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \subseteq {h({{[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\beta } ]\kern -1.2pt]}})}$ . Because W is finite it follows from the definition of h that there are $\delta _1,\dots ,\delta _n$ such that ${[\kern -1.2pt[ {\alpha } ]\kern -1.2pt]} \subseteq {[\kern -1.2pt[ {\delta _1} ]\kern -1.2pt]} \cup \dots \cup {[\kern -1.2pt[ {\delta _n} ]\kern -1.2pt]}$ and $\delta _i \leadsto \alpha \land \beta \in \Sigma $ for all $i \in \{1,\dots ,n\}$ . It follows from the former with the help of (Id) and (RW) that $\vdash \alpha \leadsto \delta _1 \lor \dots \lor \delta _n$ . Using (Or) we get that $\delta _1 \lor \dots \lor \delta _n \leadsto \alpha \land \beta \in \Sigma $ because $\delta _i \leadsto \alpha \land \beta \in \Sigma $ for all $i \in \{1,\dots ,n\}$ . With the help of (CCut’), which is derivable according to Proposition 3.1, it follows that $\alpha \lor \delta _1 \lor \dots \lor \delta _n \leadsto \alpha \land \beta \in \Sigma $ . Because of (WCM) from Proposition 3.1 we obtain that $(\alpha \lor \delta _1 \lor \dots \lor \delta _n) \land \alpha \leadsto \beta \in \Sigma $ and by (LLE) we get that $\alpha \leadsto \beta \in \Sigma $ . □

Remark 4.5. Note that no two distinct worlds in the model that is constructed in the proof of Theorem 4.1 satisfy the same propositional letters. This is in stark contrast to the completeness proofs of preferential conditional logic with respect to its semantics in orders from [9, 41]. Part of the complexity of the constructions in these proofs comes from the fact that they duplicate possible worlds to obtain enough witnesses in the constructed order. It follows from the discussion of the coherence condition in Section II.4.1 of [41] or from the example in the last paragraph of Section 5.2 in [25] that such a duplication of worlds is necessary to obtain completeness with respect to the order semantics. That such a duplication of worlds is not needed for completeness with respect to convex geometries is exploited in the duality result from [30], which uses convex geometries on the spatial side of the duality.

5. Morphisms of convex geometries

In this section we recall the notion of a morphism between convex geometries from [30]. The motivation for this notion is that in the finite case they are precisely the functions that preserve and reflect the truth of all conditionals. It should be mentioned that our notion of morphism cannot be straightforwardly adapted to the infinite case as its adequacy relies on the reformulation of the semantics from Proposition 3.5, which only holds in the finite case.

The definition of a morphism uses the following existential and universal image maps: For every $f : W \to U$ we write ${f^\exists } : \mathcal {P} W \to \mathcal {P} U$ for the left adjoint and ${f^\forall } : \mathcal {P} W \to \mathcal {P} U$ for the right adjoint of the inverse image map $f^{-1} : \mathcal {P} U \to \mathcal {P} W, X \mapsto \{w \in W \mid f(w) \in X\}$ . Concretely, this means that for all $Y \subseteq W$

$$ \begin{align*} {f^\exists}(Y) & = \{u \in U \mid f^{-1}(\{u\}) \cap Y \neq \emptyset\}, \mbox{ and} \\ {f^\forall}(Y) & = \{u \in U \mid f^{-1}(\{u\}) \subseteq Y\}. \end{align*} $$

It is easy to check that $\overline {{f^\exists }(Y)} = {f^\forall }(\overline {Y})$ for all $Y \subseteq W$ . Note that ${f^\exists }$ is just the usual direct image map.

A morphism f from a convex geometry $(W,\mathcal {C})$ to a convex geometry $(U,\mathcal {D})$ is a function $f : W \to U$ such that ${f^\forall }(C) \in \mathcal {D}$ for all $C \in \mathcal {C}$ . The morphism f is a strong morphism if it additionally satisfies that for every $D \in \mathcal {D}$ there is some $C \in \mathcal {C}$ such that $D = {f^\forall }(C)$ . Thus, strong morphism are precisely the functions for which $\mathcal {D} = \{{f^\forall }(C) \subseteq U \mid C \in \mathcal {C}\}$ . By dualizing and exploiting $\overline {{f^\exists }(Y)} = {f^\forall }(\overline {Y})$ one can adapt this definition of morphism to the feasible sets of a convex geometry. A morphism is then a function f such that ${f^\exists }(F)$ is feasible for every feasible F, and it is strong if every feasible set arises as ${f^\exists }(F)$ for some feasible F.

The reader can convince themselves that surjective affine transformations on the plane, such as translations, rotations or scalings, are strong morphisms.

For posets we have that $f : W \to U$ is a morphism between the upset convexities of partial orders $\leq $ on W and $\leq '$ on U if and only if it satisfies the following condition, which is just the back condition on bounded morphism in modal logic:

• • For all $w \in W$ and $u' \leq ' f(w)$ there is an $u \leq w$ such that $f(u) = u'$ .

The morphism f is strong if and only if it additionally satisfies the following condition: ¹

• • For all $u \in U$ there is a $w \in W$ such that $f(w) = u$ and for all $w' \leq w$ we have $f(w') \leq ' u$ .

Note that these two conditions on the graph of f correspond to the conditions on bisimulations between models based on posets from [43].

A further example of a morphism comes from the following proposition. It shows that removing impossible worlds from a model yields a submodel that embeds with a strong morphism. As a consequence impossible worlds can be removed without altering the truth of one-step formulas.

Proposition 5.1. Let $(W,\mathcal {C})$ be any convex geometry and let $I = \bigcap \mathcal {C}$ . Define $U = W \setminus I$ and let $\mathcal {D}$ be the relative convexity of U in W. Then $\emptyset \in \mathcal {D}$ and the embedding $e : U \to W,u \mapsto u$ is a strong morphism from $(U,\mathcal {D})$ to $(W,\mathcal {C})$ .

Proof. That $\emptyset \in \mathcal {D}$ follows because, by the closure of $\mathcal {C}$ under arbitrary intersection, we have that $I \in \mathcal {C}$ , and thus $\emptyset = I \cap U \in \mathcal {D}$ by the definition of the relative convexity. To see that e is a strong morphism it is easier to reason with the feasible sets. The worlds in I do not appear in any feasible set from $(W,\mathcal {C})$ and thus it is clear that the feasible sets in $(W,\mathcal {C})$ are precisely the direct images of feasible sets from $(U,\mathcal {D})$ . □

We can lift the notion of a morphism to models in the standard way. That is, $f : W \to W'$ is a morphism from $M = (W,\mathcal {C},V)$ to $M' = (W',\mathcal {C}',V')$ if f is a morphism from $(W,\mathcal {C})$ to $(W',\mathcal {C}')$ and $V(p) = f^{-1}(V'(p))$ for all $p \in \mathsf {Prop}$ . We call f from M to $M'$ strong if it is strong as a morphism between the underlying convex geometries.

Propositions 10 and 12 from [30] entail that in the finite case strong morphisms preserve and reflect the truth of conditionals. Because this result is central for our approach we restate the result in our terminology and provide a self-contained proof.

Theorem 5.2. Let f be a strong morphism from a finite model $M = (W,\mathcal {C},V)$ to a finite model $M' = (W',C',V')$ then it holds for all $\varphi \in \mathcal {L}_1$ that

$$ \begin{align*} M \models \varphi \quad \mbox{iff} \quad M' \models \varphi. \end{align*} $$

Proof. First observe that because taking preimages is a Boolean homomorphism between powerset algebras it is clear that the condition that $V(p) = f^{-1}(V'(p))$ for all $p \in \mathsf {Prop}$ entails that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_V = f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'})$ for all $\varphi \in \mathcal {L}_0$ .

To prove the preservation of true formulas in $\mathcal {L}_1$ one uses a standard induction on the complexity of formulas. We only consider the case for the conditional. Because we are in a finite setting we can use the equivalent formulation of the semantics from Proposition 3.5, stating that $\varphi \leadsto \psi $ is true in a model iff ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \subseteq \mathrm {co}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}})$ .

Assume first that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \subseteq \mathrm {co}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'}})$ holds in $\mathcal {C}'$ . To show that then $f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \subseteq \mathrm {co}({f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \cap f^{-1}({[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'})})$ holds in $\mathcal {C}$ consider any $w \notin \mathrm {co}({f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \cap f^{-1}({[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'})})$ . This means that there is some convex $C \in \mathcal {C}$ such that $f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'}) = f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \cap f^{-1}({[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'}) \subseteq C$ and $w \notin C$ . Because f is a morphism it then follows that ${f^\forall }(C) \in \mathcal {C}'$ and because ${f^\forall }$ is right adjoint to $f^{-1}$ we get ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'} \subseteq {f^\forall }(C)$ . Thus, $\mathrm {co}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'}}) \subseteq {f^\forall }(C)$ and with the assumption that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \subseteq \mathrm {co}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'}})$ it follows that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \subseteq {f^\forall }(C)$ . From $w \notin C$ we have that $f(w) \notin {f^\forall }(C)$ and so $f(w) \notin {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}$ , which means that $w \notin f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'})$ .

For the other direction assume $f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \subseteq \mathrm {co}({f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \cap f^{-1}({[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'})})$ . We show ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \subseteq \mathrm {co}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'}})$ by contraposition. Thus consider any $w' \notin \mathrm {co}({{[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'}})$ . There then is some convex $C' \in \mathcal {C}'$ such that ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'} \subseteq C'$ and $w' \notin C'$ . Because f is a strong morphism there exists a $C \in \mathcal {C}$ such that $C' = {f^\forall }(C)$ . Because ${f^\forall }$ is right adjoint to $f^{-1}$ we obtain $f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'}) \subseteq C$ from ${[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'} \subseteq C' = {f^\forall }(C)$ . With $f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'} \cap {[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'}) = f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \cap f^{-1}({[\kern -1.2pt[ {\psi } ]\kern -1.2pt]})_{V'}$ it follows that $\mathrm {co}({f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \cap f^{-1}({[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'})}) \subseteq C$ . Combining with the assumption $f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \subseteq \mathrm {co}({f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \cap f^{-1}({[\kern -1.2pt[ {\psi } ]\kern -1.2pt]}_{V'})})$ yields $f^{-1}({[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}) \subseteq C$ . Since $w' \notin {f^\forall }(C)$ it must be the case that $f^{-1}(\{w'\}) \nsubseteq C$ , and hence $w \notin {[\kern -1.2pt[ {\varphi } ]\kern -1.2pt]}_{V'}$ . □

6. Representation of convex geometries in the plane

In this section we show that the representation from Theorem 5 in [33] gives rise to a strong morphism of convex geometries. It would be possible to show that any such representation of a finite convex geometry with polygons that have disjoint extreme points yields a strong morphism. Thus, we could just use Theorem 5 from [33] as a black box, without disassembling the inner workings of the construction in its proof. But because this construction is at the heart of our completeness result, we give a detailed exposition of the representation in this section. Figure 2 contains an example of this representation for the convex geometry from Example 3.7.

Fig. 2 In the upper right corner is a decomposition of the convex geometry from Example 3.7 into linear orders. The main picture contains the representation of this convex geometry in the plane. In the lower right corner is the formula $\alpha $ from Example 3.7 that is true in this convex geometry.

6.1. Decomposition of finite convex geometries

It is shown in [14] that every finite convex geometry can be decomposed into a family of convexities arising from linear orders. Using these decompositions is crucial for the results in [33].

The relevant notion of decomposition is the join in the semi-lattice of all convex geometries over some fixed finite set W, ordered by the inclusion between sets of sets. From Theorem 2.2 in [13] it follows that the join $\mathcal {C} \vee \mathcal {D}$ of convex geometries $\mathcal {C}$ and $\mathcal {D}$ over W can be defined concretely as

$$ \begin{align*} \mathcal{C} \vee \mathcal{D} = \{C \cap D \mid C \in \mathcal{C} \mbox{ and } D \in \mathcal{D}\}. \end{align*} $$

Recall that a partial order $\leq $ on W is linear if $x \leq y$ or $y \leq x$ holds for all $x,y \in W$ . The decomposition result, which is Theorem 5.2 in [14], can be formulated in our notation as follows:

Theorem 6.1. Let $\mathcal {C}$ be a convex geometry over a finite set W such that $\emptyset \in \mathcal {C}$ . Then there is a finite family of linear orders $(\leq _j)_{j = 1}^m$ such that

(1) $$ \begin{align} \mathcal{C} = \bigvee_{j = 1}^m \mathcal{U}({\leq_j}). \end{align} $$

Note that from the definition of the join it follows that if the posets $(\leq _i)_{i = 1}^k$ are a decomposition of a convex geometry $\mathcal {C}$ according to (1) then some set $X \subseteq W$ is convex if and only if it can be written as

(2) $$ \begin{align} X = \bigcap_{j = 1}^{m} {{X}\!\!\uparrow_{j}}, \end{align} $$

where ${{X}\!\!\uparrow _{j}} = \{w \in W \mid x \leq _j w \mbox { for some }x \in X\}$ denotes the upward closure of X in the order $\leq _j$ .

6.2. The representation by Richter and Rogers

This subsection contains the proof of Theorem 5 in [33]. For this paper we need the following formulation of the representation result:

Theorem 6.2. Let $\mathcal {C}$ be a convex geometry over a finite set W such that $\emptyset \in \mathcal {C}$ . Then there is a finite set $U \subseteq \mathbb {R}^2$ and a strong morphism of convex geometries r from $(W,\mathcal {C})$ to U with the relative convexity from $\mathbb {R}^2$ .

We first describe how to construct the set U and the function r. Fix a convex geometry $(W,\mathcal {C})$ such that $\emptyset \in \mathcal {C}$ and let n be the number of elements in W. By Theorem 6.1 there exists a decomposition of $\mathcal {C}$ into linear orders $(\leq _i)_{i = 1}^m$ . Assume without loss of generality that $m \geq 2$ , otherwise just duplicate one of the linear orders. For every $w \in W$ and $j \in \{1,\dots ,m\}$ let ${r_{j}({w})} \in \mathbb {N} \subseteq \mathbb {R}$ be the rank of w in the linear order $\leq _j$ starting from the top. This means that if $\leq _j$ is $w_n <_j w_{n - 1} <_j \dots <_j w_1$ then ${r_{j}({w})} = i$ for the unique i with $w_i = w$ .

We then choose m-many points on the unit circle that are equally distributed among all directions. Thus, set $d_j = (\cos (2\pi j/m),\sin (2\pi j/m)) \in \mathbb {R}^2$ for every $j \in \{1,\dots ,m\}$ . Define $s \in \mathbb {R}$ as

$$ \begin{align*} s = \max\left\{0,\frac{n \cos(2\pi/m)}{1 - \cos(2\pi/m)} \right\}. \end{align*} $$

For every $w \in W$ and $j \in \{1,\dots ,m\}$ define the point

$$ \begin{align*} {u({j},{w})} = (s + {r_{j}({w})}) d_j \in \mathbb{R}^2, \end{align*} $$

and for every $w \in W$ define the set $U^w = \{{u({1},{w})} ,\dots ,{u({m},{w})}\}$ . Clearly we have that $U^w \cap U^u = \emptyset $ whenever $w \neq u$ . Define $U \subseteq \mathbb {R}^2$ as $U = \bigcup _{w \in W} U^a$ and $r : U \to W$ such that $r(u)$ is the unique $w \in W$ with $u \in U^w$ . Note that $r^{-1}(\{w\}) = U^w$ for all $w \in W$ .

The idea behind the definition of U is to spread out the linear orders in the decomposition of $\mathcal {C}$ along separate rays that move outward from the origin. On each ray this happens at distance s away from the origin. This safety distance ensures that every point on some ray is further out from the origin than the intersection of the ray with any line segment between points on neighboring rays.

Theorem 6.2 then follows from the following two lemmas.

Lemma 6.3. r is a morphism of convex geometries.

Proof. We need to show that whenever $C \subseteq U$ is convex in the relative convexity of U in $\mathbb {R}^2$ then ${r^\forall }(C) \in \mathcal {C}$ . Thus fix such a C and let $D = {r^\forall }(C)$ . To show that D is convex in $\mathcal {C}$ we use the characterization (2) and show that $D = \bigcap _{j = 1}^{m} {{D}\!\!\uparrow _{j}}$ . For the non-trivial $\supseteq $ -inclusion consider any w such that for all $j \in \{1,\dots ,m\}$ there is some $w_j \in D$ such that $w_j \leq _j w$ . To prove $w \in D = {r^\forall }(C)$ we need to show that $U^w \subseteq \mathrm {co}({C})$ .

First observe that the origin $(0,0)$ is in the convex hull $\mathrm {co}({C})$ of C in $\mathbb {R}^2$ . This is a little technical but not very interesting: If n is even then the origin can be written as a convex combination of the points ${u({w_m},{m})}$ and ${u({w_{m/2}},{m/2})}$ in C because both points have $0$ in their second coordinate, and the former has a positive but the latter a negative first coordinate. If n is odd then $n \geq 3$ and the points ${u({w_j},{j})}$ and ${u({w_k},{k})}$ , for $j = (m - 1)/2$ and $k = (m + 1)/2$ , are in C. They both have a negative first coordinate and a different signum in their second coordinates. Thus there is some point $s \in \mathrm {co}({C})$ that has a negative first coordinate and $0$ in the second coordinate. The origin is then a convex combination of s and ${u({w_m},{m})}$ .

Consider then any point in $U^w$ , which must be of the form ${u({w},{j})}$ for some $j \in \{1,\dots ,m\}$ . Because $D = {r^\forall }(C)$ and $w_j \in D$ we have that ${u({w_j},{j})} \in U^{w_j} = f^{-1}(\{w_j\}) \subseteq C$ . Moreover, from $w_j \leq w$ it follows that ${r_{j}({w})} \leq {r_{j}({w_j})}$ and hence ${u({w},{j})} = (s + {r_{j}({w})}) d_j$ is on the line segment from the origin to ${u({w_j},{j})} = (s + {r_{j}({w_j})}) d_j$ . It follows that ${u({w},{j})} \in \mathrm {co}({C})$ and thus that ${u({w},{j})} \in C$ , since C is convex in the relative convexity. □

Lemma 6.4. r is a strong morphism of convex geometries.

Proof. To show that r is strong consider any $D \in \mathcal {C}$ . We show that $D = {r^\forall }(C)$ for $C = \mathrm {co}({r^{-1}(D)}) \cap U$ . That $D \subseteq {r^\forall }(C)$ follows immediately from $r^{-1}(D) \subseteq C$ . To show $D \supseteq {r^\forall }(C)$ consider any $w \notin D$ . We show that $w \notin {r^\forall }(C)$ .

Because D is convex we can apply the characterization from (2) and conclude that there is some $j \in \{1,\dots ,m\}$ such that $w <_j u$ for all $u \in D$ . We then assume that $j = m$ . This is without loss of generality because one can apply a rotation to turn any ray for j until it comes to lie on the positive x-axis. Because rotations are isomorphism with respect to the convex sets this does not influence our reasoning.

To show that $w \notin {r^\forall }(C)$ it suffices to show that ${u({w},{m})} \notin \mathrm {co}({r^{-1}(D)})$ . To this aim we show that the first coordinate of ${u({w},{m})} = (s + {r_{m}({w})}) d_k$ is strictly larger than the first coordinate of any ${u({v},{k})} = (s + {r_{k}({v})}) d_k$ for $v \in D$ and $k \in \{1,\dots ,m\}$ , meaning that ${u({w},{m})}$ cannot be written as the convex combination of such points. If $k = m$ then this is clear because $d_m = (1,0)$ and ${r_{m}({w})}> {r_{m}({v})}$ , as $w <_m v$ . In the other case where $k \neq m$ first consider the case where $\cos (2\pi /m) \geq 0$ . Then $0 \leq \frac {n \cos (2\pi /m)}{1 - \cos (2 \pi /m)} = s$ and we can estimate the first coordinate of ${u({v},{k})}$ as follows:

$$ \begin{align*} (s + {r_{k}({v})}) \cos(2\pi k / m) & \leq (s + n) \cos(2\pi k / m) \\ & \leq (s + n) \cos(2\pi / m) \\ & \leq \left(\frac{n\cos(2\pi / m)}{1 - \cos(2\pi /m )} + n\right) \cos(2\pi / m) \\ & = \left(\frac{n}{1 - \cos(2\pi /m )}\right) \cos(2\pi / m) \\ & \leq s \\ & < s + {r_{m}({w})}. \end{align*} $$

Because $s + {r_{m}({w})}$ is the first coordinate of ${u({w},{m})}$ this is the needed inequality. In the other case where $\cos (2\pi / m) < 0$ we get that $m \leq 3$ . Thus, $k / m$ is either $1/3$ , $2/3$ or $1/2$ and so $\cos (2\pi k / m)$ is negative. It follows that the first coordinate of ${u({v},{k})}$ is also negative and therefore it is smaller than the first coordinate of ${u({w},{m})}$ . □

7. Completeness for Euclidean convexity

In this last section we put the results from this paper together to prove the completeness of preferential conditional logic with respect to convexity between points in the plane. We also show that this result cannot be improved to a completeness result with respect to convexity on the real line.

The following is the main result of this paper:

Theorem 7.1. Every one-step formula $\varphi \in \mathcal {L}_1$ that is consistent in preferential conditional logic is true in a model of the form $M = (W,\mathcal {C},V)$ , where $W \subseteq \mathbb {R}^2$ is a finite set of points and $\mathcal {C}$ is the relative convexity of W in $\mathbb {R}^2$ .

Proof. From Theorem 4.1 we obtain a finite model $M'' = (W'',\mathcal {C}'',V'')$ such that $M'' \models \varphi $ . From Proposition 5.1 we get a finite convex geometry $(W',\mathcal {C}')$ with $\emptyset \in \mathcal {C}'$ and strong morphism of convex geometries $r''$ from $(W',\mathcal {C}')$ to $(W'',\mathcal {C}'')$ . We can then apply Theorem 6.2 to obtain a finite set $W \subseteq \mathbb {R}^2$ together with a strong morphism $r'$ from $(W,\mathcal {C})$ to $(W',\mathcal {C}')$ such that $\mathcal {C}$ is the relative convexity of W in $\mathbb {R}^2$ .

Let $r = r' \circ r''$ be the composition of $r''$ with $r'$ . Clearly, this is also a strong morphism of convex geometries from $(W,\mathcal {C})$ to $(W'',\mathcal {C}'')$ . Then define the model $M = (W,\mathcal {C},V)$ such that $V(p) = r^{-1}(V''(p))$ for all $p \in \mathsf {Prop}$ . This turns r into a strong morphism from the model M to the model $M''$ and thus $M \models \varphi $ follows with Theorem 5.2. □

Remark 7.2. To adapt this completeness result to nested preferential conditional logic one would need to consider models $(W,U,V)$ where $W \subseteq \mathbb {R}^2$ and $U : W \to \mathcal {P} W$ . The function U fixes a finite set of points $U(w)$ for every world $w \in W$ . At a world $w \in W$ a conditional is then evaluated in the relative convexity of $U(w)$ in $\mathbb {R}^2$ . Completeness with respect to such models can be obtained by starting from a model in the semantics from Remark 3.3 and then applying Theorem 7.1 locally to $\mathcal {C}(w)$ for every world w. By suitably translating the points in the sets $U(w)$ one can ensure that $U(w) \cap U(w') = \emptyset $ whenever $w \neq w'$ . Thus, the valuation $V : \mathsf {Prop} \to \mathcal {P} W$ can be defined globally on W.

The completeness result from Theorem 7.1 cannot be improved to a completeness with respect to models based on subsets of the real line. The reason is that such models validate additional formulas that are not provable in preferential conditional logic. As a first example consider the formula

$$ \begin{align*} \gamma_2 = (p \lor q \lor r \leadsto p \lor q) \lor (p \lor q \lor r \leadsto p \lor r) \lor (p \lor q \lor r \leadsto q \lor r). \end{align*} $$

It can be seen as a generalization of the formula $\gamma _1 = (p \lor q \leadsto p) \lor (p \lor q \leadsto q)$ , which is valid over linear orders. Using soundness of the semantics over posets it is easy to see that $\gamma _2$ is not derivable in preferential conditional logic. However, one can show that $\gamma _2$ is true in all models of the form $(W,\mathcal {C},V)$ , where $W \subseteq \mathbb {R}$ is finite and $\mathcal {C}$ is the relative convexity of W in $\mathbb {R}$ . The argument is roughly that we just need to consider the two propositional letters among p, q and r that are true at the at most two extreme points of ${[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]}$ . Note that these extreme points are simply the minimal and maximal elements of ${[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]}$ in the standard order of the reals.

Surprisingly, $\gamma _2$ can be invalidated if we allow W to be an infinite subset of $\mathbb {R}$ . This shows that the conditional logic of finite sets of points on the real line is different from the logic of the whole real line. To invalidate $\gamma _2$ it suffices to consider a model $(\mathbb {R},\mathcal {C},V)$ , where $\mathcal {C}$ is the standard convexity on $\mathbb {R}$ and V is such that for every propositional letter in $\{p,q,r\}$ there are arbitrarily large and arbitrarily small reals at which the propositional letter is true.

The logic of infinite subsets of the real line is still stronger than preferential conditional logic. To see this consider the formula

$$ \begin{align*} \delta_2 = (p \lor q \lor r \leadsto s) \rightarrow (p \lor q \leadsto s) \lor (p \lor r \leadsto s) \lor (q \lor r \leadsto s). \end{align*} $$

This formula is a generalization of the formula $\delta _1 = (p \lor q \leadsto s) \rightarrow (p \leadsto s) \lor (q \leadsto s)$ expressing disjunctive rationality, which is valid over interval orders. Using the order semantics it is not hard to show that $\delta _2$ is not derivable in preferential conditional logic. But $\delta _2$ is valid in models that are based on the real line:

Proposition 7.3. The formula $\delta _2$ is valid in all models of the form $(W,\mathcal {C},V)$ , where $W \subseteq \mathbb {R}$ is any set of points on the line and $\mathcal {C}$ is the relative convexity of W in $\mathbb {R}$ .

Proof. Consider a model $M = (W,\mathcal {C},V)$ such that $W \subseteq \mathbb {R}$ and $\mathcal {C}$ is the relative convexity of W in $\mathbb {R}$ . To show that $\delta _2$ is valid assume that $M \models p \lor q \lor r \leadsto s$ .

Define $p_r \in \{p,q,r\}$ such that for all $u \in {[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]}$ there is some $v \in {[\kern -1.2pt[ {p_r} ]\kern -1.2pt]}$ with $u \leq v$ . Such a $p_r$ must exist. Otherwise, we have for all $a \in \{p,q,r\}$ a $u_a \in {[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]}$ such that $v < u_a$ for all $v \in {[\kern -1.2pt[ {a} ]\kern -1.2pt]}$ . This leads to a contradiction by considering the maximum of $u_p$ , $u_q$ and $u_r$ , which is in ${[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]}$ , but cannot be in any of ${[\kern -1.2pt[ {p} ]\kern -1.2pt]}$ , ${[\kern -1.2pt[ {q} ]\kern -1.2pt]}$ and ${[\kern -1.2pt[ {r} ]\kern -1.2pt]}$ . Analogously, we define $p_l \in \{p,q,r\}$ such that for all $u \in {[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]}$ there is some $v \in {[\kern -1.2pt[ {p_l} ]\kern -1.2pt]}$ with $v \leq u$ . Let $A = \{a_1,a_2\}$ be one of $\{p,q\}$ , $\{p,r\}$ , or $\{q,r\}$ such that $\{p_r,p_l\} \subseteq A$ .

We claim that then $M \models a_1 \lor a_2 \leadsto s$ . To see this consider any convex set $C \in \mathcal {C}$ such that ${[\kern -1.2pt[ {a_1 \lor a_2} ]\kern -1.2pt]} \nsubseteq C$ . Thus, there is some world $u \in {[\kern -1.2pt[ {a_1 \lor a_2} ]\kern -1.2pt]}$ such that $u \notin C$ . Because C is convex it follows that the worlds in C are either all to the left or are all to the right of u. Assume without loss of generality that all worlds of C are to the left of u, that is, $v < u$ for all $v \in C$ . Let $C' = (-\infty ,u)$ be the convex set of all worlds that are strictly to the left of u. Clearly $C \subseteq C'$ and $u \notin C'$ . From the latter it follows that ${[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]} \nsubseteq C'$ , because $u \in {[\kern -1.2pt[ {a_1 \lor a_2} ]\kern -1.2pt]} \subseteq {[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]}$ .

From the assumption that $M \models p \lor q \lor r \leadsto s$ it follows that there is some convex set D with $C' \cap {[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]} \subseteq D$ and ${[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]} \nsubseteq D$ such that ${[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]} \subseteq D \cup {[\kern -1.2pt[ {s} ]\kern -1.2pt]}$ . From $C' \cap {[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]} \subseteq D$ it follows that $C \cap {[\kern -1.2pt[ {a_1 \lor a_2} ]\kern -1.2pt]} \subseteq D$ and from ${[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]} \subseteq D \cup {[\kern -1.2pt[ {s} ]\kern -1.2pt]}$ it follows that ${[\kern -1.2pt[ {a_1 \lor a_2} ]\kern -1.2pt]} \subseteq D \cup {[\kern -1.2pt[ {s} ]\kern -1.2pt]}$ . It thus only remains to be seen that ${[\kern -1.2pt[ {a_1 \lor a_2} ]\kern -1.2pt]} \nsubseteq D$ . Because ${[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]} \nsubseteq D$ there is some $u' \in {[\kern -1.2pt[ {p \lor q \lor r} ]\kern -1.2pt]}$ such that $u' \notin D$ . Observe first that $u \leq u'$ because $(-\infty ,u) = C' \subseteq D$ . By the choice of $p_r$ there is then a $v' \in {[\kern -1.2pt[ {p_r} ]\kern -1.2pt]}$ such that $u' \leq v'$ . Clearly $v' \in {[\kern -1.2pt[ {a_1 \lor a_2} ]\kern -1.2pt]}$ . We also have $v' \notin D$ because D is convex, $u' \notin D$ , $u - 42 \in C' \subseteq D$ and $u - 42 < u \leq u' < v'$ . □

8. Conclusion

We have shown that preferential conditional logic is complete with respect to convexity over finite sets of points on the plane. Because of the validities discussed in Section 7 this result cannot be strengthened to convexity on the real line. There seem to be two natural directions to continue this line of research. First, one might ask what is the logic of finite sets of points on the line and what is the logic of the real line. As our examples also show these logics are not the same. Second, one might try to strengthen our completeness result. Most interesting would be to show completeness with respect to convexity over the complete plane, analogously to the completeness of S4 with respect to the standard topology on the full real line:

Problem 8.1. Is preferential conditional logic complete with respect to models of the form $(\mathbb {R}^2,\mathcal {C},V)$ , where $\mathcal {C}$ is the standard convexity and V any valuation?

It might be simpler to first show completeness with respect to bounded regions in the plane. A plausible conjecture of this kind is the following:

Problem 8.2. Is preferential conditional logic complete with respect to models of the form $(U,\mathcal {C},V)$ , where $U \subseteq \mathbb {R}^2$ is regular, compact and convex, $\mathcal {C}$ is the relative convexity of U in $\mathbb {R}^2$ , V is a valuation that sends all propositional letters to regular closed sets, and the propositional connectives are interpreted over the Boolean algebra of regular closed sets?

Note that by the Krein–Milman Theorem compact sets are in the closure of their extreme points. Thus, one might hope that for the semantics of the conditional they still behave similar to finite sets.

Another question for further research is how conditional logic relates to other modal logics that have been developed to reason about convexity or lines in space. Examples are the bimodal logics of lines and points from [6, 42] or the logics of the one-step convexity and betweenness modalities in [4]. It seems that the expressivity of the conditional is weak compared to the modalities in these logics. Thus, one might hope to find interpretations of preferential conditional logic into some of these more expressive logics.

In this paper we have investigated the connections between conditional logic and convexity from a purely formal perspective. It would be interesting to see whether this new geometric semantics can lead to new insights about applications such as the meaning counterfactual conditionals in natural language or the structure of defeasible reasoning.