Kazdy (skonczony) porzadek czesciowy mozna rozszerzyc do liniowego - dowod

[sznury]

Prosze skomentowac moje rozumowanie

Teza:
X - zbior skonczony czesciowo uporzadkowany
Chce pokazac ze mozna go uporzadkowac liniowo (kazde 2 elementy beda w
relcaji ze soba)

Dowod przez indukcje
n=1
zbior jednoelementowy jest uporzadkowany czesciowo i liniowo
(zwrotnosc)

Krok ind.
Niech n dowolne. Zakladam, ze kazdy czesciowy porzadek na dowolnym
zbiorze n-elementowym mozna rozszerzyc do porzadku liniowego.
Chce pokazac ze teza zachodzi dla dowolnego zbioru (n+1)-elementowego

Niech X' zbior n+1-elementowy czesciowo uporzadkowany. Dziele go na 2
czesci, w jednej n-elementow w drugiej 1 element. Z zalozenia umiem
uporzadkowac liniowo pierwsza czesc i teraz dla zostawionego jednego
elementu ustalam ze dla kazdego elementu z pierwszej czesci zbioru jest
on w relacji z nim co rozszerza czesciowy porzadek zbioru X' do p.
liniowego.

Czy to poprawny dowod??

[Tomasz Dryjanski]

Post by sznury
X - zbior skonczony czesciowo uporzadkowany
Chce pokazac ze mozna go uporzadkowac liniowo (kazde 2 elementy beda w
relcaji ze soba)
Dowod przez indukcje
n=1
zbior jednoelementowy jest uporzadkowany czesciowo i liniowo
(zwrotnosc)
Krok ind.
Niech n dowolne. Zakladam, ze kazdy czesciowy porzadek na dowolnym
zbiorze n-elementowym mozna rozszerzyc do porzadku liniowego.
Chce pokazac ze teza zachodzi dla dowolnego zbioru (n+1)-elementowego
Niech X' zbior n+1-elementowy czesciowo uporzadkowany. Dziele go na 2
czesci, w jednej n-elementow w drugiej 1 element. Z zalozenia umiem
uporzadkowac liniowo pierwsza czesc i teraz dla zostawionego jednego
elementu ustalam ze dla kazdego elementu z pierwszej czesci zbioru jest on
w relacji z nim co rozszerza czesciowy porzadek zbioru X' do p. liniowego.
Czy to poprawny dowod??

W jaki sposob wyznaczasz podzial X' na dwie czesci?
W jakiej relacji jest ten element z elementami z pierwszej czesci?
Jesli odpowiedzia na pierwsze pytanie jest "dowolnie",
a na drugie pytanie "mniejszy", to dowod nie jest poprawny,
bo wyrozniony element moze juz byc w innej relacji z jakims
elementem z pierwszej czesci.

Da sie z tego zrobic poprawny dowod, ale trzeba go doprecyzowac.
A pozniej zweryfikowac przy uzyciu np. takiego przykladu:
Wezmy zbior X' = {a,b,c,d,e} z nastepujacym porzadkiem czesciowym:
a>c, b>c, c>d, c>e
i podzielmy go na zbiory X = {a,b,d,e} i X'' = {c}.
Rozszerzmy porzadek na X do liniowego itd.

T. D.

[sznury]

Post by Tomasz Dryjanski

Post by sznury
X - zbior skonczony czesciowo uporzadkowany
Chce pokazac ze mozna go uporzadkowac liniowo (kazde 2 elementy beda w
relcaji ze soba)
Dowod przez indukcje
n=1
zbior jednoelementowy jest uporzadkowany czesciowo i liniowo
(zwrotnosc)
Krok ind.
Niech n dowolne. Zakladam, ze kazdy czesciowy porzadek na dowolnym
zbiorze n-elementowym mozna rozszerzyc do porzadku liniowego.
Chce pokazac ze teza zachodzi dla dowolnego zbioru (n+1)-elementowego
Niech X' zbior n+1-elementowy czesciowo uporzadkowany. Dziele go na 2
czesci, w jednej n-elementow w drugiej 1 element. Z zalozenia umiem
uporzadkowac liniowo pierwsza czesc i teraz dla zostawionego jednego
elementu ustalam ze dla kazdego elementu z pierwszej czesci zbioru jest on
w relacji z nim co rozszerza czesciowy porzadek zbioru X' do p. liniowego.
Czy to poprawny dowod??

