Zasada wyborów zależnych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Zasada wyborów zależnych (także DC od ang. dependent choice) – konsekwencja aksjomatu wyboru, która bywa często przyjmowana za dodatkowy aksjomat (istotnie słabszy od aksjomatu wyboru) do aksjomatyki Zermelo-Fraenkla (ZF). Dokładniej, DC to zdanie:

Niech X będzie zbiorem oraz niech RX × X będzie taką relacją, że dla każdego xX istnieje takie yX, że (x, y) ∈ R. Wówczas istnieje taki ciąg (xn) elementów zbioru X, że dla dowolnej liczby naturalnej n zachodzi (xn, xn+1) ∈ R.

DC a ZF[edytuj | edytuj kod]

  • Zasada wyborów zależnych implikuje przeliczalny pewnik wyboru, tzn. istnienie funkcji wyboru dla dowolnej przeliczalnej rodziny zbiorów niepustych.
Dowód. Niech (Sn) będzie ciągiem zbiorów niepustych. Niech S oznacza sumę rozłączną rodziny (Sn), tj. zbiór par (x, n), gdzie xSn, n - liczba naturalna. W zbiorze S można zdefiniować relację RS × S poprzez warunek
(x, n) R (y, m) wtedy i tylko wtedy, gdy m = n +1.
Jeżeli (x, n) ∈ S, to (x, n) R (y, n + 1), gdzie y jest dowolnym elementem Sn+1, a więc można zastosować w stosunku do R zasadę wyborów zależnych. Oznacza to, że istnieje taki ciąg ((xn, Mn)) elementów S, że (xn, Mn) R (xn+1, Mn+1). Ponadto, stosując indukcję matematyczną można pokazać, że Mn = M + n dla każdej liczby naturalnej n i pewnej liczby M. W szczególności, xnSn + M dla każdej liczby naturalnej n. Iloczyn kartezjański S1 × S1 × ... × SM jest niepusty; niech (y1, y2, ..., yM) będzie jego dowolnym elementem. Ostatecznie, funkcja f: {1, 2, 3, ... } → ∪n Sn dana wzorem f(n) = yn, gdy nM oraz f(n) = xM - n, gdy n > M jest funkcją wyboru dla rodziny (Sn). □

Przypisy

  1. C.E. Blair, The Baire category theorem implies the principle of dependent choices, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 25 (1977), no. 10, 933–934.

Bibliografia[edytuj | edytuj kod]