Demostrar que para cualquier poset infinita es un subconjunto infinito que es antichain o bien linealmente ordenado.

Question

Deje $(X, \leq)$ ser un infinito poset. Demostrar que hay un infinito $X' \subset X$ para que sostiene uno de los siguientes:

1) Inducida por el orden en $X'$ es lineal.

2) $(X', \leq_\mathrm{ind})$ es antichain. (Cada dos elementos en $X'$ son incomparables)

---

Mi intento:

Vamos a empezar a intentar construir un linealmente conjunto ordenado $(X', \leq_\mathrm{ind})$ elemento por elemento. En primer lugar tomamos algún elemento $x_1 \in X$, después tomamos otro $x_2 \in X$ como $x_1 \leq x_2$ o $x_2 \leq x_1$. Básicamente, tomamos un elemento de $X$, si es "buena", la ponemos en nuestra cadena, de lo contrario la tiramos. Continuamos con la construcción de la cadena de esa manera. Si no nos detenemos en algún paso finito, entonces hemos terminado, hemos construido linealmente subconjunto ordenado.

Si no nos detenemos en algunos $x_n$ eso significa que tenemos cantidad finita de elementos comparables, lo que significa que $X \setminus X'$ es un antichain.

---

a) no estoy seguro acerca de la solidez en el último paso, podría alguien por favor comprobarlo?

b) Puede ser probado sin una función de elección?

Answer 1

Si también se exige que la cadena infinita o anti-cadena ser máxima, entonces sí necesitamos el axioma de elección. De hecho, el lema de Zorn es una herramienta útil a la hora de encontrar la máxima cadenas y anti-cadenas.

Hay un principio de elección llamado Hausdorff del maximality principio que establece que en cada conjunto parcialmente ordenado existe una máxima de cadena. También es equivalente al axioma de elección, de modo que cuando usted le niega el axioma de la opción de agregar un conjunto parcialmente ordenado sin una máxima de cadena.

Para el anti-cadenas existe un principio similar, que también implica el axioma de elección.

Si simplemente desea encontrar un infinito anti-cadena o cadena, algunos axioma de elección puede ser necesaria. De hecho, hay árboles que cada rama puede ser extendida, pero no es infinito rama (por lo tanto no hay cadena infinita).

Por otro lado, existe un modelo de ZF suponiendo cierta cantidad finita de elección, en el cual existe un conjunto parcialmente ordenado que es infinito, pero no tiene cadenas infinitas o anti-cadenas.

La prueba es bastante complicado, pero aparece en Jech, El Axioma de Elección como el modelo dado en el Teorema 7.11 (p. 107) y en el ejercicio 7.14 (p. 115)

---

La prueba es bien para la mayoría, asumiendo el axioma de elección (o al menos El Principio de Dependiente de la Elección). Sin embargo, si sólo se retire un número finito de elementos comparables no tenemos que tener un anti-cadena de la izquierda.

Dicotomía pruebas deben demostrar que si la condición de que he fallado, a continuación, condición II sostiene. Y, en efecto, supongamos que $X$ es infinito, pero cada cadena es finita. Definimos una secuencia de elementos $x_n\in X$ por inducción:

Deje $x_0\in X$ ser un elemento que $X_0=\{x\in X\mid x\nleq x_0\land x_0\nleq x\}$ es infinito. Si no hay ningún elemento tiene esta propiedad, podemos utilizar el mismo inducción para definir una cadena infinita (tomando todos los elementos comparables con $x_0$ lugar).

Supongamos $x_n$ $X_n$ fueron definidos, vamos a $x_{n+1}\in X_n$ ser tal que $X_{n+1}=\{x\in X_n\mid x\nleq x_{n+1}\land x_{n+1}\nleq x\}$ es infinito. Si nos quedamos atrapados en el $n$-ésima etapa (que es $X_{n+1}$ es finito para cada $x\in X_n$), entonces podemos definir una cadena infinita *dentro de $X_n$* por el mismo en la inducción como en el primer paso.

Yo reclamo que $\{x_n\mid n\in\mathbb N\}$ es un infinito anti-cadena. Primera nota de que $\ldots\subsetneq X_n\subsetneq X_{n-1}\subsetneq\ldots\subsetneq X$, e $x_n\in X_{n-1}$$x_0\in X$. Cada una de las $x_n$ definido $X_n$ y los que son únicos por lo $x_n\neq x_k$$n\neq k$.

En segundo lugar, desde la $x_k\in X_{k-1}$ si $x_k$ $x_n$ son comparables y $n<k$$x_k\in X_n$, lo que fue definido como un conjunto de elementos incomparable con $x_n$ a empezar, por lo tanto, tenemos un infinito anti-cadena.

Answer 2

El hecho de que cada infinito de orden parcial tiene una infinita cadena o una infinita antichain tiene una rápida prueba como consecuencia de la infinita teorema de Ramsey, que afirma que cada colorante de pares a partir de un conjunto infinito admite una infinita monocromática subconjunto. Es decir, para cualquier orden parcial, considerar el color de pares como "comparables" o "incomparable", como puede ser el caso para ese par. Por el teorema de Ramsey, hay un infinito monocromática subconjunto, lo que significa que todos los pares desde el subconjunto se le asigna el mismo color, y este subconjunto, por tanto, es una cadena infinita o un infinito antichain.

Mientras tanto, del teorema de Ramsey puede apparantly ser probado utilizando sólo el principio de dependiente de opciones---una débil principio de elección, que permite a uno hacer countably muchas opciones en la sucesión---para la prueba de Ramsey del teorema dado en los enlaces de esta página de la wikipedia, es un argumento inductivo, en cada etapa de la que uno hace countably muchas opciones en la sucesión.

Answer 3

La siguiente prueba no es muy elegante, pero funciona: Vamos a $A$ ser un máximo, finito anti-cadena. Para cada punto de $x\in A$, vamos a $\mathcal{L}(x)$ ser parte de la familia de todas máxima de las cadenas que contienen $x$. Claramente, $\bigcup_{x\in A}\mathcal{L}(x)=X$, por lo $x^*\in A$, la familia $\mathcal{L}(x^*)$ es infinito. Si contiene una cadena infinita, hemos terminado. Supongamos que no. Claramente, debe ser infinitamente muchas cadenas en la $\mathcal{L}(x^*)$ que contienen un elemento menor que $x^*$ o infinitamente muchas cadenas en la $\mathcal{L}(x^*)$ que contienen un elemento mayor que $x^*$. W. l.o.g., suponga que el último. Deje $\mathcal{L}^*(x^*)$ ser el conjunto de todas máxima de las cadenas que contienen $x^*$ que contienen un elemento mayor que $x^*$. Cada cadena en $\mathcal{L}^*(x^*)$ es finito y, por tanto, bien ordenados por $\leq$. Vamos $$\mathcal{T}_?=\bigg\{\{y:y\geq x^*\}\cap L:L\in\mathcal{L}^*(x^*)\bigg\}.$$ Let $\mathcal{T}$ be the family of all initial segments of $\mathcal{T}_?$. Now, $\mathcal{T}$ is an infinite tree. If every node has finite degree, an infinite path and hence chain containing $x^*$ existe por König del Lema, que no puede ser. De modo que existe un nodo con grado infinito. El conjunto de sucesores de este nodo formas infinito anti-cadena.

Answer 4

Uno puede usar un libre ultrafilter para obtener una razonable slick argumento de que minimiza la cantidad de detalle que tiene que tener registro en el costo de la utilización de diferentes consecuencias de CA $-$ el Booleano primer ideal teorema, que es estrictamente más débiles que los de CA independientes y Dependiente de la Elección, que también es suficiente.

Deje $\mathscr{U}$ libre de ultrafilter en $X$. Para cada una de las $x\in X$ deje $C(x)=\{y\in X:x\le y\lor y\le x\}$, y deje $A(x)=X\setminus C(x)=\{y\in X:x\not\le y \land y\not\le x\}$; exactamente uno de $C(x)$ $A(x)$ pertenece a $\mathscr{U}$. Deje $C=\{x\in X:C(x)\in\mathscr{U}\,\}$, y deje $A=X\setminus C=\{x\in X:A(x)\in\mathscr{U}\,\}$. Exactamente uno de $A$ $C$ pertenece a $\mathscr{U}$; sin pérdida de generalidad supongamos que $C\in\mathscr{U}$.

Fix $x_0\in C$, y deje $C_0=C\cap C(x_0)\setminus\{x_0\}\in\mathscr{U}$. Dado $C_n\in\mathscr{U}\,$ algunos $n\in\omega$, elija $x_{n+1}\in C_n$ y deje $C_{n+1}=C_n\cap C(x_{n+1})\setminus\{x_{n+1}\}\in\mathscr{U}\,$; claramente, la construcción pasa a través de a $\omega$ a la producción de una serie $\{x_n:n\in\omega\}$ de los elementos distintos de a $X$. Además, para cualquier $k<n<\omega$ tenemos $x_n\in C_k\subseteq C(x_k)$, lo $\{x_n:n\in\omega\}$ es una cadena infinita en $X$. ($A$ Sido miembro de $\mathscr{U}\,$ en lugar de $C$, la $\{x_n:n\in\omega\}$ sería, por supuesto, han sido un infinito antichain.)

Como JDH ya se ha señalado, esto es, básicamente, la de dos colores el caso de las infinitas teorema de Ramsey, $\kappa\to(\omega)_2^2$. Si uno quería utilizar realmente un gran palo, uno podría batir el problema en la cabeza con la Erdős-Dushnik-teorema de Miller, $\kappa\to(\kappa,\omega)^2$, y a la conclusión de que cualquiera de las $X$ tiene una cadena de cardinalidad $|X|$ o $X$ tiene una infinita antichain. (Aquí los rôles de la cadena y antichain , por supuesto, pueden ser invertidos).