Analiza matematyczna 2/Ćwiczenia 1: Przestrzenie metryczne

From Studia Informatyczne

Przestrzenie metryczne

Ćwiczenie 1.1.

Niech \displaystyle  n będzie dowolną liczbą naturalną oraz niech \displaystyle  X_n oznacza zbiór wszystkich słów długości \displaystyle  n (to znaczy ciągów liter długości \displaystyle  n). W teorii kodowania rozważa się funkcję \displaystyle  d\colon X_n\times X_n\longrightarrow\mathbb{N}_0 definiowaną przez:

\displaystyle  d(w,v) \ \stackrel{df}{=}\ ilość pozycji, na których w słowach \displaystyle  v i \displaystyle  w występują różne litery \displaystyle   .

(a) Udowodnić, że \displaystyle  d jest metryką w \displaystyle  X_n (jest to tak zwana metryka Hamminga).
(b) Czy \displaystyle  d nadal będzie metryką, gdy w powyższej definicji słowo "różne" zastąpimy przez "takie same"?

Wskazówka

(1) Pierwsze dwa punkty definicji metryki są łatwe do sprawdzenia. W celu sprawdzenia nierówności trójkąta, dla dwóch danych słów \displaystyle  w=w_1w_2\ldots w_n i \displaystyle  v=v_1v_2\ldots v_n, rozważyć zbiór \displaystyle  A_{wv} indeksów \displaystyle  i\in\{1,\ldots,n\} takich, że słowa te mają różną \displaystyle  i-tą literę, to znaczy \displaystyle  w_i\ne v_i. Jaki jest związek zbioru \displaystyle  A_{wv} z odległością \displaystyle  d(w,v)? Jaki jest związek między zbiorami \displaystyle  A_{wv} oraz \displaystyle  A_{wz} i \displaystyle  A_{zv}? Dlaczego? Co z tego wynika?

(2) Zbadać zachodzenie pierwszego punktu z definicji metryki.

Rozwiązanie

(1) Dla dwóch słów \displaystyle  w=w_1w_2\ldots w_n,\ v_1v_2\ldots v_n\in X_n rozważmy zbiór \displaystyle  A_{vw} tych indeksów (pozycji w słowach), dla których słowa \displaystyle  w i \displaystyle  v mają różne litery, to znaczy

\displaystyle  A_{wv} \ =\ \big\{ i\in\{1,2,\ldots,n\}:\ w_i\ne v_i \big\}.

Wówczas odległość \displaystyle  d(w,v) jest równa ilości elementów zbioru \displaystyle  A_{wv}, to znaczy \displaystyle  d(w,v)=\# A_{wv}.
(i) Warunek \displaystyle  d(w,v)=0 jest równoważny stwierdzeniu, że słowa \displaystyle  w i \displaystyle  v nie różnią się na żadnej pozycji, a więc mają wszystkie litery takie same, a zatemsą identyczne, to znaczy, \displaystyle  w=v. Używając zbiorów \displaystyle  A_{wv}, można to także uzasadnić następująco:

\displaystyle  d(w,v) = 0 \ \Longleftrightarrow\ \# A_{wv}=0 \ \Longleftrightarrow\ \bigg[\forall i:\ w_i=v_i\bigg] \ \Longleftrightarrow\ w=v.

(ii) Symetria \displaystyle  d(w,v)=d(v,w) jest oczywista, gdyż pozycje, na których słowo \displaystyle  w jest różne od słowa \displaystyle  v, są dokładnie takie same, jak pozycje, na których słowo \displaystyle  v różni się od słowa \displaystyle  w. Używając zbiorów \displaystyle  A_{wv}, można to także uzasadnić następująco:

\displaystyle  d(w,v) \ =\ \# A_{wv} \ =\ \# A_{wv} \ =\ d(v,w).

(iii) Aby pokazać nierówność trójkąta, rozważmy trzy słowa: \displaystyle  w,v,z\in X_n. Pokażmy najpierw, że zachodzi następująca inkluzja:

\displaystyle  A_{wv} \ \subseteq\ A_{wz}\cup A_{zv}.

