¿Dónde puedo obtener más información sobre la operación "else" / "else monoid"?

Question

(El conjunto de los números naturales $\mathbb{N}$ comienza en $0$ para mí).

Sea $X$ denotan un conjunto, y definimos $X_\bot = X \uplus \{\bot\}.$ Sea $\mathbf{else}$ denota la operación binaria sobre $X_\bot$ definida del siguiente modo.

• Si $x \in X$ entonces $x \mathop{\mathbf{else}} y = x$ .
• Si $x = \bot$ entonces $x \mathop{\mathbf{else}} y = y$ .

De ello se deduce que $\mathbf{else}$ es una operación asociativa (normalmente no conmutativa) con identidad $\bot$ . Por lo tanto, $\mathbf{else}$ hace $X_\bot$ en un monoide, que podría llamarse razonablemente el "monoide else sobre $X$ ."

Pregunta. ¿Dónde puedo obtener más información sobre la operación? $\mathbf{else}$ y/o el "else-monoid"?

Aquí hay algunas cosas que podemos hacer con él. Si $f,g : X \rightarrow Y$ son parcial funciones que coinciden en su intersección, entonces existe una función parcial correspondiente $f \cup g : X \rightarrow Y$ al afirmar que $(f \cup g)(x) = f(x)$ siempre que $f(x)$ está bien definido, y que $(f \cup g)(x) = g(x)$ siempre que $g(x)$ está bien definida. Sin embargo, $f$ et $g$ ¡pueden no coincidir en su intersección! No se preocupe, $\mathbf{else}$ viene al rescate. Recordemos que las funciones parciales son "lo mismo" que los homomorfismos preservadores del punto base. Por lo tanto, tiene sentido definir que $(f \mathbin{\mathbf{else}} g)(x) = f(x) \mathbin{\mathbf{else}} g(x),$ donde imaginamos que $f$ et $g$ devolver $\bot$ en puntos de su dominio en los que no están definidos. Por lo tanto, $f \mathbin{\mathbf{else}} g$ está de acuerdo con $f \cup g$ siempre que la segunda esté bien definida; sin embargo, la ventaja de la primera es que es siempre definido.

He aquí una aplicación extremadamente sencilla. Si $a : \mathbb{N} \rightarrow \mathbb{R}$ es una secuencia de números reales, entonces es posible que queramos definir la turno de $a$ como la secuencia $\mathrm{Sh}(a) : \mathbb{N} \rightarrow \mathbb{R}$ definida del siguiente modo.

1. $\mathrm{Sh}(a)_0 = 0$
2. $\mathrm{Sh}(a)_{i+1} = a_i$

Se trata de una transformación lineal; $\mathrm{Sh}$ aparece como un importante contraejemplo en el análisis funcional. De hecho, pensando en términos de series de potencias formales, $\mathrm{Sh}$ es básicamente la multiplicación por $x$ . Explícitamente:

$$x \cdot \sum_{i:\mathbb{N}} a_i x^i = \sum_{i:\mathbb{N}} \mathrm{Sh}(a)_i x^i$$

Bien, he aquí una observación genial: podemos dar una descripción más simple de $\mathrm{Sh}$ utilizando el $\mathbf{else}$ operación. A saber:

$$\mathrm{Sh}(a)_i = a_{i - 1} \mathop{\mathbf{else}} 0$$

Básicamente, esto funciona porque $\mathbf{else}$ da una acción de funciones parciales sobre funciones totales. Es decir, dada una función parcial $p : X \rightarrow Y$ y una función total $f : X \rightarrow Y$ obtenemos una nueva función total $p \mathbin{\mathbf{else}} f$ calculado puntualmente. Esto da una acción del monoide $(\mathbf{PartialFunctions}(X,Y),\mathbf{else},\bot)$ en el plató $\mathbf{TotalFunctions}(X,Y)$ . La definición anterior de $\mathrm{Sh}(a)$ se obtiene teniendo la función parcial $i \in \mathbb{N} \mapsto a_{i-1}$ actúan sobre la función total $i \in \mathbb{N} \mapsto 0$ con lo que se obtiene una nueva función total. Me pregunto si hay argumentos complicados que impliquen funciones híbridas que puedan simplificarse utilizando $\mathbf{else}$ .

Answer 1

En si no monoide es un semigrupo cero a la izquierda con una identidad contigua.

Para cada $n > 0$ el monoide $U_n$ se define en el conjunto $\{1, a_1, \ldots, a_n\}$ por la operación $a_ia_j = a_j$ para cada $i, j \in \{1, \ldots, n\}$ et $1a_i = a_i1 = a_i$ para $1 \leqslant i \leqslant n$ . El monoide $\tilde{U}_n$ tiene el mismo conjunto subyacente que $U_n$ pero la multiplicación se define a la inversa: estos monoides son exactamente los "monoides else" finitos.

Los monoides $U_n$ y, en particular $U_2$ juegan un papel importante en el estudio del producto corona de monoides finitos. En particular, todo monoide finito aperiódico divide un producto en corona de copias de $U_2$ y todo monoide finito divide un producto corona de copias de $U_2$ y de grupo simple: se trata del famoso Teorema de Krohn-Rhodes .

Referencias:

[1] S. Eilenberg, Autómatas, lenguajes y máquinas Vol. B, Matemáticas puras y aplicadas, Vol. 58. Academic Press [Una filial de Harcourt Brace Jovanovich, Publishers], Nueva York, 1974. { \rm xvi}+451 pp.

[2] J. Rhodes y B. Steinberg,La $q$ -teoría de semigrupos finitos. Springer Monographs in Mathematics. Springer, Nueva York, 2009. xxii+666 pp.