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{implies}}\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:

• The positive integers{1, 2, 3, ...}, with the order defined by a < bif and only ifadividesb and a ≠ b.
• The set of all finite strings over a fixed alphabet, with the order defined by s < t if and only if s is a proper substring of t.
• The set N × N of pairs of natural numbers, ordered by (n₁, n₂) < (m₁, m₂) if and only if n₁ < m₁ and n₂ < m₂.
• Every class whose elements are sets, with the relation ∈ ("is an element of"). This is the axiom of regularity.
• The nodes of any finite directed acyclic graph, with the relation R defined such that aRb if and only if there is an edge from a to b.

Examples of relations that are not well-founded include:

• The negative integers {−1, −2, −3, ...}, with the usual order, since any unbounded subset has no least element.
• The set of strings over a finite alphabet with more than one element, under the usual (lexicographic) order, since the sequence "B" > "AB" > "AAB" > "AAAB" > ... is an infinite descending chain. This relation fails to be well-founded even though the entire set has a minimum element, namely the empty string.
• The set of non-negative rational numbers (or reals) under the standard ordering, since, for example, the subset of positive rationals (or reals) lacks a minimum.

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