Information content in formal languages

Variables are the center and core of mathematics, physics, theoretical technics and theoretical economy theory. In this paper we consider formal languages with variables (see definition 2.1), provided with a length function for sentences (for example a simple character count), and define something which appears like a pseudo-metric between the sentences within one languages (see definition 2.12).

The languages are assumed to be equipped with an equivalence relation (def. 2.6), and the more two sentences $x,y$ have in common, the closer their distance becomes.

Actually, this project was motivated by physics in the quest for a solution to quantum gravity, see for instance Weinberg [21] and Hawking and Israel [11]. It is observed, that in general physical theories are surprisingly short when formulated as equations, and that progress in advancing the correct equations in physics is often realized by small modifications in formulas. For example, the formulas between Hamiltonian mechanics and quantum mechanics are very close in distance, also in our approach here, for all given Hamiltonians, even if quantum mechanics and mechanics appear very different when considered without formulas (cf. example 11.1).

We guess that a solution that unites gravity and quantum field theory, when formulated as mathematical equations, is actually close as formulas, for example in the sense proposed in this paper, to the existing ununited theories of gravity and quantum field theory. This might lead to the direction towards a candidate for a united theory, and on the other hand, might be used as a tool to evaluate a given candidate theory by computing the distance to the existing theory so far.

In short terms, the simpler a theory is, the better. The closer it is to existing effective theories, the better, as the more likely it is the correct generalization.

In this sense, even quantum mechanics might very theoretically have had been predicted without any inspection of black body radiation or double slit experiment, because it is perhaps the closest theory to mechanics which avoids the infinities. Simply by looking at formulas.

In this sense also, a solution to quantum gravity is perhaps less a physical problem but more a pure mathematical problem. It may be formulated like so: indicate the theory with the shortest distance - in the sense of this paper, say - to the existing theory, such that no infinities occur (cf. problem 11.3). Even more so, as ultrahigh-energy experiments appear currently to be impossible by several reasons, for example the no-return from black holes obstacle.

After this motivating and ambitious remarks, which may also appear somewhat self-evident, let us come to the hard facts of this paper:

Our definitions may be used much more widely, for example in computing, and it is widely applicable, as the approach is very flexible and does not bother with details but with the core principle. World applications are viewed as formulas. Actually, the distance $d(s,t)$ between two formulas $s,t$ is defined as

which means in words: unite both theories $s$ and $t$ (called $s\nabla t$), optimize their length (called $\ell$) and compute it (the more overlap they have the shorter it will become) and then subtract the length of the shorter theory of $s$ and $t$.

It looks natural and simple, but is also intriguing because of the minus sign. Even if it appears natural that the triangle inequality - also called $\Delta$-inequality in this paper - holds for $d$ (cf. lemma 3.6), it is difficult and enormous involving when trying to verify this. A key of this paper is to repair the definition of $d$ by making the $\Delta$-inequality valid, see definition 7.1. See also theorem 6.10 for other conditions which imply the $\Delta$-inequality.

As another example, it is difficult to get any easy criteria for the uniform continuity of a homomorphism between two languages, for example computer languages, but see lemma 12.1.

To not get lost in details or become too specific, in this paper we mainly forget languages at all but instead work with an abelian, idempotent monoid $(S,\nabla)$ provided with a length function $\ell$ (see definition 2.15).

This setting can be somewhat compared with a measured space $(M,\cup)$ with the operation $\cup$ of taking the union of sets and a measure $\ell$ on it. And indeed, we will make parallels, and show how we can compute the “signed measure” $\zeta$ (i.e. length) of a formal Boolean expression in the monoid $S$, see definition 6.15. The above formula for $d$ is easily seen to be indeed a metric for measured spaces $(M,\cup)$ and $\nabla:=\cup$, see lemma 3.3.

