2. Algebras of concepts

There are mainly two types of algebras of concepts: Lindenbaum–Tarski algebras of theories, and meaning algebras of models. The later corresponds to concepts that one can define on a given model. These algebras are also known in the literature as cylindric set algebras. Lindenbaum–Tarski algebras can be viewed as algebras of concepts that can be defined in a given theory (that is not necessarily complete). In this section, we are going to recall the definitions of these two types of concrete concept algebras.

The understanding of the term concept depends on where we are. In a Lindenbaum–Tarski algebra, concepts are equivalence classes of formulas modulo the theory, in a meaning algebra, they are the definable relations of the model, and in general, in an arbitrary cylindric algebra, viewed as abstract algebra of concepts, they are just elements of the algebra.

For simplicity, we assume that languages contain only predicates (relation symbols) and fix an enumeration of the variables $\{v_i:i<\omega \}$ .

The meaning of formula $\varphi $ in model $\mathcal {M}$ is the set of infinite sequences from $\mathcal {M}$ satisfying $\varphi $ when the i-th variable $v_i$ is evaluated to the i-th element of the sequence in hand, i.e.,

These meanings form a Boolean algebra with set operations $+$ (union), $\cdot $ (intersection) and $\complement $ (complement) corresponding, respectively, to disjunction, conjunction and negation. The operation $\mathsf {C}_i$ connecting the meanings of formulas $\exists v_i \varphi $ and $\varphi $ is called cylindrification because of its geometrical meaning: it is the smallest cylinder that contains and whose axis is parallel to the i-th coordinate axis of $M^\omega $ . Formally,

The meanings of formulas $v_i=v_j$ for arbitrary $i,j\in \omega $ are called the diagonal elements. Formally,

There are two other important constants in a concept algebra, namely the ones corresponding to the meanings of tautologies and self-contradictions, which can be introduced in meaning algebras, for example, as follows:

The meaning algebra $\mathfrak {Cs}(\mathcal {M})$ of model $\mathcal {M}$ is this natural algebra of meanings of formulas in $\mathcal {M}$ :

where $\mathit {Cs}(\mathcal {M})$ denotes the set of all concepts definable in model $\mathcal {M}$ . In this paper, we are going to use the following notation for the smallest class which is closed under isomorphism and contains all meaning algebras:

Let us now see the other main type of concept algebras. Using the terminology of [Reference Henkin, Monk and Tarski4], by the free algebra of formulas in language $\Lambda $ , we understand the natural algebra given on the set $\mathsf {Fm}_{\Lambda }$ of formulas when the logical connectives considered as operations:

We have that

is a congruence relation on $\mathfrak {Fm}_{\Lambda }$ for every theory T of $\Lambda $ (see, e.g., [Reference Henkin, Monk and Tarski5, theorem 4.3.13, p. 156]). Let T be a theory of language $\Lambda $ . Then the Lindenbaum–Tarski algebra of T in $\Lambda $ is the formula algebra of language $\Lambda $ factorized by relation $\equiv _T$ , i.e.,

Herein, we are going to use the following notation for the class of algebras isomorphic to some Lindenbaum–Tarski algebra:

$$ \begin{align*} \mathsf{LT}=\left\{\mathfrak{A}: \mathfrak{A}\cong\mathfrak{Fm}^{\Lambda}_{T} \text{ for some Lindenbaum--Tarski algebra } \mathfrak{Fm}^{\Lambda}_{T} \right\}\!. \end{align*} $$

There is a strong connection between meaning algebras and Lindenbaum–Tarski algebras. To see this connection, let $\mathsf {Th}(\mathcal {M})$ denote the complete theory of structure $\mathcal {M}$ , i.e., the set of all statements (formulated in the language of $\mathcal {M}$ ) that are true in $\mathcal {M}$ . Let $\Lambda $ be a language and $\mathcal {M}$ be a model for that language, then

(1) $$ \begin{align} \mathfrak{Cs}(\mathcal{M})\cong \mathfrak{Fm}^{\Lambda}_{\mathsf{Th}(\mathcal{M})}. \end{align} $$

To see this, let $[\varphi ]$ denote the equivalence class of $\varphi $ in $\mathfrak {Fm}^{\Lambda }_{\mathsf {Th}(\mathcal {M})}$ and consider map for all $\varphi \in \mathsf {Fm}_{\Lambda }$ . Map f is an isomorphism because of the following equivalences

for all $\varphi ,\psi \in \mathsf {Fm}_{\Lambda }$ .

3. Conceptual distance of theories and generator distance of algebras

In this section, we recall two notions of distance from the literature. One of them is between theories and called conceptual distance. The other one is between algebras of the same similarity type and called generator distance.

For convenience and simplicity, we use the same subscripts and superscripts for theories and their corresponding languages, etc.

Conceptual distance is a natural refinement of definitional equivalence. The basic idea behind definitional equivalence is that introducing new definitions does not change a theory. In this spirit, definitional equivalence can be introduced as the transitive and symmetric closure of definitional extension.Footnote ² There are many equivalent reformulation of this notion (see, e.g., [Reference Lefever and Székely11]). We are going to write $T_1\mathrel {\rightleftarrows } T_2$ for that theories $T_1$ and $T_2$ are definitionally equivalent. From [Reference Khaled, Székely, Lefever and Friend7], we recall that theory $T^+$ is a one-concept-extension of theory T iff

