Идемпотентное отношение - Idempotent relation - Wikipedia

В математике идемпотентное бинарное отношение это бинарное отношение р на съемочной площадке Икс (подмножество Декартово произведение Икс × Икс), для которого состав отношений р ∘ р такой же как р.[1][2] Это понятие обобщает понятие идемпотентная функция отношениям.

Определение

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

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

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

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

Примеры

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

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

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

Использует

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

Идемпотентные отношения, определенные на слабо счетно компактные пространства также было показано, что они удовлетворяют "условию Γ": то есть каждое нетривиальное идемпотентное отношение на таком пространстве содержит точки для некоторых . Это используется, чтобы показать, что некоторые подпространства бесчисленного товар пространств, известных как продукты Махавье, не могут быть метризуемый когда определяется нетривиальным идемпотентным отношением.[6]

Рекомендации

  1. ^ Флориан Каммюллер, Дж. В. Сандерс (2004). Идемпотентные отношения в Isabelle / HOL (PDF) (Технический отчет). ТУ Берлин. п. 27. 2004-04. Архивировано из оригинал (PDF) на 2014-05-12. Получено 2014-05-10. Здесь: стр.3
  2. ^ Флориан Каммюллер (2011). «Механический анализ конечных идемпотентных отношений». Fundamenta Informaticae. 107: 43–65. Дои:10.3233 / FI-2011-392.
  3. ^ Гюнтер Шмидт (2011) Реляционная математика, стр. 212, Издательство Кембриджского университета ISBN  978-0-521-76268-7
  4. ^ Флориан Каммюллер (2006). «Количество идемпотентных отношений на n помеченных элементах». Онлайн-эциклопедея целочисленных последовательностей (A12137).
  5. ^ Флориан Каммюллер (2008). Подсчет идемпотентных отношений (PDF) (Технический отчет). ТУ Берлин. п. 27. 2008-15.
  6. ^ Клонц, Стивен; Варагона, Скотт (2018). «Продукты Махавье, идемпотентные отношения и условие Γ». arXiv:1805.06827 [math.GN ].

дальнейшее чтение