Идемпотентные отношения
В математике отношение — это бинарное отношение 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 также является истинным.
- р ∘ р ⊇ р . Эквивалентно, с точки зрения отдельных элементов, для каждых 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]
Ссылки [ править ]
- ^ Флориан Каммюллер, Дж. В. Сандерс (2004). Идемпотентное отношение в Изабель/HOL (PDF) (Технический отчет). ТУ Берлин. п. 27. 2004–04. Архивировано из оригинала (PDF) 12 мая 2014 г. Проверено 10 мая 2014 г. Здесь: стр.3
- ^ Флориан Каммюллер (2011). «Механический анализ конечных идемпотентных отношений» (PDF) . Фундамента информатика . 107 : 43–65. дои : 10.3233/FI-2011-392 .
- ^ Гюнтер Шмидт (2011) Реляционная математика , стр. 212, Cambridge University Press ISBN 978-0-521-76268-7
- ^ Флориан Каммюллер (2006). «Количество идемпотентных отношений на n помеченных элементах» . Интернет-энциклопедия целочисленных последовательностей (A12137).
- ^ Флориан Каммюллер (2008). Подсчет идемпотентных отношений (PDF) (Технический отчет). ТУ Берлин. п. 27. 2008-15.
- ^ Клонц, Стивен; Варагона, Скотт (2018). «Произведения Махавье, идемпотентные отношения и условие Γ». arXiv : 1805.06827 [ мат.GN ].
Дальнейшее чтение [ править ]
- Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010). Коды и автоматы . Энциклопедия математики и ее приложений. Том. 129. Кембридж: Издательство Кембриджского университета . п. 330. ИСБН 978-0-521-88831-8 . Збл 1187.94001 .