Operación binaria iterada

En matemáticas , una operación binaria iterada es una extensión de una operación binaria en un conjunto S a una función en secuencias finitas de elementos de S mediante aplicación repetida. ^{[ 1 ]} Ejemplos comunes incluyen la extensión de la operación de suma a la operación de suma y la extensión de la operación de multiplicación a la operación de producto . Otras operaciones, por ejemplo, las operaciones de teoría de conjuntos unión e intersección , también se iteran con frecuencia , pero las iteraciones no reciben nombres separados. En la imprenta, la suma y el producto se representan con símbolos especiales; pero otros operadores iterados a menudo se denotan con variantes más grandes del símbolo del operador binario ordinario. Por lo tanto, las iteraciones de las cuatro operaciones mencionadas anteriormente se denotan

${\displaystyle \sum ,\ \prod ,\ \bigcup ,}$y${\displaystyle \bigcap }$, respectivamente.

De forma más general, la iteración de una función binaria se suele denotar con una barra inclinada: iteración de${\displaystyle f}$sobre la secuencia${\displaystyle (a_{1},a_{2}\ldots ,a_{n})}$se denota por${\displaystyle f/(a_{1},a_{2}\ldots ,a_{n})}$, siguiendo la notación para reducir en el formalismo de Bird–Meertens .

En general, hay más de una forma de extender una operación binaria para que opere en secuencias finitas, dependiendo de si el operador es asociativo y de si el operador tiene elementos neutros .

Denotemos por a _{j , k} , con j ≥ 0 y k ≥ j , la secuencia finita de longitud k − j de elementos de S , con miembros ( a _i ), para j ≤ i < k . Nótese que si k = j , la secuencia está vacía.

Para f  : S × S → S , definimos una nueva función F _l sobre secuencias finitas no vacías de elementos de S , donde $${\displaystyle F_{l}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(F_{l}(\mathbf {a} _{0,k-1}),a_{k-1}),&k>1.\end{cases}}}$$

De manera similar, defina $${\displaystyle F_{r}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(a_{0},F_{r}(\mathbf {a} _{1,k})),&k>1.\end{cases}}}$$

Si f tiene un único elemento neutro izquierdo e , la definición de F _l puede modificarse para operar sobre secuencias vacías definiendo el valor de F _l en una secuencia vacía como e (el caso base anterior sobre secuencias de longitud 1 se vuelve redundante). De manera similar, F _r puede modificarse para operar sobre secuencias vacías si f tiene un único elemento neutro derecho.

Si f es asociativa, entonces F _l es igual a F _r , y podemos escribir simplemente F . Además, si existe un elemento identidad e , entonces es único (ver Monoide ).

Si f es conmutativa y asociativa, entonces F puede operar sobre cualquier multiconjunto finito no vacío aplicándola a una enumeración arbitraria del multiconjunto. Si además f tiene un elemento identidad e , este se define como el valor de F sobre un multiconjunto vacío. Si f es idempotente, entonces las definiciones anteriores pueden extenderse a conjuntos finitos .

Si S también está equipado con una métrica o, más generalmente, con una topología de Hausdorff , de modo que el concepto de límite de una sucesión se define en S , entonces una iteración infinita en una sucesión numerable en S se define exactamente cuando la sucesión correspondiente de iteraciones finitas converge. Así, por ejemplo, si a₀ , _a₁ , _a₂ , a₃ _, … es una sucesión infinita de números reales _, entonces el producto infinito  ${\textstyle \prod _{i=0}^{\infty }a_{i}}$está definido y es igual a${\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n}a_{i},}$si y solo si existe ese límite.

La operación binaria general no asociativa viene dada por un magma . El acto de iterar sobre una operación binaria no asociativa puede representarse como un árbol binario .

La operación binaria iterada se escribe como:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}}$

Significado de los símbolos:

Ejemplo:

${\displaystyle \mathop {\bigstar } _{k=1}^{4}a_{k}=\mathop {\bigstar } _{k=1}^{k=4}a_{k}=a_{1}\star a_{2}\star a_{3}\star a_{4}}$

Forma general:

${\displaystyle \mathop {\bigstar } _{k\in K}a_{k}}$

Forma restringida:

${\displaystyle \mathop {\bigstar } _{1\leq k\leq n \atop k\equiv 0{\pmod {2}}}a_{k}}$

Versión infinita:

${\displaystyle \mathop {\bigstar } _{k=1}^{\infty }a_{k}=\mathop {\bigstar } _{k=1}^{k\to \infty }a_{k}}$

Dejar${\displaystyle (S,\star )}$ser una estructura con operación asociativa${\displaystyle \star }$:

• Elemento único:

${\displaystyle \mathop {\bigstar } _{k=n}^{n}a_{k}=a_{n}}$

• Expansión:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star a_{2}\star \dots \star a_{n}}$

• Recursión:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\left(\mathop {\bigstar } _{k=1}^{n-1}a_{k}\right)\star a_{n}}$

• Recursión derecha:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star \left(\mathop {\bigstar } _{k=2}^{n}a_{k}\right)}$

• Terrible:

${\displaystyle \left(\mathop {\bigstar } _{k=1}^{m}a_{k}\right)\star \left(\mathop {\bigstar } _{k=m+1}^{n}a_{k}\right)=\mathop {\bigstar } _{k=1}^{n}a_{k}}$

• Invariancia de permutación:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\mathop {\bigstar } _{k=1}^{n}a_{\sigma (k)}}$

• Producto vacío (monoide):

${\displaystyle \mathop {\bigstar } _{k=1}^{0}a_{k}=e}$

• Idempotencia:

si${\displaystyle a\star a=a}$, entonces${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a}$

• Secuencia constante:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a\star \cdots \star a}$

Si${\displaystyle (S,\star ,e)}$Si es un monoide , entonces:

• Producto vacío = elemento de identidad
• Suma vacía = 0 (en monoides aritméticos)

En la programación funcional, las operaciones binarias iteradas corresponden a funciones de orden superior como fold o reduce .

• operación unaria
• función unaria
• Operación binaria
• Función binaria
• Operación ternaria

• Acción en masa
• Operación de prefijo paralelo. Archivado el 3 de junio de 2013 en Wayback Machine.
• Operaciones binarias iteradas de Nupl. Archivado el 3 de marzo de 2016 en Wayback Machine.