Relacja dobrze ufundowana

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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).

Częściowy porządek (ang. partial order) – relacja zwrotna, przechodnia i antysymetryczna albo równoważnie antysymetryczny praporządek.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} .

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).

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.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, 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.

Linki zewnętrzne[ | edytuj kod]

  • Lawrence S. Moss, Non-wellfounded Set Theory, [w:] Stanford Encyclopedia of Philosophy [online], CSLI, Stanford University, 24 kwietnia 2018, ISSN 1095-5054 [dostęp 2018-08-07] (ang.). (Niedobrze ufundowana teoria mnogości)
  • 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.International Standard Serial Number, ISSN czyli Międzynarodowy Znormalizowany Numer Wydawnictwa Ciągłego – ośmiocyfrowy niepowtarzalny identyfikator wydawnictw ciągłych tradycyjnych oraz elektronicznych. Jest on oparty na podobnej koncepcji jak identyfikator ISBN dla książek, ISAN dla materiałów audio-wideo. Niektóre publikacje wydawane w seriach mają przyporządkowany zarówno numer ISSN, jak i ISBN.




    Reklama