Идемпотентное отношение

В математике идемпотентное бинарное отношение — это бинарное отношение R на множестве X (подмножестве декартова произведения X  ×  X ), для которого композиция отношений R  ∘  R такая же, как и R. ^{[1] [2]} Это понятие обобщает понятие идемпотентной функции на отношения .

В качестве сокращения запись xRy указывает, что пара ( x , y ) принадлежит отношению R. Композиция отношений R  ∘  R — это отношение S , определяемое установкой xSz как истинного для пары элементов x и z в X всякий раз, когда существует y в X, для которого xRy и yRz оба истинны. R является идемпотентным, если R  =  S.

Эквивалентно, отношение R является идемпотентным тогда и только тогда, когда выполняются следующие два свойства:

• R является транзитивным отношением , что означает, что R  ∘  R  ⊆  R. Эквивалентно, с точки зрения отдельных элементов, для каждых x , y и z, для которых xRy и yRz оба истинны, xRz также истинен.
• R  ∘  R  ⊇  R . Эквивалентно, в терминах отдельных элементов, для каждого x и z , для которых xRz истинно, существует y, для которого xRy и yRz оба истинны. Некоторые авторы называют такое R плотным отношением . [ ^3]

Поскольку идемпотентность включает в себя как транзитивность, так и второе свойство выше, она является более сильным свойством, чем транзитивность.

Например, отношение < на рациональных числах является идемпотентным. Отношение строгого порядка транзитивно, и всякий раз, когда два рациональных числа x и z подчиняются отношению x  <  z, между ними обязательно существует другое рациональное число y (например, их среднее) с x  <  y и y  <  z .

Напротив, то же самое отношение упорядочения < на целых числах не является идемпотентным. Оно все еще транзитивно, но не подчиняется второму свойству идемпотентного отношения. Например, 1 < 2, но не существует никакого другого целого числа y между 1 и 2.

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

Идемпотентные отношения были использованы в качестве примера для иллюстрации применения механизированной формализации математики с использованием интерактивного доказателя теорем Isabelle/HOL. Помимо проверки математических свойств конечных идемпотентных отношений, в Isabelle/HOL был выведен алгоритм подсчета числа идемпотентных отношений. ^{[4] [5]}

Было также показано, что идемпотентные отношения, определенные на слабо счетно компактных пространствах, удовлетворяют «условию Γ»: то есть каждое нетривиальное идемпотентное отношение на таком пространстве содержит точки для некоторых . Это используется для того, чтобы показать, что некоторые подпространства несчетного произведения пространств, известные как произведения Махавье, не могут быть метризуемыми, если определены нетривиальным идемпотентным отношением. ^[6]${\ displaystyle \ langle x, x \ rangle, \ langle x, y \ rangle, \ langle y, y \ rangle}$${\displaystyle x,y}$

• Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010). Коды и автоматы. Энциклопедия математики и ее приложений. Том 129. Кембридж: Cambridge University Press . стр. 330. ISBN 978-0-521-88831-8. Збл  1187.94001.