Инвариант (математика)

Простой пример инвариантности выражается в нашей способности считать. Для конечного множества объектов любого рода существует число, к которому мы всегда приходим, независимо от порядка, в котором считаем объекты в множестве. Эта величина — кардинальное число — ассоциируется с множеством и инвариантна относительно процесса счёта.

Тождество — это равенство, которое остаётся верным при любых значениях переменных. Существуют также неравенства, сохраняющие истинность при изменении значений переменных.

Расстояние между двумя точками на числовой прямой не изменяется при прибавлении одного и того же числа к обоим значениям. В то же время Умножение не обладает этим свойством, так как расстояние не инвариантно относительно умножения.

Углы и отношения расстояний инвариантны относительно масштабирования, поворотов, переносов и отражений. Эти преобразования порождают подобные фигуры, что лежит в основе тригонометрии. В отличие от этого, углы и отношения не инвариантны относительно неравномерного масштабирования (например, растяжения). Сумма внутренних углов треугольника (180°) инвариантна относительно всех указанных выше преобразований. Ещё один пример: все окружности подобны — их можно преобразовать друг в друга, и отношение длины окружности к диаметру инвариантно (обозначается греческой буквой π (пи)).

Более сложные примеры:

• Действительная часть и модуль комплексного числа инвариантны относительно комплексного сопряжения.
• Трёхцветность узлов^[4].
• Степень многочлена инвариантна относительно линейной замены переменных.
• Размерность и гомологические группы топологического объекта инвариантны относительно гомеоморфизма^[5].
• Число неподвижных точек динамической системы инвариантно относительно многих математических операций.
• Евклидово расстояние инвариантно относительно ортогональных преобразований.
• Площадь инвариантна относительно линейных отображений с определителем ±1.
• Некоторые инварианты проективных преобразований включают Коллинеарность трёх и более точек, сходимость трёх и более прямых, конические сечения и кросс-отношение^[6].
• Определитель, след, собственные векторы и собственные значения линейного эндоморфизма инвариантны относительно смены базиса. Иными словами, спектр матрицы инвариантен относительно смены базиса.
• Главные инварианты тензоров не изменяются при повороте системы координат (см. ).
• Сингулярные значения матрицы инвариантны относительно ортогональных преобразований.
• Мера Лебега инвариантна относительно параллельных переносов.
• Дисперсия распределения вероятностей инвариантна относительно параллельных переносов вещественной прямой. Следовательно, дисперсия случайной величины не изменяется при добавлении константы.
• Неподвижные точки преобразования — это элементы области определения, инвариантные относительно данного преобразования. В зависимости от контекста их могут называть симметричными относительно этого преобразования. Например, объекты с трансляционной симметрией инвариантны относительно определённых переносов.
• Интеграл ${\textstyle \int _{M}K\,d\mu }$ гауссовой кривизны ${\displaystyle K}$ двумерного риманова многообразия ${\displaystyle (M,g)}$ инвариантен относительно изменения римановой метрики ${\displaystyle g}$. Это теорема Гаусса — Бонне.

Задача MU^[7] — хороший пример логической задачи, где определение инварианта полезно для доказательства невозможности. В задаче требуется, начиная со слова MI, получить слово MU, используя на каждом шаге одно из следующих правил преобразования:

1. Если строка оканчивается на I, можно добавить U (xI → xIU)
2. Строку после M можно полностью удвоить (Mx → Mxx)
3. Любые три подряд идущих I (III) можно заменить на один U (xIIIy → xUy)
4. Любые две подряд идущих U можно удалить (xUUy → xy)

Пример вывода (с верхними индексами, указывающими применённые правила):

MI →² MII →² MIIII →³ MUI →² MUIUI →¹ MUIUIU →² MUIUIUUIUIU →⁴ MUIUIIUIU → ...

