Proof of Proposition 1. We show that \(\varphi=\sigma_\rho\circ\kappa\) is a suitable mapping witnessing alignment. Because a flat support is a partial alphabet, Lemma 2 implies \(\rho(\kappa[\alpha])= r(\kappa[\alpha])\) for all \(\alpha \in \Lambda\). Since \(r(\kappa[\alpha]) = r[\alpha]\), agreement follows. One also sees cover-preservation by integrality. Finally, inclusion follows by our choice of \(\varphi\). ◻

Proof. Let \(\varphi:\mathscr{L}(\Lambda)\to\mathscr{L}(\rho)\) be the mapping satisfying the alignment axioms, and fix a basic word \(x_1\ldots x_R \in \Lambda\) and non-loop \(y\in\Sigma\). Note that inclusion implies \(\kappa[\alpha]\subseteq\varphi[\alpha]\) for all \(\alpha \in \Lambda\). So, because there is a feasible word containing \(y\) in its support it follows that \(y \in \varphi[x_1\ldots x_R]\). Moreover, agreement makes \(\rho(\varphi[\epsilon]) = 0\), and so \(\varphi[\epsilon]\) can only contain loops of the greedoid. This makes \(y \in \varphi[x_1\ldots x_R]\setminus\varphi[\epsilon]\), and as cover-preservation implies, \[\varphi[\epsilon] \prec \varphi[x_1]\prec\varphi[x_1x_2]\prec\ldots\prec\varphi[x_1\ldots x_R],\] it follows that there exists an index \(i \in \{1,\ldots, R\}\) such that \(y \in \varphi[x_1\ldots x_i]\setminus\varphi[x_1\ldots x_{i-1}]\). By cover-preservation, we see that \(\sigma_\rho(\varphi[x_1\ldots x_{i-1}] + y) = \varphi[x_1\ldots x_i],\) which makes, \[(\rho/\{x_1,\ldots,x_{i-1})(y) = (\rho/\varphi[x_1\ldots x_{i-1}])(y) = (\rho/\varphi[x_1\ldots x_{i-1}])(x_i) = (\rho/\{x_1\ldots x_{i-1}\})(x_i) = 1.\] Thus \(y \in \Gamma[x_1 \ldots x_{i-1}]\). As our choices were arbitrary, optimism follows. ◻

Proof. Select \(x,y \in \Gamma[\mu]\) and \(\alpha \in \Sigma^*\) satisfying the premise. Note that \(\mu x \alpha \not\sim \mu y \alpha\) ensures that \(x \neq y\), making the task of showing \(x \in \Gamma[\mu y \alpha]\) well-formed. To do so, first recall that two words in the same flat of an interval greedoid are cospanning. Hence, via negation we find \(\Gamma[\mu x \alpha] \neq \Gamma[\mu y \alpha]\). First, suppose \(\Gamma[\mu x \alpha] \setminus \Gamma[\mu y \alpha] \neq \varnothing\), and select a letter \(z\) in this difference. Then because, \[\label{eq:pidgeonhole} \widetilde{\mu x \alpha z} \setminus \widetilde{\mu y \alpha} = \{x, z\},\tag{8}\] and the words of \(\Lambda\) are simple, the fact that \(\mu x \alpha z \in \Lambda\) and \(|\mu x \alpha z| > |\mu y \alpha|\) makes the lemma by way of the exchange axiom. More precisely, since \(z \notin \Gamma[\mu y \alpha]\) and Eq. 8 makes \(x\) the only letter that can be concatenated onto \(\mu y \alpha\) from \(\widetilde{\mu x \alpha z}\) while maintaining feasibility, we conclude that \(\mu y \alpha x \in \Lambda\).

To finish, we must also verify that the case of \(\Gamma[\mu x\alpha]\setminus \Gamma[\mu y \alpha] = \varnothing\) does not pose any problems. If this is true, then there exists \(z \in \Gamma[\mu y \alpha]\setminus \Gamma[\mu x \alpha]\). Then, by symmetry the preceding arguments show that \(\mu x \alpha y \in \Lambda\). Therefore, by simple exchange it must be the case that \(\mu y \alpha x\) is feasible as well, because \(|\mu x \alpha y| > |\mu y \alpha|\) and \(\widetilde{\mu x \alpha y} \setminus \widetilde{\mu y \alpha} = \{x\}\). ◻

Proof of the Forking Lemma. Let \(\mu \in \Lambda\) and \(x \in \Gamma[\mu]\) be as described in Lemma 3. Put more concisely, our assumptions make, \[F\sqcap F' = [\mu] \sqsubset [\mu x] \sqsubseteq F'.\] and from this, the reader should observe that the strict ordering relation between \([\mu]\) and \([\mu x]\) ensures \([\mu x] \not\sqsubseteq F\), thereby making \(F \neq F'\) as well. Hence, there exists a letter \(y \in \Gamma[\mu]\) and \(\alpha \in \Sigma^*\) where \(y \neq x\) and \(\mu y \alpha \in F\). To prove the lemma, we will induct over the difference \(r(F) - r[\mu]\). In the base case where \(r(F) - r(F\sqcap F') = 1\), we see that \(\alpha = \epsilon\). Then, because \(\mu y \in F\) and \([\mu x] \not \sqsubseteq F\), it is the case that \(\mu x \not\sim \mu y\). Therefore, by applying Lemma 4 to \(\mu x \epsilon\) and \(\mu y \epsilon\) we find \(\mu y \epsilon x = \mu y x\) is feasible, which makes the base case as this is equivalent to stating \(x \in \Gamma(F)\).

Now, recalling \(\mu y \alpha \in F\), for the inductive step we make \(r(F) - r[\mu] > 1\) by assuming \(\alpha = \beta z\) where \(z \in \Sigma\) is a letter and \(\beta \in \Sigma^*\) is a simple word, possibly \(\beta = \epsilon\). By the interval property there exists a subword of \(\mu y \beta z\) of length at least \(|\mu y \beta z| - |\mu x| = |\beta| + 1\) which can be concatenated onto \(\mu x\) to make a feasible word. The resulting feasible word must be simple (no letters can be repeated), and so there are three possibilities for the identity of this observed subword:

1. The subword equals \(y\beta\), and so \(\mu x y \beta\) is feasible,

2. The subword equals \(\beta z\), and so \(\mu x \beta z\) is feasible,

3. There exists another subword \(\beta'\) of \(\beta\) resulting from the deletion of some single letter, which is to say \(|\beta'| = |\beta| -1\), such that \(\mu x y \beta' z\) is feasible.

Suppose that either (1.) or (3.) is true. Then, in either of these cases the hereditary axiom makes \(\mu xy\) feasible, and thus \(\mu y x\) is feasible as well by exchange from \(\mu xy\) to \(\mu y\). Furthermore, \([\mu x] \not\sqsubseteq F\) implies \([\mu y x] \not\sqsubseteq F\) as well (since \([\mu x] \prec [\mu y x]\) by \(y \in \Gamma[\mu x]\)), and so \([\mu y] \sqsubseteq F\) makes \(F \sqcap [\mu yx] = [\mu y]\) by construction. As a consequence, \[r(F) - r(F \sqcap [\mu y x]) = r(F) - r([\mu y]) = r(F) - r([\mu]) + 1.\] Therefore, by applying the inductive hypothesis to \(F\) and \([\mu y x]\), we witness \(x \in \Gamma(F)\). The only remaining case is (2.), where \(\mu x \beta z \in \Lambda\). Here, we simply apply Lemma 4 to \(\mu x \beta z\) and \(\mu y \beta z\) to find \(\mu y \beta z x \in \Lambda\). Then, because this case makes \(\mu y \beta z \in F\) we conclude that \(x \in \Gamma(F)\). ◻

Proof. Induct over \(|\alpha|\). If \(\alpha = \epsilon\), then \(F\sqsubseteq F'\). So \(F=F\sqcap F'\) and \(F' = F\sqcup F'\), making \(\epsilon \in F/F\sqcap F'\) and \(\epsilon \in F\sqcup F'/F'\). Now for the inductive step, let \(\alpha = \beta x\) and \(F_0\) be the flat covered by \(F\) which is formed by concatenating any word spanning \(F\sqcap F'\) with \(\beta\). By hypothesis, there exists a subword \(\beta'\) of \(\beta\) such that \(\beta'\in F_0\sqcup F'/F'\). If \(F_0\sqcup F' = F\sqcup F'\) then we are done, so assume \(F_0\sqcup F' \neq F\sqcup F'\). This makes \(F\not\sqsubseteq F_0\sqcup F'\), and so it follows that, \[\label{eq:igiveup} F \sqcap (F_0\sqcup F') = F_0,\tag{9}\] since \(F_0 \prec F\), and \(F_0\) lies below both \(F\) and \(F_0\sqcup F'\). By substitution \(F \succ F \sqcap (F_0\sqcup F')\), so, \[F_0\sqcup F' \prec F \sqcup (F_0\sqcup F') = F\sqcup F',\] by semimodularity. Observe, because \(F_0\sqcup F'\) is rank one less than \(F\sqcup F'\), appending any letter in \(\Gamma(F_0\sqcup F')\cap\kappa(F\sqcup F')\) to \(\beta'\) leads to a word spanning \(F\sqcup F'/F'\). Well, \(\alpha = \beta x\) implies \(x \in \kappa(F)\), and Eq. 9 shows \(x\) is a continuation of the meet of \(F\) and \(F_0\sqcup F'\) leading to a flat (\(F\) to be precise) which is not lesser than \(F_0\sqcup F'\). Then, by applying the Forking Lemma for \(x \in \Gamma(F_0\sqcup F')\), we see that \(\alpha'=\beta'x\) gives the result. ◻

Proof. By optimism, at least one of the following are true: There exists an \(\alpha\)-prefix \(\alpha'\) such that \(y \in \Gamma[\alpha']\), or there exists \(\beta\in\Lambda/\alpha\) with \(y \in \widetilde{\beta}\). The latter is our target statement, so suppose the former is true. Because \(y \notin \kappa[\alpha]\) implies \([\alpha'y] \neq [\alpha]\), it is the case that \([\alpha'y]\sqcap [\alpha] \sqsubset [\alpha'y]\). Observe, \([\alpha']\) lies below both \([\alpha'y]\) and \([\alpha]\). So, since \([\alpha'y]\) covers \([\alpha']\), it follows that \([\alpha'] = [\alpha' y] \sqcap [\alpha]\). Hence, we may apply the Forking lemma to \([\alpha'y]\) and \([\alpha]\) to see \(y \in \Gamma[\alpha]\). Thus \(y\in\Lambda/\alpha\), so the word \(\beta = y\) satisfies the proposition. ◻

Proof. First, we show \(\ddot{\rho}(\widetilde{\alpha}) = \psi_{[\alpha]}(\widetilde{\alpha})\) for all \(\alpha \in \Lambda\). Select any \(\ddot{\rho}(\widetilde{\alpha})\)-optimal flat, i.e. some \(F\in\Lambda/\mathord{\sim}\) achieving \(\ddot{\rho}(\widetilde{\alpha}) = \psi_F(\widetilde{\alpha})\) such that there exists \(\beta \in F\) with \(\widetilde{\beta}\subseteq\widetilde{\alpha}\). Through the exchange axiom there is some \(\gamma \in (\widetilde{\alpha}\setminus\widetilde{\beta})!\) such that \(\gamma\in\Lambda/F\). Hence, \[b_F(\widetilde{\alpha})\geq|\widetilde{\gamma}\cap\widetilde{\alpha}| = |\gamma| = |\alpha| - r(F).\] Applying this to the definition of \(\psi_F\) and rearranging terms shows, \[\psi_{F}(\widetilde{\alpha}) \geq r(F) + \left(1+\frac{1}{r(\Lambda) + 1}\right)\cdot\left(|\alpha| - r(F)\right) = |\alpha| + \frac{1}{r(\Lambda) + 1}\cdot\left(|\alpha| - r(F)\right)\geq |\alpha|.\] But \(\psi_{[\alpha]}(\widetilde{\alpha}) = |\alpha|\), so our assumptions require \(\psi_F(\widetilde{\alpha}) \leq |\alpha|\) also hold. Thus, \(\ddot{\rho}(\widetilde{\alpha}) = \psi_{F}(\widetilde{\alpha}) = |\alpha|\).

Now fix \(x \in \Sigma\). Notice, if \(x \in\Gamma[\alpha]\) then \(\alpha x\) is feasible. So, our preceding argument shows the desired \(x \in\Gamma[\alpha]\) implies \(\ddot{\rho}(\widetilde{\alpha x}) - \ddot{\rho}(\widetilde{\alpha}) = 1\). Then, for the other direction assume \(x \notin\Gamma[\alpha]\). Once again select a \(\ddot{\rho}(\widetilde{\alpha})\)-optimal flat \(F\), and let \(\beta\in F\) be any word with \(\widetilde{\beta}\subseteq\widetilde{\alpha}\). Observe \(x\notin\widetilde{\beta}\), as otherwise the word \(\beta'x\) is a \(\beta\)-prefix for some subword \(\beta'\) of \(\beta\). Then, applying the Forking Lemma to \([\beta' x]\) and \([\alpha]\) (take note that \([\beta']\sqsubseteq [\alpha]\) and \([\beta'x]\succ[\beta']\) implies \([\beta']=[\alpha]\sqcap[\beta'x]\)) shows \(x\in \Gamma[\alpha]\), a contradiction. Hence \(\widetilde{\beta}\subseteq\widetilde{\alpha}\), which implies \([\beta]\sqsubseteq [\alpha]\). Then, recalling that our assumptions about the greedy algorithm ensure that \(b\) satisfies the law of diminishing returns, by way of Lemma 11 one finds \(\left(b_{F}/\widetilde{\alpha}\right)(x)=\left(b_{[\beta]}/\widetilde{\alpha}\right)(x) \geq \left(b_{[\alpha]}/\widetilde{\alpha}\right)(x)\). So by combining this with \([\alpha]\) being \(\ddot{\rho}(\widetilde{\alpha})\)-optimal, \[\begin{gather} \psi_{F}(\widetilde{\alpha}+ x) = r(F) + \left(1 + \frac{1}{r(\Lambda) + 1}\right)\cdot b_F(\widetilde{\alpha}) +\left(1 + \frac{1}{r(\Lambda) + 1}\right)\cdot \left(b_{F}/\widetilde{\alpha}\right)(x),\\\geq \psi_{[\alpha]}(\widetilde{\alpha}) + \left(1 + \frac{1}{r(\Lambda) + 1}\right)\cdot \left(b_{F}/\widetilde{\alpha}\right)(x) = \psi_{[\alpha]}(\widetilde{\alpha}+x). \end{gather}\] Thus \([\alpha]\) is \(\ddot{\rho}(\widetilde{\alpha}+x)\)-optimal as well. So, as \(\left(\ddot{\rho}/\widetilde{\alpha}\right)(x) = \psi_{[\alpha]}(\widetilde{\alpha}+x) - \psi_{[\alpha]}(\widetilde{\alpha})\), we see \(x\notin\Gamma[\alpha]\) implies \(\left(\ddot{\rho}/\widetilde{\alpha}\right)(x) \neq 1\) by, \[\psi_{[\alpha]}(\widetilde{\alpha}+x) - \psi_{[\alpha]}(\widetilde{\alpha}) = \begin{cases} 1 + \frac{1}{r(\Lambda) + 1},\quad&\text{if }b_{[\alpha]}(x) \neq 0,\\ 0,&\text{otherwise}. \end{cases}\] And we’ve already seen \(\left(\ddot{\rho}/\widetilde{\alpha}\right)(x) = 1\) whenever \(x \in\Gamma[\alpha]\), so \(\left(\ddot{\rho}/\widetilde{\alpha}\right)(x) \in \{0\}\cup[1,\infty)\) holds too. ◻

