„Jólrendezett halmaz” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Bot: következő hozzáadása: uk:Цілком впорядкована множина |
a Bot: következő módosítása: zh:良序关系; kozmetikai változtatások |
||
1. sor:
'''Jólrendezett halmaznak''' nevezünk egy halmazt, ha adott rajta egy [[teljes rendezés]], ami '''jólrendezés''', vagyis a halmaz minden nemüres részhalmazának van a rendezés szerint legkisebb eleme.
== Definíció ==
Az <math>(A, \leq)</math> rendezett halmazt '''jólrendezett halmaznak''' nevezzük, ha <math>(A, \leq)</math> minden nemüres részhalmazának van legkisebb eleme.
8. sor:
bijekció, melyre ''a'' <<sub>1</sub> ''b'' pontosan akkor, ha ''F(a)'' <<sub>2</sub> ''F(b)'' minden <math>a, b \in A</math> -ra.
Az izomorfia tehát a halmazok és a rajtuk definiált jólrendezések közös tulajdonsága, egy adott halmaznak is lehetnek egymással nem izomorf jólrendezései (sőt, pontosan a véges halmazok azok, amiknek minden (jól)rendezése izomorf egymással). A jólrendezett halmazok közötti izomorfizmus [[ekvivalenciareláció]].<br />
Izomorf jólrendezett halmazok közös tulajdonságát, "a jólrendezésük típusát" [[rendszám (halmazelmélet)|
== Tulajdonságok ==
Egy jólrendezett halmaz nem tartalmazhat végtelen csökkenő sorozatot.
21. sor:
A jólrendezett halmazok azért kényelmesek, mert alkalmazható bennük a [[transzfinit indukció]] (a [[teljes indukció]] általánosítása), melynek segítségével a halmaz elemeire olykor könnyen bizonyíthatunk állításokat.
== Példák ==
Példák jólrendezett halmazra:
* Bármely véges teljesen rendezett halmaz.
30. sor:
* A pozitív valós számok a szokásos rendezéssel, hiszen például a (0,1) nyílt [[intervallum]]nak nincs legkisebb eleme. <math>(\mathbb{R}, < )</math>
== Jólrendezési tétel ==
=== Tétel ===
Minden halmaz jólrendezhető, azaz tetszőleges halmazon megadható olyan rendezés, amellyel a struktúra jólrendezett.
=== Megjegyzés ===
A Jólrendezési tétel ekvivalens a [[Kiválasztási axióma|Kiválasztási axiómával]]. A bizonyítása tehát csak azt jelenti, hogy föltesszük a Kiválasztási axiómát vagy egy azzal ekvivalens állítást, és abból levezetjük a Jólrendezési tételt.
Az itt bemutatott bizonyítások közül az első a [[Zorn-lemma]] egy következményét használja, a második közvetlenül a Kiválasztási axiómát.
40. sor:
A tétel és az eredeti bizonyítás [[Ernst Zermelo]]tól származik. Ebben a bizonyításban mondta ki először Zermelo a kiválasztási axiómát.
=== Definíció ===
Legyenek <math>A</math> és <math>B</math> egy tetszőleges <math>(R, \leq)</math> részbenrendezett halmaz részhalmazai. Azt mondjuk, hogy <math>A</math> '''szelete''' <math>B</math>-nek, ha <math>A=B</math> vagy valamely <math>b\in B</math>-re <math>A = \{x< b: x\in B\}</math>.
=== Bizonyítás ===
A tételt [[Hausdorff–Birkhoff-tétel]] felhasználásával fogjuk bizonyítani. Legyen <math>H</math> tetszőleges halmaz. A bizonyításhoz tekintsük az összes lehetséges <math>(A, \leq)</math> jólrendezett halmazt, ahol <math>A \subseteq H</math>. Két ilyen jólrendezett halmaz akkor és csak akkor egyenlő, ha nem csak az alaphalmazok elemei egyeznek meg, de a rajtuk megadott <math>\leq</math> reláció is. Definiáljuk most a <math>\leq_1</math> részbenrendezést az így képezett jólrendezett halmazok halmazán a következőképpen: <math>(A, \leq) \leq_1 (B, \leq)</math> akkor és csak akkor, ha <math>A</math> szelete <math>B</math>-nek. A Hausdorff–Birkhoff-tétel szerint az így definiált részbenrendezett halmazban van maximális rendezett részhalmaz, legyen ez <math>(A_1, \leq), (A_2, \leq), \ldots</math>. Legyen ezeknek az egyesítése
=== Bizonyítás-vázlat a [[Kiválasztási axióma]] felhasználásával ===
Legyen ''H'' tetszőleges halmaz. A bizonyítás lényege az, hogy ''H'' elemeihez [[Rendszám (halmazelmélet)|rendszámokat]] rendelünk egyértelmű módon, azaz megadunk egy bijekciót a halmaz és a rendszámok egy szelete között. Mivel a rendszámok szeletei jólrendezett halmazok, a megfeleltetetés jólrendezést generál ''H''-n.
A Kiválasztási axióma azt biztosítja, hogy tudunk tetszőlegesen sokszor új elemet választani ''H''-ból, amit a soron következő rendszámhoz rendelünk hozzá.
52. sor:
Legyen tehát ''F'' egy kiválasztási függvény ''H'' hatványhalmazán: <math>F:\mathcal{P}(H)\rightarrow H ;\ F(A) \in A</math> minden <math>A \subseteq H ;\ A \ne \emptyset</math> esetén.
Kiválasztási függvény létezését a Kiválasztási axióma garantálja. Azonban a kiválasztási függvény az üres halmazhoz nem rendel semmit, ''F'' ottani értékét ezért külön kell definiálnunk:
<math>F(\emptyset):=t</math>, ahol ''t'' egy tetszőleges ''H''-n kívüli elem.<br />
Ezután [[transzfinit rekurzió]]val legyártjuk a ''G'' jólrendező függvényt. Minden rendszámhoz hozzárendelünk egy-egy elemet ''H''-ból, mégpedig a következőképp: legyen α egy rendszám. Ha az α-nál kisebb rendszámokra már meghatároztuk ''G'' értékét, nézhetjük ''H''-nak azon elemeit amiket már fölvett a ''G'' függvény az α-nál kisebb rendszámokon. Ezek egy részhalmazt alkotnak. Az ''F'' függvény ezen részhalmazon fölvett értéke lesz ''G''(α). Tehát a <br />
: <math>G(\alpha)=F(H \setminus \{G(\beta) \mid \beta < \alpha \})</math>
rekurzió megoldása lesz ''G'', a traszfinit rekurzió tétele szerint ''G'' létezik és egyértelmű. Ez a ''G'' még nem függvény, hanem ún. operáció, mert az értelmezési tartománya -a rendszámok osztálya- nem halmaz.
Viszont belátható, hogy ''G'' injektív, amég föl nem veszi a ''t'' értéket, onnantól kezdve viszont mindig ''t''-t vesz föl:
* <math>G(\alpha) \ne G(\beta) \,</math> , ha <math>\alpha \ne \beta</math> és egyikük sem <math>t</math>. Hiszen ha például α < β, akkor ''G''(β) értékét olyan halmazból választjuk, amiben ''G''(α) már nincs benne.
* <math>\alpha < \beta</math> és <math>G(\alpha)= t \ \Rightarrow \ G(\beta)=t</math>. G(α)=''t'' ugyanis azt jelenti, hogy ''H''-nak már minden elemét fölvette ''G'' α-nál kisebb rendszámokra, és így
* ''G'' fölveszi a ''t'' értéket. Mert ha nem venné föl, akkor ''G'' bijekció lenne ''H'' és a rendszámok osztálya között, márpedig ''H'' halmaz, a rendszámok osztálya nem halmaz. (Egész pontosan a [[Neumann–Bernays–Gödel-halmazelmélet|Pótlás axiómájára]] lehet hivatkozni.)
Legyen φ a legkisebb rendszám, amire ''G'' a ''t'' értéket veszi föl. A rendszámok tulajdonságai miatt ilyen rendszám létezik. Ekkor ''G'' megszorítása a φ-nél kisebb rendszámokra függvény, és bijekció ezen rendszámok és ''H'' között.
Ez a bizonyítás nem tartalmazza a transzfinit rekurzió pontos leírását.
=== Ekvivalens állítások ===
A jólrendezési tétel ekvivalens a következő állításokkal:
* [[kiválasztási axióma]]
72. sor:
* [[Tyihonov-tétel]]
=== Következmény ===
A jólrendezési tétel következménye, hogy létezik kiválasztási függvény, azaz a kiválasztási axióma teljesül, mert ekkor definiálhatjuk úgy a kiválasztási függvényt, hogy az rendelje hozzá minden részhalmazhoz az adott részhalmaz legkisebb elemét.
== Hivatkozások ==
* Rédei, László: ''Algebra
* Szendrei, Ágnes: ''Diszkrét matematika
{{csonk-dátum|csonk-mat|2005 júniusából}}
104. sor:
[[tr:İyi-sıralı]]
[[uk:Цілком впорядкована множина]]
[[zh:良序
| |||