Introduction to the Combinatorial Theory of Partially Ordered Sets (in Greek) [version 15 Jan 2007 ed.] [PDF]

Zitiervorschau

Eisagwg 

sth Sunduastik 

Jewra

twn Merik¸ Diatetagmènwn Sunìlwn

Qrhstos A. Ajanasiadhs Tmhma Majhmatikwn Panepisthmio Ajhnwn Anoixh 2006

2

Perieqìmena

1

2

3

4

Arqikè

'Ennoie

5

1.1

Apeikonsei kai sqèsei isodunama . . . . . . . . . . . . . . . . . . . . . . .

5

1.2

Merikè diatˆxei kai isomorfismo . . . . . . . . . . . . . . . . . . . . . . . .

8

1.3

Prˆxei se merikè diatˆxei . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

1.4

Ask sei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

Alusde kai Antialusde

23

2.1

Alusde , antialusde kai diabajmsei . . . . . . . . . . . . . . . . . . . . .

23

2.2

Ide¸dh kai fltra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.3

To Je¸rhma tou Dilworth . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.4

Summetrikè alusde kai to Je¸rhma tou Sperner . . . . . . . . . . . . . . .

32

2.5

Ask sei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

Ide¸dh kai Grammikè Epektˆsei

45

3.1

Morfismo merik¸n diatˆxewn . . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.2

H merik  diˆtaxh twn idewd¸n . . . . . . . . . . . . . . . . . . . . . . . . . .

46

3.3

Grammikè epektˆsei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

3.4

Ask sei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

SÔndesmoi

55

4.1

Orismo

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

4.2

Epimeristiko sÔndesmoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3

4 4.3

SÔndesmoi kai kleistìthta . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

4.4

Arjrwto, hmiarjrwto kai gewmetriko sÔndesmoi . . . . . . . . . . . . . . .

65

4.5

Gewmetriko sÔndesmoi kai mhtroeid  . . . . . . . . . . . . . . . . . . . . . . .

68

4.6

Stoiqei¸dei idiìthte mhtroeid¸n . . . . . . . . . . . . . . . . . . . . . . . .

71

4.7

Hmiepimeristiko sÔndesmoi kai kurtè gewmetre . . . . . . . . . . . . . . . .

77

4.8

Ask sei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

Kefˆlaio

Arqikè

1

'Ennoie

Oi merikè diatˆxei enai dimele sqèsei pou apolambˆnoun trei basikè idiìthte , thn anaklastik  idiìthta, thn antisummetra kai th metabatikìthta. Oi dimele autè sqèsei sunant¸ntai kai pazoun shmantikì rìlo se èna eurÔtato fˆsma twn sÔgqronwn majhmatik¸n. Sto kefˆlaio autì eisˆgoume thn ènnoia th merik  diˆtaxh se èna sÔnolo kaj¸ kai aut n tou isomorfismoÔ dÔo merik¸ diatetagmènwn sunìlwn. Akìmh, dnoume paradegmata kai perigrˆfoume basikoÔ trìpou me tou opoou mporoÔme na kataskeuˆsoume nèe (pio sÔnjete ) merikè diatˆxei apì ma   perissìtere dosmène diatˆxei . Ja qrhsimopoi soume tou ex  sumbolismoÔ :

∅: to kenì sÔnolo N = {1, 2, . . .}: to sÔnolo twn fusik¸n arijm¸n Z: to sÔnolo twn akerawn Z≥0 = {0, 1, . . .}: to sÔnolo twn mh arnhtik¸n akerawn Q: to sÔnolo twn rht¸n R: to sÔnolo twn pragmatik¸n [n]: to sÔnolo {1, 2, . . . , n} #S : o plhjˆrijmo tou sunìlou S . 1.1

Apeikonsei kai sqèsei isodunama

JewroÔme gnwstè basikè ènnoie th jewra sunìlwn, ìpw aut  tou egkleismoÔ sunìlwn A ⊆ B , tou kartesianoÔ ginomènou (peperasmènou pl jou ) sunìlwn, th apeikìnish 5

6 sunìlwn kai th sÔnjesh apeikonsewn kai grˆfoume A ⊂ B , ìtan A ⊆ B kai apokleetai h isìthta. Gia apeikìnish sunìlwn f : A → B kai y ∈ B sumbolzoume me

◦ f (A) = {f (x) : x ∈ A} kai me ◦ f −1 (y) = {x ∈ A : f (x) = y}, antstoiqa, thn eikìna tou A kai thn antstrofh eikìna tou y ∈ B (mèsw th f ) kai upenjumzoume ìti f (A) ⊆ B kai f −1 (y) ⊆ A . H apeikìnish f : A → B lègetai

◦ ènrriyh (  1 1   enrriptik  apeikìnish) an #f −1 (y) ≤ 1 gia kˆje y ∈ B , ◦ eprriyh (  ep   epirriptik  apeikìnish) an #f −1 (y) ≥ 1 gia kˆje y ∈ B , ◦ amfrriyh (  1 1 kai ep   amfirriptik  apeikìnish) an #f −1 (y) = 1 gia kˆje y ∈ B . Paradeigma. An A = {a, b, c, d}, ìpou a, b, c, d enai diaforetikˆ anˆ dÔo stoiqea tou A, kai B = {1, 2, 3}, tìte h apeikìnish f : A → B me f (a) = 2, f (b) = 3 kai f (c) = f (d) = 1 enai eprriyh allˆ den enai ènrriyh, diìti to f −1 (1) = {c, d} èqei dÔo stoiqea. ✷

H epìmenh basik  prìtash jewretai gnwst . Prìtash 1.1.1

'Estw f : A → B apeikìnish peperasmènwn sunìlwn.

(i) An h f enai ènrriyh tìte #A ≤ #B . (ii) An h f enai eprriyh tìte #A ≥ #B . (iii) An h f enai amfrriyh tìte #A = #B .

✷

Dimel  sqèsh se èna sÔnolo S lègetai èna uposÔnolo R tou kartesianoÔ ginomènou S × S . Gia a, b ∈ S grˆfoume a R b an (a, b) ∈ R kai lème ìti to a sqetzetai me to b w pro th dimel  sqèsh R. H ènnoia th dimeloÔ sqèsh sto S genikeÔei thn ènnoia th apeikìnish f : S → S , me thn opoa kˆje stoiqeo a tou S sqetzetai me akrib¸ èna stoiqeo tou S , to b = f (a). Mia shmantik  kathgora dimel¸n sqèsewn enai oi sqèsei isodunama . H ènnoia th sqèsh isodunama sto S enai stenˆ sundedemènh me aut n th diamèrish tou sunìlou S. 'Estw sÔnolo S . Onomˆzoume diamèrish (  merismì) tou S èna sÔnolo π = {B1 , B2 , . . . , Bk } mh ken¸n uposunìlwn tou S pou anˆ dÔo enai xèna metaxÔ tou kai h ènws  tou enai sh me S . Ta uposÔnola Bi lègontai mèrh th diamèrish π . Orismì 1.1.1

7 To π = {{1, 5, 9}, {2, 8}, {7}, {3, 4, 6}} enai diamèrish tou [9]. Grˆfoume π = 159/28/7/346, ìpou h seirˆ me thn opoa anagrˆfontai ta mèrh th π ìpw kai h seirˆ me thn opoa anagrˆfontai ta stoiqea se kˆje mèro th π , den èqei shmasa. ✷ Paradeigma.

'Estw π = {B1 , B2 , . . . , Bk } diamèrish tou S . JewroÔme th dimel  sqèsh ≡π sto S pou orzetai w ex  : gia x, y ∈ S èqoume x ≡π y an ta x kai y an koun sto dio mèro Bi th π . H sqèsh aut  èqei profan¸ ti epìmene trei basikè idiìthte :

(i) a ≡π a (anaklastik ), (ii) an a ≡π b, tìte b ≡π a (summetrik ), (iii) an a ≡π b kai b ≡π c, tìte a ≡π c (metabatik ) gia ìla ta a, b, c ∈ S . An S = [9] kai π = {{1, 5, 9}, {2, 8}, {7}, {3, 4, 6}}, tìte 1 ≡π 5, 5 ≡π 9, 1 ≡π 9, 2 ≡π 8, 7 ≡π 7 klp. ✷

Paradeigma.

Mia dimel  sqèsh, èstw ≡, sto sÔnolo S lègetai sqèsh isodunama (equivalence relation) an gia ìla ta a, b, c ∈ S isqÔoun ta ex  :

Orismì 1.1.2

(i) a ≡ a, (ii) an a ≡ b, tìte b ≡ a, (iii) an a ≡ b kai b ≡ c, tìte a ≡ c. Lème ìti to a enai isodÔnamo me to b (w pro th sqèsh isodunama ≡) an a ≡ b. 'Wste gia kˆje diamèrish π tou S h ≡π enai sqèsh isodunama sto S . Antstrofa, kˆje sqèsh isodunama ≡ sto S orzei mia diamèrish π tou S gia thn opoa oi ≡π kai ≡ tautzontai. Pio sugkekrimèna, klˆsh isodunama tou a ∈ S lègetai to uposÔnolo

Ca = {x ∈ S : x ≡ a} tou S pou apoteletai apì ìla ta isodÔnama me to a stoiqea tou S . 'Eqoume a ≡ a kai sunep¸ a ∈ Ca gia kˆje a ∈ S , pou shmanei ìti oi klˆsei isodunama enai mh kenè kai h ènws  tou enai to sÔnolo S . Epsh oi klˆsei Ca kai Cb enai xène metaxÔ tou ektì an Ca = Cb . Prˆgmati, an Ca ∩ Cb 6= ∅ tìte upˆrqei c ∈ Ca ∩ Cb , opìte c ≡ a kai c ≡ b. Apì ti sqèsei autè , exaita th summetrik  kai th metabatik  idiìthta th sqèsh ≡ èqoume a ≡ b. 'Estw t¸ra tuqao x ∈ Ca . Apì ti x ≡ a kai a ≡ b parnoume x ≡ b, dhlad 

8 ìti x ∈ Cb . Dexame ìti Ca ⊆ Cb kai anˆloga apodeiknÔoume ìti Cb ⊆ Ca , ˆra Ca = Cb . Sumperanoume ìti ta diakekrimèna apì ta sÔnola Ca gia a ∈ S apoteloÔn diamèrish π tou S , ta mèrh th opoa enai oi klˆsei isodunama th ≡, opìte h sqèsh ≡π tautzetai me thn ≡. Paradeigma. An S = {a, b, c} kai ≡ enai h dimel  sqèsh {(a, a), (b, b), (c, c), (a, b), (b, a)} sto S , tìte h ≡ enai sqèsh isodunama me dÔo klˆsei isodunama Ca = Cb = {a, b} kai Cc = {c}. ✷

1.2

Merikè diatˆxei kai isomorfismo

Me ton akìloujo orismì eisˆgoume thn ènnoia th merik  diˆtaxh . Mia dimel  sqèsh, èstw ≤, sto sÔnolo P lègetai merik  diˆtaxh (partial order) an gia ìla ta a, b, c ∈ P isqÔoun ta ex  :

Orismì 1.2.1

