Funkcja wyboru i dobry porządek

[Oxford]

Treść zadania jest następująca:

Czy \(\displaystyle{ f}\) jest funkcją wyboru na zbiorze wszystkich niepustych podzbiorów zbioru \(\displaystyle{ X}\); \(\displaystyle{ A \subseteq X}\)
\(\displaystyle{ X = \mathbb{Q} \cap (0,1) \ni x = \frac{p}{q}}\)
\(\displaystyle{ f(A) = \min_{ x \in A } x}\)

Próba rozwiązania zadania:
Zbiór \(\displaystyle{ X}\) jest zbiorem liczb wymiernych na przedziale \(\displaystyle{ (0,1)}\). Nie da się określić funkcji wyboru na tym zbiorze, gdyż zbiór ten nie jest dobrze uporządkowany: na przykład podzbiór \(\displaystyle{ (0, \frac{1}{2} ) \subseteq X}\) nie posiada elementu najmniejszego.

Możemy jednak uporządkować zbiór \(\displaystyle{ X}\) relacją dobrego porządku w następujący sposób:
\(\displaystyle{ \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, ... , \frac{2}{3}, \frac{2}{4}, \frac{2}{5}, ... , \frac{3}{4}, \frac{3}{5}, \frac{3}{6}, ...}\)

I w tej chwili zwątpiłem. Wydawało mi się, że rozumiem dobry porządek, jednak okazało się, że nie do końca. Czy w takim razie w uporządkowanym przed chwilą zbiorze nie da się już wyznaczyć podzbioru \(\displaystyle{ (0, \frac{1}{2} )}\)?

Postaram się wyjaśnić o co mi chodzi na przykładzie liczb całkowitych.
Wiadomo, że liczby \(\displaystyle{ \mathbb{Z}}\) ze swoim naturalnym porządkiem nie są dobrze uporządkowane. Wybierając podzbiór liczb naturalnych postaci \(\displaystyle{ \{-2, -4, -8, -16, -32, ... \}}\) widzimy, że nie posiada on najmniejszego elementu.

Zbiór liczb naturalnych możemy uporządkować relacją dobrego porządku następująco:
\(\displaystyle{ 0, -1, 1, -2, 2, -3, 3, -4, 4, ...}\)
Z tego wynika, że nie możemy już wybrać z tego zbioru podzbioru \(\displaystyle{ \{-2, -4, -8, -16, -32, ... \}}\). Dlaczego? Czy taki podzbiór nie należy już do tego zbioru?

Moje wątpliwości wynikają zapewne ze złego pojmowania zbioru po tym, jak zostaje on dobrze uporządkowany. Co takiego przeoczyłem?
Będę wdzięczny za każdą pomoc.

[Jan Kraszewski]

Treść zadania jest następująca:

Czy \(\displaystyle{ f}\) jest funkcją wyboru na zbiorze wszystkich niepustych podzbiorów zbioru \(\displaystyle{ X}\); \(\displaystyle{ A \subseteq X}\)
\(\displaystyle{ X = \mathbb{Q} \cap (0,1) \ni x = \frac{p}{q}}\)
\(\displaystyle{ f(A) = \min_{ x \in A } x}\)

Funkcja jest źle zdefiniowana. By rozważać, czy jest ona funkcją wyboru, to powinna być ona postaci \(\displaystyle{ f:P(X)\setminus\{\emptyset\} \rightarrow X}\). A nie jest - czemu jest równe \(\displaystyle{ f(X)}\)? Poza tym co to za pomysł, by definiować funkcję samym wzorem.

Próba rozwiązania zadania:
Zbiór \(\displaystyle{ X}\) jest zbiorem liczb wymiernych na przedziale \(\displaystyle{ (0,1)}\). Nie da się określić funkcji wyboru na tym zbiorze, gdyż zbiór ten nie jest dobrze uporządkowany

Mylisz pojęcia. To, że standardowy porządek na \(\displaystyle{ X}\) nie jest dobry nie ma wpływu na fakt istnienia funkcji wyboru.

Możemy jednak uporządkować zbiór \(\displaystyle{ X}\) relacją dobrego porządku w następujący sposób:
\(\displaystyle{ \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, ... , \frac{2}{3}, \frac{2}{4}, \frac{2}{5}, ... , \frac{3}{4}, \frac{3}{5}, \frac{3}{6}, ...}\)

Oj, chyba nie tak prosto... Zauważyłeś, że \(\displaystyle{ \frac{1}{2}}\) i \(\displaystyle{ \frac{2}{4}}\) to ta sama liczba?

I w tej chwili zwątpiłem. Wydawało mi się, że rozumiem dobry porządek, jednak okazało się, że nie do końca. Czy w takim razie w uporządkowanym przed chwilą zbiorze nie da się już wyznaczyć podzbioru \(\displaystyle{ (0, \frac{1}{2} )}\)?

Postaram się wyjaśnić o co mi chodzi na przykładzie liczb całkowitych.
Wiadomo, że liczby \(\displaystyle{ \mathbb{Z}}\) ze swoim naturalnym porządkiem nie są dobrze uporządkowane. Wybierając podzbiór liczb naturalnych postaci \(\displaystyle{ \{-2, -4, -8, -16, -32, ... \}}\) widzimy, że nie posiada on najmniejszego elementu.

Zbiór liczb naturalnych możemy uporządkować relacją dobrego porządku następująco:
\(\displaystyle{ 0, -1, 1, -2, 2, -3, 3, -4, 4, ...}\)

Rozumiem, że chodziło Ci o zbiór liczb całkowitych.

Z tego wynika, że nie możemy już wybrać z tego zbioru podzbioru \(\displaystyle{ \{-2, -4, -8, -16, -32, ... \}}\). Dlaczego? Czy taki podzbiór nie należy już do tego zbioru?

Co to znaczy "nie możemy już wybrać z tego zbioru podzbioru \(\displaystyle{ \{-2, -4, -8, -16, -32, ... \}}\)"? To stwierdzenie nie bardzo ma sens. Może pomoże Ci spostrzeżenie, że elementem najmniejszym zbioru \(\displaystyle{ \{-2, -4, -8, -16, -32, ... \}}\) w zadanym przez Ciebie dobrym porządku na \(\displaystyle{ \mathbb{Z}}\) jest \(\displaystyle{ -2}\).

Moje wątpliwości wynikają zapewne ze złego pojmowania zbioru po tym, jak zostaje on dobrze uporządkowany. Co takiego przeoczyłem?

Niewykluczone. Choć część tych problemów może się też wiązać z tym, że masz duży kłopot ze ścisłym i wystarczająco formalnym formułowaniem swoich myśli.

JK

[Oxford]

Czyli moje wątpliwości wynikały jednak z nieprawidłowego pojmowania dobrego porządku oraz elementu najmniejszego.

Mylisz pojęcia. To, że standardowy porządek na \(\displaystyle{ X}\) nie jest dobry nie ma wpływu na fakt istnienia funkcji wyboru.

To bardzo ciekawa informacja, nie wiedziałem tego.

Zauważyłeś, że \(\displaystyle{ \frac{1}{2}}\) i \(\displaystyle{ \frac{2}{4}}\) to ta sama liczba?

Tak, zauważyłem. Czy w takim razie prawidłowo uporządkowany relacją dobrego porządku zbiór liczb wymiernych będzie wyglądał w ten sposób?:
\(\displaystyle{ \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, ... , \frac{2}{3}, \frac{2}{5}, \frac{2}{7} ... , \frac{3}{4}, \frac{3}{5}, \frac{3}{7}, ...}\)

Rozumiem, że chodziło Ci o zbiór liczb całkowitych.

Oczywiście

