Section I.II: Strings

Table of Contents

Definitions

1. Definition 1.2.1: Concatenation: \(st\)

2. Definition 1.2.2: String Length: \(l(s)\)

3. Definition 1.2.3: Character Indices: \(s[i]\)

4. Definition 1.2.5: Containment: \(t \subset_s s\)

5. Definition 1.2.6: Canonization: \(\pi(s)\)

6. Definition 1.2.7: Canon: \(\mathbb{S} = \{ \pi(s) \mid s \in S \}\)

7. Definition 1.2.8: String Inversion: \(s^{-1}\)

Axioms

1. Axiom 0: Empty Axiom: \(\exists! \varepsilon\)

2. Axiom I: Comprehension Axiom: \(\iota \in S\)

3. Axiom II: Equality Axiom: \(s = t\)

4. Axiom III: Decomposition Axiom: \((s \neq \varepsilon) \implies (s = {\iota}{t}) \lor (s = {t}{\iota})\)

5. Axiom IV: Closure Axiom: \(st \in S\)

Theorems

1. Theorem 1.2.1: \(l(st) = l(s) + l(t)\)

2. Theorem 1.2.2: \(\varepsilon \subset_s s\)

3. Theorem 1.2.3: \((\iota \subset_s uv) \implies ((\iota \subset_s u) \lor (\iota \subset_s v))\)

4. Theorem 1.2.4: \(\pi(\pi(s)) = \pi(s)\)

5. Theorem 1.2.5: \(s \in \mathbb{S} \equiv \pi(s) = s\)

6. Theorem 1.2.6: \(s,t \in \mathbb{S} \implies st \in \mathbb{S}\)

7. Theorem 1.2.8: \(\forall s \in \mathbb{S}: ((l(s) = l(t)) \land (\forall i \in N_{l(t)}: s[i] = t[i])) \implies (s = t)\)

8. Theorem 1.2.9: \((s^{-1})^{-1} = s\)

9. Theorem 1.2.10: \((st)^{-1} = (t^{-1})(s^{-1})\)

10. Theorem 1.2.11: \(u \subset_s v \equiv u^{-1} \subset_s v^{-1}\)

String Axioms

The formal development of this section largely agrees with standard treatments found in the theory of strings and concatenation

Axiom 0: Empty

The Empty Character exists.

\[\exists! s \in S: s = \varepsilon\]

This assumption immediately establishes the existence of an element in the domain, namely the Empty Character. This element will act as the identity element for formal expressions and allows recursions to halt. Most of the recursive definitions that follow will implicitly rely on the Empty Axiom.

A String is regarded as a linguistic artifact or inscription that is defined entirely by its Characters and their ordering. A Character is seen as the basic unit of a String. In order to construct a String or set of Strings, an Alphabet of Characters must be selected and assigned.

If a Characters is non-Empty, it belongs to the Alphabet,

\[\Sigma = \{ \mathfrak{a}, \mathfrak{b}, \mathfrak{c}, ... \}\]

This is to be regarded as a value assignment. The entities \(\mathfrak{a}, \mathfrak{b}, \mathfrak{c}, ...\) are interpretted within a particular model of the formal system. They are descriptive constants.

In particular, the Delimiter belongs to the Alphabet.

\[\sigma \in \Sigma\]

Warning

The work will proceed as if the \(\Sigma \neq \varnothing\), but it should be noted at this stage \(\Sigma = \varnothing\) trivially satisifies all of the axioms that will be presented by annihiliating the domain of discourse.

However, \(\varepsilon\), as a formal term, is not of the same type as Alphabetic Characters. Alphabetic Characters are non-logical and are dependent on an interpretation. \(\varepsilon\), on the contrary, is structural in nature. In this regard, \(\varepsilon\) bears similarity to the parenthesis.

The aggregate of the Alphabet and the Empty Character is referred to as the Total Alphabet and is denoted,

\[\Sigma_{e} = \Sigma \cup \{ \varepsilon \}\]

Axiom I: Comprehension

All Characters in the Total Alphabet are Strings.

\[\forall \iota \in \Sigma_{e}: \iota \in S\]

In order to construct more complicated Strings through the sequencing of Characters, the operation of Concatenation must be defined, but defining Concatenation requires a well-defined notion of equality.

Axiom II: Equality

For any Strings \(s, t \in S\), the notion of equality, denoted by \(s = t\), is a primitive concept and assumed to be understood. It is further assumed that equality is an equivalence relation, satisfying reflexivity, symmetry and transitivity,

1. \(\forall s \in S: s = s\)

2. \(\forall s, t \in S: s = t \leftrightarrow t = s\)

3. \(\forall s, t, u \in S: ((s = t) \land (t = u)) \implies (s = u)\)

Note

The Equality Axiom is technically a conjunction of axioms.

Important

The order of dependence in the logical notions that underlie formal string theory is nearly unavoidable. In this hierarchy,

\(\text{Equality} \to \text{Concatenation} \to \text{Length}\)

Equality must be assumed to give meaning to the Concatenated expression, \(s = ut\). Next, concatenation must be defined to give meaning to \(l(s)\).