• • the language of $T^+$ is that of T plus one relation symbol, i.e., $\Lambda ^+=\Lambda \cup \{R\}$ for some relation symbol R, and

• • $T^+$ is a conservative extension of T, i.e., $\mathsf {Fm}_{\Lambda }\subseteq \mathsf {Fm}_{\Lambda ^+}$ and $T^+ \models \varphi $ iff $T\models \varphi $ for all $\varphi \in \mathsf {Fm}_{\Lambda }$ .

In this case, we write $T\leadsto T^+$ to denote this relation, and we also say that T is a one-concept-removal of $T^+$ . By $\leftrightsquigarrow $ , we denote the symmetric closure of relation $\leadsto $ .

The conceptual distance $\mathsf {Cd}(T_1,T_2)$ between theories $T_1$ and $T_2$ is defined to be the minimum number of one-concepts-extension and one-concept-removal steps needed to be taken to reach theory $T_2$ from theory $T_1$ . Note that $\mathsf {Cd}(T_1,T_2)=\infty $ is possible. This notion of distance satisfies all the axioms of the metric spaces, up to definitional equivalence and allowing infinite distance:

• • $\mathsf {Cd}(T_1,T_2)\geq 0$ , and $\mathsf {Cd}(T_1,T_2)=0\iff T_1\mathrel {\rightleftarrows } T_2.$

• • $\mathsf {Cd}(T_1,T_2)=\mathsf {Cd}(T_2,T_1)$ .

• • $\mathsf {Cd}(T_1,T_3)\leq \mathsf {Cd}(T_1,T_2)+\mathsf {Cd}(T_2,T_3)$ .

In Section 5, we will see some simple examples such as that the complete theory of the cherry graph (path graph of length two) is of conceptual distance 2 from that of the directed circle graph of length 3. This is clear intuitively because none of those relations can be defined from the other one, but both can be reached from the theory of the three-element set by adding a new relation. For further examples, see [Reference Khaled, Székely, Lefever and Friend7], where among others it is shown that conceptual distance between special relativity and classical kinematics is 1.

To recall the generator distance, we need some definitions. Let $\mathfrak {A}$ and $\mathfrak {B}$ be two algebras of the same similarity type. We say that $\mathfrak {A}$ is a large subalgebra in $\mathfrak {B}$ iff $\mathfrak {A}$ is a subalgebra of $\mathfrak {B}$ , and there is an element $b\in B$ such that $A\cup \{b\}$ generates the whole big algebra $\mathfrak {B}$ . Through out this paper, we use the notation $\langle X\rangle $ for the the subalgebra generated by set X. With this notation $\mathfrak {A}$ is a large subalgebra of $\mathfrak {B}$ iff $\mathfrak {B}=\langle A\cup \{b\}\rangle $ for some $b\in B$ . By large embedding, we mean an injective homomorphism whose range is a large subalgebra, and we denote the fact that $\mathfrak {A}$ is largely embeddable into $\mathfrak {B}$ by .

Let $\mathrm {K}$ be a class of similar algebras. Consider the following possibly infinite network on $\mathrm {K}$ : the nodes are the elements of $\mathrm {K}$ , two nodes are connected by a blue edge if one of them is a large subalgebra of the other, and two nodes are connected by a red edge if they are isomorphic. Then the generator distance $d_{\mathrm {K}}:\mathrm {K}\times \mathrm {K}\rightarrow \mathbb {N}\cup \{\infty \}$ on this network of $\mathrm {K}$ is defined as follows: $d_{\mathrm {K}}(\mathfrak {A},\mathfrak {B})$ is the minimum number of blue edges that we can have in a finite red-blue path connecting $\mathfrak {A}$ and $\mathfrak {B}$ in the network, and $d_{\mathrm {K}}(\mathfrak {A},\mathfrak {B})=\infty $ if there is no finite path between $\mathfrak {A}$ and $\mathfrak {B}$ .

A class $\mathrm {K}$ of similar algebras equipped with the generator distance $d_{\mathrm {K}}:\mathrm {K}\times \mathrm {K}\rightarrow \mathbb {N}\cup \{\infty \}$ satisfies all the axioms of the metric spaces, up to isomorphism and allowing infinite distance, i.e., for all $\mathfrak {A},\mathfrak {B},\mathfrak {C}\in \mathrm {K}$ ,

• • $d_{\mathrm {K}}(\mathfrak {A},\mathfrak {B})\geq 0$ , and $d_{\mathrm {K}}(\mathfrak {A},\mathfrak {B})=0\iff \mathfrak {A}\cong \mathfrak {B}$ ,

• • $d_{\mathrm {K}}(\mathfrak {A},\mathfrak {B})=d_{\mathrm {K}}(\mathfrak {B},\mathfrak {A})$ , and

• • $d_{\mathrm {K}}(\mathfrak {A},\mathfrak {C})\leq d_{\mathrm {K}}(\mathfrak {A},\mathfrak {B})+d_{\mathrm {K}}(\mathfrak {B},\mathfrak {C})$ .

As an illustration for the generator distance, we mention the following example. In the class $\mathrm {K}$ of vector spaces over the same field,

