3
$\begingroup$

I am having a hard time understanding the Axiom of Choice(AC).

Say I have an index set $A$ , and a collection of indexed sets {${V_\alpha}$}, where $\alpha$ is a member of $A$.

Then, does the difficulty of defining a "choice function" come from the fact that

(a) elements of each set $V_\alpha$ in the collection might not be "ordered" (in some sense) so that whoever is constructing a choice function is not sure which element to choose from each set?

OR

(b) the collection might be uncountably infinite so that there seems to be no systematic way to go through each set (without missing one) in the collection?

Or

(c) Is it both?

As an illustration of my confusion with AC, please consider the following examples.

(1) If I want to prove that the square of a real number is always non-negative, then I would begin my proof by saying that "Pick any real number $x$." Here, am I using AC? I am "choosing" an element from the set of real numbers $R$, but I am not specifying "how" so I feel that I am using AC. On the other hand, however, since I only have one set $R$, it seems intuitively obvious that I can just "grab" any element from the set without a problem.

(2) Here is the proof by Rudin of the theorem that monotonic functions have at most countable discontinuities. enter image description here When Rudin writes that "with every point x of E, we associate a rational number $r(x)$", is he using AC here? If I can somehow associate a natural number n(x) with every point x of E, would I still be using AC?

I am sorry if my questions are a bit all over the place, but I would appreciate it very much if you could help me understand AC!

$\endgroup$

5 Answers 5

Reset to default
3
$\begingroup$

First of the bat, using $V_\alpha$ is extremely bad notation. These sets have a very special meaning in set theory, and they are "the building blocks of the universe of sets". But let me gloss over this issue now, as it's unimportant for the rest of your question.

Choosing one element does not invoke the axiom of choice. Instead it invokes the rules of first-order logic. We can prove that "there exists a real number" therefore we can instantiate this existential quantifier and actually "pick" a real number. We choose one real number, so it's fine.

Even choosing an infinite collection of real numbers can be easy, because you in fact choose one subset. If you can prove that a subset with the properties that you would like exists (without using the axiom of choice), then you don't need the axiom of choice for it. For example, I can always prove that there is a countably infinite subset of any interval in the real numbers. So I can write "let $\{x_n\mid n\in\Bbb N\}\subseteq [0,1]$" without invoking the axiom of choice. I instantiated a single existential quantifier.

But in general, choosing from infinitely many different sets can be proved as an impossible task without the axiom of choice. Sometimes, not always. If there is a way to give some structure to all the sets at once, in such way that we can choose from each set, then we don't need the axiom of choice. For example if all the sets are sets of positive integers, then we can choose the least in each set.

On the other hand, if you are told that these are arbitrary sets, then you can't do that. In fact, even if you're told that each of the sets is finite, or god forbid, consists of two points, you still can't make a canonical choice, because you first have to choose how to endow each set with a structure. Only if you can endow all the sets at the same time with some structure, then you can make a choice without invoking the axiom.

More specifically to Rudin's proof. We know that the rational numbers are countable, so we can write them as $\{q_n\mid n\in\Bbb N\}$. Therefore from each non-empty set of rational numbers we can choose the rational number whose index in that enumeration is minimal in that set. So in order to associate a rational number to $x$ we just need to prove that a rational number exists between $f(x-)$ and $f(x+)$, but that set is an interval so it includes a rational number. So the axiom of choice is not used.

$\endgroup$
6
  • 1
    $\begingroup$ We did not even have to choose one of the many enumerations of $\mathbb Q$ (which would be valid to do because we choose just one where the existence of it is granted by the statement that $\mathbb Q$ is countable). Instead we may remember that $\mathbb Q$ is not just "some" countable set, but we once have proved the very fact that $\mathbb Q$ is countable by means of an explicit map $\mathbb N\to \mathbb Q$. $\endgroup$
    – Hagen von Eitzen
    May 2, 2014 at 7:40
  • $\begingroup$ @AsafKaragila If choosing one element from a set does not require the axiom of choice, why would it be difficult to choose one element from each set in the arbitrary collection of sets? I can simply say that for each element $a$ from the index set, the corresponding set $V_a$ is nonempty so there exists an element $\alpha$ in $V_a$, hence I can define a choice function as $f(a) = \alpha$. $\endgroup$
    – mononono
    May 3, 2014 at 8:24
  • 1
    $\begingroup$ @user144840: No, choosing from one set is done by instantiating an existential quantifier. But here you don't have an existential quantifier to instantiate, because your family is not [necessarily] finite. It's just a collection of sets satisfying $\forall x(x\in X\rightarrow\exists y(y\in x))$, where $X$ is a family of non-empty sets. The "map" which instantiates the quantifier is not within the set theoretical universe, it happens outside, in the meta theory. So you can't use it to define a function inside the set theoretical universe. $\endgroup$
    – Asaf Karagila ♦
    May 3, 2014 at 8:29
  • $\begingroup$ @AsafKaragila If my family happens to be finite, then would I have an existential quantifier to instantiate a choice map? If so, are you saying that what determines whether the axiom of choice is needed is NOT whether each set in the collection has some structure or not BUT whether the collection is finite or not? $\endgroup$
    – mononono
    May 3, 2014 at 8:56
  • $\begingroup$ @user144840: No, you're misunderstanding my comment and answer. If there is a global structure on your sets, then you can prove the existence of a choice function, you don't need to resort to instantiation of quantifiers. If the family is finite, then you can prove by induction on its size that there is a choice function. This is better than instantiating quantifiers because the universe of sets might disagree on what "finite" means with the meta theory (it might have non-standard integers), in which case instantiation can only take you so far [...] $\endgroup$
    – Asaf Karagila ♦
    May 3, 2014 at 9:02
