Relación ben ordenada

En matemáticas, unha relación ben ordenada nun conxunto $S$ é unha orde total en $S$ coa propiedade de que cada subconxunto non baleiro de $S$ ten un elemento menor nesta ordenación. O conxunto $S$ xunto coa ordenación chámase entón conxunto ben ordenado.

Todo conxunto ben ordenado non baleiro ten un elemento menor. Cada elemento $s$ dun conxunto ben ordenado, agás un posíbel elemento maior, ten un sucesor único (elemento seguinte), é dicir, o elemento menor do subconxunto de todos os elementos maiores que $s$ . Pode haber elementos, alén do elemento menor, que non teñan antecesores (ver abaixo § Números naturais). Un conxunto $S$ ben ordenado contén para cada subconxunto $T$ cun límite superior un límite superior mínimo (supremo), é dicir, o elemento mínimo do subconxunto de todos os límites superiores de $T$ en $S$ .

Se ≤ é unha relación ben ordenada non estrita, entón < é unha relación ben ordenada estrita. Unha relación é ben ordenada estrita se e só se é unha orde total estrita ben fundada. A distinción entre relacións ben ordenadas estritas e non estritas adoita ignorarse xa que son facilmente interconvertíbeis.

Relacións binarias transitivas

	Simétrica	Antisimétrica	Conexa	Ben fundada	Ten joins	Ten meets	Reflexiva	Irreflexiva	Asimétrica

Relación de equivalencia	Si	Non	Non	Non	Non	Non	Si	Non	Non
Preorde (Cuasiorde)	Non	Non	Non	Non	Non	Non	Si	Non	Non
Orde parcial	Non	Si	Non	Non	Non	Non	Si	Non	Non
Preorde total	Non	Non	Si	Non	Non	Non	Si	Non	Non
Orde total	Non	Si	Si	Non	Non	Non	Si	Non	Non
Pre-Ben ordenada	Non	Non	Si	Si	Non	Non	Si	Non	Non
Cuasi-Ben ordenada	Non	Non	Non	Si	Non	Non	Si	Non	Non
Ben ordenada	Non	Si	Si	Si	Non	Non	Si	Non	Non
Retícula	Non	Si	Non	Non	Si	Si	Si	Non	Non
Semiretícula superior (join)	Non	Si	Non	Non	Si	Non	Si	Non	Non
Semiretícula inferior (meet)	Non	Si	Non	Non	Non	Si	Si	Non	Non
Orde estrita parcial	Non	Si	Non	Non	Non	Non	Non	Si	Si
Orde estrita feble	Non	Si	Non	Non	Non	Non	Non	Si	Si
Orde estrita total	Non	Si	Si	Non	Non	Non	Non	Si	Si
	Simétrica	Antisimétrica	Conexa	Ben fundada	Ten joins	Ten meets	Reflexiva	Irreflexiva	Asimétrica
Definicións, para todo $a,b$ e $S\neq \varnothing :$	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ e }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ ou }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{existe}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}$	$aRa$	${\text{non }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{non }}bRa\end{aligned}}$

Si indica que a columna da propiedade é sempre verdadeira no termo da fila (na esquerda de todo), mentres que

Non indica que a propiedade non está garantida en xeral (pode cumprirse ou non). Por exemplo, toda relación de equivalencia é simétrica, mais non necesariamente antisimétrica, está indicada por

Si na columna "Simétrica" e

Non na columna "Antisimétrica".

Todas as definicións requiren tacitamente que a relación homoxénea $R$ sexa transitiva: para todo $a,b,c,$ se $aRb$ e $bRc$ entón $aRc.$
Algunha definición dalgún termo pode requerir propiedades adicionais non recollidas na táboa.

Todo conxunto ben ordenado ten un isomorfismo de orde en relación a un número ordinal único, chamado tipo de orde do conxunto ben ordenado. O teorema de Zermelo, que é equivalente ao axioma da escolla, afirma que todo conxunto pode estar ben ordenado.

Números ordinais

A observación de que os números naturais están ben ordenados pola relación usual "menor que", chámase comunmente principio de ben ordenado (para os números naturais).