$$ \begin{align*} d_{\mathrm{K}}(V,W)=\begin{cases} 0, & \text{ if } V\cong W, \\ |dim(V)-dim(W)|, & \text{ if }dim(V),dim(W)<\infty,\\ \infty, & \text{ otherwise}. \end{cases} \end{align*} $$

For further details and examples, see [Reference Aslan, Khaled and Székely1, Reference Khaled, Székely, Allahviranloo, Salahshour and Arica6].

4. The conceptual distance between theories is equal to the generator distance of their Lindenbaum–Tarski algebras

In this section, we are going to prove that the conceptual distance between any two theories is equal to the generator distance of their Lindenbaum–Tarski algebras. To do so, in Proposition 4.1, first we show that one-concept-extension implies large embeddibility of the corresponding Lindenbaum–Tarski algebras. The converse is not necessarily true, but in Proposition 4.2, we give a characterization of large embeddibility of Lindenbaum–Tarski algebras in terms of one-concept-extensions between theories.

Proposition 4.1. Let T and $T^+$ be two arbitrary theories on respective languages $\Lambda $ and $\Lambda ^+$ , and let $\mathfrak {Fm}^{\Lambda }_{T}$ and $\mathfrak {Fm}^{\Lambda ^+}_{T^+}$ be their corresponding Lindenbaum–Tarski algebras. Then

Proof. Let $[\varphi ]$ and $[\varphi ]^+$ denote the $\equiv _T$ and $\equiv _{T^+}$ equivalence classes of formula $\varphi $ , respectively.

Since $T\leadsto T^+$ , we have that $\Lambda ^+=\Lambda \cup \{R\}$ for some relation symbol R and $T^+$ is a conservative extension of T. Consider map $f:\mathfrak {Fm}^{\Lambda }_{T}\to \mathfrak {Fm}^{\Lambda ^+}_{T^+}$ that maps $[\varphi ]$ to $[\varphi ]^+$ . To show that f is well-defined, let $\psi \in [\varphi ]$ be another formula representing the equivalence class of $\varphi $ in $\mathfrak {Fm}^{\Lambda }_{T}$ . Then $T\models \varphi \leftrightarrow \psi $ , and from this, because $T^{+}$ is a conservative extension of T, we have $T^+\models \varphi \leftrightarrow \psi $ , i.e., $\psi \in [\varphi ]^+$ . Hence f is well-defined.

From the definitions, it is straightforward to check that f is a homomorphism. As an illustration, we show this in the case of operation $\land $ . To do so, let $[\varphi ]$ and $[\psi ]$ be two arbitrary elements of $\mathfrak {Fm}^{\Lambda }_{T}$ . By definitions, we have $[\varphi \land \psi ]=[\varphi ]\cdot [\psi ]$ and $[\varphi \land \psi ]^+=[\varphi ]^+\cdot [\psi ]^+$ . Therefore,

$$ \begin{align*} f\left([\varphi]\cdot[\psi]\right)=f\left([\varphi\land\psi]\right)=[\varphi\land\psi]^+=[\varphi]^+\cdot[\psi]^+=f\left([\varphi]\right)\cdot f\left([\psi]\right)\!. \end{align*} $$

So f preserves operation $\cdot $ . Showing that f preserves the other operations is completely analogous.

To show that f is one-to-one, let $\varphi ,\psi \in \mathsf {Fm}_{\Lambda }$ such that $[\varphi ]^+=[\psi ]^+$ , i.e., $T^+\models \varphi \leftrightarrow \psi $ . Since $T^{+}$ is a conservative extension of T and $\varphi ,\psi \in \mathsf {Fm}_{\Lambda }$ , we have $T\models \varphi \leftrightarrow \psi $ , and hence $[\varphi ]=[\psi ]$ . Consequently, f is an embedding of $\mathfrak {Fm}^{\Lambda }_{T}$ to $\mathfrak {Fm}^{\Lambda ^+}_{T^+}$ .

To show that f is a large embedding, it is enough prove that the f-image of $\mathfrak {Fm}^{\Lambda }_{T}$ plus the element $[R]^+\in \mathfrak {Fm}^{\Lambda ^+}_{T^+}$ generates the whole Lindenbaum–Tarski algebra $\mathfrak {Fm}^{\Lambda ^+}_{T^+}$ . This is so because the formula algebra $\mathfrak {Fm}^{\Lambda ^+}_{T^+}$ is generated by formulas $\mathsf {Fm}_{\Lambda }$ and formula R since $\Lambda ^+=\Lambda \cup \{R\}$ . This completes the proof.

The converse of Proposition 4.1 is not necessarily true because it is possible that holds but there are more than one relation symbols in $\Lambda ^+\setminus \Lambda $ . Nevertheless, even in such cases, it is possible to replace the language $\Lambda ^+$ to another language $\Lambda ^+_*$ and find a theory $T^+_*$ in this language such that $T\leadsto T^+_*$ and $\mathfrak {Fm}^{\Lambda ^+_*}_{T^+_*}\cong \mathfrak {Fm}^{\Lambda ^+}_{T^+}$ :

Proposition 4.2. Let T and $T^+$ be two arbitrary theories on respective languages $\Lambda $ and $\Lambda ^+$ ; and let $\mathfrak {Fm}^{\Lambda }_{T}$ and $\mathfrak {Fm}^{\Lambda ^+}_{T^+}$ be their corresponding Lindenbaum–Tarski algebras. Then

