Relació ben fundada

En teoria de conjunts, una relació ben fundada sobre una classe X és una relació binaria R sobre X tal que tot subconjunt no buit de X té un element R-mínim; açò és:

Per a tot subconjunt no buide S de X, hi ha un element m en S tal que cap s en S complix sRm.

Equivalentemente, si assumim l'axioma d'elecció, una relació és ben fundada si i només si X no conté cadenes descendents infinites numerables: açò és, no hi ha seqüència infinita x₀, x₁, x₂, ... d'elements de X tal que x_n+1R x_n per a tot número natural n. En la teoria de l'orde, un orde parcial és cridat ben fundat si l'orde estricte corresponent és una relació ben fundada. Si l'orde ben fundat és un orde total llavors és un bon orde. Un conjunt X es diu regular si la relació de pertinença ∈ està ben fundada en la clausura transitiva de X, ct X. Açò implica que no existixen dins de X conjunts del tipo A={A}={{A}}=... En teoria axiomàtica de conjunts, l'axioma de regularitat afirma que tots els conjunts són regulars.

Eixemples

Entre les relacions ben fundades que no són totalment ordenades estan:

• Els número natural {1, 2, 3, ...}, en l'orde definit per a < b si i solament si b és dividit per a i a ≠ b.
• El conjunt de totes les cadenes finitas d'un alfabet fixat, en l'orde definit per s < t si i solament si s és una subcadena estricta de t.
• El conjunt N × N de parells de número natural, ordenats per (n₁, n₂) < (m₁, m₂) si i solament si n₁ < m₁ i n₂ < m₂.
• El conjunt de totes les expressions regulars d'un alfabet fixat, en l'orde definit per s < t si i solament si s és una subexpresión estricta de t.
• Qualsevol classe en conjunts com a elements, en la relació $\in$ ("és un element de"). Açò és l'axioma de regularitat.

Eixemples de relacions que no són ben fundades són:

• Els números negatius {-1, -2, -3, …}, en l'orde usual, ya que qualsevol subconjunt no acotat no té un element mínim.
• El conjunt de les cadenes d'un alfabet finit en més d'un element, en l'orde lexicogràfic, ya que la seqüència "B" > "AB" > "AAB" > "AAAB" > … és un infinita i descendent.
• Els número racional (o els reals) en l'orde usual, ya que, per eixemple, el conjunt dels racionals (o reals) positius carix de mínim.

Vore també

Propietats de la relació binaria homogénea. Relació reflexiva Relació simètrica Relació transitiva Relació total Relació ben fundada Relació irreflexiva Relació antisimètrica Relació intransitiva Acotat