In a main result, see theorem 7.21, we show how one can, starting with a length function $\ell$, construct a length function ${{\ell}^{(\infty)}}$ such that the above formula for $d$ with $\ell$ replaced by ${{\ell}^{(\infty)}}$ is indeed a pseudometric, and the measure $\zeta(x\cap y)$ of the Boolean expression of intersection of two sentences $x$ and $y$, is monotonically increasing in $x$ and $y$, as one may naturally expect it. We have however no clue in how far ${{\ell}^{(\infty)}}$ degenerates, it could even be completely zero (but don’t believe that).

A key role in this paper also plays the $\nabla$-inequality

which, even if it holds heuristically, see lemma 4.2, we also force by definition finally, see definition 7.4.

For homomorphisms between languages we use the same concepts as for languages itself to define a metric, enriched by the submultiplicativity (cf. lemma 8.14).

As a distance between languages, or more generally, abelian, idempotent monoids, one may use the proposed Banach-Mazur-like distance of definition 8.27.

In the final sections we give various examples which should illustrate and motivate the theory of this paper, presented in an extremely superficially and sloppy way.

Actually, defining pseudometrics on languages, and on a family of languages goes back for a long time with a wide literature, and we only cite samples, far from being in any way complete, Han and Ko [10], Djordjević, Ikodinović and Stojanović [6], Fulop and Kephart [8], Ko, Han and Salomaa [15], Imaoka [13], Cseresnyes and Seiwert [2], Ibarra, McQuillan and Ravikumar [12], Bertoni, Goldwurm and Sabadini [1], Stratford [20], Jalobeanu [14], Parker, K.B. Yancey and M.P. Yancey [16], Cui, Dang, Fischer and Ibarra [3], Pighizzini [17], and in the context of physical theories, Giangiacomo [9]. We will not compare these approaches with the one in this paper, but we think there is a different emphasis on the latter.

Let us remark, that we less stress the exact computability of the proposed metrics, but the idealized relations they should satisfy. Also, our definitions are designed such that we find them particularly useful for physical theories.

Under a language $(S,A)$ we mean a set $A$ called alphabet, and a set $S\subseteq\{f:\{1,\ldots,n\}\rightarrow A|\,n\geq 1\}\cup\{\emptyset\}$ of finite text-strings with letters in $A$ called sentences or formulas or theories. Here, $\emptyset$ means the empty sentence (i.e. empty set). In this section we are going to give successively several definitions, each of which becomes part of the considered setting after the definition.

Here, $s{\vee}t$ means the concatenated string of the string $s$ with the letter ${\vee}$ with the string $t$ in the order as indicated. The letter ${\vee}$ serves purely as a symbol for concanation of strings.

In other words, the empty word has no length, the length of two concanated strings is the sum of of the length of the single strings, and the length or cost of a string does not change if we just choose other variable names.

Two sentences are completely unrelated if they have no variables in common because they do not speak about the same variables:

In languages like mathematical of physical theories, one can typically express formulas in formally different ways but which are equivalent in content (for example, formally different equations may have the same solution). That is why we need an equivalence relation on the set of sentences, and the following axioms are the minimum natural ones we postulate:

Let us revisit some aspects of the last definition. Relation (2) means it is unimportant in which order we list our sentences separated by ${\vee}$, like it is unimportant in which order we list the single formulas in a longer theory, or the collection of subroutines in a longer computer program. The connection between the single sentences is regulated solely by the variables they have in common. That is why relation (3) says that the semigroup operation ${\vee}$ of concatenation does not preserve the equivalence relation in general, but only if the concatenated sentences are unrelated. Thus we also needed to incorporate $a$ and $b$ in commutativity (2). Relation (5) tells us that it is unimportant which variables we choose (but only as a whole sentence). Relation (4) says if a theory is restated and fused with the original theory with other variables then essentially nothing new is said and the so new formed theory collapses to the original theory. The relation (6) is actually theoretically unimportant in the sense that it does not shine to the later abstract approach stated in definition 2.15 below through and may thus be omitted, but it is essential in the examples that we shall consider and are the only difference and the point what the distinction between main and auxiliary variables is all about. (See also example 10.1.)

