Dnia 16.10.2012 M.M. <m...@g...com> napisał/a:
> W dniu wtorek, 16 października 2012 20:39:53 UTC+2 użytkownik notb napisał:
>> Aby sortowanie miało sens (teoretyczny) musi istnieć jakaś metoda
>> porównywania, czyli na zbiorze musi istnieć jakiś porządek liniowy.
>
> No wlasnie jak to bylo? Na pewno nie wystarczy ze istnieje metoda
> porownywania. Typowy przyklad z programow szachowych: program A
> wygrywa z programem B, B wygrywa z C, a C wygrywa z A - da sie
> porownac, ale jak to sensownie posortowac (bez dodatkowych
> zabiegow)?
>

Musi być tzw. dobry porządek liniowy. Porządek liniowy to zbiór z
relacją R, która spełnia 3 własności:
1) zwrotność: aRa (a jest w relacji z a)
2) przechodniość: aRb i bRc => aRc
3) antysymetryczność: jeśli aRb to not(bRa) (jeśli a jest w relacji z
b, to b nie jest w relacji z a)
"Dobry porządek" to porządek liniowy, w którym każdy niepusty podzbiór
danego zbioru ma element najmniejszy (w sensie relacji R).

W podanym przez Ciebie przykładzie szachowym z relacją "lepszy niż"
nie ma elementu "najmniejszego" więc nie jest to dobry porządek
liniowy czyli nie da się posortować zbioru relacją "lepszy niż" :D