Не тривиальное — понятие в математике и логике¶

Не тривиальное — характеристика объекта, утверждения или решения, означающая, что оно не сводится к очевидному, вырожденному или пустому случаю. Термин широко используется в математике, логике, теории алгоритмов и теории игр, причём конкретное содержание понятия зависит от контекста: в каждом разделе знаний «тривиальность» и «нетривиальность» определяются относительно соответствующих допущений и определений.

¶Математический контекст

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

¶Не тривиальные группы и кольца

В теории групп тривиальной называется группа, состоящая из одного элемента. Не тривиальная группа — группа, содержащая хотя бы два элемента. Аналогично в теории колец: тривиальное кольцо — кольцо, в котором 0 = 1. Понятие нетривиальности фундаментально при формулировке многих результатов: например, любая конечная группа порядка p (p — простое число) нетривиальна и циклична.

¶Не тривиальные нуль и корень

При решении уравнений вида f(x) = 0 часто тривиальным решением считается x = 0, если оно очевидно удовлетворяет уравнению. Не тривиальное решение — корень, отличный от очевидного. Например, уравнение xⁿ = x имеет тривиальные корни 0 и 1, а все остальные корни (в комплексном случае — корни степени n−1 из единицы) считаются нетривиальными.

¶Не тривиальные пути и петли

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

¶Не тривиальные распределения и оценки

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

¶Логика и теория доказательств

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

Важное следствие связано с принципом «от противного»: если допустить противоречие в доказательстве, то по правилу вывода ex falso sequituritur («из ложного следует всё») можно доказать любое утверждение, в том числе заведомо ложное. Поэтому нетривиальность теории — отсутствие в ней противоречий — является одним из центральных требований к формальным системам. Теорема Гёделя о неполноте показывает, что для любой непротиворечивой формальной системы, достаточно мощной для арифметики, существуют истинные, но недоказуемые в этой системе утверждения.

¶Теория графов

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

¶Теория игр и криптография

В теории игр нетривиальное равновесие Нэша — равновесие, отличное от очевидного (например, от вырожденного, где один из игроков всегда выбирает одну и ту же стратегию). Наличие нетривиальных равновесий в играх с непрерывными стратегиями было доказано Джоном Нэшем в 1950 году, что принесло ему Нобелевскую премию по экономике 1994 года.

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

¶Философия и методология

Понятие нетривиальности имеет методологическое значение: научный результат оценивается не только по его истинности, но и по нетривиальности — степени, в которой он расширяет знание. Тривиальные истины («некоторые числа просты») не представляют интереса, тогда как нетривиальные утверждения («простых чисел бесконечно много») являются содержательными результатами.

¶История термина

Слово «тривиальный» происходит от латинского trivium — «перекрёсток, место слияния трёх дорог». В средневековых университетах trivium обозначал совокупность трёх начальных дисциплин леберального образования: грамматику, риторику и диалектику. Эти знания считались общедоступными и очевидными, отсюда переносное значение «общий, очевидный, не представляющий интереса». В математический обиход термин вошёл в XIX веке вместе с формализацией доказательств.

¶Источники

• Куратовский К., Мостовский А. Теория множеств
• Энгельking К. Общая топология
• Нэш Дж. Non-Cooperative Games (1950)
• Гёдель К. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I (1931)
• Гарднер М. Книга логических головоломок и математических игр