W tym celu niech \displaystyle  i_0\in A_{wv}. Oznacza to, że \displaystyle  w_{i_0}\ne v_{i_0} (to znaczy słowa \displaystyle  w i \displaystyle  v różnią się na pozycji \displaystyle  i_0). Zauważmy, że wówczas \displaystyle  w_{i_0}\ne z_{i_0} lub \displaystyle  z_{i_0}\ne v_{i_0} (w przeciwnym razie z przechodniości relacji równości mielibyśmy \displaystyle  w_{i_0}=v_{i_0}). Zatem \displaystyle  i_0\in A_{wz} lub \displaystyle  i_0\in A_{zv}, czyli \displaystyle  i_0\in A_{wz}\cup A_{zv}, co dowodzi powyższej inkluzji.

Powyższa inkluzja oznacza w szczególności, że

\displaystyle  \# A_{wv} \ \le\ \# A_{wz}\cup \# A_{zv},

zatem

\displaystyle  d(w,v) \ =\ \# A_{wv} \ \le\ \# A_{wz}\cup \# A_{zv} \ =\ d(w,z)+d(z,v),

co należało dowieść.

(2) Zauważmy, że przy tak zmodyfikowanej definicji metryki Hamminga nie zachodzi już pierwszy punkt z definicji metryki. Dla dowolnego słowa \displaystyle  w\in X_n mamy bowiem \displaystyle  d(w,w)=n\ne 0.

Ćwiczenie 1.2.

Niech \displaystyle  X będzie dowolnym zbiorem niepustym oraz niech \displaystyle  f\colon X\longrightarrow\mathbb{R} będzie dowolną iniekcją. Udowodnić, że odwzorowanie dane wzorem

\displaystyle  d(x,y)\ \stackrel{df}{=}\  \big|f(x)-f(y)\big| \qquad\forall\  x,y\in X

jest metryką w \displaystyle  X.

Wskazówka

Wszystkie trzy warunki definicji metryki są łatwe do sprawdzenia. W nierówności trójkąta należy wykorzystać nierówność dla wartości bezwzględnej w \displaystyle \mathbb{R} (to znaczy nierówność trójkąta dla metryki euklidesowej w \displaystyle \mathbb{R}).

Rozwiązanie

Sprawdzimy kolejno trzy punkty z definicji metryki.
(a) Dla dowodu pierwszego warunku w definicji metryki zauważmy, że dla dowolnych \displaystyle  x,y\in X mamy następujące równoważności

\begin{array}{lll} \displaystyle  d(x,y) = 0 &\Longleftrightarrow\& \big|f(x)-f(y)\big| = 0 \\ & \Longleftrightarrow\  f(x)-f(y) = 0 \\ & \Longleftrightarrow\ f(x)=f(y) \Longleftrightarrow\ x=y \end{array}

(ostatnia równoważność wynika z iniektywności funkcji \displaystyle  f).
(b) Dla dowodu symetrii zauważmy, że dla dowolnych \displaystyle  x,y\in X mamy

\displaystyle  d(x,y) \ =\ \big|f(x)-f(y)\big| \ =\ \big|f(y)-f(x)\big| \ =\ d(y,x).

(c) Dla dowodu nierówności trójkąta zauważmy, że dla dowolnych \displaystyle  x,y\in X mamy

\begin{array}{lll} \displaystyle  d(x,y)&=& \big|f(x)-f(y)\big| \ =\ \big|f(x)-f(z)+f(z)+f(y)\big|\\ &\le&\big|f(x)-f(z)\big|+\big|f(z)-f(y)\big|=\ d(x,z)+d(z,y) \end{array}

(gdzie nierówność wynika z nierówności trójkąta dla metryki euklidesowej w \displaystyle \mathbb{R}).

Ćwiczenie 1.3.

Sprawdzić, czy funkcja \displaystyle  d\colon\mathbb{N}\times\mathbb{N}\longrightarrow\mathbb{R}_+ dana wzorem

\displaystyle  d(n,m) \ \stackrel{df}{=}\  \bigg|\frac{1}{n}-\frac{1}{m}\bigg| \qquad\forall\  n,m\in\mathbb{N}

jest metryką w \displaystyle \mathbb{N}. Jeśli tak, to jak wyglądają kule \displaystyle  K(1,1) oraz \displaystyle  K\bigg(3,\frac{1}{2}\bigg) w tej metryce.

Wskazówka

Należy wykorzystać ćwiczenie 1.2.

