Confundido acerca de la preservación de bienórdenes cuasi-buenos

Question

No entiendo la preservación de bien quasiórdenes, aquí es lo que he pensado:

---

Definición Una relación binaria $R$ en $X$ es un cuasiorden cuando es reflexiva y transitiva.

Definición Un cuasiorden $\le$ es un bien quasiorden cuando satisface cualquiera de las siguientes condiciones equivalentes:

1. (condición de cadena en ninguna parte ascendente) cada secuencia $x_1,x_2,x_3\ldots$ con $\lnot x_1 \le x_2$, $\lnot x_2 \le x_3$, $\ldots$ es finita.
2. (condición de cadena estrictamente descendente) cada cadena estrictamente descendente $\ldots \le x_2 \le x_1$ con $\lnot x_2 \le x_1$, $\lnot x_3 \le x_2$, $\ldots$ es finita.
3. (condición de ideal generado finitamente) todo ideal es generado finitamente. Un ideal $I$ es tal que para todo $x \in I$, $y \in X$ que $x \le y$ implica $y \in I$. Ser generado finitamente significa que $I$ es el ideal más pequeño que contiene algún conjunto finito de puntos.

Teorema Sean $R,S$ bien quasiórdenes en $X$ con $R \subseteq S$ (así que $aRb$ implica $aSb$). Entonces $R$ B.Q.O. implica $S$ B.Q.O.

explicación Intenté probar el teorema usando varias definiciones diferentes, todavía no siento que entiendo la relación.

prueba usando la condición de cadena en ninguna parte ascendente: cualquier cadena ascendente en $S$ es una cadena ascendente en $R$, por lo tanto finita.

condición de cadena estrictamente descendente: No puedo hacer que esta prueba funcione, pero aquí está lo que intenté: (1) Sea $\ldots R x_2 R x_1$ una cadena ascendente en $R$, entonces también es una cadena ascendente en $S$ porque $R$ es más estricto que $S$. (2) Sea $\lnot x_2 S x_1$, $\lnot x_3 S x_2$, $\lnot x_3 S x_2$ entonces esto también se cumple para $R$ porque hay menos relaciones $R$.

Ahora la prueba podría suponer una cadena estrictamente descendente en $S$, entonces o tenemos una cadena estrictamente descendente en $R$ por lo tanto es finita - o la cadena $S$ es infinita y se rompe en infinitas piezas finitas en $R$: Entonces tenemos infinitas relaciones del tipo $\lnot x_{b+1}Rx_b$, y también $x_i R x_{i+1}$ para todos los $i$.

Aunque no veo la contradicción aquí...

condición de ideal generado finitamente: Cualquier ideal $S$ es un ideal $R$ también, por lo tanto generado finitamente.

---

así que intenté probar la preservación para varias definiciones equivalentes diferentes pero no siento que lo entienda más y no pude hacer que la prueba funcionara para una definición. Además, definí un bien quasiorden aquí y se convirtió en no bien-fundado cuando dtldalek lo extendió a un orden total - eso parece ir directamente en contra del teorema.

Así que estoy realmente confundido acerca de esto, ¿cómo debo entender la preservación intuitivamente? ¿y qué debo arreglar en la prueba intermedia? (aunque esa prueba intermedia podría no conducir a ninguna idea en cuyo caso no me importa)

Answer 1

Esto puede que no responda a tu pregunta inmediata pero amplía sobre por qué no necesitas preocuparte por ello.

Recuerda que muchas definiciones interesantes surgen (como aquí) a partir de observaciones de que ciertas condiciones son equivalentes:

• un subgrupo es invariante bajo conjugación si y solo si es el núcleo de algún homomorfismo si y solo si los cosets izquierdos son iguales a los cosets derechos - da origen a la definición de subgrupo normal;
• una familia de vectores es maximal entre las familias linealmente independientes si y solo si es minimal entre las familias generadoras si y solo si es tanto linealmente independiente como generadora - da origen a la definición de base de un espacio vectorial.