Todo conxunto ben ordenado ten un isomorfismo de orde única a un número ordinal único, chamado tipo de orde do conxunto ben ordenado. A posición de cada elemento dentro do conxunto ordenado tamén vén dada por un número ordinal. No caso dun conxunto finito, a operación básica de contar,asigan un número a cada obxecto. O tamaño (número de elementos, número cardinal) dun conxunto finito é igual ao tipo de orde.^[1] Teña en conta que estes números son un máis que os números ordinais formais segundo a orde isomorfa, porque estes son iguais ao número de obxectos anteriores (o que corresponde a contar desde cero). Así, para $n$ finito, a expresión " $n$ -ésimo elemento" dun conxunto ben ordenado require contexto para saber se isto conta desde cero ou un. Nunha notación " $β$ -ésimo elemento" onde $β$ tamén pode ser un ordinal infinito, normalmente contará desde cero.

Para un conxunto infinito o tipo de orde determina a cardinalidade, mais non á inversa: hai conxuntos ben ordenados dunha cardinalidade particular que poden ter moitos tipos de orde diferentes (ver § Números naturais, a continuación, por exemplo). Para un conxunto numerábel infinito, o conxunto de posíbeis tipos de orde é incontábel.

Exemplos e contraexemplos

Números naturais

A ordenación estándar ≤ dos números naturais é unha relación ben ordenada e ten a propiedade adicional de que cada número natural distinto de cero ten un único predecesor.

Outra ordenación correcta dos números naturais dáse ao definir que todos os números pares son menores que todos os números impares, e a ordenación habitual aplícase dentro dos pares e dos impares:

{\begin{matrix}0&2&4&6&8&\dots &1&3&5&7&9&\dots \end{matrix}}

Este é un conxunto ben ordenado co tipo de orde $ω + ω$ . Cada elemento ten un sucesor (non hai un elemento máis grande). Dous elementos carecen de predecesor: 0 e 1.

Números enteiros

A diferenza da ordenación estándar ≤ dos números naturais, a ordenación estándar ≤ dos enteiros non é unha relación ben ordenada, xa que, por exemplo, o conxunto de enteiros negativos non contén un elemento menor.

A seguinte relación binaria $R$ é un exemplo de relación ben ordenada dos números enteiros: $x R y$ se e só se cumpre unha das seguintes condicións:

$x = 0$
$x$ é positivo, e $y$ é negativo
$x$ e $y$ son positivos, e $x \leq y$
$x$ e $y$ son negativos, e $| x | \leq | y |$

Esta relación $R$ pódese visualizar do seguinte xeito:

{\begin{matrix}0&1&2&3&4&\dots &-1&-2&-3&\dots \end{matrix}}

$R$ é isomorfa ao número ordinal $ω + ω$ .

Outra relación ben ordenada dos números enteiros é a seguinte definición: $x\leq _{z}y$ se e só se

|x|<|y|\qquad {\text{ou}}\qquad |x|=|y|{\text{ e }}x\leq y.

Esta relación ben ordenada pódese visualizar do seguinte xeito:

{\begin{matrix}0&-1&1&-2&2&-3&3&-4&4&\dots \end{matrix}}

Esta ten o tipo de orde $ω$ .

Reais

A ordenación estándar ≤ de calquera intervalo real non é unha relación ben ordenada, xa que, por exemplo, o intervalo aberto $(0,1)\subseteq [0,1]$ non contén un elemento menor. A partir dos axiomas ZFC da teoría de conxuntos (incluíndo o axioma de escolla) pódese demostrar que hai unha relación ben ordenada dos reais. Tamén Wacław Sierpiński demostrou que ZF + GCH (a hipótese do continuo xeneralizada) implica o axioma da escolla e, polo tanto, unha relación ben ordenada dos reais. No entanto, é posíbel demostrar que os axiomas ZFC+GCH en solitario non son abondo para demostrar a existencia nos reais dunha relación ben ordenada definíbel (por unha fórmula).^[2] No entanto, é coherente con ZFC que existe unha relación ben ordenada definíbel dos reais; por exemplo, é consistente con ZFC que V=L (axioma de construtibilidade), e de ZFC+V=L se desprende que unha fórmula particular ordena ben os reais, ou de feito calquera conxunto.

