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:

Para todo subconjunto no vacío S de X, hay un elemento m en S tal que ningún s en S cumple sRm.

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 dividido 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₁ y 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 $\in$ ("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

Propiedades de las relación binaria homogénea.

Relación reflexiva	Relación simétrica	Relación transitiva	Relación total	Relación bien fundada
Relación irreflexiva	Relación antisimétrica	Relación intransitiva		Acotado