There are feasible constructions that bend the order of dependence slightly, but they tend to lack the simplicity of the proposed order. For example, it is possible to build a formal theory of strings by assuming a primitive notion of character equality and then defining string equality in terms of string length and character equality, but systems built on these artifices tend to require prosaic constructions that obscure the subject matter with unnecessary formal machinery.

Concatenation

Definition 1.2.1: Concatenation

The Concatenation of any Strings \(s, t \in S\) and is denoted \(st\). Concatenation is defined inductively through the following schema,

1. Basis:

   • If \(s = \varepsilon\), \(st = t\)

2. Induction:

   • If \(s \neq \varepsilon\), then \(s = {\iota}{u}\) where \(\iota \in \Sigma_e\) and \(u \in S\). Define \(st = ({\iota}u)t = \iota(ut)\).

To make the operands clear, parenthesis will sometimes be used, e.g. \(s(t) = (s)t = (s)(t) = st\).

Note

As previously indicated and now presently shown, the Empty Axiom and the Equality Axiom are necessary assumptions to ensure the Basis and Induction clauses of Concatenation are well-defined.

The notion of Concatenation is immediately followed by several assumptions that strengthen its definition and provide a basis for understanding the expanded range of expressions that are now possible by representing Strings as sequences of other Strings, e.g. \(s = uv\).

Axiom III: Decomposition

If a String is non-Empty, it can be decomposed into a Concatenation of a single Character and a String, in either direction.

\[\forall s \in S: (s \neq \varepsilon) \implies (\exists \iota \in \Sigma_e, u \in S: s = (\iota)(u) ) \quad \text{ (1) }\]

\[\forall s \in S: (s \neq \varepsilon) \implies (\exists \iota \in \Sigma_e, u \in S: s = (u)(\iota) ) \quad \text{ (2) }\]

Decomposition as in (1) will be referred to as left-handed decomposition. Decomposition as in (2) will be referred to as right-handed decomposition.

Note

The Decomposition Axiom is implicitly used by the Induction clause of Concatenation to ensure the decomposition \(s = {\iota}{u}\) exists.

Note

In the event \(\Sigma = \varnothing\), nothing exists in the domain to satisfy the inequality \(s \neq \varepsilon\), so the Decomposition Axiom is vacuously true.

Note

The \(\iota\) in the Decomposition Axiom is always satisfied by atleast \(\varepsilon\).

The direction of implication Decomposition Axiom cannot be extended into an equivalence without admitting a class of expressions, such as \(s = \varepsilon\varepsilon\), \(s = \varepsilon\varepsilon\varepsilon\), etc., as possible solutions to the inequality \(s \neq \varepsilon\), which would invalidate the Basis clause of Concatenation.

In other words, the unidirectional implication of the Decomposition Axiom ensures every non-Empty String can be “extended” indefinitely, e.g. \(s = (s)(\varepsilon) = ((s)(\varepsilon))(\varepsilon)\), etc., a necessary condition for Concatenation, but it also allows for the identities \(\varepsilon\varepsilon = \varepsilon\), \(\varepsilon\varepsilon\varepsilon = \varepsilon\), etc.

Axiom IV: Closure

Concatenation is closed over the set of all finite Strings.

\[\forall s,t \in S: st \in S\]

Closure and Decomposition form different poles of a String’s logical structure. The Closure Axiom ensures all Concatenations are Strings (possibly Empty), whereas the Decomposition Axiom ensure all Strings are Concatenations (of possibly Empty Characters). Both are necessary to ensure Strings and Concatenation belong to the same universe of discourse.

Warning

It is important to keep in mind the essential distinction between Strings and Characters versus String Variables and Character Variables.

An expression such as \(s_1 = \mathfrak{ab}\) is an identity assignment to the literal String \(s_1\) of a specific sequence of literal Characters. It is formally incorrect to regard \(\mathfrak{ab}\) as a Concatenation; it is a physical inscription that satisfies the equation \(s = (u)(v)\) for \(u = \mathfrak{a}\) and \(v = \mathfrak{b}\).

Carefully consider the distinction between these meanings illustrated in the following example.

Example Let \(s, t \in S\) for some Characters \(\iota, \nu, \omicron, \rho \in \Sigma\) such that \(s = \iota\nu = (\iota)(\nu)\) and \(t = \omicron\rho = (\omicron)(\rho)\).

Consider,

\[st = (\iota\nu)(\omicron\rho) = ((\iota)(\nu))((\omicron)(\rho))\]

Apply the Induction clause of Concatenation,

\[st = \iota((\nu)((\omicron)(\rho)))\]

By the Comprehension Axiom (all Characters are Strings) and Decomposition Axiom (all non-Empty Strings can be decomposed), \(\nu = \nu\varepsilon = (\nu)(\varepsilon)\),

\[st = \iota(((\nu)(\varepsilon))((\omicron)(\rho)))\]

\[st = \iota(\nu((\varepsilon)(\omicron)(\rho)))\]

Note

The \(\varepsilon\) pulled in through the Decomposition Axiom once the end Character of \(s\) was reached then propagates the operation of Concatenation into the second String by inserting a leading Empty Character into it to kick off the nested operation.

\[st = \iota(\nu((\omicron)(\rho)))\]

\[st = \iota(\nu(\omicron(\rho)))\]