In the proof of Proposition 4.2, we need to introduce some terminology. The so-called dimension set of x is defined as $\Delta x:= \left \{i\in \omega : \mathsf {C}_{i} x \neq x\right \}$ . We denote the rank function that associate their arity with predicates (relation symbols) by $\rho $ . A key step in the proof is based on the following fact of algebraic logic (see [Reference Henkin, Monk and Tarski5, theorem 4.3.15, p. 156, theorem 4.3.17, p. 156 and theorem 4.3.28, p. 161] and [Reference Henkin, Monk and Tarski4, p. 349]):

1. (CA1) Let $\Lambda $ be an arbitrary language, then $\mathfrak {Fm}^{\Lambda }_{\emptyset }$ is a dimension-restricted free algebra. That is, for any $\mathfrak {A}\in \mathsf {LT}$ , that is generated by $\langle x_R: R\in \Lambda \rangle $ such that $\Delta {x_R}\subseteq \rho {R}$ , there is a (unique) homomorphism $h:\mathfrak {Fm}^{\Lambda }_{\emptyset }\to \mathfrak {A}$ satisfying $h(R)=x_R$ for all $R\in \Lambda $ .

Note that, for the sake of notational simplicity, R is also used as an abbreviation for atomic formula $R(v_0,\ldots ,v_{\rho {R}-1})$ and not just for relation symbol $R\in \Lambda $ .

Proof. Direction $\Longleftarrow $ follows immediately from Proposition 4.1. To show the converse direction, as before, let $[\varphi ]$ , $[\varphi ]^+$ and $[\varphi ]^+_*$ denote the $\equiv _T$ , $\equiv _{T^+}$ and $\equiv _{T^+_*}$ equivalence classes of formula $\varphi $ .

Since , there is an embedding $e:\mathfrak {Fm}^{\Lambda }_{T} \to \mathfrak {Fm}^{\Lambda ^+}_{T^+}$ and element $b\in \mathfrak {Fm}^{\Lambda ^+}_{T^+}$ such that $ \mathfrak {Fm}^{\Lambda ^+}_{T^+}=\left \langle \text {Im}(e)\cup \{b\}\right \rangle $ , where $\text {Im}(e)$ denotes the image $\left \{e(x): x\in \mathfrak {Fm}^{\Lambda }_{T}\right \}$ of e. Let $\Lambda ^+_*:=\Lambda \cup \{R_b\}$ for some relation symbol $R_b\not \in \Lambda $ and let $\rho ^+_*$ be an extension of $\rho $ such that

$$ \begin{align*} \rho^+_*(R_b):=\bigcap\left\{\beta<\omega: \Delta b \subseteq \beta\right\}\!. \end{align*} $$

By its definition, we have that $\rho ^+_*(R_b)$ is finite, and hence $\Lambda ^+_*$ is a first-order language.

Since e is a large embedding, $\mathfrak {Fm}^{\Lambda ^+}_{T^+}$ can be generated by $R_b$ all the relations in $\Lambda $ . Hence, by (CA1), there is a homomorphism h from $\mathfrak {Fm}^{\Lambda ^+_*}_{\emptyset }$ to $\mathfrak {Fm}^{\Lambda ^+}_{T^+}$ such that $h\big (R_b\big )=b$ and $h\big (R\big )=[R]^+$ for all $R\in \Lambda $ .Footnote ³ Let

$$ \begin{align*} T^+_*:=\left\{\varphi\in\mathsf{Fm}_{\Lambda^+_*}:h(\varphi)=1\right\}\!. \end{align*} $$

Let us define $g:\mathfrak {Fm}^{\Lambda ^+_*}_{T^+_*}\to \mathfrak {Fm}^{\Lambda ^+}_{T^+}$ as $g:[\varphi ]^+_*\mapsto h(\varphi )$ (see Figure 1).

Fig. 1 The diagram illustrates the connection of algebras used in the proof of Proposition 4.2.

It is straightforward to check that g is an isomorphism, and hence $\mathfrak {Fm}^{\Lambda ^+}_{T^+}\cong \mathfrak {Fm}^{\Lambda ^+_*}_{T^+_*}$ : it is easy to check that g is a homomorphism; g is one-to-one because $g([\varphi ]^+_*)=g([\psi ]^+_*)$ iff $h(\varphi )=h(\psi )$ iff $h(\varphi \leftrightarrow \psi )=1$ iff $\varphi \leftrightarrow \psi \in T^+_*$ , which implies $[\varphi ]^+_*=[\psi ]^+_*$ ; g is surjective because h is so.

To show that $T\subseteq T^+_*$ , let $\varphi \in \mathsf {Fm}_{\Lambda }\subset \mathsf {Fm}_{\Lambda ^+_*}$ . If $\varphi \in T$ , we have $[\varphi ]=1$ . Hence, $[\varphi ]^+=e([\varphi ])=1$ , and thus $h(\varphi )=1$ because $[\varphi ]^+=h(\varphi )$ as $[R]^+=h\big (R\big )$ for all $R\in \Lambda $ . Consequently, $\varphi \in T^+_*$ .

Theory $T^+_*$ is a conservative extension of T because, for all $\varphi \in \mathsf {Fm}_{\Lambda }$ , we have

