<p>There is no need for the axiom of choice here. The proof that the rational numbers are countable does not make use of the axiom of choice, and there are even <a href="https://math.stackexchange.com/questions/7643/produce-an-explicit-bijection-between-rationals-and-naturals">very concrete enumerations</a> available. And that is all we need to define <span class="math-container">$q$</span> explictely.</p>
<p>So let <span class="math-container">$(q_n)$</span> be an enumeration of the rational numbers. You can then  define <span class="math-container">$q:\mathbb{R}\to \mathbb{Q}$</span> explicitly by letting <span class="math-container">$q(a)$</span> be the first rational in  <span class="math-container">$(u((a,0)),u((a,1)))$</span> under this enumeration. No &quot;arbitrary choice&quot; is involved in this argument.</p>

CC BY-SA 4.0
2024-10-07T01:57:08.930Z
2024-10-07T01:57:08.930Z
Michael Greinecker
<p>In the proof of the theorem about lexicographic preferences in your question, the <em><strong>Axiom of Choice (AC)</strong></em> is necessary, and it is implicitly used, as we are constructing a function through an infinite number of arbitrary choices, as you pointed out in your question.</p>
<p>The point is that the <em>AC</em> is often taken for granted in many proofs.</p>
<p>The most part of mathematicians don’t mention the use of the <em>AC</em>  when they use it in  their proofs: they are aware they  use it, but they use it implicitly, I think because they consider  making it  explicit a pedantic complication and believe the fact that they are using it rather obvious.</p>
<p>Munkres, J. R., <em>Topology</em>, 2nd  ed., Prentice Hall, p. 60, describes the attitude of mathematicians towards the <em>AC</em> in the following way:</p>
<blockquote>
<p>Having emphasized that in order to construct a proof of Theorem <span class="math-container">$9.1$</span>
that is logically correct, one must made specific use of a choice function,  we now backtrack and admit  that in
practice most mathematicians do no such thing. They go on with no
qualms giving proofs […] that involve an infinite number of arbitrary
choices. They know that they are really using the choice axiom;  and
they know that if it were necessary, they could put their proofs into
a logically more satisfactory form, by introducing a choice function
specifically. But they usually do not bother.</p>
<p>And neither will we. You will find  few  further specific uses of a choice function in this book; we shall introduce a choice function only when the proof would become confusing without it. But there will be many proofs in which we make an infinite number of arbitrary choices, and in each such case we will actually be using the choice axiom implicitly.</p>
</blockquote>
<p>The <em>AC</em> is explicitly mentioned, instead, in  many important theorems, where the proofs would be unintelligible  or impossible without mentioning it, and usually   the <em>AC</em> in these theorems is used in the equivalent form of the <a href="https://en.wikipedia.org/wiki/Zorn%27s_lemma" rel="nofollow noreferrer"><em><strong>Zorn’s Lemma</strong></em></a>: Zorn’s lemma is far from obvious or intuitive.</p>
<p>Two well-known proofs that use the <em>AC</em> are the proofs of the theorem that <em><strong>every  non empty vector space has a basis</strong></em> and the <strong>Hahn-Banach theorem</strong> in its analytic form (in both the <em>AC</em> is used in the form of Zorn’s Lemma).</p>
<p>Sometimes  the use of <em>AC</em> is implicit and unconscious.  There are examples of proofs of theorems preceding the formulation of the <em>AC</em> that make unaware use of the  <em>AC</em>, and even some  mathematicians who rejected the <em>AC</em>, as <a href="https://en.wikipedia.org/wiki/G._H._Hardy" rel="nofollow noreferrer">G. H. Hardy</a>, actually   used unconsciously the <em>AC</em> in some proof.</p>
<p>See Herrlich, H., <em>Axiom of Choice</em>, Springer, 2006,  to which you can refer to read about  all the intricacies related to the <em>AC</em> and its tormented history: the <em>AC</em> is one of the most controversial subjects of the history of mathematics.</p>

