Construir un operador de conjunto de punto fijo

Question

Cómo encontrar un conjunto incontable $S$ y construir una función $f : 2^S \longrightarrow S$ tal que para cualquier $T \subseteq S$ , $f \left( T \right) \in T$ ?

por ejemplo, que $S =\mathbb{R}$ ¿Cómo puedo construir una función $f$ , como por ejemplo que para cada conjunto $T \subseteq \mathbb{R}$ , $f \left( T \right) \in T$ ?

podemos encontrar algún ejemplo erróneo:

dejar $T =$ {1.9, 1.99, 1.999, 1.9999, ....}

observe que si $F \left( T \right) = \max \left( T \right)$ entonces $\max \left( T \right) \notin T$

o $F \left( T \right) = \sup \left( T \right)$ pero $\sup \left( T \right) = 2 \notin T$

Tal vez el teorema del buen orden sea útil, T puede estar bien ordenado, así que podemos encontrar un elemento mínimo $t \in T$ . Sin embargo, no se trata de una función constructiva, no sabemos cuál es el elemento $t$ es.
Entonces, ¿cómo puedo "construir" ¿una función satisface las condiciones indicadas anteriormente?

Answer 1

La respuesta de Andrej Bauer demuestra, en ZF, que cualquier conjunto con una función de elección puede estar bien ordenado. Esta prueba requiere la lógica clásica, ya que la definición de $g$ requiere que $T=S$ o $T\neq S$ . Pero Peter Freyd ha demostrado que el mismo resultado es cierto en los topoi, donde la lógica interna es intuicionista. La prueba, que implica bastante más trabajo que la clásica, está en su artículo "Choice and well-ordering" [Annals of Pure and Applied Logic 35 (1987) pp.149-166]. Una versión de la prueba que no menciona los topoi pero que funciona directamente en la lógica intuicionista de orden superior (es decir, la lógica interna de los topoi) está en mi artículo "Well-ordering and induction in intuitionistic logic and topoi" [en "Mathematical Logic and Theoretical Computer Science", ed. por D. W. Kueker, E. G. K. Lopez-Escobar, y C. H. Smith, Marcel Dekker Lecture Notes in Pure and Applied Mathematics 106 (1987) pp. 29-48].

Answer 2

Obviamente quieres decir "para cada no vacío $T$ ". A partir de una función de elección se puede construir un bien-orden de $S$ por lo que "construir" una función de elección es lo mismo que "construir" una orden de pozo.

Utilice el conjunto $\omega_1$ el conjunto de ordinales contables. Está bien ordenado por $\in$ .

Como alternativa, considere el conjunto $W$ de todos los subconjuntos bien ordenados de los números racionales $\mathbb Q$ . Definir dos elementos de $W$ como equivalentes si existe un isomorfismo de orden entre ellos. Dividir $W$ por esta relación de equivalencia y se obtiene un conjunto bien ordenado.

Answer 3

Evidentemente, tenemos que enmendar su pregunta considerando sólo el no vacío subconjuntos, ya que no podemos encontrar un elemento del conjunto vacío. Denotemos el conjunto de subconjuntos no vacíos de $S$ con $P_{+}(S)$ .

Llamemos a una función $f : P_{+}(S) \to S$ a elección función si $f(T) \in T$ para todos $T$ . Usted pregunta cómo construir una función de elección para un incontable $S$ por una vaga noción de "construcción". Parece que no tiene suerte porque dicha función nos da una ordenación de $S$ . Por ejemplo, tenemos:

Teorema: (ZF) Un conjunto $S$ tiene una función de elección si, y sólo si, puede estar bien ordenada.

Prueba. Esto es bien conocido. En una dirección, si $\leq$ es una buena ordenación de $S$ definir una función de elección $f(T) = \min_{\leq} T$ . A la inversa, supongamos que existe una función de elección $f$ . Considere la familia $W$ cuyos elementos son $(T, {\leq})$ donde $T \in P_{+}(S)$ y $\leq$ es una buena ordenación de $T$ . Pida $W$ por "es un segmento inicial de". Entonces $W$ es un poset completo en cadena. Utilizando $f$ podemos definir una función progresiva $g : W \to W$ por:

• si $T = S$ entonces deja que $g(S, {\leq}) = (S, {\leq})$ ,
• si $T \neq S$ entonces deja que $g(T, {\leq}) = (T \cup \lbrace f(S \setminus T) \rbrace, {\leq}')$ donde ${\leq}'$ es $\leq$ con $f(S \setminus T)$ adjunta al final.

Por el Teorema de Bourbaki-Witt $g$ tiene un punto fijo. Pero esto sólo puede ser un bien ordenado de $S$ por definición de $g$ . QED.

Sin embargo, este no es el final de la historia. Es concebible que podamos tener una función de elección "explícita" que no dé un bien explícito porque pasa por la demostración del teorema de Bourbaki-Witt. Todas las pruebas que conozco hacen algo ofuscado.

Así que hay dos preguntas:

1. Cómo precisar la siguiente pregunta: ¿Da cada función de elección una descripción explícita de un pozo en términos de la función?
2. ¿Tiene la pregunta una respuesta positiva?