Idempotencia

Propiedad de operaciones

Botones de encendido / apagado del panel de control de la señal de destino de un tren . Presionar 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 ( Reino Unido : / ˌ ɪ d ɛ m ˈ p oʊ t ən s / , ^[1] EE. UU. : / ˈ aɪ d ə m -/ ) ^[2] es la propiedad de ciertas operaciones en matemáticas e informática mediante las cuales pueden ser Se aplica 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 de proyectores y operadores de cierre ) y de la programación funcional (en la que está relacionado con la propiedad de transparencia referencial ).

El término fue introducido por el matemático estadounidense Benjamin Peirce en 1870 ^{[3] [4]} en el contexto de elementos de álgebras que permanecen invariantes cuando se elevan a una potencia entera positiva, y literalmente significa "(la cualidad de tener) la misma potencia". de ídem + potencia (igual + potencia).

Definición

Un elemento de un conjunto equipado con un operador binario se dice que es idempotente si ^{[5] [6]} ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle \cdot }$ ${\displaystyle \cdot }$

${\displaystyle x\cdot x=x}$.

Se dice que la operación binaria es idempotente si ^{[7] [8]} ${\displaystyle \cdot }$

${\displaystyle x\cdot x=x}$para todos ${\displaystyle x\in S}$ .

Ejemplos