2
$\begingroup$

Your confusion is understandable, but the "axiom of single (or finite) choice" is none. It is rather a consequence of the rules of inference (Existential Elimination) we hold valid for the existential quantifier: $$ \begin{align}\exists \alpha\colon\phi(\alpha)\\\underline{\phi(\beta/\alpha)\vdash\psi}\\\psi\end{align}$$ If you have $\exists x\colon \phi(x)$ the it is valid to pick "some" $x$ such that $\phi(x)$ and keep on proving things, and finally you have that there exists $x$ such that whatever you have shown. This can be repeated for finitely many choices, but not more (as that would require infinitely many proof steps, or even an infitely long premise $\exists x_1\exists x_2\exists x_3\ldots$). This is maybe comparabele that we can join finitely many true statements by and ($\phi_1,\phi_2,\ldots,\phi_n\vdash \phi_1\land\phi_2\land\ldots\land\phi_n$) because the rules of inference allow this for the basic case of two statements, but this is not allowed for an "infinite and", the allquantor.

And yet the Axiom of Choice comes in several shades that indeed have different strength (i.e. there are theorems that can be proven only with the stronger versions), e.g. Axiom of Countable choice (for countable index sets) or the Axiom of Dependent Choice. So in this sense only part of the problematic of choice comes from the fact that the index set might be larger than $\mathbb N$. The main problem really (even in the countable index case) is that the individual $V_\alpha$ in general do not allow to pick a canonical element (such as the smallest one or the unique one with a specific property, anything we could write donw explicitly as an algorithm really).

$\endgroup$
1
$\begingroup$

I think that the guiding principle is that if you can write a finite specification for what you want to choose then you don't need to rely on AC. To pick a real number, you write a specification

{$x \in R: x = 2.745 $}, or whatever.

If you want to pick elements from a finite collection of infinite sets you can compose a finite number of clauses to do so.

If you have an infinite number of choices to make then you might have a common way to make the choice (e.g. take the first element from each set in an infinite collection of ordered sets, the left from each pair in an infinite collection of shoes) which allows you to write a finite specification.

Otherwise, you can rely on AC to say that a set can be formed comprising one element from each set in a (infinite) collection.

$\endgroup$
0
$\begingroup$

For the first part, I think that the difficulty comes from the order. Whether the set is finite or infinite doesn't really matter so long as you have established an ordering. You can have a partial order (poset) or a strict order (i.e. trichotomy).

I think the cardinality of the set matters only insofar as the number of possible orderings (i.e. permutations of the elements) you can come up with for any given set.

The book "Tools of the Trade" by Paul Sally has an excellent discussion on the AC and once I have more time, I will edit this to reproduce what he is saying.

$\endgroup$
0
$\begingroup$

Even if the question has been posted a long time ago, I would like to add an answer for other people facing the same issue.

Indeed, in the particular case of Rudin's proof, there is actually a constructive way to build the rational $r(x)$. To see that, assume you are given to real numbers $a<b$, and you want to find explicitly a rational between $a$ and $b$ such that its expression only depends on $a$ and $b$. The easiest way is to choose it around the middle $m:=\frac{a+b}{2}$ of the interval (note that $m$ explicitly depends on $a$ and $b$). Therefore, one begins with approximating this middle point by the sequence of rational numbers $(m_n)_n$ obtained by truncating the decimal part of $m$ after the $n$-th decimal digit, that is: $$ m_n:=m-\left(\frac{10^nm-E(10^nm)}{10^n}\right)=\frac{E(10^nm)}{10^n} $$ here $E(\cdot)$ stands for the integer part of a real number. Of course, $m_n$ are all rational numbers as it is shown by the right hand side of the above equation. Moreover, when $n$ goes to infinity, $m_n$ converges to $m$. Thus one could say that for a sufficiently large $n$, $m_n$ belongs to $]a,b[$ because $m$ already belongs to $]a,b[$. Yes, but this result is actually obvious by density of $\mathbb{Q}$, and recall that the goal here is to find an explicit value for our rational number. So one has to compute the value of $n$ in terms of $a$ and $b$ that will be large enough to get $m_n\in]a,b[$. Because $m_n\leq m$ for each $n$, one has $$ m_n\in]a,b[\Leftrightarrow a<m_n\leq m\Leftrightarrow a-m<m_n-m\leq 0\Leftrightarrow 0\leq m-m_n<m-a\Leftrightarrow \frac{10^nm-E(10^nm)}{10^n}<\frac{b-a}{2} $$ But because $\forall x\in\mathbb{R},x-E(x)<1$, we have $\frac{10^nm-E(10^nm)}{10^n}<10^{-n}$, and so a sufficient condition to get the last property of the equivalence sequence is $10^{-n}\leq\frac{b-a}{2}$, which is equivalent to $n\geq-\log_{10}(\frac{b-a}{2})$. Therefore, setting for instance $$ n:= E(-\log_{10}(\frac{b-a}{2}))+1 $$ one has $10^{-n}\leq\frac{b-a}{2}$, so $\frac{10^nm-E(10^nm)}{10^n}<\frac{b-a}{2}$, and finally $m_n\in]a,b[$. To conclude, the expression of our rational number is the following, which indeed only depends on $a$ and $b$: $$ \frac{E(\frac{a+b}{2}10^{E(-\log_{10}(\frac{b-a}{2}))+1})}{10^{E(-\log_{10}(\frac{b-a}{2}))+1}} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .