udowodnij ze ta metryka spelnia warunek trójkąta

[kadykianus]

Są 3 zbiory: A liczący \(\displaystyle{ N_{A}}\) elementów, B liczący \(\displaystyle{ N_{B}}\) elementow i C liczacy \(\displaystyle{ N_{C}}\) elementow.

Istnieje \(\displaystyle{ K}\) klastrów (kubeczków, wiader, pojemników itp.). Załóżmy, że w klastrze pierwszym \(\displaystyle{ k_{1}}\) znajduje się \(\displaystyle{ n_{Ak1}}\) elementow zbioru A, w klastrze drugim \(\displaystyle{ k_{2}}\) znajduje się \(\displaystyle{ n_{Ak2}}\) elementow zbioru A itd. Podobnie z B.

Dana jest metryka postaci:

\(\displaystyle{ d(A,B)= \frac{1}{2} \sum_{k=1}^{K}| \frac{n_{Ak}}{N_{A}}- \frac{n_{Bk}}{N_{B}}|}\)

gdzie

\(\displaystyle{ d(A,B)}\) jest odległością między zbiorami A i B. Oczywiście \(\displaystyle{ 0\le d(A,B) \le 1}\)
\(\displaystyle{ n_{Ak}}\) jest liczbą elementów zbioru A w klastrze \(\displaystyle{ k}\)
\(\displaystyle{ n_{Bk}}\) jest liczbą elementów zbioru B w klastrze \(\displaystyle{ k}\)
Udowodnij, że metryka ta spełnia tzw. warunek trójkąta, czyli, ze jest prawdą, że

\(\displaystyle{ d(A,B) \le d(A,C)+d(B,C)}\) dla dowolnego \(\displaystyle{ k \ge 2}\)

[klaustrofob]

próbowałeś standardowo:

\(\displaystyle{ | \frac{n_{Ak}}{N_{A}}- \frac{n_{Bk}}{N_{B}}|=| \frac{n_{Ak}}{N_{A}}- \frac{n_{Ck}}{N_{C}}+\frac{n_{Ck}}{N_{C}}- \frac{n_{Bk}}{N_{B}}| \leq | \frac{n_{Ak}}{N_{A}}- \frac{n_{Ck}}{N_{C}}|+|\frac{n_{Ck}}{N_{C}}- \frac{n_{Bk}}{N_{B}}|}\)

i teraz wysumować to stronami do K?

ciekawy pomysł, gdzie się takie rzeczy robi?

[kadykianus]

To jest metryka którą wymyśliłem do badań nad strukturą genetyczną bakterii
Bardzo chciałbym to udowodnić ale nie umiem. Umiem dla k=2 ale na więcej k już nie.
A takie rzeczy robi sie na Uniwersytecie Wroclawskim

Jestem przekonany że nierówność trójkąta jest spełniona bo próbowałem Solverem w Excelu by spróbował znaleźć takie proporcje dla k=5 by nie była spełniona ale nie znalazł. Tylko, że to nie jest dowód.

[klaustrofob]

dla dowolnego 1<=k<=K jest tak:
\(\displaystyle{ | \frac{n_{Ak}}{N_{A}}- \frac{n_{Bk}}{N_{B}}|\leq | \frac{n_{Ak}}{N_{A}}- \frac{n_{Ck}}{N_{C}}|+| \frac{n_{Ck}}{N_{C}}- \frac{n_{Bk}}{N_{B}}|}\)
sumujemy od 1 do K:
\(\displaystyle{ \sum_{1}^{K}| \frac{n_{Ak}}{N_{A}}- \frac{n_{Bk}}{N_{B}}|\leq \sum_{1}^{K}(| \frac{n_{Ak}}{N_{A}}- \frac{n_{Ck}}{N_{C}}|+| \frac{n_{Ck}}{N_{C}}- \frac{n_{Bk}}{N_{B}}|)= \sum_{1}^{K}|\frac{n_{Ak}}{N_{A}}- \frac{n_{Ck}}{N_{C}}|+\sum_{1}^{K}| \frac{n_{Ck}}{N_{C}}- \frac{n_{Bk}}{N_{B}}|}\)
gdzieś robię błąd?

[kadykianus]

Nie widze tu błędu. Ale czy widać z tego, że nierówność musi być spełniona? Przyznam sie, że bardziej przemawiałby do mnie dowód "nie wprost", tzn. założyć, że nierówność nie jest spełniona i doprowadzić tym samym do sprzeczności, wykazująć, ze musi być spełniona. Ogólnie, przyjąć na chwilę, że

\(\displaystyle{ \sum_{1}^{K}| \frac{ n_{Ak} }{N _{A} } - \frac{n _{Bk} }{ N_{B} }| > \sum_{1}^{K}| \frac{ n_{Ak} }{N _{A} } - \frac{n _{Ck} }{ N_{C} }| + \sum_{1}^{K}| \frac{ n_{Ck} }{N _{C} } - \frac{n _{Bk} }{ N_{B} }|}\)

i wykazać, że dochodzi się do absurdu. Co o tym sądzisz? Ja tego nie umiem zrobić, bo albo to jest za trudne albo tak proste, ze tego nie widzę.

