Инволюция (В. А. Мусинов)

Материал из Викиучебника — открытых книг для открытого мира
Перейти к навигации Перейти к поиску

Инволю́ция (от лат. involutio — свёртывание, завиток) — нетождественное преобразование, которое является обратным самому себе, то есть своей собственной инверсией. Это унарная операция.

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

Scale 1200 (1).png

Иногда пишут: , где обозначает тождественное преобразование. Вместо используют запись: .

Таким образом, двойное применение функции даёт исходное значение.

Свойства[править]

Любая инволюция — это биекция.

Если преобразование инволютивное, то для любого выражения и его образа имеем . В самом деле, .

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


Если — инволюция, то имеют место следующие соотношения:

  1. [основное свойство]
  2. [критерий]
  3. Для всякой инволюции выполняется тождество: .

Примеры[править]

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

  • инволюция называется тривиальной;
  • , заданная на множестве целых , рациональных или вещественных чисел . Понятно, что последовательное умножение на , например, в поле вещественных чисел, приводит к изначальному результату:
    Scale 1200 (2).png
  • простейшие инволюции на множестве вещественных чисел :
    , , , , , , , , ;
  • инволюция при и ;
  • Функция непрерывна, монотонно убывает, , , . То есть есть инволюция, производная которой имеет разрыв в точке ;
  • дополнение множества, заданная для подмножеств некоторого универсального множества ;
  • логическое отрицание булевой алгебры: двойное применение этого унарного оператора оставляет высказывание "на месте", а значит является инволюцией для элементов булева множества;
    Scale 1200 (6).png
  • симметрии: центральная, осевая, зеркальная;
  • инверсия;
  • комплексное сопряжение;
  • преобразование Лежандра
  • при факторизации обычного тора (точнее, одномерного комплексного тора, ещё точнее, эллиптической кривой) по инволюции вида получается сфера;
  • Если представить, что — нажатие на клавишу бытового накладного выключателя (т. е. включить либо выключить свет), то будет инволюцией.

Задача. Привести примеры:

  1. аналитической инволюции в ;
  2. инволюции в геометрии;
  3. свой пример инволюции (например, из таких дисциплин, как информатика, техника, риторика и т. п., а также личный опыт).

Воможное решение.

  1. производная функции , где ;
  2. поворот полуокружности на :
    Поворот полуокружности.png
    Очевидно, что такая операция является инволюцией, возвращая точку на окружности в исходное положение.
  3. Предложим сразу два варианта ответа на этот пункт.
    1. Явление в лингвистике: любой палиндром (палиндром — это последовательность символов, которая слева-направо и справа-налево пишется одинаково; напр.: «АБА» или «АББ ББА»). Например, написание таких слов, как «доход», «шалаш» и «топот», чисел и , а также предложение «А роза упала на лапу Азора» Афанасия Фета — инволюции.
    2. Повседневный опыт: выворачивание ткани или одежды обратной стороной (по отношению к лицевой) наизнанку. Пример: выворачивание наизнанку панамы.

Упражнение 1. Выполните предыдущую задачу самостоятельно со своими примерами.

Важнейшие факты[править]

Теорема 1.
Композиция двух инволюций и является инволюцией тогда и только тогда, когда они коммутируют: .

Пример 1. Такая композиция есть инволюция.

Аналогично, если и , , — инволюции, то и — инволюция.

Пример 2. , , .

Теорема 2.
Если — монотонно возрастающая функция, то уравнения и , или , равносильны.

Рассмотрим следующую задачу.

Теорема 3.
Функция вида (где — некоторое биективное отображение) будет инволюцией в том и только в том случае, если функция — инволюция.

Замечание. Ясно, что теорема 3 сохраняет свою силу, если , где — биекция.

Пример 3. В положительных числах такая функция будет как раз инволюцией по доказанной выше теореме:

Scale 1200 (3).png

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

Scale 1200 (4).png

В более общем случае инволюцией на плоскости является симметричное отражение относительно прямой.

И это не удивительно! Если функция является инволюцией, то она является обратной самой себе. На нашем примере это можно легко показать, если поменять местами x и y:

Scale 1200 (5).png


Следствие 1.
Пусть — инволюция на множестве . Тогда если — взаимно-однозначное отображение [биекция] множества на с обратной биекцией , то композиция — инволюция на множестве .

Involution4

Теорема 4.
Пусть — инволюция на множестве . Если — такое отображение из в , что , то и — инволюции на .
Следствие 2.
Если — такое отображение из в , что , причём и — инволюции на . Тогда — инволюция на множестве .

Пример 4. Функция .