Rozwiązanie

Zauważmy, że funkcja \displaystyle  f\colon \mathbb{N}\longrightarrow\mathbb{R} dana wzorem

\displaystyle  f(n) \ =\ \frac{1}{n} \qquad\forall\  n\in\mathbb{N}

jest iniekcją oraz

\displaystyle  d(n,m) \ =\ \bigg|\frac{1}{n}-\frac{1}{m}\bigg| \ =\ \big|f(n)-f(m)\big|,

zatem możemy wprost skorzystać z ćwiczenia 1.2. i wywnioskować, że \displaystyle  d jest metryką.

Kula \displaystyle  K(1,1) jest zbiorem

\displaystyle  K(1,1) \ =\ \bigg\{ m\in\mathbb{N}: \bigg|1-\frac{1}{m}\bigg| <1 \bigg\}.

Rozwiązując powyższą nierówność, mamy

\displaystyle  -1 \ <\ 1-\frac{1}{m} \ <\ 1,

stąd

\displaystyle  0 \ <\ \frac{1}{m} \ <\ 2.

Ponieważ nierówność ta jest spełniona dla dowolnej liczby \displaystyle  m\in\mathbb{N}, zatem \displaystyle  K(1,1)=\mathbb{N}.

Podobnie

\displaystyle  K\bigg(3,\frac{1}{2}\bigg) \ =\ \bigg\{ m\in\mathbb{N}: \bigg|\frac{1}{3}-\frac{1}{m}\bigg| < \frac{1}{2} \bigg\}.

Rozwiązując powyższą nierówność, mamy

\displaystyle  -\frac{1}{2} \ <\ \frac{1}{3}-\frac{1}{m} \ <\ \frac{1}{2},

skąd

\displaystyle  -\frac{1}{6} \ <\ \frac{1}{m} \ <\ \frac{5}{6},

a więc \displaystyle  m>\frac{6}{5}. Zatem \displaystyle  K\bigg(3,\frac{1}{2}\bigg)= \big\{m\in\mathbb{N}:\ m\ge 2\big\}.

Uwaga: Łatwo sprawdzić, że \displaystyle \mathrm{diam}\, \mathbb{N}=1, zatem dowolna

kula o promieniu większym niż 1 jest równa całej przestrzeni \displaystyle \mathbb{N}.

Ćwiczenie 1.4.

Niech \displaystyle  (X,d) będzie przestrzenią metryczną. Udowodnić, że dla dowolnych zbiorów \displaystyle  A,B\subseteq X zachodzi implikacja

\displaystyle  A\subseteq B \ \Longrightarrow\ \mathrm{diam}\, A\le \mathrm{diam}\, B.

Wskazówka

Należy wykorzystać jedynie definicję średnicy zbioru.

Rozwiązanie

<flash>file=Am2.M01.C.R01.swf|width=375|height=375</flash>

Średnice zbiorów A i B gdy A\subseteq B

Mamy

\displaystyle  \mathrm{diam}\, A \ =\ \sup_{x,y\in A}d(x,y) \ \le\ \sup_{x,y\in B}d(x,y) \ =\ \mathrm{diam}\, B,

gdzie w nierówności skorzystaliśmy z faktu, że supremum po

większym zbiorze jest nie mniejsze.

Ćwiczenie 1.5.

Niech \displaystyle  (X,d) będzie przestrzenią metryczną. Udowodnić, że dla dowolnego \displaystyle  x_0\in X oraz \displaystyle  r\ge 0, zachodzi \displaystyle \mathrm{diam}\, \overline{K}(x_0,r)\le 2r. Czy nierówność "\displaystyle \le" można zastąpić równością?

Wskazówka

Korzystając z nierówności trójkąta, pokazać, że dla dowolnych \displaystyle  x,y\in K(x_0,r) mamy \displaystyle  d(x,y)\le 2r.

Rozwiązanie

Korzystając z nierówności trójkąta dla dowolnych \displaystyle  x,y\in \overline{K}(x_0,r), mamy:

\displaystyle  d(x,y) \ \le\ d(x,x_0)+d(x_0,y) \ \le\ r+r \ =\ 2r.

Ponieważ \displaystyle  x,y były dowolne, więc także:

\displaystyle  \mathrm{diam}\, K(x_0,r) \ =\ \sup_{x,y\in K(x_0,r)} \ \le\ 2r.

co należało dowieść.

Nierówności "\displaystyle \le" nie można zastąpić równością. Dla pewnych metryk (i kul domkniętych w nich zawartych) może bowiem zachodzić, że \displaystyle \mathrm{diam}\, \overline{K}(x_0,r)<2r. Dla przykładu rozważmy przestrzeń metryczną \displaystyle \big((0,1),d_2\big) (to znaczy przedział \displaystyle  (0,1)\subseteq \mathbb{R} z metrykę euklidesową). Wówczas

\displaystyle  \mathrm{diam}\, \overline{K}\bigg(\frac{1}{2},2\bigg) \ =\ 1 \ <\ 4,

przy czym promień \displaystyle  r=2 możemy tu zastąpić dowolną większą

liczbą i średnica nadal pozostanie 1.

Ćwiczenie 1.6.

Niech \displaystyle  (X,d) będzie przestrzenią metryczną. Udowodnić, że jeśli \displaystyle  x_0\in X,\displaystyle R>0,\displaystyle x_1\in K(x_0,r) oraz \displaystyle  r_1=R-d(x_0,x_1), to \displaystyle  r_1>0 oraz \displaystyle  K(x_1,r_1)\subseteq K(x_0,R).

Wskazówka

Wykonać rysunek. Nierówność \displaystyle  r_1>0 wynika wprost z definicji kuli. W celu pokazania inkluzji skorzystać jedynie z nierówności trójkąta.

Rozwiązanie

<flash>file=Am2.M01.C.R02.swf|width=375|height=375</flash>

Rysunek do dowodu twierdzenia z ćwiczenia 1.6.

Ponieważ, \displaystyle  x_1\in K(x_0,R), więc z definicji kuli mamy, że \displaystyle  d(x_0,x_1)<R, a zatem \displaystyle  r_1=R-d(x_0,x_1)>0.

W celu pokazania inkluzji

\displaystyle  K(x_1,r_1)\subseteq K(x_0,R) weźmy dowolne \displaystyle  x\in K(x_1,r_1). Z nierówności trójkąta oraz definicji \displaystyle  r_1, mamy

\displaystyle  d(x,x_0) \ \le\ d(x,x_1)+d(x_1,x_0) \ <\ r_1+(R-r_1) \ =\ R,

skąd wynika, że

\displaystyle  x_1\in K(x_0,R). Kończy to dowód inkluzji.

Ćwiczenie 1.7.

Udowodnić, że kule w \displaystyle  (X,d) są zbiorami otwartymi.

Wskazówka

Wykorzystać definicję zbioru otwartego oraz ćwiczenie 1.6..

Rozwiązanie

Aby pokazać, że kula \displaystyle  K(x_0,R) jest otwarta, weźmy dowolny punkt \displaystyle  x_1\in K(x_0,R). Z zadania 1.6 wynika, że istnieje \displaystyle  r_1>0 takie, że \displaystyle  K(x_1,r_1)\subseteq K(x_0,R). Ponieważ punkt \displaystyle  x_1\in K(x_0,R) był dowolnie wybrany, więc kula \displaystyle  K(x_0,R) jest otwarta.

Ćwiczenie 1.8.

Dany jest zbiór \displaystyle  A=[0,1]\times[0,1]\subseteq\mathbb{R}^2 oraz dwa punkty \displaystyle  x=(2,3) oraz \displaystyle  y=(3,-2). Wyznaczyć
(a) odległość punktów \displaystyle  x i \displaystyle  y,
(b) \displaystyle \mathrm{dist}\,\big(x,A\big),
(c) \displaystyle \mathrm{diam}\,(A),
kolejno w metrykach: dyskretnej \displaystyle  d_d; metryce rzece \displaystyle  d_r; gdy "rzeką" jest prosta o równaniu \displaystyle  y=-1; metryce kolejowej \displaystyle  d_k, gdy "węzłem" kolejowym jest punkt \displaystyle  (-1,0).

Wskazówka

Należy wykonać rysunek zbioru \displaystyle  A oraz wszystkich zadanych punktów

