Section II.III: Reductions

Definition & Examples

Definition 2.3.1: σ-Reduction

Let \(s \in S\). The σ-Reduction of \(s\), denoted \(\varsigma(s)\), is defined inductively with the following schema,

• Basis:

  • \(\varsigma(\sigma) = \varepsilon\)

  • If \(\neg(\sigma \subset_s s)\), then \(\varsigma(s) = s\)

• Induction:

  • If \(s = (u)(\sigma)(v)\) for any \(u, v \in S\) where \(\neg(\sigma \subset_s u)\), \(\varsigma(s) = \varsigma(uv)\)

\(\varsigma(s)\) is said to be reduced from, or a reduction of, \(s\).

Example \(ᚠ = \text{the widening circles into nothing gone}\). Consider \(\varsigma(ᚠ)\)

Let \(u_1 = \text{the}\) and \(v_1 = \text{widening circles into nothing gone}\). Let \(w_1 = (u_1)(v_1)\). Then, \(ᚠ = (u_1)(\sigma)(v_1)\). By the Induction clause of σ-Reduction,

\[\varsigma(ᚠ) = \varsigma((u_1)(v_1)) = \varsigma(w_1)\]

Let \(u_2 = \text{thewidening}\) and \(v_2 = \text{circles into nothing gone}\). Let \(w_2 = (u_2)(v_2)\). Then \(w_1 = (u_2)(\sigma)(v_2)\). By the Induction clause,

\[\varsigma(w_1) = \varsigma((u_2)(v_2)) = \varsigma(w_2)\]

Let \(u_3 = \text{thewideningcircles}\) and \(v_3 = \text{into nothing gone}\). Let \(w_3 = (u_3)(v_3)\). Then \(w_2 = (u_3)(\sigma)(v_3)\). By the Induction clause,

\[\varsigma(w_2) = \varsigma((u_3)(v_3)) = \varsigma(w_3)\]

Let \(u_4 = \text{thewideningcirclesinto}\) and \(v_4 = \text{nothing gone}\). Let \(w_4 = (u_4)(v_4)\). Then \(w_3 = (u_4)(\sigma)(v_4)\). By the Induction clause,

\[\varsigma(w_3) = \varsigma((u_4)(v_4)) = \varsigma(w_4)\]

Let \(u_5 = \text{thewideningcirclesintonothing}\) and \(v_5 = \text{gone}\). Let \(w_5 = (u_5)(v_5)\). Then \(w_4 = (u_5)(\sigma)(v_5)\). By the Induction clause,

\[\varsigma(w_4) = \varsigma((u_5)(v_5)) = \varsigma(w_5)\]

But \(neg(\sigma \subset_s w_5)\), therefore by the Basis clause,

\[\varsigma(w_5) = w_5\]

Working back up through the recursion, the original reduction is found,

\[\varsigma(ᚠ) = \text{"thewideningcirclesintonothinggone"}\]

∎

Properties

Note

All of these properties follow from the definition of σ-Reduction and the indicated axiom or theorem, and they are all understood to be quantified over \(S\).

1. From the definition of String Length: \(l(\varsigma(\sigma)) = l(\varepsilon) = 0\)

2. From the Discovery Axiom: \(\varsigma(\alpha) = \alpha\)

3. From the Discovery Axiom and the definition of String Length: \(l(\varsigma(\alpha)) = l(\alpha)\)

4. From the definition of String Length: \(l(\varsigma(s)) \leq l(s)\)

5. From the definition of Concatenation and the Closure Axiom: \(\varsigma(s) \in S\)

6. From the definition of the Delimiter Count: \(\Delta(\varsigma(s)) = 0\)

Theorems

Theorem 2.3.1

The Reduction of Concatenations is the Concatenation of Reductions.

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

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

By Theorem 1.2.3, there are only three cases to consider.

• Case I: \(\neg(\sigma \subset_s st)\)

• Case II: \(\neg(\sigma \subset_s s) \land (\sigma \subset_s t)\)

• Case III: \((\sigma \subset_s s) \land \neg(\sigma \subset_s t)\)

Note \((\sigma \subset_s st)\) is included in the disjunction of Case II and III.

Case I: \(\neg(\sigma \subset_s st)\)

By the contrapositive of Theorem 1.2.3,

