Relación bien fundada

En matemáticas , una relación bien fundada (también llamada relación noetheriana o relación artiniana ) es una relación binaria que satisface una de las dos condiciones siguientes, equivalente según el axioma de elección dependiente (una versión débil del axioma de elección ):

• para cualquier parte X de E no vacía , existe un elemento x de X que no tiene antecedente R en X (un antecedente R de x en X es un elemento y de X que satisface yRx );
• Condición de cadena descendente  : no hay resultado infinito ( x n ) de elementos de E tal que exista x n +1 Rx n para cualquier n .

Un orden bien fundado (también llamado orden noetheriano u orden artiniano ) es una relación de orden del cual el orden estricto asociado es una relación bien fundada.

Toda relación bien fundada es estrictamente acíclica , es decir que su cierre transitivo es un orden estricto. Una relación R está bien fundada si su cierre transitivo lo es, o si R es antirreflexivo y si su cierre transitivo reflexivo es un orden bien fundado.

Ejemplos de

• Sobre el conjunto N de enteros naturales , la relación R definida por x R y ⇔ y = x + 1 está bien fundada (su cierre transitivo es el orden estricto habitual <), y el orden habitual ≤ es un orden total bien fundado, que es, un buen orden .
• La buena base se conserva mediante el retroceso , es decir, para cualquier mapa ρ: E → F y cualquier relación bien fundada S sobre F , la relación T sobre E definida por xTy ⇔ ρ ( x ) S ρ ( y ) está bien fundada.
• En el conjunto de cadenas de caracteres , el orden estricto "es el prefijo estricto de" está bien fundado.
• En todas las cadenas de caracteres, el orden lexicográfico no está bien fundado.
• El axioma de fundación afirma que la relación de pertenencia está bien fundada; pero podemos tener una teoría de conjuntos equicoherente con el axioma de anti-fundamento .
• En el conjunto de árboles binarios finitos, construido a partir del árbol vacío y el enraizamiento ¤ (es decir, de dos árboles A y B formamos el árbol A ¤ B ), el orden estricto "es un subárbol estricto de" es un orden bien fundado . Por lo tanto, significa: A ¤ B> o A ¤ B> C si A C o B C .◻{\ Displaystyle \ Box} ◻{\ Displaystyle \ Box} ≥{\ Displaystyle \ geq} ≥{\ Displaystyle \ geq}
• En el conjunto de árboles binarios, podemos definir el siguiente orden bien fundado>:
  • A ¤ B> ,◻{\ Displaystyle \ Box}
  • o A ¤ B> C ¤ D porque
    • A> C y A ¤ B> D ,
    • o A = C y B> D

En el último orden, el árbol ( ¤ ) ¤ tiene una infinidad de árboles más pequeños que él.◻{\ Displaystyle \ Box}◻{\ Displaystyle \ Box}◻{\ Displaystyle \ Box}

Recurrencia noetheriana o bien fundada

Denotamos por R −1 [ x ] el conjunto de R- antecedentes de x .

El siguiente teorema (en la teoría de conjuntos de Zermelo ) ofrece tanto una tercera definición equivalente del buen fundamento como una generalización del principio de prueba por inducción transfinita (en un buen orden o en un ordinal ), que a su vez extiende el axioma de Peano n o  5 o el principio de inducción (correspondiente al orden habitual en números naturales):

Teorema (buen fundamento e inducción bien fundamentada)  -  Una relación R en un conjunto E está bien fundamentada si y solo si, para que una parte de E sea ​​igual a E como un todo, es suficiente que contenga cada elemento del cual contiene todos los antecedentes R.

Formalmente: R está bien fundado si y solo si, para cualquier parte P de E ,si ∀ x ∈ E ( R -1 [ x ] ⊂ P ⇒ x ∈ P ), entonces P = E . Demostración

Al pasar al complementario , la condición del enunciado equivale a la implicación

para cualquier parte X de E , si ∀ x ∈ E ( R −1 [ x ] ∩ X = ∅ ⇒ x ∉ X ) entonces X = ∅

o nuevamente, en su opuesto  :

para cualquier parte no vacía X de E , ∃ x ∈ X ( R −1 [ x ] ∩ X = ∅),

que expresa así como para todo subconjunto no vacío X de E , existe un elemento x de X sin R -antécédent en X .

Asimismo, un segundo teorema (en la teoría de conjuntos de Zermelo-Fraenkel , por lo tanto con reemplazo ) generaliza el principio de definición por inducción de una secuencia y más generalmente, de definición de una función por recursividad transfinita  :