Возникает вопрос: возможно ли получить MU из MI, используя только эти четыре правила? Можно потратить много времени, перебирая варианты, однако быстрее будет найти свойство, инвариантное относительно всех правил (то есть не изменяющееся ни одним из них), и тем самым показать невозможность получения MU. С логической точки зрения можно заметить, что избавиться от I можно только, если в строке есть три подряд идущих I. Это делает интересным следующий инвариант:

Число I в строке не делится на 3.

Это инвариант задачи, если для каждого правила выполняется: если инвариант выполнялся до применения правила, он будет выполняться и после. Рассмотрим влияние каждого правила на количество I и U:

Таблица выше ясно показывает, что инвариант сохраняется при каждом из возможных правил, то есть, какое бы правило ни было выбрано и в каком бы состоянии ни находилась строка, если число I не делилось на три до применения правила, оно не будет делиться и после.

Поскольку в исходной строке MI содержится одна буква I, а 1 не делится на 3, можно заключить, что получить MU из MI невозможно (так как число I никогда не станет кратным трём).

Подмножество S области определения U отображения T: U → U называется инвариантным множеством относительно этого отображения, если ${\displaystyle x\in S\iff T(x)\in S.}$ Элементы S не обязательно неподвижны, хотя само множество S фиксировано в булеане U. (Некоторые авторы используют терминологию инвариантно как множество^[8] в отличие от инвариантно поэлементно^[9] для различения этих случаев.) Например, окружность является инвариантным подмножеством плоскости относительно поворота вокруг её центра. Кроме того, Коническая поверхность инвариантна как множество относительно гомотетии пространства.

Инвариантное множество относительно операции T также называют устойчивым относительно T. Например, нормальные подгруппы, играющие важную роль в теории групп, — это те подгруппы, которые устойчивы относительно внутренних автоморфизмов данной группы^[10].^[11][12] В линейной алгебре, если линейное преобразование T имеет собственный вектор v, то прямая, проходящая через 0 и v, является инвариантным множеством относительно T; в этом случае собственные векторы порождают инвариантное подпространство, устойчивое относительно T.

Если T — винтовое перемещение, то винтовая ось — инвариантная прямая, хотя при ненулевом шаге у T нет неподвижных точек.

В теории вероятностей и эргодической теории инвариантные множества обычно определяются через более сильное свойство ${\displaystyle x\in S\Leftrightarrow T(x)\in S.}$^[13][14][15] Если отображение ${\displaystyle T}$ измеримо, инвариантные множества образуют сигма-алгебру, называемую инвариантной сигма-алгеброй.

Понятие инвариантности формализуется в математике тремя различными способами: через действия групп, представления и деформации.

Во-первых, если имеется группа G, действующая на математическом объекте (или множестве объектов) X, можно спросить, какие точки x остаются неизменными, «инвариантными» относительно действия группы или её элемента g.

Часто группа действует на множестве X, и возникает задача определить, какие объекты в связанном множестве F(X) инвариантны. Например, поворот плоскости вокруг точки оставляет эту точку инвариантной, а параллельный перенос не оставляет ни одной точки инвариантной, но оставляет инвариантными все прямые, параллельные направлению переноса. Формально, множество прямых на плоскости P обозначим как L(P); тогда жёсткое движение плоскости переводит прямые в прямые — группа жёстких движений действует на множестве прямых — и можно спросить, какие прямые остаются неизменными при действии.

Более важно, можно определить функцию на множестве, например, «радиус окружности на плоскости», и спросить, инвариантна ли эта функция относительно действия группы, например, жёстких движений.

Двойственным к инвариантам является понятие коинвариантов, также называемых орбитами, что формализует понятие конгруэнтности: объекты, которые можно перевести друг в друга действием группы. Например, относительно группы жёстких движений плоскости периметр треугольника — инвариант, а множество треугольников, конгруэнтных данному, — коинвариант.

