Relación ben fundada

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.

En matemáticas, unha relación binaria $R$ chámase ben fundada ^[1] nun conxunto ou, máis xeralmente, nunha clase $X$ se todo subconxunto non baleiro $S \subseteq X$ ten un elemento mínimal con respecto a $R$ ; é dicir, existe un $m \in S$ tal que, para todo $s \in S$ , non se ten $s R m$ . Noutras palabras, unha relación está ben fundada se: $(\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].$ Algúns autores inclúen unha condición adicional de que $R$ sexa tipo conxunto, é dicir, que os elementos menores que calquera elemento dado formen un conxunto.

De forma equivalente, asumindo o axioma de escolla dependente, unha relación está ben fundamentada cando non contén cadeas descendentes infinitas, o que se pode demostrar cando non hai unha secuencia infinita $x 0, x 1, x 2, ...$ de elementos de $X$ tales que $x n +1 R x n$ para todo número natural $n$ .^[2]^[3]

Na teoría da orde, unha orde parcial chámase ben fundada se a orde estrita correspondente é unha relación ben fundada. Se a orde é unha orde total, denomínase ben ordenada.

Na teoría de conxuntos, un conxunto $x$ chámase conxunto ben fundado se a relación de pertenza do conxunto está ben fundada no peche transitivo de $x$ . O axioma de regularidade, que é un dos axiomas da teoría de conxuntos de Zermelo-Fraenkel, afirma que todos os conxuntos están ben fundados.

Unha relación $R$ é inversa ben fundada, ben fundada para arriba ou noetheriana en $X$ , se a relación inversa $R -1$ está ben fundada en $X$ . Neste caso tamén se di que $R$ satisfai a condición de cadea ascendente.

Indución e recursividade

Unha razón importante pola que as relacións ben fundadas son interesantes é porque se pode usar nelas unha versión da indución transfinita: se ( $X, R$ ) é unha relación ben fundada, $P (x)$ é algunha propiedade dos elementos de $X$ , e queremos demostrar que

P (x)

cúmprese para todos os elementos

x

de

X

,

abonda con demostrar que:

Se

x

é un elemento de

X

e

P (y)

é verdadeira para todo

y

tal que

y R x

, entón

P (x)

tamén debe ser verdadeira.

É dicir, $(\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implies P(y)]\implies P(x)]\quad {\text{implica}}\quad (\forall x\in X)\,P(x).$

A indución ben fundada chámase ás veces indución noetheriana, ^[4] debido a Emmy Noether.

Ao igual que a indución, as relacións ben fundadas tamén admiten a construción de obxectos mediante recursión transfinita. Sexa $(X, R)$ unha relación ben fundada tipo conxunto e $F$ unha función que asigna un obxecto $F (x, g)$ a cada par dun elemento $x \in X$ e unha función $g$ no segmento inicial ${y : y R x}$ de $X$ . Entón hai unha función única $G$ tal que para cada $x \in X$ , $G(x)=F\left(x,G\vert _{\left\{y:\,y\mathrel {R} x\right\}}\right).$

É dicir, se queremos construír unha función $G$ sobre $X$ , podemos definir $G (x)$ usando os valores de $G (y)$ para $y R x$ .

Como exemplo, considere a relación ben fundamentada $(N, S)$ , onde $N$ é o conxunto de todos os números naturais e $S$ é o grafo da función sucesora $x \mapsto x +1$ . Entón a indución en $S$ é a indución matemática habitual, e a recursión en $S$ dá a recursividade primitiva. Se consideramos a relación de orde $(N, <)$ , obtemos a indución completa e a recursión global. A afirmación de que $(N, <)$ está ben fundada tamén se coñece como principio da boa ordenación .

Cando a relación ben fundada é a orde habitual na clase de todos os números ordinais, a técnica chámase indución transfinita. Cando o conxunto ben fundado é un conxunto de estruturas de datos definidas recursivamente, a técnica chámase indución estrutural. Cando a relación ben fundada pertence á clase universal, a técnica coñécese como ∈-indución (indución epsilon).

Exemplos

As relacións ben fundadas que non son totalmente ordenadas inclúen:

Os enteiros positivos ${1, 2, 3, ...}$ , coa orde definida por $a < b$ se e só se $a$ divide $b$ e $a \neq b$ .
O conxunto de todas as cadeas finitas sobre un alfabeto fixo, coa orde definida por $s < t$ se e só se $s$ é unha subcadea propia de $t$ .
O conxunto $N \times N$ de pares de números naturais, ordenados por $(n 1, n 2) < (m 1, m 2)$ se e só se $n 1 < m 1$ e $n 2 < m 2$ .
Toda clase cuxos elementos son conxuntos, coa relación ∈ ("é un elemento de"). Este é o axioma da regularidade.
Os nós de calquera grafo acíclico finito dirixido, coa relación $R$ definida de tal xeito que $a R b$ se e só se hai unha aresta de $a$ a $b$ .

