Finanszírozott készlet

A jól megalapozott halmaz olyan részben rendezett halmaz , amelyben minden nem üres részhalmaznak van egy minimális eleme . Itt a minimális elem alatt azt értjük , hogy a következők bármelyikére [ 1 ] . A matematikában egy jól megalapozott halmazt teljes félrácsnak is neveznek . $\langle M,R\rangle$ $S\subseteq M$ $S$ $m\in S$ $x\in S$ $x\,R\,m$ $x=m$

(Egyes szerzők[ mi? ] ezenkívül megkövetelik, hogy az R reláció össze legyen kapcsolva .)

Egy ekvivalens definíció a választási axióma használatától függően az , hogy egy R relációjú M halmaz akkor és csak akkor megalapozott, ha teljesíti a csökkenő láncfeltételt , azaz nincs végtelen x 0 , x 1 sorozat. , x 2 , ... az M elemből úgy, hogy x n +1 R x n bármely n indexre .

Példák

Példák a jól megalapozott készletekre teljes sorrend nélkül.

Az a < b részleges rendű egész számok halmaza akkor és csak akkor, ha a osztja a b -t és a ≠ b
Az összes véges karakterlánc halmaza egy véges ábécén, amelynek részleges rendje s < t , akkor és csak akkor, ha s szigorúan szerepel a t -ben.

A transzfinit indukció elve

Legyen egy jól megalapozott halmaz és . Ekkor ha valamelyik zárványra következik , akkor az egybeesik a [2] -vel . $\langle M,R\rangle$ $S\subseteq M$ $m\in M$ $\{s\in M:s\,R\,m,s\not =m\}\subseteq S$ $m\in S$ $M$ $S$

Noether-indukció

A Noether-indukció a transzfinit indukció általánosítása, amely a következő.

Legyen egy jól megalapozott halmaz, legyen némi állítás a halmaz elemeiről , és meg akarjuk mutatni, mi igaz mindenkire . Ehhez elegendő megmutatni, hogy ha , és igaz minden olyanra, hogy , akkor az is igaz. Más szavakkal $\langle X,R\rangle$ $P(x)$ $x$ $P(x)$ $x\X-ben$ $x\X-ben$ $P(y)$ $y\in X$ $y\,R\,x$ $P(x)$ $\forall x\in X\,((\all y\in X\,(y\,R\,x\to P(y)))\to P(x))\to \forall x\ in X\,(P(x)).$

Irodalom

Ershov Yu.L., Palyutin E.A. Matematikai logika. — M .: Nauka, 1987. — 336 p.