(i) a ≤ a, (ii) an a ≤ b kai b ≤ a, tìte a = b, (iii) an a ≤ b kai b ≤ c, tìte a ≤ c. H idiìthta (ii) lègetai antisummetra. To zeÔgo (P, ≤) lègetai merik¸ diatetagmèno sÔnolo kai sumbolzetai aploÔstera me P ìtan h merik  diˆtaxh ≤ enai eunìhth. 'Otan anaferìmaste se èna merik¸ diatetagmèno sÔnolo P ja sumbolzoume th merik  diˆtaxh tou P me ≤   me ≤P . Gia lìgou suntoma , ja qrhsimopoioÔme suqnˆ ton ìro {merik  diˆtaxh} ant gia {merik¸ diatetagmèno sÔnolo}. Ta stoiqea a, b tou P lègontai sugkrsima an a ≤ b   b ≤ a. Grˆfoume a < b (kai b > a) an a ≤ b kai a 6= b. Lème ìti to b kalÔptei to a (  ìti to zeÔgo (a, b)   h sqèsh a < b enai sqèsh kˆluyh ), an a < b kai den upˆrqei x ∈ P me a < x < b. An to P enai peperasmèno, tìte to (P, ≤) apeikonzetai me to diˆgramma Hasse, to opoo perièqei ta stoiqea tou P w korufè kai mia akm  pou na sundèei ta a kai b gia kˆje sqèsh kˆluyh (a, b) sto P , me to b na emfanzetai yhlìtera apì to a. Sto Sq ma 1.1 apeikonzontai ta diagrˆmmata Hasse dÔo merik¸n diatˆxewn sta sÔnola P = {a, b, c, d} kai Q = {a, b, c, d, e}. Sthn pr¸th èqoume ti sqèsei kˆluyh a < b, c < b kai c < d kai sth deÔterh ti a < b, b < d, d < e, a < c kai c < e. Sthn perptwsh tou Q parathroÔme ìti oi a < d, a < e kai b < e den enai sqèsei kˆluyh kai sunep¸ den upˆrqoun oi antstoiqe akmè sto diˆgramma. Oi akmè autè ja apoteloÔsan Paradeigma.

9 e b

d d b

a

c

c a P

Q

Sq ma 1.1: DÔo merik¸ diatetagmèna sÔnola. katˆ kˆpoio trìpo pleonasmì afoÔ, gia parˆdeigma, apì ti akmè metaxÔ twn a, b kai b, d prokÔptei ìti a < b kai b < d kai sunep¸ ìti a < d apì th metabatik  idiìthta. Ta {a, c}, {a, d} kai {b, d} enai zeÔgh mh sugkrsimwn stoiqewn sto P , ìpw kai ta {b, c} kai {c, d} sto Q. ✷ A exetˆsoume t¸ra kai ˆlla paradegmata merik¸n diatˆxewn. H fusik  diˆtaxh ≤Z twn akerawn enai merik  diˆtaxh sto Z, kaj¸ kai se opoiod pote uposÔnolo tou Z (oi idiìthte tou OrismoÔ 1.2.1 sthn perptwsh aut  jewroÔntai gnwstè ). Sth diˆtaxh aut  (thn opoa sumbolzoume aploÔstera me ≤ ìtan pisteÔoume ìti den upˆrqei knduno sÔgqhsh ) opoiad pote dÔo stoiqea tou Z enai sugkrsima. Mia merik  diˆtaxh me aut  thn idiìthta lègetai olik  diatˆxh   grammik  diatˆxh   alusda. Gia parˆdeigma, upˆrqoun dÔo alusde sto sÔnolo {1, 2}, h 1 < 2 kai h 2 < 1. Genikìtera (Prìtash 2.1.1), kˆje olik  diˆtaxh se èna sÔnolo P me n stoiqea enai th morf  σ1 < σ2 < · · · < σn (dhlad  isqÔei x ≤ y sto P an kai mìno an x = σi kai y = σj me i ≤Z j ) gia kˆpoia apì ti n! metajèsei (σ1 , σ2 , . . . , σn ) tou P . Diagrˆmmata Hasse alusdwn me tra kai tèssera stoiqea apeikonzontai sto tèlo th pr¸th kai trth seirˆ tou Sq mato 1.4. ✷ Parˆdeigma 1.2.1

'Estw sÔnolo P kai h dimel  sqèsh ≤ h opoa orzetai jètonta a ≤ b, gia a, b ∈ P , an a = b. H sqèsh aut  enai profan¸ merik  diˆtaxh sto P , lègetai antialusda kai apotele th monadik  merik  diˆtaxh sto P sthn opoa den upˆrqoun diakekrimèna sugkrsima (metaxÔ tou ) stoiqea tou P . Diagrˆmmata Hasse antialusdwn me tra kai tèssera stoiqea apeikonzontai sthn arq  th pr¸th kai deÔterh seirˆ tou Sq mato 1.4. ✷ Parˆdeigma 1.2.2

'Estw Bn to dunamosÔnolo (sÔnolo ìlwn twn uposunìlwn) tou [n] me th dimel  sqèsh ≤ tou egkleismoÔ, dhlad  me S ≤ T an S ⊆ T gia S, T ⊆ [n]. Oi trei idiìthte Parˆdeigma 1.2.3

10 tou OrismoÔ 1.2.1 enai fanerè ìpou h antisummetra, p.q., isoduname me to gegonì ìti an S ⊆ T kai T ⊆ S gia S, T ⊆ [n], tìte S = T . Sunep¸ h ≤ enai merik  diˆtaxh sto Bn . Me aut  th merik  diˆtaxh to sÔnolo Bn lègetai ˆlgebra Boole tˆxh n. To diˆgramma Hasse tou Bn apeikonzetai sto Sq ma 1.2 (a) gia n = 3. Isqurizìmaste t¸ra ìti sthn ˆlgebra Boole Bn , to T kalÔptei to S an kai mìno an S ⊆ T kai #T = #S + 1. Upojètoume pr¸ta ìti to T kalÔptei to S . Tìte S < T , opìte S ⊆ T kai #T ≥ #S + 1. An eqame #T > #S + 1 tìte ja up rqan toulˆqiston dÔo diaforetikˆ stoiqea a, b tou T − S kai ja eqame S ⊂ S ∪ {a} ⊂ T . Sunep¸ ja sque S < S ∪ {a} < T sto Bn kai h S < T den  tan sqèsh kˆluyh . H antfash aut  ma odhge sto sumpèrasma ìti #T = #S + 1. Antstrofa an S ⊆ T kai #T = #S + 1 tìte enai fanerì ìti S ⊂ T kai ìti den upˆrqei sÔnolo R me S ⊂ R ⊂ T , dhlad  ìti to T kalÔptei to S . ✷

{1,2,3}

12

{1,2}

{1,3}

{2,3}

{1}

{2}

{3}

{}

(a)

6

4

3

2 1

(b)

Sq ma 1.2: Oi merikè diatˆxei B3 kai D12 . H sqèsh tou egkleismoÔ mpore na oriste pˆnw se tuqaa sullog  A uposunìlwn enì dosmènou sunìlou, jètonta S ≤ T gia S, T ∈ A an S ⊆ T . H sqèsh aut  apotele merik  diˆtaxh sto A. Endiafèronta paradegmata merik¸n diatˆxewn autoÔ tou edou emfanzontai se afjona sthn ˆlgebra kai th gewmetra kai perilambˆnoun th merik  diˆtaxh (tou egkleismoÔ) sto sÔnolo twn grammik¸n upìqwrwn enì dianusmatikoÔ q¸rou, sto sÔnolo twn upoomˆdwn mia omˆda (me idiaterh shmasa gia th jewra Galois), sto sÔnolo twn pr¸twn idewd¸n enì antimetajetikoÔ daktulou (me idiaterh shmasa sth metajetik  ˆlgebra) kai sto sÔnolo twn pleur¸n enì kurtoÔ poluèdrou (  poluedrikoÔ sumplègmato ). Shmantikì parˆdeigma enai epsh h {merik  diˆtaxh twn idewd¸n}, pou ja Parat rhsh 1.2.1

11 melet soume sti Paragrˆfou 3.2 kai 4.2, kaj¸ kai aut  twn {kleist¸n sunìlwn} mia ✷ prˆxh kleistìthta , pou ja eisˆgoume sthn Parˆgrafo 4.3. 'Estw h dimel  sqèsh | sto sÔnolo N twn jetik¸n akerawn me a | b an o b diairetai me to a, dhlad  an upˆrqei s ∈ N me b = as. H sqèsh aut  enai merik  diˆtaxh sto N. Prˆgmati, h anaklastik  idiìthta enai faner . Gia thn antisummetra, parathroÔme ìti an a | b kai b | a, tìte a ≤Z b kai b ≤Z a kai sunep¸ a = b. Gia th metabatikìthta, parathroÔme ìti an a | b kai b | c, tìte upˆrqoun s, t ∈ N me b = as kai c = bt, opìte c = ast = aq me q = st ∈ N kai sunep¸ a | c. Se aut  th merik  diˆtaxh oi akèraioi pou kalÔptoun to 1 (to elˆqisto stoiqeo th diˆtaxh ) enai auto pou den èqoun diairèth ˆllo apì to 1 kai ton eautì tou , dhlad  oi pr¸toi arijmo. Genikìtera to b kalÔptei to a sth merik  diˆtaxh | an kai mìno an b = ap gia kˆpoio pr¸to arijmì p. ✷ Parˆdeigma 1.2.4

'Estw n ∈ N kai èstw Dn to sÔnolo twn jetik¸n diairet¸n tou n me th sqèsh th diairetìthta tou Paradegmato 1.2.4, dhlad  me a | b sto Dn an o b diairetai me to a. H sqèsh aut  sto Dn enai merik  diˆtaxh afoÔ, ìpw èqoume  dh dexei, oi idiìthte tou OrismoÔ 1.2.1 isqÔoun sto megalÔtero sÔnolo N. To diˆgramma Hasse tou Dn apeikonzetai sto Sq ma 1.2 (b) gia n = 12. ✷ Parˆdeigma 1.2.5

Gia n ∈ N èstw Πn to sÔnolo twn diamersewn tou sunìlou [n]. Gia π, σ ∈ Πn jètoume π ≤ σ an kˆje mèro th diamèrish π perièqetai se kˆpoio mèro th diamèrish σ . Sthn perptwsh aut , lème ìti h π enai eklèptunsh th σ . An p.q. n = 9, π = 159/28/7/346 kai σ = 1579/23468, tìte π ≤ σ . H sqèsh ≤ kajistˆ to Πn merik¸ diatetagmèno sÔnolo, to opoo anafèretai w to sÔnolo twn diamersewn tou [n] me merik  diˆtaxh thn eklèptunsh. Gia na epalhjeÔsoume thn antisummetra (oi ˆlle dÔo idiìthte enai fanerè ) parathroÔme ìti an π ≤ σ , tìte h σ èqei to polÔ tìsa mèrh ìsa kai h π . Epomènw an π ≤ σ kai σ ≤ π tìte h σ èqei akrib¸ tìsa mèrh ìsa kai h π en¸ kˆje mèro th π perièqetai se kˆpoio mèro th σ , opìte anagkastikˆ π = σ . ParathroÔme epsh ìti isqÔei 0ˆ ≤ π ≤ 1ˆ gia kˆje π ∈ Πn , ìpou 0ˆ enai h diamèrish tou [n] ìla ta mèrh th opoa èqoun èna stoiqeo kai ˆ1 enai h diamèrish tou [n] me èna mìno mèro . Epiplèon h σ kalÔptei thn π sto Πn an kai mìno an h σ prokÔptei apì thn π en¸nonta dÔo diaforetikˆ mèrh th π se èna kai af nonta ta upìloipa mèrh ametˆblhta. Gia n = 9, p.q. h π = 159/28/7/346 kalÔptetai, metaxÔ ˆllwn, apì ti diamersei 1579/28/346 kai 159/278/346. To diˆgramma Hasse tou Πn apeikonzetai sto Sq ma 1.3 gia n = 3. ✷ Parˆdeigma 1.2.6

Prwtarqik  shmasa enai h ènnoia tou isomorfismoÔ merik¸ diatetagmènwn sunìlwn.

12 123

12/3

13/2

23/1

1/2/3

Sq ma 1.3: H merik  diˆtaxh Π3 . DÔo merik¸ diatetagmèna sÔnola (P, ≤P ) kai (Q, ≤Q ) lègontai isìmorfa an upˆrqei amfrriyh f : P → Q ¸ste gia x, y ∈ P na isqÔei x ≤P y an kai mìno an f (x) ≤Q f (y). Mia tètoia amfrriyh f lègetai isomorfismì merik¸ diatetagmènwn sunìlwn. Orismì 1.2.2

