Prosty dowod nieprzxeliczalnosci R

[Wlodzimierz Holsztynski]

NOTACJA:

{} -- zbior pusty;
R -- zbior wszystkich liczb rzeczywistych;
N := {1 2 ...} -- zbior wszystkich liczb naturalnych;

< -- uporzadkowanie liniowe, ostre (nieprawda, ze a < a);

\< -- "< lub =".

ins(a; b c) <==> b < a < c lub c < a < b;

liczby a(n) b(n) c(n) x(n) beda rzeczywiste,
natomiast u_n beda naturalne.

========

Prosty dowod nieprzeliczalnosci R
==================================

WSTEP

W ponizszym dowodzie nieprzeliczalnosci zbioru liczb
rzeczywistych R bede korzystal jedynie z pewnych
wlasnosci liniowego uporzadkowania < zbioru R,
a mianowicie z tego, ze R ma dwa rozne elementy:

(B) istnieja a b \in R takie, ze a =/= b;

takze z gestosci:

(G) dla dowolnych a b \in R istnieje c \in R takie,
ze a < c < b lub b < c < a,

i wreszcie z aksjomatu Dedekinda, ktory formuluje ponizej.

================

DEFINCJA Zbiory A B liczb rzeczywistych stanowia
podzial Dedekinda, jezeli:

(i) A =/= {} =/= B;

(ii) A \cup B = R;

(iii) a < b dla kazdego a \in A oraz b \in B.


================
AKSJOMAT (Dedekind) Dla dowolnego podzialu Dedekinda A B
istnieje c \in R takie, ze:

a \< c \< b

dla kazdego a \in A oraz b \in B.
================

W ogole nie bede korzystal z zadnych wlasnosci
arytmetycznych zbioru liczb rzeczywistych; dowod
nie potrzebuje nawet istnienia dodawania i mnozenia.
Uwazam ten dowod za prostszy od dowodu Cantora,
stosowanego do liczb rzeczywistych (natomiast
w kontekscie nierownolicznosci X i 2^X dowod
Cantora jest piekny i tak prosty jak tylko moze byc).

UWAGA Wszystkie powyzsze wlasnosci uporzadkowania
< w R ma takze uporzadkowanie przeciwne >.

KONIEC WSTEPU

================

TWIERDZENIE (Cantor) Niech x : N --> R bedzie dowolna
funkcja roznowartosciowa. Wtedy

{x(n) : n \in N} =/= R.

DOWOD

Mozemy zalozyc, ze x(1) < x(2). W przeciwnym razie
zastapimy uporzadkowanie < przez > i dowod
przeprowadzimy dokladnie tak samo (patrz UWAGA powyzej).

Zdefiniujmy u_1 := 1 oraz u_2 := 2.

Zalozmy (indukcja), ze zdefiniowalismy juz skonczony
ciag liczb naturalnych:

(u_k : k=1 ... n)

dla pewnego n > 1, spelniajacy warunek:

(*) u_(n-1) =/= u_n.

Mamy taki ciag dla n=2. Zdefiniujmy teraz u_(n+1)
jako najmniejsza liczbe naturalna, spelniajaca:

(**) ins(c(n+1); c(n-1) c(n))

gdzie c(k) jest skrotowym zapisem, c(k) := x(u_k);
w szczegolnosci c(1)=x(1) oraz c(2)=x(2).

Liczba u_(n+1) istnieje, bo c(n-1) =/= c(n) oraz
uporzadkowanie w R jest geste. Co wiecej, (**)
oznacza, ze

