Analiza matematyczna 2/Ćwiczenia 1: Przestrzenie metryczne

Przestrzenie metryczne

Ćwiczenie 1.1.

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

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

(a) Udowodnić, że $d$ jest metryką w $X_n$ (jest to tak zwana metryka Hamminga).
(b) Czy $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 $w=w_1{w}_2\dots w_n$ i $v=v_1{v}_2\dots v_n$, rozważyć zbiór $A_{wv}$ indeksów $i\in \{1,\dots ,n\}$ takich, że słowa te mają różną $i$-tą literę, to znaczy $w_i\ne v_i$. Jaki jest związek zbioru $A_{wv}$ z odległością $d(w,v)$? Jaki jest związek między zbiorami $A_{wv}$ oraz $A_{wz}$ i $A_{zv}$? Dlaczego? Co z tego wynika?

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

Rozwiązanie

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

$A_{wv}=\{i\in \{1,2,\dots ,n\}:w_i\ne v_i\}$

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

$d(w,v)=0⟺\mathrm{\#}{A}_{wv}=0⟺[\mathrm{\forall }i:w_i=v_i]⟺w=v$

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

$d(w,v)=\mathrm{\#}{A}_{wv}=\mathrm{\#}{A}_{wv}=d(v,w)$

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

$A_{wv}\subseteq A_{wz}\cup A_{zv}$

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

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

$\mathrm{\#}{A}_{wv}\le \mathrm{\#}{A}_{wz}\cup \mathrm{\#}{A}_{zv}$,

zatem

$d(w,v)=\mathrm{\#}{A}_{wv}\le \mathrm{\#}{A}_{wz}\cup \mathrm{\#}{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 $w\in X_n$ mamy bowiem $d(w,w)=n\ne 0$.

Ćwiczenie 1.2.

Niech $X$ będzie dowolnym zbiorem niepustym oraz niech $f:X⟶\mathbb{ℝ}$ będzie dowolną iniekcją. Udowodnić, że odwzorowanie dane wzorem

$d(x,y)\stackrel{df}{=}|f(x)-f(y)|\mathrm{\forall }x,y\in X$

jest metryką w $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 $\mathbb{ℝ}$ (to znaczy nierówność trójkąta dla metryki euklidesowej w $\mathbb{ℝ}$).

Rozwiązanie

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

$\begin{array}{lll}d(x,y)=0& ⟺& |f(x)-f(y)|=0\\ & ⟺f(x)-f(y)=0\\ & ⟺f(x)=f(y)⟺x=y\end{array}$

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

$d(x,y)=|f(x)-f(y)|=|f(y)-f(x)|=d(y,x)$

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

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

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

Ćwiczenie 1.3.

Sprawdzić, czy funkcja $d:\mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}}⟶{\mathbb{ℝ}}_{+}$ dana wzorem

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

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

Wskazówka

Należy wykorzystać ćwiczenie 1.2.

Rozwiązanie

Zauważmy, że funkcja $f:\mathbb{\mathbb{N}}⟶\mathbb{ℝ}$ dana wzorem

$f(n)=\frac{1}{n}\mathrm{\forall }n\in \mathbb{\mathbb{N}}$

jest iniekcją oraz

$d(n,m)=|\frac{1}{n}-\frac{1}{m}|=|f(n)-f(m)|$,

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

Kula $K(1,1)$ jest zbiorem

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

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

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

stąd

$0<\frac{1}{m}<2$

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

Podobnie

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

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

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

skąd

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

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

Uwaga: Łatwo sprawdzić, że $\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}\mathbb{\mathbb{N}}=1$, zatem dowolna kula o promieniu większym niż 1 jest równa całej przestrzeni $\mathbb{\mathbb{N}}$.

Ćwiczenie 1.4.

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

$A\subseteq B⟹\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}A\le \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}B$

Wskazówka

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

Rozwiązanie

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

Mamy

$\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}A=\underset{x,y\in A}{\sup }d(x,y)\le \underset{x,y\in B}{\sup }d(x,y)=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}B$,

gdzie w nierówności skorzystaliśmy z faktu, że supremum po większym zbiorze jest nie mniejsze.

