Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the proof of 'Every open set in $\mathbb{R}^1$ is a countable union of disjoint open intervals', we need to pick one rational representative from each of the intervals hence establish the countability.

This seems to depend on the axiom of choice.

Thus I wonder does this property of $\mathbb{R}$ is equivalent to the axiom of choice, that is, is there any construction such that this property is not true once we abandon the axiom of choice?

Thanks!

share|improve this question

2 Answers 2

up vote 7 down vote accepted

There are $\pi$ points here:

  1. Given an interval $(a,b)$ we can write all the rationals in it as $\dfrac{p}{q}$ where $q>0$ and $\gcd(p,q)=1$. Now let $n$ be the minimal $q$ appearing in all those rationals, then find $m\in\mathbb Z$ such that $|m|$ is minimal in the set of all the rationals in $(a,b)$ with $n$ in the denominator.

    The resulting rational $\dfrac{m}{n}$ is in $(a,b)$ and we have constructed it without the axiom of choice. Note that one can write simpler, perhaps, functions like the least $n\in\mathbb N$ that $q=\dfrac1n$ for which $a<\lfloor a\rfloor+q<b$ (this is guaranteed to exist since $0\le a-\lfloor a\rfloor<b-a$, and we can find some rational there).

  2. If $U$ is an open set it can be written as $\bigcup\{U_x\mid x\in U, U_x\text{ basic open set}\}$. Now consider the fact that $\mathbb Q\times\mathbb Q$ is countable without does not require the axiom of choice, thus there are still only countably many intervals $(a,b)$ in $\mathbb R$ such $a,b\in\mathbb Q$.

    We can, if so, write the interval $(s,t)=\bigcup\{(a,b)\mid a,b\in\mathbb Q\cap(s,t)\}$, that is the union of all possible subintervals of $(s,t)$ whose endpoints are rational.

  3. If one wants to write $U$ as a disjoint union, one can enumerate $\{(a,b)\subseteq U\mid a,b\in\mathbb Q\}$ as $U_n, n\in\mathbb N$ and define $\mathcal A=\{U_n\mid\forall k<n:U_n\cap U_k=\varnothing\}$, this does not require the axiom of choice. We now define a relation on $\mathcal A$ which will be an equivalence relation:

    Let $U_n \# U_k$ if they share an endpoint. This is a reflexive and symmetric relation. Let $\sim$ be its transitive closure (again, no use of the axiom of choice since this can be defined without it). Now we have an equivalence relation on $\mathcal A$, such that the union of every equivalence relation is an interval, they are disjoint, and there are only be countably many since $\mathcal A$ was countable to begin with. We wrote $U$ as the countable union of disjoint intervals.

Lastly, properties holding for small collections (i.e. sets of a bounded size, like $\mathbb R$) are not usually equivalent to the axiom of choice, as we can construct a model in which the axiom of choice holds for everything of cardinality at most $|P(P(P(P(P(P(P(P(P(P(P(P(P(P(P(P(P(\mathbb R)))\ldots)|$ but will fail for some sets larger than this cardinality.


I should probably add another method to replace the first step, which is cleaner although less algorithmic in nature.

We know that the rational numbers are countable, so we can enumerate them $\{q_n\mid n\in\mathbb N\}$.

Note that every non-empty open set (in particular non-devenerate intervals) has at least one rational number inside, so for an open set $U$ simply let $q_U$ be $q_k$ where $k=\min\{n\in\mathbb N\mid q_n\in U\}$.

share|improve this answer

It is not necessary to pick more than one point in each interval, but

  • It is harmless to pick more than one, or even all of them, and
  • There is a simple algorithm for choosing one from each interval, so no reliance on the axiom of choice is needed. Just take any computable enumeration of the rationals, and let the first rational to fall in a particular interval be the one chosen for that interval.
share|improve this answer
    
Thanks! As for the second point, do you mean that once we have a clear algorithm for 'choosing', then we do not rely on the axiom of choice? –  Hui Yu Jan 14 '12 at 2:45
2  
That's correct. –  Dustan Levenstein Jan 14 '12 at 3:21
    
@Hui: See my answer for such algorithm (there are many different ones, this is just an example). –  Asaf Karagila Jan 14 '12 at 7:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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