Dado un poset infinito, demuestre que contiene una cadena infinita o un conjunto infinito totalmente desordenado.

Question

Llevo tiempo dándole vueltas a esto y sigo atascado... He pensado en demostrarlo llegando a una contradicción pero no he llegado a nada digno de mención. Si haces una prueba por contradicción, estás asumiendo que tienes un poset infinito que no contiene una cadena infinita y un conjunto infinito totalmente desordenado pero no sé en qué me ayuda eso :(

Answer 1

Supongo que por conjunto totalmente desordenado te refieres a un anticadena .

Sea $\langle P,\preceq\rangle$ sea su poset, y que $P_0$ sea un subconjunto contablemente infinito de $P$ . $[P_0]^2$ es el conjunto de subconjuntos de dos elementos de $P_0$ . Definir un mapa $c:[P_0]^2\to\{0,1\}$ estableciendo $c(\{x,y\})=1$ si $x$ y $y$ son comparables (es decir $p\preceq q$ o $q\preceq p$ ), y aplicar el teorema de Ramsey infinito .

Answer 2

Una gran edición, debido a un fallo en el post original (gracias Sr. Karagila)

Supongamos que no existen cadenas infinitas. SI (editar) existe un tamaño máximo M de cualquier cadena. Quitar y apartar todos los elementos inferiores (x s.t. no existe y inferior a x). Este subconjunto es totalmente desordenado/anti-cadena. Repetir M veces. El conjunto original queda así dividido en M subconjuntos disjuntos, cada uno totalmente desordenado.

Como M es finito, al menos un subconjunto debe ser infinito, qed

EDITAR. SI no hay límite superior para el tamaño de la cadena.

Considerando sólo las cadenas maximales (necesariamente finitas, posiblemente solapadas, pero que no pueden ampliarse). Si hay una infinidad de cadenas maximales (dos por dos distintas) por debajo de cierta longitud L*, aplicar el argumento anterior al subconjunto representado por su unión, hecho.

Por tanto, el único problema es la situación en la que para cualquier longitud finita sólo hay un número finito de cadenas distintas (máximas) de esa longitud. Entonces tenemos un conjunto infinito de cadenas de longitudes finitas crecientes (C1, C2, etc.), no acotadas anteriormente.

PASO A. De nuevo, trabaja dentro de los límites de su unión (un subconjunto del gran conjunto original), con el orden original. Tomar el conjunto de sus fondos (elementos más bajos), que existen debido a la finitud. El conjunto de los fondos no está ordenado (un fondo no puede ser más pequeño que otro debido a la maximalidad). Si el conjunto de fondos es infinito, hecho. Si el conjunto de fondos es finito, entonces al menos un fondo es un fondo para un número infinito de cadenas distintas (en pares).

Restringir a la unión de las cadenas delimitadas por debajo de este fondo (B1) MENOS B1 (subconjunto SB1). La intersección de las cadenas iniciales (C1, C2, etc) con SB1 da lugar de nuevo a cadenas maximales dentro de SB1.

Repita el paso A, dando como resultado un conjunto infinito de fondos u otro fondo a un número infinito de cadenas (B2). Obsérvese que B2>B1.

Entonces, o el proceso termina encontrando un conjunto infinito de fondos en un número finito de iteraciones del proceso, o creamos una cadena infinita B1 < B2 < B3 < ....

qed.