(i) 'Estw P = {a, b}, Q = {1, 2} kai f : P → Q, me f (a) = 1, f (b) = 2. An ta P, Q enai merik¸ diatetagmèna kai isqÔei 1 < 2 sto Q, tìte h f enai isomorfismì an kai mìno an isqÔei a < b sto P . Ta P kai Q den enai isìmorfa an ta a, b den enai sugkrsima sto P . Parˆdeigma 1.2.7

(ii) H apeikìnish f : B2 → D6 me f (∅) = 1, f ({1}) = 2, f ({2}) = 3 kai f ({1, 2}) = 6 enai isomorfismì merik¸ diatetagmènwn sunìlwn, ìpw enai epsh kai h g : B2 → D6 me g(∅) = 1, g({1}) = 3, g({2}) = 2 kai g({1, 2}) = 6. (iii) Opoiesd pote dÔo alusde P kai Q me n stoiqea enai isìmorfe . Prˆgmati, èqoume σ1 < σ2 < · · · < σn sto P kai τ1 < τ2 < · · · < τn sto Q gia kˆpoie metajèsei (σ1 , σ2 , . . . , σn ) kai (τ1 , τ2 , . . . , τn ) twn sunlown P kai Q (Prìtash 2.1.1) kai h apeikìnish f : P → Q me f (σi ) = τi gia 1 ≤ i ≤ n enai o zhtoÔmeno isomorfismì . (iv) 'Estw 2P to dunamosÔnolo enì sunìlou P me n stoiqea. Efodiasmèno me th merik  diˆtaxh tou egkleismoÔ, to 2P enai isìmorfo me thn ˆlgebra Boole Bn (giat?). ✷ H tautotik  apeikìnish iP : P → P , h antstrofh apeikìnish f −1 : Q → P enì isomorfismoÔ f : P → Q kai h sÔnjesh g ◦ f : P → R dÔo isomorfism¸n f : P → Q kai g : Q → R enai ìle isomorfismo merik¸n diatˆxewn. ProkÔptei ìti h sqèsh isomorfismoÔ enai sqèsh isodunama sto sÔnolo twn merik¸n diatˆxewn. H klˆsh isodunama tou P lègetai tÔpo isomorfismoÔ tou P .

13

Sq ma 1.4: Oi merikè diatˆxei se 3 kai 4 stoiqea. Upˆrqei èna tÔpo isomorfismoÔ merik¸n diatˆxewn me èna stoiqeo kai dÔo tÔpoi gia merikè diatˆxei me dÔo stoiqea. Sto Sq ma 1.4 apeikonzontai ta diagrˆmmata Hasse twn pènte anisìmorfwn merik¸n diatˆxewn me 3 stoiqea kai twn dekaèxi me 4 stoiqea. ✷ Paradeigma.

Suneqzoume me merikoÔ akìmh basikoÔ orismoÔ . 'Estw (P, ≤) merik¸ diatetagmèno sÔnolo kai a ∈ P . To a lègetai elaqistikì an den upˆrqei x ∈ P me x < a, megistikì an den upˆrqei x ∈ P me x > a, elˆqisto an a ≤ x gia kˆje x ∈ P kai mègisto an a ≥ x gia kˆje x ∈ P . ParathroÔme ìti to P mpore na èqei to polÔ èna elˆqisto stoiqeo kai to polÔ èna mègisto stoiqeo. Prˆgmati, an ta a, b  tan kai ta dÔo elˆqista (  kai ta dÔo mègista) stoiqea, tìte ja eqame a ≤ b kai b ≤ a, ˆra ja eqame kai a = b lìgw th antisummetra . ParathroÔme akìmh ìti kˆje elˆqisto (  mègisto) stoiqeo (an upˆrqei) enai elaqistikì (megistikì) kai ìti to antstrofo den enai genikˆ alhjè . Gia ti merikè diatˆxei tou Sq mato 1.1, to P èqei dÔo elaqistikˆ stoiqea kai dÔo megistikˆ en¸ to Q èqei elˆqisto kai mègisto stoiqeo. Sth merik  diˆtaxh Bn to kenì sÔnolo ∅ enai to elˆqisto stoiqeo kai to [n] to mègisto stoiqeo, diìti isqÔei ∅ ⊆ S ⊆ [n] gia kˆje S ∈ Bn . Sth merik  diˆtaxh tou Paradegmato 1.2.4 o akèraio 1 enai to elˆqisto stoiqeo en¸ den upˆrqoun megistikˆ (  mègista) stoiqea. H merik  diˆtaxh Dn èqei elˆqisto stoiqeo to 1 kai mègisto stoiqeo to n. ✷ Paradeigma.

14 Gia kˆje peperasmèno merik¸ diatetagmèno sÔnolo (P, ≤) kai kˆje x ∈ P upˆrqei elaqistikì stoiqeo a ∈ P kai megistikì stoiqeo b ∈ P me a ≤ x ≤ b. Eidikìtera, kˆje mh ken  peperasmènh merik  diˆtaxh èqei toulˆqiston èna elaqistikì kai toulˆqiston èna megistikì stoiqeo. L mma 1.2.1

Apìdeixh. ApodeiknÔoume thn Ôparxh elaqistikoÔ stoiqeou. 'Estw ìti den upˆrqei elaqistikì stoiqeo a tou P me a ≤ x. Tìte to x den enai elaqistikì kai sunep¸ upˆrqei x1 ∈ P me x > x1 . To x1 epsh den enai elaqistikì kai sunep¸ upˆrqei x2 ∈ P me x1 > x2 . Epanalambˆnonta to dio epiqerhma brskoume mia ˆpeirh akolouja x = x0 > x1 > x2 > · · · stoiqewn tou P . Efìson to P enai peperasmèno oi ìroi th akolouja aut  den mpore na enai ìloi anˆ dÔo diaforetiko. Me ˆlla lìgia upˆrqoun dekte i < j me xi = xj . Apì th metabatikìthta kai ti sqèsei xi > xi+1 > · · · > xj = xi prokÔptei ìti xi > xi+1 kai xi+1 ≥ xi , sqèsei pou antibanoun sthn antisummetra. To zhtoÔmeno èpetai. Anˆloga apodeiknÔetai kai h Ôparxh megistikoÔ stoiqeou b ≥ x. ✷ 1.3

Prˆxei se merikè diatˆxei