We use class brackets as in $[x]$ for classes in quotients, where $x$ is a representative. The limits of sequences and the compare of all real valued functions $f:Y\rightarrow{\mathbb{R}}$ are always understood to be taken pointwise (i.e. $f\leq g$ iff $f(x)\leq g(x)$ for all $x,y\in Y$).

The whole theory of this paper is mainly build only on the quotient set of sentences:

On the quotient of sentences we naturally form an operation of concatenation by concatenating different sentences by choosing copies of them with disjoint variables chosen:

We will then mainly work with an abstract abelian monoid that actually comes out so far:

On the quotient set of sentences we essentially define a length function $\ell$ by choosing the shortest possible length $L$ among the equivalent representatives (i.e. $\ell([x])=\inf_{y\equiv x}L(y)$), but to ensure that the length of $s\nabla t$ is always bigger or equal than the length of $s$ for $s,t$ in the quotient $\overline{S}$, we correct this definition by the formula of definition 7.9. Thus the following definition of $\ell$ is just a somewhat obscured reformulation of defining $\ell$ at first as in definition 9.1 and then correcting it by definition 7.9:

We shall conveniently denote $\emptyset:=[\emptyset]\in\overline{S}$. We get very natural properties for the length function which we later will postulate axiomatically for abelian monoids:

We often abbreviate the notion “monotonically increasing” for (9) simply by “monotone” or “increasing”. Let $x{\wedge}y:=\min(x,y)$ and $x{\vee}y:=\max(x,y)$ denote the minimum and maximum, respectively, of two real numbers $x,y\in{\mathbb{R}}$.

The length function induces now two very natural notions of distance functions between sentences:

We sometimes call these functions also more precisely $d_{\ell}:=d$ and $\sigma_{\ell}:=\sigma$. They have the characteristic of distance between elements of $\overline{S}$:

As an illustrative example let us recall that in his famous work [4], Dirac took the then known quantum numbers valued Klein-Gordon function $\psi:{\mathbb{R}}^{4}\rightarrow B(H)$ (operators on Hilbert space) defined on spacetime ${\mathbb{R}}^{4}$ and the Klein-Gordon differential equation $\Delta\psi-\partial_{t}\psi-m^{2}\psi=0$ ($m\in{\mathbb{R}}$ constant) and took the formal square-root of the Klein-Gorden differential operator $K:=\Delta-\partial_{t}-m^{2}$ and formed the Dirac differential operator $D:=\sqrt{K}$ with constant coefficients in matrix algebra $M_{4}({\mathbb{C}})$, that is, $D^{2}=K$, and proposed the physical equation $D\psi=0$ and along with it predicted correctly the existence of particles and anti-particles [5]. This is a prototype example where an existing physical theory is slightly modified to obtain a new theory. That is, the Klein-Gordon equation is close to the Dirac equation, also in our “metric”. Let us compute this:

Throughout, if nothing else is said, we switch to the following general setting for $\overline{S},\nabla$ and $\ell$. Only if we discuss something involving $S$ itself, we implicitly assume without saying that we use the above specific definitions of $\overline{S},\nabla$ and $\ell$.

$\ell(x)$ is also called the information content of $x\in\overline{S}$.

Positivity of $\ell$ is also automatic by idempotence and subadditivity, as $\ell(x)=\ell(x\nabla x)\leq 2\ell(x)$. Instead of the above specific metric candidates $d$ and $\sigma$ from above, we shall sometimes use the following generalization:

$d$ is called a pseudometric on $\overline{S}$ if it is positive, symmetric, nilpotent and satisfies the $\Delta$-inequality (see definition 3.1).

The following section is a first discussion when the proposed distance functions $d$ and $\sigma$ of defintion 2.12 could indeed satisfy the well known triangle inequality (here also called $\Delta$-inequality). This is actually a main theme of this paper and first satisfying answers are given in theorems 6.10 and 7.21.

Let $(\overline{S},\nabla,\emptyset)$ be an abelian, idempotent monoid.

