Idempotent relation

I matematik är en idempotent binär relation en binär relation R på en mängd X (en delmängd av kartesisk produkt X × X ) för vilken sammansättningen av relationerna R ∘ R är densamma som R . Denna uppfattning generaliserar den om en idempotent funktion till relationer.

Definition

Som en stenografi indikerar notationen xRy att ett par ( x , y ) tillhör en relation R . Sammansättningen av relationer R ∘ R är relationen S som definieras genom att sätta xSz att vara sann för ett par av element x och z i X närhelst det finns y i X med xRy och yRz båda sanna. R är idempotent om R = S .

På motsvarande sätt är relation R idempotent om och endast om följande två egenskaper är sanna:

R är en transitiv relation , vilket betyder att R ∘ R ⊆ R . På motsvarande sätt, i termer av individuella element, för varje x , y och z för vilka xRy och yRz båda är sanna, är xRz också sant.
R ∘ R ⊇ R . På motsvarande sätt, i termer av individuella element, för varje x och z för vilka xRz är sann, finns det y med xRy och yRz båda sanna. Vissa författare kallar en sådan R för en tät relation .

Eftersom idempotens innehåller både transitivitet och den andra egenskapen ovan, är det en starkare egenskap än transitivitet.

Exempel

Till exempel är relationen < på de rationella talen idempotent. Den strikta ordningsrelationen är transitiv, och närhelst två rationella tal x och z följer relationen x < z finns det nödvändigtvis ett annat rationellt tal y mellan dem (till exempel deras medelvärde) med x < y och y < z .

Däremot är samma ordningsrelation < på heltalen inte idempotent. Den är fortfarande transitiv, men lyder inte den andra egenskapen hos en idempotent relation. Till exempel, 1 < 2 men det finns inget annat heltal y mellan 1 och 2.

En yttre produkt av logiska vektorer bildar en idempotent relation. En sådan relation kan finnas i en mer komplex relation, i vilket fall det kallas ett begrepp i det större sammanhanget. Beskrivningen av relationer i termer av deras begrepp kallas formell begreppsanalys .

Används

Idempotenta relationer har använts som ett exempel för att illustrera tillämpningen av mekaniserad formalisering av matematik med hjälp av den interaktiva satsbevisaren Isabelle/HOL. Förutom att kontrollera de matematiska egenskaperna hos finita idempotenta relationer, har en algoritm för att räkna antalet idempotenta relationer härletts i Isabelle/HOL.

Idempotenta relationer definierade på svagt räknat kompakta utrymmen $har$ också visat sig uppfylla "villkor Γ": det vill säga varje icke-trivial idempotent relation på ett sådant utrymme innehåller punkter $,y\rangle ,\langle y,y\rangle }$ $x,y$ för några . Detta används för att visa att vissa delrum av en oräknelig produkt av utrymmen, kända som Mahavier-produkter, inte kan mätas när de definieras av en icke-trivial idempotent relation.

Vidare läsning

Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Koder och automater . Encyclopedia of Mathematics and its Applications. Vol. 129. Cambridge: Cambridge University Press . sid. 330. ISBN 978-0-521-88831-8 . Zbl 1187.94001 .