Tvarkos sąryšiai ir dalinai sutvarkytos aibės

Vienas rinkinys gali apimti kitą, nors ne visas poras galima palyginti

Turime du įrankius: raktą, pažymėtą a, ir lempą, pažymėtą b. Galimi rinkiniai yra ∅, {a}, {b} ir {a,b}. Sakykime, kad rinkinys X yra pirmesnis už rinkinį Y, kai kiekvienas X įrankis priklauso ir Y. Tuomet ∅ yra pirmesnis už kiekvieną rinkinį, o abu vieno įrankio rinkiniai yra pirmesni už {a,b}.

Rinkinių {a} ir {b} pagal šią taisyklę palyginti negalima: kiekviename yra įrankis, kurio kitame nėra. Nė vienas nėra pirmesnis už kitą. Vienodas rinkinių dydis nereiškia, kad vienas yra kito poaibis, o jų išdėstymas piešinyje iš kairės į dešinę nenustato tvarkos.

Užrašykime P = {∅, {a}, {b}, {a,b}} ir X ⪯ Y, kai X ⊆ Y. Simbolis ⪯ žymi šią taisyklę; jis nereiškia įprasto skaitinio dydžio. Greta esančioje diagramoje pirmesnis rinkinys vaizduojamas žemiau vėlesnio, ir matomi visi leidžiami rinkiniai.

Prieš nagrinėdami diagramą, perskaitykite apie objektus ir taisyklę

Grįžkite prie paskelbtos pamokos „Simboliai, apibrėžimai ir matematinė kalba“, kad atskirtumėte objektą, jo žymenį ir teiginį apie jį. Grįžkite prie pamokos „Skaičių tiesės, tvarka ir palyginimas“, kad prisimintumėte pažįstamą ≤ pavyzdį, ir prie pamokos „Daugyba ir dalyba“, kad prisimintumėte neneigiamų sveikųjų skaičių kartotinių sampratą, taikomą dalumo pavyzdyje.

Aibių ir sąryšių pamokose poaibiai ir sutvarkytosios poros aptariami išsamiau. Čia X ⊆ Y reiškia, kad kiekvienas X elementas yra Y elementas, o sąryšis aibėje P nurodo, kurios sutvarkytosios poros (x,y), kur x,y ∈ P, tenkina taisyklę. Galite pradėti nuo keturių rinkinių ir baigtinių lentelių, o kai tvirtai suprasite šias sąvokas, grįžti prie įrodymų su kvantoriais.

Skaitydami pirmą kartą, pirmiausia išnagrinėkite palyginamumą, kelius Hasės diagramose ir baigtinių aibių ekstremumus, o tik tada pereikite prie paskutinių atvejų su realiųjų skaičių intervalais ir tuščiuoju poaibiu. Neprivalomame intervalo atvejyje remiamasi paskelbta pamoka „Nelygybės, intervalai ir modulis“. Grįžkite prie jo, kai gebėsite atskirti intervalo galą nuo intervalo elemento.

Trys negriežtosios dalinės tvarkos sąlygos

Negriežtoji dalinė tvarka ⪯ aibėje P yra refleksyvi, antisimetriška ir tranzityvi. Pora (P, ⪯) yra dalinai sutvarkyta aibė. Šios sąlygos taikomos visiems P elementams, o ne tik toms poroms, kurias nubrėžėte.

Refleksyvumas reiškia, kad x ⪯ x kiekvienam x ∈ P. Antisimetriškumas reiškia, kad jei x ⪯ y ir y ⪯ x, tai x = y. Tranzityvumas reiškia, kad jei x ⪯ y ir y ⪯ z, tai x ⪯ z. Implikacija reikalauja, kad jos išvada galiotų tik tada, kai tenkinama visa nurodyta prielaida.

Poaibio įtraukimo sąryšis tenkina šias taisykles. Kiekvienas rinkinys apima visus savo įrankius. Jei X ⊆ Y ir Y ⊆ X, juose yra lygiai tie patys įrankiai, todėl šie rinkiniai yra lygūs. Jei X ⊆ Y ir Y ⊆ Z, kiekvienas X įrankis per Y patenka į Z, todėl X ⊆ Z. Šie argumentai taikomi bet kokioms aibėms, ne tik mūsų keturiems rinkiniams.

Antisimetriškumas leidžia ryšius su savimi

Simetriškumas reiškia, kad iš xRy išplaukia yRx. Antisimetriškumas leidžia ryšius abiem kryptimis tik tada, kai abu elementai yra lygūs. Jis nedraudžia xRx: kiekvienai negriežtajai dalinei tvarkai būtini visi tokie ryšiai su savimi. Asimetriškumas yra kita sąlyga: iš xRy išplaukia, kad yRx yra neteisinga; ji taip pat draudžia ryšius su savimi.

Lygybės sąryšis yra ir simetriškas, ir antisimetriškas. Visų jo porų abu elementai yra lygūs. Kita vertus, sąryšis gali būti nesimetriškas ir kartu nebūti antisimetriškas: trims skirtingiems elementams a,b,c imkime tik poras (a,b), (b,a) ir (a,c). Poros (c,a) nebuvimas paneigia simetriškumą, o poros (a,b) ir (b,a) paneigia antisimetriškumą.

Todėl „nesimetriškas“ nėra antisimetriškumo apibrėžimas. Tiesiogiai patikrinkite implikaciją apie ryšius abiem kryptimis. Refleksyvumas ir antisimetriškumas taip pat negarantuoja tranzityvumo: ryšiai su savimi kartu su poromis (a,b) ir (b,c), bet be poros (a,c), yra kontrpavyzdys su trimis skirtingais elementais.

Vienodai atrodanti taisyklė gali pasikeisti pasikeitus jos apibrėžimo sričiai

Teigiamųjų sveikųjų skaičių aibėje apibrėžkime x ⪯ y pagal dalumą x | y: egzistuoja sveikasis skaičius k, toks, kad y = kx. Kiekvienas x dalija pats save. Jei y = kx ir z = ly, tai z = (lk)x, o tai įrodo tranzityvumą. Jei teigiamieji x, y dalija vienas kitą, jų teigiamųjų sveikųjų daugiklių sandauga yra 1, todėl abu daugikliai yra 1 ir x = y. Taigi dalumas yra dalinė tvarka teigiamųjų sveikųjų skaičių aibėje.

Ši tvarka nėra pilnoji: nei 2 dalija 3, nei 3 dalija 2. Baigtinėje dalinai sutvarkytoje aibėje D = {1,2,3,6,12}, kurioje tvarka apibrėžta pagal dalumą, galioja 2 ⪯ 6 ⪯ 12 ir 3 ⪯ 6, tačiau 2 ir 3 lieka nepalyginami. Šioje tvarkoje didesnis užrašytas skaičius nebūtinai yra aukščiau už kiekvieną mažesnį skaičių.

Visų sveikųjų skaičių aibėje ta pati dalumo taisyklė netenkina antisimetriškumo: 2 dalija −2, o −2 dalija 2, tačiau 2 ≠ −2. Visada kartu nurodykite ir aibę, ir taisyklę. Įprastas sąryšis ≤ sveikųjų skaičių aibėje yra kitas sąryšis ir išlieka pilnąja tvarka.

Pilnojoje tvarkoje kiekviena pora yra palyginama

Dalinai sutvarkytos aibės elementai x, y yra palyginami, kai x ⪯ y arba y ⪯ x. Jie yra nepalyginami, kai negalioja nė vienas iš šių sąryšių. „Arba“ čia nėra išskiriamasis: dėl refleksyvumo elementas yra palyginamas pats su savimi.

Pilnoji, arba tiesinė, tvarka yra dalinė tvarka, kurioje kiekviena elementų pora yra palyginama. Įprastas sąryšis ≤ realiųjų skaičių aibėje yra pilnoji tvarka. Įtraukimo sąryšis keturių rinkinių aibėje yra dalinė, bet ne pilnoji tvarka, nes {a} ir {b} yra nepalyginami. Tvarką vadinant daline, nereikalaujama, kad joje būtų nepalyginama pora: kiekviena pilnoji tvarka taip pat tenkina dalinės tvarkos sąlygas.

Nepalyginamumas nėra lygybė. Jis taip pat nereiškia, kad elementai neturi bendro viršutinio rėžio: {a,b} yra aukščiau už abu vieno įrankio rinkinius. Klausimas „ar šiuos du elementus galima palyginti?“ skiriasi nuo klausimo „ar yra elementas, esantis aukščiau už juos abu?“

Naudodami griežtąją tvarką, sąmoningai atmeskite lygybę

Iš negriežtosios dalinės tvarkos apibrėžkime x ≺ y, kai x ⪯ y ir x ≠ y. Tuomet x ≺ x niekada negalioja: griežtoji tvarka yra antirefleksyvi. Ji yra tranzityvi. Jei x ≺ y ir y ≺ z, iš negriežtosios tvarkos tranzityvumo gauname x ⪯ z; lygybė x = z reikštų, kad y ⪯ x ir x ⪯ y, o tai dėl antisimetriškumo prieštarautų sąlygai x ≠ y. Vadinasi, x ≺ z.

Ir atvirkščiai, griežtoji dalinė tvarka yra antirefleksyvus ir tranzityvus sąryšis ≺. Apibrėžkime x ⪯ y, kai x = y arba x ≺ y. Refleksyvumas išplaukia iš lygybės. Jei du skirtingi elementai būtų susieti abiem kryptimis, gautume x ≺ y ≺ x, o tai prieštarautų antirefleksyvumui. Tikrinant tranzityvumą, lygybės atvejais tiesiog pakeičiamas lygus elementas; kai abu palyginimai griežti, taikomas griežtosios tvarkos tranzityvumas. Taip atkuriama negriežtoji dalinė tvarka.

Griežtoji dalinė tvarka yra asimetriška: iš x ≺ y ir y ≺ x sektų x ≺ x. Žodis „griežtoji“ nereiškia, kad visi elementai tampa palyginami. Griežtojo poaibio įtraukimo sąryšis yra griežtas, tačiau abu vieno įrankio rinkiniai vis tiek nepalyginami. Nurodykite, kuri sutartinė apibrėžtis taikoma, užuot tikrinę < refleksyvumą taip, tarsi tai būtų ≤.

Hasės diagramos briauna žymi dengimą, o ne kiekvieną sąryšiu susietą porą

Kai x ≺ y, sakome, kad y dengia x, jei nėra tokio z ∈ P, kad x ≺ z ≺ y. Baigtinėje Hasės diagramoje kiekvienas toks dengimas vaizduojamas viena briauna, o x yra žemiau už y. Joje nevaizduojamos kilpos ir tiesioginės briaunos, kurių ryšį jau nusako tarpiniai elementai. Nevaizduojami ryšiai vis tiek priklauso negriežtajai tvarkai.

Rinkinių atveju yra keturi dengimai: nuo ∅ iki {a}, nuo ∅ iki {b}, nuo {a} iki {a,b} ir nuo {b} iki {a,b}. Tiesioginės dengimo briaunos nuo ∅ iki {a,b} nėra: abu vieno elemento rinkiniai yra tarpiniai. Vis dėlto ∅ ⪯ {a,b} yra teisinga, kaip rodo abu aukštyn vedantys dviejų briaunų keliai.

Baigtinėje iš dalies sutvarkytoje aibėje x ⪯ y tada ir tik tada, kai x = y arba yra dengimo briaunų kelias, visą laiką vedantis aukštyn nuo x iki y. Baigtinumas leidžia įterpti tarpinius elementus tol, kol kiekvienas likęs žingsnis tampa dengimu. Kelias, kuris kyla aukštyn, o paskui leidžiasi žemyn, neparodo palyginamumo. Aukštis čia žymi tvarkos kryptį, o ne išmatuotą skaitinį atstumą.

Baigtinumo sąlyga svarbi. Aibėje (ℚ, ≤) tarp bet kurių skirtingų x < y yra (x+y)/2, todėl dengimų nėra, nors daugeliui porų galioja griežtosios tvarkos ryšys. Vien dengimo briaunų vaizdas neleistų atkurti šios begalinės tvarkos.

Grandinėje kiekviena pora palyginama, antigrandinėje jokie du skirtingi elementai nepalyginami

Grandinė yra aibės P poaibis C, kurio elementai yra poromis palyginami. Rinkinių atveju {∅, {a}, {a,b}} yra grandinė. Grandinė nebūtinai apima visus P elementus, o išvardytos grandinės gretimi elementai nebūtinai susiję dengimu. Dviejų elementų poaibis {∅, {a,b}} taip pat yra grandinė.

