Jump to content

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

В математике отношение — это бинарное отношение 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]

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: bff73128341c63c5f762e7a35b8dbd9d__1706103060
URL1:https://arc.ask3.ru/arc/aa/bf/9d/bff73128341c63c5f762e7a35b8dbd9d.html
Заголовок, (Title) документа по адресу, URL1:
Idempotent relation - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)