Szerkesztő:Gubbubu/Halmazelmélet/Konnekció, operáció

• Témák jegyzéke
• Előző fejezet (Párok)
• Következő fejezet (Osztályműveletek)

E fejezetben a reláció és függvény fogalmak osztályelméleti megfelelőit definiáljuk.

Konnekció

A konnekció definíciója

Definíció: Egy olyan osztályt, amelynek minden eleme rendezett pár, konnekciónak (hosszabb kifejezéssel, osztályokra általánosított bináris relációnak vagy másodrendű relációnak) nevezünk.

Sajnos - akárcsak egy valódi osztály részhalmazainak sokasága, az osztálycsaládok sokasága, vagy az összes osztály sokasága - az osztályelméletben ez nem formalizálható fogalom . Ezért alapfogalomnak tekintjük Egyébként ugyanazt a halmazelméletet kapjuk, ha speciális esetét, az operáció fogalmát tekintenénk alapfogalomnak (ahogy Hajnal és Hamburger, vagy Komjáth teszik idézett munkáikban) .

Definíció: Ha κ egy konnekció, és x,y∈U olyanok, hogy

<x,y>∈κ,

akkor ehelyett szokásosan azt is írjuk,

xκy,

és azt mondjuk, az x és y individuumok a κ konnekcióban vannak egymással. Ez csak egy másféle írásmód, amit infix írás- v. jelölésmódnak nevezünk.

Alaposztály és képosztály

A konnekciók "kétdimenziós" valamik, akárcsak elemeik, a rendezett párok.

Definíció:

1. Egy κ konnekció alaposztálya vagy alaptartománya az elemei első koordinátái osztálya (ha ez létezik). Jele D(κ).
2. Egy κ konnekció képosztálya vagy képtartománya az elemei második koordinátáinak halmaza (ha ez létezik). Jele R(κ).

Ez szóban világos. Egy konnekció rendezett párok osztálya, tehát elemeinek van első és második koordinátája is, és ha ezek osztályokat alkotnak, akkor képezhetőek ezen osztályok. Formálisan mindez így néz ki :

D(κ) := {x | (∃y∈U)<x,y>∈κ}

R(κ) := {y | (∃x∈U)<x,y>∈κ}

A formális felírásból következően egyébként egy konnekciónak mindig van alap-és képtartománya, ez a részhalmaz-axióma erős alakjából következik.

Balról és jobbról egyértelmű konnekciók

Definíció: Legyen κ konnekció. Ezt balról egyértelműnek (jobbra egyértelműnek vagy alulról egyértelműnek) nevezzük, ha bármilyen dolog legfeljebb egyszer szerepel κ-ban második koordinátaként, azaz

(∀x): ( [(∃y,z):(<x,y>∈κ ∧ <x,z>∈κ) ⇒ y=z] )

Itt a (∀x) helyett (∀x∈U) vagy (∀x∈D(κ)) is írható.

Definíció: Legyen κ konnekció. Ezt jobbról egyértelműnek (balra egyértelműnek vagy felülről egyértelműnek) nevezzük, ha bármilyen dolog legfeljebb egyszer szerepel κ-ban első koordinátaként, azaz

(∀y): ( [(∃w,x):(<w,y>∈κ ∧ <x,y>∈κ) ⇒ w=x] )

Itt a (∀y) helyett (∀y∈U) vagy (∀x∈R(κ)) is írható.

Konnekció leszűkítése

Definíció: Legyen κ konnekció, valamint A és B tetszőleges osztályok. Ekkor a κ A-ra és B-re való leszűkítésén (vagy megszorításán) azon κ-beli rendezett párok osztályát értjük, melyek első koordinátája A-beli, a második B-beli.

κ_|A,B := {p∈κ | (∃x∈A)(∃y∈B):(p=<x,y>) }

Később bevezetett jelölések segítségével egyébként ez is írható:

κ_|A,B = κ∩(A×B)

Magától értetődik, hogy ha A bővebb (nem szűkebb) mint D(κ) és B bővebb (nem szűkebb), mint R(κ), akkor κ_|A,B = κ.

Konnekció metszete

Definíció: Legyen κ konnekció, valamint A tetszőleges osztály. Ekkor a κ A-ra vonatkozó metszetén azon R(κ)-beli elemek osztályát értjük, amelyek κ-beli rendezett párt alkotnak az A valamely elemével .