Grandinę sudaro ∅, {a} ir {a,b}; bet kurie du jos elementai yra palyginami. Antigrandinę sudaro {a} ir {b}, kurie yra nepalyginami. Abi yra tos pačios iš keturių rinkinių sudarytos dalinai sutvarkytos aibės poaibiai.

Antigrandinė yra poaibis, kurio bet kurie du skirtingi elementai yra nepalyginami. Poaibis {{a}, {b}} yra antigrandinė. Skirtingumo sąlyga būtina: kiekvienas elementas vis tiek yra palyginamas su savimi. Tuščias poaibis ir vieno elemento poaibis tenkina abu apibrėžimus, nes juose nėra skirtingų elementų poros, kuri galėtų netenkinti kurios nors iš šių sąlygų.

Dviejuose greta esančiuose vaizduose išryškinta grandinė ir antigrandinė toje pačioje iš dalies sutvarkytoje aibėje. Palyginamumą nustatykite pagal aukštyn vedančius kelius, o ne pagal vizualų išsidėstymą. Bet kaip nubraižytoje diagramoje viena mazgų eilė savaime neapibrėžia antigrandinės; ją apibrėžia tvarkos ryšys.

Neturėti nieko žemiau savęs nėra tas pats, kas būti žemiau visų

Poaibio S ⊆ P minimalusis elementas m priklauso S, ir nėra jokio kito S elemento, griežtai mažesnio už m. Maksimalusis elementas priklauso S, ir nėra jokio kito S elemento, griežtai didesnio už jį. Mažiausiasis elementas l priklauso S ir tenkina l ⪯ s kiekvienam s ∈ S; didžiausiasis elementas g priklauso S ir tenkina s ⪯ g kiekvienam s ∈ S.

Visoje šakutės pavidalo dalinai sutvarkytoje aibėje a,b,c minimalieji elementai yra a,b, o didžiausiasis elementas yra c. Mažiausiojo elemento nėra. Pasirinktai porai {a,b} elementas c yra viršutinis rėžis, nepriklausantis šiai porai, o apatinio rėžio nėra.

Sprendžiant šiuos keturis klausimus, aibės P tvarka apribojama poaibiu S. Kai S = {{a}, {b}}, abu elementai yra minimalieji ir maksimalieji, tačiau nė vienas nėra nei mažiausiasis, nei didžiausiasis. Visoje keturių rinkinių aibėje P mažiausiasis elementas yra ∅, o didžiausiasis – {a,b}. Aiškiai nurodę S, nesupainiojame poaibio ekstremaliųjų elementų su visos iš dalies sutvarkytos aibės ekstremaliaisiais elementais.

Trijų elementų iš dalies sutvarkytoje aibėje, kurioje a ≺ c ir b ≺ c, bet a ir b yra nepalyginami, minimalieji elementai yra a,b. Vienintelis maksimalusis elementas c yra ir didžiausiasis. Mažiausiojo elemento nėra. Kiekvienas mažiausiasis elementas yra minimalusis, bet minimalusis elementas nebūtinai yra mažiausiasis; teiginiai apie didžiausiąjį ir maksimalųjį elementus yra dualūs.

Vienatinumui naudokite antisimetriškumą, egzistavimui – baigtinumą

Jei l ir m abu yra mažiausi S elementai, tai l ⪯ m, nes l yra mažiausias, ir m ⪯ l, nes m yra mažiausias. Iš antisimetrinės savybės gauname l = m. Taigi mažiausias elementas, jei jis egzistuoja, yra vienintelis. Apgręžę nelygybes, įrodykite didžiausio elemento vienatinumą. Šis įrodymas neparodo, kad kuris nors iš šių elementų egzistuoja.

Kiekviena netuščia baigtinė aibė S turi minimalų ir maksimalų elementą. Pradėkite nuo bet kurio elemento; jei jis nėra minimalus, pereikite prie griežtai mažesnio S elemento. Leidžiantis žemyn negalima pakartotinai pasiekti to paties elemento, o elementų yra tik baigtinis skaičius, todėl procesas sustoja ties minimaliu elementu. Kylant aukštyn įrodomas teiginys apie maksimalų elementą. Keli elementai, ties kuriais procesas sustoja, gali likti nepalyginami.

