Section II.IV: Palindromes

Definition & Examples

Definition 2.4.1: Palindromes

The class of Palindromes, denoted \(P\), is defined as the Sentences that satisfy the following formula,

\[\zeta \in P \equiv \varsigma(\zeta) = (\varsigma(\zeta))^{-1}\]

Example

Let \(ᚠ_1 = \text{never odd or even}\). Then,

\[\varsigma(ᚠ_1) = \text{neveroddoreven}\]

\[(\varsigma(ᚠ_1))^{-1} = \text{neveroddoreven}\]

Therefore, \(ᚠ_1 \in P\).

Let \(ᚠ_2 = \text{not a ton}\). Then,

\[\varsigma(ᚠ_2) = \text{notaton}\]

\[(\varsigma(ᚠ_2))^{-1} = \text{notaton}\]

Therefore, \(ᚠ_2 \in P\)

Let \(ᚠ_2 = \text{fair is foul and foul is fair}\). Then,

\[\varsigma(ᚠ_3) = \text{fairisfoulandfoulisfair}\]

\[(\varsigma(ᚠ_3))^{-1} = \text{riafsiluofdnaluofsiriaf}\]

Therefore, \(ᚠ_3 \notin P\)

◼︎

Aspect

Perfect Palindromes

Definition 2.4.2: Perfect Palindromes

The class of Perfect Palindromes, denoted \(J\), is defined the Sentences that satisfy the following formula,

\[\zeta \in K \equiv \zeta = \zeta^{-1}\]

Note

The name, Perfect Palindromes, is premature, as it must be shown this definition satisfies Definition 2.3.1 before concluding membership in \(K\) implies membership in \(P\). This will be established in Theorem 2.3.4.

Theorem 2.4.1

Perfect Palindromes are Invertible Setences.

\[K \subseteq J\]

Proof Let \(\zeta \in K\). Then by definition of Perfect Palindromes,

\[\zeta = \zeta^{-1}\]

Therefore, since \(\zeta \in C\), \(\zeta^{-1} \in C\). By definition of Invertible Sentences, \(\zeta \in J\). Therefore,

\[\zeta \in K \implies \zeta \in J\]

But this is exactly the definition of a subset. Therefore,

\[K \subseteq J\]

◼︎

Note

Theroem 2.4.2 through Theorem 2.4.4 follow directly from Theorem 2.4.1 and Theorem 1.4.10 through Theorem 1.4.12.

Theorem 2.4.2

\[\forall \zeta \in K: \forall i \in N_{\Lambda(\zeta)}: \zeta[[i]] \in I\]

◼︎

Theorem 2.4.3

\[\forall \zeta \in K: \forall i \in N_{\Lambda(\zeta)}: \zeta^{-1}[[i]] = (\zeta[[\Lambda(\zeta) - i + 1]])^{-1}\]

◼︎

Theorem 2.4.4

\[\forall \zeta \in K: \Lambda(\zeta) = \Lambda(\zeta^{-1})\]

◼︎

Theorem 2.4.5

Perfect Palindromes are Palindromes.

\[K \subseteq P\]

Proof Let \(\zeta \in K\). By definition of Perfect Palindromes,

\[\zeta = \zeta^{-1}\]

Reducing both sides,

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

By Theorem 2.2.4,

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

Therefore, by definition of Palindromes,

\[\zeta \in J \implies \zeta \in P\]

But this is exactly the definition of subsets,

\[K \subseteq P\]

◼︎

Theorem 2.4.6

All Perfect Palindromes have a non-Empty Pivot Character.

\[\forall \zeta \in K: \omega_{\zeta} \neq \varepsilon\]

Proof Let \(\zeta \in K\).

By definition of a Perfect Palindrome, \(\zeta = \zeta^{-1}\). By Theorem 2.2.4,

\[\omega_{\zeta} \neq \varepsilon\]

◼

Theorem 2.4.7

All Perfect Palindromes have a non-Empty Pivot Word

\[\forall \zeta \in K: \Omega_{\zeta} \neq \varepsilon\]

Proof Let \(\zeta \in K\) and \(n = \Lambda(\zeta)\).

By definition of String Inversion,

\[l(\zeta) = l(\zeta^{-1}) \quad \text{ (1) }\]

By Theorem 2.4.3,

\[{\zeta}^{-1}[[i]] = (\zeta[[n - i + 1]])^{-1} \quad \text{ (2) }\]

