Idempotencia

Propiedad de operaciones

Para conocer los conceptos de álgebra, consulte Idempotente (teoría del anillo) y Matriz idempotente .

Botones de encendido / apagado del panel de control de la señal de destino de un tren . Pulsar el botón On (verde) es una operación idempotente, ya que tiene el mismo efecto ya sea que se haga una o varias veces. Asimismo, presionar Off es idempotente.

Idempotencia ( UK : / ˌ ɪ d ɛ m p oʊ t ən s / , ^[1] de Estados Unidos : / ˌ aɪ d ə m - / ) ^[2] es la propiedad de ciertas operaciones en matemáticas y ciencia de la computación mediante el cual pueden ser aplicado varias veces sin cambiar el resultado más allá de la aplicación inicial. El concepto de idempotencia surge en varios lugares del álgebra abstracta (en particular, en la teoría deproyectores y operadores de cierre ) y programación funcional (en la que se conecta a la propiedad de transparencia referencial ).

El término fue introducido por Benjamin Peirce ^[3] en el contexto de elementos de álgebras que permanecen invariantes cuando se elevan a un poder entero positivo, y literalmente significa "(la cualidad de tener) el mismo poder", de idem + potencia (mismo + energía).

Definición

Se dice que un elemento x de un magma ( M , •) es idempotente si: ^{[4] [5]}

x • x = x .

Si todos los elementos son idempotentes con respecto a •, entonces • se llama idempotente. La fórmula ∀ x , x • x = x se llama ley de idempotencia para •. ^{[6] [7]}

Ejemplos

• El número natural 1 es un elemento idempotente con respecto a la multiplicación (ya que 1 × 1 = 1), y también lo es 0 (ya que 0 × 0 = 0), pero ningún otro número natural lo es (por ejemplo, 2 × 2 = 2 no se cumple ). Por esta última razón, la multiplicación de números naturales no es una operación idempotente. Más formalmente, en el monoide ( ℕ , ×), los elementos idempotentes son solo 0 y 1.
• En un magma ( M , •), un elemento de identidad e o un elemento absorbente a , si existe, es idempotente. De hecho, e • e = e y a • a = a .
• En un grupo ( G , •), el elemento de identidad e es el único elemento idempotente. De hecho, si x es un elemento de G tal que x • x = x , entonces x • x = x • e y finalmente x = e multiplicando a la izquierda por el elemento inverso de x .
• Tomando la intersección x ∩ y de dos conjuntos x y y es una operación idempotente, puesto que x ∩ x siempre es igual a x . Esto significa que la ley de idempotencia ∀ x , x ∩ x = x es verdadera. Del mismo modo, tomar la unión de dos conjuntos es una operación idempotente. Formalmente, en los monoides (𝒫 ( E ), ∪) y (𝒫 ( E ), ∩) del conjunto de potencias del conjunto E con la unión del conjunto ∪ y la intersección del conjunto∩ respectivamente, todos los elementos son idempotentes; por tanto, ∪ y ∩ son operaciones idempotentes en 𝒫 ( E ).
• En los monoides ({0, 1}, ∨) y ({0, 1}, ∧) del dominio booleano con la disyunción lógica ∨ y la conjunción lógica ∧ respectivamente, todos los elementos son idempotentes.
• En un anillo booleano , la multiplicación es idempotente.
• En un semirrígido tropical , la adición es idempotente.

Funciones idempotentes

En el monoide ( E ^E , ∘) de las funciones de un conjunto E a sí mismo con la composición de funciones ∘, los elementos idempotentes son las funciones f : E → E tales que f ∘ f = f , es decir, tales que para todo x en E , f ( f ( x )) = f ( x ) (la imagen de cada elemento en E es un punto fijo de f ). Por ejemplo:

• Tomar el valor absoluto abs ( x ) ^[8] de un número entero x es una función idempotente por la siguiente razón: abs ( abs ( x )) = abs ( x ) es verdadero para cada número entero x . ^[9] Esto significa que abs ∘ abs = abs ^{[10] se} cumple, es decir, abs es un elemento idempotente en el conjunto de todas las funciones (de enteros a enteros) ^[11] con respecto a la composición de funciones. Por lo tanto, abdominales satisface la definición anterior de función idempotente.

Otros ejemplos incluyen:

• la función de identidad es idempotente;
• las funciones constantes son idempotentes;
• las funciones de suelo , techo y parte fraccionaria son idempotentes;
• la función generada por el subgrupo a partir del conjunto de poder de un grupo hacia sí mismo es idempotente;
• la función de casco convexo del conjunto de poder de un espacio afín sobre los reales a sí mismo es idempotente;
• las funciones de cierre e interior del conjunto de poder de un espacio topológico a sí mismo son idempotentes;
• los Kleene estrella y Kleene más funciones del conjunto potencia de un monoide a sí mismo son idempotente;
• los endomorfismos idempotentes de un espacio vectorial son sus proyecciones .

Si el conjunto E tiene n elementos, podemos dividirlo en k puntos fijos elegidos y n - k puntos no fijos bajo f , y entonces k ^{n - k} es el número de funciones idempotentes diferentes. Por lo tanto, teniendo en cuenta todas las particiones posibles,

${\displaystyle \sum _{k=0}^{n}{n \choose k}k^{n-k}}$

es el número total de posibles funciones idempotentes en el conjunto. La secuencia entera del número de funciones idempotentes dada por la suma anterior para n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... comienza con 1, 1, 3, 10, 41, 196 , 1057, 6322, 41393,… (secuencia A000248 en la OEIS ).

Ni la propiedad de ser idempotente ni la de no ser se conserva en la composición de funciones. ^[12] Como ejemplo para el primero, f ( x ) = x mod 3 y g ( x ) = max ( x , 5) son ambos idempotentes, pero f ∘ g no lo es, ^[13] aunque g ∘ f pasa a ser. ^[14] Como ejemplo de este último, la función de negación ¬ en el dominio booleano no es idempotente, pero ¬ ∘ ¬ sí lo es. De manera similar, la negación unaria - () de los números reales no es idempotente, sino - () ∘ - () es.

Significado de la informática

Consulte también: Transparencia referencial , Reentrante (subrutina) y Clasificación estable

En informática , el término idempotencia puede tener un significado diferente según el contexto en el que se aplique:

• En programación imperativa , una subrutina con efectos secundarios es idempotente si el estado del sistema permanece igual después de una o varias llamadas, es decir, si la función del espacio de estados del sistema a sí mismo asociada a la subrutina es idempotente en el sentido matemático dado en el definición ;
• en programación funcional , una función pura es idempotente si es idempotente en el sentido matemático dado en la definición .

Esta es una propiedad muy útil en muchas situaciones, ya que significa que una operación puede repetirse o reintentarse tantas veces como sea necesario sin causar efectos no deseados. Con operaciones no idempotentes, el algoritmo puede tener que realizar un seguimiento de si la operación ya se realizó o no.

Ejemplos de informática

Una función que busca el nombre y la dirección de un cliente en una base de datos suele ser idempotente, ya que esto no provocará que la base de datos cambie. De manera similar, cambiar la dirección de un cliente a XYZ suele ser idempotente, porque la dirección final será la misma sin importar cuántas veces se envíe XYZ. Sin embargo, realizar un pedido de un carrito para el cliente no suele ser idempotente, ya que ejecutar la llamada varias veces dará lugar a que se realicen varios pedidos. Cancelar un pedido es idempotente, porque el pedido permanece cancelado sin importar cuántas solicitudes se realicen.

Sin embargo, una composición de métodos o subrutinas idempotentes no es necesariamente idempotente si un método posterior en la secuencia cambia un valor del que depende un método anterior: la idempotencia no está cerrada bajo composición . Por ejemplo, suponga que el valor inicial de una variable es 3 y hay una secuencia que lee la variable, luego la cambia a 5 y luego la vuelve a leer. Cada paso de la secuencia es idempotente: ambos pasos que leen la variable no tienen efectos secundarios y cambiar una variable a 5 siempre tendrá el mismo efecto sin importar cuántas veces se ejecute. No obstante, ejecutar la secuencia completa una vez produce la salida (3, 5), pero ejecutarla una segunda vez produce la salida (5, 5), por lo que la secuencia no es idempotente.