Netuščioje baigtinėje dalinai sutvarkytoje aibėje vienintelis minimalus elementas yra mažiausias: kiekvienam x, leidžiantis žemyn tarp elementų, mažesnių už x arba jam lygių, pasiekiamas minimalus visos dalinai sutvarkytos aibės elementas, kuris turi būti tas vienintelis minimalus elementas. Šiai išvadai būtinas baigtinumas. Pavyzdžiui, imkime visus sveikuosius skaičius su įprasta tvarka ir naują elementą a, palyginamą tik su savimi. Tuomet a yra vienintelis minimalus elementas, bet jis nėra mažiausias, nes yra nepalyginamas su kiekvienu sveikuoju skaičiumi.

Jei S yra tuščia, joje nėra elemento, kuris galėtų būti minimalus, maksimalus, mažiausias ar didžiausias. Aibėje (ℤ, ≤) apskritai nėra nei minimalaus, nei maksimalaus elemento: kiekvienam sveikajam skaičiui n egzistuoja n−1 ir n+1. Baigtinė diagrama negali pagrįsti šių išvadų apie elementų egzistavimą begalinėje aibėje.

Rėžis turi priklausyti P, bet nebūtinai S

Tegu S ⊆ P. Viršutinis rėžis u yra aibės P elementas, kuriam s ⪯ u su kiekvienu s ∈ S. Apatinis rėžis l yra aibės P elementas, kuriam l ⪯ s su kiekvienu s ∈ S. Rėžių ieškoma nurodytoje dalinai sutvarkytoje aibėje P, o mažiausias ir didžiausias elementai turi priklausyti pačiai S.

Abiejuose skydeliuose pasirinktas poaibis yra ta pati vieno įrankio rinkinių pora. Visas rinkinys yra jų viršutinis rėžis tik pirmojoje dalinai sutvarkytoje aibėje. Tuščias rinkinys išlieka jų apatiniu rėžiu abiejose.

Keturių rinkinių atveju, kai S = {{a}, {b}}, vienintelis viršutinis rėžis yra {a,b}, o vienintelis apatinis rėžis yra ∅. Nė vienas iš jų nepriklauso S. Dabar pašalinkime {a,b} iš dalinai sutvarkytos aibės, palikdami P′ = {∅, {a}, {b}} su ta pačia įtraukimo tvarka. Ta pati S aibėje P′ neturi viršutinio rėžio, nors {a,b} tebėra visiškai prasminga aibė už P′ ribų.

Aibėje D = {1,2,3,6,12} su dalumo tvarka aibės S = {2,3} viršutiniai rėžiai yra 6,12, o apatinis rėžis yra 1. Jie nustatomi ne vien lyginant skaičių dydį: viršutinis rėžis turi dalytis iš abiejų pasirinktų sveikųjų skaičių. Lentelėje patikrinamas kiekvienas baigtinės aibės D kandidatas.

Geriausias rėžis pats turi būti rėžis

Supremumas, arba mažiausias viršutinis rėžis, supₚ S priklauso P, yra aibės S viršutinis rėžis ir yra mažesnis už kiekvieną S viršutinį rėžį arba jam lygus. Infimumas, arba didžiausias apatinis rėžis, infₚ S priklauso P, yra aibės S apatinis rėžis ir yra didesnis už kiekvieną S apatinį rėžį arba jam lygus. Apatinis indeksas primena, kurioje dalinai sutvarkytoje aibėje ieškoma kandidatų.

Kai S = {p,q}, viršutiniai rėžiai yra u,v, o vienintelis apatinis rėžis – 0. Abu viršutiniai rėžiai yra nepalyginami, todėl nė vienas nėra supremumas. Susikertančių nubrėžtų linijų pora neprideda jokio elemento tarp p,q ir u,v.

Rinkinių atveju supₚ {{a},{b}} = {a,b} ir infₚ {{a},{b}} = ∅. Aibėje D su dalumo tvarka supᴅ {2,3} = 6, nes 6 yra bendras viršutinis rėžis ir dalija kiekvieną kitą viršutinį rėžį aibėje D; infᴅ {2,3} = 1. Supremumas yra mažiausias iš viršutinių rėžių pagal nagrinėjamą tvarką, o ne mažiausia užrašyta žyma ar spėjamas vidurkis.