Teorema (función definida por recursividad bien fundada)  -  Sea R una relación bien fundada en un conjunto E y G una clase funcional definida en todas partes. Entonces, existe una función f y solo una (en el sentido: una única gráfica de función ), de dominio D f = E , tal que para todo x ∈ E , f ( x ) = G ( x , f | R - 1 [ x ] ), donde f | P indica la restricción de f a P .

Demostración

Definamos el predicado rec ( h ) por: h es una función, de dominio D h ⊂ E , tal que para todo z ∈ D h , R −1 [ z ] ⊂ D h y h ( z ) = G ( z , h | R −1 [ z ] ), luego el predicado F ( x , y ) por: ∃ h (rec ( h ) y h ( x ) = y ).

Por inducción bien fundada, la clase F es funcional (lo que ya prueba, por extensionalidad , que la posible función f anunciada en el teorema es única), pero su dominio está incluido en el conjunto E por tanto (según el diagrama de axiomas de reemplazo ) existe una función f tal que F ( x , y ) ⇔ f ( x ) = y . Además, por construcción, se satisface rec ( f ).

Finalmente, D f = E , nuevamente por inducción bien fundada: para todo x ∈ E tal que R −1 [ x ] ⊂ D f , el conjunto de pares h  : = f ∪ {( x , G ( x , f | R −1 [ x ] ))} satisface rec ( h ) entonces x ∈ D f .

Estos dos teoremas se extienden a las clases, como sus contrapartes en el caso particular de la recurrencia transfinita . Más precisamente: se puede sustituir, en estos dos estados, los conjuntos E , R y f por clases (relacionales para R y funcionales para f ), siempre que para cualquier conjunto x , la clase R -1 [ x ] es un juntos ( en el caso de la inducción transfinita, es inútil agregar este supuesto porque ∈ −1 [ x ] = x ).

Función de rango

En un conjunto E provisto de una relación R bien fundada , cada elemento x admite un rango ρ ( x ), que es un número ordinal . La función de rango se define en E por recursividad bien fundada por:

ρ ( x ) = ∪ {α + 1 | α ∈ im (ρ | R −1 [ x ] ) } = ∪ {ρ ( y ) + 1 | y R x }

(la unión de un conjunto de ordinales es un ordinal). Por tanto, el rango de x es el ordinal más pequeño estrictamente mayor que los rangos de los antecedentes de x .

La longitud de la relación R , a menudo indicada | R |, es el ordinal más pequeño que contiene todo ρ ( x ).

La inducción y recursión bien fundamentadas ( ver arriba ) se aplican a R , pero a veces es más conveniente aplicarlas al retroceso por ρ del orden estricto en el ordinal | R |, es decir, a la relación T definida por: xTy ⇔ ρ ( x ) <ρ ( y ).

La función de rango permite organizar E de una manera obvia en una jerarquía, ampliamente utilizada en la teoría de conjuntos con la relación de pertenencia para R (cf. “  Rango de un conjunto  ”).

Uso algorítmico

Un caso especial de recurrencia bien fundada es la recurrencia estructural . Un algoritmo , cuando construye una serie de elementos mientras asegura que un elemento construido es estrictamente inferior a su predecesor, también asegura su terminación , tan pronto como el orden estricto esté bien fundado.

Las estructuras utilizadas en algorítmica (tipos construidos) son a menudo órdenes estrictas bien fundamentadas, por lo que tenemos un método muy general para probar la terminación de un programa de computadora .

Notas y referencias

1. Jean-Pierre Ramis , André Warusfel et al. , Matemáticas todo en uno para la licencia: Nivel L1 , Dunod ,2013, 2 nd  ed. ( leer en línea ) , pág.  38.
2. (in) Kees Doets, From Logic to Logic Programming , MIT Press ,1994( leer en línea ) , pág.  7.
3. (en) András Hajnal y Peter Hamburger, Teoría de conjuntos , Cambridge University Press ,1999( leer en línea ) , pág.  202 y 280.
4. (en) Michael Holz, Karsten Steffens y Edmund Weitz Introducción a la aritmética cardinal , Birkhauser ,1999( leer en línea ) , pág.  20-23.

Artículos relacionados

• Árbol (matemáticas)
• Método de descenso infinito
• Buen orden y el lema de Higman
• Terminación de un sistema de reescritura
• ∈-inducción  (en)
• Noetherian