$$ \begin{align*} T^+_*\models \varphi \iff \varphi\in T^+_* \iff h(\varphi)=1 \iff [\varphi]^+=e([\varphi])=1 \iff T\models \varphi. \end{align*} $$

Consequently, $T\leadsto T^+_*$ because $\Lambda ^+_*=\Lambda \cup \{R_b\}$ .

Now we show that conceptual distance can be reduced to generator distance between certain algebras of logic. By Theorem 4.3 below, the conceptual distance between theories is the same as the generator distance between their Lindenbaum–Tarski algebras in the class $\mathsf {LT}$ .

Theorem 4.3. Let $T_{1}$ and $T_{2}$ be two arbitrary theories and let $\mathfrak {Fm}^{\Lambda _1}_{T_1}$ and $\mathfrak {Fm}^{\Lambda _1}_{T_1}$ be their Lindenbaum–Tarski algebras. Then

$$ \begin{align*} \mathsf{Cd}\big(T_1,T_2\big) = d_{\mathsf{LT}}\left(\mathfrak{Fm}^{\Lambda_1}_{T_1},\mathfrak{Fm}^{\Lambda_2}_{T_2}\right)\!. \end{align*} $$

In the proof of Theorem 4.3, we are going to use the following fact of algebraic logic (see [Reference Henkin, Monk and Tarski5, theorems 4.3.15, 4.3.28(ii) and 4.3.43]):

1. (CA2)

   1. ○ For any two theories $T_1$ and $T_2$ , $T_1\mathrel {\rightleftarrows } T_2$ iff $\mathfrak {Fm}^{\Lambda _1}_{T_1}\cong \mathfrak {Fm}^{\Lambda _2}_{T_2}$ .

   2. ○ For all $\mathfrak {A},\mathfrak {B}\in \mathsf {LT}$ , we have that $\mathfrak {A}\cong \mathfrak {B}$ iff there are definitionally equivalent theories $T_1$ and $T_2$ of respective languages $\Lambda _1$ and $\Lambda _2$ such that $\mathfrak {A}\cong \mathfrak {Fm}^{\Lambda _1}_{T_1}$ and $\mathfrak {B}\cong \mathfrak {Fm}^{\Lambda _2}_{T_2}$ .

The following is a corollary of Theorem 4.3 and (1) on page 3:

Corollary 4.4. Let $\mathcal {M}_1$ and $\mathcal {M}_2$ be two arbitrary mathematical structures. Then

$$ \begin{align*} \mathsf{Cd}\big(\mathsf{Th}(\mathcal{M}_1),\mathsf{Th}(\mathcal{M}_2)\big) = d_{\mathsf{LT}}\big(\mathfrak{Cs}(\mathcal{M}_1),\mathfrak{Cs}(\mathcal{M}_2)\big). \end{align*} $$

In case of complete theories, one may wonder if it is possible to find a minimal path representing their conceptual distance that goes through complete theories only. To answer this natural question positively in Corollary 4.5, let us see some consequences of the things above. By Proposition 4.2, (CA2) and (1), we have

(2)

for all models $\mathcal {M}$ and $\mathcal {M}^+$ . By (1) and (CA2), we have

(3) $$ \begin{align} \mathfrak{Cs}(\mathcal{M}_1) \cong \mathfrak{Cs}(\mathcal{M}_2)\ \iff\ \mathsf{Th}(\mathcal{M}_1) \mathrel{\rightleftarrows} \mathsf{Th}(\mathcal{M}_2) \end{align} $$

for all $\mathcal {M}_1$ and $\mathcal {M}_2$ . From (2) and (3), it follows straightforwardly that, for all $\mathcal {M}_1$ and $\mathcal {M}_2$ ,

$$ \begin{align*} d_{\mathsf{MA}}\big(\mathfrak{Cs}(\mathcal{M}_1),\mathfrak{Cs}(\mathcal{M}_2)\big)=\mathsf{Cd}\big(\mathsf{Th}(\mathcal{M}_1),\mathsf{Th}(\mathcal{M}_2)\big). \end{align*} $$

From this, by Theorem 4.3 and (1), we get the following:

Corollary 4.5. Let $\mathcal {M}_1$ and $\mathcal {M}_2$ be two arbitrary mathematical structures. Then

$$ \begin{align*} d_{\mathsf{LT}}\big(\mathfrak{Cs}(\mathcal{M}_1),\mathfrak{Cs}(\mathcal{M}_2)\big) = d_{\mathsf{MA}}\big(\mathfrak{Cs}(\mathcal{M}_1),\mathfrak{Cs}(\mathcal{M}_2)\big); \end{align*} $$

in other words, it does not matter if one calculates the distance of $\mathfrak {Cs}(\mathcal {M}_1)$ and $\mathfrak {Cs}(\mathcal {M}_2)$ in the class $\mathsf {LT}$ of all Lindenbaum–Tarski algebras or in the class $\mathsf {MA}$ of all meaning algebras.

So, by Corollary 4.5, if there is a minimal path

$$ \begin{align*} \mathsf{Th}(\mathcal{M}_1) \leftrightsquigarrow T_1 \leftrightsquigarrow T_2 \leftrightsquigarrow\cdots \leftrightsquigarrow T_n \leftrightsquigarrow \mathsf{Th}(\mathcal{M}_2) \end{align*} $$