Proof. Select an arbitrary set of letters \(X\subseteq \Sigma\). It should be clear that \(b_F(X) \leq (b/\kappa(F))(X)\). For the reverse inequality, take a subset \(Y\subseteq X\) such that \((b/\kappa(F))(X) = (b/\kappa(F))(Y) = |Y|\). Such a \(Y\) must exist: Because \(b\) is subcardinal, there must be a sequence \(y_1,\ldots, y_k\in X\) wsuch that \(k = (b/\kappa(F))(X)\) and \((b/\kappa(F) \cup \{y_1,\ldots,y_{i-1}\})(x_i) = 1\) for all \(i \in \{1,\ldots, k\}\). Hence, \[k = (b/\kappa(F))(\{y_1,\ldots,y_k\}) = (b/\kappa(F))(X),\] and so we can let \(Y = \{y_1,\ldots, y_k\}\). Now, notice that by subcardinality we must have \((b/\kappa(F))(Y-z) = |Y|-1\) for all \(z \in Y\). Hence, for any \(z \in Y\), \[b(\kappa(F)\cup Y) - b(\kappa(F)\cup Y - z) = 1,\] and so \(z\) lies in the support of any feasible word \(\alpha \in \Lambda\) such that \(|\widetilde{\alpha} \cap (\kappa(F)\cup Y)| = b(\kappa(F) \cup Y)\). However, as our choice of \(z\in Y\) was arbitrary, this means, \[\alpha\in\Lambda\text{ and }|\widetilde{\alpha} \cap (\kappa(F)\cup Y)| = b(\kappa(F) \cup Y) \implies Y \subseteq \widetilde{\alpha}.\]

With that, select a basic word \(\beta \in \Lambda\) achieving \(|\widetilde{\beta} \cap (\kappa(F)\cup Y)| = b(\kappa(F) \cup Y)\). Then, from \(Y\subseteq \widetilde{\beta}\) and \((b/\kappa(F))(Y) = |Y|\) we observe, \[\label{eq:2345r} |\widetilde{\beta}\cap \kappa(F)| = b(\kappa(F)\cup Y) - |Y| =b(\kappa(F)\cup Y) - (b/\kappa(F))(Y) = b(\kappa(F)) = r(F).\tag{12}\] Or put in other terms, there are exactly \(r(F)\) letters from \(\kappa(F)\) in the support of \(\beta\). Well, for any \(\gamma \in F\), it follows by exchange that there is a simple word \(\pi \in (\widetilde{\beta} \setminus \kappa(F))^*\) which can be appended onto \(\gamma\) to make a basic word \(\gamma\pi \in \Lambda\). However, the support of \(\pi\) cannot overlap with \(\kappa(F)\), as \(\pi \in \Lambda/\gamma=\Lambda/F\) by construction. By this and Eq. 12 , there are exactly \(r(\Lambda)-r(F)\) to choose from \(\widetilde{\beta}\setminus\kappa(F)\) to form \(\pi\). But, because \(|\gamma| = r(F)\) and \(\gamma\pi\) is basic we also have that \(|\pi| = r(\Lambda)-r(F)\). Therefore \(\widetilde{\pi} = \widetilde{\beta}\setminus\kappa(F)\), which implies \(Y \subseteq \widetilde{\pi}\). Then by recalling \(\pi \in \Lambda/F\) and \(Y\subseteq X\), \[b_F(X) \geq b_F(Y) \geq |\widetilde{\pi} \cap Y| = |Y| = (b/\kappa(F))(X),\] and we conclude \(b_F(X) = (b/\kappa(F))(X)\). ◻