• En el monoide de los números naturales con multiplicación , sólo 0 y 1 son idempotentes. De hecho, y . ${\displaystyle (\mathbb {N} ,\times )}$ ${\displaystyle 0\times 0=0}$ ${\displaystyle 1\times 1=1}$
• En el monoide +) de los números naturales con suma , sólo 0 es idempotente. De hecho, 0 + 0 = 0 . ${\displaystyle (\mathbb {N} ,}$
• En un magma , un elemento identitario o un elemento absorbente , si existe, es idempotente. De hecho, y . ${\displaystyle (M,\cdot )}$ ${\displaystyle e}$ ${\displaystyle a}$ ${\displaystyle e\cdot e=e}$ ${\displaystyle a\cdot a=a}$
• En un grupo , el elemento identidad es el único elemento idempotente. De hecho, si es un elemento de tal que , entonces y finalmente multiplicando a la izquierda por el elemento inverso de . ${\displaystyle (G,\cdot )}$ ${\displaystyle e}$ ${\displaystyle x}$ ${\displaystyle G}$ ${\displaystyle x\cdot x=x}$ ${\displaystyle x\cdot x=x\cdot e}$ ${\displaystyle x=e}$ ${\displaystyle x}$
• En los monoides y en el conjunto potencia del conjunto con unión de conjuntos y intersección de conjuntos respectivamente, y son idempotentes. En efecto, para todos , y para todos . ${\displaystyle ({\mathcal {P}}(E),\cup )}$ ${\displaystyle ({\mathcal {P}}(E),\cap )}$ ${\displaystyle {\mathcal {P}}(E)}$ ${\displaystyle E}$ ${\displaystyle \cup }$ ${\displaystyle \cap }$ ${\displaystyle \cup }$ ${\displaystyle \cap }$ ${\displaystyle x\cup x=x}$ ${\displaystyle x\in {\mathcal {P}}(E)}$ ${\displaystyle x\cap x=x}$ ${\displaystyle x\in {\mathcal {P}}(E)}$
• En los monoides y del dominio booleano con disyunción lógica y conjunción lógica respectivamente, y son idempotentes. En efecto, para todos , y para todos . ${\displaystyle (\{0,1\},\vee )}$ ${\displaystyle (\{0,1\},\wedge )}$ ${\displaystyle \vee }$ ${\displaystyle \wedge }$ ${\displaystyle \vee }$ ${\displaystyle \wedge }$ ${\displaystyle x\vee x=x}$ ${\displaystyle x\in \{0,1\}}$ ${\displaystyle x\wedge x=x}$ ${\displaystyle x\in \{0,1\}}$
• En un dominio GCD (por ejemplo en ), las operaciones de GCD y LCM son idempotentes. ${\displaystyle \mathbb {Z} }$
• En un anillo booleano , la multiplicación es idempotente.
• En un semiring tropical , la suma es idempotente.
• En un anillo de matrices cuadráticas , el determinante de una matriz idempotente es 0 o 1. Si el determinante es 1, la matriz necesariamente es la matriz identidad . ^{[ cita necesaria ]}

Funciones idempotentes

En el monoide de las funciones de un conjunto a sí mismo (ver exponenciación de conjuntos ) con composición de funciones , los elementos idempotentes son las funciones tales que , ^[9] es decir tales que para todos (en otras palabras, la imagen de cada elemento es un fijo Punto de ). Por ejemplo: ${\displaystyle (E^{E},\circ )}$ ${\displaystyle E}$ ${\displaystyle \circ }$ ${\displaystyle f\colon E\to E}$ ${\displaystyle f\circ f=f}$ ${\displaystyle f(f(x))=f(x)}$ ${\displaystyle x\in E}$ ${\displaystyle f(x)}$ ${\displaystyle x\in E}$ ${\displaystyle f}$

• el valor absoluto es idempotente. En efecto, eso es para todos ; ${\displaystyle \operatorname {abs} \circ \operatorname {abs} =\operatorname {abs} }$ ${\displaystyle \operatorname {abs} (\operatorname {abs} (x))=\operatorname {abs} (x)}$ ${\displaystyle x}$
• las funciones constantes son idempotentes;
• la función de identidad es idempotente;
• las funciones suelo , techo y parte fraccionaria son idempotentes;
• la función parte real de un número complejo es idempotente. ${\displaystyle {\mathcal {Re}}(z)}$
• la función generada por el subgrupo a partir del conjunto potencia de un grupo sobre sí mismo es idempotente;
• la función de casco convexo del conjunto de potencias de un espacio afín sobre los reales a sí mismo es idempotente;
• las funciones de cierre e interiores del conjunto de potencias de un espacio topológico respecto de sí mismo son idempotentes;
• las funciones estrella Kleene y Kleene plus del conjunto de potencias de un monoide consigo mismo son idempotentes;
• los endomorfismos idempotentes de un espacio vectorial son sus proyecciones .

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

${\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 serlo se conservan bajo la composición de funciones. ^[10] Como ejemplo para el primero, mod 3 y ambos son idempotentes, pero no lo son, ^[11] aunque resulta que lo son. ^[12] Como ejemplo de esto último, la función de negación en el dominio booleano no es idempotente, pero lo es. De manera similar, la negación unaria de números reales no es idempotente, pero lo es. En ambos casos, la composición es simplemente la función identidad , que es idempotente. ${\displaystyle f(x)=x}$ ${\displaystyle g(x)=\max(x,5)}$ ${\displaystyle f\circ g}$ ${\displaystyle g\circ f}$ ${\displaystyle \neg }$ ${\displaystyle \neg \circ \neg }$ ${\displaystyle -(\cdot )}$ ${\displaystyle -(\cdot )\circ -(\cdot )}$

Significado de la informática

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 múltiples llamadas a la subrutina tienen el mismo efecto en el estado del sistema que una sola llamada, en otras palabras, si la función del espacio de estados del sistema asociada con la subrutina es idempotente en el sentido matemático dado en la 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 se puede repetir o reintentar tantas veces como sea necesario sin provocar efectos no deseados. Con operaciones no idempotentes, es posible que el algoritmo deba 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 hará que la base de datos cambie. De manera similar, una solicitud para 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 la solicitud. Sin embargo, la solicitud de un cliente para realizar un pedido no suele ser idempotente, ya que varias solicitudes darán lugar a que se realicen varios pedidos. Una solicitud de cancelación de un pedido en particular es idempotente porque no importa cuántas solicitudes se realicen, el pedido permanece cancelado.

Sin embargo, una secuencia de subrutinas idempotentes donde al menos una subrutina es diferente de las demás no es necesariamente idempotente si una subrutina posterior en la secuencia cambia un valor del que depende una subrutina anterior; la idempotencia no está cerrada bajo composición secuencial . Por ejemplo, supongamos que el valor inicial de una variable es 3 y hay una secuencia de subrutina que lee la variable, luego la cambia a 5 y luego la lee nuevamente. Cada paso de la secuencia es idempotente: ambos pasos que leen la variable no tienen efectos secundarios y el paso que cambia la 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 por segunda vez produce la salida (5, 5), por lo que la secuencia no es idempotente.

int x = 3 ; lectura vacía () { printf ( "%d \n " , x ); } cambio nulo () { x = 5 ; } secuencia vacía () { leer (); cambiar (); leer (); }                    int principal () { secuencia (); // imprime la secuencia "3\n5\n" (); // imprime "5\n5\n" devuelve 0 ; }        

En el Protocolo de transferencia de hipertexto (HTTP), la idempotencia y la seguridad son los atributos principales que separan los métodos HTTP . De los principales métodos HTTP, GET, PUT y DELETE deben implementarse de manera idempotente según el estándar, pero POST no es necesario. ^[13] GET recupera el estado de un recurso; PUT actualiza el estado de 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). Actualizar y eliminar datos determinados suele ser idempotente siempre que la solicitud identifique de forma única el recurso y solo ese recurso nuevamente en el futuro. PUT y DELETE con identificadores únicos se reducen al simple caso de asignación a una variable de un valor o del 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 difiere. ^[14]

La violación del requisito de identificación única durante el almacenamiento o la eliminación generalmente causa una violación de la idempotencia. Por ejemplo, almacenar o eliminar un conjunto determinado 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 diferentes resultados 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 de 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 carga y almacenamiento , las instrucciones que posiblemente podrían causar un error de página son idempotentes. Entonces, si ocurre un error en la página, el sistema operativo puede cargar la página desde el disco y luego simplemente volver a ejecutar la instrucción errónea. En un procesador donde dichas instrucciones no son idempotentes, abordar los errores de página es mucho más complejo. ^{[15] [16]}

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 para la impresora bonita. ^{[ cita necesaria ]}

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

Muchas operaciones que son idempotentes a menudo tienen formas de "reanudar" un proceso si se interrumpe, formas que finalizan mucho más rápido que comenzar 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 típico de paso de peatones es un ejemplo de un sistema idempotente.

Ejemplos aplicados que muchas personas podrían encontrar en su día a día incluyen botones de llamada de ascensor y botones de paso de peatones . ^[17] 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 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 bioordenado
• Operador de cierre
• Punto fijo (matemáticas)
• Idempotente de un código
• Análisis idempotente
• matriz idempotente
• Relación de idempotencia  : una generalización de la idempotencia a las relaciones binarias
• Idempotente (teoría del anillo)
• Involución (matemáticas)
• función iterada
• Lista de matrices
• nilpotente
• Función pura
• Transparencia referencial

Referencias

1. "idempotencia". Diccionario de inglés 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. Manuscrito original de una conferencia de 1870 ante la Academia Nacional de Ciencias (Washington, DC, EE. UU.): Peirce, Benjamin (1870) "Álgebra asociativa lineal" De las páginas 16-17: "Cuando una expresión que se eleva al cuadrado o a cualquier potencia superior desaparece, puede llamarse nilpotente , pero cuando se eleva a un cuadrado o a una potencia superior se da como resultado, puede llamarse idempotente .
   La ecuación que define las expresiones nilpotente e idempotente es, respectivamente, An ⁼ 0 y An ⁼ A; pero con referencia a expresiones idempotentes, siempre se supondrá que son de la forma An ⁼ A a menos que se indique claramente lo contrario."
   • Impreso: Peirce, Benjamín (1881). "Álgebra asociativa lineal". Revista Estadounidense de Matemáticas . 4 (1): 97–229. Ver pág. 104.
   • Reimpreso: Peirce, Benjamín (1882). Álgebra asociativa lineal (PDF) . Nueva York, Nueva York, Estados Unidos: D. Van Nostrand. pag. 8.
4. Polcino y Sehgal 2002, pág. 127.
5. 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 .
6. Doneddu, Alfred (1976). Polynômes et algèbre linéaire (en francés). París: Vuibert. pag. 180. Soit M un magma, noté multiplicativement. En nomme idempotent de M tout elemento a de M tel que a ² = a .
7. George Grätzer (2003). Teoría general de la red . Basilea: Birkhäuser.Aquí: Sección 1.2, p.5.
8. Garrett Birkhoff (1967). Teoría de la celosía . Publicaciones del Coloquio. vol. 25. Providencia: Enm. Matemáticas. Soc.. Aquí: Sección I.5, p.8.
9. Esta es una ecuación entre funciones. Dos funciones son iguales si sus dominios y rangos coinciden, y sus valores de salida coinciden en todo su dominio.
10. Si y conmutan bajo composición (es decir, si ) entonces la idempotencia de ambos y implica la de , ya que , usando la asociatividad de la composición. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f\circ g=g\circ f}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f\circ g}$ ${\displaystyle (f\circ g)\circ (f\circ g)=f\circ (g\circ f)\circ g=f\circ (f\circ g)\circ g=(f\circ f)\circ (g\circ g)=f\circ g}$
11. por ejemplo , pero ${\displaystyle f(g(7))=f(7)=1}$ ${\displaystyle f(g(1))=f(5)=2\neq 1}$
12. también muestra que la conmutación de y no es una condición necesaria para la preservación de la idempotencia ${\displaystyle f}$ ${\displaystyle g}$
13. IETF, Protocolo de transferencia de hipertexto (HTTP/1.1): semántica y contenido Archivado el 8 de junio de 2014 en Wayback Machine . Véase también Protocolo de transferencia de hipertexto .
14. "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 deseado, incluso si la solicitud original tuvo éxito, aunque la respuesta pueda diferir.
15. John Ousterhout . "Paginación por demanda".
16. Marc A. de Kruijf. "Construcción de compiladores de regiones idempotentes y aplicaciones en diseño arquitectónico". 2012. pág. 10.
17. "Información/instrucciones de la guía de especificaciones del ascensor de pasajeros con tracción engranada" (PDF) . Departamento de Trabajo de Carolina del Norte, Oficina de Ascensores . 2002. Archivado desde el original (PDF) el 23 de mayo de 2011.Por ejemplo, esta especificación de diseño incluye un algoritmo detallado para saber cuándo las cabinas de ascensor responderán a llamadas de servicio posteriores.

Otras lecturas

• "idempotente" en el Diccionario gratuito de informática en línea
• 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, señor  1150975
• Gunawardena, Jeremy (1998), "Una introducción a la idempotencia" (PDF) , en Gunawardena, Jeremy (ed.), Idempotencia. Basado en un taller, Bristol, Reino Unido, 3 al 7 de octubre de 1994 , Cambridge: Cambridge University Press , págs. 1 a 49, Zbl  0898.16032
• "Idempotente", 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, vol. 575, Dordrecht: Kluwer Academic Publishers, págs. xii+380, ISBN 978-1-4020-2690-4, señor  2106764
• Lam, TY (2001), Un primer curso sobre anillos no conmutativos , Textos de Graduado en Matemáticas, vol. 131 (2 ed.), Nueva York: Springer-Verlag, págs. 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, Benjamín. Álgebra asociativa lineal 1870.
• Polcino Milies, César; Sehgal, Sudarshan K. (2002), Introducción a los anillos de grupo, álgebras y aplicaciones, vol. 1, Kluwer Academic Publishers, págs. 127, ISBN 978-1-4020-0238-0, señor  1896125