CC BY-SA 4.0
2024-10-07T18:39:51.400Z
What if the infinitely many choices are *not arbitrary* but explicitly provided. For example, for each $a\in\mathbb R$ we define $q(a)$ as follows: Let 
\begin{align}
\underline q(a) & = \inf \Bigl[(u((a,0)), u((a,1))) \cap \mathbb Q \Bigr] \\
\overline q(a) & = \sup \Bigl[(u((a,0)), u((a,1))) \cap \mathbb Q \Bigr] 
\end{align}
and define 
\begin{equation}
q(a) := \frac{\underline q(a)+\overline q(a)}{2}
\end{equation}
Clearly, $\underline q, \overline q, q\in\mathbb Q$, satisfying the requirement of the proof. Would this construction spare the necessity of AC then?
Herr K.
CC BY-SA 4.0
2024-10-07T19:53:19.717Z
@Herr K. If one can show an effective choice, that is a rule that determines a unique member, the AC is not needed. I have to think about your example, because it is not granted that the sup and the inf of a set of rational numbers is rational.
When I answered I had in mind that fact that when we have  choices in general infinite countable sets, the AC is needed, as far as I know. If we have more information about the structure of the sets, as for $\mathbb{Q}$, we can try to find a choice rule.
BakerStreet
CC BY-SA 4.0
2024-10-07T21:03:57.220Z
in the answer of Greinecker are indicated some possibilities, I have to think about it, if it is possible using particular bijections find a rule to establish, to pick effectively, the ‘first’ (according to the bijection) rational in an interval. To what extent is 'constructive'. AC is really intricated. –
BakerStreet
CC BY-SA 4.0
2024-10-08T03:23:42.970Z
Thanks for pointing out the issue with $\inf$ and $\sup$. I think changing them to $\min$ and $\max$ (and open interval to closed) should fix it: 
\begin{align}
\underline q(a) & = \min\Bigl\{\Bigl[u((a,0)), u((a,1))\Bigr] \cap \mathbb Q\Bigr\}  \\
\overline q(a) & = \max\Bigl\{\Bigl[u((a,0)), u((a,1))\Bigr] \cap \mathbb Q \Bigr\} 
\end{align}
This should guarantee that $\underline q,\overline q\in\mathbb Q$ and that their "midpoint" is in the open interval.
Herr K.
CC BY-SA 4.0
2024-10-08T06:49:05.610Z
@HerrK. I think the $\min$ and $\max$ still have issues, the set $[0,\sqrt{2}]\cap \mathbb{Q}$ has no maximal rational, for example. There is always a rational in the interval  $(\sqrt{2}-1/n,\sqrt{2})$ for any $n\in \mathbb{N}$, by density.
Joseph Basford
CC BY-SA 4.0
2024-10-08T06:53:05.930Z
@BakerStreet I think Greinecker had in mind the following. As $\mathbb{Q}$ is countable, there exists a bijective map $f:\mathbb{N}\to \mathbb{Q}$. This is arbitrarily chosen, but there is only one choice to make so no need for AC. So, enumerate $\mathbb{Q}$ as $\{q_1,q_2,\dots\}$. Define $q:\mathbb{R}\to \mathbb{Q}$ as $$q(a)=\{q_i: \ q_i\in (u((a,0)),u((a,1))) \text{ and } \nexists j<i \text{ st. } q_j \in (u((a,0)),u((a,1))) \}$$
Joseph Basford
CC BY-SA 4.0
2024-10-08T12:26:15.720Z
@Yes yes, you choose once a specific, concrete, enumeration., and avoid multiple choices. I was wondering how, through the formula, an algorithm, you can pick, practically, the first rational of the interval, according to the bijection. You have to enumerate all rationals from 0, 1,2, ... and so on, to the point you reach a natural $n$ that is in the interval. $n$ could be enormous and the task take centuries. But from a logical point of view is right.
BakerStreet
CC BY-SA 4.0
2024-10-06T13:37:18.080Z
2024-10-06T13:37:18.080Z
BakerStreet
<p>I am once again thinking about the proof that lexicographic preferences over <span class="math-container">$\mathbb{R}^2$</span> have no utility representation. The proof I have seen is the following.</p>
<blockquote>
<p>Suppose that there does exists <span class="math-container">$u:\mathbb{R}^2\to \mathbb{R}$</span> which represents the lexicographic preferences (seeking a contradiction). Then, for any <span class="math-container">$a\in \mathbb{R}$</span>, <span class="math-container">$(a,1)\succ (a,0)$</span>, so <span class="math-container">$u((a,1))&gt;u((a,0))$</span>. By density of the rationals, <span class="math-container">$\exists q \in \mathbb{Q}$</span> such that <span class="math-container">$u((a,1))&gt;q&gt;u((a,0))$</span>. This defines a function <span class="math-container">$q:\mathbb{R}\to \mathbb{Q}$</span> with <span class="math-container">$q(a)\in (u((a,0)),u((a,1)))$</span> for any <span class="math-container">$a\in \mathbb{R}$</span>. This function is injective. But this would imply <span class="math-container">$\mathbb{Q}$</span> is uncountable, a contradiction.</p>
</blockquote>
<p>The problem I've had with understanding this proof is the statement &quot;This defines a function <span class="math-container">$q:\mathbb{R}\to \mathbb{Q}\dots$</span>&quot;. I can't understand why this doesn't require the Axiom of Choice (AoC) to construct.</p>
<p>My (admittedly shaky) understanding of the AoC is that it allows us to pick one element from any collection of sets, and is required when we want to pick elements from an uncountable collection of sets. Is this not what we are doing here? We have the uncountable collection of non-empty sets <span class="math-container">$\{(u((r,0)),u((r,1)))\cap\mathbb{Q}\}_{r\in \mathbb{R}}$</span> and want to pick one element from each of these. I admit my understanding of the AoC is not strong, so perhaps explaining exactly when it is required would clear up my misunderstanding.</p>