Proof. Recall \(\lfloor\psi_F(X)\rfloor = r(F)+b_F(X)\) for all \(F\in\Lambda/\mathord{\sim}\). It follows then that \(r(F)+b_F(X) < r(F')+b_{F'}(X)\) implies \(\psi_F(X) < \psi_{F'}(X)\). Hence, we need only show, \[\label{eq:fjfkll} \{F\in\Lambda/\mathord{\sim}\mid(\exists\alpha\in F)\;\widetilde{\alpha}\subseteq X\}\cap\left(\mathop{\mathrm{arg\,min}}_{F\in\Lambda/\mathord{\sim}}r(F)+b_F(X)\right) \neq \varnothing.\tag{13}\] Well, via Corollary 1 we have \(b(\kappa(F)\cup X) = r(F) + b_F(X)\). Furthermore, monotonicity of the basis rank makes \(b(X) \leq b(\kappa(F)\cup X)\), and for the bottom flat \([\epsilon]\) it should be clear that \(r[\epsilon] + b_{[\epsilon]}(X) = b(X)\). Combining these observations together shows, \[r[\epsilon] + b_{[\epsilon]}(X) \leq r(F) + b_F(X),\quad\forall F\in\Lambda/\mathord{\sim},\] and so because the empty word trivially satisfies \(\widetilde{\epsilon}\subseteq X\), the bottom flat \([\epsilon]\) witness Eq. 13 . ◻

Proof. This essentially follows by showing \(F\mapsto r(F) + b_F(X)\) is a submodular function over \(\mathscr{L}(\Lambda)\). Once submodularity is shown, a standard technique for showing that the minimizers form a distributive lattice can be applied (see [44] for a working example over a ring of sets).

Select two flats \(F,F'\in\Lambda/\mathord{\sim}\). To show submodularity, first observe because \(\kappa(F)\cup\kappa(F')\) is a partial alphabet, it follows that \(b(\kappa(F)\cup\kappa(F')) = r(\kappa(F)\cup\kappa(F'))\). However, \(r(Y) = r(\kappa(Y))\) for all \(Y\subseteq \Sigma\), and \(\kappa(\kappa(F)\cup\kappa(F')) = \kappa(F\sqcup F')\) since \(\kappa(\kappa(F)\cup\kappa(F'))\) is the join of \(\kappa(F)\) and \(\kappa(F')\) in the lattice of flat supports. Thus, \[\label{eq:783473} \left(b/\kappa(F)\cup\kappa(F')\right)(\kappa(F\sqcup F')) = 0.\tag{14}\] Now, our assumptions make \(b\) a matroid rank function. We leverage this with Corollary 1, \[\def\arraystretch{1.25} \begin{array}{lll} r(F) \!\!\!\!&+\; r(F') + b_F(X) + b_{F'}(X) = b(\kappa(F)\cup X) + b(\kappa(F') \cup X),\quad&\text{by Corollary~\ref{cor:bf-eq}},\\ &\geq b((\kappa(F)\cap\kappa(F'))\cup X) + b(\kappa(F)\cup\kappa(F')\cup X),\quad&\text{by submodularity},\\ &\geq b((\kappa(F)\cap\kappa(F'))\cup X) + b(\kappa(F\sqcup F')\cup X),\quad&\text{by Eq.~\ref{eq:783473}},\\ &= b_{F\sqcap F'}((\kappa(F)\cap\kappa(F'))\cup X) + b_{F\sqcup F'}(X) + r(F\sqcap F') + r(F\sqcap F'),\quad&\text{by Corollary~\ref{cor:bf-eq}},\\ &\geq b_{F\sqcap F'}(X) + b_{F\sqcup F'}(X) + r(F\sqcap F') + r(F\sqcup F'),\quad&\text{by monotonicity}. \end{array}\] So we have submodularity over \(\mathscr{L}(\Lambda)\). It is easy now to show that the minimizers form a sublattice: Suppose \(F\) and \(F'\) additionally satisfy, \[\label{eq:min-assump} r(F) + b_F(X) = r(F') + b_{F'}(X)\text{ and }(\forall F'' \in \Lambda/\mathord{\sim})\;r(F) + b_F(X) \leq r(F'') + b_{F''}(X).\tag{15}\] Well, by the averaging principle, \[\min\{r(F\sqcap F') + b_{F\sqcap F'}(X), r(F\sqcup F') + b_{F\sqcup F'}(X)\} \leq r(F) + b_F(X),\] which implies \(\min\{r(F\sqcap F') + b_{F\sqcap F'}(X), r(F\sqcup F') + b_{F\sqcup F'}(X)\} = r(F) + b_F(X)\) by Eq. 15 . Therefore, to maintain the submodular law, \[\max\{r(F\sqcap F') + b_{F\sqcap F'}(X), r(F\sqcup F') + b_{F\sqcup F'}(X)\} \leq r(F') + b_{F'}(X).\] And so, \(F\sqcap F'\) and \(F\sqcup F'\) are also minimizers. ◻

Proof. Now, for 1., let \(F_X'\) be another \(\ddot{\rho}(X)\)-optimal flat. Lemma 5 implies that both \(F_X\) and \(F_X'\) minimize \(F\mapsto\lfloor\psi_F(X)\rfloor\), and so through Lemma 6 we observe the join \(F_X\sqcup F_X'\) minimizes this function as well. Without loss of generality, we assume either \(F_X\) and \(F_X'\) are incomparable or \(F_X\) and \(F_X'\) can be ordered as \(F_X\sqsubseteq F_X'\). Hence, as some \(\alpha\in F_X\) and \(\beta \in F_X'\) such that \(\widetilde{\alpha}\cup\widetilde{\beta}\subseteq X\) are guaranteed to exist by \(\ddot{\rho}(X)\)-feasibility, we apply the Amplified Forking Lemma to witness the existence of a subword \(\beta'\) of \(\beta\) such that \(\beta'\in F_X\sqcup F_X'/F_X\). Thus, \(\alpha\beta'\in F_X\sqsubseteq F_X'\) shows that the join is \(\ddot{\rho}(X)\)-feasible as well. Now, because \(b_{F_X}(X) \geq |\widetilde{\beta'\gamma}\cap X|\) and \(\widetilde{\beta}'\cap\widetilde{\gamma} = \varnothing\) for every \(\gamma \in F_X\sqcup F_X'\), by letting selecting such a \(\gamma\) satisfy \(b_{F_X\sqcup F_X'}(X) =|\widetilde{\gamma}\cap X|\) (and recalling \(\widetilde{\beta}'\subseteq\widetilde{\beta}\subseteq X\)), \[\label{eq:57ty} b_{F_X}(X) - b_{F_X\sqcup F_X'}(X) \geq |\widetilde{\beta'\gamma}\cap X| - |\widetilde{\gamma}\cap X| = |\beta'|.\tag{16}\] Therefore, \[\psi_{F_X}(X) - \psi_{F_X\sqcup F_X'}(X) = \lfloor\psi_{F_X}(X)\rfloor - \lfloor\psi_{F_X\sqcup F_X'}(X)\rfloor + \frac{b_{F_X}(X) - b_{F_X\sqcup F_X'}(X)}{r(\Lambda) + 1} \geq \frac{|\beta'|}{r(\Lambda) + 1}.\] Optimality requires this equal zero, forcing \(|\beta'| = 0\). Thus \(F_X = F_X\sqcup F_X'\), so \(F_X\) and \(F_X'\) are comparable as \(F_X'\sqsubseteq F_X\). But, as comparability implies \(F_X\sqsubseteq F_X'\) by earlier assumptions, \(F_X = F_X'\).

Next up we examine 2. Let \(\beta \in F_X\) with \(\widetilde{\beta}\subseteq X\). One witnesses a subword \(\beta'\) of \(\beta\) with \(\beta'\in F_X\sqcup F_Y/F_Y\) by way of the Amplified Forking Lemma. Select \(\alpha \in F_Y\) with \(\widetilde{\alpha}\subseteq Y\). Then it is clear that \(\alpha\beta'\in F_X\sqcup F_Y\) and \(\widetilde{\alpha\beta'} \in F_X\sqcup F_Y\), thereby making the join \(\ddot{\rho}(Y)\)-feasible. By repeating the same logic underlying Eq. 16 , one can observe the bound, \[b_{F_Y}(Y) - b_{F_X\sqcup F_Y}(Y) \geq |\beta'| = r(F_X\sqcup F_Y) - r(F_Y).\] However, we also have \(b_{F_Y}(Y) - b_{F_X\sqcup F_Y}(Y) \leq r(F_X\sqcup F_Y) - r(F_Y)\): Take a \(\gamma \in \Lambda/F_Y\) with \(b_{F_Y}(Y) = |\widetilde{\gamma}\cap Y|\). By the exchange axiom, there is a word \(\gamma'\in \Lambda/F_X\sqcup F_Y\) of length \(r(\Lambda) - r(F_X\sqcup F_Y)\) supported on a subset of \(\widetilde{\gamma}\). This implies there are at most \(r(F_X\sqcup F_Y) - r(F_Y)\) letters in \(\widetilde{\gamma}\cap Y\) which are not contained in \(\widetilde{\gamma}'\cap Y\). Hence, \[r(F_X\sqcup F_Y) - r(F_Y) \geq |\widetilde{\gamma}\cap Y| - |\widetilde{\gamma}'\cap Y| \geq b_{F_Y}(Y) - b_{F_X\sqcup F_Y}(Y).\] So, we’ve identified \(b_{F_Y}(Y) - b_{F_X\sqcup F_Y}(Y) = r(F_X\sqcup F_Y) - r(F_Y)\). This makes, \[\psi_{F_X\sqcup F_Y}(Y) - \psi_{F_Y}(Y) = r(F_X\sqcup F_Y) - r(F_Y) + \left(1+\frac{1}{r(\Lambda) + 1}\right)\cdot\left(r(F_Y) - r(F_X\sqcup F_Y)\right) \leq 0,\] and so \(F_X\sqcup F_Y\) is also \(\ddot{\rho}(Y)\)-optimal. By 1., it can only be that \(F_Y = F_X\sqcup F_Y\), making \(F_X\sqsubseteq F_Y\).

Now, we’ll show 3. and 4. together. For 4. assume \(F_X\sqsubset F_{X+z}\). Let \(\beta \in F_{X+z}\) be such that \(\widetilde{\beta}\subseteq X+z\). By the Amplified Forking Lemma there is a subword \(\beta'\) of \(\beta\) such that \(\beta'\in F_{X+z}/F_X\). Notice that 3. and 4. follow if \(\Gamma(F_X) \cap X = \varnothing\). Specifically, this is a restatement of 3., and it would force \(\beta' = z\alpha\) for some \(\widetilde{\alpha}\subseteq X\) by pigeonhole principle. So by way of contradiction, assume there exists \(y \in \Gamma(F_X) \cap X\). For convenience, let \(F_0 \triangleq \kappa^{-1}(\kappa(F_X)+y)\) Notice, by fixing \(\gamma \in \Lambda/F_0\) with \(b_{F_0}(X) = |\widetilde{\gamma}\cap X|\), since \(y\gamma \in F_X\) we have, \[b_{F_X}(X) - b_{F_0}(X) \geq |\widetilde{y\gamma}\cap X| - |\widetilde{\gamma}\cap X| = 1.\] Thus, \[\begin{gather} \psi_{F_X}(X) - \psi_{F_0}(X) = r(F_X) - r(F_0) + \left(1+\frac{1}{r(\Lambda)+1}\right)\cdot\left(b_{F_X}(X) - b_{F_0}(X)\right),\\\geq r(F_X) - (r(F_X) + 1) + \left(1+\frac{1}{r(\Lambda)+1}\right)=\frac{1}{r(\Lambda)+1}, \end{gather}\] and so \(\psi_{F_0}(X) < \psi_{F_X}(X)\). It is easy to see that \(F_0\) is \(\ddot{\rho}(X)\)-feasible (since we can append \(y\) onto the end of any word in \(F_X\) to achieve a word spanning \(F_0\), and \(y\in X\)). So we’ve found that \(F_X\) is not \(\ddot{\rho}(X)\)-optimal, a contradiction. As discussed this witnesses 3. and 4., and so concludes the lemma. ◻

Proof. First we show \(b(Z) = b(Z\cap \kappa({F_Z})) + b_{F_Z}(Z)\) for arbitrary \(Z\subseteq\Sigma\). Our assumptions make the basis rank \(b\) submodular. So, \[\label{eq:dddss} b(Z) = b(Z \cap \kappa({F_Z})) + (b/Z \cap \kappa({F_Z}))(Z).\tag{17}\] Because \({F_Z}\) is \(\ddot{\rho}(Z)\)-feasible the existence of \(\alpha \in Z^*\) such that \(\alpha \in {F_Z}\) follows. This construction implies \((b/Z \cap \kappa({F_Z}))(Z) = (b/\kappa({F_Z}))(Z)\) since by the law of diminishing returns, \[(b/\widetilde{\alpha})(Z) \geq (b/Z \cap \kappa({F_Z}))(Z) \geq (b/\kappa({F_Z}))(Z) = (b/\widetilde{\alpha})(Z).\] Thus we see, \[\label{eq:bZ61sum} b(Z) = b(Z\cap \kappa({F_Z})) + b_{F_Z}(Z),\tag{18}\] by substituting \((b/Z \cap \kappa({F_Z}))(Z) = (b/\kappa({F_Z}))(Z)\) into Eq. 17 . Since \(b(Z\cap\kappa(F_Z)) = r(F_Z)\) by way of \(\ddot{\rho}(Z)\)-feasibility, we observe \(\lfloor \psi_{F_Z}(Z)\rfloor = b(Z)\) as a consequence. Finally, if \(F \in \Lambda/\mathord{\sim}\) is such that \(F\sqsubseteq F_Z\) then applying this argument to the minor \(\Lambda/F\) shows, \[F\sqsubseteq F_Z \implies b_F(Z) = b_F(Z\cap\kappa({F_Z}) + b_{F_Z}(Z).\] Take note that \(F_X \sqsubseteq F_Y\) by Lemma 7.2, so \(b_{F_X}(Y) = b_{F_X}(Y\cap\kappa(F_Y)) + b_{F_Y}(Y)\). However, because \(F_Y\) is \(\ddot{\rho}(Y)\)-feasible, \(b_{F_X}(Y\cap\kappa(F_Y)) = r(F_Y) - r(F_X)\). Therefore, \[\label{eq:ifyfzf} \lfloor \psi_{F_X}(Y)\rfloor = r(F_X) + b_{F_X}(Y) = r(F_X) - r(F_X) + r(F_Y) + b_{F_Y}(Y) = \lfloor \psi_{F_Y}(Y) \rfloor,\tag{19}\] i.e. \(\lfloor \psi_{F_X}(Y)\rfloor = \lfloor \psi_{F_Y}(Y) \rfloor\). This and Eq. 18 is used in what follows.

Now first suppose \(F_X = F_Y\). Then \(\ddot{\rho}(X) \leq \ddot{\rho}(Y)\) follows from \(X\subseteq Y\), \(r(F_X) = r(F_Y)\), and \(b_{F_X} = b_{F_Y}\). In the other case, where \(F_X \neq F_Y\), we see \(F_X \sqsubset F_Y\) by Lemma 7.2. So there exists a nonempty \(z\beta \in F_Y/F_X\) with \(\widetilde{z\beta}\subseteq Y\). This makes \(z \in \Gamma(F_X)\), and by way of Lemma 7.3 we see \(z \notin X\). Now, we claim that any \(\beta \in F_X\) such that \(\widetilde{\beta}\subseteq X\) is such that \(|\beta| = r(X)\), which makes \(r(X) = r(F_X)\). Suppose this weren’t true. Let \(\gamma\in\Lambda\) be a longest word with \(\widetilde{\gamma}\subseteq X\). Then since \(\widetilde{\gamma}\) is independent in the matroid induced by \(b\), it follows by exchange that \(b(\widetilde{\gamma}) + (b/\widetilde{\gamma})(X) = b(X)\). Hence, as \(b(\widetilde{\gamma}) = r[\gamma]\) and \(b/\widetilde{\gamma} = b/\kappa[\gamma]\), we see \(\lfloor \psi_{[\gamma]}(X)\rfloor = \lfloor\psi_{F_X}(X)\rfloor\) by way of Eq. 18 . But \(r[\gamma] > r(F_X)\) by our assumptions, and so \(\psi_{[\gamma]}(X) < \psi_{F_X}(X)\) which contradicts the optimality of \(F_X\). So we have shown \(r(X) = r(F_X)\). Since \(z \in \Gamma(F_X)\), this implies \(z \notin \sigma_r(X)\). By Theorem 7, we have that \(\sigma_r(X)\) is \(b\)-closed. Then \((b/\sigma_{r}(X))(z) = 1\), and so by \(z \in Y\) and the law of diminishing returns (using \(\kappa(F_X)\subseteq \sigma_r(X)\) and Proposition 11) we observe \((b_{F_X}/X)(Y) > 0\). The upshot is that this implies \(\psi_{F_X}(Y) > \psi_{F_X}(X)\). Well, because the increments of \(\psi_{F_X}\) are greater than or equal to one, this also makes \(\lfloor\psi_{F_X}(Y)\rfloor > \lfloor\psi_{F_X}(X)\rfloor\). Therefore, by applying Eq. 19 we observe, \[\lfloor \psi_{F_Y}(Y)\rfloor = \lfloor\psi_{F_X}(Y)\rfloor > \lfloor\psi_{F_X}(X)\rfloor.\] But \(\lfloor \psi_{F_Y}(Y)\rfloor > \lfloor\psi_{F_X}(X)\rfloor\) implies \(\psi_{F_Y}(Y) > \psi_{F_X}(X)\). So monotonicity follows in all cases. ◻

Proof. Because \(F_{X+z}\) is \(\ddot{\rho}(X+z)\)-optimal, we require \(\lfloor\psi_{F_X}(X+z)\rfloor \geq \lfloor \psi_{F_{X+z}}(X+z)\rfloor\). \(F_X\sqsubset F_{X+z}\) implies \(\left(b_{F_X}/X\right)(z) = 1\), so plugging in \(\lfloor\psi_{F_X}(X+z)\rfloor = r(F_X) + b_{F_X}(X+z)\) and \(\lfloor\psi_{F_{X+z}}(X+z)\rfloor = r(F_{X+z}) + b_{F_{X+z}}(X+z)\) this makes, \[\label{eq:floor-psi-x-xz} r(F_X) + b_{F_X}(X) + 1 \geq r(F_{X+z}) + b_{F_{X+z}}(X+z).\tag{20}\] Assume the inequality is strict. Then, \(r(F_{X+z}) + b_{F_{X+z}}(X+z) \leq r(F_X) + b_{F_X}(X)\) as \(\left(b_{F_X}/X\right)(z) = 1\). However, \(\lfloor\psi_{F_{X+z}}(X+z)\rfloor \geq \lfloor\psi_{F_X}(X)\rfloor\) must hold to maintain the monotonicity of \(\ddot{\rho}\), so we find \(r(F_{X+z}) + b_{F_{X+z}}(X+z) = r(F_X) + b_{F_X}(X)\), or equivalently \(\lfloor \psi_{F_{X+z}}(X+z) \rfloor = \lfloor \psi_{F_X}(X)\rfloor\). Because \(F_X\sqsubset F_{X+z}\), \(r(F_X) < r(F_{X+z})\). This makes \(b_{F_X}(X) > b_{F_{X+z}}(X+z)\). Hence, \[\ddot{\rho}(X) = \lfloor \psi_{F_X}(X)\rfloor + \frac{b_{F_X}(X)}{r(\Lambda)+1} < \lfloor \psi_{F_{X+z}}(X+z) \rfloor + \frac{b_{F_{X+z}}(X+z)}{r(\Lambda)+1} = \ddot{\rho}(X+z),\] which contradicts the monotone structure of \(\ddot{\rho}\) shown in Proposition 12. And so we conclude the desired \(r(F_X) + b_{F_X}(X) + 1 = r(F_{X+z}) + b_{F_{X+z}}(X+z)\). ◻

Proof. Let \(F_X \neq F_{X+z}\), as otherwise \(r(F_{X+z}) - r(F_X) = 0\) and the lemma follows trivially. Then, by Lemma 7.4 there exists \(z\alpha\in F_{X+z}/F_X\) satisfying \(\widetilde{\alpha}\subseteq X\). We prove the lemma by verifying \(z\alpha \in \Lambda/F_Y\). To see why this suffices, observe that \(z\alpha\in\Lambda/F_Y\) implies, \[\def\arraystretch{1.25} \begin{array}{lll} \kappa(F_Y)\cup\widetilde{z\alpha} &\subseteq \kappa\left(\kappa(F_Y)\cup\widetilde{z\alpha}\right),\quad&\text{because \kappa(F_Y)\cup\widetilde{z\alpha} is a partial alphabet},\\ &\subseteq \kappa\left(\kappa(F_X)\cup\widetilde{z\alpha}\cup\kappa(F_Y)\right),\quad&\text{by Lemma~\ref{lem:big-stick}.2},\\ &\subseteq \kappa\left(\kappa(F_{X+z})\cup\kappa(F_Y)\right),\quad&\text{by z\alpha\in F_{X+z}/F_X},\\ &= \kappa(F_{X+z}\sqcup F_Y), \end{array}\] and so because one can examine Eq. 5 to see \(\kappa^{-1}:\left(2^\Sigma,\subseteq\right)\to\mathscr{L}(\Lambda)\) is order-preserving, we find \(\kappa^{-1}(\kappa(F_Y)\cup\widetilde{z\alpha}) \sqsubseteq F_{X+z}\sqcup F_Y\). But by assuming \(z\alpha\in\Lambda/F_Y\), it follows that, \[r(\kappa^{-1}(\kappa(F_Y)\cup\widetilde{z\alpha})) - r(F_Y) = |z\alpha|.\] Hence, by recalling that Lemma 7.2 shows \(F_{Y+z} \sqsupseteq F_{X+z} \sqcup F_Y\), \[r(F_{Y+z}) - r(F_Y) \geq |z\alpha| = r(F_{X+z})-r(F_X),\] and so the lemma follows upon verifying \(z\alpha\in\Lambda/F_Y\).

We’ll show \(z\alpha \in \Lambda/F_Y\) by proving that \(z\alpha'\in\Lambda/F_Y\) for every \(\alpha\)-prefix \(\alpha'\). Induct over \(|\alpha'|\), and first examine the case \(\alpha' = \epsilon\). Because \(\left(\ddot{\rho}/Y\right)(z)\neq 0\) by assumption, we find \(\left(b_{F_Y}/Y\right)(z) = 1\). This makes \(z \notin \kappa(F_Y)\), and so \(\kappa^{-1}(\kappa(F_X) + z) \not\sqsubseteq F_Y\). Therefore, because our construction makes \(z \in \Gamma(F_X)\), \(z \in \Gamma(F_Y)\) follows by applying the Forking Lemma to \(\kappa^{-1}(\kappa(F_X) + z)\) and \(F_Y\). Now for the inductive step, let \(\alpha' = \beta x\), and fix any \(y_1\ldots y_k \in F_Y/F_X\). We first show, \[\label{eq:cant-use-x} (\forall x' \in\widetilde{\beta x})(\nexists i \in\{1,\ldots, k\})\;y_1\ldots y_i x' \in\Lambda/F_X.\tag{23}\] Examine any \(y' \in \Sigma\) and \(i\in\{1,\ldots, k\}\) making \(y_1\ldots y_i y' \in \Lambda/F_X\). There are two cases, given by the ordering of \(F_Y\) and \(\kappa^{-1}(\kappa(F_X) \cup \{y_1,\ldots, y_i, y'\})\): If \(\kappa^{-1}(\kappa(F_X) \cup \{y_1,\ldots, y_i, y'\}) \not\sqsubseteq F_Y\), then as, \[\kappa^{-1}(\kappa(F_X) \cup \{y_1,\ldots, y_i, y'\}) \sqcap F_Y = \kappa^{-1}(\kappa(F_X) \cup \{y_1,\ldots, y_i\}),\] since \(\kappa^{-1}(\kappa(F_X) \cup \{y_1,\ldots, y_i, y'\}) \succ \kappa^{-1}(\kappa(F_X) \cup \{y_1,\ldots, y_i\})\), it follows by the Forking Lemma that \(y' \in \Gamma(F_Y)\). Therefore, by Lemma 7.3 implies \(y'\notin Y\), and as \(\widetilde{\beta x}\subseteq X\subseteq Y\) this shows \(y'\notin\widetilde{\beta x}\). Now assume \(\kappa^{-1}(\kappa(F_X) \cup \{y_1,\ldots, y_i, y'\}) \sqsubseteq F_Y\). Observe, this forces \(i < k\). Moreover, because \(z\beta \in \Lambda/F_Y\) by inductive hypothesis, it is clear that \(y' \notin \widetilde{\beta}\). By way of contradiction then, suppose \(y' = x\). Because \(y_1\ldots y_k\) is an arbitrary word in \(F_Y/F_X\), we can assume \(y_{i+1} = x\) without loss of generality. From our inductive hypothesis, \[y_1\ldots y_i x y_{i+2} \ldots y_k z \beta \in \Lambda/F_X,\] so the union of the supports of \(z\beta x\) and \(y_1\ldots y_i x\) are contained in the support of some \((\Lambda/F_X)\)-feasible word. Hence, as \(z\beta \in \Lambda/F_Y\) implies \(\widetilde{z\beta}\cap\{y_1,\ldots,y_i\} = \varnothing\), \(x \in \Lambda/F_X\) follows by the local poset property (which is easily seen to be closed under contraction by examining Definition 4). But Lemma 7.3 requires \(x\notin\Gamma(F_X)\) as \(x \in X\), a contradiction. So Eq. 23 holds.

With that done define \(F_0 \triangleq \kappa^{-1}(\kappa(F_Y) \cup \widetilde{z\beta})\) for notational convenience, and take some basic \(\pi = c_1\ldots c_{r(\Lambda/F_0)} \in \Lambda/F_0\). We will examine a greedy optimization over \(\Lambda/F_X\), and use Eq. 23 to show a contradiction whenever \(z\beta x \not\in\Lambda/F_Y\). Note that it is folklore knowledge that contraction minors inherit the correctness properties of the greedy algorithm in our setting; we give a short proof in Appendix 10. So, let \(\beta = b_1\ldots b_{k'}\) and weigh the letters of the alphabet according to, \[w(a) \triangleq \begin{cases} 1 - (k - i + 1)\cdot\delta,\quad&\text{if }a = y_i,\\ i\cdot\delta,\quad&\text{if }a=b_i,\\ (k'+1)\cdot\delta,\quad&\text{if }a=x,\\ 1,\quad&\text{if }a=z,\\ 2 + i\cdot\delta,\quad&\text{if }a=c_i,\\ \infty,\quad&\text{otherwise}, \end{cases}\] where \(\delta > 0\) is a small real selected so that, \[\label{eq:delta-bound} \max\{k,k' + 1\}\cdot\delta < \frac{1}{2}.\tag{24}\] Towards a contradiction, let’s assume \(z\beta x \notin\Lambda/F_Y\). One can identify that applying the greedy algorithm to \(\Lambda/F_X\) will form the word \(y_1\ldots y_k z\beta\pi\): Beginning at the empty word \(\epsilon\), because the continuations of \(\epsilon\) in \(\Lambda/F_X\) equal \(\Gamma(F_X)\), and \(\widetilde{\beta x}\subseteq X\) makes \(\widetilde{\beta x}\cap\Gamma(F_X)=\varnothing\) by Lemma 7.3, the algorithm cannot select any of \(\{b_1,\ldots,b_{k'}, x\}\). Therefore, because our construction makes \(w(y_1) < w(y_2) < \ldots < w(y_k) < w(z)\), and \(w(z) < w(c_i)\) for all \(c_i \in \widetilde{\pi}\), the greedy algorithm selects \(y_1\) as its first letter. Then, due to Eq. 23 , similar logic shows that the greedy algorithm forms \(y_1\ldots y_k\) over the next \(k-1\) steps. For the \((k+1)^\text{th}\) step, see that \(z\) is the continuation because \(z\beta \in \Lambda/F_Y\) by our inductive hypothesis, and \(y_1\ldots y_k\in F_Y/F_X\). Then, it follows (once again) from Eq. 23 that \(z\) is the continuation of least weight. So, the greedy algorithm selects \(z\). Following this, the greedy algorithm forms the word \(y_1\ldots y_k z \beta\) over the next \(k'\) steps, since each \(b_i\) is a minimum weight continuation of \(y_1\ldots y_k z b_1\ldots b_{i-1}\), as, \[w(b_i) < w(b_{i+1}) < \ldots < w(b_{k'}) < w(x) < w(c_1) < \ldots < w\left(c_{r(\Lambda/F_0)}\right).\] Here, take note that \(y_1\ldots y_k z \beta \in F_0/F_X\) by \(y_1\ldots y_k \in F_Y/F_X\) and our definition of \(F_0\). Because \(z\beta x \notin\Lambda/F_Y\) by assumption, it thus follows that \(x\notin\Gamma(F_0)\). Furthermore, \[\begin{align} \kappa^{-1}\left(\kappa(F_X) \cup \widetilde{z\beta x}\right) \succ \kappa^{-1}\left(\kappa(F_X) \cup \widetilde{z\beta}\right),&&\text{and},&&\kappa^{-1}\left(\kappa(F_X) \cup \widetilde{z\beta}\right) \sqsubseteq F_0, \end{align}\] so \(x\notin\Gamma(F_0)\) makes (by the contrapositive) of the Forking Lemma, \[\kappa^{-1}\left(\kappa(F_X) \cup \widetilde{z\beta x}\right) \sqsubseteq F_0.\] Hence, \(x \in \kappa(F_0)\), meaning there is no \(\xi\in\Sigma^*\) such that \(y_1\ldots y_k z \beta \xi x\) can be feasible in \(\Lambda/F_X\). Importantly, this forces the greedy algorithm to select continuations from \(\widetilde{\pi}\) until it terminates with \(y_1\ldots y_k z \beta \pi\), as we made the weight of every other remaining letter infinite. The weight of the resulting word is then, \[\label{eq:greedy-value} w(\{y_1,\ldots, y_k, z\}\cup\widetilde{\beta}\cup\widetilde{\pi}) = 1 + \left(\sum_{i=1}^{k} 1 - (k-i + 1)\cdot \delta\right) + \left(\sum_{i=1}^{k'} i\cdot \delta\right) + w(\widetilde{\pi}).\tag{25}\]

Now, recall \(z\beta x \in \Lambda/F_X\). By applying the exchange property to \(z\beta x\) and \(y_1\ldots y_k z \beta \pi\) there is a word \(\gamma\in\Sigma^*\) with \(\widetilde{\gamma}\subseteq \{y_1,\ldots, y_k\}\cup\widetilde{\pi}\) which makes a basic word \(z\beta x \gamma \in\Lambda/F_X\). Hence, \(z\beta x \gamma\) is feasible for our optimization. But, we can bound the weight of this word as follows, \[\begin{align} w(\widetilde{\beta}\cup\widetilde{\gamma}&\cup\{x,z\}) \leq 1 + \left(\sum_{i=2}^{k} 1 - (k-i + 1)\cdot \delta\right) + \left(\sum_{i=1}^{k'+1} i\cdot \delta\right) + w(\widetilde{\pi}),\\ &= (k+k' + 1)\cdot \delta + \left(\sum_{i=1}^{k} 1 - (k-i + 1)\cdot \delta\right) + \left(\sum_{i=1}^{k'} i\cdot \delta\right) + w(\widetilde{\pi}). \end{align}\] From Eq. 24 it is apparent that \((k+k'+1)\cdot\delta <1\). Then by examining Eq. 25 we find, \[w(\{y_1,\ldots, y_k, z\}\cup\widetilde{\beta}\cup\widetilde{\pi}) > w(\widetilde{\beta}\cup\widetilde{\gamma}\cup\{x,z\}),\] which means that the greedy algorithm fails to optimize \(\alpha\mapsto \sum_{a\in\widetilde{\alpha}} w(a)\) over \(\Lambda/F_X\), a contradiction. Hence \(z\alpha' = z\beta x\in\Lambda/F_Y\), which makes \(z\alpha\in\Lambda/F_Y\) by the principle of induction. ◻

Proof of Main Result 1. First we verify that \(\ddot{\rho}\) is a polymatroid rank function. Well, it is clear that \(\ddot{\rho}(\varnothing) = r[\epsilon]\), so \(\ddot{\rho}\) is normalized. Furthermore, monotonicity was proven in Proposition 12. Now, fix \(X,Y\subseteq \Sigma\) and \(z \in\Sigma\). For submodularity we will verify the law of diminishing returns, i.e. \(X\subseteq Y\) implies \(\left(\ddot{\rho}/X\right)(z)\geq \left(\ddot{\rho}/Y\right)(z)\). So, assume \(X\subseteq Y\). By monotonicity, \(\left(\ddot{\rho}/X\right)(z) \geq 0\). And so the desired inequality is clear if \(\left(\ddot{\rho}/Y\right)(z) = 0\). In light of this, suppose \(\left(\ddot{\rho}/Y\right)(z) \neq 0\). As outlined before, one applies Lemma 9 to Eq. 21 to obtain Eq. 22 . Recalling that Eq. 21 is equivalent to \(\lfloor\psi_{F_{X+z}}(X+z)\rfloor -\lfloor \psi_{F_X}(X)\rfloor = \lfloor\psi_{F_{Y+z}}(Y+z)\rfloor -\lfloor \psi_{F_Y}(Y)\rfloor\), this equality and Eq. 22 imply, \[\begin{gather} \left(\ddot{\rho}/X\right)(z) = \lfloor\psi_{F_{X+z}}(X+z)\rfloor -\lfloor \psi_{F_X}(X)\rfloor + \frac{b_{F_{X+z}}(X+z) - b_{F_X}(X)}{r(\Lambda)+1},\\ \geq \lfloor\psi_{F_{Y+z}}(Y+z)\rfloor -\lfloor \psi_{F_Y}(Y)\rfloor + \frac{b_{F_{Y+z}}(Y+z) - b_{F_Y}(Y)}{r(\Lambda)+1} = \left(\ddot{\rho}/Y\right)(z), \end{gather}\] hence the law of diminishing returns. Thus, \(\ddot{\rho}\) is a polymatroid rank function. And so, by Proposition 10 we see \(\ddot{\rho}\) is a representation. What remains is verifying alignment. We inspect the composition \(\varphi = \sigma_{\ddot{\rho}}\circ\kappa\). The inclusion axiom should be clear. For agreement, select \(\alpha \in \Lambda\) and \(x \in \kappa[\alpha]\setminus\widetilde{\alpha}\). By the contrapositive of Proposition 6, there exists no \(\beta \in \Lambda/\alpha\) such that \(x \widetilde{\beta}\). Suppose \(\alpha\beta\) is feasible and basic. Combining our previous observation with optimism shows the existence of a strict \(\alpha\)-prefix \(\alpha'\) with \(x \in \Gamma[\alpha']\). Therefore \((\ddot{\rho}/\widetilde{\alpha})(x) < 1\) by \(\alpha x \notin \Lambda\) and the law of diminishing returns. So, \((\ddot{\rho}/\widetilde{\alpha})(x) = 0\) by Proposition 10. Since our choice of \(x \in \kappa[\alpha]\setminus\widetilde{\alpha}\) was arbitrary it follows \((\ddot{\rho}/\widetilde{\alpha})(\kappa[\alpha]) = 0\), and so \(\ddot{\rho}(\kappa[\alpha]) = \ddot{\rho}(\widetilde{\alpha}) = |\alpha|\) by submodularity. This shows that \(\varphi\) satisfies agreement. Finally, select flats \(F,F'\in\Lambda/\mathord{\sim}\) such that \(F\prec F'\). We note that for there to exist a \(\ddot{\rho}\)-closed set between \(\varphi(F)\) and \(\varphi(F')\), there would have to exist some letter \(x \in \Sigma\) with \(0 < (\ddot{\rho}/\varphi(F))(x) < 1\). However, agreement shows \(\sigma_{\ddot{\rho}}(\widetilde{\alpha}) = \varphi(F)\) for all \(\alpha \in F\). So, this is equivalent to \(0 < (\ddot{\rho}/\widetilde{\alpha})(x) < 1\) for some \(\alpha \in F\), which is impossible by Proposition 10. ◻

Proof of Main Result 2. First, we show alignment implies the above three statements. For 1., select any \(y\notin\kappa[\alpha]\). By Proposition 6, there exists \(\beta\in\Lambda/\alpha\) such that \(\alpha\beta y \in \Lambda\). It follows that \((\rho/\widetilde{\alpha\beta})(y) = 1\), so \((\rho/\widetilde{\alpha})(y) \geq 1\) by the law of diminishing returns. Equivalently, \(y \notin \sigma_\rho(\widetilde{\alpha})\). Because \(y\) was an arbitrary letter beyond the flat support, this shows \(\sigma_\rho(\widetilde{\alpha})\subseteq \kappa[\alpha]\) by contraposition. Continuing on, let \(\varphi:\mathscr{L}(\Lambda)\to\mathscr{L}(\rho)\) be the mapping witnessing alignment. By agreement and inclusion, \(\varphi[\alpha] \subseteq \sigma_\rho(\widetilde{\alpha})\). But inclusion also makes \(\beta\sim\alpha\) imply \(\widetilde{\beta}\subseteq \varphi[\alpha]\), so \(\kappa[\alpha]\subseteq \varphi[\alpha]\) as well. This shows, \[\label{eq:keqs} \sigma_\rho(\widetilde{\alpha}) \subseteq \kappa[\alpha] \subseteq \varphi[\alpha] \subseteq\sigma_\rho(\widetilde{\alpha}),\tag{26}\] and so \(\kappa[\alpha]\) is \(\rho\)-closed, hence 1. follows.

Observe, Eq. 26 shows that \(\kappa = \varphi\), and so \(\kappa\) is cover-preserving by the alignment axioms. Another consequence of Eq. 26 is we may restrict the codomain of \(\kappa\) to \(\mathscr{L}(\rho)\) without problem. Conveniently, because \(\kappa\) defines an isomorphism between \(\mathscr{L}(\Lambda)\) and the flat supports ordered by containment, it follows that \(\kappa\) is order-preserving and order-reflecting onto \(\mathscr{L}(\rho)\). This makes \(\kappa\) an order-embedding between \(\mathscr{L}(\Lambda)\) and \(\mathscr{L}(\rho)\). Recall \(\mathscr{L}(\Lambda)\) is semimodular. Lemma 1 of [45] states that every cover-preserving order-embedding originating from a semimodular lattice is join-preserving. Therefore, \(\kappa\) is a lower adjoint by Lemma 1. As adjoints uniquely determine each other, using Eq. 2 we see, \[\varphi^*(X) = \bigsqcup\{F\in\Lambda/\mathord{\sim}\mid \kappa(F) \subseteq X\} = \kappa^{-1}\left(\bigcup\{\widetilde{\alpha}\mid \alpha \in \Lambda\cap X!\}\right) = \kappa^{-1}(X).\] Hence, \(\kappa:\mathscr{L}(\Lambda)\rightleftarrows\mathscr{L}(\rho):\kappa^{-1}\) is a Galois connection. This gives 3., so alignment implies (1-3).

Now, for the other direction assume (1-3) are true; we prove that \(\kappa\) is a mapping \(\mathscr{L}(\Lambda)\to\mathscr{L}(\rho)\) satisfying the alignment axioms. 1. shows that this task is well-defined, while 2. shows that \(\kappa\) is cover-preserving. Inclusion also follows by the definition of \(\kappa\) making \(\widetilde{\alpha}\subseteq\kappa[\alpha]\). Note, this implies \(\sigma_\rho(\widetilde{\alpha}) \subseteq \kappa[\alpha]\). Then by the definition of a Galois connection, \(\sigma_\rho(\widetilde{\alpha}))\subseteq \kappa[\alpha]\) implies \(\kappa^{-1}(\sigma_\rho(\widetilde{\alpha}))\sqsubseteq [\alpha]\). But, \([\alpha] = \kappa^{-1}(\widetilde{\alpha})\) makes \([\alpha]\sqsubseteq \kappa^{-1}(\sigma_\rho(\widetilde{\alpha}))\) as well, so we have \([\alpha] = \kappa^{-1}(\sigma_{\rho}(\widetilde{\alpha}))\). Continuing on, recall that \(\kappa\circ\kappa^{-1}\) is an interior operator. As it is deflationary, we have \(\sigma_\rho(\widetilde{\alpha})\supseteq \kappa(\kappa^{-1}(\sigma_\rho(\widetilde{\alpha}))\). Then, substituting \([\alpha] = \kappa^{-1}(\sigma_{\rho}(\widetilde{\alpha}))\) shows \(\sigma_\rho(\widetilde{\alpha})\supseteq \kappa[\alpha]\). Combining this with our initial observation \(\sigma_\rho(\widetilde{\alpha})\subseteq\kappa[\alpha]\), we see \(\sigma_\rho(\widetilde{\alpha}) = \kappa[\alpha]\). And so we have agreement. ◻

Proof. Observe, if \(\accentset{\vee}{\rho}\) is both a polymatroid rank function and a representation, then because \(\accentset{\vee}{\rho}\) is integral Proposition 1 would show \(\accentset{\vee}{\rho}\) is aligned. With that settled, let \(\rho\) be any aligned representation of \(\Lambda\), and select any subset \(X\subseteq \Sigma\). Fix a flat \(F\in\Lambda/\mathord{\sim}\) with \(X \subseteq \kappa(F)\) and \(\accentset{\vee}{\rho}(X) = r(F)\). Then, \(X\subseteq\kappa(F)\) implies \(\rho(X) \leq \rho(\kappa(F))\) since \(\rho\) is a polymatroid rank function. But \(\rho(\kappa(F)) = r(F)\) because \(\rho\) is aligned. Therefore, \[\rho(X) \leq \rho(\kappa(F)) = r(F) = \accentset{\vee}{\rho}(X),\] and we conclude the result. ◻

Proof of Proposition 15. Fix subsets \(X, Y\subseteq \Sigma\) and let, \[\begin{align} M_X \triangleq \mathop{ \mathpalette\@updown\bigsqcup }\{F\in\Lambda/\mathord{\sim}\mid X\subseteq\kappa(F)\}. \end{align}\] Define \(M_Y\) similarly. Our construction makes \(X\cup Y \subseteq \kappa(M_X\sqcup M_Y)\), and \(X\cap Y \in \kappa(M_X\sqcap M_Y)\) by assuming the flat supports are closed under intersection. By semimodularity, \[\accentset{\vee}{\rho}(X) + \accentset{\vee}{\rho}(Y) = r(M_X) + r(M_Y) \geq r(M_X\sqcap M_Y) + r(M_X \sqcup M_Y) \geq \accentset{\vee}{\rho}(X\cap Y) + \accentset{\vee}{\rho}(X\cup Y).\] Thus, \(\accentset{\vee}{\rho}\) is submodular. Furthermore, \(\accentset{\vee}{\rho}\) is clearly normalized, and monotonicity follows from the fact that \(X\subseteq Y\) would imply \(M_X \sqsubseteq M_Y\) in our construction. So \(\accentset{\vee}{\rho}\) is a polymatroid rank function.

Now, to show it is a representation we must first verify, \[\label{eq:ufntu} M_{\widetilde{\alpha}} = [\alpha],\quad\forall\alpha\in\Lambda,\tag{28}\] where \(M_{\widetilde{\alpha}}\) is defined as before. Fix \(\alpha \in \Lambda\), and see that \(\widetilde{\alpha} \subseteq \kappa[\alpha]\) implies \(M_{\widetilde{\alpha}}\sqsubseteq [\alpha]\). Because the flat supports are closed under intersection, we see \(\widetilde{\alpha}\subseteq \kappa(M_{\widetilde{\alpha}})\). So, there is no \(z \in \widetilde{\alpha}\) such that \(z\in\Gamma(M_{\widetilde{\alpha}})\). To maintain the exchange property the only possibility is \(M_{\widetilde{\alpha}}= [\alpha]\), and so Eq. 28 holds. Continuing on, fix \(\alpha \in \Lambda\) and \(z\in\Sigma\). First assume \(z\in\Gamma[\alpha]\). Then \([\alpha]\prec[\alpha z]\) and Eq. 28 show the desired \(\left(\accentset{\vee}{\rho}/\widetilde{\alpha}\right)(z) = 1\). Now assume \(z \notin\Gamma[\alpha]\). If \(z \in \kappa[\alpha]\), then once again with Eq. 28 it follows that the minimum flat containing \(\widetilde{\alpha}+z\) in its flat support is \([\alpha]\) itself. Therefore, \(z \in \kappa[\alpha]\) implies \(\left(\rho/\widetilde{\alpha}\right)(z) = 0\). In the other case, where \(z \notin\kappa[\alpha]\), there cannot exist any flat covering \([\alpha]\) containing \(\widetilde{\alpha} + z\) in its flat support. This is because if such a flat did exist then \(z\) would have to be a continuation by Proposition 6. Our insight here applies to \(M_{\widetilde{\alpha}+z}\) in particular. Observe that \(X \mapsto M_X\) is order-preserving between \(\left(2^\Sigma,\subseteq\right)\) and \(\mathscr{L}(\Lambda)\), and so Eq. 28 implies \(M_{\widetilde{\alpha} + z}\) lies above \([\alpha]\). And so, because \(M_{\widetilde{\alpha} + z}\) cannot cover \([\alpha]\) and \(z\notin\kappa[\alpha]\) implies \(M_{\widetilde{\alpha} + z}\neq[\alpha]\), the rank of \(M_{\widetilde{\alpha}+z}\) is at least 2 greater than that of \([\alpha]\). Thus, we find \(\left(\accentset{\vee}{\rho}/\widetilde{\alpha}\right)(z) \geq 2\). ◻

Proof of Main Result 3. Firstly, see that 1.\(\iff\)​5. by definition. We proceed by showing \(2.\iff 5.\) and \(5. \implies 3.\implies 4. \implies 5.\) First we verify \(5.\implies 2.\). Proposition 15 shows \(\accentset{\vee}{\rho}\) is an integral representation of \(\Lambda\), and so Main Result 2 makes \(\sigma_{\accentset{\vee}{\rho}}\circ\kappa = \kappa\) and \(\kappa\) a lower adjoint. By assuming 5. we find \(\kappa\) is meet-preserving. Furthermore, by Lemma 1 \(\kappa\) is also join-preserving, hence \(\sigma_{\accentset{\vee}{\rho}}\circ\kappa = \kappa\) is a lattice-embedding. Now for \(2. \implies 5.\), because \(\Lambda\) is a polymatroid greedoid we can once again let \(\sigma_{\accentset{\vee}{\rho}}\circ\kappa = \kappa\) by Main Result 2. So \(\kappa\) is a lattice-embedding. Then, because the meet operation on the closed sets of a polymatroid is intersection, this makes \(\kappa(F\sqcap F') = \kappa(F)\cap\kappa(F')\).

With that done, we see \(5.\implies 3.\) from Proposition 15. For \(3. \implies 4.\), first note that because 3. makes \(\Lambda\) possess an aligned representation, we may use the Galois connection \(\kappa:\mathscr{L}(\Lambda)\rightleftarrows\mathscr{L}(\accentset{\vee}{\rho}):\kappa^{-1}\) by Main Result 2. We show 4. by proving that the interior operator \(\kappa\circ\kappa^{-1}\) equals the identity mapping over \(\mathscr{L}(\accentset{\vee}{\rho})\). This is sufficient because if both \(\kappa\circ\kappa^{-1}\) and \(\kappa^{-1}\circ\kappa\) equal the identity mappings on their codomains then \(\kappa\) and \(\kappa^{-1}\) are inverses. Then \(\kappa:\mathscr{L}(\Lambda)\to\mathscr{L}(\accentset{\vee}{\rho})\) would define an order-preserving bijection, i.e. an isomorphism. Finally, we already know \(\kappa^{-1}\circ\kappa\) is the identity mapping because \(\kappa\) is injective (due to the correspondence between flats and the flat supports), so we need only examine \(\kappa\circ\kappa^{-1}\). Fix some \(X\subseteq \Sigma\). By inspecting the definition of \(\accentset{\vee}{\rho}\) we see that, \[\sigma_{\accentset{\vee}{\rho}}(X) = \bigcup\left\{\kappa(F)\mid X\subseteq\kappa(F)\text{ and }(\forall F'\in\Lambda/\mathord{\sim})\;X\subseteq\kappa(F')\implies r(F) \leq r(F')\right\}.\] Since \(\sigma_{\accentset{\vee}{\rho}}(X)\) is a union of flat supports, it follows that it is a partial alphabet. Hence, \(\sigma_{\accentset{\vee}{\rho}}(X) \subseteq \kappa(\sigma_{\accentset{\vee}{\rho}}(X))\), which is equivalent to \(\sigma_{\accentset{\vee}{\rho}}(X)\subseteq \kappa(\kappa^{-1}(\sigma_{\accentset{\vee}{\rho}}(X)))\). However, because the interior operator is deflationary we also have \(\kappa(\kappa^{-1}(\sigma_{\accentset{\vee}{\rho}}(X))) \subseteq \sigma_{\accentset{\vee}{\rho}}(X)\), and so \(\sigma_{\accentset{\vee}{\rho}}(X) = \kappa(\kappa^{-1}(\sigma_{\accentset{\vee}{\rho}}(X)))\). Thus 4.

The final component is proving \((4.)\implies (5.)\). Well, fix \(\alpha \in \Lambda\) and see that \([\alpha]\) is the unique flat of minimum rank containing the feasible support \(\widetilde{\alpha}\) in its flat support. By definition of \(\accentset{\vee}{\rho}\), this implies \(\sigma_{\accentset{\vee}{\rho}}(\widetilde{\alpha}) = \kappa[\alpha]\). Therefore, all flat supports are \(\accentset{\vee}{\rho}\)-closed sets. Recall \(\mathscr{L}(\Lambda)\cong\left(\kappa\left(2^\Sigma\right),\subseteq\right)\) due to the interval property, so by transitivity of isomorphism we have \(\left(\kappa\left(2^\Sigma\right),\subseteq\right)\cong\mathscr{L}(\accentset{\vee}{\rho})\). This makes the flat supports and \(\accentset{\vee}{\rho}\)-closed sets equivalent (as both are defined as subposets of \((2^\Sigma,\subseteq)\)), so the flat supports must form a Moore family. Hence, the flat supports are closed under intersection. ◻

Proof. Suppose \(\Lambda\) is a strong polymatroid greedoid. Theorems of [1] and Theorem 2 ensure any greedoid with an aligned representation is an optimistic interval greedoid, while the flat supports are a Moore family by definition. The other direction follows by Main Result 3. ◻

Proof. Distributive supermatroids possess the interval property [11], and we are including optimism in our assumptions. Therefore, by Corollary 2 we need only verify that the flat supports of such greedoids are closed under intersection. Let \(F\in\Lambda/\mathord{\sim}\). Then, by the interval property it follows that \(\kappa(F)\) is a union of ideals on some poset. However, the union of ideals is once again an ideal. Now pick another flat \(F'\in\Lambda/\mathord{\sim}\). Because ideals are closed under intersection, it follows that \(\kappa(F)\cap\kappa(F')\) is also an ideal. However, by the distributive law, \[\label{eq:asdfsadfjjj} \kappa(F)\cap\kappa(F') = \left(\bigcup\{\widetilde{\alpha} \mid \alpha \in F\}\right) \cap \left(\bigcup\{\widetilde{\beta}\mid \beta \in F'\}\right) = \bigcup\{\widetilde{\alpha}\cap\widetilde{\beta}\mid (\alpha,\beta)\in F\times F'\}.\tag{29}\] Observe, \((\alpha,\beta)\in F\times F'\) implies \(\widetilde{\alpha}\cap\widetilde{\beta}\) is an ideal which is a subset of a feasible support (either of \(\widetilde{\alpha}\) or \(\widetilde{\beta}\) suffice), and so this intersection can be permuted into a feasible word. Therefore, Eq. 29 implies \(\kappa(F)\cap\kappa(F')\) is a union of feasible supports, i.e. a partial alphabet. This makes, \[\kappa(F)\cap\kappa(F') \subseteq \kappa(\kappa(F)\cap\kappa(F')) = \kappa(F\sqcap F').\] However, because \(\kappa:\mathscr{L}(\Lambda)\to(2^\Sigma,\subseteq)\) is order-preserving, we also have \(\kappa(F \sqcap F') \subseteq \kappa(F)\cap\kappa(F')\). Hence, \(\kappa(F)\cap\kappa(F') = \kappa(F\sqcap F')\). ◻

Proof. Select a basic word \(\alpha \in\Lambda\). To show \(\Lambda\) is optimistic, it is sufficient to prove that for every \(x \in \Sigma\) which is not a loop, there is an \(\alpha\)-prefix \(\alpha'\) with \(x \in \Gamma[\alpha']\). This statement is trivially true for \(x \in \widetilde{\alpha}\), so we examine the case of \(x \notin \widetilde{\alpha}\). Proceed by way of contradiction: Suppose there exists no \(\alpha\)-prefix containing \(x\) in its set of feasible continuations. Then, let \(\alpha = y_1\ldots y_r\) and construct a weighting \(w:\Sigma\to\mathbb{R}\) via, \[w(z) \triangleq \begin{cases} \frac{i}{r(\Lambda)+1} - 1,\quad&\text{if } z = y_i,\\ -r(\Lambda),\quad&\text{if }z = x,\\ 0,\quad&\text{otherwise}. \end{cases}\] We claim that in the \(i^\text{th}\) iteration, the greedy algorithm selects the letter \(y_i\). This is true in the first step because \(\epsilon\) is an \(\alpha\)-prefix, meaning that \(x\notin\Gamma[\epsilon]\) by assumption which leaves \(y_1\) as the letter of least weight which is initially a continuation. The same principle holds for the \(i^\text{th}\) step, as if the greedy algorithm has already formed the word \(y_1\ldots y_{i-1}\) then \(x\) is not a feasible continuation by our assumptions, and \(y_i\) is thus the continuation of least weight. So, it is true that the greedy algorithm forms the word \(\alpha\) under this weighting by the principle of induction. However, because \(x\) is not a loop there exists some basic word \(\beta \in \Lambda\) containing \(x\) in its support. Observe, \[\sum_{z \in \widetilde{\beta}}w(z) \leq w(x) < \sum_{z \in \widetilde{\alpha}} w(z).\] Hence, greedy fails to output the optimal basic word, contradicting strong-exchange. ◻

Proof. Note \(\epsilon \in \Lambda_0\), and \(\Lambda_0\cup \Lambda_A\) is clearly hereditary. So, we need only examine the exchange property. Let \(\alpha,\beta \in \Lambda\) be such that \(|\beta| > |\alpha|\). Observe, the function restriction \(f'|_\Sigma\) is a monotone, normalized, and submodular function, and so \(\Lambda_0\) is a polymatroid greedoid. Hence, exchange holds whenever \(\alpha\) and \(\beta\) are both contained in \(\Lambda_0\). Likewise, by definition of \(\Lambda_A\) there of course exists a letter from \(\widetilde{\beta}\) which can be used to augment \(\alpha\) whenever \((\alpha,\beta) \in \Lambda_A\times \Lambda_A\) or \((\alpha,\beta) \in \Lambda_A\times\Lambda_0\). So, let \(\alpha \in \Lambda_0\setminus\Lambda_A\) and \(\beta \in \Lambda_A\). Suppose \(A\subseteq\sigma_{r_0}\left(\widetilde{\alpha}\right)\). Then \(|A\cap\widetilde{\alpha}| \geq 2\), meaning that \(|A\cap\widetilde{\alpha}| = 2\) by \(\alpha \notin \Lambda_A\). Therefore, there is a letter \(x \in A\cap(\widetilde{\beta}\setminus\widetilde{\alpha})\) which gives the word \(\alpha x\epsilon\in\Lambda_A\). So \(\alpha x \in \Lambda\), and exchange holds in this case. Now examine the case where \(A\not\subseteq\sigma_{r_0}\left(\widetilde{\alpha}\right)\). Recall that the rank closure is the complement of the feasible continuations, hence making \(A\setminus\widetilde{\alpha}\) a subset of the continuations of \(\alpha\) giving longer words in \(\Lambda_0\). Because \(\beta \in \Lambda_A\) implies \(A\subseteq \widetilde{\beta}\) it follows then that there is a letter in \(\widetilde{\beta}\) which can be appended onto \(\alpha\) to obtain a longer word in \(\Lambda_0\). ◻

Proof. Let \(\alpha,\beta,\gamma\) satisfy the conditions of Definition 4. Importantly, \(\widetilde{\alpha},\widetilde{\beta}\subseteq\widetilde{\gamma}\) and \(\gamma \in \Lambda\) implies \(|\widetilde{\alpha}\cup\widetilde{\beta}| \leq 6\). Then, under these conditions, we see that the intersection \(\widetilde{\alpha}\cap\widetilde{\beta}\) and union \(\widetilde{\alpha}\cup\widetilde{\beta}\) can always be permuted into another word in \(\Lambda_A\) when \((\alpha,\beta) \in \Lambda_A\times\Lambda_A\) due to the construction of \(\Lambda_A\). Likewise, the intersection and union can be permuted into a feasible word of \(\Lambda_0\) whenever \((\alpha,\beta)\in\Lambda_0\times\Lambda_0\) since \(\Lambda_0\) is a polymatroid greedoid. Finally, suppose \(\alpha\in\Lambda_0\) while \(\beta \in \Lambda_A\). Notice then that the letters from \(\widetilde{\alpha}\setminus\widetilde{\beta}\) can be appended onto \(\beta\) in any order to obtain a word in \(\Lambda_A\) supported by \(\widetilde{\alpha}\cup\widetilde{\beta}\). Likewise, one can observe \((\widetilde{\alpha}\cap\widetilde{\beta})!\cap\Lambda= \varnothing\) only if \(Y \cap \widetilde{\alpha}\cap\widetilde{\beta} \neq \varnothing\). However, by the construction of \(\Sigma\) and \(\Lambda_0\) the letters in \(Y\) are only feasible continuations (with respect to the greedoid \(\Lambda_0\)) of words \(\alpha' \in \Lambda_0\) such that \(\widetilde{\alpha}'\) either contains one of \(A\), \(B\), or \(C\), or \(|\alpha'| = 5\). If \(|\alpha| = 6\), then it follows from \(\gamma \in \Lambda\) and \(\widetilde{\alpha}\subseteq\widetilde{\gamma}\) that \(\widetilde{\alpha} = \widetilde{\gamma}\). In such a case, \(\widetilde{\alpha}\cap\widetilde{\beta} = \widetilde{\beta}\), which clearly can be permuted into a word in \(\Lambda\). So assume \(|\alpha| < 6\), meaning that \(\widetilde{\alpha}\) contains one of \(A\), \(B\), or \(C\). Because \(\widetilde{\beta}\) contains \(A\), and \(\gamma\) is a word of length at most 6 containing \(\widetilde{\alpha}\cup\widetilde{\beta}\) in its support, we see \(A\subseteq \widetilde{\alpha}\) by pigeonhole principle. Hence \(\alpha \in \Lambda_A\), and we’ve reduced this case to one which we’ve already solved. ◻

Proof. Select a basic word \(\alpha \in \Lambda\) and letter \(x \in\Sigma\), and by way of contradiction assume \(x \notin\Gamma[\alpha]\) for any \(\alpha\)-prefix. The letters of \(A\cup B\cup C\) are continuations of \(\epsilon\), hence making \(x \in Y\). Notice, if \(\widetilde{\alpha}\cap Y \neq \varnothing\) then there is a letter in \(\alpha\) which can be replaced by \(x\) without changing the relative ordering of any other letters (thereby making \(x\) a continuation of the corresponding prefix). So to maintain our assumptions, we see \(\widetilde{\alpha}\cap Y =\varnothing\). Then let \(\alpha'\) be the length 5 prefix of \(\alpha\). For \(\alpha'x \notin \Lambda\) it must be that \(\alpha' \in \Lambda_0\setminus\Lambda_A\), hence we see \(f'(\widetilde{\alpha}') = 5\). Notice that \(Y \cap \widetilde{\alpha}' = \varnothing\) as well, so the number of edges in any spanning tree of the subgraph induced by \(\widetilde{\alpha}'\cup Y\) is at least one greater than that induced by \(\widetilde{\alpha}'\). This makes, \[f'(\widetilde{\alpha}'+ x) - f'(\widetilde{\alpha}') \geq 1,\quad\forall x \in Y.\] But, \(f'(\widetilde{\alpha}'+ x) - f'(\widetilde{\alpha}') \leq 6 - 5 = 1\) by definition of \(f'\), and so \(\left(f'/\widetilde{\alpha}'\right)(x) = 1\) for all \(x \in Y\). As a consequence \(\alpha' x \in \Lambda_0\) for all \(x \in Y\), a contradiction. ◻

Proof. By the preceding claims, \(\Lambda\) is an optimistic local poset greedoid. Towards a contradiction, let \(\rho:2^\Sigma\to\mathbb{R}\) be any (possibly non-integral) aligned polymatroid representation of \(\Lambda\). Observe \(b_1b_2b_3y_1, b_1b_2b_3y_2, b_1b_2b_3y_3 \in \Lambda\) implies, \[\rho(B+ y_1) = \rho(B+y_2) = \rho(B+y_3) =4.\] Notice that the set of continuations for \(b_1b_2b_3y_1\), \(b_1b_2b_3y_2\), and \(b_1b_2b_3y_3\) are the same, hence making \(b_1b_2b_3y_1 \sim b_1b_2b_3y_2 \sim b_1b_2b_3y_3\). This implies \(\rho(B\cup Y) = 4\). The same is true of \(c_1c_2c_3y_1\), \(c_1c_2c_3y_2\), and \(c_1c_2c_3y_3\), hence \(\rho(C\cup Y) = 4\) as well. It can be seen that \(\rho(B\cup C\cup Y) = 6\), since \(b_1b_2b_3c_1c_2c_3 \in \Lambda\) and \(y_1,y_2,y_3 \in \kappa[b_1b_2b_3c_1c_2c_3]\) as \(b_1b_2b_3c_1c_2c_3\) is basic and none of \(y_1\), \(y_2\), or \(y_3\) are loops. Then because submodularity makes, \[\overbrace{\rho(B\cup Y) + \rho(C\cup Y)}^{4+4}\geq \underbrace{\rho(B\cup C\cup Y)}_{6} + \rho(Y),\] it follows that \(\rho(Y) \leq 2\). However, because \(a_1a_2a_3y_1y_2y_3 \in \Lambda\), we see \((\rho/A)(Y) = 3\). In particular, this means that \((\rho/A)(Y) > (\rho/\varnothing)(Y) = 2\), and so \(\rho\) does not satisfy the law of diminishing returns (a contradiction). ◻

Proof. The argument from [1] uses only the fact that the marginal return of any continuation under a feasible word is always one. Specifically, let \(X \subseteq Y \subseteq Z\) be such that \(X!\cap\Lambda\), \(Y!\cap\Lambda\), and \(Z!\cap\Lambda\) are non-empty. Then, take any \(x\notin Z\) satisfying the premise of Eq. 30 . From the law of diminishing returns, \[1 = (\rho/X)(x) \geq (\rho/Y)(x) \geq (\rho/Z)(x) = 1.\] Hence, for all \(\alpha \in Y!\cap\Lambda\) it follows that \((\rho/\widetilde{\alpha})(x) = 1\). Thus \(x \in \Gamma[\alpha]\) by definition of representation, so the intersection on the right hand side of Eq. 30 non-empty since \(\alpha x \in (Y +x)!\cap\Lambda\). ◻

Proof. Induct over \(|X|\). Clearly this is true when \(X=\varnothing\). Now, let \(\alpha \in Y^*\cap\Lambda\) be a maximal length word satisfying \(X\not\subseteq \widetilde{\alpha}\). Then, by the exchange property there exists \(z \in Y\setminus \widetilde{\alpha}\) such that \(\alpha z \in\Lambda\). Observe, because \(\alpha\) is a maximal word satisfying \(X\not\subseteq\widetilde{\alpha}\), we have \(X\subseteq\widetilde{\alpha z}\). This makes all of \(z \in X\),\(X - z \subseteq\widetilde{\alpha}\), and \(X\cup\widetilde{\alpha} = \widetilde{\alpha z}\) true. Because \(\rho\) is a representation, we also have all of \(\rho(X\cup\widetilde{\alpha}) = |\alpha| + 1\), \(\rho(X\cup\widetilde{\alpha}) = |X\cup\widetilde{\alpha}|\), and \(\rho(\widetilde{\alpha}) = |\alpha|\) in particular.

Our construction also makes \(X\cap\widetilde{\alpha} \subset X\), and so \(\rho(X\cap\widetilde{\alpha}) \geq |X\cap\widetilde{\alpha}|\) by inductive hypothesis. Then with submodularity, \[\label{eq:uiuitsi} \rho(X) \geq \rho(X\cap\widetilde{\alpha}) + \rho(X\cup\widetilde{\alpha}) - \rho(\widetilde{\alpha}) \geq |X\cap\widetilde{\alpha}| + |X\cup\widetilde{\alpha}| - |\widetilde{\alpha}| = |X|.\tag{31}\] This shows the first part of the result. Now for the second, first assume \(\rho(X) = |X|\). Because \((\rho/\widetilde{\alpha})(z) = 1\) and \(X-z\subseteq\widetilde{\alpha}\), it follows by the law of diminishing returns that \((\rho/X-z)(z)\geq 1\). Combining this with our inductive hypothesis, \[|X| - 1 \leq \rho(X-z) \leq \rho(X) - 1 = |X| - 1.\] So \(\rho(X-z) = |X| -1\), which makes \((X-z)!\cap\Lambda\neq\varnothing\) by our hypothesis. Therefore, since \((\rho/X-z)(z) = 1\), it follows from the definition of representation that \(X!\cap\Lambda\neq\varnothing\) as well. Now suppose \(X!\cap\Lambda\neq\varnothing\). Then \(\rho(X) = |X|\) by assuming \(\rho\) is a representation. Hence the lemma. ◻

Proof of Proposition [prop:representation-62local-poset]. Let \(\rho:2^\Sigma\to\mathbb{R}\) be any (possibly non-integral or non-aligned) representation, and select \(X\subseteq \Sigma\) and \(y,z\in\Sigma\) with \(X!\cap\Lambda\neq\varnothing\), \((X-y)!\cap\Lambda\neq\varnothing\), and \((X-z)!\cap\Lambda\neq\varnothing\). By Lemma 10 and submodularity this construction makes, \[|X| - 2 \leq \rho(X\setminus\{y,z\}) \leq \rho(X-y) + \rho(X-z) - \rho(X) = |X| - 2.\] But then, \(|X| - 2 = \rho(X\setminus\{y,z\})\), so \((X\setminus\{y,z\})!\cap\Lambda\neq \varnothing\) once again by Lemma 10. ◻

Proof. Firstly, examine \(\Lambda/F\), and select any \(\alpha\in\Lambda/F\), basic \(\beta\in\Lambda/F\), and \(x\notin\widetilde{\beta}\) which is a continuation of \(\alpha\) in \(\Lambda/F\), as in the statement of the strong exchange property. Well, for any \(\gamma\in F\) we have \(\gamma\alpha\) and \(\gamma\beta\) are feasible. Furthermore, we also have \(x\in\Gamma[\gamma \alpha]\). This means \(x\) is not in the support of \(\gamma\), so \(x \notin \widetilde{\gamma\beta}\). Then, there exists \(y\in\widetilde{\gamma\beta}\setminus\widetilde{\gamma\alpha}\) such that \(\gamma \alpha y\in\Lambda\) and \(\widetilde{\gamma\beta} - y + x\) can be permuted into a \(\Lambda\)-feasible word. This makes \(y\) a continuation of \(\alpha\) in \(\Lambda/F\). But also, our construction ensures \(y \notin\gamma\). So, by the exchange property there is some permutation \(\pi \in (\widetilde{\beta} - y + x)!\) such that \(\gamma\pi \in \Lambda\). Hence \(\pi\) is basic in \(\Lambda/F\), and the strong exchange property holds. ◻