[klaustrofob]

nie rozumiem z czym masz problem - pewnie czegoś nie dostrzegam. dla porządku podsumuję Twoje rozumowanie.
a) w pewnej rodzinie zbiorów skończonych definiujemy funkcję d podanym przez Ciebie wzorem. chcemy pokazać, że jest to metryka
b) musimy pokazać, że funkcja spełnia warunki: 1) d(A,B)>= 0; 2) d(A,B)=0<=> A=B; 3) d(A,B)=d(B,A); 4) nierówność trójkąta.

dowód: 1, 3 - oczywiste. 4) uzasadniłem. 2) ? jeżeli gdzieś jest problem, to tu właśnie. można chyba wyobrazić sobie dwa różne zbiory, które z każdym klastrem mają tyle samo wspólnych elementów? wtedy 2) zawodzi.

[kadykianus]

To wszystko wiem. Chodzi o 4). Mówisz, że dowiodles i pewnie tak, ale nie rozumiem dlaczego dowiodłeś. Po tym rozpisaniu sumami wg. Ciebie widać to, a ja nie widzę. Tu mam problem. Jak byś mi pokazał, ten rozpis i powiedział ze nierówność nie jest spełniona to bym też Ci uwierzył, bo nie dostrzegam gdzie tu jest dowód na to, że tak musi być. Dlaczego tak musi być, że ta nierówność jest spełniona??

[klaustrofob]

jeszcze raz - jak pokazałem wyżej, dochodzimy do nierówności
\(\displaystyle{ \sum_{1}^{K}| \frac{n_{Ak}}{N_{A}}- \frac{n_{Bk}}{N_{B}}| \leq \sum_{1}^{K}| \frac{n_{Ak}}{N_{A}}- \frac{n_{Ck}}{N_{C}}|+ \sum_{1}^{K}| \frac{n_{Ck}}{N_{C}}- \frac{n_{Bk}}{N_{B}}|}\)
mnożymy stronami przez 1/2 i otrzymujemy:
\(\displaystyle{ d(A,B)\leq d(A,C)+d(C,B)}\), czyli warunek trójkąta.

[kadykianus]

Przykro mi ale to nie jest dowód. Napisałeś to samo na dwa różne sposoby. Trzeba wykazać, że ta nierówność nie może być fałszywa (czyli musi być prawdziwa). To znaczy, ze nie da sie znależć takiego rozkładu elementów zbiorów A, B i C w K klastrach aby nierówność nie była spełniona.

[klaustrofob]

(...) Trzeba wykazać, że ta nierówność nie może być fałszywa (czyli musi być prawdziwa). To znaczy, ze nie da sie znależć takiego rozkładu elementów zbiorów A, B i C w K klastrach aby nierówność nie była spełniona.

po raz ostatni, bo najwyraźniej czegoś nie rozumiem: masz K zbiorów nazywanych klastrami. bierzesz dowolne dwa zbiory A i B. dla każdego klastra wyznaczasz różnice jego "istotności" dla poszczególnych zbiorów. sumujesz te różnice.

jeżeli tak właśnie jest, to przedstawione przeze mnie "rachunki" są dowodem - to prosta konsekwencja nierówności trójkąta.

natomiast wątpię, by udało się pokazać warunek identyczności: d(A,B)=0<=> A=B.

[kadykianus]

Nie chce wykazywać identyczności tylko nierówność trójkąta. Ma być dowód. Wiem, ze rozumiesz jak działa ta metryka bo to widać po rachunkach i gadce, ale trzeba udowodnić. Ja napisałem te nierówność symbolicznie, w stylu \(\displaystyle{ d(A,B)}\) a Ty to samo napisałeś wzorami jawnymi, po czym z powrotem w stylu \(\displaystyle{ d(A,B)}\). Innymi słowy, wyszedleś od nierówności i do niej doszedleś a to nie jest dowód. Trzeba te nierówność dopiero udowodnić a nie zapisać pod inna postacią i wrócić do zapisu pierwszego. To dlatego sugerowałem, aby pokazać, co się dzieje gdyby założyć, że nie jest ona prawdziwa. Doprowadzając do sprzeczności mozna jednoznacznie dowieść, że nie może byc ona nieprawdziwa, czyli musi być prawdziwa, co należało dowieść. Tak to powinno wyglądać.

[klaustrofob]

to jest właśnie siła formalizmu - jeżeli obiekty spełniają pewne warunki, to niezależnie od ich natury, muszą spełniać inne, które z tych pierwszych wynikają. iloczyn skalarny wektorów spełnia nierówność Schwarza niezależnie od tego, czym ze "swej natury" są wektory: funkcjami, n-kami liczb rzeczywistych, strzałkami...

jedyne, od czego wyszedłem w dowodzie, to definicja "metryki" - wykorzystując nierówność trójkąta dla wartości bezwzględnej udowodniłem, że i ta "metryka" spełnia nierówność trójkąta. zresztą - popytaj któregokolwiek z matematyków na UWr. Zresztą, o ile zdołałem się zorientować, jest tu Jan Kraszewski z UWr - zapytaj Go na priwa.