CC BY-SA 4.0
2024-10-05T11:28:22.513Z
Isn't $q(a)$ both injective as well as strictly increasing?
Amit
CC BY-SA 4.0
2024-10-05T11:45:02.810Z
Who said that the axiom of choice is not necessary here? At first sight, it seems to me necessary. The point is that the axiom of choice is often take for granted in many proofs.
BakerStreet
CC BY-SA 4.0
2024-10-05T15:27:57.787Z
@Amit The reason $q(a)$ is injective is because it is strictly increasing. My problem is why such a function $q$ exists in the first place.
Joseph Basford
CC BY-SA 4.0
2024-10-05T15:31:08.907Z
@BakerStreet I have just never seen it explicitly mentioned that the AoC is used in the proof and took this absence to imply it was not needed. If it is needed in this particular proof, is it true that any proof will require AoC at some point?
Joseph Basford
CC BY-SA 4.0
2024-10-05T15:35:00.487Z
@ I think it is not mentioned because often mathemaricians dont' mention it in many proofs. Not *every* proof requires the axiom of choice, but only proofs that involve an infinite number of arbitrary choices, as constructing that function in your proof.
BakerStreet
CC BY-SA 4.0
2024-10-05T15:45:03.313Z
They consider in most cases an unnecessary complication to mention it, they consider its use  rather obvious.
BakerStreet
CC BY-SA 4.0
2024-10-05T15:59:53.293Z
@BakerStreet Sorry for being unclear, I meant does every proof that lexicographic preferences cannot be represented by a utility function require AoC at some point? That is, is AoC necessary for any proof of this fact, or is there a more constructive proof? I find its use very non-obvious!
Joseph Basford
CC BY-SA 4.0
2024-10-05T16:23:29.880Z
I know the proof in MasColell, that is actually the same as your proof. I saw a proof in Rubistein, *Lecture notes in Microeconomic theory*,  slightly different, but it seems to me substantially the same. I don' know if there are other proofs really different.
BakerStreet
CC BY-SA 4.0
2024-10-05T16:27:08.407Z
The axiom of choice is of course a not obvious axiom, it has a tormented history, but one must or accept it, or not accept it. Once accepted, its use is in most cases rather obvious.
BakerStreet
CC BY-SA 4.0
2024-10-05T16:36:43.420Z
If you don't accept it, you have to renounce many important parts of mathematics!
BakerStreet
CC BY-SA 4.0
2024-10-06T09:22:40.087Z
@BakerStreet I suppose I was wondering whether the AoC is needed for this proof in the same sense it is necessary for the construction of the Vitali set or proving Tychonoff's theorem. But this wasn't my original question. If you write an answer saying that AoC is necessary in this proof, I will accept it.
Joseph Basford
CC BY-SA 4.0
2024-10-06T11:59:01.700Z
Ok, thank you Basford. The AC is really a complicated matter. When I said that the use of the AC is in many cases rather obvious, of course I referred to simpler theorems as the theorem about lexicographic preferences,  not to important theorems as Tychonoff. In these theorems the use of AC is by no means trivial, the AC is often used in the equivalent form of the Zorn’s Lemma, which is certainly not obvious.
BakerStreet
<microeconomics><mathematical-economics><utility><preferences>
Lexicographic Preferences and The Axiom of Choice
Joseph Basford
# Lexicographic Preferences and The Axiom of Choice