representing the distance $\mathsf {Cd}\big (\mathsf {Th}(\mathcal {M}_1),\mathsf {Th}(\mathcal {M}_2)\big )$ with some not necessarily complete theories $T_1$ , $T_2$ , …, $T_n$ , then there are models $\mathcal {N}_1$ , $\mathcal {N}_2$ , …, $\mathcal {N}_n$ such that

$$ \begin{align*} \mathsf{Th}(\mathcal{M}_1) \leftrightsquigarrow Th(\mathcal{N}_1) \leftrightsquigarrow Th(\mathcal{N}_2) \leftrightsquigarrow\cdots \leftrightsquigarrow Th(\mathcal{N}_n) \leftrightsquigarrow \mathsf{Th}(\mathcal{M}_2). \end{align*} $$

5. Examples and applications

In this section, we give some illustrative examples and applications of the previous results. We are going to call two models conceptually equivalent iff their theories are definitionally equivalent.Footnote ⁴

For every nonzero cardinality $\kappa $ , let $\mathfrak {M}in_\kappa $ denote the minimal algebra of concepts definable in a set of cardinality $\kappa $ only by equality. For different countable cardinalities, these algebras are mutually non-isomorphic, and each meaning algebra contains a unique isomorphic copy of $\mathfrak {M}in_\kappa $ for some $\kappa \le \omega $ as a minimal subalgebra. If ${\kappa \ge \omega} $ , then $\mathfrak {M}in_\kappa \cong \mathfrak {M}in_\omega $ . Let $\mathfrak {F}ull_\kappa $ denote the full algebra of concepts containing all relations having finite arity over a nonempty set of cardinality $\kappa $ . These algebras are mutually non-isomorphic for all different cardinalities, and each meaning algebra can be embedded to one of them. For all nonzero finite n, we have since $\mathfrak {F}ull_n\cong \mathfrak {Cs}(\langle n,\le \rangle )$ as every element of n can be defined from $\le $ and this is enough to define every finitary relation over n. Note that $\mathfrak {F}ull_\omega \ncong \mathfrak {Cs}(\langle \omega ,\le \rangle )$ .

We say that concept x is an ${n}$ -ary concept if $\mathsf {C}_ix=x$ for all $i\ge n$ . Such concepts are essentially the definable relations of arity n. Note that n-ary concepts are also $(n+1)$ -ary ones, and thus $0$ and $1$ are n-ary concepts for all natural number n. Hence, we are going to call these two trivial n-ary concepts.

Let $|M|=n$ for some natural number $n\ge 1$ and let be an m-ary concept of $\mathcal {M}$ for some $m\ge n+1$ . Equation $\sum _{i<j\le n}{\mathsf {D}}_{ij}=1$ holds in $\mathfrak {Cs}(\mathcal {M})$ because it is not possible to take more than n distinct elements of $\mathcal {M}$ . From this, it follows that

(4)

So can be reconstructed from the concepts , which are $(m-1)$ -ary ones up to substitution of variables.Footnote ⁵ Repeating this construction enough times, one can reconstruct any relation from (at most) n-ary ones. Hence,

(5) $$ \begin{align} \text{If }|M|=n, \text{ every concept of }\mathfrak{Cs}(\mathcal{M})\text{ can be generated by (at most)}\ n\text{-ary ones.} \end{align} $$

Actually, statement (5) can be strengthened: it is enough to consider (at most) $(n-1)$ -ary relations. For a precise proof of this claim, see Lemma 6.2 herein.

(6) $$ \begin{align} \text{If }|M|=n,\text{ every concept of }\mathfrak{Cs}(\mathcal{M}) \text{ can be generated by (at most) }(n-1)\text{-ary ones}. \end{align} $$

Now we will list the meaning algebras of all finite models of size at most 3, up to isomorphism. Note that by (6), it is enough to search for meaning algebras of models whose relation symbols are of arity at most $n-1$ , where $n = |M|$ . Let $\mathcal {M}$ be an arbitrary model such that $|M|\le 3$ .

Suppose that $|M|=1$ . The are only two 1-ary concepts that can be defined on a one-element set: the empty concept, and its complement. Each of these relations is defined by equality. Thus

$$ \begin{align*}\mathfrak{Cs}(\mathcal{M})\cong\mathfrak{M}in_1\cong \mathfrak{F}ull_1.\end{align*} $$

Suppose that $|M | = 2$ . Note that $\mathfrak {M}in_2\not \cong \mathfrak {F}ull_2$ , but still we have

$$ \begin{align*}\mathfrak{Cs}(\mathcal{M})\cong\mathfrak{M}in_2 \text{ or } \mathfrak{Cs}(\mathcal{M})\cong \mathfrak{F}ull_2.\end{align*} $$

This is so because a 1-ary relation on $\mathcal {M}$ is either $\emptyset $ , $\mathcal {M}$ itself or a one-element subset of $\mathcal {M}$ .

Suppose that $|M| = 3$ . There are exactly four meaning algebras up to isomorphism:

where is the meaning algebra of the directed cycle graph of length 3, and is the meaning algebra of the cherry graph (i.e., path graph of length two). In other words, up to conceptual equivalence there are only four structures that one can give on a three-element set. Let us see why this is so. By (6), it is enough to consider structures given by binary relations. If none of the three elements is distinguishable, i.e., any one of them can be mapped to any other one by an automorphism, then these binary relations can only be the unions of the following ones: the one giving a directed cycle, its converse or the equality. These cases give exactly and $\mathfrak {M}in_3$ up to conceptual equivalence. If exactly two of the three elements are indistinguishable but the third is not, then we get . Finally, if all the three elements are distinguishable, then we get $\mathfrak {F}ull_3$ . Let us also note that is the only one of these four algebras that cannot be generated by unary relations.

Clearly, we have and as and are both given by only one relation. Neither nor can be largely embedded to the other. cannot be embedded to because there are two nontrivial unary concepts in and there are no such unary concepts in at all. cannot be embedded to because the concept has to be mapped to a nontrivial binary concept under $-{\mathsf {D}}_{01}$ in . Every such concept is the union of the following three , and . It is straightforward to check that any of these nontrivial binary concepts generate the whole algebra , and hence it cannot be the image of .

Fig. 2 The figure shows a complete description for the large embedding network of meaning algebras if $|M|\le 3$ .

Based on the observations above, we can give a complete description for the large embedding network of meaning algebras if $|M|\le 3$ (see Figure 2). In this small network, the distances are either $0$ , $1$ , $2$ or $\infty $ . We are going to show that only these four distances appear even in the network of all meaning algebras (cf. also Theorem 5.1 below).

By the size of a model $\mathcal {M}$ , we mean its cardinality if it is finite and $\infty $ otherwise, i.e.,

$$ \begin{align*} \mathsf{size}(\mathcal{M})=\begin{cases} |M|, & \text{ if } |M|<\infty, \\ \infty, & \text{ otherwise}. \end{cases} \end{align*} $$

Let us first note that if two models $\mathcal {M}_1$ and $\mathcal {M}_2$ have different sizes, then their minimal subalgebras are non-isomorphic, and hence we have that

(7) $$ \begin{align} \mathsf{size}(\mathcal{M}_1)\neq \mathsf{size}(\mathcal{M}_2) \implies d_{\mathsf{LT}}(\mathfrak{Cs}(\mathcal{M}_1),\mathfrak{Cs}(\mathcal{M}_2))=\infty. \end{align} $$

Now, borrowing some ideas from the proof of [Reference Henkin, Monk and Tarski4, theorem 2.3.22], which shows that certain finitely generated algebras can be generated by a single element, we show that

(8)

By induction, it is enough to show that (8) holds for $n=3$ . If $\mathfrak {Cs}(\mathcal {M}_1)\cong \mathfrak {M}in_1$ , then $|M_1|=1$ , and hence $|M_2|=|M_3|=1$ and $\mathfrak {Cs}(\mathcal {M}_2)\cong \mathfrak {Cs}(\mathcal {M}_3)\cong \mathfrak {M}in_1$ , and thus holds trivially. Otherwise, we have $|M_1|=|M_2|=|M_3|\ge 2$ . Let $\rho $ and $\sigma $ be the formulas representing the concepts that we have added to $\mathfrak {Cs}(\mathcal {M}_1)$ and $\mathfrak {Cs}(\mathcal {M}_2)$ to reach $\mathfrak {Cs}(\mathcal {M}_3)$ , and let for some variables $v_i$ and $v_j$ none of which is free in $\rho $ and $\sigma $ . Then because $|M_3|\ge 2$ , we have and . This means that instead of the two concepts represented by $\rho $ and $\sigma $ we could have added the one represented by $\tau $ to reach $\mathfrak {Cs}(\mathcal {M}_3)$ from $\mathfrak {Cs}(\mathcal {M}_1)$ , and this completes the proof of (8).

By [Reference Aslan, Khaled and Székely1, proposition 2.12] and the fact that the class of $\mathsf {LT}$ has the amalgamation property (see, e.g., [Reference Madárasz and Sayed-Ahmed12, table 1] or [Reference Kiss, Márki, Pröhle and Tholen8]), we have that there is any path between two algebras $\mathfrak {A},\mathfrak {B}\in \mathsf {LT}$ , then there is an algebra $\mathfrak {D}\in \mathsf {LT}$ such that $\mathfrak {D}$ is reachable from both $\mathfrak {A}$ and $\mathfrak {B}$ by finitely many large embedding steps. Since up to isomorphism every algebra in $\mathsf {LT}$ is a meaning algebra, we get from this that, for any two models $\mathcal {M}_1$ and $\mathcal {M}_2$ ,

(9) $$ \begin{align} d_{\mathsf{LT}}(\mathfrak{Cs}(\mathcal{M}_1),\mathfrak{Cs}(\mathcal{M}_2))\le 2\quad \text{ if }\quad d_{\mathsf{LT}}(\mathfrak{Cs}(\mathcal{M}_1),\mathfrak{Cs}(\mathcal{M}_2))<\infty. \end{align} $$

From the above, it also follows that, if the languages of $\mathcal {M}_1$ and $\mathcal {M}_2$ are finite and $\mathsf {size}(\mathcal {M}_1)=\mathsf {size}(\mathcal {M}_2)$ , then $d_{\mathsf {LT}}(\mathfrak {Cs}(\mathcal {M}_1),\mathfrak {Cs}(\mathcal {M}_2))\le 2$ . This is so because, in this case, $\mathfrak {Cs}(\mathcal {M}_1)$ and $\mathfrak {Cs}(\mathcal {M}_2)$ have isomorphic minimal subalgebras from which they can be reached in one large embedding step by (8).

