Cualquier operación conmutativa asociativa se puede ampliar a una función de conjuntos finitos no vacíos

Question

Este es un hecho que se utiliza muy frecuentemente en matemáticas generales, cuando escribimos estas indicaciones como $1+2+3+4$: ya sabemos que $+$ es conmutativa y asociativa, podemos "colocar los paréntesis" y no te preocupes por el orden de las operaciones. Por supuesto, yo creo que este, pero, ¿cómo hace uno para probar esto en todos los casos? Incluso diciendo que me está dando problemas. Aquí está mi intento:

Asumir una operación $\oplus:S\times S\to S$ es proporcionado satisfacciones $x\oplus y=y\oplus x$ $x\oplus(y\oplus z)=(x\oplus y)\oplus z$ todos los $x,y,z\in S$.

Reclamo: Dado cualquier conjunto finito $\emptyset\subset A\subseteq S$, no existe un único $z\in S$ tal que para cualquier función de $f:{\cal P}(A)\to{\cal P}(A)$ que satisface $\emptyset \subset f(B)\subset B$ todos los $B\subseteq A$ $|B|\ge 2$ y cualquier función de $g:{\cal P}(A)\to S$ que satisface $g(\{x\})=x$ todos los $x\in S$ $g(B)=g(f(B))\oplus g(B-f(B))$ para todos los $|B|\ge 2$, $g(A)=z$.

La operación $\oplus$ no tienen necesariamente un elemento de identidad, así que no intente definir un vacío de la suma. Intuitivamente, este elemento $z$ representa la suma finita de los elementos en $A$, por lo que si $A=\{1,2,3\}$$f(\{1,2,3\})=\{1\}$$f(\{2,3\})=\{3\}$, luego $$z=g(\{1,2,3\})=g(\{1\})\oplus g(\{2,3\})=g(\{1\})\oplus (g(\{3\})\oplus g(\{2\}))=1\oplus(3\oplus 2).$$ Tiene que haber una mejor manera de decirlo, pero esta es la única manera que se me ocurre para la captura de todas las posibilidades de parenthesization, y aún ser susceptibles a una prueba formal. Y ahora que he dicho esto, ¿cómo puedo demostrarlo? Supongo que debo introducir en algo, pero no tengo idea de qué.

Edit: aquí, El objetivo es ser capaz de definir una operación $F$ tal que $F(\{x_1,\dots,x_n\})=x_1\oplus\cdots\oplus x_n$, y estar seguro de que la operación está bien definido y satisface $F(A\cup B)=F(A)\oplus F(B)$, cuando se $A$ $B$ son disjuntas finita no vacía de subconjuntos de a $S$.

Answer 1

Usted puede indicar lo siguiente: es un conjunto de $S$ con la operación binaria $\oplus$ en él que es asociativa y conmutativa.

Cada finito no vacío sistema $A\subseteq S$, existe un elemento $S_A\in S$ tal que: 1) si $A=\{a\}$, entonces el $S_A=a$. 2) si $|A|=n$ entonces para cualquier biyectiva función $f:\{1,2,3,4,\cdots ,n\}\to A$, sostiene que el $S_A = f(1)\otimes S_{\{f(2),f(3),\cdots, f(n)\}}$.

Por otra parte, esta asignación $A\mapsto S_A$ es el único con estas propiedades.

La prueba de existencia y unicidad se hace por un estándar prueba por inducción.

Answer 2

Esta es la equivalencia entre conmutativa semigroups en el sentido usual de la palabra y su monádico descripción. De ello se desprende, por ejemplo, de Beck monadicity teorema. Aquí está una de la abajo-a-tierra formulación: Si $S$ es un conmutativa semigroup, entonces tenemos un mapa que asocia a cada función de $\lambda : S \to \mathbb{N}$ con la propiedad de que $\lambda(s)>0$ durante al menos un $s$, un elemento $\sum_{x \in S} \lambda(x) \cdot x$ $S$ (abreviado por $\sum \lambda$), con las siguientes propiedades:

• Si $E=\{s\}$ algunos $s \in S$$\lambda(s)=1$, $$\sum_{x \in E} \lambda(x) \cdot x = s.$$
• Si $\mu$ es una función que asocia a cada $\lambda$ por encima de un número natural (con la propiedad de que hay algo de $\lambda$$\mu(\lambda)>0$), luego $$\sum_{x \in S} \left(\sum_{\lambda} \mu(\lambda) \cdot \lambda(x)\right) \cdot x = \sum_{x \in S} \left(\sum_{\sum \lambda = s} \mu(\lambda) \right) \cdot x$$

Lo contrario también es cierto. Siempre que $S$ es un conjunto equipado con una operación de suma como de arriba, a continuación, esto dota a $S$ con la estructura de un conmutativa semigroup. El punto es que el conjunto de funciones de $\lambda$ equipada con el pointwise además es el libre conmutativa semigroup en el set $S$. Ver aquí para el correspondiente monádico descripción de abelian grupos.

Answer 3

Así que usted quiere probar que si $S$ es un conjunto y $+$ es un binario conmutativa asociativa de la ley : $S \times S \to S$, entonces existe una única función de $\sum$ de los no vacía de subconjuntos finitos de $S$ $S$la satisfacción de :
- si $x \in S, \sum \{x\} = x$
- si $A \cap B = \emptyset, \sum A \cup B = \sum A + \sum B$.

