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 y 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.

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

Esquema de temas relacionados

Teoría del orden
Bien ordenado
Orden total
Parcialmente ordenado
Preordenado
Conjunto
Relación binaria
Relación reflexiva
Relación transitiva
Relación antisimétrica
Relación total
Relación bien fundada


Referencias

  1. Lo segundo no implica lo primero, si no asumimos el axioma de elección.

Enlaces externos