W jaki sposob wyznaczasz podzial X' na dwie czesci?
W jakiej relacji jest ten element z elementami z pierwszej czesci?

Powiedzmy, ze biore zbior X czesciowo uporzadkowany i dodaje do niego
jeden element, ktory nie jest w relacji z zadnym z X.
Wydaje mi sie ze to wystaczy, zeby dowod byl poprawny. Czy sie myle ?

Post by Tomasz Dryjanski
Jesli odpowiedzia na pierwsze pytanie jest "dowolnie",
a na drugie pytanie "mniejszy", to dowod nie jest poprawny,
bo wyrozniony element moze juz byc w innej relacji z jakims
elementem z pierwszej czesci.
Da sie z tego zrobic poprawny dowod, ale trzeba go doprecyzowac.
a>c, b>c, c>d, c>e
i podzielmy go na zbiory X = {a,b,d,e} i X'' = {c}.
Rozszerzmy porzadek na X do liniowego itd.
T. D.

[Tomasz Dryjanski]

Post by sznury

Post by Tomasz Dryjanski
W jaki sposob wyznaczasz podzial X' na dwie czesci?
W jakiej relacji jest ten element z elementami z pierwszej czesci?

Powiedzmy, ze biore zbior X czesciowo uporzadkowany i dodaje do niego
jeden element, ktory nie jest w relacji z zadnym z X.
Wydaje mi sie ze to wystaczy, zeby dowod byl poprawny. Czy sie myle ?

Mylisz sie. Aby uzyskac krok indukcyjny, musisz wziac /dowolny/
zbior X'. Nie wiadomo, czy znajdziesz w nim element, ktory nie jest
w relacji z zadnym z pozostalych. Patrz przyklad ponizej.

Post by sznury

Post by Tomasz Dryjanski
a>c, b>c, c>d, c>e
i podzielmy go na zbiory X = {a,b,d,e} i X'' = {c}.
Rozszerzmy porzadek na X do liniowego itd.

Przeprowadz swoj dowod dla tego przypadku.

T. D.

[sznury]

Post by sznury

Post by Tomasz Dryjanski

Post by sznury
X - zbior skonczony czesciowo uporzadkowany
Chce pokazac ze mozna go uporzadkowac liniowo (kazde 2 elementy beda
w relcaji ze soba)
Dowod przez indukcje
n=1
zbior jednoelementowy jest uporzadkowany czesciowo i liniowo
(zwrotnosc)
Krok ind.
Niech n dowolne. Zakladam, ze kazdy czesciowy porzadek na dowolnym
zbiorze n-elementowym mozna rozszerzyc do porzadku liniowego.
Chce pokazac ze teza zachodzi dla dowolnego zbioru (n+1)-elementowego
Niech X' zbior n+1-elementowy czesciowo uporzadkowany. Dziele go na 2
czesci, w jednej n-elementow w drugiej 1 element. Z zalozenia umiem
uporzadkowac liniowo pierwsza czesc i teraz dla zostawionego jednego
elementu ustalam ze dla kazdego elementu z pierwszej czesci zbioru
jest on w relacji z nim co rozszerza czesciowy porzadek zbioru X' do
p. liniowego.
Czy to poprawny dowod??

W jaki sposob wyznaczasz podzial X' na dwie czesci?
W jakiej relacji jest ten element z elementami z pierwszej czesci?

Powiedzmy, ze biore zbior X czesciowo uporzadkowany i dodaje do niego
jeden element, ktory nie jest w relacji z zadnym z X.
Wydaje mi sie ze to wystaczy, zeby dowod byl poprawny. Czy sie myle ?

Inaczej - X' jest czesciowo uporzadkowany wiec z zalozenia umiem
uporzadkowac zbior n-elementowy a dla dodatkowego n+1wszego elementu
sprawdzam, czy jest on w relacji z ktorymkolwiek z n-elementow i jesli
nie jest to rozbie relacje miedzy nimi. Jesli juz jest to zostawiam bez
zmian.

Post by sznury

