En matemáticas , una relación binaria R se llama bien fundada (o bien fundada o fundacional [1] ) sobre un conjunto o, más generalmente, una clase X si todo subconjunto no vacío S ⊆ X tiene un elemento minimal respecto de R ; es decir, existe un m ∈ S tal que, para todo s ∈ S , no se tiene s R m . En otras palabras, una relación está bien fundada si: Algunos autores incluyen una condición extra de que R sea semejante a un conjunto , es decir, que los elementos menores que cualquier elemento dado formen un conjunto.
De manera equivalente, suponiendo el axioma de elección dependiente , una relación está bien fundada cuando no contiene cadenas descendentes infinitas , lo que se puede demostrar cuando no existe una secuencia infinita x 0 , x 1 , x 2 , ... de elementos de X tales que x n +1 R x n para todo número natural n . [2] [3]
En la teoría del orden , un orden parcial se denomina bien fundado si el orden estricto correspondiente es una relación bien fundada. Si el orden es un orden total , se denomina bien-orden .
En teoría de conjuntos , un conjunto x se denomina conjunto bien fundado si la relación de pertenencia al conjunto está bien fundada en la clausura transitiva de x . El axioma de regularidad , que es uno de los axiomas de la teoría de conjuntos de Zermelo-Fraenkel , afirma que todos los conjuntos están bien fundados.
Una relación R es bien fundada de forma inversa , bien fundada de forma ascendente o noetheriana en X si la relación inversa R −1 está bien fundada en X. En este caso, también se dice que R satisface la condición de cadena ascendente . En el contexto de la reescritura de sistemas, una relación noetheriana también se denomina terminante .
Una razón importante por la que las relaciones bien fundadas son interesantes es porque se puede utilizar una versión de la inducción transfinita en ellas: si ( X , R ) es una relación bien fundada, P ( x ) es alguna propiedad de los elementos de X , y queremos demostrar que
Basta demostrar que:
Eso es,
La inducción bien fundada a veces se denomina inducción noetheriana, [4] en honor a Emmy Noether .
A la par de la inducción, las relaciones bien fundadas también admiten la construcción de objetos por recursión transfinita . Sea ( X , R ) una relación bien fundada de tipo conjunto y F una función que asigna un objeto F ( x , g ) a cada par de un elemento x ∈ X y una función g en el segmento inicial { y : y R x } de X . Entonces existe una función única G tal que para cada x ∈ X ,
Es decir, si queremos construir una función G en X , podemos definir G ( x ) utilizando los valores de G ( y ) para y R x .
Como ejemplo, considere la relación bien fundada ( N , S ) , donde N es el conjunto de todos los números naturales y S es el gráfico de la función sucesora x ↦ x +1 . Entonces, la inducción sobre S es la inducción matemática habitual y la recursión sobre S da la recursión primitiva . Si consideramos la relación de orden ( N , <) , obtenemos la inducción completa y la recursión de curso de valores . La afirmación de que ( N , <) está bien fundada también se conoce como el principio de buen ordenamiento .
Existen otros casos especiales interesantes de inducción bien fundada. Cuando la relación bien fundada es el ordenamiento habitual en la clase de todos los números ordinales , la técnica se denomina inducción transfinita . Cuando el conjunto bien fundado es un conjunto de estructuras de datos definidas recursivamente, la técnica se denomina inducción estructural . Cuando la relación bien fundada es la pertenencia al conjunto en la clase universal, la técnica se conoce como ∈-inducción . Consulte esos artículos para obtener más detalles.
Las relaciones bien fundadas que no están totalmente ordenadas incluyen:
Algunos ejemplos de relaciones que no están bien fundadas incluyen:
Si ( X , <) es una relación bien fundada y x es un elemento de X , entonces las cadenas descendentes que comienzan en x son todas finitas, pero esto no significa que sus longitudes estén necesariamente acotadas. Consideremos el siguiente ejemplo: Sea X la unión de los enteros positivos con un nuevo elemento ω que es mayor que cualquier entero. Entonces X es un conjunto bien fundado, pero hay cadenas descendentes que comienzan en ω de longitud arbitrariamente grande (finita); la cadena ω, n − 1, n − 2, ..., 2, 1 tiene longitud n para cualquier n .
El lema de colapso de Mostowski implica que la pertenencia a un conjunto es universal entre las relaciones bien fundadas extensionales: para cualquier relación bien fundada de tipo conjunto R en una clase X que sea extensional, existe una clase C tal que ( X , R ) es isomorfa a ( C , ∈) .
Una relación R se dice que es reflexiva si se cumple un R a para cada a en el dominio de la relación. Toda relación reflexiva en un dominio no vacío tiene infinitas cadenas descendentes, porque cualquier secuencia constante es una cadena descendente. Por ejemplo, en los números naturales con su orden habitual ≤, tenemos 1 ≥ 1 ≥ 1 ≥ ... . Para evitar estas secuencias descendentes triviales, cuando se trabaja con un orden parcial ≤, es común aplicar la definición de bien fundado (quizás implícitamente) a la relación alternativa < definida de modo que a < b si y solo si a ≤ b y a ≠ b . De manera más general, cuando se trabaja con un preorden ≤, es común usar la relación < definida de modo que a < b si y solo si a ≤ b y b ≰ a . En el contexto de los números naturales, esto significa que se usa la relación <, que está bien fundada, en lugar de la relación ≤, que no lo está. En algunos textos, la definición de una relación bien fundada se modifica respecto de la definición anterior para incluir estas convenciones.
![{\displaystyle (\para todo S\subseteq X)\;[S\neq \varnothing \implica (\existe m\en S)(\para todo s\en S)\lno (s\mathrel {R} m)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39674b23f300f531f307e8dbab52b953786a5e4b)
![{\displaystyle (\para todo x\en X)\;[(\para todo y\en X)\;[y\mathrel {R} x\implica P(y)]\implica P(x)]\quad {\text{implica}}\quad (\para todo x\en X)\,P(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/891f3d17973e3226b31a0773b4b81e03b2292754)
