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

А обои на стену является инвариантный под бесконечным количествомпереводы, члены группа, из которых операция обозначается ${\displaystyle \circ }$ это функциональная композиция.

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

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

Примеры

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

An личность уравнение, которое остается верным для всех значений его переменных. Это также неравенство которые остаются верными при изменении значений их переменных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Когда Т это смещение винта, то ось винта инвариантная линия, хотя если подача не равно нулю, Т не имеет фиксированных точек.

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

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

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

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

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

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

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

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

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

Независимо от презентации

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

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

• В представление многообразия в плане координатных карт - инварианты должны быть неизменными при изменение координат.
• Разные многообразие разложения, как обсуждалось для характеристики Эйлера.
• Инварианты презентация группы.

Без изменений при возмущении

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

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

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

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

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

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

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

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

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

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

пустота Морда(пустота) {    летучий int RandomRule;    int Я считаю = 1, UCount = 0;    пока (Я считаю % 3 != 0)                         // бесконечный цикл        выключатель(RandomRule) {        дело 1:                  UCount += 1;   перемена;        дело 2:   Я считаю *= 2;   UCount *= 2;   перемена;        дело 3:   Я считаю -= 3;   UCount += 1;   перемена;        дело 4:                  UCount -= 2;   перемена;        }                                          // вычисляемый инвариант: ICount% 3 == 1 || ICount% 3 == 2}

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

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

Примечания

1. «Окончательный словарь высшего математического жаргона - инвариантность». Математическое хранилище. 2019-08-01. Получено 2019-12-05.
2. «Инвариантное определение (иллюстрированный математический словарь)». www.mathsisfun.com. Получено 2019-12-05.
3. Вайсштейн, Эрик В. «Инвариант». mathworld.wolfram.com. Получено 2019-12-05.
4. «Инвариант - Математическая энциклопедия». www.encyclopediaofmath.org. Получено 2019-12-05.
5. Фрали (1976), стр. 166–167).
6. Кей (1969, стр.219)
7. Дифференциальные инварианты для дифференциальных уравнений Андре Платцера
8. Хофштадтер, Дуглас Р. (1999) [1979], Гедель, Эшер, Бах: вечная золотая коса, Базовые книги, ISBN  0-465-02656-7Здесь: Глава I.
9. Барри Саймон. Представления конечных и компактных групп. American Mathematical Soc. п. 16. ISBN  978-0-8218-7196-6.
10. Джудит Седерберг (1989). Курс современной геометрии. Springer. п.174. ISBN  978-1-4757-3831-5.
11. Фрали (1976), п. 103)
12. Герштейн (1964, п. 42)
13. Маккой (1968), п. 183)
14. Bouajjani, A .; Drǎgoi, C .; Enea, C .; Резин, А .; Сигиряну, М. (2010). «Инвариантный синтез программ, управляющих списками с неограниченными данными» (PDF). Proc. CAV. Дои:10.1007/978-3-642-14295-6_8.
15. Хоар, К.А.Р. (Октябрь 1969 г.). «Аксиоматическая основа компьютерного программирования» (PDF). Коммуникации ACM. 12 (10): 576–580. Дои:10.1145/363235.363259. S2CID  207726175. Архивировано из оригинал (PDF) на 2016-03-04.

Рекомендации

• Фрали, Джон Б. (1976), Первый курс абстрактной алгебры (2-е изд.), Литература: Эддисон-Уэсли, ISBN  0-201-01984-1
• Герштейн, И. Н. (1964), Темы по алгебре, Уолтем: Издательство Blaisdell, ISBN  978-1114541016
• Кей, Дэвид К. (1969), Колледж Геометрия, Нью-Йорк: Холт, Райнхарт и Уинстон, LCCN  69-12075
• Маккой, Нил Х. (1968), Введение в современную алгебру, исправленное издание, Бостон: Аллин и Бэкон, LCCN  68-15225
• J.D. Fokker, Х. Зантема, С.Д. Свиерстра (1991). "Iteratie en invariatie", Programmeren en Correctheid. Академическая служба. ISBN  90-6233-681-7.
• Вайсштейн, Эрик В. «Инвариант». MathWorld.
• Попов, В. (2001) [1994], «Инвариант», Энциклопедия математики, EMS Press

внешняя ссылка

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