Set finanțat

O mulțime bine fundamentată este o mulțime parțial ordonată în care fiecare submulțime nevidă are un element minim . Prin elementul minim de aici înțelegem , astfel încât pentru oricare dintre următoarele [1] . În matematică, o mulțime bine întemeiată este cunoscută și sub numele de semirete completă . $\langle M,R\rangle$ $S\subseteq M$ $S$ $m\în S$ $x\în S$ $x\,R\,m$ $x=m$

(Unii autori[ ce? ] necesită în plus ca relația R să fie conectată .)

O definiție echivalentă, sub rezerva utilizării axiomei alegerii , este aceea că o mulțime M cu relația R este bine întemeiată dacă și numai dacă satisface condiția lanțului descendent , adică nu există o succesiune infinită x 0 , x 1 , x 2 , ... a elementelor din M astfel încât x n +1 R x n pentru orice indice n .

Exemple

Exemple de seturi bine întemeiate fără ordine completă.

Mulțimea numerelor întregi cu ordin parțial a < b dacă și numai dacă a împarte b și a ≠ b
Mulțimea tuturor șirurilor finite dintr-un alfabet finit cu ordine parțială s < t dacă și numai dacă s este inclus strict ca subșir în t

Principiul inducției transfinite

Să fie un set bine întemeiat și . Atunci dacă pentru oricare dintre incluziuni urmează , atunci coincide cu [2] . $\langle M,R\rangle$ $S\subseteq M$ $m\în M$ $\{s\în M:s\,R\,m,s\nu =m\}\subseteq S$ $m\în S$ $M$ $S$

Inducția noetheriană

Inducția noetheriană este o generalizare a inducției transfinite, care este după cum urmează.

Să fie o mulțime bine întemeiată, să fie o afirmație despre elementele mulțimii și să vrem să arătăm ce este adevărat pentru toți . Pentru a face acest lucru, este suficient să arătăm că dacă , și este adevărată pentru toate acestea , atunci este și adevărată. Cu alte cuvinte $\langle X,R\rangle$ $P(x)$ $X$ $P(x)$ $x\în X$ $x\în X$ $P(y)$ $y\in X$ $y\,R\,x$ $P(x)$ $\forall x\in X\,((\forall y\in X\,(y\,R\,x\la P(y)))\la P(x))\la \forall x\ în X\,(P(x)).$

Note

↑ Ershov, Paliutin, 1987 , p. 70.
↑ Ershov, Paliutin, 1987 , p. 74.

Literatură

Ershov Yu.L., Paliutin E.A. Logica matematică. — M .: Nauka, 1987. — 336 p.