(Asked by: username_0 on 2024-10-05)

I am once again thinking about the proof that lexicographic preferences over $\mathbb{R}^2$ have no utility representation. The proof I have seen is the following.

> Suppose that there does exists $u:\mathbb{R}^2\to \mathbb{R}$ which represents the lexicographic preferences (seeking a contradiction). Then, for any $a\in \mathbb{R}$, $(a,1)\succ (a,0)$, so $u((a,1))>u((a,0))$. By density of the rationals, $\exists q \in \mathbb{Q}$ such that $u((a,1))>q>u((a,0))$. This defines a function $q:\mathbb{R}\to \mathbb{Q}$ with $q(a)\in (u((a,0)),u((a,1)))$ for any $a\in \mathbb{R}$. This function is injective. But this would imply $\mathbb{Q}$ is uncountable, a contradiction.

The problem I've had with understanding this proof is the statement "This defines a function $q:\mathbb{R}\to \mathbb{Q}\dots$". I can't understand why this doesn't require the Axiom of Choice (AoC) to construct.

My (admittedly shaky) understanding of the AoC is that it allows us to pick one element from any collection of sets, and is required when we want to pick elements from an uncountable collection of sets. Is this not what we are doing here? We have the uncountable collection of non-empty sets $\{(u((r,0)),u((r,1)))\cap\mathbb{Q}\}\_{r\in \mathbb{R}}$ and want to pick one element from each of these. I admit my understanding of the AoC is not strong, so perhaps explaining exactly when it is required would clear up my misunderstanding.