Co to znaczy "nie możemy już wybrać z tego zbioru podzbioru \(\displaystyle{ \{-2, -4, -8, -16, -32, ... \}}\)"? To stwierdzenie nie bardzo ma sens.

Stwierdzenie to jak najbardziej ma sens, jeśli nie wie się tego, co wyjaśnił mi Pan w następnym zdaniu:

Może pomoże Ci spostrzeżenie, że elementem najmniejszym zbioru \(\displaystyle{ \{-2, -4, -8, -16, -32, ... \}}\) w zadanym przez Ciebie dobrym porządku na \(\displaystyle{ \mathbb{Z}}\) jest \(\displaystyle{ -2}\).

Pomogło i to bardzo. Już wyjaśniam w czym tkwił problem.
Tak jak napisałem wcześniej, moje wątpliwości związane były z pojmowaniem zbioru po jego dobrym porządkowaniu, a raczej z elementem najmniejszym takiego zbioru.
Wybierając na przykład podzbiór \(\displaystyle{ {-8, -4, -2}}\) ze zbioru liczb całkowitych uporządkowanych ich naturalnym porządkiem widzimy, że elementem najmniejszym jest tu \(\displaystyle{ -8}\).
Uważałem, że po uporządkowaniu liczb całkowitych relacją dobrego porządku (tak, jak zrobiłem to wcześniej) elementem najmniejszym podzbioru \(\displaystyle{ {-8, -4, -2}}\) nadal jest \(\displaystyle{ -8}\).
Z tego wnioskowałem także, iż nie da się wybrać podzbioru \(\displaystyle{ (0, \frac{1}{2} )}\) zbioru liczb wymiernych po jego dobrym uporządkowaniu, gdyż - jak wiadomo - każdy podzbiór zbioru dobrze uporządkowanego ma element najmniejszy. A taki podzbiór elementu najmniejszego nie posiada.

Okazuje się jednak że istnieje element najmniejszy takiego podzbioru względem zadanego przeze mnie dobrego porządku. Wszystko staje się jasne.

By rozważać, czy jest ona funkcją wyboru, to powinna być ona postaci \(\displaystyle{ f:P(X)\setminus\{\emptyset\} \rightarrow X}\)

Do tej pory uważałem, że funkcja wyboru musi być postaci:
\(\displaystyle{ f:P(X)\setminus\{\emptyset\} \rightarrow P(X)\setminus\{\emptyset\}}\)

Niestety nadal mam problem ze zrozumieniem jak znaleźć funkcję wyboru danego zbioru.
Czy dobrze myślę, że funkcja wyboru dowolnego zbioru jest suriekcją?

Funkcja jest źle zdefiniowana.

Czy wystarczy sprecyzować w treści zadania, że taka funkcja wyboru jest postaci:
\(\displaystyle{ f:P(X)\setminus\{\emptyset\} \rightarrow X}\)?

[Jan Kraszewski]

Czy w takim razie prawidłowo uporządkowany relacją dobrego porządku zbiór liczb wymiernych będzie wyglądał w ten sposób?:
\(\displaystyle{ \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, ... , \frac{2}{3}, \frac{2}{5}, \frac{2}{7} ... , \frac{3}{4}, \frac{3}{5}, \frac{3}{7}, ...}\)

Tak (oczywiście nie zawracając sobie głowy dowodem, dlaczego to jest dobry porządek...).

Do tej pory uważałem, że funkcja wyboru musi być postaci:
\(\displaystyle{ f:P(X)\setminus\{\emptyset\} \rightarrow P(X)\setminus\{\emptyset\}}\)

Funkcją wyboru dla rodziny zbiorów niepustych \(\displaystyle{ \mathcal{A}}\) nazywamy dowolną funkcję \(\displaystyle{ f:\mathcal{A} \rightarrow \bigcup\mathcal{A}}\) o własności \(\displaystyle{ (\forall A\in \mathcal{A})f(A)\in A}\).

