Kratownica zbioru liczb całkowitych

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Kratownica zbioru liczb całkowitych

Post autor: Jakub Gurak »

Udało się, przynajmniej częściowo, rozwiązać pewne ciekawe zadanie. Oto jego treść:

Na ile sposobów można ułożyć proste na płaszczyźnie, tak aby one wszystkie razem przechodziły już przez wszystkie punkty kratowe płaszczyzny, i tak aby dwie różne proste nie przecinały się w punkcie kratowym (mogą się przecinać na płaszczyźnie poza punktem kratowym)?? Ściślej rzecz biorąc:

Rozważmy kratownicę \(\displaystyle{ \ZZ \times \ZZ.}\) Rozważmy rodzinę wszystkich prostych na płaszczyźnie, tzn. niech:

\(\displaystyle{ \mathbb {S}=\left\{ l \subset \RR^{2}: \ \ l \hbox { jest prostą w } \RR ^{2} \right\} }\),

tzn. chodzi o wykresy wszystkich funkcji liniowych oraz proste pionowe postaci \(\displaystyle{ l:x=a,}\) gdzie \(\displaystyle{ a \in\RR.}\)

Niech \(\displaystyle{ \mathbb {A}}\) będzie rodziną wszystkich przekrojów takich prostych z naszą kratownicą, tzn. niech:

\(\displaystyle{ \mathbb {A}=\left\{ l \cap\left( \ZZ \times \ZZ\right): \ l \in \mathbb {S}\right\}. }\)

Niech \(\displaystyle{ \mathbb {B}}\) będzie rodziną wszystkich rozkładów naszej kratownicy na zbiory z rodziny \(\displaystyle{ \mathbb {A},}\) tzn. niech:

\(\displaystyle{ \mathbb {B}= \left\{ \mathcal {R}: \ \mathcal {R} \hbox { jest rozkładem zbioru } \ZZ \times \ZZ \hbox{ i } \mathcal {R} \subset \mathbb {A} \right\} .}\)

I pytamy o moc rodziny \(\displaystyle{ \mathbb {B}.}\)

Wykażemy, że ta moc jest co najmniej przeliczalna.
DOWÓD TEGO FAKTU::    
A więc takich rozkładów mamy co najmniej przeliczalnie wiele. Pytanie teraz czy takich rozkładów może nie być więcej, tego nie wiem, ktoś może wie??


Udowodniłem też wczoraj, że kratownicę \(\displaystyle{ \ZZ \times \ZZ}\) można rozlożyć na zbiory będące przekrojami okręgów z tą kratownicą, tzn.:

Niech:

\(\displaystyle{ \mathbb{S}= \left\{ \hbox{ OKRĘGI PŁASZCZYZNY}{ }\right\},}\)

( rozważamy tu też okręgi o promieniu równym \(\displaystyle{ 0}\)).

Niech \(\displaystyle{ \mathbb{A}}\) będzie rodziną wszystkich przekrojów takich okregów z naszą kratownicą, tzn. niech:

\(\displaystyle{ \mathbb{A}= \left\{ O \cap \left( \ZZ \times \ZZ\right)\Bigl| \ \ O\in \mathbb{S} \right\} .}\)

Wykażemy, że zbiór \(\displaystyle{ \ZZ \times \ZZ}\) można rozłożyć na zbiory z rodziny \(\displaystyle{ \mathbb{A}}\), czyli można utworzyć taki rozkład \(\displaystyle{ \mathcal{R}}\), taki, że: \(\displaystyle{ \mathcal{R}\subset \mathbb{A}.}\)

Nim to udowodnimy, przypomnijmy dość prosty fakt, że jeżeli mamy niepusty zbiór \(\displaystyle{ X}\) oraz rozkład \(\displaystyle{ \mathcal{R}}\) zbioru \(\displaystyle{ X}\), oraz niepusty podzbiór \(\displaystyle{ Y\subset X}\), to rodzina wszystkich niepustych podzbiorów zbioru \(\displaystyle{ Y}\), które są postaci \(\displaystyle{ A= B \cap Y}\), gdzie \(\displaystyle{ B \in \mathcal{R}}\), rodzina takich przekrojów mnogościowych, tworzy rozkład podzbioru \(\displaystyle{ Y}\)- jest to prosty fakt.

Przejdźmy do dowodu naszego faktu:

DOWÓD TEGO FAKTU:

Zauważmy, że płaszczyznę \(\displaystyle{ \RR ^{2}}\) można rozłożyć na okręgi o środku w punkcie \(\displaystyle{ \left( 0,0\right)}\)- wystarczy rozwazyć rodzinę wszystkich okręgów o środku w początku układu i promieniach nieujemnych (wliczając w to okrąg o promieniu \(\displaystyle{ 0}\)).

