Analogical proportions in monounary algebras

Analogical proportions are expressions of the form “$a$ is to $b$ what $c$ is to $d$” written $a:b::c:d$ at the core of analogical reasoning which itself is at the core of artificial general intelligence (e.g. ?, ?, ?, ?, ?, ?, ?, ?, ?, ?).

The purpose of this paper is to study ?’s (?) abstract algebraic framework of analogical proportions — recently introduced in the general setting of universal algebra — in monounary algebras containing only a single unary function.

The motivation for studying proportions in that specific context is that monounary algebras are simple enough to provide a convenient context to analyze interesting concepts like congruences in combination with proportions, and rich enough to yield interesting novel insights.

The rest of the paper is structured as follows.

In §3, we repeat that every monounary algebra satisfies — as an instance of the general framework — for all elements of the domain (cf. Theorem 4):

• •

  p-symmetry: $a:b::c:d\quad\Leftrightarrow\quad c:d::a:b$,

• •

  inner p-symmetry: $a:b::c:d\quad\Leftrightarrow\quad b:a::d:c$,

• •

  inner p-reflexivity: $a:a::c:c$,

• •

  p-reflexivity: $a:b::a:b$,

• •

  p-determinism: $a:a::a:d\quad\Leftrightarrow\quad d=a$.

To the contrary, we will provide counterexamples showing that there are monounary algebras and elements such that:

• •

  central permutation: $a:b::c:d\quad\not\Leftrightarrow\quad a:c::b:d$,

• •

  strong inner p-reflexivity: $a:a::c:d\quad\not\Rightarrow\quad d=c$,

• •

  strong p-reflexivity: $a:b::a:d\quad\not\Rightarrow\quad d=a$,

• •

  p-commutativity: $a:b\not::b:a$,

• •

  p-transitivity: $a:b::c:d\quad\text{and}\quad c:d::e:f\quad\not\Rightarrow\quad a:b::e:f$,

• •

  inner p-transitivity: $a:b::c:d\quad\text{and}\quad b:e::d:f\quad\not\Rightarrow\quad a:e::c:f$.

This is in line with what we have observed in the general context of arbitrary algebras in Theorem 28 in ? (?).

Moreover, in §4 we shall prove that analogical proportions and congruences are in general not compatible in the following sense:¹¹1This observation was the motivation for introducing proportional congruences in ? (?). In each of the following cases, there is a monounary algebra $\mathfrak{A}=(A,S)$, a congruence $\theta$ on $\mathfrak{A}$, and elements $a,b,c,d\in A$ such that:

• •

  $a:b::c:d$ whereas $a/\theta:b/\theta\not::c/\theta:d/\theta$ (Theorem 7).

• •

  $a/\theta:b/\theta::c/\theta:d/\theta$ whereas $a:b\not::c:d$ (Theorem 8).

• •

  $a:b\not::a/\theta:b/\theta$ (Theorem 9).

• •

  $a\theta b$ and $c\theta d$ whereas $a:b\not::c:d$ (Theorem 10).

In §5, on the other hand, we shall prove a positive result showing that in the monounary algebra $(\mathbb{N},S)$ consisting of the natural numbers together with the unary successor function, we obtain the Difference Proportion Theorem 11 saying that within the abstract framework we have

This is more surprising than it might appear, as the abstract framework is not explicitly geared towards proportions in monounary algebras.

In a broader sense, this paper is a further step towards a mathematical theory of analogical proportions and analogical reasoning in general.

In this section, we interpret the abstract algebraic framework of analogical proportions in ? (?) within monounary algebras of the form $\mathfrak{A}=(A,S)$, where $A$ is a universe and $S:A\to A$ is a unary function.

We shall now recall the abstract algebraic framework of analogical proportions in ? (?) where we restrict ourselves to monounary algebras of the form $\mathfrak{A}=(A,S)$, where $A$ is a set and $S:A\to A$ is a unary function on $A$ (we can imagine $S$ to be a generalized “successor” function). Terms in $\mathfrak{A}$ have the form $S^{k}z$, for $k\geq 0$.

In what follows, let $\mathfrak{A}=(A,S_{A})$ and $\mathfrak{B}=(B,S_{B})$ be two monounary algebras — we will always omit the subscripts from notation and simply write $S$ instead of $S_{A}$ and $S_{B}$.

We define the analogical proportion entailment relation in two steps:²²2We use here the updated notation of ? (?) where we write $\uparrow$ instead of $Jus$ for sets of justifications; see ? (?) for motivation.