Viršutiniai rėžiai gali egzistuoti, nors mažiausio iš jų nėra. Nagrinėkime P = {0,p,q,u,v}, kurios griežtosios tvarkos ryšiai yra 0 ≺ p, 0 ≺ q, p ≺ u, p ≺ v, q ≺ u, q ≺ v, o iš tranzityvumo gaunami ryšiai yra 0 ≺ u, 0 ≺ v. Kai S = {p,q}, viršutiniai rėžiai yra u,v. Nė vienas nėra mažesnis už kitą, todėl supremumo nėra. Tai, kad jie yra minimalūs viršutinių rėžių aibėje, nereiškia, kad kuris nors iš jų yra mažiausias tos aibės elementas. Vienintelis apatinis rėžis yra 0, todėl infimumas yra 0.

Jei egzistuotų du supremumai, kiekvienas būtų mažesnis arba lygus kitam, nes abu yra viršutiniai rėžiai; dėl antisimetriškumo jie yra lygūs. Taip pat įrodomas infimumo vienatinumas. Didžiausias S elementas, jei jis egzistuoja, yra jos supremumas aibėje P: jis yra S viršutinis rėžis, o kiekvienas viršutinis rėžis yra didesnis arba lygus jam, nes didžiausiasis S elementas priklauso S. Mažiausiam elementui ir jo infimumui taikomas atvirkštinis samprotavimas.

Tuštieji ir begaliniai poaibiai atskleidžia sąlygas

Kai S = ∅, kiekvienas P elementas yra ir viršutinis, ir apatinis rėžis: nėra nė vieno S elemento, kuris galėtų pažeisti kurią nors iš šių sąlygų. Taigi supₚ ∅ egzistuoja tada ir tik tada, kai P turi mažiausią elementą, ir yra lygus tam mažiausiam elementui. Taip pat infₚ ∅ egzistuoja tada ir tik tada, kai P turi didžiausią elementą, ir yra lygus tam didžiausiam elementui. Jei P yra tuščia, nėra jokio galimo rėžio, todėl nei supremumas, nei infimumas neegzistuoja.

Kai keturių rinkinių iš dalies sutvarkytoje aibėje pasirinktas poaibis yra tuščias, kiekvienas pavaizduotas mazgas turi abu rėžių žymeklius. Mažiausias mazgas ∅ yra šio poaibio supremumas, o didžiausias mazgas {a,b} – jo infimumas. Šie rėžiai yra P elementai, o ne tuščio pasirinkto poaibio nariai.

Keturių rinkinių aibėje P tai duoda supₚ ∅ = ∅, tuščią rinkinį, ir infₚ ∅ = {a,b}, visą rinkinį. Kairėje esantis ∅ žymi tuščią dalinai sutvarkytos aibės poaibį; dešinėje esantis ∅ žymi tuščią rinkinį, kuris yra vienas iš P elementų. Atkreipkite dėmesį, kurio lygmens objektą žymi kiekvienas simbolis.

Neprivalomas realiųjų skaičių intervalo atvejis: aibėje (ℝ, ≤) poaibio S = (0,1) supremumas yra 1, o infimumas – 0, nors nė vienas intervalo galas nepriklauso S. Kiekvienas elementas yra mažesnis už 1. Joks kandidatas u < 1 nėra S viršutinis rėžis: jei u ≤ 0, imkite 1/2; jei 0 < u < 1, imkite (u+1)/2, kuris priklauso S ir yra didesnis už u. Taigi 1 yra viršutinis rėžis, mažesnis arba lygus kiekvienam viršutiniam rėžiui. Samprotavimas apie apatinį rėžį yra dualus: joks l > 0 netinka; kai l ≥ 1, imkite 1/2, o kai 0 < l < 1, imkite l/2.

Tas pats S neturi nei viršutinio, nei apatinio rėžio, kai jį apimanti dalinai sutvarkyta aibė yra ((0,1), ≤): kiekvienas kandidatas priklauso S, ir pačioje S galima rasti geresnį. Tiesinė tvarka nebūtinai turi kiekvieno poaibio supremumą. Atskirai tikrinkite egzistavimą, priklausymą apimančiai dalinai sutvarkytai aibei ir geriausio rėžio palyginimą.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Tarkime, a, b, c yra skirtingi, o sąryšį R sudaro tik (a,b), (b,a), (a,c). Ar R yra simetrinis? Ar jis antisimetrinis? Kiekvieną atsakymą pagrįskite konkrečiu pavyzdžiu.

   Rodyti atsakymą ir paaiškinimą

   R nėra nei simetrinis, nei antisimetrinis.

   Porai (a,c) nėra atvirkštinės poros (c,a), todėl simetriškumo sąlyga netenkinama. Skirtingi elementai a,b susieti abiem kryptimis, todėl antisimetriškumo sąlyga netenkinama. Tai atskiros sąlygos; vienos netenkinimas nereiškia, kad kita tenkinama.

