Transitiv stängning

Transitiv stängning i mängdteorin  är en operation på binära relationer . Den transitiva stängningen av en binär relation R på en mängd X är den minsta transitiva relationen på en mängd X som inkluderar R.

Till exempel, om X är en uppsättning människor (både levande och döda), och R är en "är en förälder"-relation, då är den transitiva stängningen av R en "är en förfader"-relation. Om X är mängden flygplatser, och xRy är ekvivalent med "det finns en flygning från x till y", och den transitiva stängningen av R är lika med P, då är xPy ekvivalent med "du kan flyga från x till y med flyg " (även om du ibland måste flyga med transfers)

Exempel

Låt mängd A vara följande uppsättning delar och strukturer:

A = {bult, mutter, motor, bil, hjul, axel}

dessutom kan vissa av delarna och strukturerna användas vid montering av andra strukturer. Förhållandet mellan detaljer beskrivs av relationen R("används direkt i") och består av följande tuplar:

Tabell 1. Relation R.
Transitiv stängning består av tupler (tillagda tupler är markerade med fetstil):

Tabell 2. Den transitiva stängningen av relationen R.

Den uppenbara innebörden av förslutningen R är att beskriva införandet av delar i varandra, inte bara direkt, utan genom deras användning i mellandelar, till exempel används en bult i en bil, eftersom den används i en motor, och en motor används i en bil.