Связь такова: инварианты постоянны на коинвариантах (например, конгруэнтные треугольники имеют одинаковый периметр), но два объекта с одинаковым значением одного инварианта могут быть и не конгруэнтны (например, два треугольника с одинаковым периметром могут не быть конгруэнтными). В классификационных задачах стремятся найти полную систему инвариантов, такую, что если два объекта имеют одинаковые значения всех инвариантов, то они конгруэнтны.

Например, треугольники, у которых все три стороны равны, конгруэнтны относительно жёстких движений (по признаку SSS), и потому длины трёх сторон образуют полную систему инвариантов для треугольников. Три угла треугольника также инвариантны относительно жёстких движений, но не образуют полной системы, так как неконгруэнтные треугольники могут иметь одинаковые углы. Однако если разрешить масштабирование наряду с жёсткими движениями, то признак подобия AAA показывает, что это полная система инвариантов.

Во-вторых, функция может быть определена через некоторое представление или разложение математического объекта; например, Эйлерова характеристика клеточного комплекса определяется как чередующаяся сумма числа клеток по размерностям. Можно забыть структуру клеточного комплекса и рассматривать только лежащее в основе топологическое пространство (например, многообразие) — поскольку разные клеточные комплексы могут соответствовать одному и тому же многообразию, возникает вопрос, зависит ли функция от выбора представления, и если нет, то это внутренне определённый инвариант. Так обстоит дело с эйлеровой характеристикой, и общий метод определения и вычисления инвариантов состоит в том, чтобы определить их для конкретного представления, а затем доказать независимость от выбора представления. В этом смысле понятие действия группы не используется.

Наиболее распространённые примеры:

• Представление многообразия через координатные карты — инварианты должны быть неизменны при смене координат.
• Различные разложения многообразий, как в случае эйлеровой характеристики.
• Инварианты представления группы.

В-третьих, если изучается объект, изменяющийся в семействе, как это часто бывает в алгебраической и дифференциальной геометрии, можно спросить, сохраняется ли свойство при деформации (например, если объект постоянен на семействе или инвариантен относительно изменения метрики).

В информатике инвариант — это логическое утверждение, которое всегда считается истинным в определённой фазе выполнения компьютерной программы. Например, инвариант цикла — это условие, истинное в начале и конце каждой итерации цикла.

Инварианты особенно полезны при рассуждениях о корректности программы. Теория оптимизирующих компиляторов, методология проектирования по контракту и формальные методы проверки корректности программ во многом опираются на инварианты.

Программисты часто используют утверждения в коде для явного указания инвариантов. Некоторые объектно-ориентированные языки программирования имеют специальный синтаксис для задания инвариантов класса.

Инструменты абстрактной интерпретации могут вычислять простые инварианты для заданных императивных программ. Вид свойств, которые могут быть обнаружены, зависит от используемых абстрактных доменов. Типичные примеры — диапазоны значений целых переменных, например 0<=x<1024, отношения между переменными, например 0<=i-j<2*n-1, и информация о делимости, например y%4==0. В академических прототипах рассматриваются также простые свойства указателей^[16].

Более сложные инварианты, как правило, должны задаваться вручную. В частности, при верификации императивной программы с помощью исчисления Хоара^[17] инвариант цикла должен быть задан вручную для каждого цикла, что является одной из причин непрактичности этого подхода для большинства программ.

В контексте приведённого выше примера задачи MU в настоящее время не существует общего автоматического инструмента, способного обнаружить невозможность получения MU из MI только с помощью правил 1–4. Однако, если вручную абстрагировать строку до числа символов "I", например, с помощью следующей программы на C, инструмент абстрактной интерпретации сможет обнаружить, что ICount%3 не может быть равно 0, и, следовательно, цикл "while" никогда не завершится.

void MUPuzzle(void) {
    volatile int RandomRule;
    int ICount = 1, UCount = 0;
    while (ICount % 3 != 0)                         // бесконечный цикл
        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;
        }                                          // вычисленный инвариант: ICount % 3 == 1 || ICount % 3 == 2
}