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 a través de la aplicación repetida. ^[1] Los ejemplos comunes incluyen la extensión de la operación de adición 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 a menudo , pero las iteraciones no reciben nombres separados. En la impresión, la suma y el producto se representan mediante símbolos especiales; pero otros operadores iterados a menudo se denotan mediante variantes más grandes del símbolo para el operador binario ordinario. Por lo tanto, las iteraciones de las cuatro operaciones mencionadas anteriormente se denotan

${\displaystyle \suma ,\ \prod ,\ \bigcup ,}$y , respectivamente.${\estilo de visualización\bigcap}$

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

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

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 , defina una nueva función F _l en 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, definir $${\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 una identidad izquierda única e , la definición de F _l se puede modificar para operar en secuencias vacías definiendo el valor de F _l en una secuencia vacía como e (el caso base anterior en secuencias de longitud 1 se vuelve redundante). De manera similar, F _r se puede modificar para operar en secuencias vacías si f tiene una identidad derecha única.

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ándolo a una enumeración arbitraria del multiconjunto. Si f además tiene un elemento identidad e , entonces este se define como el valor de F en un multiconjunto vacío. Si f es idempotente, entonces las definiciones anteriores se pueden extender a conjuntos finitos .

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

La operación binaria general no asociativa se representa mediante un magma . El acto de iterar sobre una operación binaria no asociativa se puede representar mediante un árbol binario .

Las operaciones binarias iteradas se utilizan para representar una operación que se repetirá sobre un conjunto sujeto a ciertas restricciones. Normalmente, el límite inferior de una restricción se escribe debajo del símbolo y el límite superior sobre el símbolo, aunque también se pueden escribir como superíndices y subíndices en notación compacta. La interpolación se realiza sobre números enteros positivos desde el límite inferior hasta el superior, para producir el conjunto que se sustituirá en el índice (denotado a continuación como i  ) para las operaciones repetidas.

Las notaciones comunes incluyen las notaciones Sigma grande ( suma repetida ) y Pi grande ( producto repetido ).

$${\displaystyle \sum _{i=0}^{n-1}i=0+1+2+\puntos +(n-1)}$$ $${\displaystyle \prod _{i=0}^{n-1}i=0\times 1\times 2\times \puntos \times (n-1)}$$

Es posible especificar la pertenencia a un conjunto u otras restricciones lógicas en lugar de índices explícitos, para especificar implícitamente qué elementos de un conjunto se utilizarán:

$${\displaystyle \sum_{x\in S}x=x_{1}+x_{2}+x_{3}+\puntos +x_{n}}$$

Se pueden escribir múltiples condiciones ya sea unidas con un y lógico o por separado:

$${\displaystyle \sum _{(i\in 2\mathbb {N} )\wedge (i\leq n)}i=\sum _{\stackrel {i\in 2\mathbb {N} }{i\leq n}}i=0+2+4+\dots +n}$$

Con menos frecuencia, también se puede utilizar cualquier operador binario como o exclusivo ( )${\displaystyle \oplus}$ o unión de conjuntos ( ) . ${\displaystyle \taza}$^[2] Por ejemplo, si S es un conjunto de proposiciones lógicas :

$${\displaystyle \bigwedge _{p\in S}p=p_{1}\wedge p_{2}\wedge \dots \wedge p_{N}}$$

lo cual es verdadero si y solo si todos los elementos de S son verdaderos.

• Fracción continua
• Pliegue (función de orden superior)
• Producto infinito
• Serie infinita

• Acción masiva
• Operación de prefijo paralelo Archivado el 3 de junio de 2013 en Wayback Machine.
• Operaciones binarias iteradas de Nuprl