„Matroidaxiómák” 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
Syp (vitalap | szerkesztései) |
a kisebb formai javítások |
||
8. sor:
Mindenekelőtt belátjuk, hogy '''''egy leszálló halmazrendszer akkor és csak akkor nem üres, ha tartalmazza az üres halmazt'''''. Ugyanis ha leszálló, akkor amennyiben tartalmaz egy halmazt, akkor annak minden részhalmazát is, tehát az üres halmazt is, és mivel nem üres, ezért tartalmaz is egy halmazt, és így a leszállóságból következően az üres halmazt is. Fordítva, ha egy halmazrendszer tartalmazza elemként üres halmazt, akkor maga nyilván nem üres.
Tehát ekvivalens a következő két axiómarendszer egy <math> U </math> halmaz feletti <math> \mathcal{F} </math> halmazrendszerre:
26. sor:
# a halmazrendszer '''nem üres''';
# a halmazrendszer '''leszálló''', azaz egy független halmaz összes részhalmaza is független;
# a független halmazok '''kölcsönösen bővíthető'''ek: ha két független halmaz számossága eltérő, akkor a nagyobból (a több elemet tartalmazóból) ki tudunk választani egy, a kisebb halmazban nem szereplő elemet úgy, hogy azt a kisebbe téve az így „bővített kisebb” halmaz is független.
Ez a matroidok definiálására leginkább használt axiómarendszer.
81. sor:
== A bővíthetőségi axiómarendszer gyengítései ==
A bővíthetőségi axiómarendszer harmadik axiómáját meg lehet fogalmazni számos „gyengébb” változatban is, melyekből önmagukban (tetszőleges halmazrendszerben) nem következne a harmadik axióma, azonban a leszálló tulajdonsággal együtt már igen.
Néhány ilyen gyengítés:
93. sor:
* Ennek igazolása:
** ha ez igaz, akkor a bővíthetőségi axióma is teljesül, hiszen ha <math> \left| K \right| < \left| N \right| </math> független halmaz, akkor amennyiben <math> M \subseteq N </math>, úgy <math> M </math> is független a leszállási axióma szerint, és létezik olyan <math> M </math> is, hogy <math> \left| M \right| = \left| K+1 \right| </math> legyen, és ekkor a gyengített axióma szerint van egy <math> K </math>-t függetlenné bővítő <math> M-K \subseteq N-K </math>-beli elem, tehát ez a bővítő elem <math> N-K </math>-beli is.
** Fordítva pedig, ha az eredeti, erősebb bővíthetőségi axióma teljesül, azaz tetszőleges <math> \left| N \right| > \left| K \right| </math> független halmazok esetén bővíthető a <math> K </math>, akkor nyilván olyan <math> N </math>-ekre is, melyekre <math> \left| N \right| = \left| K \right| +1 </math>. A két állítás tehát egyenértékű (pontosabban, a bővíthetőség egyenértékű a gyenge bővíthetőség és a leszálló tulajdonság együttesével).
== Források ==
| |||