2. Aibėje P = {a,b,c} apibrėžtas sąryšis turi visas poras, kuriose elementas susietas su savimi, ir papildomas poras (a,b),(b,c), bet jokių kitų porų. Ar tai dalinė tvarka?

   Rodyti atsakymą ir paaiškinimą

   Ne. Sąryšis yra refleksyvus ir antisimetriškas, bet ne tranzityvus.

   Pagal tranzityvumo sąlygą iš porų (a,b) ir (b,c) turi išplaukti pora (a,c), tačiau jos nėra. Išvardytos skirtingų elementų poros neturi atvirkštinių porų, todėl antisimetriškumo sąlyga tenkinama. Sąryšio, kuriame trūksta bent vienos pagal tranzityvumą būtinos poros, negalima vadinti daline tvarka.

3. Ar tarp keturių rinkinių galioja ∅ ≺ {a,b}? Ar {a,b} dengia ∅? Paaiškinkite, kodėl atsakymai skiriasi.

   Rodyti atsakymą ir paaiškinimą

   Griežtosios tvarkos palyginimas galioja, tačiau teiginys apie dengimą yra klaidingas.

   Tuščiasis rinkinys yra pilnojo rinkinio tikrasis poaibis. Ir {a}, ir {b} yra tarpiniai rinkiniai, todėl dengimo briauna būtų perteklinė. Griežtosios tvarkos palyginimas leidžia tarpinius elementus, o dengimas – ne.

4. Ar C = {∅,{a,b}} ir A = {{a},{b}} yra grandinės, ar antigrandinės keturių rinkinių dalinai sutvarkytoje aibėje?

   Rodyti atsakymą ir paaiškinimą

   C yra grandinė ir nėra antigrandinė. A yra antigrandinė ir nėra grandinė.

   Tuščiasis rinkinys yra žemiau pilnojo rinkinio, net jei nėra tiesioginės dengimo briaunos. Abu vieno įrankio rinkiniai yra nepalyginami. Grandinę apibrėžia elementų palyginamumas poromis, o ne briaunos buvimas tarp paeiliui pavaizduotų elementų.

5. Aibėje P = {a,b,c}, kurioje a ≺ c, b ≺ c, o a,b yra nepalyginami, raskite visos aibės P minimaliuosius, maksimaliuosius, mažiausiąjį ir didžiausiąjį elementus.

   Rodyti atsakymą ir paaiškinimą

   Minimalieji elementai: a,b. Maksimalusis elementas: c. Mažiausiojo elemento nėra. Didžiausiasis elementas: c.

   Nė vienas P elementas nėra griežtai žemiau a ar b. Nė vienas elementas nėra griežtai aukščiau c, o kiekvienas elementas yra žemiau c arba jam lygus. Nei a, nei b nėra žemiau kito, todėl nė vienas nėra mažiausias; c negali būti mažiausias, nes yra aukščiau abiejų.

6. Aibėje P′ = {∅,{a},{b}}, sutvarkytoje pagal įtrauktį, raskite aibės S = {{a},{b}} apatinius ir viršutinius rėžius ir nustatykite, ar egzistuoja infₚ′ S ir supₚ′ S.

   Rodyti atsakymą ir paaiškinimą

   Apatinių rėžių aibė yra {∅}, o infimumas yra ∅. Viršutinių rėžių nėra, todėl nėra ir supremumo.

   Tuščias įrankių rinkinys yra žemiau abiejų rinkinių, kuriuose yra po vieną įrankį. Nė viena vienaelementė aibė neapima kitos, o visas įrankių rinkinys nėra leistinas P′ elementas. Kandidatas, nepriklausantis nagrinėjamai iš dalies sutvarkytai aibei, negali būti jos rėžis.

