I have a proof of the following theorem:

Let A be a finite set and X be a perfectly normal topological space, and let $\{(A,\succsim_x): x\in X\}$ be a family of binary relations on $A$ satisfying certain conditions. Then there exists $g: A\times X \rightarrow \mathbb R $ such that $g(a,\cdot)$ is continuous for all $a$ in $A$ and for each $x$ in $X$, $a\succsim_x b$ if and only if $g(a,x) \geq g(b,x)$.

Aside: The proof proceeds by standard induction and uses finiteness of $A$ to obtain lower semi-continuity of the lower envelope of lower semi-continuous functions together with Michael's selection theorem for continuity of $g(a,\cdot)$.

I then claim that, by the axiom of choice, I can extend to the case of countable $A$ by the following argument:

First I well order $A$ and then let $\{A_n\}_{n\in \mathbb N}$ be the collection of initial segments of $A$ (that is $\lvert A_n\rvert=n-1$ for each $n$ and $n\leq m$ implies $A_n \subseteq A_m$). Then $\lim_n A_n =A$ and the above theorem holds on each $A_n$, and by finite induction I can find a sequence of functions $f_n: A_n\times X\rightarrow \mathbb R$, each with the same properties as the $g$ above, and moreover such that $n\leq m$ implies $f_n(a,\cdot)=f_m(a,\cdot)$ for all $a$ in $A_n$.

Let $a_n$ be the maximal element of $A_n$ for each $n\geq 2$. By the axiom of (countable) choice, I can choose $h:A\times X \rightarrow \mathbb R$ such that for each $n$, $h(a_n,\cdot):= f_n(a_n,\cdot)$, and moreover, the above theorem now holds for $h$, that is $h(a,\cdot)$ is continuous for each $a$ and $h(\cdot,x)$ order preserving for each $x$.

My question is:

Is there anything wrong with this use of the axiom of choice?

  • 1
    $\begingroup$ There is a $g$ appearing out of nowhere somewhere in your question. $\endgroup$ – Asaf Karagila Nov 19 '13 at 14:38
  • 1
    $\begingroup$ Side note: what is the maximal element of $A_1=\emptyset$? Also, out of curiosity, what are the "certain conditions" you refer to in the first paragraph? $\endgroup$ – Cameron Buie Nov 19 '13 at 15:01
  • $\begingroup$ The conditions are that each relation is transitive and total, and the sets $\{x:a\succ_x b\}$ are open. $\endgroup$ – Patrick Nov 19 '13 at 15:10
  • 4
    $\begingroup$ This title really have to be replaced by something else. $\endgroup$ – Asaf Karagila Nov 19 '13 at 19:01

If you really can choose the functions $f_n$ so that they are compatible, then the argument is legitimate. If you can actually define them so that they are compatible, rather than merely show that they exist, you don’t need any choice; otherwise, you probably need the axiom of dependent choice. The hypothesis that $A$ is countably infinite already ensures that it has an enumeration $A=\{a_n:n\in\Bbb N\}$, ordinary recursion (possibly using dependent choice) gives you the sequence of functions $f_n$ for $n\in\Bbb N$, and the desired function $h$ is simply $\bigcup_{n\in\Bbb N}f_n$. However, it is crucial that you be able to define the functions $f_n$ so that $f_n\upharpoonright A_m=f_m$ whenever $m\le n$.

  • 2
    $\begingroup$ If one can define the functions $f_n$ coherently, then indeed there is no need for the axiom of choice. But I can imagine a situation where one can prove that, for each appropriate $f_m$, there exists an appropriate extension $f_{m+1}$, without an explicit definition and without a definable way to choose among the (possibly many) available $f_m$'s. In such a situation, it seems the axiom of dependent choice would be needed. $\endgroup$ – Andreas Blass Nov 19 '13 at 18:54
  • $\begingroup$ @Andreas: Good point; I was sloppy. Better now? $\endgroup$ – Brian M. Scott Nov 19 '13 at 18:59
  • $\begingroup$ Yes, definitely better. $\endgroup$ – Andreas Blass Nov 19 '13 at 20:16
  • 1
    $\begingroup$ @Patrick: It sounds to me as if you’re using dependent choice. I can’t imagine why the reviewers care, however, unless use of choice is explicitly at issue in the paper; outside of explicitly foundational set-theoretic areas, the axiom of choice is a normal, unproblematic part of mathematics. $\endgroup$ – Brian M. Scott Nov 20 '13 at 0:43
  • 1
    $\begingroup$ @Patrick: We can hope! $\endgroup$ – Brian M. Scott Nov 20 '13 at 1:03

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.