Supongamos que tengo un conjunto junto con una relación que es un orden total. El conjunto no tiene ningún elemento mínimo. Ahora, quiero crear una secuencia infinita decreciente de elementos en este conjunto. Para ello tengo que utilizar el axioma de elección. Pero no soy capaz de averiguar de qué familia de conjuntos debo escoger los elementos para poder utilizar el AoC.
Respuestas
¿Demasiados anuncios?
Para cada $x\in X$ , dejemos que $L_x = \{y\in X \mid y\lt x\}$ . Lleva a la familia $\{L_x\}_{x\in X}$ . Sea $f$ sea un elemento de $\prod_{x\in X}L_x$ .
Ahora escoge $x_1\in X$ . Utilice el teorema de recursión para definir una función $g\colon\mathbb{N}\to X$ dejando $g(1) = x_1$ y dejar que $g(n+1) = f(g(n))\in L_{g(n)}$ . La secuencia que desea es $x_i=g(i)$ .
De hecho, no es necesario todo el AC para hacer lo anterior, basta con utilizar el Axioma de la elección dependiente que está implícito, pero no es equivalente, al Axioma de Elección completo. Demostrando que realmente Necesito ADC para el resultado general (en lugar de mostrar que basta con usarlo) requiere argumentos en la línea de la respuesta de Asaf.
DanV
Puntos
281
Consideremos todos los ordinales que se pueden incrustar en el orden inverso, es decir, el tipo de orden que forma cadenas decrecientes en el orden lineal.
Dejemos que $\alpha$ sea el supremum de todos los ordinales. Si $\alpha<\omega$ entonces hay un elemento mínimo; si $\alpha>\omega$ entonces podemos integrar inversamente $\omega$ y tener la cadena.
Si $\alpha=\omega$ entonces podemos utilizar el lema de Zorn como sigue:
Tomemos todas las cadenas decrecientes ordenadas por extensión. Toda cadena está acotada ya que la unión de dichas cadenas da una secuencia decreciente. Por tanto, existe un elemento máximo. Como sabemos que una cadena finita puede ser extendida por otro elemento (si no existe un elemento mínimo) el elemento máximo tiene una longitud infinita.
Como ha comentado Arturo esto se puede hacer con Axioma de la elección dependiente que es una versión restringida del lema de Zorn para órdenes parciales cuya altura es $\omega$ .
Para ver que el axioma de elección es necesario, tomemos el modelo básico de Cohen, es decir, añadamos un conjunto Dedekind-finito de reales. Este conjunto está totalmente ordenado, es ilimitado y no tiene ningún subconjunto contable. En particular, no podemos encontrar una secuencia contable en este conjunto totalmente ordenado.
La fuerza de elección exacta es en realidad la sugerida por Arturo en los comentarios como un fragmento del Principio de Elección Dependiente.
Dejemos que $\operatorname{DC}_{\operatorname{lin}}$ sea la afirmación de que todo ordenamiento lineal en el que se puede extender toda cadena finita tiene un $\omega$ -secuencia.
Claramente, $\operatorname{DC}\Rightarrow\operatorname{DC}_{\operatorname{lin}}$ , como $\operatorname{DC}$ habla también de órdenes no lineales.
En primer lugar, hay que tener en cuenta que es obvio que $\operatorname{DC}_{\operatorname{lin}}$ implica que un ordenamiento que no está acotado desde abajo tiene una $\omega$ -secuencia. Invirtiendo el orden, como toda secuencia finita (creciente) puede extenderse (si no llegamos a un máximo) tenemos una $\omega$ -secuencia; invierte el orden de nuevo y ahí lo tenemos.
Por otro lado, si $\operatorname{DC}_{\operatorname{lin}}$ no se cumple entonces hay un orden lineal tal que toda secuencia finita creciente puede ser extendida pero no hay $\omega$ -de la secuencia. En particular, la inversa de dicho orden será un ordenamiento lineal sin ningún elemento menor, que no tiene decreciente $\omega$ -secuencia.
Pregunta I: Supongamos que ZF+Existe un conjunto amorfo. Como los conjuntos amorfos no pueden ser ordenados linealmente no pueden ser utilizados como contraejemplos de $\operatorname{DC}_{\operatorname{lin}}$ .
¿Puede haber un modelo de ZF+Existe un conjunto amorfo+ $\operatorname{DC}_{\operatorname{lin}}$ ? ¿Podemos relajar el requisito de amorfo a un conjunto infinito Dedekind-finito?
Pregunta II: ¿Podemos tener un modelo de ZF+$ \operatorname {DC} {\i1}Nombre del operador{\i} {\i1}Línea{\i} {\i} $+$ \No se trata de un nombre de operador. \omega $?
Este es un modelo en el que ZF se mantiene, $\operatorname{DC}_{\operatorname{lin}}$ se mantiene pero hay una familia contable de conjuntos sin función de elección.
Hurkyl
Puntos
57397
Si quieres aplicar directamente el axioma de la elección, presta mucha atención a lo que eliges:
- En primer lugar, se elige un elemento $x_0 \in X$
- En segundo lugar, has elegido un elemento $x_1 \in \{ a \in X \mid a < x_0 \}$
Presta mucha atención al segundo punto: ¡no estamos eligiendo realmente un elemento de un conjunto! En su lugar, estamos eligiendo entre una función valorada por el conjunto de $x_0$ y así $x_1$ realmente debería ser una función de $x_0$ ¡!
Ahora está claro cómo aplicar la elección.
- En primer lugar, usted elige $x_0 \in x$
- En segundo lugar, usted elige $f_1$ del subconjunto $S_1$ de las funciones $X \to X$ Satisfaciendo a $f(a) < a$
- En tercer lugar, usted elige $f_2$ del subconjunto $S_2$ de las funciones $X \times S_1 \to X$ Satisfaciendo a $g(a,f) < a$ y $g(a,f) < f(a)$
- ...
Pero para facilitarnos las cosas, voy a simplificar:
- En primer lugar, usted elige $x_0 \in X$
- En segundo lugar, usted elige $f_1 : X \to X$ Satisfaciendo a $f(a) < a$
- En tercer lugar, usted elige $f_2 : X^2 \to X$ Satisfaciendo a $f(a,b) < a$ y $f(a,b) < b$
- ...
Ahora, cada uno de nuestros conjuntos está completamente determinado. Podemos demostrar que no son vacíos (invocando la inducción y la elección), y así podemos aplicar la elección a la colección.
Finalmente, nuestra secuencia es:
- $x_0$
- $x_1 = f_1(x_0)$
- $x_2 = f_2(x_0, x_1)$
- ...
EDIT: sólo para hacerlo explícito, la versión simplificada define los conjuntos $S_n$ para ser el conjunto de funciones $g : X^n \to X$ Satisfaciendo a $g(\vec{x}) < x_i$ para todos $1 \leq i \leq n$ .
(Dependiendo de sus gustos, es posible que quiera hacer un caso especial $S_0 = X$ )
Para elegir $g \in S_n$ el valor $g(\vec{x})$ debe interpretarse como "la elección que haría en el momento $n$ si hubiera hecho previamente las elecciones $x_0, x_1, \ldots, x_{n-1}$ a veces $0, 1, \ldots, n-1$ ".
Ahora aplique el axioma de elección para obtener una familia de elecciones $f_n \in S_n$ . Según la interpretación prevista, nuestra secuencia decreciente elegida es
$$x_n = f_n(x_0, x_1, \ldots, x_{n-1})$$
(Si es una carcasa especial $0$ entonces $x_0 = f_0$ en su lugar)
Por supuesto, si bien este enfoque es sistemático, no condujo al resultado más sencillo. En algún momento podríamos haber reconocido que nuestra elección en el momento $n$ podría hacerse depender únicamente de la elección realizada en el momento $n-1$ en lugar de toda la familia de decisiones tomadas a veces $0$ a través de $n-1$ . Y si lo hacemos, puede que entonces nos hayamos dado cuenta de que una única opción serviría para todos los tiempos positivos. Esto daría lugar a la respuesta de Arturo.
