Financovaná sada

Dobře podložená množina je částečně uspořádaná množina , ve které má každá neprázdná podmnožina minimální prvek . Minimálním prvkem zde rozumíme takový, že pro kterýkoli z následujících [1] . V matematice je dobře podložená množina známá také jako úplná polomřížka . $\langle M,R\rangle$ $S\subseteq M$ $S$ $m\in S$ $x\in S$ $x\,R\,m$ $x=m$

(Někteří autoři[ co? ] navíc vyžadují, aby vztah R byl připojen .)

Ekvivalentní definicí, s výhradou použití axiomu výběru , je, že množina M s relací R je dobře podložená tehdy a jen tehdy, když splňuje podmínku sestupného řetězce , to znamená, že neexistuje nekonečná posloupnost x 0 , x 1 , x 2 , ... prvků z M tak, že x n +1 R x n pro libovolný index n .

Příklady

Příklady fundovaných sestav bez plného řádu.

Množina celých čísel s částečným řádem a < b právě tehdy, když a dělí b a a ≠ b
Množina všech konečných řetězců v konečné abecedě s částečným řádem s < t právě tehdy, když s je striktně zahrnuto jako podřetězec v t

Princip transfinitní indukce

Budiž fundovaná množina a . Pak pokud pro některý z inkluzí následuje , pak se shoduje s [2] . $\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$

Noetherovská indukce

Noetherovská indukce je zobecněním transfinitní indukce, která je následující.

Buďme dobře podloženou množinou, buďme nějakým tvrzením o prvcích množiny a chceme ukázat, co platí pro všechny . K tomu stačí ukázat, že jestliže , a platí pro všechny takové , že , pak je to také pravda. Jinými slovy $\langle X,R\rangle$ $P(x)$ $X$ $P(x)$ $x\in X$ $x\in X$ $P(y)$ $y\in X$ $y\,R\,x$ $P(x)$ $\forall x\in X\,((\forall y\in X\,(y\,R\,x\to P(y)))\to P(x))\to \forall x\ v X\,(P(x)).$

Poznámky

↑ Ershov, Paljutin, 1987 , str. 70.
↑ Ershov, Paljutin, 1987 , str. 74.

Literatura

Ershov Yu.L., Paljutin E.A. Matematická logika. — M .: Nauka, 1987. — 336 s.