Транзитивность — свойство отношений¶

Транзитивность — свойство бинарного отношения, заключающееся в том, что из выполнения отношения для пары элементов (a, b) и пары элементов (b, c) следует его выполнение для пары (a, c). Формально: ∀a, b, c: если aRb и bRc, то aRc. Транзитивность является одним из ключевых свойств, определяющих структуру отношений в математике, лингвистике, логике и теории категорий.

¶Математическая логика и теория множеств

В теории множеств транзитивное отношение на множестве M — это отношение R ⊆ M × M, удовлетворяющее указанному условию. Транзитивность входит в набор свойств, по которым классифицируются отношения:

Отношение, являющееся одновременно рефлексивным, симметричным и транзитивным, называется отношением эквивалентности. Оно разбивает множество на классы эквивалентности. Отношение, являющееся рефлексивным, антисимметричным (aRb и bRa влечёт a = b) и транзитивным, называется частичным порядком.

Примеры транзитивных отношений: «меньше или равно» (≤), «делится на» (в натуральных числах), «подмножество» (⊆), «предшествует во времени». Примеры не транзитивных: «строго меньше по модулю» (|−5| < |3| и |3| < |4|, но |−5| > |4|), «дружит с» в бытовом смысле, «родитель» (отец отца — не отец).

Транзитивное замыкание произвольного отношения R — наименьшее транзитивное отношение, содержащее R. Оно строится путём «присоединения» цепочек: если aRb и bRc, добавляется пара (a, c), и процесс повторяется до стабилизации. Транзитивное замыкание отношения «непосредственно предшествует» даёт отношение «предшествует вообще».

¶Транзитивные множества

В аксиоматической теории множеств множество A называется транзитивным, если каждый его элемент является также его подмножеством: ∀x ∈ A ⇒ x ⊆ A. Эквивалентно: A ⊆ 𝒫(A), где 𝒫(A) — множество всех подмножеств A. Например, множество {∅, {∅}} транзитивно: его элементы ∅ и {∅} являются подмножествами.

Транзитивные множества играют важную роль при построении порядков по фон Нейману, где натуральные числа определяются как транзитивные множества, упорядоченные отношением принадлежности ∈. Порядковые числа фон Неймана: 0 = ∅, 1 = {∅}, 2 = {∅, {∅}}, 3 = {∅, {∅}, {∅, {∅}}}. Класс всех транзитивных множеств образует модель теории множеств Зермело — Франкеля.

¶Транзитивность в лингвистике

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

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

¶Транзитивность в теории категорий

В теории категорий морфизм f: A → B называется транзитивным, если он факторизуется через нетранзитивные морфизмы. Конкретнее, морфизм f является транзитивным, если существует нетранзитивный морфизм g: A → C и морфизм h: C → B такие, что f = h ∘ g. Эта концепция используется при классификации объектов по их «размеру» и при построении моделей теории множеств внутри категорий.

¶Применение

Транзитивность лежит в основе понятия порядка. Линейно упорядоченное множество (полный порядок) — множество с транзитивным рефлексивным антисимметричным отношением, в котором любые два элементы сопоставимы. Числовые прямые, словари, хронологические шкалы — примеры линейных порядков.

В теории игр и социальных выборов транзитивность предпочтений игрока означает: если альтернатива A предпочтительнее B, а B предпочтительнее C, то A предпочтительнее C. Нарушение транзитивности предпочтений (_cycle) приводит к «парадоксу голосования» и делает невозможным определение оптимального выбора. Кеннет Эрроу доказал в своей теореме (1951), что при нетранзитивных предпочтениях избирателей агрегация индивидуальных порядков в общественный порядок с разумными свойствами невозможна.

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

¶Интересные факты

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

Понятие транзитивности введено в математическую логику Готлобом Фреге (1879) и развито в работах Бертрана Рассела и Альфреда Уайтхеда «Principia Mathematica» (1910—1913).

Источники:

• Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970.
• Арутюнова Н. Д. Лингвистические проблемы семантики. — М.: Наука, 1988.
• Лавров Ф. А., Максимова Л. Л. Задачи по теории множеств и математической логике. — М.: Наука, 1984.
• Mac Lane S. Categories for the Working Mathematician. — Springer, 1998.
• Arrow K. Social Choice and Individual Values. — Wiley, 1951.