En el Protocolo de transferencia de hipertexto (HTTP), la idempotencia y la seguridad son los principales atributos que separan los verbos HTTP . De los principales verbos HTTP, GET, PUT y DELETE deben implementarse de manera idempotente de acuerdo con el estándar, pero POST no tiene por qué serlo. ^[15] GET recupera un recurso; PUT almacena contenido en un recurso; y DELETE elimina un recurso. Como en el ejemplo anterior, la lectura de datos generalmente no tiene efectos secundarios, por lo que es idempotente (de hecho, nulipotente). El almacenamiento y la eliminación de un determinado conjunto de contenido suelen ser idempotentes siempre que la solicitud especifique una ubicación o identificador que identifique de manera única ese recurso y solo ese recurso nuevamente en el futuro. Las operaciones PUT y DELETE con identificadores únicos se reducen al simple caso de asignación a una variable inmutable de un valor o el valor nulo, respectivamente, y son idempotentes por la misma razón; el resultado final es siempre el mismo que el resultado de la ejecución inicial, incluso si la respuesta es diferente. ^[dieciséis]

La violación del requisito de identificación única en el almacenamiento o la eliminación generalmente causa una violación de la idempotencia. Por ejemplo, almacenar o eliminar un determinado conjunto de contenido sin especificar un identificador único: las solicitudes POST, que no necesitan ser idempotentes, a menudo no contienen identificadores únicos, por lo que la creación del identificador se delega al sistema receptor que luego crea un nuevo registro correspondiente. De manera similar, las solicitudes PUT y DELETE con criterios no específicos pueden generar resultados diferentes según el estado del sistema, por ejemplo, una solicitud para eliminar el registro más reciente. En cada caso, las ejecuciones posteriores modificarán aún más el estado del sistema, por lo que no son idempotentes.

En el procesamiento del flujo de eventos , la idempotencia se refiere a la capacidad de un sistema para producir el mismo resultado, incluso si el mismo archivo, evento o mensaje se recibe más de una vez.

En una arquitectura de almacenamiento de carga , las instrucciones que pueden causar un error de página son idempotentes. Entonces, si ocurre una falla de página, el sistema operativo puede cargar la página desde el disco y luego simplemente volver a ejecutar la instrucción fallada. En un procesador donde tales instrucciones no son idempotentes, lidiar con fallas de página es mucho más complejo. ^{[17] [18]}

Al reformatear la salida, se espera que la impresión bonita sea ​​idempotente. En otras palabras, si la salida ya es "bonita", no debería haber nada que hacer por la impresora bonita. ^{[ cita requerida ]}

En la arquitectura orientada a servicios (SOA), un proceso de orquestación de varios pasos compuesto completamente por pasos idempotentes se puede reproducir sin efectos secundarios si falla alguna parte de ese proceso.

Muchas operaciones que son idempotentes a menudo tienen formas de "reanudar" un proceso si se interrumpe, formas que terminan mucho más rápido que empezar desde el principio. Por ejemplo, reanudar una transferencia de archivos , sincronizar archivos , crear una compilación de software , instalar una aplicación y todas sus dependencias con un administrador de paquetes , etc.

Ejemplos aplicados

Un botón de paso de peatones típico es un ejemplo de un sistema idempotente

Los ejemplos aplicados que muchas personas podrían encontrar en su vida cotidiana incluyen botones de llamada de ascensor y botones de paso de peatones . ^[19] La activación inicial del botón mueve el sistema a un estado de solicitud, hasta que se satisface la solicitud. Las activaciones posteriores del botón entre la activación inicial y la satisfacción de la solicitud no tienen ningún efecto, a menos que el sistema esté diseñado para ajustar el tiempo para satisfacer la solicitud en función del número de activaciones.

Ver también

• Conjunto biordado
• Operador de cierre
• Punto fijo (matemáticas)
• Idempotente de un código
• Análisis idempotente
• Matriz idempotente
• Relación idempotente : una generalización de la idempotencia a las relaciones binarias
• Involución (matemáticas)
• Función iterada
• Lista de matrices
• Nilpotente
• Función pura
• Transparencia referencial

Referencias

1. "idempotencia" . Diccionario de inglés de Oxford (3ª ed.). Prensa de la Universidad de Oxford. 2010.
2. "idempotente" . Merriam-Webster . Archivado desde el original el 19 de octubre de 2016.
3. Polcino y Sehgal (2002), p. 127.
4. Valenza, Robert (2012). Álgebra lineal: una introducción a las matemáticas abstractas . Berlín: Springer Science & Business Media. pag. 22. ISBN 9781461209010. Un elemento s de un magma tal que ss = s se llama idempotente .
5. Doneddu, Alfred (1976). Polynômes et algèbre linéaire (en francés). París: Vuibert. pag. 180. Soit M un magma, noté multiplicativement. Sobre nomme idempotent de M tout élément a de M tel que a ² = a .
6. George Grätzer (2003). Teoría general de la celosía . Basilea: Birkhäuser. Aquí: Sección 1.2, p.5.
7. Garrett Birkhoff (1967). Teoría de celosía . Publicaciones del coloquio. 25 . Providencia: Am. Matemáticas. Soc.. Aquí: Sección I.5, p.8.
8. Una notación más común para esto es, pero es más difícil de leer cuando las expresiones están anidadas.${\displaystyle |x|}$
9. De hecho, esta ecuación también es válida para todos los números racionales , reales e incluso complejos .
10. Esta es una ecuación entre funciones. Dos funciones son iguales si sus dominios y rangos concuerdan, y sus valores de salida concuerdan en todo su dominio.
11. Este conjunto de funciones se denota formalmente como ℤ ^ℤ .
12. Si f y g conmutan, es decir, si f ∘ g = g ∘ f , entonces la idempotencia de f y g implica la de f ∘ g , ya que ( f ∘ g ) ∘ ( f ∘ g ) = ( f ∘ f ) ∘ ( g ∘ g ) = f ∘ g , usando la asociatividad de composición.
13. por ejemplo, f ( g (7)) = f (7) = 1, pero f ( g (1)) = f (5) = 2 ≠ 1
14. también muestra que la conmutación de f y g no es una condición necesaria para la preservación de la idempotencia
15. IETF, Protocolo de transferencia de hipertexto (HTTP / 1.1): semántica y contenido archivado el 8 de junio de 2014 en Wayback Machine . Consulte también Protocolo de transferencia de hipertexto .
16. "Métodos idempotentes" . Protocolo de transferencia de hipertexto (HTTP / 1.1): Semántica y contenido . segundo. 4.2.2. doi : 10.17487 / RFC7231 . RFC 7231 . Sabe que repetir la solicitud tendrá el mismo efecto previsto, incluso si la solicitud original tuvo éxito, aunque la respuesta puede diferir.
17. John Ousterhout ."Búsqueda de demanda" .
18. Marc A. de Kruijf. "Construcción de compiladores de regiones idempotentes y aplicaciones en el diseño de arquitectura" . 2012. p. 10.
19. https://web.archive.org/web/20110523081716/http://www.nclabor.com/elevator/geartrac.pdf Por ejemplo, esta especificación de diseño incluye un algoritmo detallado sobre cuándo las cabinas de ascensor responderán a las siguientes llamadas de servicio

Lectura adicional

Busque idempotencia en Wikcionario, el diccionario libre.

Wikilibros tiene más sobre el tema: Idempotencia

Wikiversity tiene recursos de aprendizaje sobre Portal: Ciencias de la Computación

• " Idempotente " en FOLDOC
• Goodearl, KR (1991), anillos regulares de von Neumann (2 ed.), Malabar, FL: Robert E. Krieger Publishing Co. Inc., págs. Xviii + 412, ISBN 978-0-89464-632-4, MR  1150975
• Gunawardena, Jeremy (1998), "Una introducción a la idempotencia" (PDF) , en Gunawardena, Jeremy (ed.), Idempotency. Basado en un taller, Bristol, Reino Unido, 3 al 7 de octubre de 1994 , Cambridge: Cambridge University Press , págs. 1-49, Zbl  0898.16032
• "Idempotent" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Hazewinkel, Michiel ; Gubareni, Nadiya; Kirichenko, VV (2004), Álgebras, anillos y módulos. vol. 1 , Matemáticas y sus aplicaciones, 575 , Dordrecht: Kluwer Academic Publishers, págs. Xii + 380, ISBN 978-1-4020-2690-4, MR  2106764
• Lam, TY (2001), A first course in non conmutative rings , Graduate Texts in Mathematics, 131 (2 ed.), Nueva York: Springer-Verlag, pp. Xx + 385, doi : 10.1007 / 978-1-4419-8616 -0 , ISBN 978-0-387-95183-6, Señor  1838439
• Lang, Serge (1993), Álgebra (Tercera ed.), Reading, Mass .: Addison-Wesley, ISBN 978-0-201-55540-0, Zbl  0848.13001pag. 443
• Peirce, Benjamin. Álgebra asociativa lineal 1870.
• Polcino Milies, César; Sehgal, Sudarshan K. (2002), Introducción a los anillos de grupo , Álgebras y aplicaciones, 1 , Dordrecht: Kluwer Academic Publishers, págs. Xii + 371, doi : 10.1007 / 978-94-010-0405-3 , ISBN 978-1-4020-0238-0, Señor  1896125