w układzie współrzędnych. Przy liczeniu odległości punktów oraz odległości punktu od zbioru należy skorzystać z definicji poszczególnych metryk oraz rysunków. Przy wyznaczaniu średnicy zbioru można skorzystać z ćwiczeń 1.4. i 1.5.

Rozwiązanie

<flash>file=Am2.M01.C.R03.swf|width=375|height=375</flash>

Odległości punkrów i odległość punktu od zbioru dla metryki rzeki

<flash>file=Am2.M01.C.R04.swf|width=375|height=375</flash>

Odległości punkrów i odległość punktu od zbioru dla metryki kolejowej

(1) Dla metryki dyskretnej mamy:
(a) \displaystyle  d_d(x,y)=1, gdyż \displaystyle  x\ne y,
(b) \displaystyle \mathrm{dist}\,(x,A)=1, gdyż \displaystyle  A\setminus \{x\}\ne\emptyset,
(c) \displaystyle \mathrm{diam}\, A=1, gdyż \displaystyle \# A\ge 2.

(2)
Dla metryki rzeki (z "rzeką" \displaystyle  l:\ y=-1) mamy:
(a) Zauważmy, że rzutem punktu \displaystyle  x=(2,3) na prostą \displaystyle  l jest punkt \displaystyle  x'=(2,-1) oraz rzutem punktu \displaystyle  y=(3,-2) na prostą \displaystyle  l jest punkt \displaystyle  y'=(3,-1). Zatem

\displaystyle  d_r(x,y) \ =\ d_2(x,x')+d_2(x',y')+d_2(y',y) \ =\ 3+1+2 \ =\ 6.

(b)

Odległość \displaystyle  x od zbioru \displaystyle  A w metryce rzece jest realizowana w punkcie \displaystyle  z=(1,0) (patrz rysunek; łatwo pokazać, że odległość od \displaystyle  x do dowolnego innego punktu zbioru \displaystyle  A jest większa, niż do \displaystyle  z), zatem

\displaystyle  \mathrm{dist}\, (x,A) \ =\ d_r\big((2,3),(1,0)\big) \ =\ 4+1+1 \ =\ 6.

(c)

Zauważmy, że:

\displaystyle  A \ \subseteq\ \overline{K}_{d_r}\bigg(\bigg(\frac{1}{2},-1\bigg),\frac{5}{2}\bigg).

Zatem z ćwiczeń 1.4. i 1.5. wynika, że

\displaystyle  \mathrm{diam}\, A \ \le\ \mathrm{diam}\, \overline{K}_{d_r}\bigg(\bigg(\frac{1}{2},-1\bigg),\frac{5}{2}\bigg) \ \le\ 5.

Ale z drugiej strony zauważmy, że dla punktów

\displaystyle  (0,1),(1,1)\in A mamy \displaystyle  d\big((0,0),(1,1)\big)=2+1+2=5, zatem \displaystyle \mathrm{diam}\, A\ge 5. Z obu nierówności wynika, że \displaystyle \mathrm{diam}\, A=5.

(3)
Dla metryki kolejowej (z "węzłem kolejowym" \displaystyle  S(-1,0) ) mamy:
(a)Mamy

\begin{array}{lll}\displaystyle  d_k(x,y) &=& d_2(x,S)+d_2(S,y)= d_2\big((2,3),(-1,0)\big)\\ &+& d_2\big((-1,0),(3,-2)\big)=3\sqrt{2}+2\sqrt{5}. \end{array}

(b)

Odległość \displaystyle  x od zbioru \displaystyle  A w metryce kolejowej jest realizowana w punkcie \displaystyle  z=(1,1) (patrz rysunek; łatwo pokazać, że odległość od \displaystyle  x do dowolnego innego punktu zbioru \displaystyle  A jest większa, niż do \displaystyle  z; zauważmy, że punkt \displaystyle  z należy do półprostej wychodzącej z \displaystyle  S i przechodzącej przez \displaystyle  x), zatem

\displaystyle  \mathrm{dist}\, (x,A) \ =\ d_k\big((2,3),(1,1)\big) \ =\ d_2\big((2,3),(1,1)\big) \ =\ \sqrt{5}.

(c)

Zauważmy, że:

\displaystyle  A \ \subseteq\ \overline{K}_{d_k}(S,\sqrt{5}).

Zatem z ćwiczeń 1.4. i 1.5. wynika, że

