En matemáticas , una relación binaria R se llama bien fundada (o bien fundada o fundacional [1] ) en un conjunto o, más generalmente, una clase X si todo subconjunto no vacío S ⊆ X tiene un elemento mínimo con respecto a R ; es decir, existe un m ∈ S tal que, por cada s ∈ S , no se tiene s R m . En otras palabras, una relación está bien fundada si:
De manera equivalente, asumiendo el axioma de elección dependiente , una relación está bien fundada cuando no contiene cadenas descendentes infinitas , lo que puede demostrarse 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 cada número natural n . [2] [3]
En la teoría del orden , un orden parcial se llama bien fundamentado si el orden estricto correspondiente es una relación bien fundada. Si el orden es total entonces se llama bien-orden .
En teoría de conjuntos , un conjunto x se denomina conjunto bien fundado si la relación de pertenencia del 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 fundamentados.
Una relación R es bien fundada a la inversa , bien fundada hacia arriba 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 terminación .
Una razón importante por la que las relaciones bien fundadas son interesantes es que 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 quiero mostrar eso
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 apoyan la construcción de objetos mediante recursividad transfinita . Sea ( X , R ) una relación bien fundada en forma de 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 ) usando 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 la gráfica de la función sucesora x ↦ x +1 . Entonces la inducción en S es la inducción matemática habitual , y la recursividad en S da la recursividad primitiva . Si consideramos la relación de orden ( N , <) , obtenemos inducción completa y recursividad del curso de valores . La afirmación de que ( N , <) está bien fundada también se conoce como principio de buen ordenamiento .
Hay otros casos especiales interesantes de inducción bien fundada. Cuando la relación fundada es el ordenamiento habitual en la clase de todos los números ordinales , la técnica se llama inducción transfinita . Cuando el conjunto bien fundado es un conjunto de estructuras de datos definidas recursivamente, la técnica se llama inducción estructural . Cuando la relación bien fundada se establece como miembro de 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:
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. Considere el siguiente ejemplo: Sea X la unión de los números enteros positivos con un nuevo elemento ω que es mayor que cualquier número 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 del colapso de Mostowski implica que la pertenencia a un conjunto es un universal entre las relaciones extensionales bien fundadas: para cualquier relación R bien fundada tipo conjunto en una clase X que sea extensional, existe una clase C tal que ( X , R ) es isomorfo a ( C , ∈) .
Se dice que una relación R es reflexiva si R a se cumple para todo 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 fundamento (quizás implícitamente) a la relación alternativa < definida tal que a < b si y solo si a ≤ b y a ≠ b . De manera más general, cuando se trabaja con un pedido anticipado ≤, es común usar la relación < definida tal que a < b si y solo si a ≤ b y b ≰ a . En el contexto de los números naturales, esto significa que se utiliza la relación <, que está bien fundada, en lugar de la relación ≤, que no lo es. En algunos textos, la definición de relación bien fundada se modifica con respecto a la definición anterior para incluir estas convenciones.
![{\displaystyle (\forall S\subseteq X)\;[S\neq \varnothing \implica (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)]. }](https://wikimedia.org/api/rest_v1/media/math/render/svg/39674b23f300f531f307e8dbab52b953786a5e4b)
![{\displaystyle (\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implica P(y)]\implica P(x)]\quad {\ text{implica}}\quad (\forall x\in X)\,P(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/891f3d17973e3226b31a0773b4b81e03b2292754)