To heuristically see that $d$ of definition 2.12 in the context of formal languages could satisfy the $\Delta$-inequality we do the following considerations. Assume a sentence $s\in S$ is written in its shortest form as $s\equiv s_{1}{\vee}\ldots{\vee}s_{n}$ for $s_{i}\in S$, that is, such that $\ell([s])\approx L(s_{1}{\vee}\ldots{\vee}s_{n})=L(s_{1})+\ldots L_{(}s_{n})$. Similarly we do so for a given sentence $t\equiv t_{1}{\vee}\ldots t_{m}$. Many $s_{i}$ could be auxiliary function definitions, some of which may be identical to some $t_{j}$. As a first approximation we may estimate

where in the last line we have dropped identical auxiliary function definitions $\phi(t_{k+1}),\ldots,\phi(t_{m})$ which appear already in the $s_{i}$s, and so instead of calling $\phi(t_{j})$ we may call $s_{i}$ and that is why we had to introduce another transformation $\psi$ and dropped the superfluous $\phi(t_{j})$ by (6). In a certain sense, we formed the set theoretical union of $\{s_{1},\ldots,s_{n}\}$ and $\{t_{1},\ldots,t_{m}\}$.

If we sloppily replace the above $\leq$ by $\approx$ and view $L$ as a measure, then the $\Delta$-inequality holds:

Actually $d$ is like the maximum’s norm or $\ell^{\infty}$-norm, and $\sigma$ like the $\ell^{1}$-norm in ${\mathbb{R}}^{n}$ or space of real-valued sequences:

This is obvious by (10). Actually, $\sigma$ as just formulated is well-known to be a metric, $d$ might be less used. We continue by imposing definitions 2.15 and 2.12.

Switch back to the notions of definitions 2.15 and 2.16 for $\overline{S},\ell,d$ and $\sigma$.

This criterion for the triangle inequality will be extensively used in section 6:

Interestingly, if $\sigma$ satisfies the triangle inequality then $\ell$ must be a length function:

An important ingredient of our theory is the $\nabla$-inequality defined and first discussed in this section. It is fundamental in the proof of lemma 7.14, and thus for the whole section 7, theorem 7.14 and corollary 7.24.

Let $(\overline{S},\nabla,\emptyset)$ be an abelian, idempotent monoid.

This may be heuristically compared with normed vector spaces by setting $d(x,y):=\|x-y\|$, $x\nabla y:=x+y$ and having

Going back to the remark before lemma 3.3 and the setting of this lemma, we heuristically argue that the $\nabla$-equality may hold:

We say that a function $d$ satisfies the weak $\nabla$-inequality if it satisfies the inequality (14), and only the very weak one, if this holds only for $x\leq y$ (see definition 5.1).

We finally remark that given a (possibly infinite) sequence of pseudometrics in our setting, we may sum them up to get possibly a more faithful pseudometric:

In this section we consider a natural order relation on an abelian idempotent monoid induced by the monoid operation. This is not only important in various occasions in the theory like in the monotone increasingness of $\ell$ and in various aspects in the next section, but also a fundamental relation for information itself. It says when a theory is information-theoretically contained in another theory, and because we work with equivalence relations on theories, this works also for formally very different looking representatives of theories. This effect will even become more intense when we shall divide out equivalences induced by a pseudometric in definition 5.7.

In this section, if nothing else is said, we continue with the setting and notions of definitions 2.15 and 2.12.

The following three lemmas are straightforward to check, and the reader should recall the monotone increasingness of $\ell$, see (9), which is often used, as it is in lemmas 5.5 and 5.6.

The length function $\ell$ preserves the order and $d$ and $\sigma$ have particular simple formulas for ordered pairs:

Here are some further relations ($\delta_{y}$ is defined below) for $d$ and $\sigma$ under ordered pairs:

The following lemma reverses lemma 5.3. It also states in words that a theory is contained in another theory (i.e. $x\leq y$) if and only if the information content of the united theory is the information content of the bigger theory (i.e. $\ell(x\nabla y)=\ell(y)$).