Post by Tomasz Dryjanski
Jesli odpowiedzia na pierwsze pytanie jest "dowolnie",
a na drugie pytanie "mniejszy", to dowod nie jest poprawny,
bo wyrozniony element moze juz byc w innej relacji z jakims
elementem z pierwszej czesci.
Da sie z tego zrobic poprawny dowod, ale trzeba go doprecyzowac.
a>c, b>c, c>d, c>e
i podzielmy go na zbiory X = {a,b,d,e} i X'' = {c}.
Rozszerzmy porzadek na X do liniowego itd.
T. D.

[Tomasz Dryjanski]

Post by sznury
Inaczej - X' jest czesciowo uporzadkowany wiec z zalozenia umiem
uporzadkowac zbior n-elementowy a dla dodatkowego n+1wszego elementu
sprawdzam, czy jest on w relacji z ktorymkolwiek z n-elementow i jesli nie
jest to rozbie relacje miedzy nimi. Jesli juz jest to zostawiam bez zmian.

Rozwaz nastepujaca sytuacje:
X' = {a,b,c,d}
a<b, a<c, b<d, c<d
i wyodrebnij element b.
Pozostaly zbior X = {a,c,d} jest juz liniowo uporzadkowany,
wiec nie musisz nic z nim robic. Ale jesli dolaczysz element b
zostawiajac relacje bez zmian, porzadek ktory otrzymasz nie bedzie liniowy.

T. D.

PS. Odpowiadajac na wiadomosc wycinaj zbedne cytaty.

[sznury]

Post by Tomasz Dryjanski
X' = {a,b,c,d}
a<b, a<c, b<d, c<d
i wyodrebnij element b.
Pozostaly zbior X = {a,c,d} jest juz liniowo uporzadkowany,
wiec nie musisz nic z nim robic. Ale jesli dolaczysz element b
zostawiajac relacje bez zmian, porzadek ktory otrzymasz nie bedzie liniowy.

No ok, dolaczam b i sprawdzam ktore elementy sa w relacji z b ( sa nimi
a i d ) wiec dodaje jeszcze relacje b<c i mam (chyba) porzadek liniowy.
a<b b<d => a<d
Tak na marginesie to < nie jest relecje czesciowo porzadkujaca gdzyz
dla zadnego a a<a ( jeden z warunkow )... troche sie namieszalo... co
teraz ??

Kazde 2 elementy sa ze soba w relacji...
Moze ja juz nie widze bledow swojego myslenia... Ktos zechce mnie
oswiecic i przedstawic pelny dowod indukcyjny..??

[Tomasz Dryjanski]

Post by Tomasz Dryjanski
X' = {a,b,c,d}
a<b, a<c, b<d, c<d
i wyodrebnij element b.
Pozostaly zbior X = {a,c,d} jest juz liniowo uporzadkowany,
wiec nie musisz nic z nim robic. Ale jesli dolaczysz element b
zostawiajac relacje bez zmian, porzadek ktory otrzymasz nie bedzie liniowy.

No ok, dolaczam b i sprawdzam ktore elementy sa w relacji z b ( sa nimi a
i d ) wiec dodaje jeszcze relacje b<c i mam (chyba) porzadek liniowy.
a<b b<d => a<d

Chyba?
Napisz w dowodzie w jaki sposob dodajesz relacje w ogolnym przypadku

Tak na marginesie to < nie jest relecje czesciowo porzadkujaca gdzyz dla
zadnego a a<a ( jeden z warunkow )... troche sie namieszalo... co teraz ??

Pominalem wszystkie "x<x" dla prostoty zapisu.

T. D.

[sznury]

Post by Tomasz Dryjanski

No ok, dolaczam b i sprawdzam ktore elementy sa w relacji z b ( sa nimi a
i d ) wiec dodaje jeszcze relacje b<c i mam (chyba) porzadek liniowy.
a<b b<d => a<d

Chyba?

Napisz w dowodzie w jaki sposob dodajesz relacje w ogolnym przypadku
No i tu jest problem .... :) ale nie twierdze ze tego nie da sie pokazac
poprostu ja nie wiem jak... ( moze sie nie da - tez nie wiem )

W takim razie czy umiesz to udowodnic?

Post by Tomasz Dryjanski

Tak na marginesie to < nie jest relecje czesciowo porzadkujaca gdzyz dla
zadnego a a<a ( jeden z warunkow )... troche sie namieszalo... co teraz ??