**Tags:** microeconomics, mathematical-economics, utility, preferences
> **Comments:**
> **username_1**: Isn't $q(a)$ both injective as well as strictly increasing?  
> **username_2**: Who said that the axiom of choice is not necessary here? At first sight, it seems to me necessary. The point is that the axiom of choice is often take for granted in many proofs.  
> **username_0**: @Amit The reason $q(a)$ is injective is because it is strictly increasing. My problem is why such a function $q$ exists in the first place.  
> **username_0**: @BakerStreet I have just never seen it explicitly mentioned that the AoC is used in the proof and took this absence to imply it was not needed. If it is needed in this particular proof, is it true that any proof will require AoC at some point?  
> **username_2**: @ I think it is not mentioned because often mathemaricians dont' mention it in many proofs. Not *every* proof requires the axiom of choice, but only proofs that involve an infinite number of arbitrary choices, as constructing that function in your proof.  
> **username_2**: They consider in most cases an unnecessary complication to mention it, they consider its use  rather obvious.  
> **username_0**: @BakerStreet Sorry for being unclear, I meant does every proof that lexicographic preferences cannot be represented by a utility function require AoC at some point? That is, is AoC necessary for any proof of this fact, or is there a more constructive proof? I find its use very non-obvious!  
> **username_2**: I know the proof in MasColell, that is actually the same as your proof. I saw a proof in Rubistein, *Lecture notes in Microeconomic theory*,  slightly different, but it seems to me substantially the same. I don' know if there are other proofs really different.  
> **username_2**: The axiom of choice is of course a not obvious axiom, it has a tormented history, but one must or accept it, or not accept it. Once accepted, its use is in most cases rather obvious.  
> **username_2**: If you don't accept it, you have to renounce many important parts of mathematics!  
> **username_0**: @BakerStreet I suppose I was wondering whether the AoC is needed for this proof in the same sense it is necessary for the construction of the Vitali set or proving Tychonoff's theorem. But this wasn't my original question. If you write an answer saying that AoC is necessary in this proof, I will accept it.  
> **username_2**: Ok, thank you Basford. The AC is really a complicated matter. When I said that the use of the AC is in many cases rather obvious, of course I referred to simpler theorems as the theorem about lexicographic preferences,  not to important theorems as Tychonoff. In these theorems the use of AC is by no means trivial, the AC is often used in the equivalent form of the Zorn’s Lemma, which is certainly not obvious.  

---

## 2 answers

### Answer by username_3 on 2024-10-07. Score: 2 | Accepted answer