Demostrar mediante la inducción de el tamaño del subconjunto : si $|A| = 1$, entonces no tenemos ninguna opción.
Si $|A| \ge 2$, supongamos que podemos definir $\sum A$ en varias formas : $A = B_1 \cup B_2 = C_1 \cup C_2$, donde las parejas son disjuntas. Usando la hipótesis de inducción, las sumas de los subconjuntos $B_i$ $C_j$ están bien definidos y tenemos que mostrar que $\sum B_1 + \sum B_2 = \sum C_1 + \sum C_2$.
Deje $D_{ij} = B_i \cap C_j$. Supongamos por ahora que ninguno de ellos está vacío. A continuación, $\sum B_1 = \sum D_{11} + \sum D_{12}$ y así sucesivamente, y la demanda se reduce a probar que $\forall a,b,c,d \in S, (a+b)+(c+d) = (a+c)+(b+d)$.

Y esto es fácil : $(a+b)+(c+d) = a+(b+(c+d)) = a+((c+d)+b) = a+(c+(d+b)) = (a+c)+(d+b) = (a+c)+(b+d)$.

Los casos en que uno o más de los $D_{ij}$ está vacío se hace de forma similar (y son aún más fácil). O usted podría agregar un elemento $\star$ $S$y extender $+$ definiendo $\star + x = x + \star = x$, demuestran que, a $+$ todavía es conmutativa y asociativa, y, finalmente, definir $\sum \emptyset = \star$

Answer 4

Resulta que la reclamación como declaró en un principio que no puede probarse por inducción directamente, ya que posteriormente pasos pueden introducir elementos repetidos, que no se tienen en cuenta en la demanda. En su lugar, vamos a probarlo para las secuencias y debilitar al final.

Reclamo: Vamos A $[n]=\{0,1,\dots,n-1\}$. Dado cualquier secuencia finita $A=\langle x_0,x_2,\dots,x_{n-1}\rangle$ $n\ge1$ y cada una de las $x_i\in S$, no existe un único $z\in S$ (denotado $F(A)$) tal que para cualquier función de $f:{\cal P}[n]\to{\cal P}[n]$ que satisface $\emptyset \subset f(B)\subset B$ todos los $B\subseteq [n]$ $|B|\ge 2$ y cualquier función de $g:{\cal P}[n]\to S$ que satisface $g(\{i\})=x_i$ todos los $i\in [n]$ $g(B)=g(f(B))\oplus g(B-f(B))$ para todos $|B|\ge 2$, $g[n]=z=F(A)$.

Vamos a tratar de demostrar mediante la inducción en $n$. En el caso base, $A=\langle x_0\rangle$ algunos $x_0\in S$. A continuación, $g(\{0\})=g(\{x\})=x_0$ es única, por lo que se hace.

En la inducción de paso, suponemos que para todos los $|B|\le n$, no hay una única $F(B)$ como se indica en la demanda, y consideramos que $|A|=n+1$. A continuación, tenemos la pretensión de que existe algo de dos elementos, establece que es evaluado por $g$. (Este paso se lleva a algún tipo de justificación; no fuimos precisos acerca de la "relevante" en la parte del dominio de $g$, por lo que este debe decir: $\exists k\in{\Bbb N}\ \exists h:[k]\to {\cal P}(n)$ tal que $h(0)=[n+1]$$|h(k-1)|=2$$\forall m<k-1\,\big[h(m+1)=f(h(m))\vee h(m+1)=h(m)-f(h(m))\big]$. Esta es nuestra forma de especificar un "camino" a través del "árbol binario" prescrito por $f$.) Supongamos $h(k-1)=\{i,j\}$ es de este elemento del conjunto. A continuación, $g(\{i,j\})=x_i\oplus x_j$ o $g(\{i,j\})=x_j\oplus x_i$, y sabemos que estos son iguales.

Ahora considere el $B=\langle y_0,\dots,y_{n-1}\rangle=A-\langle x_i,x_j\rangle+\langle x_i\oplus x_j\rangle$, donde nos quite $x_i$ $x_j$ a partir de la secuencia y anexar $x_i\oplus x_j$ hasta el final. Hay un índice de asignación de $\varphi$, lo que lleva a cada elemento de a $A$ para el elemento correspondiente de $B$, $y_{\varphi(m)}=x_m$, salvo que $y_{\varphi(i)}=y_{\varphi(j)}=x_i\oplus x_j$. Si definimos una función de $f':{\cal P}[n]\to{\cal P}[n]$$f'(\varphi(X))=\varphi(f(X))$, se va a satisfacer los requisitos de la inducción (y un $g$ la satisfacción de los requisitos de $B$ $f'$ siempre existe), así que podemos aplicar la hipótesis de inducción a $B$, para encontrar que podemos reorganizar la secuencia de $$(\,((y_0\oplus y_1)\oplus y_2)\cdots\oplus y_{n-2})\oplus(x_i\oplus x_j)=((\,((y_0\oplus y_1)\oplus y_2)\cdots\oplus y_{n-2})\oplus x_i)\oplus x_j$$

por la asociatividad. Estamos a punto de terminar; sólo tenemos que poner $x_{n+1}$ al final en vez de $x_j$. Si $j=n+1$, grandes, de lo contrario, swap $x_{n+1}$ $x_i$ en la izquierda argumento (que es de longitud $n$ y por lo tanto puede ser reorganizado por hipótesis) y, a continuación, intercambiar $x_{n+1}$ $x_j$ por regular la asociatividad y conmutatividad. La izquierda argumento ahora es $\langle x_0,x_1,\dots,x_n\rangle$ en un poco de orden, por lo que se añade a algo único por hipótesis; por lo tanto $F(A)=F(A-\langle x_{n+1}\rangle)\oplus x_{n+1}$ es independiente de $f$ $g$ y por lo tanto es única.

Hay mi prueba; como se puede ver me cansé de la $f$ $g$ interpretación a mitad de camino a través de, pero esperamos que el lector atento puede completar los detalles. Por desgracia, que se supone que va a ser de mí, así que vamos a ver cómo la verdadera prueba va.