[Tomasz Dryjanski]

Moze ja juz nie widze bledow swojego myslenia... Ktos zechce mnie oswiecic
i przedstawic pelny dowod indukcyjny..??

Jestes juz bardzo blisko wlasciwego wyniku.

T. D.

[Tomasz Dryjanski]

Post by Tomasz Dryjanski

Post by sznury
Moze ja juz nie widze bledow swojego myslenia... Ktos zechce mnie
oswiecic i przedstawic pelny dowod indukcyjny..??

Jestes juz bardzo blisko wlasciwego wyniku.

... ktorego dla odmiany ja przestalem byc pewien...
Zrob inaczej.
Wybierz dowolny element, i podziel zbior pozostalych elementow
na dwa: (wiekszych lub nieporownywalnych) i mniejszych.
Dalej wiadomo.

T. D.

[sznury]

Post by Tomasz Dryjanski
Zrob inaczej.
Wybierz dowolny element, i podziel zbior pozostalych elementow
na dwa: (wiekszych lub nieporownywalnych) i mniejszych.
Dalej wiadomo.
T.D.

Ok. Z przechodniosci wynika ze wyrozniony element jest w relacji z
elementami mniejszmi-rownymi i wiekszymi od siebie. Teraz zabieram sie
za elementy ktorych nie da sie ( jeszcze porownac )
No i nasowa sie pytanie jak zdefiniowac teraz relacje, tzn jak pokazac
ze wprowadzenie relacji pomiedzy te elementy nie popsuje np. czesciowego
porzadku? ( moze to jest oczywiste ale jeszcze tego nie widze )

[Maciek]

Post by sznury

Post by Tomasz Dryjanski
Zrob inaczej.
Wybierz dowolny element, i podziel zbior pozostalych elementow
na dwa: (wiekszych lub nieporownywalnych) i mniejszych.
Dalej wiadomo.
T.D.

Ok. Z przechodniosci wynika ze wyrozniony element jest w relacji z
elementami mniejszmi-rownymi i wiekszymi od siebie. Teraz zabieram sie
za elementy ktorych nie da sie ( jeszcze porownac )
No i nasowa sie

NasUUUUUUUwa sie.

Post by sznury
pytanie jak zdefiniowac teraz relacje, tzn jak pokazac ze wprowadzenie
relacji pomiedzy te elementy nie popsuje np. czesciowego porzadku? (
moze to jest oczywiste ale jeszcze tego nie widze )

No przeciez T.D. juz pokazal Ci, jak zdefiniowac:
podzielic zbior na elementy *mniejsze* od wybranego
oraz na *wieksze i nieporownywalne*.


Maciek

[Maciek]

Post by sznury
Prosze skomentowac moje rozumowanie
X - zbior skonczony czesciowo uporzadkowany
Chce pokazac ze mozna go uporzadkowac liniowo (kazde 2 elementy beda w
relcaji ze soba)
Dowod przez indukcje
n=1
zbior jednoelementowy jest uporzadkowany czesciowo i liniowo
(zwrotnosc)
Krok ind.
Niech n dowolne. Zakladam, ze kazdy czesciowy porzadek na dowolnym
zbiorze n-elementowym mozna rozszerzyc do porzadku liniowego.
Chce pokazac ze teza zachodzi dla dowolnego zbioru (n+1)-elementowego

DOWOLNEGO zbioru (n+1)-elementowego?
Tzn. ze jesli np. 4-elementowy zbior {a, b, c, d} jest czesciowo
uporzadkowany, i ten porzadek da sie rozszerzyc do liniowego,
to niby z tego ma wyniknac, ze dowolny czesciowy porzadek
w zbiorze {a, g, q, v, z} takze sie da?

Post by sznury
Niech X' zbior n+1-elementowy czesciowo uporzadkowany. Dziele go na 2
czesci, w jednej n-elementow w drugiej 1 element. Z zalozenia umiem
uporzadkowac liniowo pierwsza czesc i teraz dla zostawionego jednego
elementu ustalam ze dla kazdego elementu z pierwszej czesci zbioru jest

^^^^^^^^

Post by sznury
on w relacji z nim co rozszerza czesciowy porzadek zbioru X' do p.
liniowego.