(*') u_n =/= u_(n+1)

Otrzymalismy zatem, indukcyjnie, nieskonczony ciag
(u_n : n=1 2 ...), spelniajacy (*) dla kazdego
n=2 3 ...

Pokazemy wiecej, ze ciag (u_n) jest rosnacy:

Oczywiscie u_1 < u_2 < u_3. Niech wiec n >/ 3.
Chcemy pokazac, ze u_n < u_(n+1). Z (**) wynika,
ze

(**') ins(c(n); c(n-2) c(n-1))

oraz (z wlasnosci uporzadkowania + (**) + (**")),
ze takze

(**") ins(c(n+1); c(n-2) c(n-1).

Ale u_n bylo najmniejsza liczba naturalna, dla
ktorej zachodzilo (**'). Zatem u_n < u_n+1.

Udowodnilismy, ze ciag liczb naturalnych (u_n)
jest rosnacy. Pokazemy jeszcze ostatnia nierownosc:

(***) c(2*n-1) < c(2*n+1) < c(2*n+2) < c(2*n)

dla dowolnego n=1 2 ...

Dla n=1 wynika to z zalozenia x(1) < x(2),
czyli c(1) < c(2), oraz z zastosowania definicji
indukcyjnej (**) dla n = 2 3. Tak wiec (***)
zachodzi dla n=1. Niech (***) zachodzi dla pewnego
n. W definicji (**) podstawmy za n najpierw
2*n+2, a nastepnie 2*n+3, a otrzymamy (***) dla
n+1 w miejsce n, co zakonczy indukcyjny dowod
nierownosci (***) dla wszystkich n.

Oczywiscie (***) oznacza to samo, co:

c(1) < c(3) < c(5) < ... ... < c(6) < c(4) < c(2)

Zdefiniujmy:

A := {t \in R : t < c(2*n) dla kazdego n \in N}

B := {t \in R : t > c(2*n-1) dla kazdego n \in N}

Zachodza oczywiscie warunki (i) (ii) definicji podzialu
Dedekinda (patrz wyzej, we WSTEPie).

Zalozmy teraz "nie wprost", ze {x(k) : k \in N} = R.
Rozpatrzmy zatem dowolna liczbe rzeczywista x(k).
Jezeli k=u_(2*n-1) to x(k) = c(2*n-1) \in A\B;
a jezeli k=u_(2*n) to x(k) = c_(2*k) \in B\A.

W pozostalych wypadkach istnieje najmniejsze n > 1
takie, ze

u_n < k < u_(n+1).

Wtedy, z definicji (**), mamy:

(#)
x(k) < min(c(n-1) c(n))
lub
x(k) > max(c(n-1) c(n)).

W pierwszym przypadku x(k) \in A\B, w drugim x(k) \in B\A.

To oznacza, ze zbiory A B sa rozlaczne. Teraz juz jest
oczywistym, ze a < b dla kazdego a \in A oraz b \in B;
pokazalismy, ze A B stanowia podzial Dedekinda.

Istnieje zatem c \in R, spelniajace aksjomat Dedekinda:

a \< c \< b dla kazdego a \in A oraz b \in B.

Liczba c rozni sie od dowolnego c(n). A na mocy (#),
patrz kilka linijek wyzej, c takze rozni sie od dowolnej
z pozostalych liczb rzeczywistych x(k). Otrzymalismy
sprzecznosc: c nie jest liczba rzeczywista. Oznacza to,
ze nasze zalozenie "ne wprost" bylo falszywe. A wiec nie
kazda liczba rzeczywista jest postaci x(k).

KONIEC DOWODU.

Pozdrawiam,

Wlodek

PS. Slynne twierdzenia na ogol maja co najmniej kilka
prawdziwie roznych dowodow. W wypadku twierdzenia Cantora
|N|=/=|R| nie napotkalem w publikacjach na zaden inny,
poza "diagonalnym". Sam na sci.math pisalem przed laty,
ze mozna dac inne, na przyklad topologiczne. Mialem o tym
pisac tez na naszej liscie (a moze pisalem)? Wstrzymywal
mnie ruch robaczkowy na naszej liscie, balem sie dlugich
a niemozebnie "cię(ż)kawych" dyskusji. Jednak temat ten
z jednej strony jest fundamentalny, a z drugiej wciaz sie
na naszej liscie pojawia co jakis czas.

[Wlodzimierz Holsztynski]

Przypomne:

TWIERDZENIE (Cantor) |2^X| =/= |X|

DOWOD Niech f : X --> 2^X bedzie dowolna funkcja.
Niech:

D := {x \in X : x \not_in f(x)} (wiec D \in 2^X)

innymi slowy:

x \in D <==> x \not_in f(x)

Z tego powodu D =/= f(x) dla kazdego x \in X.
KONIEC DOWODU

I jak tu nie lubic matematyki? :-)

Pozdrawiam,

Wlodek

[Wlodzimierz Holsztynski]

Pech, ze literowka wystapila akurat w tytule,
w slowie kluczowym (poprawilem powyzej).

Ponadto w waryunku gestosci (G) zabraklo slowa "roznych".
Powinno byc jak w twierdzeniu ponizej.

Pokazalem w notce rozpoczynajacej ten watek
dosyc ogolne twierdzenie:

TWIERDZENIE Niech (X <) bedzie zbiorem czesciowo
uporzdkowanym, spelniajacym trzy warunki:

(B) istnieja a b \in X, takie ze a =/= b;

(G) dla dowolnych roznych a b \in X istnieje x \in X
takie, ze a < x < b lub b < x < a;

(D) aksjomat Dedekinda.

wtedy X jest nieprzeliczalne.

UWAGA Gestosc tak mocno sformulowalem, ze wynika
z niej liniowosc porzadku <. Nalezy unikac takich
sztuczek (chyba, ze sie je objasni), ale nie moglem
sie powstrzymac (wiec objasniam).

Pozdrawiam,

Wlodek

[Wlodzimierz Holsztynski]

NOTACJA

N := {1 2 ...} -- zbior wszystkich liczb naturalnych
(dodatnich liczb calkowitych).

=================================== ==================

Podalem wczesniej dowod ponizszego twierdzenia,
powolujac sie bezposrednio na aksjomat Dedekinda.
Jezeli aksjomat Dedekinda uzyc we wzmocnionej
wersji (ale rownowaznej--w kazdym razie w obecnosci
aksjomatu wyboru), to mozna podac prostszy dowod,
po linii argumentu przedstawionego przez Adama
Gregosiewicza w watku o zbiorach rownolicznych.
Argument ten uogolnie i troche "oczyszcze". Po
podaniu dowodu Twierdzenia, wyprowadze takze
wzmocniona wersje aksjomatu Dedekinda z oryginalnej.

Post by Wlodzimierz Holsztynski
TWIERDZENIE Niech (X <) bedzie zbiorem czesciowo
(B) istnieja a b \in X, takie ze a =/= b;
(G) dla dowolnych roznych a b \in X istnieje x \in X
takie, ze a < x < b lub b < x < a;
(D) aksjomat Dedekinda.
wtedy X jest nieprzeliczalne.

DOWOD. Uzyjmy aksjomatu Dedekinda w nastepujacej
(wzmocnionej) wersji:

(D') Dla dowolnych niepustych podzbiorow A B
zbioru X, takich, ze a < b dla kazdego a \in A
oraz b \in B, istnieje c \in X, spelniajace:

a \< c \< b dla kazdego a \in A oraz b \in B.

Ponadto z (G) natychmiast wynika:

(G') dla dowolnych roznych a b \in X, spelniajacych
a < b, istnieja x y \in X takie, ze a < x < y < b.

Niech (x_n : n \in N} bedzie dowolnym ciagiem elementow
zbioru X.

Skorzystajmy z zalozenia (B), przy czym tak oznaczmy
dwa rozne elementy a b \in X, zeby a < b. Zdefiniujmy:

A_0 := {a} oraz B_0 := {b}

Zdefiniujemy indukcyjnie dwa ciagi niepustych zbiorow
skonczonych (A_n : n \in N) oraz (B_n : n \in N) tak,
zeby zachodzil warunek:

(*) a < b dla kazdego a \in A_n oraz b \in B_n.

Widzimy, ze warunek (*) jest spelniony dla n=0.

Niech dane beda juz zbiory skonczone A_(n-1) B_(n-1),
spelniajace (*). Niech:

a' := max(A_(n-1)) oraz b' := min(B_(n-1)).

Zatem a' < b'. Istnieja wiec elementy x y \in X,
spelniajace a' < u < w < b'. Gdy u < x(n), to
definiujemy:

A_n := A_(n-1) oraz B_n := B_(n-1) \cup {u}.

W przeciwnym wypadku x(n) < w, i definiujemy:

A_n := A_(n-1) \cup {w} oraz B_n := B_(n-1).

Tak wiec A_n B_n sa niepustymi zbiorami skonczonymi,
spelniajacymi oczywiscie (*). Otrzymalismy wiec nieskonczone
ciagi (A_n : n \in N) oraz (B_n : n \in N), przy czym z
ich definicji wynika, ze:

(**) A_(n-1) \subset A_n oraz B_(n-1) \subset B_n;

(***) x(n) < max(A_n) lub min(B_n) < x(n);

dla kazdego n \in N. Niech:

A := Unia(A_n : n \in N) oraz B := Unia(B_n : n \in N)

Oczywiscie x < y dla kazdego x \in A oraz y \in B.
Na mocy wlasnosci (D') istnieje wiec c \in X takie, ze:

x \< c \< y dla kazdego x \in A oraz y \in B.

Oznacza to, na mocy (***), ze c =/= x(n) dla kazdego n \in N.
Zatem rownosc {x(n) : n \in N} = X nie zachodzi dla zadnego
ciagu (x(n) : n \in N). Innymi slowy, X jest nieprzeliczalne.

KONIEC DOWODU

Widzimy, ze powyzszy dowod, w ktorym modyfikuje lekko
idee dzielenia odcinka na 3 rowne czesci, przedstawiona
przez Adama Gregosiewicza, faktycznie jest latwiejszy
od dowodu, ktory sam wczesniej podalem. Jednak wymaga on
uzupelnienia, wciaz nalezy udowodnic:

TWIERDZENIE' (D) ==> (D')

DOWOD Niech (X <) spelnia warunki (B) (G) (D).
Niech A B beda niepustymi podzbiorami zbioru X,
takimi ze a < b dla kazdego a \in A oraz b \in B.
Zbior wszystkich par (A' B') podzbiorow bioru X,
takich, ze:

(di) A \subset A' oraz B \subset B';

(dii) a < b dla kazdego a \in A' oraz b \in B';

jest induktywna, w sensie kontekstu twierdzenia
Kuratowskiego-Zorna, wzgledem uporzadkowania przez
pare inkluzji A' w A" oraz B' w B". Istnieje wiec
wsrod nich para maksymalna (A' B'). Pokazemy, ze
A' \cup B' = X: niech x \in X. Jezeli x < b
dla kazdego b \in B', to para A" := A' \cup {x}
oraz B" := B' tez spelnia (di) (dii). Z maksymalnosci
(A' B') wynika wiec, ze A'=A", czyli x \in A'.

Jezeli nieprawda jest, ze x < b dla kazdego b \in B,
to b0 \< x dla pewnego b0 \in B. Wtedy para A" := A'
oraz B" := B' \cup {x} spelnia (di) (dii). Zatem B'=B",
czyli x \in B'.

Udowodnilismy, ze A' \cup B' = X. Zatem (A' B') jest
podzialem Dedekinda. Istnieje wiec c \in X takie, ze
a \< c \< b dla kazdego a \in A' oraz b \in B';
tym bardziej dla a \in A oraz b \in B. Wiec warunek (D')
zachodzi.

KONIEC DOWODU

Pozdrawiam,

Wlodek