Wikiszótár

Tarski-Kuratowski-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈtɒrʃkikurɒtofʃkiɒlɡoritmuʃ]

Főnév

Tarski-Kuratowski-algoritmus

  1. (matematika)

A Tarski-Kuratowski-algoritmus elsősorban matematikai logikai és halmazelméleti kontextusban jelenik meg, különösen a halmazok transzformációjának vizsgálatakor a komplementáció és lezárási műveletek sorozatában. A Tarski-Kuratowski tétel egy híres eredmény a topológia és halmazelmélet területén, amely a halmazok komplementációjával és lezárásával végezhető műveletek számát korlátozza.


Tarski-Kuratowski tétel

Legyen ( X ) egy halmaz, és ( (X) ) az ( X )-en értelmezett hatványhalmaz. Tekintsünk két műveletet:

  1. Komplementáció (( C )): Egy ( A X ) halmaz komplementuma: [ C(A) = X A. ]
  2. Lezárás (( K )): Egy ( A ) halmaz topológiai lezárása a ( X )-en adott topológia szerint.

Ekkor a Tarski-Kuratowski tétel kimondja, hogy:

Legyen ( A ) egy ( X )-beli tetszőleges halmaz. A komplementáció és lezárás műveletek sorozatának segítségével legfeljebb 14 különböző halmaz hozható létre.

A Tarski-Kuratowski-algoritmus lényege

Az algoritmus célja, hogy a komplementáció (( C )) és lezárás (( K )) műveletek egymás utáni alkalmazásával meghatározza az összes lehetséges halmaztranszformációt. Ezeket a transzformációkat egy fastruktúrában lehet ábrázolni.

A Tarski-Kuratowski algoritmus által meghatározott maximum 14 halmaz így jön létre:

  1. Kiindulási halmaz: ( A )
  2. Lehetséges műveletek:
    • ( C(A) ) - komplementum,
    • ( K(A) ) - lezárás,
    • További iterációk a ( C ) és ( K ) műveletekkel.


Lehetséges transzformációk példája

A transzformációk sorozata a következő:

  1. ( A ) - eredeti halmaz,
  2. ( C(A) ) - komplementuma,
  3. ( K(A) ) - lezárása,
  4. ( K(C(A)) ) - komplementum lezárása,
  5. ( C(K(A)) ) - lezárás komplementuma,
  6. ( C(K(C(A))) ) - komplementum lezárásának komplementuma,
  7. ( K(C(K(A))) ) - lezárás komplementum lezárása.

… és így tovább.

A tétel szerint a műveletek sorrendjének minden kombinációja végül legfeljebb 14 különböző halmazhoz vezet.


Példa Python Implementációval

Az alábbi példa egy halmaz és egyszerű műveletek segítségével demonstrálja a Tarski-Kuratowski algoritmus elvét. 

# Alapműveletek: komplementáció és lezárás

def complement(universe, A):
    """A halmaz komplementuma az univerzumban."""
    return universe - A

def closure(A, topology):
    """
    A halmaz topológiai lezárása.
    A lezárás definíciója szerint az A összes nyílt halmazokhoz tartozó lezárt pontjait tartalmazza.
    """
    closure_set = set(A)
    for subset in topology:
        if A <= subset:
            closure_set |= subset
    return closure_set

def tarski_kuratowski_algorithm(universe, A, topology):
    """
    Tarski-Kuratowski-algoritmus implementációja.
    """
    transformations = set()
    queue = [(A, "A")]
    visited = set()
    
    while queue:
        current, name = queue.pop(0)
        if name not in visited:
            visited.add(name)
            transformations.add((name, current))
            
            # Komplementáció
            comp = complement(universe, current)
            queue.append((comp, f"C({name})"))
            
            # Lezárás
            clos = closure(current, topology)
            queue.append((clos, f"K({name})"))
    
    return transformations

# Példa univerzum és topológia
universe = set(range(1, 6))  # Univerzum: {1, 2, 3, 4, 5}
A = {1, 2}                  # Kiindulási halmaz
topology = [{1, 2, 3}, {3, 4, 5}, {1, 2, 3, 4, 5}]  # Egyszerű topológia

# Algoritmus futtatása
results = tarski_kuratowski_algorithm(universe, A, topology)

# Eredmények kiíratása
print("Transzformációk és eredmények:")
for name, result in results:
    print(f"{name}: {result}")

Kimenet

A kimenet a halmazokra alkalmazott összes lehetséges transzformációt fogja tartalmazni, például: 

Transzformációk és eredmények:
A: {1, 2}
C(A): {3, 4, 5}
K(A): {1, 2, 3}
C(K(A)): {4, 5}
K(C(A)): {3, 4, 5}
...

Magyarázat

  1. Komplementáció:
    • A komplementáció a halmaz pontjainak kiegészítését jelenti az univerzumban.
  2. Lezárás:
    • A lezárás a topológia szerint értelmezett “lezárt” pontok összessége.
  3. Iteráció:
    • A komplementáció és lezárás műveletek iterálásával minden lehetséges halmaz létrejön, de a Tarski-Kuratowski tétel szerint ezek száma legfeljebb 14.


Alkalmazások

  • Topológia: Halmazok vizsgálata topológiai terekben.
  • Matematikai logika: Halmazműveletek lehetséges kombinációinak vizsgálata.
  • Automatizmusok: Halmazok állapottereinek transzformációja.

A Tarski-Kuratowski algoritmus különösen szemléletes példát ad a topológiai műveletek és kombinatorikai korlátok megértésére.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Tarski-Kuratowski-algoritmus&oldid=3480705”