Rendezett pár

A Wikipédiából, a szabad lexikonból.

A rendezett pár a matematika egyik legalapvetőbb fogalma. Két dolog együttesét (párosát) akkor nevezzük rendezett párnak, ha a két dolog sorrendje is lényeges, szemben a rendezetlen párral, amely esetén csak az elemek egy párba tartozása számít; de az nem, hogy melyik az első és melyik a második elem.

Elemek párosa akkor rendezett pár, ha egyik vagy másik elemének, vagy akár mindkettőnek megváltoztatásával a pár is biztosan megváltozik. Világos, hogy egy rendezetlen pár elemeit lehet úgy megváltoztatni, hogy ne változzon a pár, éspedig oly módon, hogy mindkettőt a másikra cseréljük. A rendezett pár tehát tényleg abban különbözik a rendezetlentől, hogy az elemeket kicserélve mást kapunk.

A rendezett párok esetén önkényesen, de konzekvensen rögzítjük, hogy melyik az úgynevezett „első” és a „második” elem (lásd a konkrét példáknál). Két (nem feltétlenül különböző) elemből álló rendezett párra tehát akkor hivatkozunk egyértelműen, ha azt mondjuk: az "a" mint első elem és a "b" mint második elem alkotta rendezett pár.

Bár leggyakrabban matematikai objektumokból képezünk rendezett párokat, de a fogalmat alkalmazza az analitikus filozófiai is, mely különösen fontosnak tartja a matematikai eredmények felhasználását.

A „rendezett pár” nagyon alapvető fogalom, de nem alapfogalom a matematikában: lehetséges (többféle módon is) halmazelméleti eszközökkel meghatározni.

Tartalomjegyzék 1 Matematikai definíció 2 A fogalom filozófiai eredete 3 Formális-axiomatikus elmélet és szemantika 4 Halmazelméleti modellek 4.1 A „standard modell” 4.2 Más elképzelhető definíciók-modellek 4.3 Alkalmatlan „modell” 5 Osztályelméleti modell 6 Problémák a halmazelméleti modell(ekk)el 7 Általánosítások és változatok 8 Rendezett párok, mint kombinatorikai szituációk modelljei 9 Hivatkozások 9.1 Irodalom 10 Külső hivatkozások

[szerkesztés] Matematikai definíció

Ugyan több tárgyalás így utal rá, de nem szokás a rendezett pár fogalmát alapfogalomnak tekinteni, Norbert Wiener, Kazimierz Kuratowski és mások (ld. lentebb) kutatásai nyomán ugyanis egyértelművé vált, hogy a (sztenderd) halmazelmélet eszközeivel is könnyen definiálható olyan halmaz, mely nagyjából olyan tulajdonságokkal rendelkezik, mint amilyeneket intuitíve a rendezett pár fogalmától elvárnánk. Konkrétan, a H halmazból, mint első elemből és a K halmazból, mint második elemből álló rendezett pár olyan halmazként definiálható, amely megváltozik, akár az elemeiket, akár ezek „sorrendjét” cseréljük meg. Példa egy így definiálható halmazra (a matematikában leggyakrabban ezt értik rendezett pár alatt, így szokásos az alábbit sztenderd modellnek is nevezni).

A rendezett pár sztenderd definíciója - A H halmazból mint első elemből és a K halmazból mint második elemből képezett rendezett pár a

halmaz, melynek jelölése:

Gyakran használják a (H,K) jelölést is, de kisbetűkkel jelölt objektumok rendezett párjának jele ekkor összetéveszthető sok más, például a nyílt intervallumra használt (a,b) jelöléssel. H-t néha első, K-t második komponensnek nevezik.

Az iménti halmazelméleti konstrukció - lényegében egy rendezetlen pár - lehetőségét és létezését a sztenderd axiomatikus halmazelméletben a páraxióma biztosítja.

Már csak azt kell belátni, hogy a definíció jó, azaz az így meghatározott rendezett pár tényleg megfelel a bevezetőben leírt követelménynek, vagyis akár az egyik, akár a másik elemének, vagy akár mindkettőnek megváltoztatásával a pár is biztosan megváltozik. Ezt formálisan a következőképpen fogalmazhatjuk meg. Tetszőleges H, K, H' , K' halmazokra:

akkor és csak akkor, ha és

Ezt nevezzük a rendezett párok karakterisztikus tulajdonságának. Ebből következik az a múlhatatlanul fontos tény, hogy ha H és K különböző halmazok, akkor

tehát az elemek sorrendje számít. A bizonyítást lásd lentebb.

[szerkesztés] A fogalom filozófiai eredete

A rendezett pár fogalmának szükségességét például a logikai grammatika eszközeivel mutathatjuk be. Tekintsük a következő kétváltozós predikátumot:

'...₍₁₎ férje ...₍₂₎.'

A kipontozott helyekre tetszőleges neveket írhatunk, ráadásul akár különbözőket is (ezt jelzik az alsó indexek). Azonban nem feltétlenül azonos jelentésű mondatokat kapunk, ha a két helyre más-más sorrendbe helyettesítünk be neveket. Például az

' Amália férje Béla '

mondat egészen mást jelenthet, mint a

' Béla férje Amália '

(feltéve, hogy Amália és Béla két különböző személy). Feltehetjük a kérdést mi a fenti predikátum igazságtartománya, azaz mely párokat behelyettesítve lesz igaz a predikátum. Nyilvánvaló azonban, hogy fontos, hogy egy pár elemeit melyik változó helyére helyettesítünk. Olyan párfogalmat kell választanunk, ahol az < Amália, Béla > pár más, mint a < Béla, Amália > pár (feltéve, hogy Amália és Béla két különböző személy). Ez megvalósul, ha megköveteljük a rendezett pár fogalmától a bevezetőben leírt tulajdonságot.

Megjegyezzük, hogy rendkívül fontos, hogy a halmazelméletben definiálhatók a rendezett párok, amennyiben a formális nyelvek terminusainak referenciáit halmazelméleti modellekben kívánjuk megadni. Ekkor a kétváltozós predikátumok halmazelméleti referenciái halmazelméleti függvények, igazságtartományaiknak elemei rendezett párok lesznek. A rendezett párok ontológiája tehát tisztázódik, ha a "halmazok világát" tekintjük a formális elméletek hátterének. Ellenben kérdéses, hogy létezik-e az Amáliából (mint valóságos emberből) és Bélából (mint valóságos emberből) képezett rendezett pár, és ha igen milyen természetű objektum ez.

[szerkesztés] Formális-axiomatikus elmélet és szemantika

Egy adott L formális nyelvre alapuló T elméletben definiálható a „rendezett pár” fogalom, ha van olyan

op(x,y)

kétváltozós kifejezés (term, melyben az x és y változó szabadon szerepel) melyre a következő formula (karakterikus tulajdonság) tétel:

(∀ x)(∀ y)(∀ u)(∀ v)( op(x,y)=op(u,v) ⇒ (x=u & y=v) )

Ekkor tetszőleges T és S termekre az op(T,S) term rendezett pár. Ha C(x) olyan egyváltozós kifejezés, melyre tétel az alábbi formula:

(∀ x)(∀ y)( C(op(x,y))=x ∨ C(op(x,y))=y) & ( C(op(x,y))=C(op(y,x)) ⇒ (op(x,y)=op(y,x)) )

akkor C-t „komponens-kiválasztó” függvénynek nevezzük. A C( op(T,S) ) termet az op(T,S) rendezett pár első komponensének nevezzük, a T és S közül az ezzel nem egyenlőt (ha van ilyen) második komponensnek (ha nincs, akkor a második komponens is C( op(T,S)) ). Az op(T,S) első komponensét gyakran az op(T,S) első projekciójának is nevezik és π₁(op(T,S))-sel is jelölik, a második komponenst pedig második projekciónak és π₂(op(T,S))-sel is jelölik. Érdemes <T,S> -sel jelölni azt az op(T,S) rendezett párt, melyre