W jaki sposob to ustalasz?

Z tego co napisales NIE wynika, ze ten n-plus-pierwszy element
jest w relacji z ktorymkolwiek z pozostalych n elementow.

Post by sznury
Czy to poprawny dowod??

Kazdy dowod z istoty swojej jest poprawny.
Jesli nie jest poprawny, to nie jest dowodem.
Tak jak Twoj.


Maciek

[Tomasz]

Post by sznury
Prosze skomentowac moje rozumowanie
X - zbior skonczony czesciowo uporzadkowany
Chce pokazac ze mozna go uporzadkowac liniowo (kazde 2 elementy beda w
relcaji ze soba)
Dowod przez indukcje
n=1
    zbior jednoelementowy jest uporzadkowany czesciowo i liniowo
(zwrotnosc)
Krok ind.
    Niech n dowolne. Zakladam, ze kazdy czesciowy porzadek na dowolnym
zbiorze n-elementowym mozna rozszerzyc do porzadku liniowego.
Chce pokazac ze teza zachodzi dla dowolnego zbioru (n+1)-elementowego
Niech X' zbior n+1-elementowy czesciowo uporzadkowany. Dziele go na 2
czesci, w jednej n-elementow w drugiej 1 element.  Z zalozenia umiem
uporzadkowac liniowo pierwsza czesc i teraz dla zostawionego jednego
elementu ustalam ze dla kazdego elementu z pierwszej czesci zbioru jest
on w relacji z nim co rozszerza czesciowy porzadek zbioru X' do p.
liniowego.

Już dostałeś odpowiedzi, że to nie jest kompletny dowód oraz wskazówki jak go
uzupełnić. Wiadomo, że musisz określć jak wybierasz 1 element i jak definiujesz
relacje z nim w porządku liniowym. Moja wskazówka jest taka:
wybierz 1 element z X' tak, aby w porządku linowym na X' mógł być elementem
ekstremalnym (np. minimalnym).

Tomek

[sznury]

Post by Tomasz
Już dostałeś odpowiedzi, że to nie jest kompletny dowód oraz wskazówki jak go
uzupełnić. Wiadomo, że musisz określć jak wybierasz 1 element i jak definiujesz
wybierz 1 element z X' tak, aby w porządku linowym na X' mógł być elementem
ekstremalnym (np. minimalnym).

Czyli tak:
Dziele X' na A i B. A to elementy mniejsze a B to elementy wieksze lub
nieporownywalne. W A mam liniowy porzadek z zalozenia indukcyjnego.
Zabieram sie teraz za elementy nieporownywalne. JEst ich skonczona ilosc
wiec biore kazdy i porownuje go z elementem wyroznionym i jesli jest
mniejszy to pakuje do A a jesli wiekszy to do B ustalajac przy tym
relacje miedzy elementami. Po skonczonej ilosci porownan mam liniowy
porzadek.
Czy tak ?

[Tomasz]

Post by sznury

Post by Tomasz
wybierz 1 element z X' tak, aby w porządku linowym na X' mógł być elementem
ekstremalnym (np. minimalnym).

Dziele X' na A i B. A to elementy mniejsze a B to elementy wieksze lub
nieporownywalne. W A mam liniowy porzadek z zalozenia indukcyjnego.
Zabieram sie teraz za elementy nieporownywalne. JEst ich skonczona ilosc
wiec biore kazdy i porownuje go z elementem wyroznionym  i jesli jest
mniejszy to pakuje do A a jesli wiekszy to do B ustalajac przy tym
relacje miedzy elementami. Po skonczonej ilosci porownan mam liniowy
porzadek.
Czy tak ?

Nie czytasz uważnie. Wybierasz z (n+1)-elementowego zbioru X' _jeden_ element,
dla którego nie istnieje element większy w sensie porządku częściowego na X'.
Pozostałe elementy z X' porządkujesz liniowo zgodnie z porządkiem częściowym
(założenie indukcyjne). Teraz ten wybrany element dodajesz jako element
najmniejszy w porządku liniowym na X'. Koniec dowodu.


Tomek

PS. Z faktem, że porządek częściowy można rozszerzyć do liniowego związany jest
algorytmiczny problem pt. 'sortowanie topologiczne' w grafach. Dowód
poprawności odpowiedniego algorytmu jest dowodem wspomnianego faktu.