Let \(\iota = \mathfrak{a}, \nu = \mathfrak{b}, \omicron = \mathfrak{c}, \rho = \mathfrak{d}\). Then \(s = (\mathfrak{a})(\mathfrak{b}) = \mathfrak{ab}\) and \(t = (\mathfrak{c})(\mathfrak{d}) = \mathfrak{cd}\). The previous equation shows the Concatenation of these literal Strings is accomplished through the sequential Concatenations,

\[\mathfrak{a}(\mathfrak{b}(\mathfrak{c}(\mathfrak{d}))) = \mathfrak{a}(\mathfrak{b}(\mathfrak{cd}))\]

\[= \mathfrak{a}(\mathfrak{bcd}) = \mathfrak{abcd}\]

The general logic of this example can be extended to Strings composed of an arbitrary number of Characters.

∎

Note

By Comprehension Axiom, all Characters are Strings and Concatenation is closed under \(S\) by the Closure Axiom, therefore, as each nested concatenation is evaluated in the preceding example, the Induction clause in Concatenation ensures the next level of concatenation is a String.

Important

Many of the results of the formal theory of strings are taken as given and are not proven. The following list details the properties of concatenation that will be assumed.

1. Associativity: \((s)(ut) = (su)t\)

2. Non-commutative: \(st \neq ts\)

3. Left-cancellation: \(st = su \implies t = u\)

4. Right-cancellation: \(ts = us \implies t = u\)

Keep in mind, in the preceding example, the equation \(\mathfrak{bcd} = (\mathfrak{b})(\mathfrak{cd}) = \mathfrak{b}(\mathfrak{cd})\) is a relation between three literal Strings. A translation of the example into English would read as follows,

“bcd” is the concatenation of b and cd

It is only incidental the name “bcd” in this translation is the literal concatenation of the names “b” and “cd”. It is not logically necessary to represent a sequence with the literal terms that compose it, but such a decision would be akin to a numeral system where the number one is represented with ||, the number two is represented with |, the number three with |||| and so on. Formally, such constructions can be accomplished, but nothing but confusion would be gained by such an effort.

Note

Refer to Motivation for a more in-depth discussion of the nature of concatenation.

String Length

The length of a String is defined as its number of non-Empty Characters.

Definition 1.2.2: String Length

Let \(s \in S\). The String Length of \(s\), denoted \(l(s)\), is defined inductively using the following schema,

1. Basis:

   • If \(s = \varepsilon\), \(l(s) = 0\)

2. Induction:

   • If \(s \neq \varepsilon\) and \(s = (\nu)(u)\) with \(\nu \in \Sigma\) and \(u \in S\), then \(l(s) = l(u) + 1\)

   • If \(s \neq \varepsilon\) and \(s = (\nu)(u)\) with \(\nu = \varepsilon\) and \(u \in S\), then \(l(s) = l(u)\)

Note

The Empty Axiom in conjunction with String Length ensures there is exactly one String in \(S\) such that \(l(s) = 0\).

Note

The Decomposition Axiom is used in the Induction clause of String Length to ensure the existence of the String’s decomposition.

Example Let \(s = {\iota_1}{\iota_2}\varepsilon{\iota_3}{\iota_4} = ({\iota_1})(({\iota_2})((\varepsilon)(({\iota_3})({\iota_4}))))\).

Applying the Induction Clause of String Length with \(\nu = \iota_1\) and \(u = u_1 = {\iota_2}\varepsilon{\iota_3}{\iota_4}\),

\[l(s) = l(u_1) + 1\]

Applying the Induction Clause of String Length with \(\nu = \iota_2\) and \(u = u_2 = \varepsilon{\iota_3}{\iota_4}\),

\[l(u_1) = l(u_2) + 1\]

Applying the Induction Clause of String Length with \(\nu = \varepsilon\) and \(u = u_3 = {\iota_3}{\iota_4}\),

\[l(u_2) = l(u_3)\]

Applying the Induction Clause of String Length with \(\nu = \iota_3\) and \(u = u_4 = \iota_4\),

\[l(u_3) = l(u_4) + 1\]

Applying the Induction Clause of String Length with \(\nu = \iota_4\) and \(u = u_5 = \varepsilon\), which is guaranteed to exist by the Decomposition Axiom,

\[l(u_4) = l(u_5) + 1\]

Applying the Basis cluase of String Length to \(u_5 = \varepsilon\),

\[l(u_5) = 0\]

Note

The Empty Character, \(\varepsilon\), serves to terminate the recursion.

Putting the recursion together,

\[l(s) = (((0) + 1) + 1 + 1) + 1 = 4\]

∎

The definition of String Length allows an important shorthand to be defined. This notation introduces nothing new into the system, but significantly improves the readability of proofs.

Definition 1.2.3: Character Indices

Let \(s \in S\). Let \(i \in \mathbb{N}\) such that \(1 \leq i \leq l(s)\). The Character at index \(i\) in \(s\), denoted \(s[i]\), is defined inductively using the schema,

1. Basis:

   • If \(s = \varepsilon\), \(s[i]\) is undefined.

2. Induction: If \(s \neq \varepsilon\), then \(s = u(\iota)\) for some \(\iota \in \Sigma_e\) and \(u \in S\).

   • If \(i = l(s)\) and \(\iota \neq \varepsilon\), \(s[i] = \iota\)

   • If \(i \neq l(s)\) or \(\iota = \varepsilon\), then \(s[i] = u[i]\)