\[\neg(\sigma \subset_s st) \implies (\neg(\sigma \subset_s s) \land \neg(\sigma \subset t))\]

Thus, by assumption, \(\neg(\sigma \subset_s s)\) and \(\neg(\sigma \subset_s t)\) are true.

From this and the definition of Reductions, it follows,

\[\varsigma(s) = s\]

\[\varsigma(t) = t\]

\[\varsigma(st) = st\]

Thus,

\[\varsigma(st) = st = (\varsigma(s))(\varsigma(t))\]

Case II \(\neg(\sigma \subset_s s) \land (\sigma \subset_s t)\)

By assumption and Containment, for some \(u,v \in S\) with \(\neg(\sigma \subset_s u)\),

\[t = (u)(\sigma)(v)\]

By the Induction clause of Reduction,

\[\varsigma(t) = (u)(\varsigma(v))\]

Now, consider \(st\)

\[st = (s)(u)(\sigma)(v)\]

By the contrapositive of Theorem 1.2.3,

\[\neg(\sigma \subset_s s) \land \neg(\sigma \subset_s u) \implies \neg(\sigma \subset_s su)\]

Thus, \(\neg(\sigma \subset_s su)\). From this, it can be concluded,

\[\varsigma(s) = s\]

\[\varsigma(u) = u\]

\[\varsigma(su) = su\]

Putting these three equalities together,

\[\varsigma(su) = (\varsigma(s))(\varsigma(u))\]

By the Induction clause Reduction,

\[\varsigma(st) = \varsigma((s)(u)(\sigma)(v)) = (su)\varsigma(v)\]

\[= (s)(u\varsigma(v)) = \varsigma(s)\varsigma(t)\]

Case III

The proof for Case III is identical to Case II, except \(s\) is decomposed into \(s = (u)(\varsigma)(v)\) with \(\neg(\sigma \subset_s v)\)

Thus all three cases are established. Summarizing and generalizing,

\[\forall s \in S: \varsigma(st) = (\varsigma(s))(\varsigma(t))\]

∎

Theorem 2.3.2

There are no Delimiters in a String if and only if it is equal to its own Reduction.

\[\forall s \in S: \Delta(s) = 0 \equiv \varsigma(s) = s\]

Proof Let \(s \in S\).

(\(\rightarrow\)) Assume \(\Delta(s) = 0\). By the properties of the Delimiter Count,

\[\neg(\sigma \subset_s s)\]

Therefore, by the Basis clause of Reduction,

\[\varsigma(s) = s\]

(\(\leftarrow\)) Assume \(\varsigma(s) = s\). By the properties of Reductions,

\[\Delta(\varsigma(s)) = 0\]

But by assumption,

\[\Delta(s) = 0\]

Thus equivalence is established. Summarizing and generalizing,

\[\forall s \in S: \Delta(s) = 0 \equiv \varsigma(s) = s\]

∎

Theorem 2.3.4

The Inverse of a Reduction is the Reduction of the Inverse.

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

Proof Let \(s \in S\). The proof proceeds by induction on the number of Delimiters in \(s\).

Basis Let \(\neg(\sigma \subset_s s)\); that is, assume there are no Delimiters in \(s\) (\(\Delta(s) = 0\)). By Theorem 1.2.10 and the fact \(\sigma^{-1} = \sigma\),

\[\neg(\sigma \subset_s s) \equiv \neg(\sigma \subset_s s^{-1})\]

Consider \((\varsigma(s))^{-1}\). By the Basis clause of the Reduction definition and the Basis assumption,

\[\varsigma(s) = s\]

Therefore,

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

Consider \(\varsigma(s^{-1})\). By \(\neg (\sigma \subset_s s^{-1})\) and the Basis clause of the Reduction definition,

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

Induction Assume for any \(s\) with \(\Delta(s) = k\) for some \(k \geq 1\) that \((\varsigma(s))^{-1} = \varsigma(s^{-1})\).

Let \(u \in S\) such that \(\Delta(u) = k + 1\). Let \(u = (v)(\sigma)(w)\), where \(\Delta(v) = 0\) and \(\Delta(w) = k\). By Induction clause of Reduction,

\[\varsigma(u) = \varsigma(vw) = \varsigma(v)\varsigma(w)\]

