Relación bien fundada

En teoría de conjuntos, una relación bien fundada sobre una clase X es una relación binaria R sobre X tal que todo subconjunto no vacío de X tiene un elemento R-mínimo; esto es:

Equivalentemente, si asumimos el axioma de elección, una relación es bien fundada si y sólo si X no contiene cadenas descendientes infinitas numerables: esto es, no hay secuencia infinita x₀, x₁, x₂, ... de elementos de X tal que x_n+1R x_n para todo número natural n.^[1]

• En la teoría del orden, un orden parcial es llamado bien fundado si el orden estricto correspondiente es una relación bien fundada. Si el orden bien fundado es un orden total entonces es un buen orden.
• Un conjunto X se dice regular si la relación de pertenencia ∈ está bien fundada en la clausura transitiva de X, ct X. Esto implica que no existen dentro de X conjuntos del tipo A={A}={{A}}=... En teoría axiomática de conjuntos, el axioma de regularidad afirma que todos los conjuntos son regulares.

Ejemplos

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

• Los números naturales {1, 2, 3, ...}, con el orden definido por a < b si y solamente si b es divido por a y a ≠ b.
• El conjunto de todas las cadenas finitas de un alfabeto fijado, con el orden definido por s < t si y solamente si s es una subcadena estricta de t.
• El conjunto N × N de pares de números naturales, ordenados por (n₁, n₂) < (m₁, m₂) si y solamente si n₁ < m₁ and n₂ < m₂.
• El conjunto de todas las expresiones regulares de un alfabeto fijado, con el orden definido por s < t si y solamente si s es una subexpresión estricta de t.
• Cualquier clase con conjuntos como elementos, con la relación ("es un elemento de"). Esto es el axioma de regularidad.

Ejemplos de relaciones que no son bien fundadas son:

• Los números negativos {-1, -2, -3, …}, con el orden usual, ya que cualquier subconjunto no acotado no tiene un elemento mínimo.
• El conjunto de las cadenas de un alfabeto finito con más de un elemento, con el orden lexicográfico, ya que la secuencia "B" > "AB" > "AAB" > "AAAB" > … es un infinita y descendente.
• Los números racionales (o los reales) con el orden usual, ya que, por ejemplo, el conjunto de los racionales (o reales) positivos carece de mínimo.

Véase también

Referencias

Enlaces externos

• Esta obra deriva de la traducción de Well-founded relation de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.