és

teljesül, tehát ha u rendezett pár, akkor

Ez azt jelenti, hogy a <T,S> jelölésben tényleg a tipográfiailag előbb lévő (T) term az első elem és a későbbi (S) a második elem, ellenben a fenti (kissé bonyolult) bevezetés jótékony hatására nem attól első az első elem, hogy a nyomtatott szövegben előrébb van, vagyis matematikai kritérium van a komponensek szétválasztására.

Megjegyezzük, hogy C( op(T,S) ) nem feltétlenül ugyanaz a term mint T vagy S, de egyenlő valamelyikükkel. Például az op( 4 , 2² ) rendezett pár komponensei nem biztos, hogy grafikusan azonosak 4-gyel vagy 2²-vel, de egyenlők egymással és 4-gyel is illetve 2²-vel is (feltéve, hogy 4 és 2² kifejezhetők és az aritmetika tételei igazolhatók az adott elméletben).

Példa. A halmazelméletben op(x,y)-nak alkalmas az {{x},{x,y}} term és C( {{x},{x,y}} )-nek az "{{x},{x,y}} nem kételemű elemének eleme" kifejezés (mely egyértelműen létezik).

Axiomatikus bevezetés. Eszerint, ha a T elméletetben választunk egy, a fenti tulajdonsággal rendelkező kétváltozós op(x,y) kifejezést és a hozzá tartozó egyváltozós C(x) kifejezést, akkor a rendezett pár L nyelv feletti, T elméletbeli fogalmához jutunk. Ekkor az op(x,y) alakú termek lesznek az elméletben a rendezett párok, vagy másként fogalmazva azok a termek, melyek szándékolt módon „rendezett párokat jelölnek”.

Szemantika. Ha a T elméletnek van modellje, akkor op és C is megfelelően interpretálható, azaz az op(x,y) alakú termeknek megfelelnek bizonyos objektumok az individuumtartományon belül. Például, ha a halmazelméleti modell alaphalmaza az A halmaz, akkor az interpretáció kijelöl minden op(x,y)-nek egy olyan A-beli elemet, melyet op(x,y) jelöl. Ekkor A ezen elemei a rendezett párok, illetve a nyelvbéli „rendezett pár termek” (op(x,y)-ok) jelöletei. Adott esetben ezek semmilyen kapcsolatban nincsenek az {{x},{x,y}} vagy hasonló halmazelméleti objektumokkal.

Megjegyzés. Az op(x,y) -ok jelöletének halmazelméleti biztosításakor (modell megadásakor) ugynaz az „önhivatkozási probléma” lép föl, mint minden halmazelméleti modellnél. Egyrészt a halmazelmélet {{x},{x,y}} termjei a Set formális nyelvben, azaz a halmazelmélet formális nyelvében alkalmasak rendezett párnak (op(x,y)-nak), ezek tehát, ha abban állapodunk meg „rendezett pár termek”. Másrészt egy másik T formális elméletben Set halmazai az interpretáció szerepét játsszák, azaz itt a halmazokat nem termként, hanem objektumként, illetve individuumként kell kezelnünk. A konfliktus feloldására két megoldás kínálkozik. 1) Platonista: léteznek a matematikai objektumok (individuumok, azaz halmazok), de nem tudjuk, hogy mik azok. 2) Formalista: csak formális nyelvek léteznek, és ezek tulajdonságain keresztül érhetjük el a matematikai objektumok lehetséges/feltételes világát. Ez utóbbi esetben érvényes Skolem azon kijelentése, hogy a halmazelméleti fogalmak egyfajta relativitással rendelkeznek, a halmazelmélet nem jelöl ki egyértelműen egy világot, a szándékolt modellt (talán ez az elvárás naiv is, nem is tudna kijelölni ilyen modellt).

[szerkesztés] Halmazelméleti modellek

Többféle halmazelméleti modellt, definíciót is lehet találni a rendezett párokra, mely a rendezett párt speciális halmaznak fogja fel. A fő követelmény az, hogy ezek eleget tegyenek a fent leírt (<a,b> = <c,d> ⇔ (a = c)∧(b = d)) ekvivalenciának.

A leggyakoribb és legelfogadottabb modell definíciója a következő:

[szerkesztés] A „standard modell”

Ezt K. Kuratowski vezette be 1921-ben, és több szempontból is a legszerencsésebben használható modellnek bizonyult:

Tehát egy rendezett pár egy speciális alakú rendezetlen pár (bármilyen furcsán is hangzik), melynek egyik eleme a rendezett pár első tagját tartalmazó egyelemű halmaz (ez maga is rendezetlen pár mellesleg, csak két eleme ugyanaz), míg másik eleme a rendezett pár mindkét tagját tartalmazó halmaz (ez is egy rendezetlen pár). Ennek a párnak a képzéséhez természetesen fel kell használni a páraxiómát.

Ellenőrizhető, hogy ez eleget tesz a cikk elején említett ekvivalenciának. Ezt egyszerű esetszétválasztásos bizonyítással lehet belátni: legyen

<a,b> = <c,d> ,

azaz a Kuratowski-modell szerint:

{ {a}, {a,b} } = { {c}, {c,d} } ;

ami a rendezetlen pár definíciója alapján azt jelenti, hogy az elemek párba állíthatóak úgy, hogy páronként megegyezzenek. Eszerint

vagy {a} = {c}, vagy {a} = {c,d}      (I.)

kell hogy teljesüljön (mindkettő is teljesülhet).

1. ha {a} = {c}, az egyelemű halmaz definíciója szerint rögtön a = c . Felmerül a kérdés, hogy mivel egyenlő ekkor {a,b}: a {c} = {a}-val, vagy a {c,d} = {a,d}-vel.
   1. Az első esetben {a,b} = {a}. Ez csakis úgy lehetséges, ha az a elem egyenlő az összes {a,b}-beli elemmel, azaz a = b. Ez esetben már tudtuk (ld. aláhúzás), hogy a=c, most már azt is tudjuk, hogy a = b. Tehát érvényes { {a}, {a,a} } = { {a}, {a,d} } azaz (tekintetbe véve, hogy „halmazban elem csak egyszer fordulhat elő”, azaz {a,a} = {a} ): { {a}, {a,a} } = { {a}, {a} } = { {a} } = { {a}, {a,d} }. Innen {a} = {a,d}, és az előzőekhez hasonló indoklással ekkor a = d. Tehát a = b = c = d, és így a = c és b = d kétségkívül teljesül.
   2. A második esetben {a,b} = {a,d}, és ekkor b egyenlő kell hogy legyen a rendezetlen pár definíciója szerint {a,d} egyik elemével. Ha ez a b az a-val egyenlő, azaz b = a = c, ekkor ugyanazzal a gondolatmenettel, mint az előző bekezdésben, kijön a = b = c = d, és így a tétel is. Hiszen { {a}, {a,b} } = { {a}, {a,a} } = { {a} } = { {c}, {c,d} } = { {a}, {a,d} }, és ekkor {a} = {a,d} miatt a = d. Ha meg ez a b a d-vel egyenlő, akkor az aláhúzás szerint a = c, most meg már azt is tudjuk, b = d, és pontosan ezt kellett bizonyítani.
2. A másik lehetőség (I.) szerint, hogy {a} = {c,d} . Ekkor a = c és a = d azonnal jön; tehát { {a}, {a,b} } = { {c}, {c,d} } = { {a}, {a,a} } = (a már unalomig ismert gondolatmenet szerint) = { {a}, {a} } = { {a} }, és innen szükségképp {a} = {a,b} és innen meg szükségképp a = b, tehát összességében a = b = c = d, és ekkor is igaz a (*) tétel.
3. QED.

A bizonyításhoz kizárólag a rendezetlen pár definícióját és az egyenlőségre vonatkozó axiómákat (tranzitivitás és szimmetria) kellett alkalmazni.

[szerkesztés] Más elképzelhető definíciók-modellek

1. „rsm” a „reverz standard modell” kifejezés rövidítése

2. „em” az „egyszerű modell” rövidítése;

3. „rem” a „reverz egyszerű modell” rövidítése,

4. , ahol x y olyan elemek, amelyek nem fordulnak elő az a-k vagy a b-k között; „hm” a „Hausdorff-modell” rövidítése. (F. Hausdorff, 1914)

5. , ahol 0 olyan elem, ami nem fordul elő az a-k vagy a b-k között; „wm” a „Wiener-modell” rövidítése. (N. Wiener, 1913; ld. [1] )

A „reverz” standard modellnek semmi előnye vagy hátránya nincs a Kuratowski-modellhez képest. Általában a fenti modelleknél maradva, a „reverz” modell alkalmazása semmilyen matematikai (vagy filozófiai) előnnyel vagy hátránnyal nem jár a megfelelő „nem-reverz” modellhez képest.

Norbert Wiener hívta fel a figyelmet a rendezettpár-fogalom halmazelméleti meghatározhatóságára (ld. 5. modell), 1913-14 között írt cikkeiben (pl.: A relációk logikájának egyszerűsítése).

[szerkesztés] Alkalmatlan „modell”

A halmazelméleti keretben egyszerűen kínálkozó,

definíció nem modellje a rendezett párságnak, mert lehet ellenpéldát találni, hogy két ilyen objektum egyenlő akkor is, ha tagjaik páronként különböznek. Például ha a = {x} és b = y, továbbá c = {y}   és   d = x, akkor = = = annak ellenére, hogy nem feltétlenül teljesül {x} = {y} és y = x. Például ha x = 1-et és y = 2-t választunk, vagy bármilyen olyan x,y objektumokat, melyekre x≠y.

[szerkesztés] Osztályelméleti modell

A Kuratowski-féle definíció sajnos nem működik olyankor, amikor nem halmazok, hanem valódi osztályok párjait próbáljuk képezni. Ez amiatt van, hogy valódi osztály nem lehet eleme osztálynak, holott több olyan alkalmazás van, például a kategóriaelméletben, ahol szükség lenne valódi osztályokból álló rendezett párra. Anthony P. Morse volt az, aki először definiálta az osztálypárt. Eszerint ha x és y két osztály, akkor ezek rendezett párja az (x,y)=(x × {0}) ∪ (y × {1}) osztály. A definícióban természetesen hamazok párjaként kell gondolni a Descartes-szorzat elemeire és 0 és 1 is a szokásos halmazelméleti objektum.

[szerkesztés] Problémák a halmazelméleti modell(ekk)el

[szerkesztés] Általánosítások és változatok

• rendezett n-es
• elemrendszer (Dedekind?)
• sorozat

[szerkesztés] Rendezett párok, mint kombinatorikai szituációk modelljei

A kombinatorika és a kombinatorikus valószínűségelmélet alkalmazásszerű problémáiban általában egy n elemű alaphalmazból kell kiválasztani adott tulajdonságú elmeket k-asát és ezek számát megmondani. A k-asok a szövegkörnyezettől függően tartalmazhatnak ismétlődést, vagy számíthat a sorrendjük. Azt, hogy az adott feladatban milyen típusú k-asokat választunk, sokszor csak rajtunk múlik, a nem matematikai feladatra (életből vett példára) mi alkothatunk matematikai modellt. Nézzünk két példát.

Feladat. Jól megkevert 52 lapos francia kártyából kiveszünk 3 kártyát. Hány különböző lapkiosztást tarthatunk a kezünkben, melyben pontosan egy király található?

Megoldás. A legelső megállapításunk, hogy a feladat alapján a kártyalapokat visszatevés nélkül húzzuk (mind különböző) és sorrendjük nem számít, csak az, hogy melyek vannak a kezünkben. (Elvileg a feladat szövege mást is megengedne, de maradjunk ennél. Ha a szöveget ennél egyértelműbben fogalmaznánk, akkor nem lenne életszerű, de kétségtelenül félreérthetetlen lenne. Azt is megjegyezzük, hogy a szövegértelmezés, a modellalkotás és a pontos kérdésfeltétel nem tisztán matematikai tevékenysége után a feladat matematikai szempontból triviális, adott esetben persze lehetne ezután is nemtriviális kombinatorikai probléma.)

