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

Чтобы узнать о других значениях, см. Инвариант (значения) .

Обои . инвариантны при некоторых преобразованиях Он инвариантен при горизонтальном и вертикальном перемещении, а также при вращении на 180° (но не при отражении).

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

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

Примеры

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

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

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

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

Несколько более сложных примеров:

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

МУ головоломка

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

1. Если строка заканчивается буквой I, к ней может быть добавлена ​​буква U ( x I → x IU).
2. Строка после M может быть полностью продублирована (M x → M xx ).
3. Любые три последовательных I (III) можно заменить одной U ( x III y → x U y ).
4. Любые две последовательные буквы U могут быть удалены ( x UU y → xy ).

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

МЫ → ² ТЫСЯЧИ → ² ТРЕТЬЯ → ³ МУИ → ² МЮИУИ → ¹ МНОГО → ² ОЧЕНЬ ОЧЕНЬ → ⁴ МНОГО → ...

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

Количество I в строке не кратно 3 .

Это инвариант задачи, если для каждого из правил преобразования выполняется следующее: если инвариант сохранялся до применения правила, он будет выполняться и после его применения. Глядя на конечный эффект применения правил на количество I и U, можно увидеть, что это действительно так для всех правил:

Правило	#Является	#Вошь	Влияние на инвариант
1	+0	+1	Количество I не меняется. Если инвариант соблюдается, он все равно сохраняется.
2	×2	×2	Если n не кратно 3, то и 2× n тоже не кратно 3. Инвариант по-прежнему сохраняется.
3	−3	+1	Если n не кратно 3, то n −3 тоже не кратно 3. Инвариант по-прежнему сохраняется.
4	+0	−2	Количество I не меняется. Если инвариант соблюдается, он все равно сохраняется.

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

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

Инвариантный набор

Подмножество U S области U отображения T : U → когда является инвариантным множеством относительно отображения, $x\in S\implies T(x)\in S.$ что элементы S Обратите внимание , не фиксированы хотя набор S фиксирован в степеней U. наборе , (Некоторые авторы используют терминологию «множественно-инвариантный», против точечного инварианта, различать эти случаи.) Например, круг — это инвариантное подмножество плоскости относительно вращения вокруг центра круга. Далее, коническая поверхность инвариантна как множество относительно гомотетии пространства.

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

Когда T — смещение винта , ось винта представляет собой инвариантную линию, хотя, если шаг ненулевой, T не имеет фиксированных точек.

В теории вероятностей и эргодической теории инвариантные множества обычно определяются посредством более сильного свойства $x\in S\Leftrightarrow T(x)\in S.$ Когда карта $T$ измерима, инвариантные множества образуют сигма-алгебру , инвариантную сигма-алгебру .

Официальное заявление

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

Без изменений при групповом действии

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

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

Что еще более важно, можно определить функцию на множестве, например «радиус круга на плоскости», а затем спросить, инвариантна ли эта функция относительно группового действия, такого как жесткие движения.

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

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

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

Независимость от представления

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

Наиболее распространенными примерами являются:

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

Не изменяется при возмущении

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

Инварианты в информатике

Чтобы узнать о других значениях слова «инвариант» в информатике, см. «Инвариант (значения)» .

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

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

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

Автоматическое обнаружение инвариантов в императивных программах

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

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

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

void MUPuzzle(void) {
    volatile int RandomRule;
    int ICount = 1, UCount = 0;
    while (ICount % 3 != 0)                         // non-terminating loop
        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;
        }                                          // computed invariant: ICount % 3 == 1 || ICount % 3 == 2
}

См. также

• Эрлангенская программа
• Инвариант графа
• Инвариантный дифференциальный оператор
• Инвариантная оценка в статистике
• Инвариантная мера
• Инвариант (физика)
• Инварианты тензоров
• Инвариантная теория
• Инвариант узла
• Математическая константа
• Математические константы и функции
• Масштабная инвариантность
• Симметрия в математике
• Топологический инвариант
• Развитие Янга – Деруйца

Ссылки

• Фрэли, Джон Б. (1976), Первый курс абстрактной алгебры (2-е изд.), Чтение: Аддисон-Уэсли , ISBN  0-201-01984-1
• Херштейн, Индиана (1964), Темы алгебры , Уолтем: издательство Blaisdell Publishing Company , ISBN  978-1114541016
• Кей, Дэвид К. (1969), Геометрия колледжа , Нью-Йорк: Холт, Райнхарт и Уинстон , LCCN   69-12075
• Маккой, Нил Х. (1968), Введение в современную алгебру, исправленное издание , Бостон: Аллин и Бэкон , LCCN   68-15225
• Дж. Д. Фоккер, Х. Зантема , С. Д. Свирстра (1991). «Итерация и инвариантность», Программирование и корректность. Академическая служба. ISBN   90-6233-681-7 .
• Вайсштейн, Эрик В. «Инвариант» . Математический мир .
• Попов, В.Л. (2001) [1994], «Инвариант» , Энциклопедия Математики , EMS Press
• Биллингсли, Патрик (1995). Вероятность и мера . Джон Уайли и сыновья. ISBN  0-471-00710-2 .
• Мило, Рэндал; Мулен, Эрик; Приоре, Пьер; Сулье, Филипп (2018). Марковские цепи . Спрингер. ISBN  978-3-319-97703-4 .
• Кленке, Ахим (2020). Теория вероятностей: Комплексный курс . Спрингер. ISBN  978-3-030-56401-8 .

Внешние ссылки

• «Апплет: визуальные инварианты в алгоритмах сортировки» Уильяма Брайнена в 1997 году.