7. Kokie yra tuščiojo poaibio viršutiniai ir apatiniai rėžiai iš dalies sutvarkytoje aibėje su penkiomis viršūnėmis 0,p,q,u,v? Kuris iš jų egzistuoja: supremumas ar infimumas?

   Rodyti atsakymą ir paaiškinimą

   Kiekviena viršūnė yra ir viršutinis, ir apatinis rėžis. Tuščiojo poaibio supremumas yra 0, o jo infimumas neegzistuoja.

   Abi rėžių sąlygos formuluojamos visiems pasirinktiems elementams, tačiau nė vienas elementas nepasirinktas. Mažiausias iš dalies sutvarkytos aibės elementas yra 0, todėl jis yra mažiausias iš visų viršutinių rėžių. Didžiausio elemento nėra, nes u ir v yra nepalyginamos maksimalios viršūnės, todėl tuščiasis poaibis neturi didžiausio apatinio rėžio.

8. Tarkime, kad S ⊆ P turi didžiausią elementą g. Įrodykite, kad g yra supₚ S, patikrindami abi apibrėžimo dalis.

   Rodyti atsakymą ir paaiškinimą

   Kiekvienam s ∈ S galioja s ⪯ g, todėl g yra viršutinis rėžis aibėje P. Jei u yra bet kuris S viršutinis rėžis, tai g ⪯ u, nes g ∈ S. Taigi g yra mažiausias iš viršutinių rėžių.

   Antrajame žingsnyje naudojama priklausomybė g ∈ S, o ne vien maksimalumas. Vien maksimalus elementas gali būti nepalyginamas su kitu S elementu ir net nebūti viršutinis rėžis. Antisimetriškumas užtikrina, kad šis supremumas yra vienintelis.

9. Kodėl dalumo sąryšis visų sveikųjų skaičių aibėje nėra dalinė tvarka, nors teigiamų sveikųjų skaičių aibėje jis yra dalinė tvarka?

   Rodyti atsakymą ir paaiškinimą

   Skirtingi sveikieji skaičiai 2 ir −2 dalija vienas kitą, todėl aibėje ℤ pažeidžiamas antisimetriškumas.

   Tiek −2 = (−1)·2, tiek 2 = (−1)·(−2) yra lygybės su sveikaisiais daugikliais. Įrodyme teigiamųjų skaičių srityje teigiamumo sąlyga vertė abu daugiklius būti teigiamus, o jų sandaugą – lygią 1. Atsisakius šios srities sąlygos, išvada apie antisimetriškumą nebegalioja.

Ką verta įsidėmėti

• Dalinai sutvarkyta aibė apibrėžiama nurodant jos elementus ir refleksyvų, antisimetrišką, tranzityvų negriežtąjį sąryšį. Antisimetriškas nereiškia nesimetriškas.
• Pilnoji tvarka leidžia palyginti kiekvieną elementų porą; nepalyginami elementai vis tiek gali turėti bendrų rėžių. Griežtoji tvarka neapima lygybės ir yra irrefleksyvi bei tranzityvi.
• Baigtinė Hasės diagrama vaizduoja dengimo ryšius. Lygybė ir aukštyn einantys keliai leidžia atkurti visą tvarką; aukštis yra tvarkos vaizdavimo susitarimas, o ne skaitinė skalė.
• Grandinėse kiekviena elementų pora yra palyginama; antigrandinėse jokia skirtingų elementų pora nėra palyginama. Ekstremalieji elementai nustatomi nurodytame poaibyje, o rėžių ieškoma jį apimančioje dalinai sutvarkytoje aibėje.
• Minimalusis elementas neturi jokio griežtai mažesnio elemento; mažiausiasis yra mažesnis arba lygus kiekvienam elementui. Mažiausiasis ir didžiausiasis elementai, jei egzistuoja, yra vieninteliai, tačiau jų egzistavimą reikia pagrįsti atskirai.
• Supremumas yra viršutinis rėžis, mažesnis arba lygus kiekvienam viršutiniam rėžiui; infimumas yra apatinis rėžis, didesnis arba lygus kiekvienam apatiniam rėžiui. Prieš teigdami, kad jie egzistuoja, patikrinkite kandidatus, bendrą dalinai sutvarkytą aibę ir tuščiojo poaibio atvejį.