Niestety nadal mam problem ze zrozumieniem jak znaleźć funkcję wyboru danego zbioru. Czy dobrze myślę, że funkcja wyboru dowolnego zbioru jest suriekcją?

Zdecydowanie nie.

W ogólności istnienie funkcji wyboru dla dowolnej rodziny zbiorów niepustych jest równoważne aksjomatowi wyboru. Zatem nie jest tak, że zawsze uda Ci się zdefiniować/znaleźć funkcję wyboru. Choć w pewnych szczególnych przypadkach jest to możliwe.

Czy wystarczy sprecyzować w treści zadania, że taka funkcja wyboru jest postaci:
\(\displaystyle{ f:P(X)\setminus\{\emptyset\} \rightarrow X}\)?

Nie. Zauważ, że bez dodatkowego komentarza, funkcja określona zadanym wzorem NIE MOŻE być postaci \(\displaystyle{ f:P(X)\setminus\{\emptyset\} \rightarrow X}\) - ponownie, czemu jest równe \(\displaystyle{ f(X)}\)? Lepiej byłoby dopiero wtedy, gdybyś zaznaczył, że minimum wyznaczasz względem dobrego porządku na \(\displaystyle{ X}\) (a nie standardowego). Tyle, że wtedy to żadna łaska, bo funkcja określona tym wzorem jest funkcją wyboru dla zbioru niepustych podzbiorów dowolnego zbioru dobrze uporządkowanego (z tego spostrzeżenia korzysta dowód faktu, że zasada dobrego uporządkowania pociąga aksjomat wyboru).

JK

[Oxford]

Zatem nie jest tak, że zawsze uda Ci się zdefiniować/znaleźć funkcję wyboru.

No właśnie. Czy w ogóle istnieje funkcja wyboru na rodzinie wszystkich niepustych podzbiorów zbioru \(\displaystyle{ X = \mathbb{Q} \cap (0,1) \ni x = \frac{p}{q}}\)? Może to niezbyt fortunne pytanie, bo na mocy aksjomatu wyboru taka funkcja istnieje. Raczej, czy da się taką funkcję zdefiniować? Chodzi mi oczywiście o sytuację, gdy zbiór ten jest uporządkowany swoim naturalnym porządkiem.
Pytam na wypadek nieco inaczej sformułowanego polecenia, na przykład: "Określ funkcję wyboru w zbiorze niepustych podzbiorów liczb wymiernych w przedziale otwartym \(\displaystyle{ (0,1)}\)."

W jaki sposób należałoby postępować w takim wypadku? Czy jeśli nie został w zadaniu narzucony żaden konkretny porządek zbioru, to czy można najpierw zbiór dobrze uporządkować a następnie wyznaczyć funkcję wyboru?
Chodzi mi o to, że rozpatrując na przykład zbiór liczb wymiernych w przedziale otwartym \(\displaystyle{ (0,1)}\) ze zwoim naturalnym porządkiem, pojawia się problem:
Nie widzę funkcji wyboru tego zbioru, więc nie jestem w stanie udowodnić, że da się ją wyznaczyć. Z drugiej strony nie mogę udowodnić, że taka funkcja nie istnieje, gdyż powołując się na aksjomat wyboru jest to nieprawda. W jaki sposób podejść do takiego zadania?

[Jan Kraszewski]

W jaki sposób należałoby postępować w takim wypadku? Czy jeśli nie został w zadaniu narzucony żaden konkretny porządek zbioru, to czy można najpierw zbiór dobrze uporządkować a następnie wyznaczyć funkcję wyboru?

Można (o ile się uda).

Chodzi mi o to, że rozpatrując na przykład zbiór liczb wymiernych w przedziale otwartym \(\displaystyle{ (0,1)}\) ze zwoim naturalnym porządkiem, pojawia się problem:

Mylisz pojęcia. Funkcja wyboru jest pojęciem mnogościowym, a nie porządkowym. Wobec tego zastanawianie się, czy zbiór ma zadany porządek, czy nie, nie ma sensu - porządek nie ma tu nic do rzeczy. Pytając o funkcję wyboru rozważasz tylko pewną niepustą rodzinę zbiorów. I już.

Nie widzę funkcji wyboru tego zbioru, więc nie jestem w stanie udowodnić, że da się ją wyznaczyć. Z drugiej strony nie mogę udowodnić, że taka funkcja nie istnieje, gdyż powołując się na aksjomat wyboru jest to nieprawda. W jaki sposób podejść do takiego zadania?

Problem jest źle sformułowany. Jeżeli funkcjonujesz w rzeczywistości z aksjomatem wyboru, to funkcja wyboru istnieje zawsze. Zastanawiać się można jedynie, czy potrafisz taką funkcję zdefiniować (określić konstruktywnie), czyli pokazać jej istnienie nie odwołując się do aksjomatu wyboru.

JK

[Oxford]

Mylisz pojęcia. Funkcja wyboru jest pojęciem mnogościowym, a nie porządkowym. Wobec tego zastanawianie się, czy zbiór ma zadany porządek, czy nie, nie ma sensu - porządek nie ma tu nic do rzeczy. Pytając o funkcję wyboru rozważasz tylko pewną niepustą rodzinę zbiorów. I już.

Chodzi mi o to, że na przykład funkcja \(\displaystyle{ f(A) = \min_{ x \in A } x}\) nie jest funkcją wyboru rodziny wszystkich podzbiorów zbioru liczb wymiernych na przedziale \(\displaystyle{ (0,1)}\) ze swoim naturalnym porządkiem.
Jednak gdy zbiór uporządkujemy relacją dobrego porządku, funkcja ta jest funkcją wyboru tego zbioru.
Piszę to w nawiązaniu do zdania:

Lepiej byłoby dopiero wtedy, gdybyś zaznaczył, że minimum wyznaczasz względem dobrego porządku na \(\displaystyle{ X}\) (a nie standardowego).

Mówię o sytuacji, gdy jedyną funkcją wyboru jaką jestem w stanie podać dla danego zbioru jest właśnie funkcja minimum, która - jak Pan napisał wcześniej - jest "funkcją wyboru dla zbioru niepustych podzbiorów dowolnego zbioru dobrze uporządkowanego".

Nadal jednak nie potrafię wyobrazić sobie żadnej funkcji wyboru innej niż funkcja typu minimum czy maximum. Mógłbym prosić o jakiś przykład funkcji wyboru powiedzmy dla rodziny wszystkich podzbiorów liczb naturalnych? (lub jakiegoś innego)

[Jan Kraszewski]

Chodzi mi o to, że na przykład funkcja \(\displaystyle{ f(A) = \min_{ x \in A } x}\) nie jest funkcją wyboru rodziny wszystkich podzbiorów zbioru liczb wymiernych na przedziale \(\displaystyle{ (0,1)}\) ze swoim naturalnym porządkiem.

Zrozum, że \(\displaystyle{ f(A) = \min_{ x \in A } x}\) to nie funkcja, tylko wzór. Więc Twoje rozważania nie bardzo mają sens.

Nadal jednak nie potrafię wyobrazić sobie żadnej funkcji wyboru innej niż funkcja typu minimum czy maximum.

Weź sobie nieskończoną rodzinę par butów i funkcję wyboru, która z każdej pary wybiera lewy but.

JK

[Oxford]

Widzę, że sprawa jest bardziej skomplikowana niż mi się wydawało.

\(\displaystyle{ f(A) = \min_{ x \in A } x}\) to nie funkcja, tylko wzór.

Co to znaczy? Chodzi o nieprawidłowy zapis? Miałem na myśli funkcję, która z każdego zbioru rodziny zbiorów wybierze element najmniejszy (konkretny zbiór z rodziny zbiorów określony jest we wzorze jako \(\displaystyle{ A}\)).
Wszystkie zbiory z tej rozpatrywanej przeze mnie rodziny zbiorów są podzbiorami jakiegoś zbioru dobrze uporządkowanego.
Skoro każdy zbiór z rodziny wszystkich podzbiorów zbioru dobrze uporządkowanego posiada element najmniejszy to pomyślałem, że można wybrać wszystkie elementy najmniejsze zbiorów. Funkcja, która by to robiła byłaby funkcją wyboru na tejże rodzinie. Jeśli nie widzę żadnej innej funkcji wyboru na rodzinie zbiorów to przynajmniej taką jestem w stanie wskazać.

Wszystko, co napisałem wyżej jest w zasadzie interpretacją tego zdania:

funkcja określona tym wzorem jest funkcją wyboru dla zbioru niepustych podzbiorów dowolnego zbioru dobrze uporządkowanego

Chyba, że "tym wzorem" wcale nie oznacza \(\displaystyle{ f(A) = \min_{ x \in A } x}\).
Podejdźmy do problemu od strony praktycznej. Jeżeli na egzaminie zostanę poproszony o podanie funkcji wyboru na przykład dla rodziny wszystkich podzbiorów liczb naturalnych, to zgodnie z zacytowanym wyżej zdaniem mogę podać funkcję minimum.

[Jan Kraszewski]

Widzę, że sprawa jest bardziej skomplikowana niż mi się wydawało.

\(\displaystyle{ f(A) = \min_{ x \in A } x}\) to nie funkcja, tylko wzór.

Co to znaczy? Chodzi o nieprawidłowy zapis? Miałem na myśli funkcję, która z każdego zbioru rodziny zbiorów wybierze element najmniejszy (konkretny zbiór z rodziny zbiorów określony jest we wzorze jako \(\displaystyle{ A}\)).
Wszystkie zbiory z tej rozpatrywanej przeze mnie rodziny zbiorów są podzbiorami jakiegoś zbioru dobrze uporządkowanego.
Skoro każdy zbiór z rodziny wszystkich podzbiorów zbioru dobrze uporządkowanego posiada element najmniejszy to pomyślałem, że można wybrać wszystkie elementy najmniejsze zbiorów. Funkcja, która by to robiła byłaby funkcją wyboru na tejże rodzinie. Jeśli nie widzę żadnej innej funkcji wyboru na rodzinie zbiorów to przynajmniej taką jestem w stanie wskazać.

Jeżeli chcesz zdefiniować funkcję, to najpierw musisz podać jej dziedzinę i przeciwdziedzinę, a potem ją określić, np. wzorem.
Jeżeli używasz wzoru \(\displaystyle{ f(A) = \min_{ x \in A } x}\), gdzie minimum chcesz liczyć względem standardowego porządku na \(\displaystyle{ X=(0,1)\cap\mathbb{Q}}\), to co jest jej dziedziną i przeciwdziedziną? Jeśli za dziedzinę przyjmiesz rodzinę wszystkich niepustych podzbiorów \(\displaystyle{ X}\), to żeby funkcja była dobrze określona, to za przeciwdziedzinę musisz przyjąć (przynajmniej) przedział \(\displaystyle{ [0,1]}\) (bo taki jest zbiór wartości takiej funkcji). A to wyklucza rozpatrywanie tej funkcji jako funkcji wyboru rodziny \(\displaystyle{ P(X) \setminus \left\{ \emptyset\right\}}\).

Podejdźmy do problemu od strony praktycznej. Jeżeli na egzaminie zostanę poproszony o podanie funkcji wyboru na przykład dla rodziny wszystkich podzbiorów liczb naturalnych, to zgodnie z zacytowanym wyżej zdaniem mogę podać funkcję minimum.

W tym przypadku tak.

JK