Conjunto financiado

Un conjunto bien fundado es un conjunto parcialmente ordenado en el que cada subconjunto no vacío tiene un elemento mínimo . Por elemento mínimo aquí queremos decir , tal que para cualquiera de los siguientes [1] . En matemáticas, un conjunto bien fundado también se conoce como un semirretículo completo . $\langle M,R\rangle$ $S\subseteq M$ $S$ $m\en S$ $x \ en S$ ${\ estilo de visualización x \, R \, m}$ ${\ estilo de visualización x = m}$

(Algunos autores[ ¿Qué? ] adicionalmente requieren que la relación R sea conectada .)

Una definición equivalente, sujeta al uso del axioma de elección , es que un conjunto M con relación R está bien fundado si y solo si satisface la condición de la cadena descendente , es decir, no hay una secuencia infinita x 0 , x 1 , x 2 , ... de elementos de M tales que x n +1 R x n para cualquier índice n .

Ejemplos

Ejemplos de conjuntos bien fundados sin orden completo.

El conjunto de enteros de orden parcial a < b si y sólo si a divide a b y a ≠ b
El conjunto de todas las cadenas finitas en un alfabeto finito con orden parcial s < t si y solo si s se incluye estrictamente como una subcadena en t

El principio de inducción transfinita

Sea un conjunto bien fundado y . Entonces si para alguna de las inclusiones sigue , entonces coincide con [2] . $\langle M,R\rangle$ $S\subseteq M$ $m\en M$ $\{s\in M:s\,R\,m,s\not =m\}\subseteq S$ $m\en S$ $METRO$ $S$

Inducción noetheriana

La inducción noetheriana es una generalización de la inducción transfinita, que es la siguiente.

Sea un conjunto bien fundado, sea alguna afirmación sobre los elementos del conjunto , y queramos mostrar lo que es verdadero para todos . Para hacer esto, basta mostrar que si , y es verdadero para todo tal que , entonces también lo es. En otras palabras $\langle X,R\rangle$ $P(x)$ $X$ $P(x)$ $x\en X$ $x\en X$ $P(y)$ ${\ estilo de visualización y \ en X}$ ${\ estilo de visualización y \, R \, x}$ $P(x)$ $\para todo x\en X\,((\para todo y\en X\,(y\,R\,x\a P(y)))\a P(x))\a \para todo x\ en X\,(P(x)).$

Notas

↑ Ershov, Palyutin, 1987 , pág. 70.
↑ Ershov, Palyutin, 1987 , pág. 74.

Literatura

Ershov Yu.L., Palyutin E.A. Lógica matemática. — M .: Nauka, 1987. — 336 p.