Aplicaciones sucesivas de la operación binaria a un conjunto de n-tuplas produce un semigroup.

Question

Porque yo no soy un matemático de las versiones iniciales de esta pregunta no tan preciso como se necesite. Por tanto, espero a refinar y aclarar las preguntas en base a los comentarios y la retroalimentación. Gracias por su paciencia.

Dado un conjunto $A$ $n$- tuplas, por ejemplo

$$ [ (3, 5, 5), (5, 3, 4), (1, 6, 3), (2, 1, 6), (6, 2, 1), (4, 4, 2) ] $$

donde $n = 3$, y una operación binaria $\land$ tal que para cualquier par de tuplas $(x_1 , y_1 , z_1)$ $(x_2 , y_2 , z_2)$

$$ (x_1 , y_1 , z_1) \de la tierra (x_2 , y_2 , z_2) = ( min(x_1,x_2) , min(y_1,y_2) , min(z_1,z_2) ) $$

La aplicación de $\land$ a todos los pares de tuplas del conjunto $A$ de los rendimientos del conjunto de $B$ (ignorando duplicados)

$$ [(1, 2, 1), (1, 5, 3), (2, 1, 2), (3, 2, 1), (2, 1, 4), (2, 1, 1), (4, 3, 2), (2, 1, 5), (1, 1, 3), (3, 3, 4), (1, 4, 2), (4, 2, 1), (3, 4, 2), (1, 3, 3), (5, 2, 1)] $$

La aplicación de $\land$ nuevo para todos los pares de tuplas del conjunto $B$ de los rendimientos del conjunto de $C$ (de nuevo, ignorando duplicados)

$$ [ (1, 2, 1), (2, 1, 1), (1, 3, 2), (3, 3, 2), (2, 1, 4), (1, 4, 2), (3, 2, 1), (4, 2, 1), (1, 1, 2), (1, 1, 3), (2, 1, 2), (1, 1, 1), (1, 3, 3) ] $$

El conjunto $C$ tiene una propiedad interesante que he observado. Es decir, las aplicaciones posteriores de $\land$ para cualquier par de tuplas en $C$ no generan nuevas tuplas fuera del conjunto.

Más en general, he observado que para cualquier conjunto de $n$-tuplas, $n - 1$ sucesivas aplicaciones de $\land$ genera un conjunto de $n$-tuplas que es cerrado bajo $\land$. A mi limitada comprensión de $C$ es un semigroup, donde $A$ $B$ son semigroupoids.

Mi verdadera pregunta es ¿por qué hacer las aplicaciones posteriores de la operación binaria $\land$ a un semigroupoid resultado en un semigroup?

Answer 1

Esta es una buena pregunta, que en realidad es un problema en semilattices.

Deje $\mathbb{N}$ ser el semigroup de números naturales en virtud de la operación $x \wedge y = \min(x, y)$. Este semigroup es claramente conmutativa, pero también es idempotente, es decir, $x \wedge x = x$ todos los $x \in \mathbb{N}$. Conmutativa y idempotente semigroups también son llamados semilattices.

Ahora, el producto de $k$ copias de $(\mathbb{N}, \wedge)$ los rendimientos de la semilattice $(\mathbb{N}^k, \wedge)$ con la operación definida de las componentes. Es decir, si $x = (x_1, \ldots, x_k)$ $y = (y_1, \ldots, y_k)$ $$ x \wedge y = (x_1, \ldots, x_k)(y_1, \ldots, y_k) = (x_1, \wedge y_1, \ldots, x_k \wedge y_k). $$ Si $S$ es un subconjunto de a $\mathbb{N}^k$, definamos $S^n$ por inducción mediante el establecimiento $S^1 = S$$S^{n+1} = \{s \wedge t \mid s \in S \text{ and } t \in S^n\}$. Ahora, su resultado puede ser enunciada de la siguiente manera:

Para cada $k > 0$, la $S^k$ es igual a la subsemigroup de $\mathbb{N}^k$ generado por $S$.

Antes de probar el caso general, es interesante considerar el caso de $k = 2$, que ya contiene el argumento principal de la prueba. Un elemento de la subsemigroup de $\mathbb{N}^2$ generado por $S$ es de la forma $$ t=(x_1, y_1) \wedge (x_2, y_2) \wedge \dotsm \wedge (x_n,y_n) = (\min\{x_1, \ldots, x_n\}, \min\{y_1, \ldots, y_n\}) $$ con $(x_1, y_1), (x_2, y_2), \dotsm, (x_n,y_n) \in S$. El problema es demostrar que el $t$ pertenece a $S^2$. Deje $i$ $j$ ser tal que \begin{align} (1) \quad x_i &= \min\{x_1, \ldots, x_n\} \\ (2) \quad y_j &= \min(\{y_1, \ldots, y_n\} - \{y_i\}). \end{align} Yo reclamo que $$ t = (x_i, y_i) \wedge (x_j, y_j) = (\min\{x_i, x_j\}, \min\{y_i, y_j\}). $$ En efecto, por (1), $$\min\{x_i, x_j\} = x_i = \min\{x_1, \ldots, x_n\}$$ y por (2) $$\min\{y_i, y_j\} = \min(y_i, \min(\{y_1, \ldots, y_n\} - \{y_i\}) = \min(\{y_1, \ldots, y_n\}$$ lo que demuestra la demanda y de la muestra que $t \in S^2$.

El caso general no es mucho más difícil, pero requiere el doble de los índices. Deje $S$ ser un subconjunto de a $\mathbb{N}^k$. Un elemento de la subsemigroup de $\mathbb{N}^k$ generado por $S$ es de la forma $$ t= x_1 \wedge x_2 \wedge \dotsm x_n $$ donde $x_1 = (x_{1,1}, \ldots, x_{1,k}), \dots, x_n = (x_{n,1}, \ldots, x_{n,k}) \in S$. Vamos a mostrar que $t \in S^k$. Deje $i_1, \ldots, i_k$ ser tal que \begin{align} x_{i_1,1} &= \min\{x_{1,1}, \ldots, x_{n,1}\} \\ x_{i_2,2} &= \min(\{x_{1,2}, \ldots, x_{n,2}\} - \{x_{i_1,2}\}) \\ \vdots &=\vdots\\ x_{i_k,k} &= \min(\{x_{1,k}, \ldots, x_{n,k}\} - \{x_{i_1,k}, \ldots, x_{i_{k-1},k}\})\\ \end{align} Yo deje de comprobar que $t = x_{i_1} \wedge \dotsm \wedge x_{i_k}$ y por lo tanto pertenece a $S^k$.