Relación bien fundada

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

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 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 \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 conjuntod e 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[editar]

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

Referencias[editar]

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

Enlaces externos[editar]