Exemplos de relacións que non están ben fundadas inclúen:

Os enteiros negativos ${-1, -2, -3, ...}$ , coa orde habitual, xa que calquera subconxunto non limitado non ten menor elemento.
O conxunto de cadeas sobre un alfabeto finito con máis dun elemento, baixo a orde habitual (lexicográfica), xa que a secuencia "B" > "AB" > "AAB" > "AAAB" > ... é unha cadea descendente infinita. Esta relación non está ben fundada aínda que todo o conxunto teña un elemento mínimo, é dicir, a cadea baleira.
O conxunto de números racionais (ou reais) non negativos baixo a orde estándar, xa que, por exemplo, o subconxunto de racionais (ou reais) positivos carece dun mínimo.

Outras propiedades

Se $(X, <)$ é unha relación ben fundada e $x$ é un elemento de $X$ , entón as cadeas descendentes que comezan en $x$ son todas finitas, mais isto non significa que as súas lonxitudes estean necesariamente limitadas. Considere o seguinte exemplo: Sexa $X$ a unión dos enteiros positivos cun novo elemento ω que é maior que calquera número enteiro. Entón $X$ é un conxunto ben fundado, mais hai cadeas descendentes que comezan en ω de gran lonxitude (finita) arbitraria; a cadea $ω, n - 1, n - 2, ..., 2, 1$ $ω, n - 1, n - 2, ..., 2, 1$ ten lonxitude $n$ para calquera $n$ .

O lema do colapso de Mostowski implica que a pertenza do conxunto é un universal entre as relacións de extensión ben fundadas: para calquera relación ben fundada de tipo conxunto $R$ nunha clase $X$ que é extensional, existe unha clase $C$ tal que $(X, R)$ é isomorfa a $(C, \in)$ .

Reflexividade

Dise que unha relación $R$ é reflexiva se $a R a$ vale para todo $a$ no dominio da relación. Toda relación reflexiva nun dominio non baleiro ten cadeas descendentes infinitas, porque calquera secuencia constante é unha cadea descendente. Por exemplo, nos números naturais coa súa orde habitual ≤, temos 1 ≥ 1 ≥ 1 ≥ ... . Para evitar estas secuencias descendentes triviais, cando se traballa cunha orde parcial ≤, é común aplicar a definición de fundamento (quizais implícitamente) á relación alternativa < definida de tal xeito que $a < b$ se e só se $a \leq b$ e $a \neq b$ . De xeito máis xeral, cando se traballa cunha preorde ≤, é común usar a relación < definida de tal xeito que $a < b$ se e só se $a \leq b$ e $b ≰ a$ . No contexto dos números naturais, isto significa que se usa a relación <, que está ben fundada, en lugar da relación ≤, que non o é. Nalgúns textos, a definición dunha relación ben fundada múdase desde a definición deste artigo para incluír estas convencións.

Notas

↑ vexa a definición 6.21 en Zaring W.M., G. Takeuti (1971). Introduction to axiomatic set theory (2nd, rev. ed.). New York: Springer-Verlag. ISBN 0387900241.
↑ "Infinite Sequence Property of Strictly Well-Founded Relation". ProofWiki. Consultado o 10 May 2021.
↑ Fraisse, R. (15 December 2000). Theory of Relations, Volume 145 - 1st Edition (1st ed.). Elsevier. p. 46. ISBN 9780444505422. Consultado o 20 February 2019.
↑ Bourbaki, N. (1972) Elements of mathematics. Commutative algebra, Addison-Wesley.

Véxase tamén

Bibliografía

Just, Winfried and Weese, Martin (1998) Discovering Modern Set Theory. I, American Mathematical Society ISBN 0-8218-0266-6.
Karel Hrbáček & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, "Well-founded relations", pages 251–5, Marcel Dekker ISBN 0-8247-7915-0

Outros artigos

[1] vexa a definición 6.21 en Zaring W.M., G. Takeuti (1971). Introduction to axiomatic set theory (2nd, rev. ed.). New York: Springer-Verlag. ISBN 0387900241.

[2] "Infinite Sequence Property of Strictly Well-Founded Relation". ProofWiki. Consultado o 10 May 2021.

[3] Fraisse, R. (15 December 2000). Theory of Relations, Volume 145 - 1st Edition (1st ed.). Elsevier. p. 46. ISBN 9780444505422. Consultado o 20 February 2019.

[4] Bourbaki, N. (1972) Elements of mathematics. Commutative algebra, Addison-Wesley.

[1]

[2]

[3]

[4]