Hispanopedia Wiki
Articulo de referencia

Invariante (matemáticas)

Un papel pintado es invariante ante ciertas transformaciones. Este en particular es invariante ante traslaciones horizontales y verticales, así como ante rotaciones de 180° (per...

Hispanopedia WikiContenido en espanolLectura gratuita
Un papel pintado es invariante ante ciertas transformaciones. Este en particular es invariante ante traslaciones horizontales y verticales, así como ante rotaciones de 180° (pero no ante reflexiones).

En matemáticas , un invariante es una propiedad de un objeto matemático (o una clase de objetos matemáticos) que permanece inalterada después de aplicarle operaciones o transformaciones de cierto tipo. [ 1 ] [ 2 ] La clase particular de objetos y el tipo de transformaciones suelen indicarse en el contexto en el que se utiliza el término. Por ejemplo, el área de un triángulo es un invariante con respecto a las isometrías del plano euclidiano . Se utilizan las expresiones «invariante bajo» e «invariante a» una transformación. De forma más general, un invariante con respecto a una relación de equivalencia es una propiedad que es constante en cada clase de equivalencia . [ 3 ]

Los invariantes se utilizan en diversas áreas de las matemáticas, como la geometría , la topología , el álgebra y las matemáticas discretas . Algunas clases importantes de transformaciones se definen mediante un invariante que dejan inalteradas. Por ejemplo, las transformaciones conformes se definen como transformaciones del plano que preservan los ángulos . El descubrimiento de invariantes es un paso importante en el proceso de clasificación de objetos matemáticos. [ 2 ] [ 3 ]

Ejemplos

Un ejemplo sencillo de invariancia se manifiesta en nuestra capacidad de contar . Para un conjunto finito de objetos de cualquier tipo, siempre obtenemos un número, independientemente del orden en que contemos los objetos . Esta cantidad —un número cardinal— está asociada al conjunto y permanece invariable durante el proceso de conteo.

Una identidad es una ecuación que permanece verdadera para todos los valores de sus variables. También existen desigualdades que permanecen verdaderas cuando cambian los valores de sus variables.

La distancia entre dos puntos en una recta numérica no cambia al sumar la misma cantidad a ambos números. En cambio, la multiplicación no posee esta misma propiedad, ya que la distancia no es invariante bajo la multiplicación.

Los ángulos y las razones de distancias son invariantes ante escalamientos , rotaciones , traslaciones y reflexiones . Estas transformaciones producen figuras semejantes , que constituyen la base de la trigonometría . En cambio, los ángulos y las razones no son invariantes ante escalamientos no uniformes (como el estiramiento). La suma de los ángulos interiores de un triángulo (180°) es invariante ante todas las operaciones anteriores. Como otro ejemplo, todos los círculos son semejantes: pueden transformarse entre sí, y la razón entre la circunferencia y el diámetro es invariante (denotada por la letra griega π ( pi )).

Algunos ejemplos más complejos:

Rompecabezas MU

El rompecabezas MU [ 7 ] es un buen ejemplo de un problema lógico donde determinar un invariante es útil para una prueba de imposibilidad . El rompecabezas pide que se comience con la palabra MI y se transforme en la palabra MU, utilizando en cada paso una de las siguientes reglas de transformación:

  1. Si una cadena termina con una I, se le puede añadir una U ( x I → x IU)
  2. La cadena que sigue a la M puede duplicarse completamente (M x → M xx ).
  3. Cualquier tres I consecutivas (III) pueden ser reemplazadas por una sola U ( x III y → x U y )
  4. Se pueden eliminar dos U consecutivas cualesquiera ( x UU y → xy )

Un ejemplo de derivación (con superíndices que indican las reglas aplicadas) es

MI → 2 MII → 2 MIIII → 3 MUI → 2 MUIUI → 1 MUIUIU → 2 MUIUIUUIUIU → 4 MUIUIIUIU → ...

En vista de esto, cabe preguntarse si es posible convertir MI en MU utilizando únicamente estas cuatro reglas de transformación. Se podrían dedicar muchas horas a aplicar estas reglas a cadenas de caracteres. Sin embargo, podría ser más rápido encontrar una propiedad invariante a todas las reglas (es decir, que no se vea alterada por ninguna de ellas) y que demuestre que llegar a MU es imposible. Desde un punto de vista lógico, se puede observar que la única forma de eliminar cualquier I es tener tres I consecutivas en la cadena. Esto hace que el siguiente invariante resulte interesante:

El número de 'I's' en la cadena no es un múltiplo de 3 .

Esto constituye una invariante del problema, si para cada una de las reglas de transformación se cumple lo siguiente: si la invariante se cumplía antes de aplicar la regla, también se cumplirá después de aplicarla. Al observar el efecto neto de aplicar las reglas sobre el número de I y U, se puede ver que esto se cumple para todas las reglas:

La tabla anterior muestra claramente que la invariante se cumple para cada una de las posibles reglas de transformación, lo que significa que, sea cual sea la regla que se elija, en cualquier estado, si el número de I no era un múltiplo de tres antes de aplicar la regla, tampoco lo será después.

Dado que hay una sola I en la cadena inicial MI, y uno no es múltiplo de tres, se puede concluir que es imposible pasar de MI a MU (ya que el número de I nunca será múltiplo de tres).

Conjunto invariante

Un subconjunto S del dominio U de una aplicación T : U → U es un conjunto invariante bajo la aplicación cuandoincógnita∈S⟺T(incógnita)∈S.{\displaystyle x\in S\iff T(x)\in S.}Los elementos de S no son necesariamente fijos , aunque el conjunto S sea fijo en el conjunto potencia de U. (Algunos autores utilizan la terminología invariante por conjuntos, [ 8 ] frente a invariante puntual, [ 9 ] para distinguir entre estos casos). Por ejemplo, un círculo es un subconjunto invariante del plano bajo una rotación alrededor de su centro. Además, una superficie cónica es invariante como conjunto bajo una homotecia del espacio.

Un conjunto invariante de una operación T también se denomina estable bajo T. Por ejemplo, los subgrupos normales que son tan importantes en la teoría de grupos son aquellos subgrupos que son estables bajo los automorfismos internos del grupo ambiente . [ 10 ] [ 11 ] [ 12 ] En álgebra lineal , si una transformación lineal T tiene un vector propio v , entonces la recta que pasa por 0 y v es un conjunto invariante bajo T , en cuyo caso los vectores propios generan un subespacio invariante que es estable bajo T.

Cuando T es un desplazamiento del tornillo , el eje del tornillo es una línea invariante, aunque si el paso no es cero, T no tiene puntos fijos.

En teoría de la probabilidad y teoría ergódica , los conjuntos invariantes se definen generalmente mediante la propiedad más fuerte.incógnita∈S⇔T(incógnita)∈S.{\displaystyle x\in S\Leftrightarrow T(x)\in S.}[ 13 ] [ 14 ] [ 15 ] Cuando el mapaT{\displaystyle T}es medible, los conjuntos invariantes forman un sigma-álgebra , el sigma-álgebra invariante .

Declaración formal

En matemáticas, la noción de invariancia se formaliza de tres maneras diferentes: mediante acciones de grupo , presentaciones y deformación.

Sin cambios en la acción colectiva

En primer lugar, si se tiene un grupo G que actúa sobre un objeto matemático (o conjunto de objetos) X, entonces uno puede preguntarse qué puntos x permanecen inalterados, "invariantes" bajo la acción del grupo, o bajo un elemento g del grupo.

Con frecuencia, se tiene un grupo que actúa sobre un conjunto X , lo que lleva a determinar qué objetos de un conjunto asociado F ( X ) permanecen invariantes. Por ejemplo, una rotación en el plano alrededor de un punto deja invariante el punto sobre el cual gira, mientras que una traslación en el plano no deja ningún punto invariante, pero sí deja invariantes como líneas todas las líneas paralelas a la dirección de la traslación. Formalmente, definimos el conjunto de líneas en el plano P como L ( P ); entonces, un movimiento rígido del plano transforma líneas en líneas —el grupo de movimientos rígidos actúa sobre el conjunto de líneas— y uno puede preguntarse qué líneas permanecen inalteradas por una acción.

Más importante aún, se puede definir una función en un conjunto, como por ejemplo "radio de un círculo en el plano", y luego preguntarse si esta función es invariante bajo una acción de grupo, como por ejemplo movimientos rígidos.

Duales a la noción de invariantes son las coinvariantes , también conocidas como órbitas, que formalizan la noción de congruencia : objetos que pueden unirse mediante una acción de grupo. Por ejemplo, bajo el grupo de movimientos rígidos del plano, el perímetro de un triángulo es un invariante, mientras que el conjunto de triángulos congruentes a un triángulo dado es una coinvariante.

Estos conceptos se relacionan de la siguiente manera: los invariantes son constantes en los coinvariantes (por ejemplo, los triángulos congruentes tienen el mismo perímetro), mientras que dos objetos que coinciden en el valor de un invariante pueden o no ser congruentes (por ejemplo, dos triángulos con el mismo perímetro no necesariamente son congruentes). En problemas de clasificación , se podría buscar un conjunto completo de invariantes , de modo que si dos objetos tienen los mismos valores para este conjunto de invariantes, entonces son congruentes.

Por ejemplo, los triángulos cuyos tres lados son iguales son congruentes bajo movimientos rígidos, según el criterio de congruencia LLL (lado-lado-lado) , y por lo tanto, las longitudes de los tres lados forman un conjunto completo de invariantes para triángulos. Las medidas de los tres ángulos de un triángulo también son invariantes bajo movimientos rígidos, pero no forman un conjunto completo, ya que triángulos incongruentes pueden tener las mismas medidas angulares. Sin embargo, si se permite el escalado además de los movimientos rígidos, el criterio de semejanza AAA demuestra que se trata de un conjunto completo de invariantes.

Independientemente de la presentación

En segundo lugar, una función puede definirse en términos de alguna presentación o descomposición de un objeto matemático; por ejemplo, la característica de Euler de un complejo celular se define como la suma alternada del número de celdas en cada dimensión. Se puede obviar la estructura del complejo celular y considerar únicamente el espacio topológico subyacente (la variedad ); dado que diferentes complejos celulares dan lugar a la misma variedad subyacente, cabe preguntarse si la función es independiente de la presentación elegida , en cuyo caso se trata de un invariante intrínsecamente definido. Este es el caso de la característica de Euler, y un método general para definir y calcular invariantes consiste en definirlos para una presentación dada y luego demostrar que son independientes de la presentación elegida. Cabe señalar que no existe la noción de acción de grupo en este sentido.

Los ejemplos más comunes son:

Sin cambios ante perturbaciones

En tercer lugar, si se estudia un objeto que varía en una familia, como es común en la geometría algebraica y la geometría diferencial , uno puede preguntarse si la propiedad permanece inalterada ante una perturbación (por ejemplo, si un objeto es constante en familias o invariante ante un cambio de métrica).

Invariantes en informática

En informática , un invariante es una afirmación lógica que siempre se considera verdadera durante una fase determinada de la ejecución de un programa informático . Por ejemplo, un invariante de bucle es una condición que se cumple al principio y al final de cada iteración del bucle.

Los invariantes son especialmente útiles al razonar sobre la corrección de un programa informático . La teoría de los compiladores optimizadores , la metodología de diseño por contrato y los métodos formales para determinar la corrección de un programa dependen en gran medida de los invariantes.

Los programadores suelen usar aserciones en su código para hacer explícitos los invariantes. Algunos lenguajes de programación orientados a objetos tienen una sintaxis especial para especificar invariantes de clase .

Detección automática de invariantes en programas imperativos

Las herramientas de interpretación abstracta pueden calcular invariantes simples de programas informáticos imperativos dados. Los tipos de propiedades que se pueden encontrar dependen de los dominios abstractos utilizados. Ejemplos típicos de propiedades son rangos de variables enteras individuales como 0<=x<1024, relaciones entre varias variables como 0<=i-j<2*n-1, e información de módulo como y%4==0. Los prototipos de investigación académica también consideran propiedades simples de estructuras de punteros. [ 16 ]

Los invariantes más sofisticados generalmente deben proporcionarse manualmente. En particular, al verificar un programa imperativo usando la lógica de Hoare , [ 17 ] se debe proporcionar manualmente un invariante de bucle para cada bucle en el programa, lo cual es una de las razones por las que este enfoque generalmente no es práctico para la mayoría de los programas.

En el contexto del ejemplo del rompecabezas MU anterior , actualmente no existe ninguna herramienta automatizada general que pueda detectar que es imposible derivar de MI a MU utilizando únicamente las reglas 1 a 4. Sin embargo, una vez realizada manualmente la abstracción de la cadena al número de sus "I", lo que lleva, por ejemplo, al siguiente programa en C, una herramienta de interpretación abstracta podrá detectar que ICount%3no puede ser 0 y, por lo tanto, el bucle "while" nunca terminará.

void MUPuzzle ( void ) { volatile int RandomRule ; int ICount = 1 , UCount = 0 ; while ( ICount % 3 != 0 ) // bucle no terminante switch ( RandomRule ) { case 1 : UCount += 1 ; break ; case 2 : ICount *= 2 ; UCount *= 2 ; break ; case 3 : ICount -= 3 ; UCount += 1 ; break ; case 4 : UCount -= 2 ; break ; } // invariante calculado: ICount % 3 == 1 || ICount % 3 == 2 }

Véase también

Notas

  1. ↑ "Definición de invariante (Diccionario de matemáticas ilustrado)" . www.mathsisfun.com . Consultado el 5 de diciembre de 2019 .
  2. 1 2 Weisstein, Eric W. "Invariante" . mathworld.wolfram.com . Consultado el 5 de diciembre de 2019 .
  3. 1 2 "Invariante – Enciclopedia de Matemáticas" . www.encyclopediaofmath.org . Consultado el 5 de diciembre de 2019 .
  4. ↑ Qiao, Xiaoyu (20 de enero de 2015). "Tricolorability.pdf" (PDF) . Semana 2 de la teoría de nudos: Tricolorability . Archivado del original (PDF) el 25 de mayo de 2024. Recuperado el 25 de mayo de 2024 .
  5. ^ Fraleigh (1976 , págs. 166-167) 
  6. ↑ Kay (1969 , págs. 219) 
  7. ↑ Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: Una eterna trenza dorada , Basic Books, ISBN 0-465-02656-7 Aquí: Capítulo I.
  8. ↑ Barry Simon. Representaciones de grupos finitos y compactos . American Mathematical Soc. pág. 16. ISBN  978-0-8218-7196-6.
  9. ↑ Judith Cederberg (1989). Un curso de geometría moderna . Springer. pág . 174. ISBN  978-1-4757-3831-5.
  10. ↑ Fraleigh (1976 , pág. 103) 
  11. ↑ Herstein (1964 , p. 42) 
  12. ↑ McCoy (1968 , pág. 183) 
  13. ↑ Billingsley (1995) , págs. 313–314 
  14. ^ Douc y otros. (2018) , pág. 99 
  15. ↑ Klenke (2020) , pág. 494-495 
  16. ↑ Bouajjani, A.; Drǎgoi, C.; Enea, C.; Rezine, A.; Sighireanu, M. (2010). "Síntesis invariante para programas que manipulan listas con datos ilimitados" (PDF) . Proc. CAV . doi : 10.1007/978-3-642-14295-6_8 .
  17. ↑ Hoare, CAR (octubre de 1969). "Una base axiomática para la programación de computadoras" . Communications of the ACM . 12 (10): 576– 580. doi : 10.1145/363235.363259 . S2CID 207726175 . 

Referencias

  • Fraleigh, John B. (1976), Un primer curso de álgebra abstracta (2.ª  ed.), Reading: Addison-Wesley , ISBN 0-201-01984-1
  • Herstein, IN (1964), Temas de álgebra , Waltham: Blaisdell Publishing Company , ISBN 978-1114541016{{citation}}: Incompatibilidad de ISBN/Fecha ( ayuda )
  • Kay, David C. (1969), Geometría universitaria , Nueva York: Holt, Rinehart and Winston , LCCN 69-12075 
  • McCoy, Neal H. (1968), Introducción al álgebra moderna, edición revisada , Boston: Allyn and Bacon , LCCN 68-15225 
  • JD Fokker, H. Zantema , SD Swierstra (1991). "Iteratie e invariatie", programadores y correcciones. Servicio Académico. ISBN 90-6233-681-7.
  • Weisstein, Eric W. "Invariante" . MathWorld .
  • Popov, VL (2001) [1994], "Invariante" , Enciclopedia de Matemáticas , EMS Press
  • Billingsley, Patrick (1995). Probabilidad y medida . John Wiley & Sons. ISBN 0-471-00710-2.
  • Douc, Randal; Moulines, Eric; Prioret, Pierre; Soulier, Philippe (2018). Cadenas de Markov . Saltador. doi : 10.1007/978-3-319-97704-1 . ISBN 978-3-319-97703-4.
  • Klenke, Achim (2020). Teoría de la probabilidad: Un curso completo . Universitext. Springer. doi : 10.1007/978-1-4471-5361-0 . ISBN 978-3-030-56401-8.
  • "Applet: Invariantes visuales en algoritmos de ordenación" Archivado el 24/02/2022 en Wayback Machine por William Braynen en 1997.