Question

How to find an uncountable set $S$, and construct an function $f : 2^S \longrightarrow S$ such that for any $T \subseteq S$, $f \left( T \right) \in T$?

for example, let $S =\mathbb{R}$, how can I construct a funciton $f$, such that for every set $T \subseteq \mathbb{R}$, $f \left( T \right) \in T$?

we can find some wrong example:

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

observe that if $F \left( T \right) = \max \left( T \right)$, then $\max \left( T \right) \notin T$

or $F \left( T \right) = \sup \left( T \right)$, but $\sup \left( T \right) = 2 \notin T$

Maybe the well-ordering theorem is helpful, T can be well-ordered, so we can find an least element $t \in T$. However, this is not a constructive function, we don't know what the element $t$ is.
So how can I "construct" a function satisfies the conditions stated above?

Answer 1

Andrej Bauer's answer shows, in ZF, that any set with a choice function can be well-ordered. This proof requires classical logic, as the definition of $g$ requires that $T=S$ or $T\neq S$. But Peter Freyd has proved that the same result is true in topoi, where the internal logic is intuitionistic. The proof, which involves considerably more work than the classical one, is in his paper "Choice and well-ordering" [Annals of Pure and Applied Logic 35 (1987) pp.149-166]. A version of the proof that doesn't mention topoi but works directly in intuitionistic higher-order logic (i.e., the internal logic of topoi) is in my paper "Well-ordering and induction in intuitionistic logic and topoi" [in "Mathematical Logic and Theoretical Computer Science", ed. by D. W. Kueker, E. G. K. Lopez-Escobar, and C. H. Smith, Marcel Dekker Lecture Notes in Pure and Applied Mathematics 106 (1987) pp. 29-48].

Answer 2

Obviously you mean "for every nonempty $T$". From a choice function one can construct a well-order of $S$, so "constructing" a choice function is the same as "constructing" a well-order.

Use the set $\omega_1$, the set of countable ordinals. It is well-ordered by $\in$.

Alternatively, consider the set $W$ of all well-ordered subsets of the rational numbers $\mathbb Q$. Define two elements of $W$ as equivalent if there is an order isomorphism between them. Divide $W$ by this equivalence relation and you get a well-ordered set.

Answer 3

Clearly, we have to amend your question by considering only the non-empty subsets, as we cannot find an element of the empty set. Let me denote the set of non-empty subsets of $S$ with $P_{+}(S)$.

Let us call a function $f : P_{+}(S) \to S$ a choice function if $f(T) \in T$ for all $T$. You are asking how to construct a choice function for an uncountable $S$, for some vague notion of "construct". It looks like you are out of luck because such a function gives us a well-ordering of $S$. For example, we have:

Theorem: (ZF) A set $S$ has a choice function if, and only if, it can be well-ordered.

Proof. This is well known. In one direction, if $\leq$ is a well-ordering of $S$, define a choice function $f(T) = \min_{\leq} T$. Conversely, suppose there is a choice function $f$. Consider the family $W$ whose elements are $(T, {\leq})$ where $T \in P_{+}(S)$ and $\leq$ is a well-ordering of $T$. Order $W$ by "is an initial segment of". Then $W$ is a chain complete poset. Using $f$ we may define a progressive function $g : W \to W$ by:

• if $T = S$ then let $g(S, {\leq}) = (S, {\leq})$,
• if $T \neq S$ then let $g(T, {\leq}) = (T \cup \lbrace f(S \setminus T) \rbrace, {\leq}')$ where ${\leq}'$ is $\leq$ with $f(S \setminus T)$ attached at the end.

By the Bourbaki-Witt theorem $g$ has a fixed point. But this can only be a well-order of $S$, by definition of $g$. QED.

This is not the end of the story, however. It is conceivable that we could have an "explicit" choice function which does not give an explicit well-orering because it passes through the proof of the Bourbaki-Witt theorem. Every proof I am aware of does something obfuscating.

So there are two questions:

1. How to make the following question precise: Does every choice function give an explicit description of a well-order in terms of the function?
2. Does the question have a positive answer?