[Tomasz]

Post by Tomasz
Wybierasz z (n+1)-elementowego zbioru X' _jeden_ element,
dla którego nie istnieje element większy w sensie porządku częściowego na X'.
Pozostałe elementy z X' porządkujesz liniowo zgodnie z porządkiem częściowym
(założenie indukcyjne). Teraz ten wybrany element dodajesz jako element
najmniejszy w porządku liniowym na X'.

Oczywiście NAJWIĘKSZY a nie najmniejszy (albo można było wybrać taki, który nie
ma od siebie mniejszego i dodać go jako el. najmniejszy).

Tomek

[A.L.]

Post by sznury
Prosze skomentowac moje rozumowanie
X - zbior skonczony czesciowo uporzadkowany
Chce pokazac ze mozna go uporzadkowac liniowo (kazde 2 elementy beda w
relcaji ze soba)
Dowod przez indukcje
n=1
zbior jednoelementowy jest uporzadkowany czesciowo i liniowo
(zwrotnosc)
Krok ind.
Niech n dowolne. Zakladam, ze kazdy czesciowy porzadek na dowolnym
zbiorze n-elementowym mozna rozszerzyc do porzadku liniowego.
Chce pokazac ze teza zachodzi dla dowolnego zbioru (n+1)-elementowego

Cos nie kapuje. Wezny porzadek Pareto:
(a1, b1) jest-lepszy-od (a2, b2) wtedy i tylko wtedy gdy
a1 > a2 i b1 > b2.

Wez przykald (3, 3), (1, 3), (2, 2), (3, 1) i pokaz jak mozna te
elementy uporzadkowac liniowo metoda ktora opisujesz. To tak dla
rozjasnienia umyslu...

Gdyby to sie latwo dalo i mialo sens, to moglbys dokonac przewrotu w
optymalizacji wielokryterialnej :)

A.L.

[sznury]

Post by A.L.
(a1, b1) jest-lepszy-od (a2, b2) wtedy i tylko wtedy gdy
a1 > a2 i b1 > b2.
Wez przykald (3, 3), (1, 3), (2, 2), (3, 1) i pokaz jak mozna te
elementy uporzadkowac liniowo metoda ktora opisujesz. To tak dla
rozjasnienia umyslu...

Co do tego przykladu to nie mozna wprowadzic porzadku liniowego poniewaz
relacja "jest-lepszy-od" tak zdefiniowana nie jest spojna. (3,1) i (1,3)
nie sa w relacji ze soba. Jest to porzadek czesciowy ale nie liniowy.
Ja nie widze jak mozna by to przerobic do relacji liniowo porzadkujacej
( czyzby dobry kontrprzyklad ?? ) zaskocze jutro prowadzacego....
Dzieki za "rozjasnienie umyslu" Ciekawe co na to inni grupowicze ktorzy
pomagali mi przeforsowac teze..... czekam na komentarze....

[Andrzej Gorczyński]

Post by A.L.
(a1, b1) jest-lepszy-od (a2, b2) wtedy i tylko wtedy gdy
a1 > a2 i b1 > b2.

Tak z ciekawości, czy porządek Pareto nie obejmuje też sytuacji gdy a1>a2 i
b1>=b2 lub też a1>=a2 i b1>b2 ? Z tego co pamiętam to taką sytuację
dopuszczał warunek efektywności Pareto.

Pozdrawiam
Andrzej

[A.L.]

On Wed, 9 Mar 2005 22:40:46 +0000 (UTC), Andrzej Gorczyński

Post by Andrzej Gorczyński

Post by A.L.
(a1, b1) jest-lepszy-od (a2, b2) wtedy i tylko wtedy gdy
a1 > a2 i b1 > b2.

Tak z ciekawości, czy porządek Pareto nie obejmuje też sytuacji gdy a1>a2 i
b1>=b2 lub też a1>=a2 i b1>b2 ? Z tego co pamiętam to taką sytuację
dopuszczał warunek efektywności Pareto.

Owszem, definiuje sie porzadki slabe, silne, slabo-silne itede. Do
praktycznych zastosowan z reguly przyjmuje sie nierownosc slaba.

A.L.

[Marcin Kysiak]

