W dniu 2012-10-16 22:06, Baranosiu pisze:

>
> To zależy jak się rozumie pojęcie "posortować", bo w CIĄG rosnący to
> się ich ustawić nie da (choć zgoda, każde dwie da się porównać i tak

Nieprzeliczalnego zbioru (jak choćby wspomniany (0,1)) w ogole
nie da się ustawić w _jakikolwiek_ ciąg;-)

> ustawić, że "każda po prawo jest większa od tej po lewej")
> ale... jeśli nie da się ułożyć w ciąg, to też nie da się podać
> algorytmu sortującego, więc... coś za coś, jeśli zluzujemy z definicją
> "posortowany" (niekoniecznie w ciąg) to luzujemy z definicją
> "algorytmu" (rezygnujemy z "sekwencja następujących po sobie
> instrukcji") bo inaczej nie da się przedstawić algorytmu sortowania w
> "nie-ciąg" :D


Nie chodziło mi o to. Przez posortować rozumiałem potencajlną
możliwość ustawianie w sposób posortowany. Nie algorytm.
Ale niech będzie algorytm, jak zauważasz, to nieistotne.

Chodziło mi tylko o mieszanie w to pojęcia dobrego porządku
zbioru. Nie ma ono tu, nieżależnie od wybranej definicji,
żadnego znaczenia.

Każdy porządek liniowy w zbiorach skończonych jest dobry.
I skończone zbiory z liniowym porządkiem ortujemy algorytmem.

Zbór przeliczalny: wszystkie liczby wymierne >0
nie jest dobrze uporządkowany (przy 'naturalnym porządkiem').
Cały zbiór nie ma elementu najmniejszego.

Z drugiej strony, w zbiorze dowolnej mocy istnieje dobry
porządek (twierdzenie z nazwiskiem). Więc możesz mieć
pewną zmodyfikowaną relację <, taką, że porządek jest
dobry. Ale sprawy sortowania to nie zmienia,
potencjalnie możesz je uporządkować, ale ciągom
i algorytmom nie zrobi to różnicy.

pzdr
bartekltg