There is no need for the axiom of choice here. The proof that the rational numbers are countable does not make use of the axiom of choice, and there are even [very concrete enumerations](https://math.stackexchange.com/questions/7643/produce-an-explicit-bijection-between-rationals-and-naturals) available. And that is all we need to define $q$ explictely.

So let $(q\_n)$ be an enumeration of the rational numbers. You can then define $q:\mathbb{R}\to \mathbb{Q}$ explicitly by letting $q(a)$ be the first rational in $(u((a,0)),u((a,1)))$ under this enumeration. No "arbitrary choice" is involved in this argument.


---

### Answer by username_2 on 2024-10-06. Score: 2

In the proof of the theorem about lexicographic preferences in your question, the ***Axiom of Choice (AC)*** is necessary, and it is implicitly used, as we are constructing a function through an infinite number of arbitrary choices, as you pointed out in your question.

The point is that the *AC* is often taken for granted in many proofs.

The most part of mathematicians don’t mention the use of the *AC* when they use it in their proofs: they are aware they use it, but they use it implicitly, I think because they consider making it explicit a pedantic complication and believe the fact that they are using it rather obvious.

Munkres, J. R., *Topology*, 2nd ed., Prentice Hall, p. 60, describes the attitude of mathematicians towards the *AC* in the following way:

> Having emphasized that in order to construct a proof of Theorem $9.1$
> that is logically correct, one must made specific use of a choice function, we now backtrack and admit that in
> practice most mathematicians do no such thing. They go on with no
> qualms giving proofs […] that involve an infinite number of arbitrary
> choices. They know that they are really using the choice axiom; and
> they know that if it were necessary, they could put their proofs into
> a logically more satisfactory form, by introducing a choice function
> specifically. But they usually do not bother.
>
> And neither will we. You will find few further specific uses of a choice function in this book; we shall introduce a choice function only when the proof would become confusing without it. But there will be many proofs in which we make an infinite number of arbitrary choices, and in each such case we will actually be using the choice axiom implicitly.

The *AC* is explicitly mentioned, instead, in many important theorems, where the proofs would be unintelligible or impossible without mentioning it, and usually the *AC* in these theorems is used in the equivalent form of the [***Zorn’s Lemma***](https://en.wikipedia.org/wiki/Zorn%27s_lemma): Zorn’s lemma is far from obvious or intuitive.

Two well-known proofs that use the *AC* are the proofs of the theorem that ***every non empty vector space has a basis*** and the **Hahn-Banach theorem** in its analytic form (in both the *AC* is used in the form of Zorn’s Lemma).

Sometimes the use of *AC* is implicit and unconscious. There are examples of proofs of theorems preceding the formulation of the *AC* that make unaware use of the *AC*, and even some mathematicians who rejected the *AC*, as [G. H. Hardy](https://en.wikipedia.org/wiki/G._H._Hardy), actually used unconsciously the *AC* in some proof.

See Herrlich, H., *Axiom of Choice*, Springer, 2006, to which you can refer to read about all the intricacies related to the *AC* and its tormented history: the *AC* is one of the most controversial subjects of the history of mathematics.

> **Comments:**
> **username_4**: What if the infinitely many choices are *not arbitrary* but explicitly provided. For example, for each $a\in\mathbb R$ we define $q(a)$ as follows: Let  \begin{align} \underline q(a) & = \inf \Bigl[(u((a,0)), u((a,1))) \cap \mathbb Q \Bigr] \\ \overline q(a) & = \sup \Bigl[(u((a,0)), u((a,1))) \cap \mathbb Q \Bigr]  \end{align} and define  \begin{equation} q(a) := \frac{\underline q(a)+\overline q(a)}{2} \end{equation} Clearly, $\underline q, \overline q, q\in\mathbb Q$, satisfying the requirement of the proof. Would this construction spare the necessity of AC then?  
> **username_2**: @Herr K. If one can show an effective choice, that is a rule that determines a unique member, the AC is not needed. I have to think about your example, because it is not granted that the sup and the inf of a set of rational numbers is rational. When I answered I had in mind that fact that when we have  choices in general infinite countable sets, the AC is needed, as far as I know. If we have more information about the structure of the sets, as for $\mathbb{Q}$, we can try to find a choice rule.  
> **username_2**: in the answer of Greinecker are indicated some possibilities, I have to think about it, if it is possible using particular bijections find a rule to establish, to pick effectively, the ‘first’ (according to the bijection) rational in an interval. To what extent is 'constructive'. AC is really intricated. –  
> **username_4**: Thanks for pointing out the issue with $\inf$ and $\sup$. I think changing them to $\min$ and $\max$ (and open interval to closed) should fix it:  \begin{align} \underline q(a) & = \min\Bigl\{\Bigl[u((a,0)), u((a,1))\Bigr] \cap \mathbb Q\Bigr\}  \\ \overline q(a) & = \max\Bigl\{\Bigl[u((a,0)), u((a,1))\Bigr] \cap \mathbb Q \Bigr\}  \end{align} This should guarantee that $\underline q,\overline q\in\mathbb Q$ and that their "midpoint" is in the open interval.  
> **username_0**: @HerrK. I think the $\min$ and $\max$ still have issues, the set $[0,\sqrt{2}]\cap \mathbb{Q}$ has no maximal rational, for example. There is always a rational in the interval  $(\sqrt{2}-1/n,\sqrt{2})$ for any $n\in \mathbb{N}$, by density.  
> **username_0**: @BakerStreet I think Greinecker had in mind the following. As $\mathbb{Q}$ is countable, there exists a bijective map $f:\mathbb{N}\to \mathbb{Q}$. This is arbitrarily chosen, but there is only one choice to make so no need for AC. So, enumerate $\mathbb{Q}$ as $\{q_1,q_2,\dots\}$. Define $q:\mathbb{R}\to \mathbb{Q}$ as $$q(a)=\{q_i: \ q_i\in (u((a,0)),u((a,1))) \text{ and } \nexists j<i \text{ st. } q_j \in (u((a,0)),u((a,1))) \}$$  
> **username_2**: @Yes yes, you choose once a specific, concrete, enumeration., and avoid multiple choices. I was wondering how, through the formula, an algorithm, you can pick, practically, the first rational of the interval, according to the bijection. You have to enumerate all rationals from 0, 1,2, ... and so on, to the point you reach a natural $n$ that is in the interval. $n$ could be enormous and the task take centuries. But from a logical point of view is right.  

---