1. (1)

   Define the set of justifications of an arrow $a\to b$ in $\mathfrak{A}$ by

   $\displaystyle\uparrow_{\mathfrak{A}}(a\to b):=\left\{S^{k}z\to S^{\ell}z\;\middle|\;a\to b=S^{k}o\to S^{\ell}o,\text{ for some $o\in A$}\right\},$

   extended to an arrow proportion $a\to b:\joinrel\cdot\,c\to d$³³3Read as “$a$ transforms into $b$ as $c$ transforms into $d$”. in $(\mathfrak{A,B})$ by

   $\displaystyle\uparrow_{(\mathfrak{A,B})}(a\to b:\joinrel\cdot\,c\to d):=\ \uparrow_{\mathfrak{A}}(a\to b)\ \cap\uparrow_{\mathfrak{B}}(c\to d).$

   A justification is trivial in $(\mathfrak{A,B})$ iff it justifies every arrow proportion in $(\mathfrak{A,B})$, and we say that $J$ is a trivial set of justifications in $(\mathfrak{A,B})$ iff every justification in $J$ is trivial.

   Now we say that $a\to b:\joinrel\cdot\,c\to d$ holds in $(\mathfrak{A,B})$ — in symbols,

   $\displaystyle(\mathfrak{A,B})\models a\to b:\joinrel\cdot\,c\to d$

   iff

   1. (a)

      either $\uparrow_{\mathfrak{A}}(a\to b)\ \cup\uparrow_{\mathfrak{B}}(c\to d)$ consists only of trivial justifications, in which case there is neither a non-trivial relation from $a$ to $b$ in $\mathfrak{A}$ nor from $c$ to $d$ in $\mathfrak{B}$; or

   2. (b)

      $\uparrow_{(\mathfrak{A,B})}(a\to b:\joinrel\cdot\,c\to d)$ is maximal with respect to subset inclusion among the sets $\uparrow_{(\mathfrak{A,B})}(a\to b:\joinrel\cdot\,c\to d^{\prime})$, $d^{\prime}\in B$, containing at least one non-trivial justification, that is, for any element $d^{\prime}\in B$,⁴⁴4We ignore trivial justifications and write “$\emptyset\subsetneq\ldots$” instead of “$\{\text{trivial justifications}\}\subsetneq\ldots$” et cetera.

      $\displaystyle\emptyset\subsetneq\ \uparrow_{(\mathfrak{A,B})}(a\to b:\joinrel\cdot\,c\to d)$

      $\displaystyle\subseteq\ \uparrow_{(\mathfrak{A,B})}(a\to b:\joinrel\cdot\,c\to d^{\prime})$

      implies

      $\displaystyle\emptyset\subsetneq\ \uparrow_{(\mathfrak{A,B})}(a\to b:\joinrel\cdot\,c\to d^{\prime})\subseteq\ \uparrow_{(\mathfrak{A,B})}(a\to b:\joinrel\cdot\,c\to d).$

      We abbreviate the above definition by simply saying that $\uparrow_{(\mathfrak{A,B})}(a\to b:\joinrel\cdot\,c\to d)$ is $d$-maximal.

2. (2)

   Finally, the analogical proportion entailment relation is most succinctly defined by

   	$\displaystyle a:b::c:d\quad:\Leftrightarrow\quad$	$\displaystyle a\to b:\joinrel\cdot\,c\to d\quad\text{and}\quad b\to a:\joinrel\cdot\,d\to c$
   		$\displaystyle c\to d:\joinrel\cdot\,a\to b\quad\text{and}\quad d\to c:\joinrel\cdot\,b\to a.$

   This means that in order to prove $(\mathfrak{A,B})\models a:b::c:d$, we need to check the first two relations in the first line with respect to $\models$ in $(\mathfrak{A,B})$, and the last two relations in the same line in $(\mathfrak{B,A})$.

We will always write $\mathfrak{A}$ instead of $(\mathfrak{A,A})$ and we often omit the explicit reference to the underlying algebras.

Let $\mathbb{N}:=\{n,n+1,n+2,\ldots\}$. Given some justification $S^{k}z\to S^{\ell}z\in\ \uparrow_{\mathfrak{A}}(a\to b)$, $k,\ell\geq 0$, we can depict the two cases $k\leq\ell$ and $\ell\leq k$ as follows:

This is an abstract version of the situation in $(\mathbb{N},S)$ where, for example, $Sz\to S^{2}z\in\ \uparrow_{(\mathbb{N},S)}(1\to 2)$ and $S^{2}z\to Sz\in\ \uparrow_{(\mathbb{N},S)}(2\to 1)$ both have the following pictorial representation:

Define the monounary algebra $(\{0,1\},S)$ by $S0:=1$ and $S1:=0$. We can imagine $0$ and $1$ to be boolean truth values and $S$ to be negation. On the other hand, in $(\mathbb{N},S)$ let $Sa:=a+1$ be the unary successor function on the natural numbers $\mathbb{N}=\{0,1,2,\ldots\}$ starting at $0$. We can depict the algebras as:

The next result shows how we can capture evenness and oddness via analogical proportions between the two algebras.

In the tradition of the ancient Greeks, ? (?) (cf. ?, pp. 796-797) introduced (in the linguistic context) a set of proportional axioms as a guideline for formal models of analogical proportions — his list has since been extended by a number of authors (e.g. ?, ?, ?, ?, ?):⁵⁵5? (?) uses different names for the axioms — we have decided to remain consistent with the nomenclature in ? (?, §4.2).

  $a:b::c:d$         $c:d::e:f$    (p-transitivity),              $a:b::e:f$

  $a:b::c:d$         $b:e::d:f$    (inner p-transitivity).              $a:e::c:f$

We have the following analysis of the proportional axioms in monounary algebras:

This section is a collection of results relating congruences to analogical proportions in monounary algebras. Recall that an equivalence relation $\theta$ on $\mathfrak{A}=(A,S)$ is a congruence iff

The factor algebra obtained from $\mathfrak{A}$ with respect to $\theta$ is given by

where

contains the congruence classes

with respect to $\theta$, and $S/\theta:A/\theta\to A/\theta$ is defined by

Arithmetic or difference proportions are characterized as

and have been considered already by the ancient Greeks.⁶⁶6https://en.wikipedia.org/wiki/Proportion_(mathematics) In this section, we are going to see that difference proportions naturally occur in the prototypical infinite monounary algebra given by the natural numbers $\mathbb{N}=\{0,1,2\ldots\}$ together with the unary successor function $S:\mathbb{N}\to\mathbb{N}$ defined by $Sa:=a+1$. This is more surprising than it might appear, as the abstract framework is not geared towards proportions in monounary algebras — the forthcoming theorem is thus further conceptual evidence of the robustness of the underlying framework:

As a direct consequence of the Difference Proportion Theorem 11, we have the following analysis of the axioms in ? (?, §4.3) within the natural numbers with successor: