Operación binaria iterada

Aplicación repetida de una operación a una secuencia

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 \sum ,\ \prod ,\ \bigcup ,}$y , respectivamente. ${\displaystyle \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 . ${\displaystyle 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 .

Definición

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},}$

Operación binaria no asociativa

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 .

Notación

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+\dots +(n-1)}$$ $${\displaystyle \prod _{i=0}^{n-1}i=0\times 1\times 2\times \dots \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}+\dots +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 \cup }$^[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.

Véase también

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

Referencias

1. Saunders MacLane (1971). Categorías para el matemático en activo . Nueva York: Springer-Verlag. pág. 142. ISBN. 0387900357.
2. Weisstein, Eric W. "Unión". mathworld.wolfram.com . Wolfram Mathworld . Consultado el 30 de enero de 2018 .

Enlaces externos

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