Niech \(\displaystyle{ \mathcal{R}}\) bęzie takim rozkładem płaszczyzny. Wtedy dla rodziny:
\(\displaystyle{ \mathcal{R}'= \left\{ O \cap\left( \ZZ \times \ZZ\right)\Bigl| \ \ O\in \mathcal {R} \right\} \setminus \left\{ \emptyset\right\}}\),
Ponieważ \(\displaystyle{ \ZZ \times \ZZ\subset \RR \times \RR= \RR ^{2}}\), i mamy rozkład płaszczyzny na okręgi, stosując zatem przytoczony fakt otrzymujemy, że rodzina \(\displaystyle{ \mathcal{R}' }\) jest rozkładem zbioru \(\displaystyle{ \ZZ \times \ZZ.}\)

A ponieważ \(\displaystyle{ \mathcal{R}}\) jest rodziną okręgów, więc \(\displaystyle{ \mathcal{R}' \subset \mathbb{A}.\square}\) :D

Interesuje mnie jeszcze: na ile sposobów kratownicę \(\displaystyle{ \ZZ \times \ZZ}\) można rozłożyć na zbiory będące brzegami prostokątów, będzie można pomyśleć nad tym . 8-) :lol:
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Kratownica zbioru liczb całkowitych

Post autor: Jakub Gurak »

Udało się to przedwczoraj zbadać.
Udało się też dzień wcześniej zbadać na ile sposobów kratownicę \(\displaystyle{ \NN \times \NN}\) można rozłożyć na zbiory będące brzegami prostokątów (a właściwie na zbiory bedące przekrojami takich brzegów z naszą kratownicą), jak i udowodniłem przedwczoraj, że istnieje tyle samo, co odpowiednich rozkładów \(\displaystyle{ \NN \times \NN}\)- jest tyle samo rozkładów kratownicy zbioru liczb całkowitych ujemnych wraz z zerem, czyli zbioru \(\displaystyle{ \left( \ZZ_- \cup \left\{ 0\right\} \right) \times \left( \ZZ_- \cup \left\{ 0\right\} \right)}\) na zbiory będące brzegami prostokątów. Przedstawię teraz dowody tych ciekawych faktów( ale w skrócie, gdyż w sumie spisałem \(\displaystyle{ 21}\) kartek, co najmniej kilka stron jest niepotrzebnych (złe kierunki dowódów), ale większość jest potrzebna, ale szkoda żebym się tu produkował, jak i tak nikt nie będzie tego czytał), więc może w skrócie:


Podajmy najpierw dwa lematy.

Niech:

\(\displaystyle{ \mathbb{B}= \left\{ A \subset \NN: \ \ A \hbox{ jest przedziałem skończonym, i } \left| A\right| \ge 2 \right\} ,}\)

jest to rodzina wszystkich skończonych, co najmniej dwuelementowych przedziałów w \(\displaystyle{ \left( \NN, \le \right).}\)

Niech:

\(\displaystyle{ \mathbb{S}= \left\{ A \times \left\{ 0,1\right\}\Bigl| \ \ A \in \mathbb{B} \right\} .}\)

Niech \(\displaystyle{ \mathbb{A}}\) będzie rodziną wszystkich rozkładów zbioru \(\displaystyle{ \NN \times \left\{ 0,1\right\}}\) , na zbiory z rodziny \(\displaystyle{ \mathbb{S}}\), tzn. niech:

\(\displaystyle{ \mathbb{A}= \left\{ \mathcal{R}: \ \ \mathcal{R}\hbox{ jest rozkładem zbioru } \NN \times \left\{ 0,1\right\} \hbox{ i } \mathcal{R} \subset \mathbb{S}\right\}.}\)

I pytamy o moc rodziny \(\displaystyle{ \mathbb{A}.}\)

Aha, wpierw zbadamy moc rodziny \(\displaystyle{ \mathbb{D}}\), danej jako:

\(\displaystyle{ \mathbb{D}=\left\{ \mathcal{R}: \ \mathcal{R} \hbox{ jest rozkładem zbioru } \NN \hbox{ na przedziały, i } \mathcal{R} \subset \mathbb{B} \right\}.}\)

Czyli zbadamy moc wszystkich rozkładów zbioru liczb naturalnych na skończone, co najmniej dwuelementowe przedziały.

W tym celu, dla dowolnej funkcji \(\displaystyle{ f \in 2 ^{\NN}= \left\{ 0,1\right\} ^{\NN},}\) tzn. dla funkcji \(\displaystyle{ f: \NN \rightarrow \left\{ 0,1 \right\}}\), definiujemy rozkład \(\displaystyle{ \mathcal{R}_f}\), w taki sposob, że:

jeśli \(\displaystyle{ f(n)=0}\), to \(\displaystyle{ \left\{ 4n, 4n+1,4n+2,4n+3\right\} \in \mathcal{R}_f, }\)

a jeśli \(\displaystyle{ f(n)=1}\), to \(\displaystyle{ \left\{ 4n, 4n+1\right\}; \left\{ 4n+2, 4n+3\right\} \in \mathcal{R}_f.}\)

Formalniej:

\(\displaystyle{ \mathcal{R}_f = \bigcup_{n: f(n)=0} \left\{ \left\{ 4n, 4n+1, 4n+2, 4n+3\right\} \right\} \cup \bigcup_{n: f(n)=1} \left\{ \left\{ 4n,4n+1\right\} \right\} \cup \bigcup_{n: f(n)=1} \left\{ \left\{ 4n+2, 4n+3\right\} \right\}.}\)

Zauważmy najpierw, że \(\displaystyle{ \mathcal {R}_f}\) jest rodziną podzbiorów zbioru \(\displaystyle{ \NN.}\)

Musimy wykazać, że \(\displaystyle{ \bigcup\mathcal{R}_f =\NN.}\)

Nim to zrobimy, to przypomnijmy, że jak mamy trzy rodziny zbiorów \(\displaystyle{ \mathbb{X}, \mathbb{Y}}\) i \(\displaystyle{ \mathbb{Z}}\), to mamy prawo:

\(\displaystyle{ \bigcup\left( \mathbb{X} \cup \mathbb{Y} \cup \mathbb{Z}\right) = \left( \bigcup\mathbb{X}\right) \cup \left( \bigcup\mathbb{Y}\right) \cup \left( \bigcup\mathbb{Z}\right),}\)

suma uogólniona takiej potrójnej rodziny zbiorów \(\displaystyle{ \left( \mathbb{X} \cup \mathbb{Y} \cup \mathbb{Z}\right) }\) jest równa sumie trzech zbiorów: zbioru będącego sumą pierwszej rodziny zbiorów, jaki i zbioru będącego sumą drugiej rodziny zbiorów i zbioru będącego sumą trzeciej rodziny- jest to podstawowy fakt.

A zatem:

\(\displaystyle{ \bigcup\mathcal{R}_f= \bigcup \bigcup_{n: f(n)=0} \left\{ \left\{ 4n, 4n+1, 4n+2, 4n+3\right\} \right\} \cup \bigcup \bigcup_{n: f(n)=1} \left\{ \left\{ 4n, 4n+1\right\} \right\} \cup \bigcup \bigcup_{n: f(n)=1} \left\{ \left\{ 4n+2, 4n+3\right\} \right\}= \\ = \bigcup_{n: f(n)=0} \bigcup \left\{ \left\{ 4n,4n+1, 4n+2, 4n+3 \right\} \right\} \cup \bigcup_{n: f(n)=1} \bigcup \left\{ \left\{ 4n, 4n+1\right\} \right\} \cup \bigcup_{n: f(n)=1} \bigcup \left\{ \left\{ 4n+2, 4n+3\right\} \right\} \stackrel{ \bigcup \left\{ A\right\} =A }{=} \\ = \bigcup_{n: f(n)=0} \left\{ 4n, 4n+1, 4n+2, 4n+3\right\} \cup \bigcup_{n: f(n)=1} \left\{ 4n, 4n+1\right\} \cup \bigcup_{n: f(n)=1} \left\{ 4n+2, 4n+3\right\} = \\ = \bigcup_{n: f(n)=0} \left\{ 4n, 4n+1, 4n+2, 4n+3\right\} \cup \bigcup_{n: f(n)=1} \left( \left\{ 4n ,4n+1\right\} \cup \left\{ 4n+2, 4n+3\right\} \right)= \\ = \bigcup_{n: f(n)=0} \left\{ 4n, 4n+1, 4n+2, 4n+3\right\} \cup \bigcup_{n: f(n)=1} \left\{ 4n, 4n+1, 4n+2, 4n+3\right\}\stackrel{ \bigcup\left( \mathbb{A} \cup \mathbb{B}\right) = \left( \bigcup\mathbb{A}\right) \cup \left( \bigcup \mathbb{B}\right) }{=} \\ = \bigcup \left[ \left\{ \left\{ 4n ,4n+1, 4n+2, 4n+3\right\} : \ n\in\NN: f(n)=0 \right\} \cup \left\{ \left\{ 4n,4n+1, 4n+2, 4n+3\right\}: \ n: f(n)=1 \right\} \right] =}\)

a więc sumujemy zbiory zadane tym samym wzorem, w jednym przypadku po liczbach naturalnych \(\displaystyle{ n}\) takich, że \(\displaystyle{ f(n)=0}\), a w drugim przypadku po liczbach \(\displaystyle{ n}\) takich, że \(\displaystyle{ f(n)=1}\), czyli w pierwszym przypadku sumujemy po \(\displaystyle{ n \in \stackrel { \rightarrow } {f ^{-1} } \left\{ 0\right\}}\) , a w drugim przypadku sumujemy po \(\displaystyle{ n \in \stackrel { \rightarrow } {f ^{-1} } \left\{ 1\right\} }\). Ponieważ, dla funkcji między dwoma zbiorami, dla dwóch podzbiorów przeciwdziedziny funkcji, wtedy przeciwobraz sumy tych dwóch podzbiorów jest sumą przeciwobrazów, więc sumujemy tutaj po \(\displaystyle{ n \in \stackrel{ \rightarrow }{f ^{-1} } \left\{ 0,1\right\}}\), a więc ta suma mnogościowa jest równa:

\(\displaystyle{ \bigcup \left\{ \left\{ 4n, 4n+1, 4n+2, 4n+3\right\} : \ n: f(n) \in \left\{ 0,1\right\} \right\} \stackrel{f: \NN \rightarrow \left\{ 0,1\right\} } = \bigcup \left\{ \left\{ 4n, 4n+1, 4n+2, 4n+3\right\}: \ n\in\NN \right\} = \bigcup_{n \in \NN} \left\{ 4n, 4n+1, 4n+2, 4n+3\right\} = \\ =\left\{ 0,1,2,3\right\} \cup \left\{ 4,5,6,7\right\} \cup \left\{ 8,9,10,11\right\} \cup \ldots =\NN.}\)

Czyli:

\(\displaystyle{ \bigcup\mathcal {R} _f= \NN.}\)

I oczywiście rodzina \(\displaystyle{ \mathcal{R}_f}\) jest rodziną zbiorów rozłącznych.

I jest to rodzina zbiorów niepustych.

A zatem rodzina \(\displaystyle{ \mathcal{R}_f}\) jest rozkładem zbioru \(\displaystyle{ \NN.}\)

I \(\displaystyle{ \mathcal{R} _ f}\) jest rodziną przedzaiłów dwu- lub czteroelementowych.

A zatem \(\displaystyle{ \mathcal{R}_f \subset \mathbb{B}}\), i \(\displaystyle{ \mathcal{R}_f \in \mathbb{D}.}\)

I w ten sposób otrzymujemy funkcję:

\(\displaystyle{ f \in 2 ^{\NN} = \left\{ 0,1\right\} ^{\NN} \stackrel{ \alpha } { \rightarrow } \mathcal{R}_f \in \mathbb{D}}\).

I, łatwo jest pokazać, że dla dowolnych dwóch różnych funkcji \(\displaystyle{ f,g \in 2 ^{\NN}}\) otrzymujemy różne rozkłady, a zatem funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

A zatem \(\displaystyle{ \left| \mathbb{D}\right| \ge \left| 2 ^{\NN} \right| = \left| \RR\right|.\square}\)


Nim przejdziemy dalej, przypomnijmy, że jak mamy dwa zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), oraz dwa rozkłady \(\displaystyle{ \mathbb{B}_X}\) i \(\displaystyle{ \mathbb{B}_Y}\) zbiorów odpowiednio \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), to rodzina zbiorów postaci \(\displaystyle{ A \times B}\), gdzie \(\displaystyle{ A \in \mathbb{B}_X}\) i \(\displaystyle{ B \in \mathbb{B}_Y}\) tworzy rozkład zbioru \(\displaystyle{ X \times Y-}\) jest to dość prosty fakt.

Niech:

\(\displaystyle{ \mathbb{S} = \left\{ A \times \left\{ 0,1\right\}\Bigl| \ \ A \in \mathbb{B} \right\} .}\)

Niech \(\displaystyle{ \mathbb{A}}\) będzie rodziną wszystkich rozkładów zbioru \(\displaystyle{ \NN \times \left\{ 0,1\right\}}\) na zbiory z rodziny \(\displaystyle{ \mathbb{S}}\), tzn. niech:

\(\displaystyle{ \mathbb{A}= \left\{ \mathcal{R}: \ \mathcal{R} \hbox{ jest rozkładem zbioru } \NN \times \left\{ 0,1\right\} \hbox{, i } \mathcal{R} \subset \mathbb{S} \right\}.}\)

I pytamy o moc rodziny \(\displaystyle{ \mathbb{A}}\).

Wykażemy, że:

\(\displaystyle{ \left| \mathbb{A}\right| \ge \left| \RR\right|.}\)

DOWÓD TEGO FAKTU:

Definiujemy funkcję \(\displaystyle{ \alpha : \mathbb{D} \rightarrow \mathbb{A}}\), gdzie \(\displaystyle{ \mathbb{D}}\) jest rozważaną wcześniej rodziną rozkładów zbioru liczb naturalnych ( o której wiemy, że ma moc co najmniej continuum).

Jeśli \(\displaystyle{ \mathcal{R} \in \mathbb{D}}\), wtedy \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \NN}\) na przedziały, i \(\displaystyle{ \mathcal{R} \subset \mathbb{B}}\). Niech:

\(\displaystyle{ \mathcal{R}'= \left\{ A \times \left\{ 0,1\right\} \Bigl| \ \ A \in \mathcal{R} \right\},}\)

Ponieważ, dla zbioru \(\displaystyle{ \left\{ 0,1\right\}}\) , rodzina jednozbiorowa \(\displaystyle{ \mathcal{R} _{\left\{ 0,1\right\} } := \left\{ \left\{ 0,1\right\} \right\} }\) jest rozkładem zbioru \(\displaystyle{ \left\{ 0,1\right\}}\), więc w myśl przytoczonego faktu o rozkładach iloczynu kartezjańskiego, otrzymujemy, ze rodzina \(\displaystyle{ \mathcal{R}'}\) równa:

\(\displaystyle{ \mathcal{R}'= \left\{ A \times B\Bigl| \ \ A \in \mathcal{R}, B \in \mathcal{R} _{\left\{ 0,1\right\} } \right\} ,}\)

jest rozkładem zbioru \(\displaystyle{ \NN \times \left\{ 0,1\right\}.}\)

Ponadto \(\displaystyle{ \mathcal{R}' \subset \mathbb{S}}\), gdyż \(\displaystyle{ \mathcal{R} \subset \mathbb{B}.}\)

A zatem \(\displaystyle{ \mathcal{R}' \subset \mathbb{S}}\), i \(\displaystyle{ \mathcal{R}' \in \mathbb{A}}\), i w ten oto sposób otrzymujemy funkcję \(\displaystyle{ \alpha}\) działającą w poniższy sposób:

\(\displaystyle{ \mathcal{R} \in \mathbb{D}\stackrel{ \alpha }{ \rightarrow } \mathcal{R}' \in \mathbb{A}.}\)

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

Jeśli \(\displaystyle{ \mathcal{R} _{1}, \mathcal{R} _{2} \in \mathbb{D}}\), i \(\displaystyle{ \mathcal{R} _{1} \neq \mathcal{R} _{2}}\), wtedy \(\displaystyle{ \mathcal{R} _{1},\not \subset \mathcal{R} _{2}}\) lub \(\displaystyle{ \mathcal{R} _{2}\not \subset \mathcal{R} _{1}. }\)

Jeśli \(\displaystyle{ \mathcal{R} _{1}\not \subset \mathcal{R} _{2}}\), wtedy, z definicji inkluzji, i na mocy prawa zaprzeczania ograniczonemu kwantyfikatorowi ogólnemu, więc otrzymujemy pewien zbiór \(\displaystyle{ A \in \mathcal{R} _{1}}\), taki, że: \(\displaystyle{ A \not\in \mathcal{R} _{2}.}\) Wtedy \(\displaystyle{ B:= A \times \left\{ 0,1\right\} \in \mathcal{R}' _{1}}\), a \(\displaystyle{ B\not \in \mathcal {R}'_{2},}\) a zatem \(\displaystyle{ \mathcal{R}' _{1} \neq \mathcal{R}' _{2}. }\)

Jeśli \(\displaystyle{ \mathcal{R} _{2}\not \subset \mathcal{R} _{1}}\), to w sposób analogiczny uzasadniamy, że: \(\displaystyle{ \mathcal{R}' _{1} \neq \mathcal{R}' _{2}.}\)

Wobec czego funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

A zatem \(\displaystyle{ \left| \mathbb{A}\right| \ge \left| \mathbb{D}\right| \ge \left| \RR\right|}\) , a zatem \(\displaystyle{ \left| \mathbb{A}\right| \ge \left| \RR\right|.\square}\)


Przejdźmy do naszych zadań.

Niech \(\displaystyle{ \mathbb{A}}\) będzie rodziną wszystkich właściwych (o dodatnich długościach) przedziałów domkniętych na prostej , tzn. niech:

\(\displaystyle{ \mathbb{A}= \left\{ \left[ a,b\right]\Bigl| \ \ a<b \right\} .}\)

Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną wszystkich prostokątów zbudowanych z dwóch takich przedziałów domkniętych, tzn. niech:

\(\displaystyle{ \mathbb{B}= \left\{ A \times B\Big| \ \ A,B \in \mathbb{A}\ \right\} = \left\{ A \times B\Bigl| \ \ \left( A,B\right) \in \mathbb{A} \times \mathbb{A} \right\}.}\)

Jeśli \(\displaystyle{ C \in \mathbb{B}}\), wtedy \(\displaystyle{ C= A \times B}\), gdzie \(\displaystyle{ A,B \in \mathbb{A}}\); wtedy \(\displaystyle{ A=\left[ a_1, a_2\right] ,}\) gdzie \(\displaystyle{ a_1<a_2}\) i \(\displaystyle{ B= \left[ b_1, b_2\right]}\) , gdzie \(\displaystyle{ b_1<b_2}\).

Wtedy \(\displaystyle{ A= C_L= \left( A \times B\right) _L}\) i \(\displaystyle{ B= C_P= \left( A \times B\right)_P,}\) a więc zbiory \(\displaystyle{ A,B}\) są wyznaczone jednoznacznie.

Również liczby rzeczywiste \(\displaystyle{ a_1, a_2, b_1, b_2}\) są wyznaczone jednoznacznie jako elementy najmniejsze/największe tych dwóch zbiorów.

Niech:

\(\displaystyle{ b\left( C\right) := \left( A \times \left\{ b_1, b_2\right\} \right) \cup \left( \left\{ a_1, a_2\right\} \times B \right),}\)

taki zbiór nazwijmy brzegiem prostokąta \(\displaystyle{ C.}\)

Niech:

\(\displaystyle{ \mathbb{S}= \left\{ b\left( C\right): \ C \in \mathbb{B} \right\} ,}\)

będzie rodziną brzegów wszystkich prostokątów z rodziny \(\displaystyle{ \mathbb{B}.}\)

I niech:

\(\displaystyle{ \mathbb{S} _{ \NN \times \NN} }\) będzie rodziną przekrojów takich brzegów z kratownicą \(\displaystyle{ \NN \times \NN}\), tzn. niech:

\(\displaystyle{ \mathbb{S} _{\NN \times \NN} = \left\{ b\left( C\right) \cap \left( \NN \times \NN\right) \Bigl| \ \ C \in \mathbb{B} \right\} .}\)

Niech \(\displaystyle{ \mathbb{D} _{\NN \times \NN}}\) będzie rodziną wszystkich rozkładów kratownicy \(\displaystyle{ \NN \times \NN}\) na zbiory z rodziny \(\displaystyle{ \mathbb{S} _{\NN \times \NN}}\), tzn. niech:

\(\displaystyle{ \mathbb{D} _{\NN \times \NN} = \left\{ \mathcal{R}: \ \mathcal{R} \hbox{ jest rozkładem zbioru } \NN \times \NN\hbox{, i } \mathcal{R} \subset \mathbb{S} _{\NN \times \NN} \right\}.}\)

I pytamy o moc rodziny \(\displaystyle{ \mathbb{D} _{\NN \times \NN}.}\)

Wykażemy, że ta rodzina ma moc continuum.

DOWÓD TEGO FAKTU:

Niech:

\(\displaystyle{ \mathbb{B} _{\NN}= \left\{ A \subset \NN\Bigl| \ \ A \hbox{ jest przedziałem skończonym i} \left| A\right| \ge 2 \right\}.}\)

Niech:

\(\displaystyle{ \mathbb{S} _{\NN \times \left\{ 0,1\right\} } = \left\{ A \times \left\{ 0,1\right\}\Bigl| \ A \in \mathbb{B} _{\NN} \right\} , }\)

i niech \(\displaystyle{ \mathbb{A} _{\NN \times \left\{ 0,1\right\} }}\) będzie rodziną wszystkich rozkładów zbioru \(\displaystyle{ \NN \times \left\{ 0,1\right\}}\) na zbiory z rodziny \(\displaystyle{ \mathbb{S} _{\NN \times \left\{ 0,1\right\} },}\) tzn. niech:

\(\displaystyle{ \mathbb{A} _{\NN \times \left\{ 0,1\right\} }= \left\{ \mathcal{R}: \ \mathcal {R} \hbox{ jest rozkladem zbioru } \NN \times \left\{ 0,1\right\} \hbox{, i } \mathcal{R} \subset \mathbb{S} _{\NN \times \left\{ 0,1\right\} } \right\},}\)

o której to rodzinie, wiemy już, że jest mocy co najmniej continuum.

Definiujemy funkcję:

\(\displaystyle{ \alpha : \mathbb{A} _{\NN \times \left\{ 0,1\right\} } \rightarrow \mathbb{D} _{\NN \times \NN},}\)

w następujący sposób:

Jeśli \(\displaystyle{ \mathcal{R} \in \mathbb{A} _{\NN \times \left\{ 0,1\right\} },}\) wtedy \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \NN \times \left\{ 0,1\right\},}\) i \(\displaystyle{ \mathcal{R} \subset \mathbb{S} _{\NN \times \left\{ 0,1\right\} }}\). Niech:

\(\displaystyle{ \mathcal{R}_+= \left\{ \left\{ 2n, 2n+1 \right\} \times \left\{ 2m , 2m+1\right\}, \ \ n \in \NN, m \in \NN_+ \right\} }\).

Wtedy \(\displaystyle{ \mathcal{R}_+}\) jest rozkładem zbioru \(\displaystyle{ \NN \times \left( \NN \setminus \left\{ 0,1\right\} \right)}\), łatwo to można udowodnić.

Niech:

\(\displaystyle{ \mathcal{R}'= \mathcal{R} \cup \mathcal{R}_+.}\)

Wtedy ponieważ \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \NN \times \left\{ 0,1\right\}}\) i \(\displaystyle{ \mathcal{R}_+}\) jest rozkładem zbioru \(\displaystyle{ \NN \times \left( \NN \setminus \left\{ 0,1\right\} \right)}\), a zbiory \(\displaystyle{ \NN \times \left\{ 0,1\right\}}\) i \(\displaystyle{ \NN \times \left( \NN \setminus \left\{ 0,1\right\} \right) }\) są rozłączne, więc rodzina \(\displaystyle{ \mathcal{R}'}\), jako suma takich dwóch rozkładów na zbiorach rozłącznych, jest rozkładem w sumie zbiorów gdzie są określone te dwa rozkłady, czyli rodzina \(\displaystyle{ \mathcal{R}'}\) jest rozkładem zbioru \(\displaystyle{ \left( \NN \times \left\{ 0,1\right\} \right) \cup \left[ \NN \times \left( \NN \setminus \left\{ 0,1\right\} \right) \right]= \NN \times \NN.}\)

Wykażemy, że: \(\displaystyle{ \mathcal{R}' \subset \mathbb{S} _{\NN \times \NN}.}\)
DOWÓD TEGO FAKTU::    
A zatem \(\displaystyle{ \mathcal{R} ' \in \mathbb{D} _{\NN \times \NN}}\), i w ten sposób otrzymujemy funkcję \(\displaystyle{ \alpha}\) działającą w poniższy sposób:

\(\displaystyle{ \mathcal{R} \in \mathbb{A} _{\NN \times \left\{ 0,1\right\} } \stackrel{ \alpha }{ \rightarrow } \mathcal{R}' \in \mathbb{D} _{\NN \times \NN}.}\)

I, łatwo jest pokazać, że dla dowolnych dwóch różnych rozkładów \(\displaystyle{ \mathcal{R}_1, \mathcal{R}_2\in \mathbb{A}}\) mamy również: \(\displaystyle{ \mathcal{R}'_1 \neq \mathcal{R}'_2. }\)

A zatem funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

A zatem \(\displaystyle{ \left| \mathbb{D} _{\NN \times \NN} \right| \ge \left| \mathbb{A} _{\NN \times \left\{ 0,1\right\} } \right| \ge \left| \RR\right|}\). A zatem \(\displaystyle{ \left| \mathbb{D} _{\NN \times \NN} \right| \ge \left| \RR\right|. }\)

Ale:

\(\displaystyle{ \mathbb{D} _{\NN \times \NN} \subset \mathbb{B} _{\NN \times \NN}:= \left\{ \mathcal{R}: \ \ \mathcal{R} \hbox{ jest rozkładem zbioru } \NN \times \NN\right\}.}\)

A wszystkich rozkładów zbioru przeliczalnego jest continuum.

A zatem \(\displaystyle{ \left| \mathbb{D} _{\NN \times \NN} \right| \le \left| \RR\right|}\), i, na mocy twierdzenia Cantora-Bernsteina: \(\displaystyle{ \mathbb{D} _{\NN \times \NN}\sim \RR.\square}\) :D\(\displaystyle{ }\)


Przejdźmy do kolejnego problemu:

Niech:

\(\displaystyle{ \mathbb{S} = \left\{ b\left( C\right): \ C \in \mathbb{B} \right\},}\)

i niech:

\(\displaystyle{ \mathbb{S} _{\ZZ \times \ZZ} = \left\{ b\left( C\right) \cap \left( \ZZ \times \ZZ\right)\Bigl| \ \ C \in \mathbb{B} \right\}}\) ,

będzie rodziną wszystkich przecięć brzegów wszystkich prostokątów z rodziny \(\displaystyle{ \mathbb{B}}\) z kratownicą \(\displaystyle{ \ZZ \times \ZZ}\).

I niech:

\(\displaystyle{ \mathbb{D}= \left\{ \mathcal{R}: \ \mathcal {R} \hbox{ jest rozkładem zbioru } \ZZ \times \ZZ\hbox{, i } \mathcal {R} \subset \mathbb{S} _{\ZZ \times \ZZ} \right\},}\)

będzie rodziną wszystkich rozkładów kratownicy \(\displaystyle{ \ZZ \times \ZZ}\) na zbiory z rodziny \(\displaystyle{ \mathbb{S} _{\ZZ \times \ZZ}}\).

I pytamy o moc rodziny \(\displaystyle{ \mathbb{D}}\).

Wykażemy, że rodzina \(\displaystyle{ \mathbb{D}}\) jest mocy continuum.

DOWÓD TEGO FAKTU:

Definiujemy funkcję:

\(\displaystyle{ \alpha : \mathbb{A} _{\NN \times \left\{ 0,1\right\} } \rightarrow \mathbb{D} _{\ZZ \times \ZZ} }\) w następujący sposób:

Jeśli \(\displaystyle{ \mathcal{R} \in \mathbb{A} _{\NN \times \left\{ 0,1\right\} }}\), wtedy \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \NN \times \left\{ 0,1\right\}}\) i \(\displaystyle{ \mathcal{R} \subset \mathbb{S} _{\NN \times \left\{ 0,1\right\} },}\)

Łatwo jest pokazać, że rodzina:

\(\displaystyle{ \mathcal{R} _{\ZZ_- \times \left\{ 0,1\right\} } = \left\{ \left\{ 2n, 2n+1 \right\} \times \left\{ 0,1\right\}\Bigl| \ \ n \in \ZZ_- \right\} }\),

tworzy rozkład zbioru \(\displaystyle{ \ZZ_- \times\left\{ 0,1\right\} ;}\)

jak i rodzina:

\(\displaystyle{ \mathcal{R} _{2\uparrow} =\left\{ \left\{ 2n ,2n+1\right\} \times \left\{ 2m, 2m+1\right\}\Bigl| \ n \in \ZZ, m \in \NN_+ \right\} }\)

tworzy rozkład zbioru \(\displaystyle{ \ZZ \times \left( \NN \setminus \left\{ 0,1\right\} \right) ;}\)

jak i rodzina:

\(\displaystyle{ \mathcal{R} _{\ZZ, -}= \left\{ \left\{ 2n, 2n+1\right\} \times \left\{ 2m+1, 2m\right\}\Bigl| \ \ m \in \ZZ_- , n \in \ZZ \right\} ,}\)

tworzy rozkład zbioru \(\displaystyle{ \ZZ \times \ZZ_-}\).

Zauważmy, że zbiory \(\displaystyle{ \NN \times \left\{ 0,1\right\} , \ZZ_- \times \left\{ 0,1\right\} , \ZZ \times \left( \NN \setminus \left\{ 0,1\right\} \right)}\) i \(\displaystyle{ \ZZ \times \ZZ_-}\) są rozłączne, w związku z czym rodzina \(\displaystyle{ \mathcal{R}'= \mathcal{R} \cup \mathcal{R} _{\ZZ_- \times \left\{ 0,1\right\} } \cup \mathcal{R} _{2\uparrow} \cup \mathcal{R} _{\ZZ,-}}\) jest rozkładem sumy tych czterech zbiorów, czyli jest to rozkład zbioru: \(\displaystyle{ \left( \NN \times \left\{ 0,1\right\} \right) \cup \left( \ZZ_- \times \left\{ 0,1\right\} \right) \cup \left( \ZZ \times \left( \NN \setminus \left\{ 0,1\right\} \right) \right) \cup \left( \ZZ \times \ZZ_-\right) = \ZZ \times \ZZ.}\)

Musimy teraz wykazać, że \(\displaystyle{ \mathcal{R}' \subset \mathbb{S} _{\ZZ \times \ZZ}}\).

Niech więc \(\displaystyle{ B \in \mathcal{R}}\)'. Jeśli \(\displaystyle{ B \in \mathcal{R} \subset \mathbb{S} _{\NN \times \left\{ 0,1\right\} }}\), to w podobny sposób jak pokazywaliśmy podobny fakt dla kratownicy \(\displaystyle{ \NN \times \NN}\)- w bardzo podobny sposób pokazujemy, że \(\displaystyle{ B \in \mathbb{S} _{\ZZ \times \ZZ}}\), a w pozostałych trzech przypadkach łatwo pokazujemy, że \(\displaystyle{ B \in \mathbb{S} _{\ZZ \times \ZZ}}\), a zatem \(\displaystyle{ \mathcal{R}' \subset \mathbb{S} _{\ZZ \times \ZZ}}\),

i \(\displaystyle{ \mathcal{R}' \in \mathbb{D} _{\ZZ \times \ZZ}}\), i w ten sposób otrzymujemy funkcję \(\displaystyle{ \alpha }\) działającą w poniższy sposób:

\(\displaystyle{ \mathcal{R} \in \mathbb{A} _{\NN \times \left\{ 0,1\right\} } \stackrel{ \alpha }{ \rightarrow } \mathcal{R}' \in \mathbb{D} _{\ZZ \times \ZZ}.}\)

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

W tym celu weźmy dwa dowolne różne rozkłady \(\displaystyle{ \mathcal{R}_1,\mathcal{R}_2 \in \mathbb{A} _{\NN \times \left\{ 0,1\right\} } .}\) Ponieważ \(\displaystyle{ \mathcal{R}_1 \neq \mathcal{R}_2}\), więc \(\displaystyle{ \mathcal{R}_1 \not \subset \mathcal{R}_2}\) lub \(\displaystyle{ \mathcal{R}_2 \not \subset \mathcal{R}_1.}\)

Jeśli \(\displaystyle{ \mathcal{R}_1 \not \subset \mathcal{R}_2}\), wtedy, z definicji inkluzji, otrzymujemy pewien zbiór \(\displaystyle{ A \in \mathcal{R}_1}\), taki, że \(\displaystyle{ A\not \in \mathcal{R}_2 }\). Wtedy \(\displaystyle{ A \in \mathcal{R}' _{1} = \mathcal{R}_1 \cup \left( \mathcal{R} _{\ZZ_- \times \left\{ 0,1\right\} }\right) \cup \left( \mathcal{R} _{2\uparrow}\right) \cup \mathcal{R} _{\ZZ, -},}\)a \(\displaystyle{ A\not \in \mathcal{R}'_2}\).

Gdyby bowiem byłoby \(\displaystyle{ A \in \mathcal{R}'_2}\), wtedy ponieważ \(\displaystyle{ A\not \in \mathcal{R}_2}\), więc \(\displaystyle{ A \in \left( \mathcal{R} _{\ZZ_- \times \left\{ 0,1\right\} }\right)}\) lub \(\displaystyle{ A \in \left( \mathcal{R} _{2\uparrow}\right)}\) lub \(\displaystyle{ A \in \mathcal{R} _{\ZZ, -}.}\)

Jeśli \(\displaystyle{ A \in \mathcal{R}_1}\), wtedy ponieważ \(\displaystyle{ \mathcal{R}_1}\) jest rozkładem zbioru \(\displaystyle{ \NN \times \left\{ 0,1\right\} }\), więc \(\displaystyle{ A \subset \NN \times \left\{ 0,1\right\}}\) , i jako zbiór rozkładu jest to zbiór niepusty. A ponieważ \(\displaystyle{ \mathcal{R} _{\ZZ_- \times \left\{ 0,1\right\} }}\) jest rozkładem zbioru \(\displaystyle{ \ZZ_- \times \left\{ 0,1\right\}}\), a zbiór \(\displaystyle{ A}\) jest jego elementem, więc również \(\displaystyle{ A \subset \ZZ_- \times \left\{ 0,1\right\}}\) , co daje sprzeczność, bo te dwa zbiory są rozłączne, i zbiór \(\displaystyle{ A}\) jest niepustym podzbiorem ich przecięcia - sprzeczność.

W pozostałych dwóch przypadkach w podobny sposób otrzymujemy sprzeczność.

Wobec czego \(\displaystyle{ A\not \in \mathcal{R}'_2}\), a \(\displaystyle{ A \in \mathcal{R}'_1,}\) wobec czego \(\displaystyle{ \mathcal{R}'_1 \neq \mathcal{R}_2 ^{'}.}\)

Jeśli \(\displaystyle{ \mathcal{R}_2\not \subset \mathcal{R}_1}\), to w sposób analogiczny jak powyżej udowadniamy, że \(\displaystyle{ \mathcal{R}'_1 \neq \mathcal{R}'_2.}\)

Wobec czego funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

A zatem \(\displaystyle{ \left| \mathbb{D} _{\ZZ \times \ZZ} \right| \ge \left| \mathbb{A} _{\NN} \times \left\{ 0,1\right\} \right| \ge \left| \RR\right| }\), czyli \(\displaystyle{ \left| \mathbb{D} _{\ZZ \times \ZZ} \right| \ge \left| \RR \right|.}\)

Ale:

\(\displaystyle{ \mathbb{D} _{\ZZ \times \ZZ} \subset \mathbb{B} _{\ZZ \times \ZZ} := \left\{ \mathcal{R} : \ \mathcal{R} \hbox{ jest rozkładem zbioru } \ZZ \times \ZZ\right\} .}\)

Ponieważ zbiór \(\displaystyle{ \ZZ \times \ZZ}\) jest zbiorem przeliczalnym, a wszystkich rozkładów zbioru przeliczalnego jest continuum, więc \(\displaystyle{ \left| \mathbb{D} _{\ZZ \times \ZZ} \right| \le \left| \RR\right|}\), i na mocy twierdzenia Cantora-Bernsteina: \(\displaystyle{ \mathbb{D} _{\ZZ \times \ZZ}\sim \RR.\square}\) 8-)


I ostatni nasz problem:

Niech:

\(\displaystyle{ \mathbb{S}= \left\{ b\left( C\right): \ C \in \mathbb{B} \right\} ,}\)

będzie rodziną brzegów wszystkich prostokątów.

I dla zbioru \(\displaystyle{ X:= \ZZ_- \cup \left\{ 0\right\}}\), niech:

\(\displaystyle{ \mathbb{S} _{\ZZ_{-} \times \ZZ_{-}} = \left\{ b(C) \cap \left( \ \left( \ZZ_- \cup \left\{ 0\right\}\right) \times \left( \ZZ_- \cup \left\{ 0\right\} \right) \ \right) \Bigl| \ \ C \in \mathbb{B} \right\}.}\)

Niech \(\displaystyle{ \mathbb{D}}\) będzie rodziną wszystkich rozkładów zbioru \(\displaystyle{ (\ZZ_- \cup \left\{ 0\right\} ) \times \left( \ZZ_- \cup \left\{ 0\right\} \right)}\) na zbiory z rodziny \(\displaystyle{ \mathbb{S} _{\ZZ_{-} \times \ZZ_- }}\), tzn. niech:

\(\displaystyle{ \mathbb{D}= \left\{ \mathcal{R}: \ \ \mathcal{R} \hbox{ jest rozkładem zbioru } \left( \ZZ_- \cup \left\{ 0\right\} \right) \times \left( \ZZ_- \cup \left\{ 0\right\} \right)\hbox{, i } \mathcal{R} \subset \mathbb{S} _{\mathbb{Z}_{-} \times \mathbb{Z} _{-} } \right\}.}\)

I pytamy o moc rodziny \(\displaystyle{ \mathbb{D}.}\)

Wykażemy, że ta rodzina jest mocy continuum.

Wpierw, dla dowolnego podzbioru płaszczyzny \(\displaystyle{ A \subset \RR ^{2}}\), zdefiniujmy zbiór:

\(\displaystyle{ A _{\left( 0,0\right) } = \left\{ \left( -x,-y\right)\Bigl| \ \left( x,y\right) \in A \right\} \subset \RR^2.}\)

Jest to zbiór powstały poprzez symetrię względem początku układu.

Łatwo jest zauważyć, że dla dowolnego zbioru \(\displaystyle{ A \subset \RR^2}\), mamy: \(\displaystyle{ \left( A _{\left( 0,0\right) } \right) _{\left( 0,0\right) } =A}\),

czyli odbicie odbicia zbioru \(\displaystyle{ A}\) jest równe zbiorowi \(\displaystyle{ A.}\)

Przejdźmy do naszego zadania.

DOWÓD TEGO FAKTU:

Niech:

\(\displaystyle{ \mathbb{S} _{\NN \times \NN} = \left\{ b\left( C\right) \cap \left( \NN \times \NN\right)\Bigl| \ \ C \in \mathbb{B} \right\}.}\)

I niech:

\(\displaystyle{ \mathbb{D} _{\NN \times \NN}}\) będzie rodziną wszystkich rozkładów zbioru \(\displaystyle{ \NN \times \NN}\) na zbiory z rodziny \(\displaystyle{ \mathbb{S} _{\NN \times \NN},}\) tzn. niech:

\(\displaystyle{ \mathbb{D} _{\NN \times \NN}= \left\{ \mathcal{ R}: \ \mathcal{R}\hbox{ jest rozkładem zbioru } \NN \times \NN\hbox{, i } \mathcal{R} \subset \mathbb{S} _{\NN \times \NN} \right\}.}\)

Wiemy już, że ta rodzina ma moc continuum.

Definiujemy funkcję:

\(\displaystyle{ \alpha : \mathbb{D} _{\NN \times \NN} \rightarrow \mathbb{D} _{\ZZ_- \times \ZZ_-}}\), w następujący sposób:

jeśli \(\displaystyle{ \mathcal{R} \in \mathbb{D} _{\NN \times \NN}}\), wtedy \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \NN \times \NN}\) i \(\displaystyle{ \mathcal{R} \subset \mathbb{S} _{\NN \times \NN}}\), i przypisujemy mu nowy rozkład \(\displaystyle{ \mathcal{R} '}\), dany jako:

\(\displaystyle{ \mathcal{R}'= \left\{ A _{\left( 0,0\right) } \Bigl| \ \ A \in \mathcal{R}\right\},}\)

i pokazujemy, że funkcja \(\displaystyle{ \alpha}\) działająca w następujący sposób:

\(\displaystyle{ \mathcal{R} \in \mathbb{D} _{\NN \times \NN} \stackrel{ \alpha }{ \rightarrow } \mathcal{R} ' \in \mathbb{D} _{\ZZ_- \times \ZZ_-},}\)

jest dobrze określoną bijekcją (co wymaga trochę zachodu, ale teraz to już mam zawroty głowy, a i tak nikt nie chciałby tego czytać, poza tym taki dowód jest raczej bardziej techniczny, więc daruje sobie zapisywanie go).

A zatem:

\(\displaystyle{ \RR\sim \mathbb{D} _{\NN \times \NN} \sim \mathbb{D} _{\ZZ_- \times \ZZ_-}}\), czyli \(\displaystyle{ \mathbb{D} _{\ZZ_- \times \ZZ_-}\sim \RR.\square}\) 8-)
ODPOWIEDZ