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 que se aplican operaciones o transformaciones de un tipo determinado a los objetos. [1] [2] La clase particular de objetos y el tipo de transformaciones suelen indicarse por 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 frases "invariante bajo" e "invariante a" una transformación. De manera 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 inalterado. Por ejemplo, las aplicaciones conformes se definen como transformaciones del plano que conservan los ángulos . El descubrimiento de invariantes es un paso importante en el proceso de clasificación de objetos matemáticos. [2] [3]
Un ejemplo sencillo de invariancia se expresa en nuestra capacidad de contar . Para un conjunto finito de objetos de cualquier tipo, existe un número al que siempre llegamos, independientemente del orden en que contemos los objetos del conjunto . La cantidad —un número cardinal— está asociada con el conjunto y es invariante en 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 de una recta numérica no cambia al sumar la misma cantidad a ambos números. Por otra parte, la multiplicación no tiene esta misma propiedad, ya que la distancia no es invariante bajo la multiplicación.
Los ángulos y las razones de las distancias son invariantes bajo escalas , rotaciones , traslaciones y reflexiones . Estas transformaciones producen formas similares , que es la base de la trigonometría . En contraste, los ángulos y las razones no son invariantes bajo escalas no uniformes (como el estiramiento). La suma de los ángulos interiores de un triángulo (180°) es invariante bajo todas las operaciones anteriores. Como otro ejemplo, todos los círculos son similares: pueden transformarse entre sí y la razón de la circunferencia al diámetro es invariante (denotada por la letra griega π ( pi )).
Algunos ejemplos más complicados:
El rompecabezas MU [7] es un buen ejemplo de un problema lógico en el que determinar un invariante es útil para una prueba de imposibilidad . El rompecabezas pide que se comience con la palabra MI y se la transforme en la palabra MU, utilizando en cada paso una de las siguientes reglas de transformación:
Un ejemplo de derivación (con superíndices que indican las reglas aplicadas) es
En vista de esto, uno podría preguntarse si es posible convertir MI en MU, utilizando solo estas cuatro reglas de transformación. Uno podría pasar muchas horas aplicando estas reglas de transformación a cadenas. Sin embargo, podría ser más rápido encontrar una propiedad que sea invariante a todas las reglas (es decir, que no cambie con ninguna de ellas), y que demuestre que llegar a MU es imposible. Al observar el rompecabezas desde un punto de vista lógico, uno podría darse cuenta de que la única forma de deshacerse de cualquier I es tener tres I consecutivas en la cadena. Esto hace que sea interesante considerar el siguiente invariante:
Este es un invariante del problema, si para cada una de las reglas de transformación se cumple lo siguiente: si el invariante se cumplía antes de aplicar la regla, también se cumplirá después de aplicarla. Si se observa el efecto neto de la aplicación de las reglas sobre la cantidad de I y U, se puede ver que esto es en realidad el caso para todas las reglas:
La tabla anterior muestra claramente que el invariante se cumple para cada una de las posibles reglas de transformación, lo que significa que cualquiera que sea la regla que se elija, en cualquier estado, si el número de 1 no era múltiplo de tres antes de aplicar la regla, tampoco lo será después.
Dado que hay una única I en la cadena inicial MI, y una que 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).
Un subconjunto S del dominio U de una aplicación T : U → U es un conjunto invariante bajo la aplicación cuando Nótese que los elementos de S no son fijos , aunque el conjunto S está fijo en el conjunto potencia de U . (Algunos autores usan la terminología invariante por conjunto, [8] vs. invariante por punto, [9] para distinguir entre estos casos). Por ejemplo, un círculo es un subconjunto invariante del plano bajo una rotación alrededor del centro del círculo. Además, una superficie cónica es invariante como un conjunto bajo una homotecia del espacio.
También se dice que un conjunto invariante de una operación T es 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 línea que pasa por 0 y v es un conjunto invariante bajo T , en cuyo caso los vectores propios abarcan 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 la teoría de la probabilidad y la teoría ergódica , los conjuntos invariantes se definen generalmente a través de la propiedad más fuerte [13] [14] [15] Cuando el mapa es medible, los conjuntos invariantes forman un álgebra sigma , el álgebra sigma invariante .
La noción de invariancia se formaliza de tres maneras diferentes en matemáticas: mediante acciones grupales , presentaciones y deformación.
En primer lugar, si uno tiene un grupo G actuando sobre un objeto matemático (o conjunto de objetos) X, entonces uno puede preguntarse qué puntos x son inalterados, "invariantes" bajo la acción del grupo, o bajo un elemento g del grupo.
Con frecuencia, se tendrá un grupo que actúa sobre un conjunto X , lo que nos lleva a determinar qué objetos en un conjunto asociado F ( X ) son invariantes. Por ejemplo, la rotación en el plano alrededor de un punto deja invariante el punto alrededor del cual gira, mientras que la traslación en el plano no deja ningún punto invariante, pero sí deja todas las líneas paralelas a la dirección de la traslación invariantes como líneas. Formalmente, definamos el conjunto de líneas en el plano P como L ( P ); entonces, un movimiento rígido del plano convierte las 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 no cambian con una acción.
Más importante aún, uno puede definir una función en un conjunto, como "radio de un círculo en el plano", y luego preguntar si esta función es invariante bajo una acción grupal, como movimientos rígidos.
A la noción de invariantes se suman las covariantes , también llamadas órbitas, que formalizan la noción de congruencia : objetos que pueden ser llevados unos a otros por una acción grupal. 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 con un triángulo dado es un covariante.
Estos están conectados de la siguiente manera: los invariantes son constantes en coinvariantes (por ejemplo, los triángulos congruentes tienen el mismo perímetro), mientras que dos objetos que concuerdan en el valor de un invariante pueden o no ser congruentes (por ejemplo, dos triángulos con el mismo perímetro no necesitan ser congruentes). En problemas de clasificación , uno podría buscar encontrar un conjunto completo de invariantes , de modo que si dos objetos tienen los mismos valores para este conjunto de invariantes, entonces sean congruentes.
Por ejemplo, los triángulos cuyos tres lados son iguales son congruentes bajo movimientos rígidos, a través de la congruencia LLL , y por lo tanto las longitudes de los tres lados forman un conjunto completo de invariantes para triángulos. Las tres medidas de los ángulos de un triángulo también son invariantes bajo movimientos rígidos, pero no forman un conjunto completo ya que los triángulos incongruentes pueden compartir las mismas medidas de los ángulos. Sin embargo, si se permite la escala además de los movimientos rígidos, entonces el criterio de similitud AAA muestra que este es un conjunto completo de invariantes.
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 de células se define como la suma alternada del número de células en cada dimensión. Uno puede olvidar la estructura del complejo de células y mirar solo el espacio topológico subyacente (la variedad ) – como diferentes complejos de células dan la misma variedad subyacente, uno puede preguntarse si la función es independiente de la elección de presentación, en cuyo caso es un invariante definido intrínsecamente . Este es el caso de la característica de Euler, y un método general para definir y calcular invariantes es definirlos para una presentación dada, y luego demostrar que son independientes de la elección de presentación. Nótese que no existe la noción de una acción de grupo en este sentido.
Los ejemplos más comunes son:
En tercer lugar, si uno está estudiando un objeto que varía en una familia, como es común en geometría algebraica y geometría diferencial , uno puede preguntarse si la propiedad no cambia bajo perturbación (por ejemplo, si un objeto es constante en familias o invariante bajo un cambio de métrica).
En informática , un invariante es una afirmación lógica que siempre se considera verdadera durante una determinada fase de la ejecución de un programa informático . Por ejemplo, un invariante de bucle es una condición que es verdadera al principio y al final de cada iteración de un bucle.
Los invariantes son especialmente útiles cuando se razona sobre la corrección de un programa informático . La teoría de optimización de compiladores , 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 utilizar aserciones en su código para hacer explícitas las invariantes. Algunos lenguajes de programación orientados a objetos tienen una sintaxis especial para especificar invariantes de clase .
Las herramientas de interpretación abstracta pueden calcular invariantes simples de programas informáticos imperativos dados. El tipo de propiedades que se pueden encontrar depende 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 utilizando el cálculo de Hoare , [17] debe proporcionarse manualmente un invariante de bucle para cada bucle del programa, lo que 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 anterior del rompecabezas MU , actualmente no existe una herramienta automatizada general que pueda detectar que una derivación de MI a MU es imposible utilizando únicamente las reglas 1 a 4. Sin embargo, una vez que se ha realizado manualmente la abstracción de la cadena al número de sus "I", lo que conduce, 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 ) { volátil int RandomRule ; int ICount = 1 , UCount = 0 ; mientras ( ICount % 3 != 0 ) // bucle no terminal switch ( RandomRule ) { caso 1 : UCount += 1 ; descanso ; caso 2 : ICount *= 2 ; UCount *= 2 ; descanso ; caso 3 : ICount -= 3 ; UCount += 1 ; descanso ; caso 4 : UCount -= 2 ; descanso ; } // invariante calculado: ICount % 3 == 1 || ICount % 3 == 2 }