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

Свойство, которое не изменяется при математических преобразованиях

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

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

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

Примеры

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

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

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

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

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

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

MU-головоломка

Головоломка MU ^[7] является хорошим примером логической задачи, где определение инварианта полезно для доказательства невозможности . Головоломка требует начать со слова 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 )

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

МИ → ² MII → ² MIIII → ³ MUI → ² MUIUI → ¹ MUIUIU → ² MUIUIUUIUIU → ⁴ MUUIIIUIU → ...

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

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

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

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

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

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

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

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

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

В теории вероятностей и эргодической теории инвариантные множества обычно определяются с помощью более сильного свойства ^{[13] [14] [15].} Когда отображение измеримо, инвариантные множества образуют сигма-алгебру , инвариантную сигма-алгебру . ${\displaystyle x\in S\Leftrightarrow T(x)\in S.}$ ${\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 в настоящее время нет общего автоматизированного инструмента, который может обнаружить, что вывод из 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 ) // незавершающий цикл 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 }                                                     

Смотрите также

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

Примечания

1. "Определение инварианта (Иллюстрированный математический словарь)". www.mathsisfun.com . Получено 05.12.2019 .
2. Weisstein, Eric W. "Invariant". mathworld.wolfram.com . Получено 2019-12-05 .
3. "Инвариант – Энциклопедия математики". www.encyclopediaofmath.org . Получено 2019-12-05 .
4. Qiao, Xiaoyu (20 января 2015 г.). "Tricolorability.pdf" (PDF) . Теория узлов, неделя 2: Tricolorability . Архивировано из оригинала (PDF) 25 мая 2024 г. . Получено 25 мая 2024 г. .
5. Фрели (1976, стр. 166–167)
6. Кей (1969, стр. 219)
7. Хофштадтер, Дуглас Р. (1999) [1979], Гёдель, Эшер, Бах: Вечная золотая коса , Basic Books, ISBN 0-465-02656-7Здесь: Глава I.
8. Барри Саймон. Представления конечных и компактных групп. Американское математическое общество. стр. 16. ISBN 978-0-8218-7196-6.
9. Джудит Седерберг (1989). Курс современной геометрии . Springer. стр. 174. ISBN 978-1-4757-3831-5.
10. Фрейли (1976, стр. 103)
11. Херштейн (1964, стр. 42)
12. Маккой (1968, стр. 183)
13. Биллингсли (1995), стр. 313–314.
14. Дук и др. (2018), стр. 99
15. Кленке (2020), стр. 494-495
16. Bouajjani, A.; Drǎgoi, C.; Enea, C.; Rezine, A.; Sighireanu, M. (2010). «Инвариантный синтез для программ, работающих со списками с неограниченными данными» (PDF) . Proc. CAV . doi : 10.1007/978-3-642-14295-6_8 .
17. Hoare, CAR (октябрь 1969). "Аксиоматическая основа компьютерного программирования" (PDF) . Communications of the ACM . 12 (10): 576–580. doi :10.1145/363235.363259. S2CID  207726175. Архивировано из оригинала (PDF) 2016-03-04.

Ссылки

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

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

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