A exetˆsoume kˆpoiou basikoÔ trìpou na kataskeuˆsei kane nèe merikè diatˆxei apì gnwstè . 'Estw merik¸ diatetagmèno sÔnolo P . Gia kˆje uposÔnolo Q tou P o periorismì ≤Q th sqèsh ≤P sto Q × Q enai merik  diˆtaxh sto Q. 'Etsi gia x, y ∈ Q èqoume x ≤Q y an kai mìno an x ≤P y sto P . H ≤Q onomˆzetai epagìmenh merik  diˆtaxh sto Q kai to zeÔgo (Q, ≤Q ) enai to epagìmeno merik¸ diatetagmèno uposÔnolo tou P sto Q. Gia x, y ∈ P me x ≤P y orzoume to uposÔnolo [x, y] = {z ∈ P : x ≤P z ≤P y} tou P . To sÔnolo autì, efodiasmèno me thn epagìmenh merik  diˆtaxh, lègetai kleistì diˆsthma sto P (me ˆkra x kai y ). Omow orzetai to anoiktì diˆsthma (x, y) = {z ∈ P : x

· · · > ajm+1 . Gia parˆdeigma, an m = n = 2 kai A = (1, 0, 2, 0, 1), dhlad  a1 = 1, a2 = 0, a3 = 2, a4 = 0, a5 = 1, tìte upˆrqei h aÔxousa upoakolouja a2 ≤ a4 ≤ a5 th A m kou 3. Parˆdeigma 2.3.1

5 3

4

1

2

Sq ma 2.1: Mia merik  diˆtaxh sto [5]. JewroÔme to zeÔgo (P, ✂), ìpou P = [mn + 1] kai i ✂ j an kai mìno an i ≤ j kai ai ≤ aj . EÔkola blèpei kane ìti h sqèsh ✂ enai merik  diˆtaxh sto sÔnolo P . To diˆgramma Hasse aut  th merik  diˆtaxh dnetai sto Sq ma 2.1 gia thn perptwsh A = (1, 0, 2, 0, 1). Apì to Pìrisma 2.3.1 gnwrzoume ìti to P èqei alusda ai1 ✁ ai2 ✁ · · · ✁ ain+1   antialusda {aj1 , aj2 , . . . , ajm+1 } me j1 < j2 < · · · < jm+1 . Sthn pr¸th perptwsh èqoume i1 < i2 < · · · < in+1 kai ai1 ≤ ai2 ≤ · · · ≤ ain+1 kai sth deÔterh j1 < j2 < · · · < jm+1

31 kai aj1 > aj2 > · · · > ajm+1 . Parathr ste ìti sto parˆdeigma A = (1, 0, 2, 0, 1) h alusda 2 ✁ 4 ✁ 5 orzei thn aÔxousa upoakolouja a2 ≤ a4 ≤ a5 . ✷ 'Estw sÔnola A1 , A2 , . . . , An . Upì poie sunj ke upˆrqoun diaforetikˆ anˆ dÔo stoiqea x1 , x2 , . . . , xn th ènwsh twn Ai ¸ste xi ∈ Ai gia kˆje 1 ≤ i ≤ n? Mia tètoia akolouja (x1 , x2 , . . . , xn ) lègetai SÔsthma Diakekrimènwn Antipros¸pwn (SDA) gia ta A1 , A2 , . . . , An . To prìblhma th Ôparxh SDA lègetai kai prìblhma tou gˆmou lìgw th ex  ermhnea . An A1 , A2 , . . . , An enai ta sÔnola twn gunaik¸n pou gnwrzoun n ˆndre y1 , y2 , . . . , yn , antstoiqa, tìte èna SDA (x1 , x2 , . . . , xn ) gia ta A1 , A2 , . . . , An antistoiqe se èna zeugˆrwma kˆje ˆndra yi me mia gunaka xi pou gnwrzei. Efarmog :

to Je¸rhma tou

Gˆmou.

H akolouja x1 = 2, x2 = 4, x3 = 3, x4 = 5, x5 = 1 apotele SDA gia ta sÔnola A1 = {1, 2, 3}, A2 = {2, 4, 5}, A3 = {3}, A4 = {1, 5} kai A5 = {1, 4}, afoÔ xi ∈ Ai gia kˆje 1 ≤ i ≤ 5. To antstoiqo zeugˆrwma apeikonzetai sto Sq ma 2.2, sto opoo gia 1 ≤ i, j ≤ 5 ta Ai kai j sundèontai me akm  an j ∈ Ai . ✷ Paradeigma.

A1

1

A2

2

A3

3

A4

4

A5

5

Sq ma 2.2: 'Ena SÔsthma Diakekrimènwn Antipros¸pwn. Paradeigma. Ta B1 = {1, 3}, B2 = {1, 3}, B3 = {1, 2, 3, 4} kai B4 = {1, 3} den èqoun SDA, diìti h ènwsh B1 ∪ B2 ∪ B4 èqei mìno dÔo stoiqea kai sunep¸ den enai dunatì na epilegoÔn diaforetikˆ anˆ dÔo stoiqea x1 ∈ B1 , x2 ∈ B2 , x4 ∈ B4 . ✷

Mia èndeixh th isqÔo tou Jewr mato 2.3.1 enai h apìdeixh tou parakˆtw jewr mato , gnwstoÔ kai w Je¸rhma tou Gˆmou. (Hall, 1935) Ta sÔnola A1 , A2 , . . . , An èqoun SDA an kai mìno an gia kˆje 1 ≤ r ≤ n h ènwsh opoiond pote r apì ta sÔnola autˆ èqei toulˆqiston r stoiqea, dhlad  an kai mìno an # (Ai1 ∪ Ai2 ∪ · · · ∪ Air ) ≥ r (2.2)

Je¸rhma 2.3.2

32 gia kˆje epilog  deikt¸n 1 ≤ i1 < · · · < ir ≤ n. Apìdeixh. An ta A1 , A2 , . . . , An èqoun SDA x1 , x2 , . . . , xn , tìte h (2.2) isqÔei profan¸ diìti to sÔnolo Ai1 ∪ Ai2 ∪ · · · ∪ Air perièqei ta diakekrimèna stoiqea xi1 , xi2 , . . . , xir . Antstrofa, èstw ìti h sunj kh tou Jewr mato isqÔei kai èstw ìti A1 ∪ A2 ∪ · · · ∪ An = {b1 , b2 , . . . , bm }. Orzoume ma merik  diˆtaxh ≤P sto sÔnolo P = {A1 , A2 , . . . , An , b1 , b2 , . . . , bm } sthn opoa ta A1 , A2 , . . . , An enai megistikˆ stoiqea, ta b1 , b2 , . . . , bm enai elaqistikˆ kai bj

ρ(x ∧ y) kaj¸ kai gia kˆje zeÔgo u, v ∈ L me ρ(u∧v) = ρ(x∧y) kai ρ(u)+ρ(v) < ρ(x)+ρ(y). Profan¸ h (4.5) isqÔei an x = y kai prokÔptei apì th sunj kh th prìtash an ta x, y kalÔptoun to x ∧ y . A upojèsoume loipìn ìti to x den kalÔptei to x ∧ y (h perptwsh katˆ thn opoa to y den kalÔptei to x ∧ y enai ìmoia) kai èstw x′ ∈ L me x∧y < x′ < x. ParathroÔme ìti x′ ∧y = x∧y kai ρ(x′ ) < ρ(x) opìte, apì thn upìjesh th epagwg  , prokÔptei ìti

ρ(x′ ) + ρ(y) ≥ ρ(x′ ∨ y) + ρ(x ∧ y).

(4.6)

ParathroÔme epsh ìti oi sqèsei x > x′ kai x′ ∨ y ≥ x′ sto L dnoun x ∧ (x′ ∨ y) ≥ x′ > x ∧ y sto L kai sunep¸

ρ(x) + ρ(x′ ∨ y) ≥ ρ(x ∨ x′ ∨ y) + ρ(x ∧ (x′ ∨ y)),

(4.7)

apì thn upìjesh th epagwg  . Prosjètonta katˆ mèlh ti (4.6) kai (4.7) kai parathr¸nta ìti x ∨ x′ ∨ y ≥ x ∨ y kai x′ ≤ x ∧ (x′ ∨ y) sto L, h (4.5) èpetai. ✷

67 'Ena peperasmèno merik¸ diatetagmèno sÔnolo P lègetai (ˆnw) hmiarjrwtì an gia tuqaa diakekrimèna stoiqea x, y tou P , ta opoa kalÔptoun kˆpoio stoiqeo tou P , upˆrqei stoiqeo tou P to opoo kalÔptei ta x kai y kai olikˆ hmiarjrwtì (totally semimodular) an to P èqei mègisto kai elˆqisto stoiqeo kai kˆje kleistì diˆsthma sto P enai hmiarjrwtì. Apì thn Prìtash 4.4.1 prokÔptei ìti gia peperasmènou sundèsmou o parapˆnw orismì th hmiarjrwsimìthta sumfwne me autìn tou OrismoÔ 4.4.1. ✷ Parat rhsh 4.4.1

Apì thn Prìtash 4.4.1 kai to qarakthrismì twn sqèsewn kˆluyh tou sundèsmou Πn twn diamersewn tou [n] (Parˆdeigma 1.2.6) prokÔptei ìti o Πn enai hmiarjrwtì . Oi leptomèreie af nontai ston anagn¸sth. ✷ Parˆdeigma 4.4.1

Se mia merik  diˆtaxh P me elˆqisto stoiqeo ˆ0 ta stoiqea pou kalÔptoun to ˆ0 lègontai ˆtoma. Orismì 4.4.2

'Estw peperasmèno sÔndesmo L me elˆqisto stoiqeo ˆ0.

(i) O L lègetai atomikì sÔndesmo an kˆje stoiqeo tou L − {ˆ0} enai sÔndesh atìmwn tou L. (ii) O L lègetai gewmetrikì sÔndesmo an enai atomikì kai hmiarjrwtì . Se kˆje peperasmèno sÔndesmo L ta ˆtoma enai anˆgwga stoiqea, me thn ènnoia pou d¸same ston ìro {anˆgwgo stoiqeo} sthn Parˆgrafo 4.2. O sÔndesmo L enai atomikì an kai mìno an ta ˆtoma enai ta mìna anˆgwga stoiqea tou. ✷

Parathrhsh.

Paradeigma.

(i) Mia alusda m kou n enai atomikì sÔndesmo an kai mìno an n ≤ 1.

(ii) H merik  diˆtaxh Bn enai atomikì sÔndesmo , diìti ta ˆtoma th Bn enai ta monosÔnola {i} me i ∈ [n] kai kˆje mh kenì uposÔnolo tou [n] grˆfetai w ènwsh monosunìlwn. Epomènw h Bn enai gewmetrikì sÔndesmo . (iii) O sÔndesmo Πn enai atomikì . Prˆgmati, ta ˆtoma tou Πn enai oi diamersei tou [n] oi opoe èqoun èna mèro me dÔo stoiqea kai ta upìloipa mèrh tou (anagkastikˆ n − 2 se pl jo ) monosÔnola. Epiplèon, kˆje σ ∈ Πn enai h sÔndesh twn atìmwn π tou Πn me π ≤ σ . Epomènw (èqonta upìyh to Parˆdeigma 4.4.1) to Πn enai gewmetrikì sÔndesmo . (iv) O sÔndesmo tou Sq mato 4.4 enai gewmetrikì .

✷

Oi gewmetriko sÔndesmoi (ii) - (iv) tou prohgoÔmenou paradegmato enai ìloi th morf  L(S) gia kˆpoio peperasmèno sÔnolo dianusmˆtwn S kai thn prˆxh kleistìthta tou Paradegmato 4.3.1 pˆnw se autì. Sthn epìmenh parˆgrafo ja dexoume ìti ìloi oi sÔndesmoi

68 aut  th morf  enai gewmetriko, gegonì to opoo exhge thn orologa {gewmetrikì sÔndesmo }. 4.5

Gewmetriko sÔndesmoi kai mhtroeid 

Arqzoume aut  thn parˆgrafo me ton orismì th ènnoia tou mhtroeidoÔ . 'Estw prˆxh kleistìthta se peperasmèno sÔnolo S , mèsw th opoa h eikìna tou A ⊆ S sumbolzetai me A. To S efodiasmèno me thn prˆxh aut  lègetai mhtroeidè (matroid) an isqÔei Orismì 4.5.1

(iv) p ∈ / A, p ∈ A ∪ {q} ⇒ q ∈ A ∪ {p} gia ìla ta p, q ∈ S kai kˆje A ⊆ S . To mhtroeidè autì lègetai aplì an epiplèon isqÔei

(v) ∅ = ∅ kai {p} = {p} gia kˆje p ∈ S . To axwma (iv) lègetai axwma th antallag  (exchange axiom) kai apotele thn krsimh idiìthta pou kˆnei ti prˆxei kleistìthta , ti opoe orsame pˆnw se peperasmèna sÔnola dianusmˆtwn sto Parˆdeigma 4.3.1, na xeqwrzoun apì ˆlle . 'Estw S peperasmèno uposÔnolo enì grammikoÔ q¸rou V pˆnw sto s¸ma K. H prˆxh kleistìthta tou Paradegmato 4.3.1 pˆnw sto S orzei mhtroeidè sto S , to opoo enai aplì an kai mìno an ta stoiqea tou S enai mh mhdenikˆ kai dÔo opoiad pote apì autˆ enai grammik¸ anexˆrthta. L mma 4.5.1

Apìdeixh. Gia ton pr¸to isqurismì, prèpei na epalhjeÔsoume to axwma th antallag  . 'Estw A = {v1 , v2 , . . . , vk } ⊆ S kai p, q ∈ S . An p ∈ A ∪ {q} kai p ∈ / A, tìte èqoume

p = c1 v1 + c2 v2 + · · · + ck vk + cq gia kˆpoia c1 , . . . , ck , c ∈ K me c 6= 0. Apì thn teleutaa isìthta prokÔptei ìti q = 1c (p − c1 v1 − · · · − ck vk ) kai ˆra q ∈ A ∪ {p}. O deÔtero isqurismì enai fanerì . ✷ 'Ena mhtroeidè pˆnw sto sÔnolo S ja sumbolzetai me M(S). Ta kleistˆ sÔnola sto M(S) lègontai kai eppeda (flats) kai o sÔndesmo L(S) twn kleist¸n sunìlwn lègetai kai sÔndesmo twn epipèdwn (lattice of flats) tou M(S). To akìloujo je¸rhma enai to kÔrio apotèlesma aut  th paragrˆfou kai dhl¸nei ìti oi ènnoie tou gewmetrikoÔ sundèsmou kai tou mhtroeidoÔ enai katˆ kˆpoio trìpo isodÔname .

69 Je¸rhma 4.5.1

(Birkhoff-Whitney)

(i) Gia kˆje mhtroeidè M(S) h merik  diˆtaxh L(S) twn epipèdwn tou M(S) apotele gewmetrikì sÔndesmo. (ii) Kˆje peperasmèno gewmetrikì sÔndesmo L me sÔnolo atìmwn S enai isìmorfo me to sÔndesmo twn epipèdwn enì aploÔ mhtroeidoÔ pˆnw sto S . To mhtroeidè autì orzetai apì thn (4.3), dhlad  jètonta _ A = {p ∈ S : p ≤ A} gia A ⊆ S .

To akìloujo l mma ja qrhsimopoihje sthn apìdeixh tou mèrou (i) tou jewr mato . 'Estw mhtroeidè M pˆnw sto sÔnolo S . Gia A, B ∈ L(S) to B kalÔptei to A an kai mìno an B = A ∪ {p} gia kˆpoio p ∈ S me p ∈ / A.

L mma 4.5.2

Apìdeixh. Upojètoume pr¸ta ìti to B kalÔptei to A (opìte A ⊂ B ) kai jewroÔme p ∈ B −A. 'Eqoume A ⊂ A∪{p} ⊆ B kai, efarmìzonta to L mma 4.3.1 (ii), parnoume A < A ∪ {p} ≤ B sto L(S). 'Epetai ìti B = A ∪ {p}. Antstrofa, èstw A, B ∈ L(S) me B = A ∪ {p} kai p ∈ S − A. Upojètonta ìti A ⊂ C ⊆ B gia kˆpoio C ∈ L(S), arke na dexoume ìti C = B . 'Estw q ∈ C − A. Apì ti sqèsei q ∈ A ∪ {p}, q ∈ / A = A kai to axwma th antallag  prokÔptei ìti p ∈ A ∪ {q}. 'Omw A ∪ {q} ⊆ C kai sunep¸ A ∪ {q} ⊆ C apì to L mma 4.3.1 (ii), opìte p ∈ C . 'Ara A ∪ {p} ⊆ C kai sunep¸ , exaita tou diou l mmato èqoume B = A ∪ {p} ⊆ C . 'Epetai ìti B = C , ìpw to jèlame. ✷ Apìdeixh tou Jewr mato 4.5.1 (i). Gnwrzoume apì thn Prìtash 4.3.1 ìti to L(S) enai sÔndesmo . Apì to L mma 4.5.2 gnwrzoume epsh ìti ta ˆtoma tou L(S) enai ta sÔnola th / ∅. Gia A ∈ L(S) èqoume morf  {p} me p ∈

A =

[

{a}

(4.8)

a∈A

(giat?). Apì thn Prìtash 4.3.1 to dexiì mèlo th (4.8) enai so me th sÔndesh sto L(S) twn {a} me a ∈ A. 'Epetai ìti o sÔndesmo L(S) enai atomikì . Mènei na dexoume ìti o L(S) enai kai hmiarjrwtì . Apì thn Prìtash 4.4.1 arke na dexoume ìti an ta x, y kalÔptoun to x ∧ y sto L(S), tìte to x ∨ y kalÔptei ta x, y . SÔmfwna me to L mma 4.5.2 mporoÔme na

70 upojèsoume ìti x ∧ y = A ∈ L(S), x = A ∪ {p} kai y = A ∪ {q} me p, q ∈ S − A. Apì ti idiìthte (i) - (iii) tou OrismoÔ 4.3.1 kai thn Prìtash 4.3.1 brskoume ìti

x ∨ y = x ∪ y = A ∪ {p, q} = x ∪ {q} = y ∪ {p}. Profan¸ ta x, y den enai sugkrsima sto L(S) kai sunep¸ p ∈ / y kai q ∈ / x. Apì ti prohgoÔmene isìthte kai to L mma 4.5.2 prokÔptei ìti to x ∨ y kalÔptei ta x, y . ✷ An S enai peperasmèno uposÔnolo enì grammikoÔ q¸rou V pˆnw sto s¸ma K, tìte h merik  diˆtaxh L(S) twn kleist¸n sunìlwn, w pro thn prˆxh kleistìthta tou Paradegmato 4.3.1 pˆnw sto S , enai gewmetrikì sÔndesmo . Pìrisma 4.5.1

Apìdeixh. Sunduˆzoume to Je¸rhma 4.5.1 (i) me to L mma 4.5.1.

✷

Oi gewmetriko sÔndesmoi Bn kai Πn enai isìmorfoi me sundèsmou th morf  L(S), ìpw sto Pìrisma 4.5.1. Prˆgmati, an S enai bˆsh (grammikˆ anexˆrthto uposÔnolo me n stoiqea) tou grammikoÔ q¸rou Rn , tìte kˆje uposÔnolo tou S enai kleistì kai to L(S) apoteletai apì ìla ta merik¸ diatetagmèna me th sqèsh tou egkleismoÔ uposÔnola tou S . Sunep¸ enai isìmorfo me to Bn . Isqurizìmaste epsh ìti an {e1 , e2 , . . . , en } enai bˆsh tou Rn kai S = {ei − ej : 1 ≤ i < j ≤ n}, tìte to L(S) enai isìmorfo me to Πn (ja apodexoume mia genikìterh prìtash sthn Parˆgrafo 4.6). ✷ Parathrhsh.

Sto Sq ma 4.5 apeikonzetai èna gewmetrikì sÔndesmo tˆxh 3 me sÔnolo atìmwn S = {a, b, c, d}. Me thn prˆxh pou orzei h (4.3), èqoume {a, b} = {a, c} = {b, c} = {a, b, c}, {a, d} = {a, d}, {b, d} = {b, d}, {c, d} = {c, d} kai {a, b, d} = {a, c, d} = {b, c, d} = {a, b, c, d}. ✷ Paradeigma.

Apìdeixh tou Jewr mato 4.5.1 (ii). Ja dexoume pr¸ta ìti h (4.3) orzei èna aplì mhtroeidè sto sÔnolo S twn atìmwn tou L. ParathroÔme ìti to S sumpptei me to sÔnolo twn anˆgwgwn stoiqewn tou L, ìpw autì orsthke sthn Parˆgrafo 4.2. Sunep¸ to ìti ta axi¸mata (i) - (iii) tou OrismoÔ 4.3.1 isqÔoun prokÔptei apì thn Prìtash 4.3.2. Gia to (iv) (axwma th antallag  ), upenjumzoume ìti o gewmetrikì sÔndesmo L enai diabajmismèno . 'Estw ρ(y) W h tˆxh tou y ∈ L kai èstw A ⊆ S , p, q ∈ S me p ∈ / A kai p ∈ A ∪ {q}. Jètonta x = A èqoume p 6≤ x kai p ≤ x ∨ q . Apì thn (4.5) èqoume

ρ(x ∨ q) ≤ ρ(x) + ρ(q) − ρ(x ∧ q) ≤ ρ(x) + 1.

71 1

a

b

c

d

0

Sq ma 4.5: 'Ena gewmetrikì sÔndesmo me tèssera ˆtoma. Apì ti upojèsei ma isqÔei x < x ∨ p ≤ x ∨ p ∨ q = x ∨ q kai sunep¸

ρ(x) + 1 ≤ ρ(x ∨ p) ≤ ρ(x ∨ p ∨ q) = ρ(x ∨ q) ≤ ρ(x) + 1. Upoqrewtikˆ loipìn isqÔei pantoÔ h isìthta. H sqèsh ρ(x ∨ p) = ρ(x ∨ p ∨ q) dnei x ∨ p = x ∨ p ∨ q kai sunep¸ q ≤ x ∨ p, dhlad  q ∈ A ∪ {p}, ìpw to jèlame. To axwma (v) tou OrismoÔ 4.3.1 enai fanerì. To ìti o sÔndesmo L enai isìmorfo me to sÔndesmo L(S), twn kleist¸n sunìlwn tou mhtroeidoÔ pou orsame, prokÔptei epsh apì thn Prìtash 4.3.2. ✷

4.6

Stoiqei¸dei idiìthte mhtroeid¸n

H jewra twn mhtroeid¸n parèqei èna kajarˆ sunduastikì plasio sto opoo mporoÔn na melethjoÔn oi ènnoie th grammik  exˆrthsh kai anexarthsa peperasmènou pl jou stoiqewn (dianusmˆtwn) enì grammikoÔ q¸rou. Pollè apì ti ènnoie kai kataskeuè pou sunantˆ kane sth jewra aut  proèrqontai apì (kai genikeÔoun katˆllhla) antstoiqe ènnoie kai kataskeuè sth jewra twn grafhmˆtwn. Sthn parˆgrafo aut  dnoume kˆpoiou apì tou pio basikoÔ orismoÔ kai idiìthte twn mhtroeid¸n kai sth sunèqeia, ant na proqwr soume perissìtero me th stoiqei¸dh jewra tou (enallaktikˆ sust mata axiwmˆtwn, diagraf  kai sustol , du¨ikìthta klp), perigrˆfoume ta mhtroeid  pou orzontai apì graf mata. 'Estw mhtroeidè M pˆnw sto sÔnolo S kai A ⊆ S . To A lègetai anexˆrthto an p ∈ / A − {p} gia kˆje p ∈ A (opìte to A = ∅ enai anexˆrthto) kai parˆgon an A = S . An to A enai tautìqrona anexˆrthto kai parˆgon, tìte lègetai bˆsh tou M . 'Ena elaqistikì

72 exarthmèno (dhlad  ìqi anexˆrthto) uposÔnolo tou S lègetai kÔklwma. Ja sumbolzoume (pio swstˆ) me L(M) to sÔndesmo L(S) twn epipèdwn tou M . Apì to Je¸rhma 4.5.1 (i) gnwrzoume ìti o sÔndesmo L(M) enai diabajmismèno . H tˆxh tou lègetai tˆxh tou M . Ta stoiqea tou L(M) tˆxh 1 kai 2 lègontai shmea kai eujee tou M , antstoiqa. Sto Sq ma 4.6 apeikonzetai èna aplì mhtroeidè F tˆxh 3 me eptˆ shmea kai eptˆ eujee , to legìmeno eppedo tou Fano. 'Etsi o sÔndesmo twn epipèdwn L(F ) apoteletai apì to kenì sÔnolo, ta eptˆ shmea, ti eptˆ eujee kai to sÔnolo S twn eptˆ shmewn, merik¸ diatetagmèna me th sqèsh tou egkleismoÔ. H kleist  j kh tou A ⊆ S orzetai apì thn (4.3). Sto parˆdeigma autì kˆje eujea èqei tra shmea kai apotele kÔklwma tou F en¸ bˆsh enai kˆje sÔnolo tri¸n mh suneujeiak¸n shmewn. Af netai ston anagn¸sth na epalhjeÔsei ìti to F enai isìmorfo me to mhtroeidè pou orzoun ta eptˆ dianÔsmata tou tridiˆstatou grammikoÔ q¸rou F32 , pˆnw sto s¸ma F2 = {0, 1} me dÔo stoiqea, pou fanontai sto sq ma. Shmei¸noume ìti upˆrqoun mhtroeid  pou den mporoÔn na prokÔyoun w mhtroeid  dianusmˆtwn grammikoÔ q¸rou pˆnw se s¸ma K, gia kanèna K. ✷ Paradeigma.

100

110

101 111

010

011

001

Sq ma 4.6: To eppedo tou Fano. Oi epìmene protˆsei genikeÔoun gnwstè protˆsei th grammik  ˆlgebra . L mma 4.6.1

'Estw mhtroeidè M pˆnw sto sÔnolo S .

(i) An A ⊆ B ⊆ S kai to B enai anexˆrthto, tìte to A enai epsh anexˆrthto. (ii) 'Estw ìti to A ⊆ S enai anexˆrthto kai p ∈ S − A. Tìte to A ∪ {p} enai anexˆrthto an kai mìno an p ∈ / A.

73 Apìdeixh. (i) 'Estw ìti to B ⊆ S enai anexˆrthto kai A ⊆ B . 'Estw tuqao p ∈ A, opìte kai p ∈ B . Epeid  to B enai anexˆrthto èqoume p ∈ / B − {p}. Akìmh A − {p} ⊆ B − {p} kai sunep¸ A − {p} ⊆ B − {p}, opìte p ∈ / A − {p}. 'Eqoume dexei ìti p ∈ / A − {p} gia kˆje p ∈ A kai epomènw , to A enai anexˆrthto.

(ii) Upojètoume pr¸ta ìti to sÔnolo A ∪ {p} enai anexˆrthto. Tìte, sÔmfwna me ton orismì / (A ∪ {p}) − {p}, dhlad  p ∈ / A. Upojèsoume t¸ra ìti p ∈ /A th anexarthsa , èqoume p ∈ kai jewroÔme q ∈ A ∪ {p}. Ja dexoume ìti q ∈ / (A ∪ {p}) − {q}. Prˆgmati, autì enai isodÔnamo me thn upìjesh p ∈ / A an q = p. 'Estw q 6= p, opìte apì th sqèsh aut  kai thn q ∈ A ∪ {p} èqoume q ∈ A. Exaita th anexarthsa tou A, èqoume q ∈ / A − {q}. Apì th sqèsh aut  prokÔptei ìti q ∈ / (A − {q}) ∪ {p} diìti, an eqame q ∈ (A − {q}) ∪ {p}, tìte sÔmfwna me to axwma th antallag  , ja eqame kai p ∈ (A − {q}) ∪ {q} = A, se antfash me thn upìjesh p ∈ / A. Sunep¸ q ∈ / (A − {q}) ∪ {p} = (A ∪ {p}) − {q}, ìpw to jèlame. Sumperanoume ìti to A ∪ {p} enai anexˆrthto. ✷ Prìtash 4.6.1

'Estw mhtroeidè M pˆnw sto sÔnolo S .

(i) Kˆje anexˆrthto uposÔnolo tou S mpore na epektaje se bˆsh tou M . (ii) Kˆje parˆgon uposÔnolo tou S perièqei toulˆqiston ma bˆsh tou M . (iii) 'Ole oi bˆsei tou M perièqoun r stoiqea, ìpou r enai h tˆxh tou M . Apìdeixh. (i) 'Estw anexˆrthto A ⊆ S . An to A den enai bˆsh, tìte upˆrqei p ∈ S me p ∈ / A. Apì to L mma 4.6.1 (ii) prokÔptei ìti to A ∪ {p} enai anexˆrthto. Suneqzoume na prosjètoume, an autì enai aparathto, sto A ∪ {p} stoiqea me ton dio trìpo èw ìtou ftˆsoume se bˆsh tou M .

(ii) 'Estw A ⊆ S me A = S . An to A den enai bˆsh, tìte den enai anexˆrthto kai sunep¸ upˆrqei p ∈ A me A − {p} = A, opìte A − {p} = S . Suneqzoume na afairoÔme, an autì enai aparathto, stoiqea apì to A − {p} me ton dio trìpo èw ìtou ftˆsoume se bˆsh tou M . (iii) An B = {p1 , p2 , . . . , pm } enai bˆsh tou M , tìte apì to L mma 4.5.2 prokÔptei ìti h ∅ ⊂ {p1 } ⊂ {p1 , p2 } ⊂ · · · ⊂ {p1 , p2 , . . . , pm } = S enai megistik  alusda tou sundèsmou twn epipèdwn L(M). Epomènw to m ko m th alusda enai so me thn tˆxh tou M . ✷ 'Estw V sÔnolo me n stoiqea. 'Ena aplì grˆfhma sto
sÔnolo koruf¸n V enai èna zeÔgo G = (V, E), ìpou E enai uposÔnolo tou sunìlou V2

Mhtroeid 

apì

graf mata.

74 twn uposunìlwn tou V me dÔo stoiqea (ja jewr soume mìno aplˆ graf mata se ìti akolouje gia lìgou aplìthta ). Ta stoiqea twn V kai E lègontai korufè kai akmè tou G, antstoiqa. Gia U ⊆ V to epagìmeno upogrˆfhma tou G sto sÔnolo koruf¸n U enai to
zeÔgo GU = (U, EU ) me EU = E ∩ U2 , en¸ gia A ⊆ E sumbolzoume me GA to grˆfhma (V, A). Lème ìti dÔo korufè a, b ∈ V sundèontai sto G an upˆrqoun m ≥ 0 kai {u0 , u1}, {u1 , u2}, . . . , {um−1 , um } ∈ E ¸ste u0 = a kai um = b (jewr¸nta m = 0, parathroÔme ìti kˆje koruf  sundèetai me ton eautì th ). H sqèsh th sÔndesh metaxÔ koruf¸n enai sqèsh isodunama sto V . Ta epagìmena upograf mata tou G sti klˆsei isodunama th sqèsh aut  lègontai sunektikè sunist¸se tou G. To G lègetai sunektikì an èqei ma kai mìno sunektik  sunist¸sa, dhlad  an opoiesd pote dÔo korufè tou sundèontai sto G.

a

d

b

c

Sq ma 4.7: 'Ena aplì grˆfhma me tèsseri korufè . Sto Sq ma 4.7 apeikonzetai èna aplì grˆfhma sto sÔnolo koruf¸n V = {a, b, c, d} me akmè {a, b}, {a, c}, {a, d}, {b, c} kai {c, d}. To epagìmeno upogrˆfhma tou G sto sÔnolo koruf¸n U = {b, d} enai to grˆfhma me korufè b, d qwr akm . ✷ Paradeigma.

'Estw G = (V, E) ìpw prohgoumènw , me V = {v1 , v2 , . . . , vn } kai èstw {e1 , e2 , . . . , en } mia dosmènh bˆsh tou grammikoÔ q¸rou Rn . JewroÔme to uposÔnolo

S = {ei − ej : 1 ≤ i < j ≤ n, {vi , vj } ∈ E}

(4.9)

tou Rn kai parathroÔme ìti h apeikìnish φ : E → S me φ({vi , vj }) = ei − ej enai amfrriyh. 'Estw M(S) to aplì mhtroeidè pˆnw se kˆpoio sÔnolo S dianusmˆtwn tou Rn pou orzetai apì to Parˆdeigma 4.3.1 (blèpe L mma 4.5.1). Orzoume to aplì mhtroeidè MG pˆnw sto sÔnolo E jètonta A = B sto MG gia A ⊆ E , an φ(A) = φ(B) sto M(S). Me ˆlla lìgia, qrhsimopoioÔme thn amfrriyh φ gia na metafèroume th dom  tou mhtroeidoÔ M(S) apì to S sto E . H dom  tou mhtroeidoÔ MG kajorzetai apì to G mèsw gnwst¸n ennoi¸n th jewra grafhmˆtwn, ti opoe upenjumzoume sÔntoma sto shmeo autì. To grˆfhma G lègetai kÔklwma m kou r an E = {{u1 , u2}, {u2, u3 }, . . . , {ur−1, ur }, {ur , u1 }} gia kˆpoie diakekrimène

75 korufè u1 , u2, . . . , ur ∈ V me r ≥ 3. To G lègetai dˆso an den perièqei kÔklwma (w upogrˆfhma th morf  GA me A ⊆ E ). IsodÔnama, to G enai dˆso an èqei to polÔ n − 1 akmè kai akrib¸ n − #E sunektikè sunist¸se . To G lègetai dèndro (Sq ma 4.8) an enai sunektikì dˆso  , isodÔnama, an enai sunektikì kai èqei akrib¸ n − 1 akmè . Kˆje sunektik  sunist¸sa enì dˆsou G enai dèndro, w epagìmeno upogrˆfhma tou G. To grˆfhma G tou Sq mato 4.7 enai sunektikì kai perièqei dÔo kukl¸mata m kou 3 kai èna m kou 4. To upogrˆfhma GA enai dèndro gia 8 (akrib¸ ) sÔnola A ⊆ E , ìla me tra stoiqea, ìpw p.q. ta A1 = {{a, b}, {a, c}, {c, d}} kai A2 = {{a, c}, {b, c}, {c, d}}. To GA enai dˆso an kai mìno an enai dèndro   isqÔei #A ≤ 2. ✷ Paradeigma.

Sq ma 4.8: 'Ena dèndro me dekapènte korufè . 'Estw aplì grˆfhma G = (V, E) sto sÔnolo koruf¸n V = {v1 , v2 , . . . , vn } me k sunektikè sunist¸se kai èstw MG to antstoiqo mhtroeidè . Prìtash 4.6.2

(i) Gia A ⊆ E kai {vi , vj } ∈ E èqoume {vi , vj } ∈ A sto MG an kai mìno an oi korufè vi kai vj an koun sthn dia sunektik  sunist¸sa tou GA . Eidikìtera, isqÔei A ∈ L(MG ) an kai mìno an to A perièqei kˆje akm  tou G ta ˆkra th opoa an koun sthn dia sunektik  sunist¸sa tou GA . (ii) To A ⊆ E enai anexˆrthto sto MG an kai mìno an to grˆfhma GA enai dˆso . (iii) To A ⊆ E enai kÔklwma sto MG an kai mìno an to grˆfhma GA enai kÔklwma. (iv) To A ⊆ E enai parˆgon sto MG an kai mìno an to GA èqei k sunektikè sunist¸se . (v) To A ⊆ E enai bˆsh tou MG an kai mìno an to grˆfhma GA enai dˆso me k sunektikè sunist¸se . Eidikìtera, h tˆxh tou MG enai sh me n − k kai an to G enai sunektikì, tìte to A ⊆ E enai bˆsh tou MG an kai mìno an to grˆfhma GA enai dèndro.

76 Apìdeixh. 'Estw to sÔnolo twn dianusmˆtwn S , ìpw sthn (4.9).

(i) 'Estw ìti ta vi kai vj an koun sthn dia sunektik  sunist¸sa tou GA , opìte upˆrqei m ≥ 1 kai akmè {vi0 , vi1 }, {vi1 , vi2 }, . . . , {vim−1 , vim } ∈ A me i0 = i kai im = j . Tìte to diˆnusma ei − ej enai so me to ˆjroisma twn stoiqewn eir − eir+1 gia 0 ≤ r ≤ m − 1 tou φ(A) kai sunep¸ an kei sth grammik  j kh tou φ(A) ston Rn . Sumperanoume ìti ei − ej ∈ φ(A) sto M(S), pou shmanei ìti {vi , vj } ∈ A sto MG . Antstrofa, èstw ìti {vi , vj } ∈ A kai èstw W h grammik  j kh tou φ(A) ston Rn , opìte ei − ej ∈ W . Enai stoiqei¸de na dexei kane ìti o grammikì q¸ro phlko Rn /W èqei diˆstash sh me to pl jo twn sunektik¸n sunistws¸n tou GA kai ìti mia bˆsh tou q¸rou autoÔ apoteletai apì ti eikìne twn dianusmˆtwn er (upì th fusik  probol  Rn → Rn /W ) gia r ∈ I , ìpou ta vr gia r ∈ I apoteloÔn epilog  mia koruf  gia kˆje sunektik  sunist¸sa tou GA . Efìson oi eikìne twn ei kai ej enai se sto q¸ro phlko, upoqrewtikˆ ta vi kai vj na an koun sthn dia sunektik  sunist¸sa tou GA . (ii) Apì ton orismì th anexarthsa kai thn (i) èqoume ìti to A ⊆ E enai anexˆrthto sto MG an kai mìno an gia kˆje a = {vi , vj } ∈ A ta vi kai vj den an koun sthn dia sunektik  sunist¸sa tou GA−{a} . Autì sumbanei an kai mìno an to G den perièqei kÔklwma, dhlad  an kai mìno an to G enai dˆso . (iii) ProkÔptei ˆmesa apì to (ii). (iv) Apì to sqetikì orismì kai thn (i) èqoume ìti to A ⊆ E enai parˆgon sto MG an kai mìno an gia kˆje {vi , vj } ∈ E ta vi kai vj an koun sthn dia sunektik  sunist¸sa tou GA , pou shmanei ìti kˆje sunektik  sunist¸sa tou G paramènei sunektik  pern¸nta sto upogrˆfhma GA . (v) O pr¸to isqurismì prokÔptei ˆmesa apì ti (ii) kai (iv). Gia to deÔtero, upenjumzoume ìti kˆje dˆso me n korufè kai k sunektikè sunist¸se èqei n − k akmè . ✷ P¸ mpore na perigrafe o sÔndesmo twn epipèdwn tou MG apì to grˆfhma G? 'Estw aplì grˆfhma G = (V, E). Mia diamèrish π tou sunìlou V lègetai sunektik  an gia kˆje mèro B th π to epagìmeno upogrˆfhma GB tou G enai sunektikì. Orismì 4.6.1

To sÔnolo twn sunektik¸n diamersewn tou G, efodiasmèno me th merik  diˆtaxh th eklèptunsh (dhlad  me π ≤ σ an kˆje mèro th π perièqetai se kˆpoio mèro th σ ), lègetai sÔndesmo twn sustol¸n (lattice of contractions) tou G kai sumbolzetai me LG . An G enai to grˆfhma tou Sq mato 4.7, tìte to LG èqei elˆqisto stoiqeo th diamèrish tou V se tèssera monosÔnola, mègisto stoiqeo th diamèrish tou V se èna mìno mèro , 5 ˆtoma ta opoa enai diamersei tou V se èna disÔnolo kai dÔo monosÔnola Paradeigma.

77 kai antistoiqoÔn sti 5 akmè tou G kai 6 akìmh stoiqea. Af netai ston anagn¸sth na epalhjeÔsei ìti to LG enai isìmorfo me to gewmetrikì sÔndesmo tou Sq mato 4.4. ✷ Gia kˆje grˆfhma G = (V, E) to LG èqei elˆqisto stoiqeo th diamèrish tou V se monosÔnola kai mègisto stoiqeo th diamèrish tou V sti sunektikè sunist¸se tou G. H akìloujh prìtash dnei perissìtere plhrofore gia th dom  tou LG . O sÔndesmo L(MG ) twn epipèdwn tou MG enai isìmorfo me th merik  diˆtaxh LG . Eidikìtera to LG enai gewmetrikì sÔndesmo tˆxh n − k , ìpou n kai k enai to pl jo twn koruf¸n kai twn sunektik¸n sunistws¸n tou G, antstoiqa. Prìtash 4.6.3

Apìdeixh. Gia A ∈ L(MG ) èstw f (A) h diamèrish tou V , ta mèrh th opoa enai ta sÔnola koruf¸n twn sunektik¸n sunistws¸n tou GA . Enai fanerì ìti f (A) ∈ LG kai ìti h apeikìnish f : L(MG ) → LG diathre th diˆtaxh. Gia π ∈ LG èstw A = g(π) to sÔnolo ìlwn twn akm¸n {vi , vj } ∈ E gia ti opoe ta vi kai vj an koun sto dio mèro th π . Apì thn Prìtash 4.6.2 (i) èqoume A = A, opìte h g : LG → L(MG ) enai kalˆ orismènh kai profan¸ diathre th diˆtaxh. Tèlo parathroÔme ìti g(f (A)) = A gia kˆje A ∈ L(MG ) apì thn Prìtash 4.6.2 (i) kai ìti f (g(π)) = π gia kˆje π ∈ LG . 'Epetai ìti h f enai isomorfismì merik¸n diatˆxewn me antstrofo th g . O teleutao isqurismì th prìtash prokÔptei apì to Pìrisma 4.5.1 kai thn Prìtash 4.6.2 (v). ✷ H klˆsh
twn gewmetrik¸n sundèsmwn LG perièqei ti Bn kai Πn gia kˆje n ∈ N. An G = (V, V2 ) enai to pl re grˆfhma sto sÔnolo koruf¸n V = [n], tìte kˆje diamèrish tou [n] enai sunektik  kai sunep¸ LG = Πn . Epsh an G enai to grˆfhma sto sÔnolo koruf¸n V = {0, 1, . . . , n} me ti n akmè {0, 1}, {0, 2}, . . . , {0, n}, tìte to LG enai isìmorfo me th Bn . Prˆgmati, oi sunektikè diamersei tou G enai akrib¸ oi diamersei πS , ìpou S ⊆ [n], pou apoteloÔntai apì to mèro {0} ∪ S , kai ta monosÔnola {i} gia i ∈ [n] − S kai h apeikìnish f : Bn → LG me f (S) = πS enai isomorfismì merik¸n diatˆxewn. 'Epetai ìti oi Bn kai Πn enai gewmetriko sÔndesmoi. ✷ Parat rhsh 4.6.1

4.7

Hmiepimeristiko sÔndesmoi kai kurtè gewmetre

Sthn paroÔsa parˆgrafo orzoume ti ènnoie tou hmiepimeristikoÔ sundèsmou kai th kurt  gewmetra kai apodeiknÔoume ìti autè susqetzontai katˆ trìpo anˆlogo me ekenon pou susqetzontai oi ènnoie tou gewmetrikoÔ sundèsmou kai tou mhtroeidoÔ . Arqzoume me ti kurtè gewmetre .

78 'Estw prˆxh kleistìthta se peperasmèno sÔnolo S , mèsw th opoa h eikìna tou A ⊆ S sumbolzetai me A. To S efodiasmèno me thn prˆxh aut  lègetai kurt  gewmetra (convex geometry) an isqÔei Orismì 4.7.1

(iv′ ) p, q ∈ / A, p 6= q , p ∈ A ∪ {q} ⇒ q ∈ / A ∪ {p} gia ìla ta p, q ∈ S kai kˆje A ⊆ S . Sthn perptwsh aut  ta kleistˆ uposÔnola tou S lègontai epsh kurtˆ uposÔnola. Oi prˆxei kleistìthta twn Paradeigmˆtwn 4.3.2 kai 4.3.3 dnoun dÔo basikˆ paradegmata kurt¸n gewmetri¸n. 'Estw P peperasmèno merik¸ diatetagmèno sÔnolo. H prˆxh kleistìthta tou Paradegmato 4.3.2, h opoa apeikonzei to A ⊆ P sto ide¸de A = A− tou P pou parˆgei to A, orzei kurt  gewmetra sto P . Gia na epalhjeÔsoume to axwma (iv′ ) èstw p, q ∈ P kai A ⊆ P me p, q ∈ / A, p 6= q kai p ∈ A ∪ {q}. 'Eqoume p ≤ a gia kˆpoio a ∈ A ∪ {q}. Efìson p ∈ / A ja prèpei a = q , dhlad  p ≤ q . Omow an sque q ∈ A ∪ {p} tìte q ≤ p, opìte anagkastikˆ p = q , se antjesh me ti upojèsei ma gia ta p, q . 'Ara q ∈ / A ∪ {p}. Me thn prˆxh aut  ta kleistˆ uposÔnola tou P enai ta ide¸dh tou P kai sunep¸ o sÔndesmo L(P ) enai o epimeristikì sÔndesmo J(P ) twn idewd¸n tou P pou melet same sti Paragrˆfou 3.2 kai 4.2. ✷ Parˆdeigma 4.7.1

'Estw S peperasmèno uposÔnolo tou Rd . Ja dexoume ìti h prˆxh kleistìthta tou Paradegmato 4.3.3 orzei kurt  gewmetra sto S , dhlad  ìti isqÔei to axwma (iv′ ). 'Estw A = conv(A) ∩ S gia A ⊆ S (ìpw sto Parˆdeigma 4.3.3) kai èstw p, q ∈ S kai A ⊆ S me p, q ∈ / A, p 6= q , p ∈ A ∪ {q} kai q ∈ A ∪ {p}. Jèloume na katal xoume se antfash. Apì ti sqèsei p ∈ A ∪ {q} kai q ∈ A ∪ {p} èqoume Parˆdeigma 4.7.2

p = q =

λq + (1 − λ)a µp + (1 − µ)b

(4.10)

me 0 ≤ λ, µ ≤ 1 kai a, b ∈ conv(A). H upìjesh p 6= q dnei λ, µ < 1. Apalefonta to q apì ti (4.10) prokÔptei ìti (1 − λ)a + λ(1 − µ)b p = . 1 − λµ H parˆstash sto dexiì mèlo aut  th isìthta enai kurtì sunduasmì twn a kai b kai sunep¸ p ∈ conv({a, b}) ⊆ conv(A), opìte p ∈ conv(A) ∩ S = A, se antjesh me ti upojèsei ma . Sto parˆdeigma autì ofeletai h orologa {kurt  gewmetra} tou OrismoÔ 4.7.1. ✷

79 Sto Sq ma 4.9 apeikonzetai èna sÔnolo S = {a, b, c} tri¸n shmewn sto R kai o antstoiqo sÔndesmo L(S) twn kurt¸n uposunìlwn tou S . ParathroÔme ìti o sÔndesmo L(S) den enai epimeristikì . ✷

Paradeigma.

{a,b,c} {a,b}

a

b S

c

{a}

{b,c}

{b}

{c}

{}

L(S)

Sq ma 4.9: O sÔndesmo twn kurt¸n sunìlwn mia kurt  gewmetra . Sthn Parˆgrafo 4.5 edame ìti èna peperasmèno sÔndesmo L enai isìmorfo me to sÔndesmo twn epipèdwn enì mhtroeidoÔ an kai mìno an o L enai gewmetrikì . Ja doÔme ìti parìmoio qarakthrismì upˆrqei kai gia tou sundèsmou twn kurt¸n sunìlwn mia kurt  gewmetra . Apì to Parˆdeigma 4.7.1 kai to Je¸rhma 4.2.1 kaj¸ kai apì to parˆdeigma tou Sq mato 4.9, prokÔptei ìti h kathgora aut¸n twn sundèsmwn perièqei gn sia ìlou tou peperasmènou epimeristikoÔ sundèsmou . O peperasmèno sÔndesmo L lègetai hmiepimeristikì (meet-distributive) an kˆje diˆsthma th morf  [x, y] sto L, ìpou x enai h sunˆnthsh twn stoiqewn tou L pou kalÔptoun to y , enai isìmorfo me mia ˆlgebra Boole. Orismì 4.7.2

Paradeigma.

tikì ).

(i) O sÔndesmo tou Sq mato 4.9 enai hmiepimeristikì (allˆ ìqi epimeris-

(ii) Qrhsimopoi¸nta to Je¸rhma 4.2.1 mpore kane na dexei ìti kˆje peperasmèno epimeristikì sÔndesmo enai hmiepimeristikì . O isqurismì autì enai eidik  perptwsh th mia kateÔjunsh tou Jewr mato 4.7.1 pou akolouje. ✷ To akìloujo je¸rhma enai to kÔrio apotèlesma aut  th paragrˆfou.

80 (Edelman, 1980) 'Ena peperasmèno sÔndesmo L enai isìmorfo me to sÔndesmo twn kurt¸n sunìlwn mia kurt  gewmetra an kai mìno an o L enai hmiepimeristikì . Je¸rhma 4.7.1

'Estw kurt  gewmetra pˆnw sto sÔnolo S kai A, B ∈ L(S). To B kalÔptei to A sto L(S) an kai mìno an B = A ∪ {p} gia kˆpoio p ∈ S − A. L mma 4.7.1

Apìdeixh. 'Estw ìti to B kalÔptei to A sto L(S) kai èstw p ∈ B − A. Apì th sqèsh A ⊂ A ∪ {p} ⊆ B èqoume A ⊂ A ∪ {p} ⊆ B kai sunep¸ A ∪ {p} = B . A upojèsoume ìti A ∪ {p} ⊂ B , me q ∈ B , q ∈ / A ∪ {p}. Efarmìzonta to axwma (iv′ ) sth sqèsh q ∈ A ∪ {p} prokÔptei ìti p ∈ / A ∪ {q} kai sunep¸ A ⊂ A ∪ {q} ⊂ B , opìte h A ⊂ B den enai sqèsh kˆluyh sto L(S). H antfash aut  odhge sto sumpèrasma ìti B = A∪{p}. To antstrofo enai fanerì. ✷ To akìloujo pìrisma apodeiknÔei th mia apì ti dÔo kateujÔnsei tou Jewr mato 4.7.1. Pìrisma 4.7.1

hmiepimeristikì .

O sÔndesmo twn kurt¸n sunìlwn mia kurt  gewmetra pˆnw sto S enai

Apìdeixh. 'Estw X, Y ∈ L(S) me X = Y1 ∧ Y2 ∧ · · · ∧ Yk , ìpou Y1 , Y2 , . . . , Yk enai ta stoiqea tou L(S) pou kalÔptontai apì to Y . Apì to L mma 4.7.1 èqoume Yi = Y − {qi } gia 1 ≤ i ≤ k , ìpou ta qi enai diakekrimèna anˆ dÔo stoiqea tou Y kai apì thn Prìtash 4.3.1 isqÔei X = Y1 ∩ Y2 ∩ · · · ∩ Yk = Y − {q1 , q2 , . . . , qk }. Epiplèon, kˆje uposÔnolo Z tou S me X ⊆ Z ⊆ Y enai so me thn tom , ˆra kai me th sunˆnthsh sto L(S) kˆpoiwn apì ta Yi (sugkekrimèna twn Yi me qi ∈ / Z ). Eidikìtera Z ∈ L(S). 'Epetai ìti to diˆsthma [X, Y ] sto L(S) apoteletai apì ìla ta sÔnola Z me X ⊆ Z ⊆ Y kai ìti h apeikìnish f : [X, Y ] → 2Y −X me f (Z) = Z − X enai isomorfismì apì to [X, Y ] sthn ˆlgebra Boole tˆxh k twn uposunìlwn tou Y − X = {q1 , q2 , . . . , qk }. ✷ Prin asqolhjoÔme me thn antstrofh kateÔjunsh ja exˆgoume kˆpoia akìmh sumperˆsmata gia tou sundèsmou L(S). O sÔndesmo twn kurt¸n sunìlwn mia kurt  gewmetra pˆnw sto S enai diabajmismèno tˆxh #S .

Pìrisma 4.7.2

Apìdeixh. ProkÔptei ˆmesa apì to L mma 4.7.1 kai to gegonì ìti to L(S) èqei mègisto stoiqeo to S kai elˆqisto stoiqeo to kenì sÔnolo. ✷

81 'Opw sthn perptwsh twn mhtroeid¸n (Parˆgrafo 4.6), to A ⊆ S lègetai anexˆrthto an p∈ / A − {p} gia kˆje p ∈ A. ParathroÔme ìti ta anexˆrthta sÔnola sthn kurt  gewmetra tou Paradegmato 4.3.2 enai akrib¸ oi antialusde th merik  diˆtaxh P , en¸ se aut  tou Paradegmato 4.3.3 enai ta uposÔnola tou shmeiosunìlou S pou brskontai se kurt  jèsh. Epsh to A ⊆ S lègetai parˆgon uposÔnolo tou K ∈ L(S) an A = K . H epìmenh prìtash genikeÔei thn ex  prìtash: Kˆje ide¸de se peperasmènh merik  diˆtaxh P parˆgetai apì monadik  antialusda th P . Kˆje kurtì sÔnolo K ∈ L(S) mia kurt  gewmetra pˆnw sto S èqei monadikì anexˆrthto parˆgon uposÔnolo.

Prìtash 4.7.1

Apìdeixh. H Ôparxh anexˆrthtou parˆgonto uposunìlou tou K prokÔptei apì thn apìdeixh th Prìtash 4.6.1 (ii), h opoa den qrhsimopoie to axwma th antallag  . Gia th monadikìthta, èstw ìti A kai B enai anexˆrthta parˆgonta uposÔnola tou K . Ja dexoume ìti A = B . 'Estw tuqao p ∈ A kai B0 elaqistikì uposÔnolo tou B me (A − {p}) ∪ B0 = K (tètoio uposÔnolo upˆrqei diìti (A − {p}) ∪ B = K ). To B0 enai mh kenì afoÔ to A enai anexˆrthto. 'Estw loipìn q ∈ B0 . Jètonta C = (A − {p}) ∪ (B0 − {q}) èqoume C ⊂ K , apì thn kataskeu  tou B0 kai C ∪ {p} = C ∪ {q} = K , opìte

p ∈ C ∪ {q},

q ∈ C ∪ {p}.

Epiplèon p ∈ / C kai q ∈ / C , diìti alli¸ ja eqame A ⊆ C   (A − {p}) ∪ B0 ⊆ C kai epomènw C = K . Apì to axwma (iv′ ) prokÔptei ìti p = q . Sunep¸ kˆje p ∈ A enai stoiqeo tou B , dhlad  A ⊆ B . Omow B ⊆ A. ✷ Sthn apìdeixh tou Jewr mato 4.7.1 ja qrhsimopoi soume thn akìloujh jemeli¸dh arq  aparjmhsh . Prìtash 4.7.2

isqÔei

(Arq  EgkleismoÔ-ApokleismoÔ) Gia peperasmèna sÔnola A1 , A2 , . . . , Ak

#

k [

i=1

Ai =

k X t=1

(−1)t−1

X

#(Ai1 ∩ · · · ∩ Ait ).

1≤i1 k + (#Si − k) (4.14) i∈I

i∈I

gia kˆje sÔnolo deikt¸n I ⊆ [m] me toulˆqiston dÔo stoiqea. Gia S, T ∈ P (n, k) jètoume S  T an kˆje stoiqeo tou S perièqetai se kˆpoio stoiqeo tou T . (a) Dexte ìti gia k = 1 to zeÔgo (P (n, k), ) enai isìmorfo me to sÔndesmo Πn twn diamersewn tou [n]. (b) Dexte ìti to zeÔgo (P (n, k), ) enai gewmetrikì sÔndesmo tˆxh n − k gia kˆje 1 ≤ k < n. 10. 'Estw (P, ≤) peperasmèno merik¸ diatetagmèno sÔnolo. Gia A ⊆ P èstw A to sÔnolo twn stoiqewn p tou P gia ta opoa upˆrqoun a1 , a2 ∈ A me a1 ≤ p ≤ a2 . Dexte ìti h apeikìnish 2P → 2P pou stèlnei to A ⊆ P sto A orzei mia kurt  gewmetra sto P . 11. Gia k ≥ 2 dexte ìti k X i=0

  k (r − i) = 0. (−1) i i

85 Upodexei - LÔsei 1.

H merik 

2.

(a)

[u, v]

An

Q

diˆtaxh

enai

kai

twn

,

kai

sto

sto

.

'Estw

An

.

1.1 apotele parˆdeigma

diˆsthma

sunep¸

x, y ∈ L ⊕ M x∧y = x L⊕M

(b)

Sq mato

kleistì

[u, v] x y

an koun sto antstoiqa,

tou

An

sto

L

sÔndesmo

apoteloÔn to

kai

elˆqisto

sundèsmou me autè

x, y ∈ [u, v]

,

ˆnw

tìte

frˆgma kai

L⊕M

(y, y ′ )

L×M

ParathroÔme ìti gia

4.

sto

(a)

H

NCn

.

To

x∈L x, y

y∈M

kai

ta

an koun

,

x≤y

tìte

kai

ta

dÔo

L×M

Gia thn perptwsh tou

, me thn profan  ènnoia.

x, y ∈ NCn

L⊕M

sto

sto

L

 

kai

kai ta

NCn

⇒

prokÔptei

dÔo

(b)

Lìgw

tou

sto

,

tìte

L∗

x, y

amèsw

L mma

apì

kai

kai ,

af netai ston anagn¸sth.

sto

Πn

, to opoo perigrˆyame

x, y

(ii)

4.1.1

ton

to

(x, x′ ) (x ∧ y, x′ ∧ y ′ )

kai sunep¸ apotele to mègisto kˆtw frˆgma twn

apì to

,

sÔndesmo èqoun thn

(x ∨ y, x′ ∨ y ′ )

H perptwsh tou

.

orismì

th

tstrofo prokÔptei me epagwg  sto pl jo twn stoiqewn tou af nontai ston

x∨y =y M

sunep¸

parathroÔme ìti ta stoiqea

to mègisto kˆtw frˆgma twn

zhtoÔmeno èpetai

sunepagwg 

frˆgma,

.

sto Parˆdeigma 4.1.2, an kei sto kai

x∧y

kai

kˆtw

[u, v]

èqoun kat¸tato ˆnw frˆgma kai an¸tato kˆtw frˆgma

antstoiqa, sto

3.

.

idiìthte .

x∨y

ta

mègisto

kat¸tato ˆnw frˆgma kai to an¸tato kˆtw frˆgma tou ston antstoiqo dia idiìthta sto

ti

asjenoÔ

diˆtaxh

Inv(τ )−Inv(σ)

.

en¸

to

an-

Oi leptomèreie

anagn¸sth.

(a),

th

Ôparxh

mègistou

stoiqeou

gia

thn

asjen 

diˆtaxh

('Askhsh

6

b

tou

x, y ∈ Sn Inv(w) ⊆ Inv(x) ∩ Inv(y) Inv(w) ⊆ A En = {(i, j) : 1 ≤ i < j ≤ n} (i, j), (j, k) ∈ A ⇒ (i, k) ∈ A A ⊆ En z ∈ Sn w ∈ Sn Inv(w) ⊆ A Inv(w) ⊆ Inv(z) ⊆ A Inv(x) ∩ Inv(y) x, y ∈ Sn A ⊆ En z = un u1 , u2 , . . . , un ui ∈ Si 1≤i≤n u1 = (1) 1 < m ≤ n um (a1 , a2 , . . . , am ) ∈ Sm (i) um−1 um m (ii) m = ai i≥2 (ai−1 , m) ∈ / A (iii) m = ai i < m (aj , m) ∈ A j i < j ≤ m n = 6 A = {(1, 2), (1, 6), (3, 4), (3, 5), (3, 6), (4, 5)} u1 = (1) u2 = (2, 1) u3 = (2, 1, 3) u4 = (2, 1, 4, 3) u5 = (2, 1, 5, 4, 3) u6 = (2, 1, 5, 4, 6, 3) Kefalaou

1)

kai

tou

L mmato

z ∈ Sn Inv(z) ⊆ Inv(x) ∩ Inv(y) upˆrqei

tètoio,

.

th

metabatik 

idiìthta

me

thn

th

metabatik 

idiìthta

th

metabatik 

idiìthta,

idiìthta

aut 

pou

h

monadik 

,

ìro

tètoio,

Profan¸

kˆje

sunep¸

sÔnolo

arke

na

ìpou

jètoume

epagwgikˆ

w

,

ex  .

an

kˆje

dexoume

me

Inv(w) ⊆ A

,

na Gia

na

ta

,

dekth

kai

idiìthte

isqÔei

me

isqurismì.

'Eqoume

kˆje

na

morf  ton

gia

me

enai

ti

ìti

èqei

Dosmènou

metajèsei

h

prokÔptei

tìte

kai

.

tìte

,

gia

gia

h

me

me

me

Gia

apì

enai

th

an

parˆdeigma,

an

,

,

.

m Inv(um ) ⊆ A 1 ≤ m ≤ n w ∈ Sm Inv(w) ⊆ Inv(um ) m = n m ≥ 2 um Inv(um ) ⊆ A w ∈ Sm (r, s) ∈ Inv(w) − Inv(um )

epagwg 

ìti

ìla

èqei

kˆje

kai

tìte

upojèsoume

gia

Isqurizìmaste

ta

,

,

gia

th

kai

gia

ex  :

tou

dexoume

me

tìte

to

na isqÔei

¸ste

kai

Ja

dexoume

.

kai

orzontai

ton

na

me

Ja lème ìti èna uposÔnolo

metˆjesh

diagrˆfonta kai

arke

an

upˆrqei .

(ii) w ∈ Sn

4.1.1

¸ste gia kˆje

katal xoume

sto

ìti

gia

.

.

se

Apì

ˆtopo,

thn

èstw

H

perptwsh

kataskeu 

ìti

kai

upˆrqei

tou

dnei

èqoume

kai

to

ìti

an

zhtoÔmeno.

amèsw

kai

MporoÔme

ìti

.

.

Apì

86 s = m um = (a1 , a2 , . . . , am ) m = ai (r, m) ∈ / Inv(um ) i≥2 r = ak k ai−1 (ai−1 , r) ∈ Inv(um ) ⊆ A (r, m) ∈ A A (ai−1 , m) ∈ A r < ai−1 (r, ai−1 ) ∈ / Inv(um−1 ) (r, ai−1 ) ∈ / Inv(w) (r, m) ∈ Inv(w) (ai−1 , m) ∈ Inv(w) (ai−1 , m) ∈ A thn

epagwg 

m

sto

ja

prèpei

.

èqoume

tou

kai

kai

,

,

prˆgma

exaita

Upojètoume ìti to

y

[ˆ0, x]

enai

to

kai

anˆgwgo.

Gia

ˆra

kai

sto

,

èqoume

Dexame dhlad  ìti

den

enai

ìti

dunatì

(dedomènou tou

6.

,

to

enai

na

ìti

anˆgwgo

kalÔptei to

L

diast mato

dÔo

dhlad 

Bn

th

a

kai

arke

na

orsei

kane

metajèsewn tou

Enai

eÔkolo

4.5.1,

ìpou tou

na

S S

,

enai

,

tuqao

enai tou

h

to

to

opìte

zk−1 z ∈ [ˆ0, x] to

.

Epsh gia tuqaa

sunep¸ enai

diìti

megistik 

kalÔptei

,

[ˆ0, y) =

sthn

u ∨ v 6= y

.

anˆgwgo

tìte

perptwsh

aut 

.

gia

.

Gia

thn

asjen 

diˆtaxh

sto

x⊥ =

Oi zhtoÔmene idiìthte prokÔptoun apì thn 'Askhsh

tou

ei − ej to

enai isìmorfo me

dianusmˆtwn

anexˆrthta).

gia

4.5.1,

Rn S

q¸rou

ìpou

to

1≤i