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 x0, x1, x2, ... de elementos de X tal que xn+1R xn para todo número natural n.[1]

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 ab.
  • 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 (n1, n2) < (m1, m2) si y solamente si n1 < m1 and n2 < m2.
  • 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.
Other Languages