Relaciones binarias transitivas | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Todas las definiciones requieren tácitamente que la relación homogénea sea transitiva : Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de fila. Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Aquí se enumeran las propiedades adicionales que puede satisfacer una relación homogénea. |
En matemáticas , una relación binaria R se llama bien fundamentada (o bien fundamentada ) en una clase X si cada no vacío subconjunto S ⊆ X tiene un elemento mínimo con respecto a R , es decir, un elemento de m no relacionados por SRM (por ejemplo, " s no es menor que m ") para cualquier s ∈ S . En otras palabras, una relación está bien fundada si
Algunos autores incluyen una condición adicional de que R es similar a un conjunto , es decir, que los elementos menores que cualquier elemento dado forman un conjunto.
De manera equivalente, asumiendo el axioma de elección dependiente , una relación está bien fundada si no contiene cadenas infinitas descendentes contables : es decir, no hay una secuencia infinita x 0 , x 1 , x 2 , ... de elementos de X tal que x n +1 R x n para cada número natural n . [1] [2]
En la teoría del orden , un orden parcial se llama bien fundado si el orden estricto correspondiente es una relación bien fundada. Si el pedido es un pedido total , se denomina pedido de pozo .
En la teoría de conjuntos , un conjunto x se denomina conjunto bien fundado si la relación de pertenencia al conjunto está bien fundada en el cierre transitivo 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 converse bien fundada , hacia arriba bien fundada o Noetherian 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 los sistemas de reescritura , una relación noetheriana también se llama terminación .
Una razón importante por la que las relaciones bien fundadas son interesantes es porque se puede usar una versión de 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 nosotros quiero mostrar eso
basta con mostrar que:
Eso es,
La inducción bien fundada a veces se denomina inducción noetheriana, [3] en honor a Emmy Noether .
A la par con la inducción, las relaciones bien fundadas también apoyan la construcción de objetos por recursividad transfinita . Sea ( X , R ) una relación bien fundada similar a un 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 hay una función única G tal que para cada x ∈ X ,
Es decir, si queremos construir una función G sobre 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 una recursión primitiva . Si consideramos la relación de orden ( N , <), obtenemos la inducción completa y la recursividad del curso de los valores . La afirmación de que ( N , <) está bien fundada también se conoce comoprincipio de buen orden .
Hay 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 de forma recursiva, la técnica se denomina inducción estructural . Cuando la relación bien fundada se establece como pertenencia a 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 y un nuevo elemento ω, que es más grande que cualquier número entero. Entonces X es un conjunto bien fundado, pero hay cadenas descendentes que comienzan en ω de gran longitud (finita) arbitraria; la cadena ω, n - 1, n - 2, ..., 2, 1 tiene una 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 de tipo conjunto en una clase X que es extensional, existe una clase C tal que ( X , R ) isomorfo a ( C , ∈).
Se dice que una relación R es reflexiva si a R a se cumple 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 Para evitar estas triviales secuencias descendentes, cuando se trabaja con un orden parcial ≤, es común aplicar la definición de bien fundamentado (quizás implícitamente) a la relación alterna <definida tal que a < b si y solo si a ≤ b y a ≠ b. Más en general, cuando se trabaja con un orden previo ≤, es común el uso de la relación <definido de tal manera que un < b si y sólo si un ≤ b y b ≰ una . 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 está. En algunos textos, la definición de una relación bien fundada se cambia de la definición anterior para incluir estas convenciones.