Упражнение 2. Убедитесь, что представленная функция действительно обладает таким свойством.


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

Пример 5. Пусть , , . Тогда схемой функции будет .

Наконец, доказательство последнего и довольно важного утверждения в качестве упражнения проведите самостоятельно.

Упражнение 3. Докажите, что если и , то — инволюция.

Специальную функцию назовём вспомогательной для функции , если существует, причём она инволютивна, и выполняется равенство:

Пример 6. Для любой функции вида , вспомогательной функцией будет , где — некоторая константа. Ну действительно

Пример 7. Функция — вспомогательная для , где — любое действительное, отличное от нуля, число; поскольку

Теорема 5.
Пусть для функции существует такая функция , что обе эти функции коммутируют: . Для того чтобы выполнялось равенство , верное для обратной функции , необходимо и достаточно, чтобы было инволюцией.

Фокус[править]

Упражнение 4. Какова разгадка этого фокуса?

Указание. Возьмите за функцию алгоритм приписывания к числу , то есть . Так как результат совпадает с исходным числом , то над числом — это умножение его на 7, 11 и 13. Осталось найти связь и .

Инвариантные точки инволюции[править]

Бывает так, что у некоторого отображения (функции) есть так называемая инвариантная, или неподвижная, точка.

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

Определение. Точка неподвижная у данного отображения выполняется условие инвариантности: .

Если — инволюция, то для неё возможны три случая:

  1. имеет ровно 2 различные неподвижные точки;
  2. имеет только 1 неподвижную точку;
  3. не имеет неподвижных точек.

❗ Решить инвариантную задачу о неподвижных точках — значит найти (предъявить) все неподвижные точки функции или доказать, что их нет.

Утверждение 1. Если на рассматриваемом множестве имеет неподвижных точек, то на его любом подмножестве имеет не больше, чем , неподвижных точек.

Утверждение 2. Если на рассматриваемом множестве имеет неподвижных точек и , то на множестве отображение имеет не меньше, чем , неподвижных точек.

Утверждение 3. Если — инволюция с областью определения , то функция имеет счётное число неподвижных точек.

Упражнение 5. Докажите, что функция имеет одну неподвижную точку [Какую?].

Задача. Решить инвариантную задачу для функции .

Решение. Пусть — неподвижная точка, тогда должно выполняться условие инвариантности: , то есть . Иными словами, решим уравнение при . Ясно, что .

Ответ: функция в не имеет неподвижных точек.

Задача. Решить инвариантную задачу для функции .

Решение. Заранее скажем, что . Положим: — неподвижная точка. Решим уравнение . Преобразуем его: ; это квадратное уравнение с чётным средним коэффициентом. Поэтому решения таковы:

Здесь 2 ситуации:

  • если и , то неподвижных точек нет;
  • если же хотя бы одно из предыдущих неравенств не выполняется (т. е. верно или ), то функция имеет ровно 2 неподвижные точки, которые вычисляются по вышенаписанной формуле.

Упражнение 6. В разделе «Примеры» решите инвариантные задачи для оставшихся функций. Ответьте на вопросы:

  1. Какие из них:
    1. имеют 2 неподвижные точки;
    2. имеют 1 неподвижную точку;
    3. не имеют таковых?
  2. Придумайте: с чем это может быть связано?
  3. Найдите неподвижные точки функции . Сколько их?
  4. Какая приходит Вам в голову ассоциация, связанная с неподвижными точками? Приведите соответствующий пример из своего жизненного опыта.

Упражнение 7. Дано уравнение .

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

Упражнение 8. Для квадратичной иррациональности ( ) найдите неподвижные точки.

Указание. Примите её за функцию.

Ответ:

Лирическое отступление[править]

Приведём пример композиции двух инволюций, которая не будет уже инволюцией.

Пример. Функция не является инволюцией; её строение таково: , где и у нас — обе инволюции.

Упражнение 5. Докажите: для верно, что .

Замечание. Функция со схемой также не есть инволюция.

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

Перед тем, как ответить на этот вопрос, сперва-наперво выясним, а каким свойством, в принципе, обладает введённая функция .

Вычислим . У нас получится:

Значит, .

Инволюция в алгебре[править]

Перестановка является инволюцией, если , каждая инволюция является произведением непересекающихся транспозиций, например:

.

Число инволюций в группе перестановок порядка определяется по формулам:

  • (рекуррентная формула),
  • ,

(первые значения : 1, {{w:nums|link=nrl|1|2|4|10|26|76|232|764|2620|9496|35696|140152}}[1]).

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

Примечания[править]

  1. Шаблон:OEIS long