So if $\mathsf {size}(\mathcal {M}_1),\mathsf {size}(\mathcal {M}_2)< \infty $ , then by (6), we have two cases:

• either $\mathsf {size}(\mathcal {M}_1)=\mathsf {size}(\mathcal {M}_2)$ , and then $d_{\mathsf {LT}}(\mathfrak {Cs}(\mathcal {M}_1),\mathfrak {Cs}(\mathcal {M}_2))\le 2$ ;

• or $\mathsf {size}(\mathcal {M}_1)\neq \mathsf {size}(\mathcal {M}_2)$ , and then $d_{\mathsf {LT}}(\mathfrak {Cs}(\mathcal {M}_1),\mathfrak {Cs}(\mathcal {M}_2))=\infty $ by (7).

Consequently, determining the distance of meaning algebras corresponding to finite models boils down to three questions: Do they have the same size? If yes, are they definitionally equivalent? If not, can one of them largely embedded to the other?

What can we say in the case $\mathsf {size}(\mathcal {M}_1)=\mathsf {size}(\mathcal {M}_2)=\infty $ ?

Assume that $\mathsf {size}(\mathcal {M})=\infty $ , the language of $\mathcal {M}$ is countable and there is some natural number n such that $\rho (R)\le n$ for every relation symbol R in the language of $\mathcal {M}$ . Without loosing generality, we can assume that $\{R_i:i<\omega \}$ is a listing of these relation symbols and $\rho (R_i)=n$ for all natural number i. Now let us try encode the whole language of $\mathcal {M}$ with one extra relation symbol. By (8), it is enough if we can encode it with finitely many relations because adding finitely many extra relations can be replaced by adding only one extra relation if $|M|\ge 2$ . Let $<$ be an ordering on a countable infinite subset of M isomorphic to the ordering of natural numbers, there is such ordering because $\mathsf {size}(\mathcal {M})=\infty $ . From this ordering, all natural numbers $0$ , $1$ , $2$ , etc. are definable individually as unary relations $0(x)$ , $1(x)$ , $2(x)$ , etc. Now let S be an $(n+1)$ -ary relation such that $\mathcal {M}\models S(\bar x,y)\leftrightarrow R_i(\bar x)\land i(y)$ holds for every natural number i. From $<$ and S, each $R_i$ can be defined back because $\mathcal {M}\models R_i(\bar x)\leftrightarrow \exists y (S(\bar x,y)\land i(y))$ . Consequently, there is a structure $\mathcal {M}^+$ whose language contains only one relation symbol, but all the countably infinite relations of $\mathcal {M}$ can be defined from that relation. In algebraic terms, this means that $\mathfrak {Cs}(\mathcal {M})$ can be largely embedded to a one-element generated meaning algebra.

From the above, it follows that, if language of models $\mathcal {M}_1$ and $\mathcal {M}_2$ are countable such that there is a finite bound for the rank of the relation symbols of these languages and $\mathsf {size}(\mathcal {M}_1)=\mathsf {size}(\mathcal {M}_2)$ , then $d_{\mathsf {LT}}(\mathfrak {Cs}(\mathcal {M}_1),\mathfrak {Cs}(\mathcal {M}_2))\le 2$ .

By Corollary 4.4, the above considerations can be summarized in terms of conceptual distance as follows.

Theorem 5.1. Let $\mathcal {M}_1$ and $\mathcal {M}_2$ be models of arbitrary languages. Then

(10) $$ \begin{align} \mathsf{Cd}(\mathsf{Th}(\mathcal{M}_1),\mathsf{Th}(\mathcal{M}_2))\le 2 \text{ or } \mathsf{Cd}(\mathsf{Th}(\mathcal{M}_1),\mathsf{Th}(\mathcal{M}_2))=\infty \end{align} $$

and

(11) $$ \begin{align} \mathsf{size}(\mathcal{M}_1)\neq \mathsf{size}(\mathcal{M}_2) \implies \mathsf{Cd}(\mathsf{Th}(\mathcal{M}_1),\mathsf{Th}(\mathcal{M}_2))=\infty. \end{align} $$

If the languages of $\mathcal {M}_1$ and $\mathcal {M}_2$ are countable and there is some natural number n such that if the rank $\rho (R)\le n$ for every relation R in the two languages, then

(12) $$ \begin{align} \mathsf{size}(\mathcal{M}_1)= \mathsf{size}(\mathcal{M}_2) \implies \mathsf{Cd}(\mathsf{Th}(\mathcal{M}_1),\mathsf{Th}(\mathcal{M}_2))\le 2. \end{align} $$

Now we are going to show that the arity-bound condition of (12) in Theorem 5.1 cannot be omitted:

Proposition 5.2. There is a model $\mathcal {M}$ on a countable language such that

$$ \begin{align*} \mathsf{size}(\mathcal{M})=\infty \text{ and } d_{\mathsf{LT}}(\mathfrak{M}in_\omega,\mathfrak{Cs}(\mathcal{M}))=\infty. \end{align*} $$