By Theorem 1.4.12 and \(K \subseteq J\) (by Theorem 2.4.1),

\[\Lambda(\zeta) = \Lambda(\zeta^{-1}) \quad \text{ (3) }\]

Case I: \(n = 2i\) for some \(i \in \mathbb{N}\).

By the definition of Pivot Words,

\[\overrightarrow{\Omega_{\zeta}} = \zeta[[\frac{n}{2}]]\]

\[\overleftarrow{\Omega_{\zeta}} = \zeta[[\frac{n + 2}{2}]]\]

By (2),

\[(\zeta[[\frac{n}{2}]])^{-1} = \zeta^{-1}[[\frac{n + 2}{2}]]\]

Therefore,

\[\overleftarrow{\Omega_{\zeta}} = (\zeta^{-1}[[\frac{n}{2}]])^{-1}\]

But since \(\zeta \in K\) and \(\zeta = \zeta^{-1}\) by definition of Perfect Palindromes,

\[\overleftarrow{\Omega_{\zeta}} = (\zeta[[\frac{n}{2}]])^{-1} = (\overrightarrow(\Omega_{\zeta}))^{-1}\]

Therefore, by definition of Pivot Words,

\[\Omega_{\zeta} \neq \varepsilon\]

Case II: \(n = 2i + 1\) for some \(i \in \mathbb{N}\)

By the definition of Pivot Words,

\[\overleftarrow{\Omega_{\zeta}} = \zeta[[\frac{n + 1}{2}]]\]

\[\overrightarrow{\Omega_{\zeta}} = \zeta[[\frac{n + 1}{2}]]\]

By (2),

\[(\zeta[[\frac{n + 1}{2}]])^{-1} = \zeta^{-1}[[n - \frac{n + 1}{2} + 1]] = \zeta{-1}[[\frac{n+1}{2}]]\]

But \(\zeta = \zeta^{-1}\) by assumption. Therefore,

\[(\overrightarrow{\Omega_{\zeta}})^{-1} =(\zeta[[\frac{n + 1}{2}]])^{-1} = \zeta[[\frac{n+1}{2}]] = \overleftarrow{\Omega_{\zeta}}\]

Therefore, by definition of Pivot Words,

\[\Omega_{\zeta} \neq \varepsilon\]

Summarizing and generalizing,

\[\forall \zeta \in K: \Omega_{\zeta} \neq \varepsilon\]

◼

Theorem 2.4.8

All Perfect Palindromes are Subvertible.

\[K \subseteq \cancel{J}\]

Proof Let \(\zeta \in K\). Then, by Theorem 2.4.7 and Theorem 2.4.8,

\[\omega_{\zeta} \neq \varepsilon\]

\[\Omega_{\zeta} \neq \varepsilon\]

Therefore, by definition of Subvertible Sentences,

\[\zeta \in \cancel{J}\]

Thus, \(\zeta \in K \implies \zeta \in J\). But this is exactly the definition of a subset,

\[K \subseteq \cancel{J}\]

◼

Note

It follows directly from Theorem 2.4.1 and Theorem 2.4.8 that all Perfect Palindromes are Invertible and Subvertible.

\[K \subseteq (J \cap \cancel{J})\]

Imperfect Palindromes

Definition 2.4.3: Imperfect Palindromes

TODO

Parity

Definition 2.4.4: Parity

The set of Odd Palindromes, denoted \(P_{-}\), is defined as the set of Sentences which satisfy the open formula,

\[\zeta \in P_{-} \equiv ((\zeta \in P) \land (\exists n \in \mathbb{N}: l(\zeta) = 2i + 1))\]

The set of Even Palindromes, denoted \(P_{+}\), is defined as the set of Sentences which satisfy the open formula,

\[\zeta \in P_{+} \equiv (\zeta \in P) \land (\exists n \in \mathbb{N}: l(\zeta) = 2i)\]

Important

The following abbreviations are introduced,

\[K_{-} = K \cap P_{-}\]

\[K_{+} = K \cap P_{+}\]

Theorem 2.4.x

The Pivot Word of all Even Perfect Palindromes is Reflective.

\[\forall \zeta \in K_{-}: \Omega_{\zeta} \in R\]

Proof Let \(\zeta \in K_{-}\).

Theorem 2.4.x+1

The Pivot Character of all Odd Perfect Palindromes is a Delimiter

\[\forall \zeta \in K_{+}: \omega_{\zeta} = \sigma\]

Proof Let \(\zeta in K_{+}\).