• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Relacja dobrze ufundowana

    Przeczytaj także...
    Cykl prosty to droga zamknięta, czyli taka, której koniec (ostatni wierzchołek) jest identyczny z początkiem (pierwszym wierzchołkiem).Ciąg – w matematyce pojęcie oddające intuicję ponumerowania, czy też uporządkowania elementów zbioru. W zależności od rodzaju elementów zbioru stosuje się różne nazwy: w przypadku liczb mówi się o ciągach liczbowych, bądź bardziej precyzyjnie, np. w przypadku zbioru liczb całkowitych, rzeczywistych czy zespolonych, ciąg nazywa się wtedy odpowiednio ciągiem całkowitoliczbowym, rzeczywistym i zespolonym. Jeśli elementami zbioru są funkcje, to ciąg nazywa się ciągiem funkcyjnym. Ciąg powstały poprzez wybranie elementów innego ciągu nazywa się podciągiem.
    Częściowy porządek (ang. partial order) – relacja zwrotna, przechodnia i antysymetryczna albo równoważnie antysymetryczny praporządek.

    Relacja dobrze ufundowanarelacja (zwykle częściowy porządek), dla której nie istnieje nieskończony zstępujący ciąg (każdy element tego ciągu jest w tej relacji z następującym bezpośrednio po nim).

    Relacja słabo konfluentna to relacja taka, że dla dowolnych a , b , c {displaystyle a,b,c} takich że a {displaystyle a} jest w relacji z b {displaystyle b} i a {displaystyle a} jest w relacji z c {displaystyle c} , istnieją takie ciągi skończone zaczynające się odpowiednio od b {displaystyle b} i c {displaystyle c} , które mają wspólny element końcowy d {displaystyle d} .Porządek liniowy – częściowy porządek będący zarazem łańcuchem, czyli taki, w którym każde dwa elementy rozpatrywanego zbioru są porównywalne.

    Jeśli relacja ma dowolny cykl, to nie jest dobrze ufundowana, ponieważ można wybierać po kolei elementy tego cyklu. Jeśli relacja jest skończona i nie ma cykli, to jest dobrze ufundowana.

    Dla nieskończonych relacji dobrze ufundowanych często można znaleźć dowolnie długą ścieżkę skończoną, na przykład dla porządku na możemy wybrać dowolnie duży element początkowy i ciąg malejący o jeden (na przykład 10-elementowy: 9, 8, 7, 6, 5, 4, 3, 2, 1, 0).

    Dobry porządek na danym zbiorze X {displaystyle X} to porządek liniowy na X {displaystyle X} taki, że każdy niepusty podzbiór zbioru X {displaystyle X} ma element najmniejszy (ze względu na ten porządek).Relacja – w teorii mnogości dowolny podzbiór iloczynu kartezjańskiego skończonej liczby zbiorów; definicja ta oddaje intuicję pewnego związku, czy zależności między elementami wspomnianych zbiorów (elementy wspomnianych zbiorów pozostają w związku albo łączy je pewna zależność, czy też własność lub nie). Najważniejszymi relacjami są relacje dwuargumentowe, tj. między elementami pary zbiorów (opisane w osobnym artykule, w tym funkcje i działania jednoargumentowe); relacje jednoargumentowe to po prostu podzbiory pewnego zbioru.

    Relacja, która jest dobrze ufundowana i słabo konfluentna, jest silnie konfluentna.

    Relacja, która jest dobrze ufundowana i spełnia warunki porządku liniowego, jest dobrym porządkiem.




    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.039 sek.