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] Los ejemplos comunes incluyen la extensión de la adición operación a la suma operación, y la extensión de la multiplicación operación para el producto operación. Otras operaciones, por ejemplo, la unión e intersección de operaciones teóricas de conjuntos , también se repiten a menudo., pero las iteraciones no reciben nombres separados. En forma impresa, la suma y el producto están representados por símbolos especiales; pero otros operadores iterados a menudo se indican 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
- y , respectivamente.
De manera más general, la iteración de una función binaria se denota generalmente con una barra oblicua: iteración de sobre la secuencia se denota por , siguiendo la notación para reducir en el formalismo Bird-Meertens .
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 de identidad .
Definición
Denote 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 . Tenga en cuenta 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
Del mismo modo, defina
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 puede modificarse para operar en secuencias vacías si f tiene una identidad correcta única.
Si f es asociativa, entonces M l es igual a F r , y simplemente puede escribir F . Además, si existe un elemento de identidad e , entonces es único (ver Monoide ).
Si f es conmutativa y asociativa, entonces F puede operar en cualquier multiset finito no vacío aplicándolo a una enumeración arbitraria del multiset. Si f tiene además un elemento de identidad e , entonces este se define como el valor de F en un multiset 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 que es Hausdorff , de modo que el concepto de límite de una secuencia se define en S , entonces una iteración infinita en una secuencia contable en S se define exactamente cuando la secuencia correspondiente de las iteraciones finitas convergen. Así, por ejemplo, si un 0 , un 1 , un 2 , un 3 , ... es una secuencia infinita de números reales , entonces el producto infinito está definido, y es igual a si y solo si ese límite existe.
Operación binaria no asociativa
La operación binaria general no asociativa viene dada por un magma . El acto de iterar en una operación binaria no asociativa puede representarse como un árbol binario .
Notación
Las operaciones binarias iteradas se utilizan para representar una operación que se repetirá en un conjunto sujeto a algunas 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 pueden escribirse 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 al superior, para producir el conjunto que se sustituirá en el índice (a continuación, indicado como i ) para las operaciones repetidas. Es posible especificar la pertenencia al conjunto u otras restricciones lógicas en lugar de índices explícitos, para especificar implícitamente qué elementos de un conjunto se utilizarán.
Notaciones comunes incluyen la gran S IGMA ( repetido s um ) y grande P i ( repetido p roduct ) notaciones.
Aunque se pueden usar operadores binarios que incluyen , entre otros, exclusivo o y unión de conjuntos . [2]
Sea S un conjunto de conjuntos
Sea S un conjunto de proposiciones lógicas
[ aclaración necesaria ]
Sea S un conjunto de multivectores en un álgebra de Clifford / álgebra geométrica
Nótese cómo en lo anterior, no se usa límite superior, porque es suficiente para expresar que los elementos son elementos del conjunto S .
También es producir una operación repetida dada una serie de restricciones unidas por una conjunción (y) , por ejemplo:
que también se puede denotar
Ver también
Referencias
enlaces externos
- Acción masiva
- Operación de prefijo paralelo
- Operaciones binarias iteradas Nuprl