Jakub Gurak pisze: otrzymujemy:
\(\displaystyle{ \frac{3\left( n^2-1\right) }{4}+1}\), takich kół o średnicy \(\displaystyle{ 1}\) o rozłącznych wnętrzach zawartych w tym dużym kole o średnicy \(\displaystyle{ n}\) (\(\displaystyle{ n}\) jest nieparzyste). 8-
Jednak, w przypadku gdy \(\displaystyle{ n}\) jest parzyste, to teraz widzę, że zapowiedziany wynik będę musiał poprawić bo ... będzie można popracować nad tym.
Jak i będzie można popracować nad wersją tego zadania gdy średnica dużego koła jest dowolnej ustalonej długości większej od
\(\displaystyle{ 1}\) (długości niekoniecznie naturalnej- długości rzeczywistej, może to być nawet długość niewymierna), będzie można pomyśleć nad tym.
Niedawno zbadałem poniższe dwa problemy związane z teorią mocy zbiorów:
Rozważmy dwie liczby naturalne dodatnie:
\(\displaystyle{ n}\) i
\(\displaystyle{ m}\). Rozważmy iloczyn
\(\displaystyle{ n \cdot m}\) (weźmy dla przykładu
\(\displaystyle{ m=3}\)), i rozważmy skończony zbiór liniowo uporządkowany
\(\displaystyle{ X=\left\{ \ 1,2,3, \ 4,5,6, \ 7,8,9, \ \ldots, \ 3n-2, 3n-1, 3n \ \right\} }\) z naturalnym porządkiem, i badałem rozkłady tego zbioru na przedziały trzyelementowe (bo
\(\displaystyle{ m=3}\)). Okazuje się o dziwo, że taki rozkład jest dokładnie jeden.
Zbadałem też (choć może nie do końca) poniższy problem:
Na ile sposobów dany niepusty zbiór liniowo uporządkowany można przedstawić jako suma porządkowa dwóch niepustych rozłącznych podzbiorów. Przedstawię teraz rozwiązania tych
bardzo ciekawych zadań.
Niech
\(\displaystyle{ n,m \in \NN _{+} }\), i rozważmy skończony zbiór:
\(\displaystyle{ X:=\left\{ 1,2,3,\ldots, \left( n \cdot m\right) \right\} }\);
z naturalnym porządkiem.
Rozważmy rodzinę rozkładów:
\(\displaystyle{ \mathbb{B}=\left\{ \mathcal{R}: \ \mathcal{R}\hbox{ jest rozkładem zbioru } X \hbox{ i } A \in \mathcal{R} \Longrightarrow \left[ A \hbox{ jest przedziałem i } \left| A\right|= m\right] \right\}. }\)
I pytamy o moc rodziny
\(\displaystyle{ \mathbb{B}. }\)
Wykażemy, że taki rozkład jest dokładnie jeden.
Tym rozkładem będzie naturalny rozkład:
\(\displaystyle{ \mathcal{R}=\left\{ mk+1, mk+2, \ldots, mk+m\Bigl| \ \ k=0,1,2,\ldots,n-1 \right\}. }\)
Mogę pokazać, że jest to rodzina zbiorów rozłącznych, tzn. każde dwa różne zbiory tej rodziny są rozłączne, ale to jest intuicyjnie oczywiste (formalnie niestety nie), a pisze z tabletu i źle się piszę, więc może pominę ten dowód (jak ktoś zechcę bardzo, to mogę go potem dopisać), wybaczcie. A zatem
\(\displaystyle{ \mathcal {R}}\) jest rozkładem zbioru
\(\displaystyle{ X.}\) Ponadto, jeśli
\(\displaystyle{ A \in \mathcal{R},}\) to
\(\displaystyle{ A}\) jest przedziałem i
\(\displaystyle{ \left| A\right|= m, }\) a zatem:
\(\displaystyle{ \mathcal{R} \in \mathbb{B}.}\)
Pozostaje pokazać, że jest tylko jeden taki rozkład.
Niech
\(\displaystyle{ \mathcal{R} \in \mathbb {B}.}\) Zauważmy, że zbiór
\(\displaystyle{ X}\) ma dokładnie
\(\displaystyle{ \left( n \cdot m\right) }\) elementów. Popatrzmy więc na zbiór
\(\displaystyle{ \left\{ 1,2,3, \ldots,n\right\} \times \left\{ 1,2,3,\ldots, m \right\} }\) z porządkiem leksykograficznym naturalnych porządków na obu osiach. Ponieważ każdy zbiór naszego rozkładu ma dokładnie
\(\displaystyle{ m}\) elementów i ten rozkład jest rodziną zbiorów rozłącznych (które to zbiory sumują się do zbioru
\(\displaystyle{ X}\)), więc
\(\displaystyle{ m+m+\ldots +m=n \cdot m, }\) skąd
\(\displaystyle{ \left| \mathcal {R}\right|=n. }\) Ponieważ jednak każdy zbiór tego rozkładu jest przedziałem (na półprostej liczb naturalnych), to nie da się tutaj utworzyć innego takiego rozkładu niż rozkład naturalny, gdyż, w przeciwnym razie, pierwszy taki napotkany numer albo jest on 'ominęty' i wtedy zbiór do którego on należy nie jest przedziałem, albo należy on do zbioru który też nie jest przedziałem. Wobec czego dla naszego naturalnego rozkładu
\(\displaystyle{ \mathcal{R}}\) musi być:
\(\displaystyle{ \mathbb{B}=\left\{ \mathcal{R}\right\} }\) i
\(\displaystyle{ \left| \mathbb {B}\right|=1.\square }\)
Przejdźmy do naszego drugiego zadania:
Niech
\(\displaystyle{ \left( X, \le \right) }\) będzie niepustym zbiorem liniowo uporządkowanym.
Rozważmy rodzinę
\(\displaystyle{ \mathbb {B}}\):
\(\displaystyle{ \mathbb{B}=\left\{ \left( X _{1}, X _{2} \right) \in P\left( X\right) \times P\left( X\right)\Bigl| \ X _{1}, X _{2} \neq \left\{ \right\}, X _{1} \cap X _{2}=\left\{ \right\} \hbox{ i } X _{1}\oplus X _{2}=X\right\}. }\)
Jest to rodzina par podzbiorów zbioru
\(\displaystyle{ X}\) (rozłącznych i niepustych), których suma porządkowa daje zbiór liniowo uporządkowany
\(\displaystyle{ \left( X, \le \right). }\) I pytamy o moc rodziny
\(\displaystyle{ \mathbb {B}}\) - czyli pytamy na ile sposobów zbiór liniowo uporządkowany
\(\displaystyle{ \left( X, \le \right) }\) może być przedstawiony jako suma porządkowa dwóch niepustych rozłącznych podzbiorów.
ROZWIĄZANIE:
Niech
\(\displaystyle{ \mathbb {A}}\) będzie rodziną wszystkich niepustych i różnych od całego zbioru
\(\displaystyle{ X}\) przedziałów początkowych.
Wtedy
\(\displaystyle{ \mathbb {A}\sim\mathbb {B}.}\)
Aby to udowodnić definiujemy funkcję
\(\displaystyle{ \alpha:\mathbb {B} \rightarrow \mathbb {A},}\) jako:
\(\displaystyle{ \alpha \left( \left( X _{1}, X _{2} \right) \right)=X _{1}. }\)
Wtedy
\(\displaystyle{ X _{1}\oplus X _{2}= X, }\) a zatem zbiór
\(\displaystyle{ X _{1} }\) jest przedziałem początkowym w
\(\displaystyle{ \left( X, \le \right). }\) Wtedy zbiór
\(\displaystyle{ X _{1} }\) jest niepusty i jest różny od całego zbioru
\(\displaystyle{ X,}\) bo gdyby byłoby
\(\displaystyle{ X _{1}= X,}\) to
\(\displaystyle{ X _{2}= X'=\left\{ \right\}}\)- sprzeczność. Wobec czego
\(\displaystyle{ X _{1} \neq X, }\) a zatem
\(\displaystyle{ X _{1} \in \mathbb {A},}\) i funkcja
\(\displaystyle{ \alpha }\) jest dobrze określona.
Łatwo jest pokazać, że funkcja
\(\displaystyle{ \alpha}\) jest różnowartościowa.
Wykażemy, że funkcja
\(\displaystyle{ \alpha}\) jest funkcją 'na' rodzinę
\(\displaystyle{ \mathbb{A}.}\)
W tym celu:
Niech
\(\displaystyle{ A \in \mathbb{A}}\). Wtedy
\(\displaystyle{ A}\) jest niepustym i różnym od całego
\(\displaystyle{ X}\) przedziałem początkowym w
\(\displaystyle{ \left( X, \le\right).}\) Niech
\(\displaystyle{ B=A'=X \setminus A}\). Wtedy
\(\displaystyle{ B \neq X,\left\{ \right\}.}\) Z własności przekrojów Dedekinda otrzymujemy, że para zbiorów
\(\displaystyle{ \left( A,B\right)}\) tworzy przekrój Dedekinda, więc (mamy
\(\displaystyle{ A \cup B=X}\) oraz zbiory
\(\displaystyle{ A}\) i
\(\displaystyle{ B}\) są rozłączne), więc
\(\displaystyle{ A\oplus B=X.}\) A zatem otrzymujemy, że
\(\displaystyle{ \left( A,B\right) \in \mathbb{B}}\), i wtedy
\(\displaystyle{ \alpha \left( \left( A,B\right) \right)=A}\), a więc zbiór
\(\displaystyle{ A}\) jest wartością funkcji
\(\displaystyle{ \alpha}\). Z dowolności wyboru zbioru
\(\displaystyle{ A}\) otrzymujemy, że funkcja
\(\displaystyle{ \alpha}\) jest funkcją 'na'.
A zatem
\(\displaystyle{ \mathbb{B}\sim \mathbb{A}.}\)
A zatem, tych naszych sposobów przedstawienia zbioru
\(\displaystyle{ X}\) w postaci sumy porządkowej jest tyle, ile jest w nim niepustych i różnych od całego zbioru
\(\displaystyle{ X}\) przedziałów początkowych. Zauważmy teraz, że wszystkich przedziałów początkowych w
\(\displaystyle{ X}\) jest co najmniej tyle, ile jest elementów
\(\displaystyle{ X}\), bowiem, jeśli
\(\displaystyle{ \mathbb{A}'}\) jest rodziną wszystkich przedziałów początkowych w
\(\displaystyle{ X}\), to możemy zdefiniować funkcję
\(\displaystyle{ f:X \rightarrow \mathbb{A}',}\) jako:
\(\displaystyle{ f\left( x\right)= \overline{O\left( x\right) }:= \left\{ y \in X: y \le x\right\} .}\)
Wtedy
\(\displaystyle{ \overline{O\left( x\right) }}\) jest przedziałem początkowym, i:
Jeśli
\(\displaystyle{ f\left( x_1\right)= f\left( x_2\right)}\), to
\(\displaystyle{ \overline{O\left( x_1\right) } = \overline{O\left( x_2\right) }}\), więc również, dla elementów największych tych zbiorów, otrzymamy:
\(\displaystyle{ x_1=\max \overline{O\left( x_1\right) }= \max\overline{O\left( x_2\right) }=x_2,}\)
i funkcja
\(\displaystyle{ f}\) jest różnowartościowa. A zatem:
\(\displaystyle{ \left| \mathbb{A}'\right| \ge \left| X\right|}\).
Jeśli zbiór
\(\displaystyle{ X}\) jest skończony i ma
\(\displaystyle{ n \ge 1}\) elementów:
\(\displaystyle{ X=\left\{ x_1, x_2,\ldots, x_n\right\}}\), to
\(\displaystyle{ \mathbb{A}' \sim \left( n+1\right)}\) , a zatem
\(\displaystyle{ \mathbb{B}\sim \mathbb{A}\sim n-1}\) (w szczególności, dla
\(\displaystyle{ n=1}\) otrzymujemy
\(\displaystyle{ 0=1-1}\) takich sposobów, gdyż zbioru jednoelementowego nie da rady rozszarpać na dwa niepuste rozłączne podzbiory, dla
\(\displaystyle{ n=2}\) mamy tutaj tylko
\(\displaystyle{ 1=2-1}\) takich sposobów: pierwszym takim zbiorem pary musi być zbiór jednopunktowy złożony z lewego końca, a drugim zbiorem pary musi być zbiór jednopunktowy złożony z drugiego końca).
Jeśli zbiór
\(\displaystyle{ X}\) jest nieskończony, to ponieważ
\(\displaystyle{ \left| \mathbb{A}'\right| \ge \left| X\right|}\), to rodzina
\(\displaystyle{ \mathbb{A}'}\) jest również nieskończona, a wtedy:
\(\displaystyle{ \mathbb{B}\sim \mathbb{A} = \mathbb{A}' \setminus \left\{ \emptyset, X\right\}\sim \left| \mathbb{A}'\right| \ge \left| X\right|}\), czyli
\(\displaystyle{ \left| \mathbb{B}\right| \ge \left| X\right|.}\)
Ponieważ
\(\displaystyle{ \left| \mathbb{B}\right|= \left| \mathbb{A}'\right|}\), i ponieważ dla rodziny
\(\displaystyle{ \mathbb{D}}\) wszystkich przedziałów w
\(\displaystyle{ \left( X, \le \right)}\), mamy:
\(\displaystyle{ \left| \mathbb{A}'\right| \le \left| \mathbb{D}\right|}\) (bo każdy przedział początkowy jest przedziałem), więc:
\(\displaystyle{ \left| \mathbb{B}\right| \le \left| \mathbb{D}\right|.}\) A często ( np. w dowolnym zbiorze typu
\(\displaystyle{ \left( \ZZ, \le \right) }\), w zbiorze dobrze uporządkowanym, w zbiorze ciągłym, w porządku odwrotnym do dobrego), wtedy wszystkich przedziałów jest tyle, ile jest elementów zbioru
\(\displaystyle{ X}\), tzn.:
\(\displaystyle{ \mathbb{D}\sim X}\). A wtedy
\(\displaystyle{ \left| \mathbb{B}\right| \le \left| X\right|}\), i na mocy twierdzenia Cantora-Bernsteina mamy wtedy:
\(\displaystyle{ \mathbb{B}\sim X.}\)
W ogólności, jeśli
\(\displaystyle{ X}\) jest nieskończony, to doszedłem tylko do tego (oraz do powyższego wniosku), że:
\(\displaystyle{ \left| \mathbb{B}\right| \ge \left| X\right|}\).
Jednak rodzina
\(\displaystyle{ \mathbb{B}}\) może być istotnie liczniejsza niż zbiór
\(\displaystyle{ X}\):
Np. w zbiorze
\(\displaystyle{ \left( \QQ, \le \right)}\) wtedy wszystkich przedziałów początkowych jest więcej niż liczb wymiernych, bo dla dowolnej ustalonej liczby niewymiernej możemy rozważyć zbiór wszystkich liczb mniejszych od niej (liczb wymiernych). Ponieważ zbiór liczb niewymiernych jest liczniejszy niż zbiór liczb wymiernych, to:
\(\displaystyle{ \mathbb{A}'\sim \RR \setminus \QQ\sim \RR}\). A zatem
\(\displaystyle{ \mathbb{B}\sim \mathbb{A}= \mathbb{A}' \setminus \left\{ \emptyset, X\right\} \sim \RR}\), a więc
\(\displaystyle{ \left| \mathbb{B}\right| = \left| \RR\right|>\left| \QQ\right|=\left| \NN\right|.}\)
Na koniec chciałbym zrobić użytek z książki "Zarys logiki matematycznej" Andrzeja Grzegorczyka (nie planuje już więcej szukać książek, artykułów... z Logiki matematycznej- zgłębianie czystych formalizmów mnie nie pociąga), ale chciałbym podzielić się z Wami definicją dodawania i mnożenia liczb całkowitych. Liczby całkowite dodatnie będziemy oznaczać jako
\(\displaystyle{ \left( +,k\right) }\), gdzie
\(\displaystyle{ k \in \NN _{+}, }\) liczby całkowite ujemne przez
\(\displaystyle{ \left(-,k\right), }\) gdzie
\(\displaystyle{ k \in \NN _{+}, }\) a zero w liczbach całkowitych będziemy oznaczać przez
\(\displaystyle{ \textbf{0}}\). Dodawanie liczb całkowitych definiujemy w poniższy sposób (piszemy + grubo, bo formalnie to jest inne dodawanie niż dodawanie liczb naturalnych (bo bardziej ogólne); podobnie dla mnożenia- jego znak będziemy oznaczać przez:
\(\displaystyle{ \bullet}\)). Oto jest definicja takiego dodawania:
\(\displaystyle{ \left( +, n\right)}\)+ \(\displaystyle{ \left( +,m\right)= \left( +,n+m\right); }\)
\(\displaystyle{ \left( +,n\right)}\)+ \(\displaystyle{ \left( -,m\right)= \begin{cases} \left( +, n-m \right), \hbox{ gdy } n>m; \\ \textbf{0}, \hbox{ gdy } n=m; \\ \left( -,m-n\right), \hbox { gdy } m>n. \end{cases}; }\)
\(\displaystyle{ \left( -,n\right)}\) + \(\displaystyle{ \left( +,m\right)=\left( +,m\right)}\)+\(\displaystyle{ \left( -,n\right);}\)
\(\displaystyle{ \left( -,n\right)}\) + \(\displaystyle{ \left( -,m\right) =\left( -, n+ m\right); }\)
\(\displaystyle{ \left( +,n\right) }\) + \(\displaystyle{ \textbf{0}=\textbf{0}}\) + \(\displaystyle{ \left( +, n\right)=\left( +,n\right); }\)
\(\displaystyle{ \left( -,n\right)}\) + \(\displaystyle{ \textbf{0}=\textbf{0}}\) + \(\displaystyle{ \left( -, n\right)=\left( -,n\right);}\)
\(\displaystyle{ \textbf{0} }\) + \(\displaystyle{ \textbf{0}=\textbf{0}.}\)
W ten sposób takie dodawanie zostało zdefiniowane dla dowolnych dwóch liczb całkowitych.
Definicja mnożenia jest prostsza:
1): Jeśli
\(\displaystyle{ m \in \ZZ,}\) to
\(\displaystyle{ m \bullet \textbf{0} = \textbf{0} \bullet m = \textbf{0}. }\)
2): \(\displaystyle{ \left( +, n\right)\bullet \left( +,m\right) = \left( +, n \cdot m\right)=\left( -,n\right)\bullet \left( -, m\right).}\)
3): \(\displaystyle{ \left( -,n\right)\bullet \left( +,m\right) =\left( -, n \cdot m\right)= \left( +, n\right)\bullet \left( -,m\right).}\)
I w ten sposób zdefiniowaliśmy mnożenie dla dowolnych dwóch liczb całkowitych.
W ten sposób?