Note

The notation \(s[i]\) is borrowed directly from string slicing in computer science.

The following example shows how the definition of Character indexing “skips” over the physical index of Empty Characters and assigns a logical index to any non-Empty Characters in a String.

Example

Let \(s_1 = \mathfrak{ab}\varepsilon\mathfrak{c}\). By String Length, \(l(s_1) = 3\).

Consider \(s_1[3]\). Apply the definition of Character Indices with \(u_1 =\mathfrak{ab}\varepsilon\) and \(v_1 = \mathfrak{c}\). \(i = l(s_1)\) and \(v_1 \neq \varepsilon\), therefore, by the Induction clause, \(s[3] = \mathfrak{c}\).

Consider \(s_1[2]\). Apply the definition of Character Indices with \(u_1 =\mathfrak{ab}\varepsilon\) and \(v_1 = \mathfrak{c}\). At this step, \(v_1 \neq \varepsilon\) but \(i \neq l(s_1)\), so the \(s_1[i] = u_1[i]\). Note \(l(u_1) = 2\).

To find \(u_1[i]\), let \(u_1 = {u_2}{v_2}\) where \(u_2 = \mathfrak{ab}\) and \(v_2 = \varepsilon\). At this step, \(i = l(u_1)\), but \(v_2 = \varepsilon\), therefore \(u_1[i] = u_2[i]\). Note \(l(u_2) = 2\).

To find \(u_2[i]\), let \(u_2 = {u_3}{v_3}\) where \(u_3 = \mathfrak{a}\) and \(v_3 = \mathfrak{b}\). At this step, \(i = l(u_2)\) and \(v_3 \neq \varepsilon\), therefore \(u_2[i] = v_3 = \mathfrak{b}\).

From this, it follows, \(s_1[2] = u_1[2] = u_2[2] = v_3 = \mathfrak{b}\).

Similarly, it can be shown \(s_1[1] = \mathfrak{a}\).

∎

Theorem 1.2.1

The String Length of the concatenation of String \(s\) and String \(t\) is equal to the sum of their String Lengths.

\[\forall s,t \in S: l(st) = l(s) + l(t)\]

Proof The proof proceeds by structural induction on the number of non-Empty Characters in \(s\).

Basis: Let \(s = \varepsilon\) and \(t \in S\). Consider \(st = {\varepsilon}{t}\).

By Concatenation, \({\varepsilon}{t} = t\). By String Length, \(l(\varepsilon) = 0\). It follows from the basic laws of arithmetic,

\[l({\varepsilon}{t}) = l(t) = 0 + l(t)\]

\[= l(\varepsilon) + l(t) = l(s) + l(t)\]

Therefore, the base case, \(l(st) = l(s) + l(t)\), holds.

Induction: Assume \(l(ut) = l(u) + l(t)\) for any \(t \in S\) and any \(u \in S\) up to some fixed length.

Let \(s = {\iota}u\) for some \(\iota \in \Sigma\). That is, assume \(s\) has one more Character than \(u\), possibly Empty. Consider,

\[l(st) = l((\iota{u})t) = l((\iota)({u}{t}))\]

If \(\iota = \varepsilon\), then \(\iota{u} = \varepsilon{u} = u\). by the Induction clause of String Length,