\displaystyle  \mathrm{diam}\, A \ \le\ \mathrm{diam}\, \overline{K}_{d_k}(S,\sqrt{5}) \ \le\ 2\sqrt{5}.

W tym przypadku żadne dwa punkty nie realizują supremum

z występującego w definicji średnicy zbioru \displaystyle  A. Możemy jednak do tego supremum dowolnie się zbliżyć. Niech

\displaystyle  x_n \ =\ \bigg(1-\frac{1}{n},1\bigg)\in A,\qquad y_n \ =\ \bigg(1,1-\frac{1}{n}\bigg)\in A.

Wówczas

\displaystyle  d_k(x_n,y_n) \ =\ d_2 (x_n,S)+d_2(S,y_n) \ =\ \sqrt{1+\bigg(2-\frac{1}{n}\bigg)^2} +\sqrt{4+\bigg(1-\frac{1}{n}\bigg)^2}

oraz

\displaystyle  \sup_{a,b\in A}d(a,b) \ \ge\ \lim\limits_{n\rightarrow +\infty} d_k(x_n,y_n) \ =\ \sqrt{5}+\sqrt{5} \ =\ 2\sqrt{5}.

Zatem ostatecznie \displaystyle \mathrm{diam}\, A=2\sqrt{5}.

Ćwiczenie 1.9.

Niech \displaystyle  (X,d) będzie przestrzenią metryczną. Udowodnić, że
(a) suma dowolnej rodziny zbiorów otwartych jest zbiorem otwartym,
(b) przecięcie (część wspólna) skończonej rodziny zbiorów otwartych jest zbiorem otwartym.

Wskazówka

(a)-(b) Skorzystać z definicji zbiorów otwartych.

Rozwiązanie

(a) Niech \displaystyle \{U_s\}_{s\in S} będzie rodziną zbiorów otwartych oraz niech \displaystyle  U=\bigcup_{s\in S}U_s będzie zbiorem. Należy pokazać, że zbiór \displaystyle  U jest otwarty. W tym celu wybierzmy dowolny \displaystyle  x\in U. Z definicji sumy zbiorów wynika, że

\displaystyle  \exists s_0\in S:\ x\in U_{s_0}.

Ponieważ zbiór \displaystyle  U_{s_0} jest otwarty, zatem

\displaystyle  \exists r>0:\ K(x,r)\subseteq U_{s_0}.

Ale wówczas także

\displaystyle  K(x,r) \ \subseteq\ \bigcup_{s\in S_0}U_s \ =\ U.

Pokazaliśmy zatem, że dowolny punkt zbioru \displaystyle  U jest zawarty w \displaystyle  U wraz z pewną kulą (o dodatnim promieniu), której jest środkiem. Zatem \displaystyle  U jest zbiorem otwartym, co należało pokazać.
(b) Niech \displaystyle \{U_k\}_{k=1}^n będzie rodziną (skończoną) zbiorów otwartych oraz niech \displaystyle  U=\bigcap_{k=1}^n U_k. Należy pokazać, że zbiór \displaystyle  U jest otwarty. W tym celu wybierzmy dowolny \displaystyle  x\in U. Z definicji sumy zbiorów i z założenia wynika, że

\displaystyle  \forall k\in\{1,\ldots,n\}:\ \exists r_k>0:\ K(x,r_k)\subseteq U_k.

Niech \displaystyle  r=\min\{r_1,\ldots,r_k\}. Wówczas \displaystyle  r>0 (zauważmy w tym miejscu, iż istotny w naszym dowodzie jest fakt że rodzina jest skończona; w przeciwnym bowiem wypadku moglibyśmy otrzymać \displaystyle  r=0). Wówczas

\displaystyle  \forall k\in\{1,\ldots,n\}:\ K(x,r) \ \subseteq\ K(x,r_k) \ \subseteq\ U_k,

a więc

\displaystyle  \forall k\in\{1,\ldots,n\}:\ K(x,r) \ \subseteq\ \bigcap_{k=1}^n U_k \ =\ U.

Pokazaliśmy zatem, że dowolny punkt zbioru \displaystyle  U jest zawarty w \displaystyle  U wraz z pewną kulą (o dodatnim promieniu), której jest środkiem. Zatem \displaystyle  U jest zbiorem otwartym, co należało pokazać.