Where the last equality follows from Theorem 2.2.1. Consider \((\varsigma(u))^{-1}\).By application of Theorem 1.2.10,

\[(\varsigma(u))^{-1} = (\varsigma(w))^{-1}(\varsigma(v))^{-1} \quad \text{ (1) }\]

Consider \(u^{-1}\). By application of Theorem 1.2.10,

\[u^{-1} = (w^{-1})(\sigma^{-1})(v^{-1})\]

By Induction clause of Reduction,

\[\varsigma(u^{-1}) = \varsigma((w^{-1})(v^{-1}))\]

From Theorem 2.2.1

\[\varsigma(u^{-1}) = \varsigma(w^{-1})\varsigma(v^{-1}) \quad \text{ (2) }\]

Since \(\Delta(w) = k\) satisfies the inductive hypothesis,

\[\varsigma(w^{-1}) = \varsigma(w)^{-1} \quad \text{ (3) }\]

Consider \(\varsigma(v)\). \(\Delta(v) = 0\) by construction, thus by Theorem 2.2.2,

\[\varsigma(v) = v \quad \text{ (4) }\]

Likewise, since \(v\) and \(v^{-1}\) contain the same Characters,

\[\varsigma(v^{-1}) = v^{-1}\]

From (4) and String Inversion,

\[(\varsigma(v))^{-1} = v ^{-1}\]

From which it follows,

\[\varsigma(v^{-1}) = (\varsigma(v))^{-1} \quad \text{ (5) }\]

Now, (3) and (5) taken together with (1) and (2) imply,

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

Thus, the induction is established. Summarizing and generalizing,

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

∎

Theorem 2.3.5

σ-Reductions are idempotent.

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

Proof Let \(s, t \in S\) such that \(t = \varsigma(s)\). By THE properties of Reductions, \(\Delta(t) = 0\). Therefore, by Theorem 2.2.2, \(\varsigma(t) = t\). Thus, substituting in \(t\), \(\varsigma(\varsigma(s)) = \varsigma(s)\). Summarizing and generalizing,

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

∎

Theorem 2.3.6

One String is contained in another if and only if their σ-Reductions are contained in one another.

\[\forall s,t \in S: s \subset_s t \implies \varsigma(s) \subset_s \varsigma(t)\]

Proof Let \(s, t \in S\) such that \(s \subset_s t\). By Containment, for some \(u,v \in S\),

\[t = (u)(s)(v)\]

Consider \(\varsigma(t)\). By repeated application of Theorem 2.2.1,

\[\varsigma(t) = \varsigma((u)(s)(v)) = (\varsigma(u))(\varsigma(s))(\varsigma(v))\]

Since \(\varsigma(u)\) and \(\varsigma(v)\) by the closure property of Reductions, it follows,

\[\varsigma(s) \subset_s \varsigma(t)\]

∎

Important

Theorem 2.2.5 is a unidirectional implication, not an equivalence. Consider,

\[ᚠ = rob or borrow\]

\[a = orb\]

Clearly, \(\neg(a \subset_s ᚠ)\), due to the Delimiters in \(ᚠ\). However,

\[\varsigma(ᚠ) = roborborrow\]

\[\varsigma(a) = orb\]

So, \(\varsigma(a) \subset_s \varsigma(ᚠ)\).

Theorem 2.3.7

Every Word in a Sentence is contained in its σ-Reduction.

\[\forall \zeta \in C: \forall i \in N_{\Lambda(\zeta)}: \zeta[[i]] \subset_s \varsigma(\zeta)\]

Proof Let \(\zeta \in C\). Clearly \(\zeta[[i]] \subset_s \zeta\) for any \(i \in N_{\Lambda(\zeta)}\). From this and Theorem 2.2.5, it can be concluded,

\[\varsigma(\zeta[[i]]) \subset_s \varsigma(\zeta)\]

By the properties of Reductions,

\[\varsigma(\zeta[[i]]) = \zeta[[i]]\]

Therefore,

\[\zeta[[i]] \subset_s \varsigma(\zeta)\]

Summarizing and generalizing,

\[\forall \zeta \in C: \forall i \in N_{\Lambda(\zeta)}: \zeta[[i]] \subset_s \varsigma(\zeta)\]

◼︎