Idempotentní vztah - Idempotent relation - Wikipedia

V matematice, an idempotentní binární relace je binární relace R na setu X (podmnožina kartézský součin X × X) pro které složení vztahů R ∘ R je stejné jako R.[1][2] Tento pojem zobecňuje pojem idempotentní funkce na vztahy.

Definice

Jako zkratka notace xRy označuje, že pár (X,y) patří do vztahu R.v složení vztahů R ∘ R je vztah Sdefinováno nastavením xSz to platí pro dvojici prvků X a z v X kdykoli existuje y v X sxRy a yRz oba pravdivé. R je idempotentní, pokud R = S.

Ekvivalentně, vztah R is idempotent if and only if the following two properties are true:

  • R je tranzitivní vztah, znamenající, že R ∘ R ⊆ R. Ekvivalentně, pokud jde o jednotlivé prvky, pro všechny X, y, a z pro který xRy a yRz jsou oba pravdivé, xRz je také pravda.
  • R ∘ R ⊇ R. Ekvivalentně, pokud jde o jednotlivé prvky, pro všechny X a z pro který xRz je pravda, existuje y s xRy a yRz oba pravdivé. Někteří autoři tomu říkají R A hustý vztah.[3]

Protože idempotence zahrnuje jak tranzitivitu, tak druhou vlastnost výše, je to silnější vlastnost než tranzitivita.

Příklady

Například relace racionální čísla je idempotentní. Relace přísného řazení je tranzitivní a vždy, když existují dvě racionální čísla X a z dodržujte vztah X < z nutně existuje další racionální číslo z mezi nimi (například jejich průměr) s X < y a y < z.

Naproti tomu stejný objednávkový vztah celá čísla není idempotentní. Je stále tranzitivní, ale neposlouchá druhou vlastnost idempotentního vztahu. Například 1 <2, ale neexistuje žádné jiné celé číslo y mezi 1 a 2.

An vnější produkt logických vektorů tvoří idempotentní vztah. Takový vztah může být obsažen ve složitějším vztahu, v takovém případě se nazývá a pojem v tomto větším kontextu. Popis vztahů z hlediska jejich pojmů se nazývá formální koncepční analýza.

Použití

Jako příklad byly použity idempotentní vztahy k ilustraci aplikace mechanizované formalizace matematiky pomocí proverátoru interaktivních vět Isabelle / HOL. Kromě kontroly matematických vlastností konečných idempotentních vztahů byl v Isabelle / HOL odvozen algoritmus pro počítání počtu idempotentních vztahů.[4][5]

Idempotentní vztahy definované na slabě spočítatelné kompaktní prostory také bylo prokázáno, že splňují „podmínku Γ“: to znamená, že každý netriviální idempotentní vztah v takovém prostoru obsahuje body pro některé . To slouží k prokázání toho, že jisté podprostory nespočet produkt prostorů, známých jako produkty Mahavier, nemůže být měřitelný když je definován netriviální idempotentní relací.[6]

Reference

  1. ^ Florian Kammüller, J. W. Sanders (2004). Idempotentní vztah v Isabelle / HOL (PDF) (Technická zpráva). TU Berlín. p. 27. 2004-04. Archivovány od originál (PDF) dne 2014-05-12. Citováno 2014-05-10. Zde: str.3
  2. ^ Florian Kammüller (2011). "Mechanická analýza konečných idempotentních vztahů". Fundamenta Informaticae. 107: 43–65. doi:10.3233 / FI-2011-392.
  3. ^ Gunter Schmidt (2011) Relační matematika, strana 212, Cambridge University Press ISBN  978-0-521-76268-7
  4. ^ Florian Kammüller (2006). "Počet idempotentních vztahů na n označených prvcích". Online encyklopedie celočíselných sekvencí (A12137).
  5. ^ Florian Kammüller (2008). Počítání idempotentních vztahů (PDF) (Technická zpráva). TU Berlín. p. 27. 2008-15.
  6. ^ Clontz, Steven; Varagona, Scott (2018). „Výrobky Mahavier, idempotentní vztahy a stav Γ“. arXiv:1805.06827 [matematika. GN ].

Další čtení