Ordenaren teoria

Ordenaren teoria matematikaren adar bat da, matematikaren ordenaren nozio intuitiboa antzematen duten erlazio bitarren mota batzuk aztertzen dituena. Artikulu honetan zehar, hainbat definizio emango dira eta adar honetako sarrera zahatza ematen du.^[1]

Atzealdea eta motibazioa[aldatu | aldatu iturburu kodea]

Ordena beti presente dago, bereziki, matematikari eta informatikari buruz hitz egiten dugunean. Normalean lehenik ikusten eta aztertzen den ordena, lehen hezkuntzatik ikasten dena, zenbaki arrunten >, <, ≥ eta ≤ dira. Geroago, kontzeptu hau beste zenbakien multzoetara hedatu da, hala nola, zenbaki osoen eta errealen multzoetara. Izan ere, zenbaki bat beste bat baino handiagoa edo txikiagoa izatearen ideia da, oro har, zenbaki-sistema gehienen oinarrizko intuizioetako bat (normalean bi zenbakien arteko diferentzia erreala jakitean ere interesatzen dira, eta hau ez dago ordenean zehaztuta). Beste ordena zabaldu eta arrunt bat hiztegiko hitzen orden lexikografikoa da.

Lehen aipatutako ordena motak, badute ezaugarri berezi bat: elementu bakoitza beste edozeinekin konpara daitekeela, hau da, handiagoa, txikiagoa edo berdina izan daitekeela. Baina hau ez da beti baliagarria izaten. Adibidez, multzo baten azpimultzoen ordenari erreparatuz; multzo batek beste baten elementu berdinak baditu, handiagoa edo berdina dela esan dezakegu. Baina badaude honela konparatu ezin daitezkeen multzoak ere, izan ere, multzo batean egon daiteke bestean ez dagoen elementuren bat. Beraz, azpimultzoen inkluzioak ordena partziala da, lehen emandako ordena totalekin alderatuta.

Ordenen erabilera praktiko zabalak bultzatuta, multzo ordenatuen klase berezi ugari defini daitezke, horietako batzuk gainera berez eremu matematiko izatera iritsi dira. Gainera, ordenaren teoría ez da ordena-erlazio mota ezberdinetara mugatzen, baizik eta horien arteko funtzio egokiak ere kontuan hartzen ditu. Ordena teorikoaren propietate baten adibide sinple bat analisitik dator, non maíz funtzio monotonoak aurkitzen ditugun.

Definizio basikoak[aldatu | aldatu iturburu kodea]

Atal honeta zehar, multzo ordenatuen munduan sartzeko lehen gida bat emango da. Multzoen teoría eta aritmetika oinarrizko ezagutza dituen eta erlazio bitar bat zer den dakien irakurleari zuzenduta dago batez ere, baina orain arte ordenari buruzko gogoeta teorikoa egiteari ohituta ez dagoenari.

Partzialki Ordenatutako Multzoak[aldatu | aldatu iturburu kodea]

Lehen esan bezala, ordena erlazio bitar berezia da. Horregatik, P multzoa eta ≥ erlazioa bitarra hartuz, orduan ≥ ordena partziala da erreflexiboa, antisimetrikoa eta trantsitiboa bada, hau da, hiru propietate hauek betetzen baditu:

a ≥ a (erreflexiboa)
Baldin eta a ≥ b eta b ≥ c bada ⇒ a ≥ c da (trantsitiboa)
Baldin eta a ≥ b eta b ≥ a bada ⇒ a = b da (antisimetrikoa)

Ordena partziala duten multzoei, partzialki ordenatutako multzoak deritze, edo, laburrago esanda poset (Partially Ordered Set). Multzo ordenatu terminoa batzuetan ere poset-etarako erabiltzen da, beti ere argi geratzen denean beste ordena motei buruz hitz egiten ez duela. Propietate hau konprobatuz, argi eta garbi ikusten da hain ezagunak diren naturalen, osoen, arrazionalen eta errealen ordenak zentzu horretan ordenatuta daudela. Hala ere, badute beste propietate gehigarri bat, totala. Hau da, X-en barne diren edozein a eta b-rentzat: a ≤ b eta b ≥ a. Ordena honi ere ordena lineala edo katea dei ahal zaio. Nahiz eta ordena klasiko asko linealak diren, multzo baten azpimultzoen arteko ordenak hori betetzen ez den adibide dira. Izan ere, posets-en propietate aurreratu asko interesgarriak dira batez ere ordena ez-lineal baterako.

Ordenen arteko funtzioak[aldatu | aldatu iturburu kodea]

Zentzuzkoa da partzialki ordenatutako multzoek zenbait propietate gehigarri izatea eskatzea, bi multzoen ordena-erlazioarekin erlazionatuta egotea. Testuinguru horretan, monotonia da baldintzarik funtsezkoena. P poset-tik Q-ra doan f funtzioa monotonoa da edo ordena zaintzailea baldin eta a ≤ b bada P-n eta inplikatzen badu f(a) ≤ f(b) izatea Q-n. Inplikazio horren hizketak ordena islatzailea den funtzio batera eramaten gaitu, hau da, f funtzio batera zeinetan f(a) ≤ f(b) izateak inplikatzen duen a ≤ b. Bestalde, funtzio bat inbertitzailea edo antitona ere izan daiteke, baldin eta a ≤ b izanda f(a) ≥ f(b) inplikatzen badu.

Beste funtzio bat murgiltze ordena da, ordena zaintzailea eta islatzailea dena. Definizio horretarako adibideak erraz aurkitzen dira. Adibidez, zenbaki natural bat bere ondorengoan esleitzen duen funtzioa argi eta garbi monotonoa da ordena naturalarekiko. Ordena diskretu baten edozein funtzio, hau da, “=” identitate-ordenaren arabera ordenatutako multzo bat ere monotonoa da. Zenbaki natural bakoitza dagokion zenbaki errealari esleitzeak adibide bat ematen du ordena murgiltze baterako.

Ordena isomorfismoa, funtzio bijektibo bat monotono inbersoa denean da. Hau ordena murgiltzaile supraiektibo baten antzekoa da. Horregatik, ordena murgiltze batean f(P) beti izango da P-ren isomorfoa.

Beste funtzio mota landuago bat Galois-en konexioa da. Konexio hauek monotonoak dira eta alderantzizko norabideko bi funtziok osatzen dituztenez, ordena isomorfismoen orokortze gisa ikus daiteke. Alderantzizko bi funtzio hauek ez dira bata bestearen alderantzizko absolutuak, baina badute harreman oso hurbila.

Ordena-harreman hutsarekin bateragarria izateaz gain, posets-en arteko funtzio bat ondo porta daiteke elementu bereziei eta eraikuntzei dagokionez. Adibidez, elementu txikiagoko posets-ez hitz egitean, arrazoikoa dirudi elementu jori babesten duen funtzio monotoniko bat soilik kontuan hartzea, hau da, elementu txikiago bat txertatzea. ^ Bitar minimoa existitxen bada, orduan arrazoizko propietate bat izan daiteke eskatzea f(x ^y) = f(x) ^ f(y), x eta y guztietarako. Propietate guzti horiek, eta are gehiago, muga gordetzen duen funtzio etiketaren barnean taldeka daitezke.

Azkenik, ikuspuntua alda dezakegu, funtzio-ordenetatik funtzioen ordenera. Izan ere, bi posets-en arteko funtzioak, P eta Q, puntuz puntu ordenatu daitezke. f eta g bi funtzioetarako, f ≤ g izango da baldin eta Pren edozein x elementurako f(x) ≤ g(x) bada.