\[l(st) = l(\varepsilon{ut}) = {l(ut) = l(u) + l(t)\]

Where the last equality follows from the inductive hypothesis. Moreover, if \(\iota = \varepsilon\), \(s = \varepsilon{u} = u\). Therefore,

\[l(st) = l(s) + l(t)\]

If \(\iota \neq \varepsilon\), then it follows from the Induction clause of String Length,

\[l(st) = l(\iota(ut)) = l(ut) + 1 = l(u) + l(t) + 1 \quad \text{ (1) }\]

Where the last equality follows from the inductive hypothesis.

Consider the quantity \(l(s) = l(\iota{u})\). By the Induction clause of String Length,

\[l(s) = l(\iota{u}) = l(u) + 1 \quad \text{ (2) }\]

Combining (1) and (2),

\[l(st) = l(s) + l(t)\]

Therefore, the inductive step is established. It follows from the principle of finite induction,

\[\forall s,t \in S: l(st) = l(s) + l(t)\]

∎

Containment

The concept of Containment is the formal explication of the colloquial relation of “substring of”

Definition 1.2.5: Containment

Let \(u,v \in S\). The relation of containment, denoted \(u \subset_s v\), is said to obtain between \(u\) and \(v\) when the following open formula in \(u,v\) is satisfied,

\[u \subset_s v \equiv \exists w_1, w_2 \in S: v = ({w_1})(u)({w_2})\]

When this occurs, \(u\) is said to be contained in \(v\).

Example Let \(s_1 = \mathfrak{abcdef}\).

The truth of the following propositions can be verified using the given values of \(w_1\) and \(w_2\) in the definition of Containment.

• \(\mathfrak{ab} \subset_s s_1\), where \(w_1 = \varepsilon\) and \(w_2 = \mathfrak{cdef}\).

• \(\mathfrak{cde} \subset_s s_1\), where \(w_1 = \mathfrak{ab}\) and \(w_2 = \mathfrak{f}\).

• \(\neg (\mathfrak{g} \subset_s s_1)\), for any \(w_1, w_2\)

∎

Theorem 1.2.2

The Empty Character is contained in every String.

\[\forall s \in S: \varepsilon \subset_s s\]

Proof Let \(s \in S\).

Instantiating the Closure Axiom with \(\varepsilon\) and \(s\),

\[\varepsilon{s} \in S\]

Instantiating the Closure Axiom with \(\varepsilon\) and \(\varepsilon{s}\),

\[\varepsilon\varepsilon{s} \in S\]

By repeated application of Concatenation,

\[s = \varepsilon\varepsilon{s}\]

By the Empty Axiom, \(\varepsilon\) exists.

Therefore, applying the definition of Containment with \(w_1 = \varepsilon\) and \(w_2 = s\), it is concluded,

\[\varepsilon \subset_s s\]

Summarizing and generalizing,

\[\forall s \in S: \varepsilon \subset_s s\]

∎

Theorem 1.2.3

If any Character \(\iota\) is contained in \(uv\), then \(\iota\) is contained in \(u\) or \(\iota\) is contained in \(v\).

\[\forall \iota \in \Sigma_e: \forall u, v \in S: (\iota \subset_s uv) \implies ((\iota \subset_s u) \lor (\iota \subset_s v))\]

Proof Let \(\iota \in \Sigma_e\). Let \(u,v \in S\) such that \(\iota \subset_s uv\)

If \(\iota = \varepsilon\), then the theorem is trivially true by Theorem 1.2.2.

Therefore, assume \(\iota \in \Sigma\). By Containment,

\[\exist w_1, w_2 \in S: uv = (w_1)(\iota)(w_2)\]

Let \(w = (w_1)(\iota)\).

\[l(u) < l(w)\]

\[l((w_1)(\iota)) = l(w_1) + l(\iota)\]

IN PROGRESS

TODO: Since \(uv\) is a non-overlapping sequence of Characters and \(\iota \subset_s uv\), it follows from the laws of logic that it must be the case that either \(\iota\) is contained in \(u\) or \(\iota\) is contained in \(v\).

∎

Canonization

Canonization is a function defined over \(s \in S\) that produces the canonical form of a String by removing all instances of the Empty Character from it.

Definition 1.2.6: Canonization

Let \(s \in S\) such that \(s = uv\) with \(u \in S\) and \(v \in \Sigma_e\). The Canonization of \(s\), denoted \(\pi(s)\), is defined inductively using the following schema,

• Basis:

  • \(\pi(\varepsilon) = \varepsilon\)

• Induction:

  • If \(v = \varepsilon\), \(\pi(s) = \pi(u)\).

  • If \(v \neq \varepsilon\), \(\pi(s) = (\pi(u))(v)\)

The Canonization of a String \(s\) is referred to as the canonical form or canonical representation of \(s\).

Example Let \(s_1 = (\mathfrak{a})(\varepsilon)(\mathfrak{b})\).

Let \(u_1 = (\mathfrak{a})(\varepsilon)\) and \(v_1 = \mathfrak{b}\). Note \(v_1 \in \Sigma\) and \(s_1 = (u_1)(v_1)\). By the Induction clause of Canonization,

\[\pi(s_1) = (\pi(u_1))(v_1)\]

Let \(u_2 = \mathfrak{a}\) and \(v_2 = \varepsilon\). Note \(u_1 = (u_2)(v_2)\). By the Induction clause,

\[\pi(u_1) = \pi(u_2)\]

Let \(u_3 = (\varepsilon)\) and \(v_3 = \mathfrak{a}\). Note \(v_3 \in \Sigma\) and \(u_2 = (u_3)(v_3)\). By the Induction clause,

\[\pi(u_2) = (\pi(u_3))(v_3)\]

By the Basis clause,

\[\pi(u_3) = \varepsilon\]

Putting the recursion together,

\[\pi(s_1) = ((\varepsilon)(v_3))(v_1)\]

\[\pi(s_1) = (\varepsilon)(\mathfrak{ab})\]

By the Basis clause of Concatenation, this becomes,

\[\pi(s_1) = \mathfrak{ab}\]

∎

Definition 1.2.7: Canon

The Canon, denoted \(\mathbb{S}\), is defined as the image of the function \(\pi(s)\) over the set of all finite Strings \(S\),

\[\mathbb{S} = \{ \pi(s) \mid s \in S \}\]

Canonization provides a method of “cleaning” \(S\) of troublesome Strings, such as \(\mathfrak{a}\varepsilon\mathfrak{b}\), that prevent the assertion of uniqueness within the semantic domains that will be shortly introduced. The Canon provides a domain within \(S\) where the uniqueness of certain semantic properties can be established.

Theorem 1.2.4

Canonization is idempotent.

\[\forall s \in S: \pi(\pi(s)) = \pi(s)\]

Proof Let \(s \in S\). The proof proceeds by induction on \(s\).

Basis Let \(s = \varepsilon\). By the definition Canonization,

\[\pi(\varepsilon) = \varepsilon.\]

Let \(t = \pi(\varepsilon)\). Consider,

\[\pi(t) = \pi(\pi(\varepsilon)) = \pi(\varepsilon) = \varepsilon\]

Induction Assume \(\pi(\pi(t)) = \pi(t)\) for some \(t \in S\). Let \(s = (t)(\iota)\) where \(\iota \in \Sigma_e\). Either \(\iota = \varepsilon\) or \(\iota \neq \varepsilon\).

Case I: \(\iota = \varepsilon\)

By the Induction clause of Canonization,

\[\pi(s) = \pi(t)\]

By the Basis clause of Concatenation,

\[s = (t)(\varepsilon) = t\]

Therefore, by inductive hypothesis,

\[\pi(s) = \pi(t) = \pi(\pi(t)) = \pi(\pi(s))\]

Case II \(\iota \neq \varepsilon\)

By the Induction clause of Canonization,

\[\pi(s) = \pi(t\iota) = \pi(t)(\iota)\]

Now the String \(u = \pi(t)\) belongs to the Canon, \(u \in \mathbb{S}\), and must therefore be a String free of \(\varepsilon\). Likewise, \(\iota \neq \varepsilon\) by assumption. Therefore, \(u\iota\) is also a String free of \(\varepsilon\). From this and the definition of Canonization, it follows \(\pi(u\iota) = u\iota\),

\[\pi(s) = u\iota\]

Consider,

\[\pi(\pi(s)) = \pi(u\iota) = u\iota\]

Therefore,

\[\pi(s) = \pi(\pi(s))\]

And the induction is established. Summarizing and generalizing,

\[\forall s \in S: \pi(s) = \pi(\pi(s))\]

∎

Theorem 1.2.5

A String is canonical if and only if it is equal to its own Canonization.

\[s \in \mathbb{S} \equiv s = \pi(s)\]

Proof Let \(s \in S\).

(\(\leftarrow\)) Assume \(s = \pi(s)\). By the definition of Canon, any String that is the result of Canonization belongs to the Canon, therefore \(s \in \mathbb{S}\).

(\(\rightarrow\)) Assume \(s \in \mathbb{S}\). By the definition of Canon, there must exist a \(t \in S\) such that \(\pi(t) = s\). Consider \(\pi(\pi(t))\). By Theorem 1.2.4,

\[\pi(\pi(t)) = \pi(t)\]

Substituting \(\pi(t) = s\),

\[\pi(s) = s\]

Therefore, the equivalence is established.

∎

Theorem 1.2.6

Canonization is closed under Concatenation.

\[\forall s,t \in mathbb{S}: st \in \mathbb{S}\]

Proof Let \(t \in S\). The proof will proceed by induction on \(t\).

Basis: Let \(s \in \mathbb{S}\). Let \(t = \varepsilon\). By the Basis clause of Canonization and the definition of Canon, \(t \in \mathbb{S}\)

Consider \(st\). By the Basis clause of Concatenation, \(st = s\varepsilon = s\). But \(s \in \mathbb{S}\) by assumption, thus \(st \in \mathbb{S}\).

Induction. Assume \(u \in \mathbb{S}\) such that \(su \in \mathbb{S}\). By Theorem 1.2.5,

\[\pi(su) = su \quad (1)\]

Let \(t = (u)(\iota)\) where \(\iota \in \Sigma\). Consider \(st\),

\[st = (s)(u)(\iota) = (su)(\iota) \quad (2)\]

Where the last equality follows from the associativity of concatenation. By inductive hypothesis, \(su \in \mathbb{S}\). Moreover, \(\iota \in \mathbb{S}\) since \(\pi(\iota) = \iota\). Therefore, by definition of Canonization

\[\pi(st) = \pi(su)\iota\]

Substituting in (1) and (2)

\[\pi(st) = (su)\iota = st\]

By Theorem 1.2.5,

\[st \in \mathbb{S}\]

Thus, the induction is complete. Summarizing and generalizing,

\[\forall s,t \in \mathbb{S}: st \in \mathbb{S}\]

∎

Canonization is an important operation in the study of the logical relations that govern semantic Strings. The Canon provides an abstraction over the domain of all finite Strings where logical properties and physical properties of a String coincide, as in the following list shows. Each of these properties is a direct result Theorem 1.2.5.

1. The logical length (String Length) of a String is the physical length of the String’s canonical form: \(l(s) = l(\pi(s))\)

2. The logical Characters of a String are the physical Characters of the String’s canonical form: \(s[i] = (\pi(s))[i] = \pi(s)[i]\), where the last equality is shorthand.

3. The canonical form of a String is \(\varepsilon\)-free, a structural property that translates to “has no Empty Characters”.

The next two theorems will be extremely important in establishing the equality of certain classes of Strings.

Theorem 1.2.8

If two canonical Strings have the same String Length and all of their Characters equal index-wise, then those Strings are equal.

\[\forall s,t \in \mathbb{S}: ((l(s) = l(t)) \land (\forall i \in N_n: s[i] = t[i])) \implies (s = t)\]

Proof Let \(s,t \in \mathbb{S}\). The proof will proceed by induction on \(l(s)\).

Basis: Assume \(l(s) = 1\).

If a canonical String \(s\) has a \(l(s) = 1\), then it follows from Canonization, \(s = \iota\) for some \(\iota \in \Sigma\).

If \(l(t) = 1\) and \(t[1] = s[1]\), then this implies,

\[s = \iota = t\]

Therefore, the Basis holds.

Induction Assume for all for all \(u,v \in \mathbb{S}\), \(l(u) = l(v) = n\) and \(\forall i \in N_n: u[i] = v[i]\) implies \(u = v\).

Let \(s, t \in \mathbb{S}\) such that \(l(s) = l(t) = n + 1\) and \(\forall i \in N_n: s[i] = t[i]\). Since \(s\) and \(t\) are canonical, they can be written \(s = u(\iota)\) and \(t = v(\nu)\).

From \(s[n+1] = t[n+1]\), it follows \(\iota = \nu\). By inductive hypothesis, \(u = v\). Therefore, by the Equality Axiom,

\[s = u\iota = v\nu = t\]

Thus, the induction holds. Summarizing and generalizing,

\[\forall s,t \in \mathbb{S}: ((l(s) = l(t)) \land (\forall i \in N_n: s[i] = t[i])) \implies (s = t)\]

∎

Note

Theorem 1.2.8 shows how the logical properties of a String’s canonical form, namely its logical length (String Length) and its logical (non-Empty) Characters reduce to the abstract and primitive concept of “string equality”.

The formal system under construction assumes the process of Canonization precedes the formation of Language. Empty Characters possess no semantic content, and therefore must be exlcuded from the domain before Language is possible. This will be explicitly formalized in the Canonization Axiom.

Example Let \(s = \mathfrak{a}\varepsilon\) and \(t = \mathfrak{b}\).

By Canonization,

\[\pi(s) = \mathfrak{a}\]

\[\pi(t) = \mathfrak{b}\]

By Concatenation,

\[\pi(s)\pi(t) = \mathfrak{ab}\]

Now, apply Concatenation to \(st\) with \(s = (\mathfrak{a})\varepsilon\), then

\[st = \mathfrak{a}({\varepsilon}{t})\]

Important

The \(\varepsilon\) “moves” inside of the parenthesis and thus, “triggers” another recursive call to concatenation.

\[{\varepsilon}t = t = \mathfrak{b}\]

So that,

\[st = \mathfrak{ab}\]

∎

Important

The previous example suggests an important, often overlooked fact, Concatenation always yields a Canonical String. In other words, Concatenation can be regarded as \(\mathfrak{F}: S \mapsto \mathbb{S}\)

String Inversion

Important

See Motivation for a detailed epistemological explication of the proceedings.

Two definitions of String Inversion will be given, a definition using induction and a definition using logical properties. It will be shown immediately these definitions are equivalent.

Definition 1.2.8: String Inversion (Inductive)

Let \(s, t \in S\). Let \(n \in \mathbb{N}\). The inverse of \(s\), denoted \(s^{-1}\), is defined inductively with the following schema,

• Basis: If \(s = \varepsilon\), then \(s^{-1} = \varepsilon\)

• Induction: If \(s = (\iota)(t)\) where \(\iota \in \Sigma\) and \(t \in S\), then \(((\iota)(t))^{-1} = (t^{-1})(\iota)\)

Definition 1.2.8: String Inversion (Descriptive)

Let \(s, t \in S\). Let \(n \in \mathbb{N}\). \(t\) is called the inverse of \(s\), denoted \(s^{-1}\), if the following conditions hold,

• \(l(s) = l(t) = n\)

• \(\forall i \in N_n: t[i] = s[n - i + 1]\)

Example Let \(s_1 = \mathfrak{abc}\). Let \(s_2 = {s_1}^{-1}\). The Inverse can be constructed through its Character Indices by applying String Inversion,

\[s_2[1] = s_1[3 - 1 + 1] = s_1[3] = \mathfrak{c}\]

\[s_2[2] = s_1[3 - 2 + 1] = s_1[2] = \mathfrak{b}\]

\[s_2[3] = s_1[3 - 3 + 1] = s_1[1] = \mathfrak{c}\]

Concatenating the results,

\[s_2 = {s_1}^{-1} = \mathfrak{cba}\]

∎

The equivalence of these definitions can be established through structural induction. Let \(t = s^{-1}\).

Basis: If \(l(s) = 1\), that is, if \(s \in \Sigma\), then \(l(t) = 1\). By the Inductive definition of Inversion, \(t = s^{-1} = (s\varepsilon)^{-1} = (\varepsilon)^{-1}(s) = \varepsilon(s) = s\).

Induction Assume \(t = s^{-1}\) for a fixed \(l(s) = n\) such that \(\forall i \in N_n: t[i] = s[n - i + 1]\) and \(l(t) = l(s)\). Consider \(u \in S\) with \(l(u) = n + 1\). Then, \(u\) can be written \(u = \iota(v)\) for some \(\iota \in \Sigma\) and \(v \in S\) with \(l(v) = n\). Note \(s[1] = \iota\). By the Inductive definition of Inversion, \((\iota(v))^{-1} = (v^{-1})\iota\). Thus \(t\) is a String that ends in \(\iota\), \(t[n+1] = \iota = s[1]\).

Theorem 1.2.9

The inverse of an inverse is the original String.

\[\forall s \in S: (s^{-1})^{-1} = s\]

Proof Let \(s \in S\). Let \(t = s^{-1}\). Let \(n = l(s)\). From String Inversion,

\[l(t) = l(s) = n \quad \text{ (1) }\]

\[\forall i \in N_n: t[i] = s[n - i + 1] \quad \text{ (2) }\]

Let \(u = t^{-1}\). Applying String Inversion again,

\[l(u) = l(t) = n \quad \text{ (3) }\]

\[\forall j \in N_n: u[j] = t[n - j + 1] \quad \text{ (4) }\]

Plugging \(i = n - j + 1\) into (2) and substituting into (4),

\[\forall j \in N_n: u[j] = s[n - (n - j + 1) + 1] = s[j] \quad \text{ (5) }\]

Moreover, from (1) and (3), it follows,

\[l(s) = l(u) \quad \text{ (6) }\]

By the Theorem 1.2.8, (5) and (6) together imply,

\[u = t^{-1} = (s^{-1})^{-1} = s\]

Therefore,

\[\forall s \in S: (s^{-1})^{-1} = s\]

∎

Theorem 1.2.10

The Inverse of a Concatenation of two Strings is the Concatenation of their Inverses in the reversed order.

\[\forall s,t \in S: (st)^{-1} = (t^{-1})(s^{-1})\]

Proof Let \(s,t \in S\). Let \(u = st\). Let \(m = l(s)\) and \(n = l(t)\). Let \(u = st\). By Theorem 1.2.1,

\[l(u) = l(st) = l(s) + l(t) = m + n\]

Let \(v = u^{-1} = (st)^{-1}\). Let \(w = (t)^{-1}(s)^{-1}\). By repeated application of String Inversion,

\[l(v) = l(st) = m + n \quad \text{ (1) }\]

\[l((t)^{-1}) = l(t) = n\]

\[l((s)^{-1}) = l(s) = m\]

Using these results and applying Theorem 1.2.1 to \(w\),

\[l(w) = l((s)^{-1}) + l((t)^{-1}) = m + n \quad \text{ (2) }\]

From (1) and (2), it follows,

\[l(v) = l(w) \quad \text{ (3) }\]

Let \(i \in N_{m+n}\).

Case I: \(i \leq i \leq n\)

By String Inversion,

\[v[i] = u[m + n - i + 1]\]

By assumption \(i \leq n\) or \(n - i \geq 0\), therefore,

\[m + n - i \geq m\]

Increasing the LHS of this inequality does not affect the truth of its assertion,

\[m + n - i + 1 \geq m\]

From this, \(u = st\) and \(l(s) = m\), it follows that \(u[m + n - i + 1]\) is an index in \(t\),

\[v[i] = t[n - i + 1] \quad \text{ (4) }\]

Consider \(w[i]\). Since \(l((t)^{-1}) = n\) and \(i \leq n\), it follows that \(w[i] = (t^{-1})[i]\). By String Inversion,

\[w[i] = t^{-1}[i] = t[n - i + 1] \quad \text{ (5) }\]

Combining (4) and (5),

\[v[i] = w[i] \quad \text{ (6) }\]

Applying Theorem 1.2.8, (3) and (6) imply,

\[v = w\]

Case II: \(n + 1 \leq i \leq m + n\)

By String Inversion,

\[v[i] = u[m + n - i + 1]\]

By assumption \(i \geq n + 1\) or \(n - i + 1 \leq 0\), therefore,

\[m + n - i + 1 \leq m\]

From this, \(u = st\) and \(l(s) = m\), it follows that \(u[m + n - i + 1]\) is an index in \(s\),

\[v[i] = s[m + n - i + 1] \quad \text{ (7) }\]

Consider \(w[i]\). Since \(l((t)^{-1}) = n\) and \(i \geq n\), it follows that \(w[i] = (s^{-1})[i - n]\). By String Inversion,

\[w[i] = s^{-1}[i-n] = s[m - (i - n) + 1]\]

\[w[i] = s[m + n - i + 1] \quad \text{ (8) }\]

Combining (7) and (8),

\[v[i] = w[i] \quad \text{ (9) }\]

Applying Theorem 1.2.8, (3) and (6) imply,

\[v = w\]

In both cases, the theorem is proved. Summarizing and generalizing,

\[\forall s,t \in S: (st)^{-1} = (t^{-1})(s^{-1})\]

∎

Theorem 1.2.11

A String \(s\) contains another a String \(s\) if and only if the inverse of \(s\) contains the inverse of \(t\).

\[\forall s,t \in S: (t \subset_s s) \equiv (t^{-1} \subset_s s^{-1})\]

Proof Let \(s,t \in S\).

(\(\rightarrow\)) Assume \(t \subset_s s\). Then by Containment, there exists \(w_1, w_2 \in S\) such that,

\[s = (w_1)(t)(w_2)\]

Consider \(s^{-1}\). Applying Theorem 1.2.10 twice, this becomes,

\[s^{-1} = (w_2)^{-1}(t)^{-1}(w_1)^{-1}\]

Therefore, there exists \(u_1 = {w_2}^{-1}\) and \(u_2 = {w_1}^{-1}\) such that \(s^{-1} = (u_1)(t^{-1})(u_2)\) and by the definition of Containment,

\[t^{-1} \subset_s s^{-1}\]

(\(\leftarrow\)) The proof is identical to (\(\rightarrow\)).

Therefore,

\[\forall s,t \in S: t \subset_s s \equiv t^{-1} \subset_s s^{-1}\]

∎