κ[A] := {y∈R(κ) | (∃x∈A):(<x,y>∈κ) }

Létezik egy analóg fogalom is, mely azon első koordináták osztálya, amelyek rendezett párt alkotnak valamely A-beli elemmel mint első koordinátával, és e rendezett pár a konnekcióban van. Ez azonban kifejezhető más alapvető fogalmakkal (κ^-1[A]), és amúgy sem fogjuk használni.

Operáció

Az operáció definíciója

Definíció: Egy κ konnekciót operációnak (avagy másodrendű függvénynek) nevezünk, ha balról egyértelmű. Ha a κ konnekciónak van alaptartománya és ez D(κ), akkor a D(κ) osztályon értelmezett operációról is beszélünk. Továbbá, ha

<x,y>∈κ;

akkor ezt így is írjuk:

κ(x)=y;

és ez esetben az y individuumot az x képének is nevezzük a κ operáció szerint (vagy a κ-ban).

Vagyis ez a fogalom nem más, mint egy szinonima (a balról egyértelmű konnekcióra), illetve egy megkülönböztetett írásmód. Mégis az egyik legfontosabb osztályelméleti fogalom rögtön a rendezett pár után. Még egy nevezetes speciális írásmód kapcsolódik hozzá:

Ha κ egy operáció és A olyan osztály, amely az alaptartományánál bővebb (pontosabban nem szűkebb), azaz ha D(κ)⊆A, akkor κ-t az A osztály feletti operációnak is mondjuk. Továbbá, ha B olyan osztály, amely bővebb (nem szűkebb) a κ képtartományánál, akkor κ-t a B osztályba képező operációnak is mondjuk. Azt a tényt, hogy κ egy A feletti és B-be képező operáció, a következő formális alakban is jelöljük:

κ: A→B; κ(x)=y

Ahol y a halmazelméleti nyelvünk (ld. később) valamely formulája. Az ilyen jelsorozatokat a konnekciók előírásának nevezzük.

Igen zavaró, hogy helytakarékosság és más okok miatt az előírásból sokszor elhagyják az alap- és képtartomány feltüntetését, bár ezt mi is alkalmazni fogjuk. Ennek az a hátránya, hogy sok esetben összekeveredhet, hogy egy κ(x)=y alakú jelsor épp az egész operációt jelöli-e, vagy csak egy konkrét elem ama operáció (κ) szerinti képét. Ezt próbáljuk azzal kivédeni, hogy ha általános (pl. definiáló) azonosságról van szó és nem az operáció valamely konkrét konstansra vagy paraméterre való alkalmazásáról, akkor megvastagítjuk a független változót (azaz amelyik a κ jel után zárójelben áll).

A „pótlási” axióma

Az operáció fogalmához egy erős axióma is kapcsolódik:

(A11) A behelyettesítési axióma avagy a pótlás axiómája

Ha ƒ:A→B tetszőleges, az A osztályon értelmezett operáció, amelynek képtartománya B, és A halmaz, akkor B is halmaz.

Vagyis, ha egy operáció alaptartományának elemeit behelyettesítjük egy operáció független változójának helyébe, a kapott képelemek is halmazt alkotnak. Ezért hívják ezt behelyettesítési axiómának. Illetve, a magyar szakirodalomban nem is így hívják, hanem „a pótlás axiómájának” – ez vsz. az angol „replacement” (behelyettesítés) kifejezés hanyag fordítása .

Példák

Példák és ellenpéldák konnekciókra

Összegyűjtjük az eddig szereplő legfontosabb konnekciókat. Eddig ezek a jelek csak afféle absztrakciók, formális nyelvi jelenségek voltak, amiket le lehet írni, ha érvényes valamely tényállás. Ha úgy tetszik, ezenfelül felfoghatjuk őket úgy is, mint speciális osztályokat.

1. ∈. D(∈) = U. R(∈) az összes osztály sokasága - ami nem osztály.
2. ∉. Ez nem konnekció (habár "olyasmi").
3. ≡. D(≡) = R(≡) = E
4. =. D(=) = R(=) = H
5. = és ≠. Ezek valójában nem konnekciók, mert valódi osztályokra is értelmesek.
6. ⊆. Ez sem konnekció, hiszen pl. E⊆U, noha a <E,U> rendezett párról - mint olyan osztály, ami elemként valódi osztályokat tartalmaz - nem lehet beszélni, pedig egy konnekció ilyeneket tartalmazó osztály. De általában ugyanígy ⊆ jelöli azt a konnekciót, amit csak a halmazok között értelmezünk (vagyis ⊆ leszűkítését az U-ra és U-ra). Ezt mi egyébként korábban ⊆₁ módon jelöltük. Ez már egy konnekció.

Példák operációkra

Legyen {p | (∃x,y∈U):(p=<x,y>)}   =   U².

1. Tetszőleges x∈U-ra egy U→U alakú operáció a következő: {x}, azaz amely képezi egy individuumból az azt tartalmazó egyelemű halmazt.
2. P: U→U; P(X) (hatványhalmaz-képző operátor).
3. U²→H; {x,y} (rendezetlenpár-képző operátor).
4. Az {x|...} intenzionális (vagy komprehenzió-) operátor. Ennek alaptartománya a halmazelmélet összes elképzelhető értelmes formulája, képtartománya pedig az osztályok sokasága.
5. U²→H; <x, y> = {{x},{x,y}} (rendezettpár-képző operátor).
6. Legyen ∪ az ún. egyesítés művelete: ha A,B osztályok, akkor A∪B := {x | x∈A ∨ x∈B}. Tetszőleges x∈H-ra képezhető a α(x)=x∪{∅} operáció, ez hozzáadja a tárgyhalmazhoz az üres halmazt elemként.

És így tovább, még végtelen sok hasonló példa kitalálható.

Megjegyzések

A konnekció alapfogalom

Hogy miért nem formalizálható a konnekció fogalma? Természetesen azért, mert "az olyan osztályok, amelyek" ... szövegek nem formalizálhatóak az osztályelméletben, hiszen az osztályok nem alkotnak osztályt. Emlékeztetünk rá: az

"Konnekció" := {x | (∀y∈x):(∃u,v):(y=<u,v>) }

és hasonló kifejezésekben az x változó "automatikusan" U-ból veszi fel értékeit. Ezért csak olyan konnekciókat tudnánk definiálni (formálisan, és nem-alapfogalomként), melyek halmazt alkotnak. De nem minden konnekció ilyen. Például vegyük a következőt:

E := {<X,Y> | X,Y∈U ∧ X∈Y}

Belátható, hogy (legalábbis reguláris halmazelméletekben) ez pl. nem halmaz, hanem valódi osztály . Vagy legyen pl. ennek részosztálya,

E_U := {<X,X> | X∈U}

Ez is valódi osztály, hasonló okok miatt.

Konnekciók és operációk

A konnekció és operáció fogalmai „egyenértékűek”. Bármelyiket fogadjuk el alapfogalomként, a másik egy definiálható fogalom. Hogy a konnekció fogalma segítségével az operáció fogalma mint részfogalom definiálható, azt láttuk.

Vázoljuk, hogyan működik a „fordított irányú” fogalombevezetés. Legyenek 0 és 1 (vagy "i", "h") az U individuumtartomány tetszőleges elemei. Mármost ha adva van egy κ konnekció mint <x,y> alakú párok egy osztálya (x,y∈U), definiáljuk a következő osztályt:

U := {r | (∃x,y∈U):(r=<x,y>) }

Ezen az osztályon értelmezzük a χ_κ operációt, a κ ún. karakterisztikus operációját a következőképp: legyen χ_κ(x)=0 ha x∉κ és χ_κ(x)=1 ha x∈κ.

Ahelyett, hogy beszélünk konnekciókról, először beszélhetünk az összes ilyen operációról is, vagyis amelyek U-en vannak értelmezve és a {0,1} halmazba képeznek. Minden konnekcióhoz van olyan operáció, amely pontosan azokon az elempárokon vesz fel 1 értéket, amelyek elemei a konnekciónak.

Ez út szokatlanabb látszhat, mint amelyiken mi jártunk; és kezdők számára esetleg természetellenesebbne is tűnhetik, ugyanakkor van egy igen szemléletes és népszerű értelmezése. Nevezetesen, a karakterisztikus operácók felfoghatóak mint "kijelentések" (ún. relációs kijelentések), a 0 és 1 elemek pedig mint "igazságértékek", a 0 a "hamis" igazságérték és az 1 az "igaz" érték. E szemlélettel a konnekciók a "relációs kijelentések" igazsághalmazai (azaz azon elemek halmazai, melyekre a kijelentés igaz).

Jegyzetek

Lap teteje