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?

  • $\begingroup$ Hm, it feels like there is no such function, if it do not use well-ordering principle or axiom of choice. The number of constructive functions are countable, but your input data is uncountable, which somehow hints that every constructive function can be "destroyed" by some diagonal argument... What if you do the following construction: start with $S_1=\mathbb{R}$ and let $S_{n+1}=S_n \setminus f(S_n).$ It feels like the series $f(S_1),f(S_2),\dots$ is a very strange set of points, and is this set computable? $\endgroup$ – Per Alexandersson Dec 9 '12 at 10:41
  • $\begingroup$ I do not understand the title of your question: "Construct a fixed-point set operator". A fixed point of a function $f$ is a point $x$ satisfying $f(x)=x$. $\endgroup$ – Goldstern Dec 9 '12 at 11:52
  • 1
    $\begingroup$ Your tag "real-analysis" seems to indicate that you are interested in subsets of the real line. If so, please state this clearly. If not, please remove the tag. $\endgroup$ – Goldstern Dec 9 '12 at 11:54

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].

  • $\begingroup$ Ah, excellent, thanks for the references. $\endgroup$ – Andrej Bauer Dec 10 '12 at 1:26

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.


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?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.