Post by A.L.
Wez przykald (3, 3), (1, 3), (2, 2), (3, 1) i pokaz jak mozna te
elementy uporzadkowac liniowo metoda ktora opisujesz. To tak dla
rozjasnienia umyslu...
Gdyby to sie latwo dalo i mialo sens, to moglbys dokonac przewrotu w
optymalizacji wielokryterialnej :)

To się da zrobić, choć być może nie opisywaną metodą. Na przykład:

(1,3)<(2,2)<(3,1)<(3,3).

Oczywiście rozszerzenie nie ma własności produktowych, jakie ma
wyjściowy porządek, stąd widoki na przewrót marne ;-)

Fakt dowodzony jest prawdziwy, choć pierwotny dowód jest niepoprawny.
Zresztą każdy porządek częściowy można rozszerzyć do liniowego, ale
właśnie sprawdzenie dla skończonych jest istotnym krokiem w dowodzie.

Pozdrawiam
Marcin

[£ukasz Kalbarczyk]

Post by sznury
Prosze skomentowac moje rozumowanie
X - zbior skonczony czesciowo uporzadkowany
Chce pokazac ze mozna go uporzadkowac liniowo (kazde 2 elementy beda w
relcaji ze soba)
Czy to poprawny dowod??

To chyba nie jest takie trywialne...
Kojarzy mi się to zagadnienie np. z tw. Zermelo.

[Marcin Kysiak]

Post by £ukasz Kalbarczyk
To chyba nie jest takie trywialne...
Kojarzy mi się to zagadnienie np. z tw. Zermelo.

Dla dowolnych porządków - owszem. Dla skończonych liczy się na palcach
przez indukcję. Nie pamiętałem argumentu, ale wątek dobrnął już w
zasadzie do poprawnego?

Pzdr,
M.

[Tomasz Dryjanski]

Jeszcze jedno podejscie:
Ze zbioru X' wybieramy element minimalny, lub dowolny jesli minimalny
nie istnieje. Pozostale elementy porzadkujemy z zalozenia indukcyjnego,
po czym dodajemy wybrany element tak, zeby byl mniejszy od wszystkich
pozostalych.

Powinno wystarczyc.
T. D.

[Marcin Kysiak]

Post by Tomasz Dryjanski
Ze zbioru X' wybieramy element minimalny, lub dowolny jesli minimalny
nie istnieje.

Istnieje, bo zbiór jest skończony.

Pozdrawiam
Marcin

[Tomasz Dryjanski]

Post by Marcin Kysiak

Post by Tomasz Dryjanski
Ze zbioru X' wybieramy element minimalny, lub dowolny jesli minimalny
nie istnieje.

Istnieje, bo zbiór jest skończony.

Miałem na myśli element izolowany, ale faktycznie on z definicji jest
minimalny.

T. D.

[Marcin Kysiak]

To ja teraz pokażę dowód dla nieskończonego. Oprę się oczywiście o
przypadek skończony, ale chcę pokazać dowód nieco rzadziej spotykany.

Skorzystamy z twierdzenia o zwartości dla logiki I rzędu:

Twierdzenie (o zwartości): Jeżeli każdy skończony podzbiór T' zbioru
zdań T ma model, to T ma model.

Weźmy częściowy porządek ( X, < ). Weźmy język tego modelum tzn. dla
każdego x\in X mamy w języku symbol stałej c_x, ponadto symbol relacji
dwuargumentowej '<' i równość (plus standardowe symbole logiczne).

Do zbioru T zaliczamy następujące zdania:

a) aksjomaty porządku liniowego,
b) c_x < c_y, o ile (X,<) |= x < y (dla x,y\in X).

Na mocy udowodnionego faktu o porządkach skończonych widzimy, że każdy
skończony T'\subseteq T ma model. Istotnie, bierzemy (skończony!) zbiór
X'={x\in X : c_x występuje w T'} i porządek (X', <) rozszerzamy do
liniowego. To rozszerzenie jest modelem T'.

Zatem na mocy twierdzenia o zwartości, zbiór T ma model, który jest
porządkiem liniowym. Nietrudno pokazać, że przekształcenie
przyporządkowujące x\in X interpretację c_x w tym modelu jest
zanurzeniem. QED.

Pozdrawiam
Marcin