Un subconxunto incontábel dos números reais coa ordenación estándar ≤ non pode ser unha conxunto ben ordenado Por outra banda, un subconxunto numerábel infinito dos reais pode ser ou non ben ordenado co estándar ≤ . Por exemplo,

Os números naturais están ben ordenados baixo a ordenación estándar ≤.
O conxunto $\{1/n\,|\,n=1,2,3,\dots \}$ non ten menor elemento e, polo tanto, non están ben ordenados baixo a ordenación estándar ≤.

Formulacións equivalentes

Se un conxunto está totalmente ordenado, entón os seguintes son equivalentes entre si:

O conxunto está ben ordenado. É dicir, cada subconxunto non baleiro ten un elemento menor.
A indución transfinita funciona para todo o conxunto ordenado.
Toda secuencia estritamente decrecente de elementos do conxunto debe terminar despois dun número finito de pasos (asumindo o axioma da escolla dependente ).
Toda suborde é isomorfa a un segmento inicial.

Topoloxía de orde

Todo conxunto ben ordenado pódese converter nun espazo topolóxico dotándoo da topoloxía de orde.

Con respecto a esta topoloxía pode haber dous tipos de elementos:

puntos illados: estes son os mínimos e os elementos cun antecesor.
puntos límite: este tipo non aparece en conxuntos finitos, e pode ou non ocorrer nun conxunto infinito; os conxuntos infinitos sen punto límite son os conxuntos de tipo de orde $ω$ , por exemplo os números naturais $\mathbb {N} .$

Para os subconxuntos podemos distinguir:

Subconxuntos cun máximo (é dicir, subconxuntos que están limitados en si mesmos); este pode ser un punto illado ou un punto límite de todo o conxunto; neste último caso pode ser ou non tamén un punto límite do subconxunto.
Subconxuntos que non están limitados en si mesmos mais están limitados no conxunto completo; non teñen un máximo mais si teñen un supremo fóra do subconxunto; se o subconxunto non está baleiro este supremo é un punto límite do subconxunto e, polo tanto, tamén do conxunto completo; se o subconxunto está baleiro este supremo é o mínimo de todo o conxunto.
Subconxuntos que son ilimitados en todo o conxunto.

Un subconxunto é cofinal en todo o conxunto se e só se é ilimitado en todo o conxunto ou ten un máximo que tamén é máximo de todo o conxunto.

Un conxunto ben ordenado como espazo topolóxico é un primeiro espazo contábel se e só se ten un tipo de orde menor ou igual a ω₁ (omega-uno), é dicir, se e só se o conxunto é contábel ou ten o menor número dentro dos tipos de orde incontábeis.

Notas

↑ Bonnet, Rémi; Finkel, Alain; Haddad, Serge; Rosa-Velardo, Fernando (2013). "Ordinal theory for expressiveness of well-structured transition systems". Information and Computation 224: 1–22. MR 3016456. doi:10.1016/j.ic.2012.11.003.
↑ Feferman, S. (1964). "Some Applications of the Notions of Forcing and Generic Sets". Fundamenta Mathematicae 56 (3): 325–345. doi:10.4064/fm-56-3-325-345.

Véxase tamén

Bibliografía

Folland, Gerald B. (1999). Real Analysis: Modern Techniques and Their Applications. Pure and applied mathematics (2nd ed.). Wiley. pp. 4–6, 9. ISBN 978-0-471-31716-6.

Outros artigos

Ligazóns externas

Encyclopedia of mathematics.

[1] Bonnet, Rémi; Finkel, Alain; Haddad, Serge; Rosa-Velardo, Fernando (2013). "Ordinal theory for expressiveness of well-structured transition systems". Information and Computation 224: 1–22. MR 3016456. doi:10.1016/j.ic.2012.11.003.

[2] Feferman, S. (1964). "Some Applications of the Notions of Forcing and Generic Sets". Fundamenta Mathematicae 56 (3): 325–345. doi:10.4064/fm-56-3-325-345.

[1]

[2]