Relación bien fundada

En matemáticas , una relación binaria R se denomina bien fundada (o fundacional ) [ ^{1 ] en} un conjunto o , más generalmente, en una clase X si todo subconjunto no vacío (o subclase) S ⊆ X tiene un elemento mínimo con respecto a R ; es decir, existe un m ∈ S tal que para todo s ∈ S , no se tiene s ∈ R m . Formalmente, una relación es bien fundada si: $${\displaystyle (\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].}$$ Algunos autores incluyen una condición adicional: que R sea similar a un conjunto , es decir, que los elementos menores que cualquier elemento dado formen un conjunto.

De forma equivalente, asumiendo el axioma de elección dependiente , una relación está bien fundada cuando no contiene cadenas descendentes infinitas , lo que significa que no existe una secuencia infinita x ₀ , x ₁ , x ₂ , ... de elementos de X tal 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 , entonces se denomina buen 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 inversamente bien fundada , inversamente bien fundada o noetheriana en X , si la relación inversa R ⁻¹ es inversamente bien fundada en X. En este caso, también se dice que R satisface la condición de cadena ascendente . En el contexto de los sistemas de reescritura , 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 usar una versión de la inducción transfinita sobre ellas: si ( X , R ) es una relación bien fundada, P ( x ) es alguna propiedad de los elementos de X , y queremos demostrar que

P ( x ) se cumple para todos los elementos x de X ,

Basta con demostrar que:

Si x es un elemento de X y P ( y ) es verdadero para todo y tal que y R x , entonces P ( x ) también debe ser verdadero.

Eso es, $${\displaystyle (\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implies P(y)]\implies P(x)]\quad {\text{implícita}}\quad (\forall x\in X)\,P(x).}$$

La inducción bien fundamentada a veces se denomina inducción noetheriana, ^{[ 4 ]} en honor a Emmy Noether .

Al igual que la inducción, las relaciones bien fundadas también permiten la construcción de objetos mediante 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 formado por un elemento x ∈ X y una función g en el conjunto { y : y ∈ R x } de predecesores de x . Entonces existe una única función G tal que para cada x ∈ X , $${\displaystyle G(x)=F\left(x,G\vert _{\left\{y:\,y\mathrel {R} x\right\}}\right).}$$

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, consideremos 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 sobre S es la inducción matemática usual , y la recursión sobre S da como resultado 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 fundamentada. Cuando la relación bien fundamentada es el orden usual en la clase de todos los números ordinales , la técnica se denomina inducción transfinita . Cuando el conjunto bien fundamentado es un conjunto de estructuras de datos definidas recursivamente, la técnica se denomina inducción estructural . Cuando la relación bien fundamentada es la pertenencia a un conjunto en la clase universal, la técnica se conoce como ∈-inducción . Consulte los artículos correspondientes para obtener más detalles.

Entre las relaciones bien fundadas que no están totalmente ordenadas se incluyen:

• Los enteros positivos {1, 2, 3, ...} , con el orden definido por a < b si y solo si a divide a b y a ≠ b .
• El conjunto de todas las cadenas finitas sobre un alfabeto fijo, con el orden definido por s < t si y solo si s es una subcadena propia de t .
• El conjunto N × N de pares de números naturales , ordenados por ( n ₁ , n ₂ ) < ( m ₁ , m ₂ ) si y solo si n ₁ < m ₁ y n ₂ < m ₂ .
• Toda clase cuyos elementos son conjuntos, con la relación ∈ ("es un elemento de"). Este es el axioma de regularidad .
• Los nodos de cualquier grafo acíclico dirigido finito , con la relación R definida de tal manera que a R b si y solo si existe una arista de a a b .

Algunos ejemplos de relaciones que no están bien fundamentadas son:

• Los enteros negativos {−1, −2, −3, ...} , con el orden habitual, ya que cualquier subconjunto no acotado no tiene un elemento mínimo.
• El conjunto de cadenas sobre un alfabeto finito con más de un elemento, bajo el orden usual ( lexicográfico ), ya que la secuencia "B" > "AB" > "AAB" > "AAAB" > ... es una cadena descendente infinita. Esta relación no está bien fundamentada, aunque todo el conjunto tenga un elemento mínimo, a saber, la cadena vacía.
• El conjunto de números racionales (o reales ) no negativos bajo el orden estándar, ya que, por ejemplo, el subconjunto de racionales (o reales) positivos carece de un mínimo.

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 una universalidad entre las relaciones extensionales bien fundadas: 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 , ∈) .

Se dice que una relación R es reflexiva si a 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 usual ≤, 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 buena fundamentación (quizás implícitamente) a la relación alternativa < definida de tal manera 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 tal manera que a < b si y solo si a ≤ b y b ≰ a . En el contexto de los números naturales, esto significa que la relación <, que está bien fundamentada, se usa en lugar de la relación ≤, que no lo está. En algunos textos, la definición de una relación bien fundada se modifica con respecto a la definición anterior para incluir estas convenciones.

• Just, Winfried y Weese, Martin (1998) Descubriendo la teoría moderna de conjuntos. I , American Mathematical Society ISBN 0-8218-0266-6.
• Karel Hrbáček y Thomas Jech (1999) Introducción a la teoría de conjuntos , 3.ª edición, «Relaciones bien fundadas», páginas 251-255, Marcel Dekker ISBN 0-8247-7915-0

• https://ncatlab.org/nlab/show/well-founded+coalgebra