1) Rendezetlen hármasokkal. Olyan rendezetlen, ismétlődéseket nem tartalmazó {A,B,K} laphármasokat kell keresnünk, melyben pontosan 1 király van. Legyen H mind az 52 kártyalap halmaza. Először kiválasztjuk azt az 1 darab K királyt a {♠K, ♥K, ♦K, ♣K} halmazból, mely a kezünkben lesz. Ezt

féle képpen tehetjük (ennyi 1 elemű részhalmaza van {♠K, ♥K, ♦K, ♣K}-nak). Ezután ki kell választanunk a másik 2 tetszőleges "nemkirályt", a maradék H \ {♠K, ♥K, ♦K, ♣K} halmazból, melyet

féle képpen tehetünk (ennyi 2 elemű részhalmaza van H \ {♠K, ♥K, ♦K, ♣K}-nak). Mivel ezeket egymástól függetlenül tehetjük, ezért az eredmény ezeknek a szorzata:

2) Akinek az előző megoldásnem meggyőző, annak másik modellt ajánlunk. Először kiszámoljuk, hogy olyan rendezett (A,B,C) hármasból, melyben pontosan egy király van mennyi van, majd (tekintve, hogy a sorrend nem számít) elosztjuk a 3!-sal, hiszen minden esetet ennyiszer többször számoltunk. A K király lehet az első, a második és a harmadik helyen: (K, ... , ... ), (... , K , ... ), (... , ... , K ) – figyeljünk arra, hogy most (..., ..., ...) rendezett hármast jelöl. Mindhárom esetben a királyt 4 féle képpen választhatjuk, a másik kettőt a maradékból 48 majd 47 féle képpen. Tehát a H × H × H Descartes-szorzatnak 44847 + 44847 + 44847 elemű részhalmazát jelöltük ki. A rendezetlenségből adódó ismétlődésektől megszabadulva szintén

a végeredmény.

Feladat. András és Béla egymástól függetlenül hazudik, vagy mond igazat, rendre 2/3 és 1/3 valószínűséggel. Feltéve, hogy András azt állítja, hogy Béla hazudik, mi a valószínűsége, hogy Béla igazat mond?

Megoldás. Jelölje az (a,b) pár, azt, hogy András mondata a = igaz vagy hamis illetve Béla mondata b = igaz vagy hamis. Eszerint az elemi események halmaza a következő rendezett párokból álló halmaz: {(i,i), (i,h), (h,i), (h,h)} Legyen B az az esemény, hogy Béla igazat mond, A az, hogy András szerint Béla hazudik. Ez azt jelenti, hogy B={(h,i),(i,i)}, és A={(h,i), (i,h)}. Kell a P(B|A) feltételes valószínűség. Definíció alapján ez:

[szerkesztés] Hivatkozások

[szerkesztés] Irodalom

• Komjáth Péter: A matematika alapjai I. Halmazelmélet. PDF.
• Császár Ákos: Valós Analízis I.-II. Nemzeti Tankönyvkiadó, Bp., 1999. ISBN 963-19-0113-0 (I. kötet); ISBN 963-19-0114-9 (II. kötet); ISBN 963-19-0115-7 (összkiadás).
• Ruzsa Imre: Logikai szintaxis és szemantika I-II., Akadémiai Kiadó, Bp., 1988. ISBN 963-05-4720-1 (I. kötet).; ISBN 963-05-4719 (összkiadás).

[szerkesztés] Külső hivatkozások

• Sulinet-oldal: a rendezett párok és a Descartes-koordinátarendszer.
• Three questions about the initial concepts of Mathematics (A matematika felépítése a rendezetlen és rendezett párok által - részletes elemzés) (angolul) PDF