Ćwiczenie 1.5.

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

Wskazówka

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

Rozwiązanie

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

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

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

$\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}K(x_0,r)=\underset{x,y\in K(x_0,r)}{\sup }\le 2r$

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

$\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}\bar{K}(\frac{1}{2},2)=1<4$,

przy czym promień $r=2$ możemy tu zastąpić dowolną większą liczbą i średnica nadal pozostanie 1.

Ćwiczenie 1.6.

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

Wskazówka

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

Rozwiązanie

Rysunek do dowodu twierdzenia z ćwiczenia 1.6.

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

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

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

skąd wynika, że $x_1\in K(x_0,R)$. Kończy to dowód inkluzji.

Ćwiczenie 1.7.

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

Wskazówka

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

Rozwiązanie

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

Ćwiczenie 1.8.

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

Wskazówka

Należy wykonać rysunek zbioru $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

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

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

(1) Dla metryki dyskretnej mamy:
(a) $d_d(x,y)=1$, gdyż $x\ne y$,
(b) $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(x,A)=1$, gdyż $A\setminus \{x\}\ne \mathrm{\varnothing }$,
(c) $\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}A=1$, gdyż $\mathrm{\#}A\ge 2$.

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

$d_r(x,y)=d_2(x,x^{\prime })+d_2(x^{\prime },y^{\prime })+d_2(y^{\prime },y)=3+1+2=6$

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

$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(x,A)=d_r((2,3),(1,0))=4+1+1=6$

(c) Zauważmy, że:

$A\subseteq {\bar{K}}_{d_r}\left(\right(\frac{1}{2},-1),\frac{5}{2})$

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

$\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}A\le \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}{\bar{K}}_{d_r}\left(\right(\frac{1}{2},-1),\frac{5}{2})\le 5$

Ale z drugiej strony zauważmy, że dla punktów $(0,1),(1,1)\in A$ mamy $d((0,0),(1,1))=2+1+2=5$, zatem $\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}A\ge 5$. Z obu nierówności wynika, że $\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}A=5$.

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

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

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

$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(x,A)=d_k((2,3),(1,1))=d_2((2,3),(1,1))=\sqrt{5}$

(c) Zauważmy, że:

$A\subseteq {\bar{K}}_{d_k}(S,\sqrt{5})$

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

$\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}A\le \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}{\bar{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 $A$. Możemy jednak do tego supremum dowolnie się zbliżyć. Niech

$x_n=(1-\frac{1}{n},1)\in A,y_n=(1,1-\frac{1}{n})\in A$

Wówczas

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

oraz

$\underset{a,b\in A}{\sup }d(a,b)\ge \lim {}_{n\to +\mathrm{\infty }}{d}_k(x_n,y_n)=\sqrt{5}+\sqrt{5}=2\sqrt{5}$

Zatem ostatecznie $\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}A=2\sqrt{5}$.

Ćwiczenie 1.9.

Niech $(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 $\{U_s{\}}_{s\in S}$ będzie rodziną zbiorów otwartych oraz niech $U=\bigcup _{s\in S}{U}_s$ będzie zbiorem. Należy pokazać, że zbiór $U$ jest otwarty. W tym celu wybierzmy dowolny $x\in U$. Z definicji sumy zbiorów wynika, że

$\mathrm{\exists }{s}_0\in S:x\in U_{s_0}$

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

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

Ale wówczas także

$K(x,r)\subseteq \bigcup _{s\in S_0}{U}_s=U$

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

$\mathrm{\forall }k\in \{1,\dots ,n\}:\mathrm{\exists }{r}_k>0:K(x,r_k)\subseteq U_k$

Niech $r=\min \{r_1,\dots ,r_k\}$. Wówczas $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ć $r=0$). Wówczas

$\mathrm{\forall }k\in \{1,\dots ,n\}:K(x,r)\subseteq K(x,r_k)\subseteq U_k$,

a więc

$\mathrm{\forall }k\in \{1,\dots ,n\}:K(x,r)\subseteq \bigcap _{k=1}^n{U}_k=U$

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