Esta - no tan obvia - equivalencia hace que el concepto comprendido por (cada/ todas y cada una de) las condiciones sea interesante y por lo tanto justifica acuñar un nombre para ello mediante una definición. Y debido a que la equivalencia debería al menos ser algo sorprendente y no obvia, al menos un paso en la demostración de la equivalencia típicamente requiere un poco de trabajo no trivial. Como con todos los teoremas, no hay necesidad de reinventar la rueda posteriormente, sino más bien aplicar el teorema.

Por lo tanto, no es necesario usar todas las condiciones equivalentes en una demostración. De hecho, podrías asumir que $S$ es w.q.o. por la condición 2, por ejemplo, y demostrar entonces que $R$ es w.q.o. por la condición 1.

Answer 2

Parte del problema, como señaló Marc van Leeuwen, es que tus definiciones de bien quasi-orden no son del todo correctas. Comienza con un quasi-orden $\le$ (es decir, una relación reflexiva y transitiva) en $X$. Entonces $\langle X,\le\rangle$ es un bien quasi-orden si satisface alguna de las siguientes condiciones equivalentes:

1. Para cualquier secuencia $\langle x_k:k\in\Bbb N\rangle$ en $X$ existen $i,k\in\Bbb N$ tal que $i y $x_i\le x_k$.
2. $\langle X,\le\rangle$ es bien-fundado y no tiene anti-cadenas infinitas. Es decir, no hay ni una secuencia infinita estrictamente decreciente ni un conjunto infinito de elementos incomparables entre sí.
3. $\langle X,\le\rangle$ es bien-fundado, y cada $A\subseteq X$ tiene solo finitos elementos mínimos.
4. Cada secuencia $\langle x_k:k\in\Bbb N\rangle$ en $X$ tiene una subsecuencia ascendente infinita.

Aquí (1)-(3) corresponden más o menos a tus tres condiciones.

Teorema. Supongamos que $\le$ y $\preceq$ son quasi-órdenes en $X$ tal que $x\preceq y$ siempre que $x\le y$. Si $\le$ es un bien quasi-orden, entonces también lo es $\preceq$.

Una demostración usando (2) es totalmente posible.

Prueba. Cualquier anti-cadena en $\langle X,\preceq\rangle$ es una anti-cadena en $\langle X,\le\rangle$, por lo que es inmediato que $\langle X,\preceq\rangle$ no tiene anti-cadenas infinitas.

Ahora supongamos que $\preceq$ no es bien-fundado, y sea $\langle x_k:k\in\Bbb N\rangle$ tal que $x_{k+1}\prec x_k$ para cada $k\in\Bbb N$. Sea $[\Bbb N]^2$ el conjunto de pares no ordenados de enteros no negativos. Define $$\varphi:[\Bbb N]^2\to\{0,1,2\}:\{i,k\}\mapsto\begin{cases}0,&\text{si }i por el teorema de Ramsey hay un $H\subseteq\Bbb N$ infinito tal que $\varphi$ es constante en $[H]^2$. Si el valor de $\varphi$ en $[H]^2$ es $2$, los elementos de $H$ forman una anti-cadena infinita en $\langle X,\le\rangle$, lo cual es imposible. Si el valor de $\varphi$ en $[H]^2$ es $1$, $H$ es una secuencia infinita estrictamente decreciente en $\langle X,\le\rangle$, lo cual también es imposible. Por lo tanto, $x_i\le x_k$ siempre que $i,k\in H$ con $i, y se sigue que $x_i\preceq x_k$ para todos los $i,k\in H$ con $i, contradiciendo la elección de la secuencia $\langle x_k:k\in\Bbb N\rangle$. Por lo tanto, $\preceq$ es bien-fundado. $\dashv$

Answer 3

Encontré la respuesta aquí Gallier, Jean H. (1991), "¿Qué tiene de especial el teorema de Kruskal y el ordinal Γ0? Una encuesta sobre algunos resultados en teoría de la prueba", Ann. Pure Appl. Logic 53 (3):